ottatiのブログ

無職学生がネットにクソアプリをまき散らしていく様子

【読書メモ】オペレーティングシステムの仕組み 河野健二 朝倉書店

f:id:ottati:20150103125718g:plain     🍣

オペレーティングシステムの仕組みという本を何周かして読んだ。ネットワーク・セキュリティ・最後のWindowsでの実際的な章を除いた基礎的な部分は100ページ前後でほぼ網羅できる。

オペレーティングシステムの仕組み (情報科学こんせぷつ)

オペレーティングシステムの仕組み (情報科学こんせぷつ)

しかし100ページ前後といっても覚えることは多い。もし君が重要なところにハイライトをつけるなら8割以上がハイライトされてしまうだろう。それくらい内容が詰まっているし、一つひとつの固有名詞はすべて解説されるのでつまづくポイントもない。逆に一回読んだだけでは固有名詞の意味を忘れてしまって続きがうまく理解できない、少なくとも僕はー例えば複数回読むと毎回発見がある、それとも僕がADHDちっくなのか。

しかしながら本は薄く、すべての文字をじっくりと辿っていけばなんとなくOSの仕組みを想像するおとができる。ああ、あの処理はOSのあのへんの機能が使われてるんだなと。中学の時山中湖でランニングしていた時の霧も一緒に浮かんでくる。

わかりづらかったところ

わかりづらかったことと言えばセマフォと条件変数を使った競合状態の解消つまり相互排除の実現の例として挙げられていた生産者消費者問題C言語で書かれたコードか。

これは本当に有名な問題らしく、ぐぐるとわんさかでてくる。様々な大学の資料のPDFへのリンクが。

セマフォで生産者消費者問題

コードは以下の様に記載されている。

int B[N];
int In_Ptr = 0, Out_Ptr = 0;
Semaphore Elements = 0;
Semaphore Spaces = N;

void Producer()
{
  int data;
  for (;;) {
    data = produce();
    Wait(Spaces);
    B[In_Ptr] = data;
    In_Ptr = (In_Ptr + 1) % N;
    Signal(Elements);
  }
}


void Consumer()
{
  int data;
  for (;;) {
    Wait(Elements);
    data = B[Out_Ptr];
    Out_Ptr = (Out_Ptr + 1) % N;
    Signal(Spaces);
    Consume(data);
  }
}

シンプルに考えて、

  • バッファが空いたら作業開始する組
  • バッファにデータが来たら作業開始する組

があると考える。

生産者の場合、生産する領域がないとWait(Spaces);でスリープされるが、消費者のSignal(Spaces)によって叩き起こされる。消費者が叩き起こす生産者がいた場合、生産者は叩き起こされた瞬間にスペースを一つ減らすのでプラマイゼロであり、これがたたき起こす奴がいた場合はカウンタをいじらないという処理。消費者が叩き起こす生産者がいなければ生産領域が1っこ増えるだけである。消費者もの同様の処理をする。Wait(Elements);でのスリープ状態が解かれた瞬間にElementsが一個分減ると考ええばよい。Consume(data);はおまけ。おまけというか、効率化のためにSignal(Spaces);の下に記載されている。

条件変数で生産者消費者問題

セマフォだとシンプルな場合にしか対応できないので条件変数を導入

int B[N];
int In_Ptr = 0, Out_Ptr = 0;
int count = 0;
Cond full, empty;
Lock lock;


void Producer()
{
  int data;
  for (;;) {
    data = Produce();
    Lock(lock);
    while(count > N) wait(full, lock);
    count++;
    B[In_Ptr] = data;
    In_Ptr = (In_Ptr + 1) % N;
    Unlock(lock);
    signal(empty);
  }
}

void Consumer()
{
  int data;
  for (;;) {
    Lock(lock);
    while (count == 0) wait(empty, lock);
    count--;
    data = B[Out_Ptr];
    Out_Ptr = (Out_Ptr+1) % N;
    Unlock(lock);
    Signal(full);
    Consume(data);
  }
}

ロックとwait関数を使用して条件による相互排除を考える。2点について理解できればよい。

まず重要なのはロックが存在する意義は共有資源countに一つのプロセスしかアクセスしないようにするため、だけだということ。

もう一つはwaitとSignalの動作がなんであるか。まず消費者はwhileのところでwaitを食らっているが、これは条件変数emptyに属したスリープを行いつつ、ロックを開放するということ。その後生産者にSIgnal(empty)としてemptyに属したプロセスの一つが叩き起こされる。叩き起こされた奴はスリープから復帰し復帰した時にはロックも獲得し、while文の条件を再度評価し、これが0でない場合にクリティカルセクションにおいての操作を行う。

おわり

全体的にわかりやすく、OSの動作の主要な仕組みを手っ取り早く知ることができる。深いところが知りたい場合はもう少し詳しい本を読めば良いのかな