lea/10_memory の変更点

追加された行はこの色です。
削除された行はこの色です。
lea/10_memory へ行く。
lea/10_memory の差分を削除
 **メモリ管理(この記事は2008年8月21日に出現しました)
 ***今の実装
 -「9日目」終了。「10日目」半分弱くらい終わったあたりと仮定
 -構造体が丁度1026Byteだったり4100Byteだったりすると凄く悲しいので、~
 とりあえず1Byte単位で確保/解放できるようにしてみた。~
 メモリの無駄は嫌だからね
 
 ***今日の料理
 とりあえずメモリは限られてるんだし、メモリ管理をもう少し真面目にやるか~
 解放ミスしたらその分は全く使えないのは痛いよなぁ・・・~
 よし、解放ミスした分もあとで復活できるようにするか~
 
 ***失われたメモリ、どうするよ？
 あの有名な黄緑本の初版で言うところの189ページ(9章4節)に短く~
 >また、どうしてもまとめられない状況が起きて（中略）実際のOSではいろいろ工夫しているようです。~
 ひとまず忘れるけど、あとでmemmanに余裕が出来た時に使用中のメモリを再チェックして何とか復活させるとか、~
 とびとびになってきたら、最初の方法に自動で切り替えるとか、そういうものです。
 
 ここでふと疑問が浮かびます。確か「最初の方法」は「今使ってる凄く速い方法」よりメモリを食うはず・・・~
 つまり今の私には何とか復活させる摩訶不思議な方法しか原理上作れないわけです。さてどうすっか。~
 ~
 色々2日くらい考えてたら、アイデアが浮かびました。「解放ミスした領域を使えばいいんじゃね？」~
 しかし開放ミスした領域のサイズは、あの手抜きを修正してしまったら凄く小さいことになります。~
 :あの手抜き|初版で言う192ページで堂々とやらかしている、あの手抜きである。
 
 しかもそんな手抜きを修正しなくても、やっぱり領域のサイズは可変長。管理用の新たな構造体が入る保証はありません。~
 その構造体がすっぽり収まるようなサイズを最低サイズにしてもいいけど、どうせ構造体に8KiBとか使っても~
 変な確保/解放を繰り返さない限り後ろの方はがら空きです。~
 :KiB|単位。1KiB=1024Byte。1KBと書くと1000Byteの事なのか1024Byteの事なのか判別がつきづらい事があるので、私は大抵こっちの単位を使う。
 
 ということで、「構造体のサイズがとても小さい」と「複雑ではない」、それに「実用的な時間で動く」を~
 同時に満たすような奴はなかったかなと頭の引き出しをひっくり返してみると、「片方向リスト」という単語が出てきました。~
 こいつの先頭ポインタをMEMMAN構造体に・・・って、片方向リストの説明がまだでしたすみません。~
 ~
 片方向リストと言うのは、基本的には次のような構造です。~
  struct SinglyLinkedList {
      int data; // 格納しているデータ
      struct SinglyLinkedList *next; // 自分と同じ構造体へのポインタ
  };
 ~
 そして、wikipediaにいい画像と文章があったのでこれを見てもらえれば分かると思うのですが、~
 http://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%83%AA%E3%82%B9%E3%83%88#.E7.89.87.E6.96.B9.E5.90.91.E3.83.AA.E3.82.B9.E3.83.88~
 要するにSinglyLinkedList構造体のメンバであるnextが別の場所にあるSinglyLinkedList構造体を指して、~
 繋がっているように振舞うわけです。~
 ~
 さて、この構造体を確保するのに必要なサイズは12Byteかな？~
  struct MEMLIST {
      void* addr; // 失われた空き領域へのアドレス
      unsigned int size; // とそのサイズ
      struct MEMLIST *next;
  };
 ~
 なんとかして8byteか16byteかに(できれば8byteへ)できないかなぁ。そうすれば割り算も速いし。~
 ~
 ***よく考えよう。
 少し考えてみてください。この構造体は一体どこに配置される事になるかを。~
 そう、開放ミスした領域の、おそらく先頭か最後尾に配置されるように実装する筈です。~
 するとnextメンバやsizeメンバから次の構造体のaddrメンバの値を特定出来るじゃないですか。~
 という事はaddrメンバは実装上は、いらないのかな。(構造体のサイズは8Byteになったよ)~
 ~
  struct MEMLIST {
      unsigned int size; // 失われた空き領域のサイズ
      struct MEMLIST *next;
  };
 ~
 さてMEMMAN構造体にこのリストの先頭ポインタを覚えておいて貰おう。~
 復活させる時はこいつから呼び出せばいいわけだ。~
  struct MEMMAN {
      int frees, maxfrees, lostsize, losts;
      struct FREEINFO free[MEMMAN_FREES];
      struct MEMLIST *list; // リストの先頭へのポインタ
  };
 ~
 さて、こいつを含めた初期化をしないとおそらく変な事になるので書き換えておこうか。~
 (memman_init内部)~
  man->list=LIST_END;     // 解放に失敗した領域を復元させるためのヒント(LIST_ENDはヘッダかどこかで定数として定義。)
 ~
 LIST_ENDの値はとりあえず0でいいかなぁ。~
  #define LIST_END 0
 ~
 とりあえず手を抜かれた部分は修正しておこうかな、適当に。~
 (memman_free内部、かなり下の方)~
  /* 後ろにずらせなかった */
  // 最も小さな空き領域を探す(ここから追記)
  unsigned int lostaddr,lostsize;
  lostsize=size;// 今開放要求が来た奴より小さい奴を探せばいい。
  j=-1;
  for(i=0;i<MEMMAN_FREES;i++){
      if(lostsize>man->free[i].size){
          lostsize=man->free[i].size;
          j=i;
      }
  }
  if(j==-1){// 要求された奴が実は一番小さい奴だった
      lostaddr=addr;
      man->losts++;
      man->lostsize+=lostsize;
  }else{
      lostaddr=man->free[j].addr;
      // 最も小さな空き領域を握りつぶす
      for (i=j;i<MEMMAN_FREES-1;i++) {
          man->free[i]=man->free[i+1];
      }
      man->frees--;
      man->losts++;
      man->lostsize+=lostsize;
      // 最も小さな空き領域を潰した分、管理領域が空いたのでfree可能の筈
      memman_free(man,addr,size);
  }
 ~
 さて、書くぞー(memman_freeの最後に、さらに追記)
  // あとでメモリを復活できるように細工
  struct MEMLIST *t;
  if(man->list==LIST_END){// リストが空なら、ただ追加する
      man->list=(struct MEMLIST *)lostaddr;// 誰も使わない領域の先頭部分
      man->list->size=lostsize;
      man->list->next=LIST_END;
  }else{// 片方向リストの先頭に挿入する
      t=(struct MEMLIST *)lostaddr;// 誰も使わない領域の先頭部分
      t->size=lostsize;
      t->next=man->list;
      man->list=t;
  }
 ~
 多分これで動くだろう。動いてくれよ、頼むから。~
 ~
 メモリを復活させる関数は、とりあえずスケルトンだけ書いてみます。~
  void memman_GarbageCollection(struct MEMMAN *man){
      if(/* 復活させるべきものがないならば */){
          return;
      }
      // 解放した時空き領域を潰さないなら、解放していく(この関数の実行中にman->listの中身が変わるとややこしいので。)
      while(-1){
          if(/* メモリ管理領域に余裕があり、かつ復活させるべきものがあるならば */){
              /* それを解放 */
          }
          if(/* もし復活させるべきものがなくなってしまったならば */) break;
          // この時点でメモリ管理領域に余裕はないはず
          if(/* 前後どちらかでまとめる事ができるものがあるならば */){
              /* それを解放 */
          }
          // 前後どちらかでまとめる事ができた時、メモリ管理領域に少し余裕が生まれるかもしれない。
          if(/* メモリ管理領域に余裕があり、かつ復活させるべきものがまだあるならば */){
              continue;//もう一周。
          }else{
              break;//もう何も出来る事がない
          }
      }
      return;
  }
 ~
 う～ん・・・、メモリ管理領域に余裕があるかはすぐ調べられるし、復活させるべきものがあるかどうかもそうなんだけど~
 前後どちらかでまとめる事ができるものがあるかどうかなんて1行じゃ難しいよなぁ・・・。~
 しかもそのあと「それ」を解放と来てる。これはループと関数でなんとかするか・・・。~
 
 ***さて実装
 こんな感じかな。~
  void memman_GarbageCollection(struct MEMMAN *man){
      struct MEMLIST *t,*k;
      if((int)man->list==LIST_END){//復活させるべきものがない
          return;
      }
      // 解放した時空き領域を潰さないなら、解放していく(この関数の実行中にman->listの中身が変わるとややこしいので。)
      while(-1){
          // メモリ管理領域に余裕があり、かつ復活させるべきものがあるならば順次解放
          while(man->frees<MEMMAN_FREES&&(int)man->list!=LIST_END){
              t=man->list;
              man->list=t->next;// 解放可能な存在をリストから削除
              memman_free(man,t,t->size);
          }
          // 復活させるべきものがなくなったらループを抜ける
          if((int)man->list==LIST_END) break;
          // メモリ管理領域に余裕がなくても、前後どちらかでまとめる事が出来るならそれを解放
          while((int)man->list!=LIST_END){// 先頭は特別扱い
              t=man->list;
              if(memman_canfree(man,t,t->size)){// まとめられるような状態なら
                  man->list=t->next;// 解放可能な存在をリストから削除
                  memman_free(man,t,t->size);
              }else{
                  break;
              }
          }
          k=man->list;
          while((int)k->next!=LIST_END){
              t=k->next;
              if(memman_canfree(man,t,t->size)){// まとめられるような状態なら
                  k->next=t->next;// 解放可能な存在をリストから削除
                  memman_free(man,t,t->size);
              }else{
                  k=k->next;
              }
          }
          // まとめる事によってメモリ管理領域に余裕が出来て、かつ復活させるべきものがまだ存在するならもう1周
          if(man->frees<MEMMAN_FREES&&(int)man->list!=LIST_END){
              continue;// もう一周。
          }else{
              break;// もう何も出来る事がない
          }
      }
      return;
  }
  
  int memman_canfree(struct MEMMAN *man,void* addr,unsigned int size){// 既存の空間とまとめる事ができるかどうかを判定
      int i;
      for(i=0;i<man->frees;i++){
          if(man->free[i].addr>addr){
              break;
          }
      }
      if(i>0&&man->free[i-1].addr+man->free[i-1].size==addr) return -1;// 前とまとめられる
      if(i<man->frees&&addr+size==man->free[i].addr) return -1;// 後ろとまとめられる
      return 0;
  }
 ~
 忘れないうちにmemman_allocで8byte単位に切り上げる処理を書き加えておこう。~
 別に16Byteだろうが4KiBだろうが8Byte以上なら問題ないんだけど、「メモリがもったいない」から出発した改造で~
 メモリを見捨てるような真似はしちゃいけないと思うんだ。
  int memman_alloc(struct MEMMAN *man,unsigned int size){
      unsigned int i, a;
      // サイズを8byte単位に切り上げ
      size=(size+(8-1))&(-8);
  /* (省略) */
      return 0; // あきがない
  }
 ~
 ***注意事項(懸案事項)
 ①memman_freeする時に、何も考えずにリストの先頭に入れていったため、例えば次のような場合にうまく全部解放できないかもしれません。~
 ~
 使用中を×、未使用を○、そして解放ミスしたものを△として~
 ・・・×△△○×・・・と並んでいて、管理領域が満タンで、左の△が先に判定された時。~
 ~
 こいつをうまくやるには△同士が並んでいる時にまとめる必要があって、~
 するとおなじみの挿入ソートが顔を出します。~
 ということで私も書いてみたのですが、どうにも長いしぱっと見意味不明なので、「皆さんへの宿題」と言うことでいいでしょうか？~
 また、ある構造体にもうすこし手を加える事で、memman_GarbageCollection関数内等の「先頭部分は特別扱い」という状況を改善できます。~
 考えてみてください。~
 ~
 ②多分これは最良の方法ではありません。必ずロジックレベルでもっといいものがあるはずです。~
 私は今のところ思いつきませんが、皆さんもあれこれ考えてみてください。~
 できればその方法をコードに起こすなり他人に説明できる程度に詳しく外部仕様を紙に書き出すなりしてください。~
 私はその方法を見てみたいです。~
 ~
 ③一応確認はしてるのですが、あまり頭のよくない私が書いたコードにバグがないとは考えられません。~
 コードをコピペする前に「何がしたくて、どうすれば実装できそうか」を理解して、一応コードを目で追ってみてください。~
 ~
 ④ついでに言うと現状の私の作ってるOSとはあちこちでコードが違うので、コンパイルすら試してません。すみません。~
 例えばmemman_free等は全部MEMMAN構造体へのポインタを引数に取らないで、各関数内で直接参照しに行ってますし、~
 MEMLIST構造体の名前がMEMCONS構造体になってたり、そのメンバのnextの名前もcdrになってたりします。~
 これは自分にとって読みやすく書くためだったりするのですが、おそらく「cdr関数」という物をよく使う某言語を~
 使ってる人は主にC言語で書いてる人たちの中にはあまり居ないのではないかと思い、~
 書き換えながら掲載用に移植しました。という言い訳を言っておきます。
 
 ***簡易投票(今回のメモリ管理に関する記事について。)
 どの程度役に立った？
 #vote(全く。全然。[1],ほんのわずかに。あまり。[2],やや、少し。[3],まぁまぁ、割と。[1],かなり、とても[1],非常に、凄く[3])
 説明は適切？
 #vote(説明過剰,やや過剰,適切,やや不適切,分かりにくい,全く分からない)
 #vote(説明過剰[0],やや過剰[0],適切[1],やや不適切[0],分かりにくい[0],全く分からない[0])
 ソースコード中のコメントは？
 #vote(多すぎる[0],やや多い[0],やや多いが適切[1],適切で適量[0],やや少ないが適切[0],やや少ない[0],少なすぎる[0])
 あの「cdr関数」をよく使う、括弧地獄とも言われる某言語について何か知ってる？
 #vote(いいえ[1],はい（今、あるいは最近調べた）[1],はい（少しかそれ以上前から知っている）[2])
 
 ***コメント
 #comment