マエカワの備忘録的な何か

思い立ったが吉日

オペレーティングシステム 其の十一 20170705

効率化のためのテクニック

プロセス間のページ共有

 多量のプロセスから使われるファイルがある(例えばlibcとか)
  →それぞれをプロセスごとに入れていてはメモリの無駄になる.
  →実態は一つで、プロセス間で共有できればうれしい

 しかし、メモリは分離だったのでは??
  →読み書き専用データだったら問題なし

写真を挿入

遅延読み込み(Lazy Loading)

 本当に必要になったときにプログラムを実行
  →その時しなくてもよかった仕事をせずにできる.

 デマンドページング
  ex)メモリを要求されるとき
    ①最初はページテーブルにエントリだけ使っておく
    ②初アクセス時に物理ページがないのでpage fault
    ③割り込みハンドラで物理アドレスを実際に取得する

 なぜデマンドページングがうれしいのか
  →libcを仮想アドレスに対応付けるとき、無条件に張り付けてしまっては無駄になってしまう部分が多い(実際、libcで使うのはprintfとかscanfとかくらい)

ページ置換アルゴリズム

 デマンドページングだけではいずれ物理ページが無くなってしまう
  →犠牲ページを決め、スワップアウトすることで物理ページの空きを作る

 どのページを犠牲にするのか
  →最近使われていないページを選ぶ.この方法をLRUと呼ぶ

 LRUについて
  ページが使われたらフラグを立てる.一定時間経ったらフラグを下げる.これにより、最近(一定時間内に)使われていないページはフラグがない状態になっている.参照ビット汚れビットを用いる.

ユーザレベルのメモリ管理

 mallocが呼ばれるたびにOSにお伺いを立てていたらめちゃくちゃ非効率的(Ring0にアクセスするだけでも大変)

 ヒープ領域を増やす時だけbrkシステムコールでOSに頼む.それ以外はRing3でヒープ領域を取りやすくする.

 ということで、メモリの管理には
  ・ヒープ領域にメモリを持っている
  ・mallocのたびに空きメモリを探して渡す
  ・freeで開放
 が必要
  →使っているところ、使っていないところを把握する必要がある.
   →タグや線形リストで実現する

写真を挿入

mallocの仕組み(nバイトほしい時)

 First-Fit:nバイトが初めて入るメモリを取得
 Best-Fit:nバイトぴったり入るメモリを取得
 Worst-Fit:最大のメモリからnバイト切り出してくる
 →現在は高速化されたBest-Fitが使われている

freeのしくみ

 前後の空き領域同士を連結させて更新される

断片化

 mallocなどによって起こってしまう問題.メモリが虫食い状態になってしまうことにより、本来とれるメモリがとれなくなってしまう