最近よくお世話になっている
下北沢OSSCafeで、なにやら
Smooth CoffeeScriptの翻訳プロジェクトという、とても面白そうなプロジェクトが走っているみたいです。「すげぇ！僕も参加してぇ！」というわけで、その勢いに追従して（？）、１年前ぐらいに僕がオレオレ翻訳した
xv6 commentary の Scheduler の章を公開します。ちなみにこの xv6 とは、教育用のOSで、MIT の強者どもが、OSの授業のためだけに作ったという伝説の一品です。ソースコードは約1万行ありますが、コメントやらなんやらが色々挿入されているので、実際のところは1万行未満です（な、なんだってーΩΩΩ）。
ただ、言い訳ですが、元々は誰かに見せるつもりではなかったので、翻訳は結構適当です。また、
xv6 も毎年アップデートされてるみたいなので、可能であれば原本を見た方が良いと思います。とまぁ、そんな状態ではありますが、それでも参考になれば幸いです。ライセンスは
MITライセンスだそうです。
Xv6 - Scheduler オレオレ翻訳, Google Docs
GitHub版 (勢いで repos も作ってみたでござる.）
上記のリンクはいずれも"Allow anyone to edit"な状態なので、一応、現状の Snapshot を以下にコピペしておきます。ご参考（になるのか？）まで。
追記：
さっきちょっと確認してみたところ、さっそく章構成やらなんやらが変わってました。５章ではなく４章になってて、タイトルも"Scheduling"になってます。しかも、僕が読んでたときよりもっと図解が多くなってる！ということで、やっぱし英語読める人とかは原本を読んで下さいね。
以下、オレオレ翻訳
=======================
Chapter 5
[Scheduling]
OSは、実際に持っているプロセッサの数よりも多くのプロセスを走らせているかのように見える。プロセス間でプロセッサを、タイムシェアするためには、いくつかの機構が必要である。一般的なアプローチは各プロセスに仮想プロセッサを割当て、OSが仮想プロセッサを多重化させて１つの物理プロセッサに割り当てることである。
Xv6は、複数のプロセスを並列に実行するための機構を持っている。もし二つの異なったプロセスが１つの物理CPUを競合しているとき、Xv6はその２つのプロセスを多重化する。そして、実行プロセスと実行待ちプロセスを、１秒間に複数回スイッチさせている。Xv6は多重化を用いて、各プロセスがそれぞれ１つのCPUを独占させているかのように振る舞っている。これは、Xv6がメモリアロケーターと HWセグメンテーションを用いて各プロセスにメモリを割り当てたときと似ている。
多重化を実装するためには、いくつかの課題を乗り越えなくては成らない。１つ目は、どうやってあるプロセスと、他のプロセスをスイッチさせるか、である。Xv6はコンテキストスイッチの標準的なメカニズムを使用している。そのメカニズムはシンプルであるが、OSの中では最も難解のコードである。２つ目は、どうやって透過的にコンテキストスイッチを行うか、である。Xv6はタイマ割り込みを用いてコンテキストスイッチを行うという、標準的なテクニックを用いている。３つ目は、プロセスが並列に走るかもしれない、ということである。これによって発生する競合には、ロック機構を用いて対処している。４つ目は、プロセスがその処理を終えたとき、そのプロセスは他のプロセスと共に多重化することができない、ということである。プロセスを消去することは容易ではない。プロセスは自分自身を消去できない。なぜなら、そのプロセスを消去するためには、そのプロセスを実行しなければならないからである。Xv6はこういった問題に対して、出来るだけ直接的な方法を用いて解決しようと試みている。しかしながら、結果的に出来上がったコードは、ややトリッキーである。
一度多重化されたプロセスが実行されると、Xv6はその実行プロセスと他のプロセスとを協調させなくてはならない。しばしば、あるプロセスは、他のプロセスの何らかのアクションの実行が終わるのを待つことがある。その処理が終わったかどうかを繰り返しチェックするために、CPUを無駄に浪費することは無駄である。従って、Xv6はプロセスにsleepという機構を持たせて、他プロセスのある処理が終わるまで眠らせることが出来る。また、他のプロセスは、眠っているプロセスを起こすことが出来る。ただし、プロセスは並列に実行されるため、眠っているプロセスを起こし忘れる危険性がある。そういった問題と解決策の例として
、本チャプターでは、pipeの実装についても触れている。
[Code: Scheduler]
２章では、ユーザスペースにおけるスケジューラについて俯瞰した。本章では、スケジューラのもっと深い部分について触れてみよう。各プロセスは、ブート時にmpmain()を走らせている。mpmain()の最後部では、scheduler()を呼び出している(1263)。
scheduler()は単純なループを実行している(1908)。つまり、(1)次に走らせるプロセスを探し、(2)そのプロセスが止まるまで実行し続ける、ことである。このループの最初部では、scheduler()はsti()を用いて明示的に割り込みを許可している(1914)。これにより、もしHW割込みが処理されるの待っているような場合でも、スケジューラのCPUは、HW割込みを先に処理出来るようになる。その後、スケジューラはプロセステーブルの中から実行可能なプロセスを探す。実行可能なプロセスとは、"p->state == RUNNABLE"となるプロセスのことである。スケジューラが実行可能なプロセスを発見すると、現在のプロセスを変数cpに格納する。その後、スケジューラはusegment()を用いてユーザセグメントを更新し、そのプロセスの状態をRUNNINGにセットする。最後に、swtch()を呼ぶことで、そのプロセスの実行を開始する(1922-1928)。
[Code: Context Switching]
Xv6の各プロセスはkernel stackとregister setを持っている(2章参照)。各CPUはkernel stackを持っていて、スケジューラを走らせるときにそのkernel stackを用いる。swtch()はスケジューラのコンテキスト情報(stack + register)を保存する。そして、現在のプロセスのコンテキスト情報と、次に実行するプロセスのコンテキスト情報とをスイッチする。プロセスがCPUを手放すとき、プロセスはswtch()を呼び出して自身のコンテキスト情報を保存し、returnを用いてスケジューラにコンテキスト情報を返す。各コンテキスト情報はstruct context *よって宣言されている。つまり、関係のある情報の構造体に対するポインタである。swtch()は２つの引数を取る。struct context **oldと、struct context *newである。swtch()は現在のコンテキスト情報を保存し、ポインタをoldコンテキストに格納する。そして、newによって与えられた新たなコンテキスト情報を復元する。
スケジューラのswtch()の振る舞いを追う代わりに、まずユーザプロセスがどのように復元されるかを追ってみよう。私たちは、３章で割り込み処理の末端でtrap()がyield()を呼び出す様子は理解した。yield()は、swtch()を用いて現在のコンテキスト情報をcp->contextに格納するsched関数を呼び出す。そして、スケジューラのコンテキストを情報を、以前保存されたc->contextの状態にスイッチさせる(1967)。
swtch()は、eaxレジスタとedxレジスタを読み込むことで開始する(2202, 2209-2210)。swtch()は、swtch()がスタックポインタを変更する前に、この操作を行わなければ成らない。そして、espレジスタを通して引数にアクセス出来ないようにする。そして、swtch()はレジスタの状態をプッシュし、現在のスタック上にコンテクスト情報の構造体を生成する。呼び出し元が保存するレジスタは、保存される必要がある。つまり、x86の慣習により、ebp,ebx,esi,ebp, そして, espレジスタを保存する必要がある。swtch()は最初の４つのレジスタを明示的にプッシュする(2213-2216)。struct context*は*oldに書かれているため(2219)、swtch()は暗黙的にespレジスタを保存する。また、さらにもう１つ重要なレジスタが存在する。それは、eipというプログラムカウンタである。eipはswtch()を呼び出した命令の場所が保存されている。そして、その命令の場所は、スタックに置ける、ebpレジスタの丁度真上にある。古いコンテキスト情報を保存したら、swtch()は新しいコンテキスト情報の復元の準備を行う。swtch()は、新しいコンテキスト情報を指すポインタを、スタックポインタに移動させる(2220)。新しいスタックは、swtch()が先ほど使っていた古いスタックと同じフォームを持っている。新しいスタックは、swtch()を呼び出す前までは、古いスタックであった。つまり、swtch()は、新しいコンテキスト情報を復元するために、シーケンスを逆転させることが出来る。swtch()はedi,esi,ebx,ebpレジスタの情報をポップし、そして、返り値として返す(2223-2227)。swtch()はスタックポインタを変更し終わったため、各レジスタの値は復元され、戻されたアドレスには新しいコンテキスト情報がある。
私たちの用いる例では、sched()は、c->contextとスイッチさせるためにswtch関数を呼び出した。c->contextとは、各CPUが持つスケジューラのコンテキスト情報である。その新しいコンテキスト情報は、scheduler()のswtch関数の呼び出しによって、保存される(1928)。私たちが追っているswtch関数がreturnされるとき、swtch関数は、sched()ではなく、scheduler関数にreturnされる。そして、スタックポインタは、initproc()のkernel stackではなく、スケジューラのスタックを指すことになる。
[Code: Scheduling]
最後のセクションとして、swtch()の低レベルの詳細を見てみよう。具体的には、swtch()の、プロセスからスケジューラまでの振る舞いと、スケジューラからプロセスに戻ってくるまでの振る舞いを見てみよう。Xv6の慣習として、CPUを手放したいプロセスは、必ずプロセステーブルのptable.lockに鍵をかけなくてはならない。また、取得したロックは必ず解放されなければならない。次に、自分自身の状態(cp->state)を必ず更新し、最後にsched関数を呼び出さなくてはならない。yield関数は、この慣習に従っている(1973)。つまり、sleep()とexit()を実行している。これらの関数は後で見ることにしよう。sched()は自分たちの状況と、その予想される結果に対して、二重のチェックを行っている。というのも、ロックが取得されてからは、CPUは、割り込み不許可の状態で動作しているからである。最後に、sched関数はswtch()を呼び出し、現在のコンテキスト情報をcp->contextに格納している。そして、スケジューラのコンテキスト情報をc->contextにスイッチさせている。swtch()は、スケジューラのスタック情報を返す。これは、スケジューラのswtch関数がスケジューラのスタック情報を返す状況に似ている。スケジューラはforループを繰り返し行い、実行可能状態のプロセスを探す。そして、スイッチを行う。スケジューラはこれらのサイクルを繰り返す。
私たちはXv6がswtch関数の呼び出しを跨いでptable.lockが取得されるのを見てきた。つまり、swtch関数を呼び出す関数は必ずロックを取得していなければならない。そして、ロックのコントロールはスイッチ後のコードを通る。この関数は、一般的なロック機構とは異なる。ロック機構の典型的な慣習は、ロックを取得したスレッドが、そのロックの解放する責任を持つことである。これにより、正しく動作していることを簡単に確認することが出来る。というのも、コンテキストスイッチは、典型的な慣習を破る必要がある。なぜなら、各プロセスの構造体において、ptable.lockは、stateとcontextのフィールドを保護する必要があるからである。ロック機構を用いない場合、コンテキストスイッチ中に、プロセスがyield関数を呼び出す可能性がある。つまり、プロセスの状態をRUNNABLEにして、CPUを手放すためのswtch()を呼び出す前に、異なるCPUがswtch関数を用いてそのプロセスを実行する危険性がある。他のCPUがswtch関数を呼び出すことで、古いコンテキスト情報を使う可能性がある。また、ロック機構を用いない状態では、２つのCPUが同じスタックを同時に使う危険性もある。そして、いずれの状態も正しくない。
この問題を回避するために、Xv6は、プロセッサを解放するスレッドがptable.lockを取得する、という慣習に従っている。そして、そのスレッドが、プロセッサが次に解放するロックを取得する。この慣習を簡潔にするため、スレッドは、sched関数の中で常にプロセッサを手放すようにしてる。これにより、もしあるスレッドが、Xv6がスレッド間をスイッチする部分の行をプリントアウトしている場合、次の簡単なパターンを観測することが出来るだろう(1928,1967,1928,1967などなど)。様式化されたスレッド間スイッチングが起こるプロシージャは、ときどき、対応する２つのco-routinesを参照している。例えば、sched()とscheduler()は、それぞれが互いに参照し合うco-routinesである。
新しいプロセスにスイッチするためのスケジューラのswtch()が、sched関数の中で終わらないケースが存在する。私たちは２章でそのケースを理解した。つまり、新しいプロセスが最初にスケジュールされたとき、そのプロセスはforkret()によって始まる(1984)。forkret()は、ptable.lockを解放を用いて、xv6の慣習に従うためだけのために存在している。それ以外の場合では、新しいプロセスはtrapret()によって始まる。
[Sleep and Wakeup]
ロックは、CPUとプロセスが互いに干渉することを回避するのに役立ちます。また、スケジューリングは、プロセスがCPUを共有するときに役立ちます。しかしながら、今までの内容には、プロセス間の通信を簡単にする抽象化機構はありません。Sleep/wakeup機構は、あるプロセスが何らかのイベントを待つために眠り、そのイベントが発生したら他プロセスがそのプロセスを起こすという機構を用いることで、その穴を埋めてくれます。
具体的な例を見るために、シンプルなproducer/consumerのキューを見てみましょう。そのキューは、あるプロセスが、他のプロセスに対して0でないポインタを送ることを許可します。もしたった１つのsenderとreceiverしかいなく、また、それぞれが別々のCPUで実行されている場合、次の実装は正しいと言えるでしょう。
struct q {
void *ptr;
};
void* send(struct q *q, void *p){
while(q->ptr != 0)
;
q->ptr = p;
}
void* recv(struct q *q){
void *p;
while((p = p->ptr) == 0)
;
q->ptr = 0;
return p;
}
send()は、キューが空になるまで(ptr == 0になるまで)ループする。その後、send()はポインタpをキューの中に置く。recv()はキューが空でない間、ポインタpを外に取り出す。２つの異なったプロセスが走るとき、send()とrecv()は、両方ともq->ptrを編集する。しかしsend()は、ポインタが0であるときだけ、ポインタに書き込む。また、recv()は、ポインタが０でないときだけ、ポインタに書き込む。従って、send()とrecv()は相互にステップを踏むわけではない。
上述の実装は正しいかもしれないが、非常に高価である。もしsenderが時々send()する場合、receiverはポインタの値が変わるまでの間、常にwhileループでスピンし続けなくてはいけなくなるだろう。もしsend()がポインタへ到達したことをreceiverに対して通知する何らかの方法があったのだとしたら、receiverのCPUは、もっと生産的な仕事をすることが出来たかもしれない。sleep()とwakeup()は、そのような機構を提供する。sleep(chan)は、wait channelと呼ばれるポインタ"chan"の上でsleepする。chanは、参照されるためではなく、アドレスとして使われるため、chanはどんな種類のポインタであっても良い。sleep()は、呼び出し元のプロセスをsleepさせ、CPUを他の仕事のために解放する。sleep()は、プロセスが再び起きるまでreturnしない。wakeup(chan)は、chanの上で眠っているプロセスがあれば、各sleep()にreturnを実行させることで、chanの上で眠っている全てのプロセスを起こす。sleep()とwakeup()の機構を使うことで、上述の実装は次のように書き換えることが出来るだろう。
void* send(struct q *q, void *p){
while(q->ptr != 0)
;
q->ptr = p;
wakeup(q); /* wake recv */
}
void* recv(struct q *q){
void *p;
while((p = q->ptr) == 0) /* (1) */
sleep(q); /* (2) */
q->ptr = 0;
return p;
}
このコードはより効率的であるが、もはや正しくはない。なぜなら、このコードは"lost wake up"問題を起こすからである。recv()が、(1)の箇所で"q->ptr == 0"であることが分かり、sleep()を呼ぼうとするとしよう。recv()がsleepする前は、send()は他のCPU上で走っている。つまり、send()がq->ptrを0で無い値に書き換え、wakeupを呼びだしたとき、どのプロセスの眠っていないことが分かる。このとき、recv()は(2)の箇所でsleep()を実行するだろう。recv()はsleep()を呼び、sleepする。このとき、"lost wake up"問題が発生する。つまり、recv()は、既に0以外の値に書き換えられているポインタに対して、sleep()をして待ち続けることになる。次のsend()は、recv()がキューの中のポインタが消費されることを期待して、sleepして待ち続けるだろう。このような現象を、システムがデッドロックしたという。
この問題の原因は、recv()がq->ptr==0のときにだけsleepするという不定状態が、send()が間違ったタイミングで走ることで、侵害されることによって発生される。この不定状態を保持するためには、ロック機構を導入し、呼び出し元プロセスが眠っているときのみsleep()はロックを解放できるようにすれば良い。一度呼び出し元プロセスが再び起こされたとき、sleep()はreturnの直前でロックを取得する。次のコードは正しく、また、recvがwaitしているときも、CPUを効率的に使うことが出来る。
struct q {
struct spinlock lock;
void *ptr;
};
void* send(struct q *q, void *p){
lock(&q->lock);
while(q->ptr != 0)
;
q->ptr = p;
wakeup(q);
unlock(&q->lock);
}
void* recv(struct q *q){
void *p;
lock(&q->lock);
while((p = q->ptr) == 0)
sleep(q, &q->lock);
q->ptr = 0;
unlock(&q->lock);
return p;
}
１つの完全な実装は、receiverが１つ前のsend()の値の消費を待っているようなsend()時においても、sleepできるようにすることだろう。
[Code: Sleep and Wakeup]
Xv6におけるsleep()/wakeup()の実装を見てみよう。基本的なアイデアは、sleep関数で、カレントプロセスにSLEEPINGとマークすることである。次に、sched関数を呼び出し、プロセッサを解放する。wakup()は与えられたポインタの上で眠っているプロセスを探し、発券したらそのプロセスにRUNNABLEとしてマークする。
sleep()は、いくつかの健全なチェックから始まる(2003)。そのチェックとは、カレントプロセスがあることと(2005-2006)、sleep()はロックを通過し終えたばかりであることである(2008-2009)。次に、sleep()はptable.lockを取得する(2018)。このとき、sleepしようとしているそのプロセスは、ptable.lockとlkを両方とも保持している。lkを保持することはcaller(e.g. recv())にとって必要なことであった。カレントプロセスは、他のどのプロセス(e.g. send())もwakeup(chan)を開始することが出来るだろう。このとき、sleep()はptable.lockを保持していて、sleep()は安全にlkを解放することが出来る。言い換えると、ある他のプロセスがwakeup(chan)を開始させたとき、wakeup()はptable.lockを取得できるまでの間、wakeup()が動くことは無い。よって、wakeup()は、sleep()を見失わないように、sleep()の実行が終了するまでの間、待たなければならない。
やや一般的ではない複雑性も存在する。もしlsと&ptable.lockが同じであるとき、sleep()は、&ptable.lockと同様の方法でlkを取得したり、lkと同様の方法で&ptable.lockを解放することによって、デッドロックを起こすかもしれない。この場合、sleep()はacquireとreleaseが互いにキャンセルしてしまったり、また、完全にスキップしてしまったりすることを考えなければならない。
sleep()がptable.lockを保持し、他のどのロックも取得していないとき、sleep()は、sleep channelを記録し、プロセスの状態を変更し、また、sched()を呼ぶことによって、プロセスをsleepさせることが出来る(2023-2025)。
いくつかのチェックポイントを過ぎると、プロセスはwakeup(chan)を呼び出す。wakeup()はptable.lockを取得し、実際の仕事を行うwakeup1関数を呼ぶ(2053)。wakeup()関すがptable.lockを保持するということは、wakeup()がプロセスの状態を操作するという点と、ptable.lockがsleep()とwakeup()が互いに見失い合わないという点から、重要なことだと言える(wakeup1()は分離された機能である。というのも、スケジューラは、既にptable.lockを取得しているとき、wakeup()が実行する必要があるからである。この例は後で見ることにしよう。)。wakeup1()はプロセステーブルを走査する(2053)。schedulerは、適切なchanを持つSLEEPING中のプロセスを発見したとき、schedulerはそのプロセスの状態をRUNNABLEに変更する。これにより、次にschedulerが動作されるとき、schedulerは、そのプロセスが実行可能であることが分かる。
※ 他にも、Spurious Wakeups(偽りのwakeups)という複雑な問題も存在する。
SCR輪講 後半
===========
[Code: Pipes]
本章の序盤で私たちが使ったシンプルなキューはオモチャであった。しかし、Xv6が実際に使っているキューでは、readersとwritersを同期させるために、sleep()とwakeup()を使用している。Xv6のキューとは、pipeの実装である。私たちはpipeのためのインタフェースを０章で見た。具体的には、pipeの末端に書かれるバイトは、kernel buffer内にコピーされ、その後、そのpipeの他端から読み出す事が出来る(FIFO Queue)。今後の章では、pipeの周りにあるファイルシステムのサポートについて触れていく。本章では、pipewrite()とpiperead()の実装について見てみよう。
各pipeはstruct pipeとして宣言される。struct pipeはlockとdataバッファを持っている。nreadとnwriteというフィールドは、バッファから読み出した／バッファに書き出したバイト数をカウントする。また、そのバッファはラップされている。つまり、buf[PIPESIZE-1]の直後に書かれている次のバイトはbuf[0]である。しかし、カウンタはラップされない。この慣習により、(nwrite == nread+PIPESIZE)という状態の満杯のバッファと、(nwrite == nread)という状態の空のバッファを見分けるときに役立つ。しかし、一方で、バッファのインデックスの際は、buf[nread]やnwriteの代わりに、buf[nread % PIPESIZE]を使わなければならない。なお、piperead関数やpipewrite関数は、別々のCPUによって同時に呼び出される可能性がある事に注意する必要がある。
pipewrite()はpipeのロックを取得する事から始まる(5230)。ロックを取得する事により、count,dataなどの変数を保護する事が出来る。このとき、例えばpiperead()も同様にしてロックを取得しようとしたとしても、ロックを取得する事は出来ない(5251)。この場合、piperead()はロックが取得出来るまでスピンし続けるだろう(1373)。piperead()が待っている間、pipewrite()は、交互にaddr[0], addr[1], ..., addr[n-1]を書き換える動作を繰り返す(5244)。このループの間、pipewrite()はバッファを満たしていく(5236)。バッファが満杯になった場合、pipewrite()はwakeup関数を呼び出し、sleepしているreaderに対してデータが読み込み待ちであることを伝える。そして、pipewrite()は&p->nwriteに対してsleepを行い、readerがbufferからデータを取り出すのを待つ。sleep()は、pipewrite()がsleepするプロセスの途中で、p->lockを解放する。
p->lockが取得可能なとき、piperead()はp->lockの取得を管理し、その後、pipeからデータを読み出す。具体的には、piperead()は(p->nread != p->nwrite)であることをチェックする(5256)。つまり、pipewrite()は、p->nwrite == p->nread+PIPESIZEのとき、sleepし始める(5236)。従って、piperead()は、forループを抜けると、pipeからデータをコピーし、コピーしたバイト数だけnreadの値をインクリメントする(5263-5267)。最初は、pipeに多くのバイトを書き込む事が可能である。よって、piperead()はwakeup関数を呼び出し、眠っているwriterを起こす。
wakeup関数は&p->nwriteに対して眠っているプロセスを見つけ、プロセスの状態をRUNNABLEに変更する。このとき、眠っているプロセスとは、pipewrite()を走らせていたが、bufferが満杯であるためにsleepしたプロセスのことである。
他CPU上のスケジューラが異なるプロセスを走らせようとしている場合、pipewrite()はすぐに走り始める事は無い。代わりに、piperead()は、piperead関数を再び呼んだcaller関数に戻る。初めてpiperead()がpipe内のバッファを全て読み出したときは、(p->nread == p->nwrite)という条件式が成立する。その後、piperead()は、&p->nread上でsleepし、データが書き出されるのを待つ(5261)。piperead()を呼び出しているプロセスがsleep状態のとき、sleep関数をreturnさせることで、CPUはpipewrite()のプロセスを走らせる(5242)。pipewrite()は、bufferに残ったデータをコピーした後、このループを終わらせる(5244)。新しいデータを待っているreaderが存在する場合、returnする直前で、pipewrite()をwakeup関数を呼ぶ。残されたpiperead()は走り続け、pipeから新しいデータをコピーする(pipe.c/piperead-sleep/)。
[Code: Wait and exit]
sleep()とwakeup()は、キューの実装時に必ず必要というわけでは無い。sleep()とwakeup()は、チェックしたいコードや待つ必要がある状況において、動作する。0章で見たように、親プロセスは、子プロセスがexitするのを、wait関数を呼ぶ事で待つ事が出来る。Xv6においては、子プロセスがexitしたとき、子プロセスはすぐに死ぬわけではない。代わりに、子プロセスはZOMBIEというプロセス状態にスイッチして待つ。親プロセスがwait関数を呼んで、子プロセスがexitしたことを知るまで、子プロセスはZOMBIE状態で待つ。親プロセスが子プロセスを回収したとき、子プロセスが所有しているメモリを解放する。そして、struct procが再利用出来るように準備する。各プロセスの構造体は、p->parentに親プロセスへのポインタを格納する。もし子プロセスがexitする前に親プロセスがexitしてしまった場合は、initプロセスが、子プロセスのexitに対応する。これは、親プロセスが、子プロセスが終了する前にexitしてしまったときのために必要なステップである。全てのプロセスの構造体はptable.lockによって保護されている。
wait関数は、ptable.lockを取得することから始まる。wait関数は、プロセステーブルを走査し、子プロセスを探す。wait関数は、まず、カレントプロセスに子プロセスが存在し、また、そのどれも未だexitしていないかどうかをチェックする。この場合、wait関数はsleep関数を呼び出し、子プロセスのいずれかがexitするのを待ち、ループする。ここで、sleep状態から解放されるlockはptable.lockである。上述したケースは、その一例である。
exit関数はptable.lockを取得し、その後、カレントプロセスの親プロセスを起こす(2126)。exit関数は未だカレントプロセスをZOMBIEプロセスに変更していないので、ロックの取得は未だ早過ぎるかもしれない。しかし、このロック取得は安全である。親プロセスはRUNNABLE状態に変更されるかもしれないが、wait関数にループは、exit関数がsched関数からスケジューラに入り、ptable.lockを解放するまでの間、走る事は出来ない。従って、プロセスの状態がZOMBIEになるまでの間、wait関数がexitするプロセスをチェックする事は無い(2138)。exit関数がリスケジュールする直前で、親プロセスは、子プロセスからinitプロセスまでの全てのプロセスをチェックする。最終的に、exit関数は、shed関数を呼び出す事でCPUを手放す。
スケジューラは、wait関数によってsleep状態に成っている、exitするプロセスの親プロセスを選ぶ事が出来る(2188)。sleep関数の呼び出しは、ptable.lockをreturnする。具体的には、wait関数はプロセステーブルを再び走査し、exitしたプロセス(state == ZOMBIE)を見つける。wait関数は、子プロセスのPIDを記録する。その後、その子プロセスに関わるメモリを解放し、struct procをクリアする(2168-2175)。
子プロセスは、exit関数の中で上述のクリア作業を行う。重要な事は、親プロセスが、親プロセス自身によってp->kstackを解放することである。子プロセスがexit関数を走らせるとき、子プロセスのスタックは、p->kstackとして確保されたメモリに置かれる。子プロセスのスタックは、子プロセスがshed関数のswtch関数を通して解放される。そして、子プロセスの状態を移行する。こうする理由は、(1)スケジューラの処理がスタック上で走っているからである。また、(2)xv6は、sched関数とscheduler関数を相互ルーチンとして管理するからである。xv6は、子プロセスから直接scheduler関数の処理を呼び出す事は出来ない。なぜなら、scheduler関数の処理は、スタック上で走るからである。また、そのスタックは、wait関数を呼んでいる親プロセスによって削除される可能性がある。
[Scheduling concerns] /* 下書き */
- Spurious wakeupsについて
- p->killedのチェックについて
- thundering herdについて
[Real world]
sleep関数とwakeup関数はシンプルで効率的な同期メソッドである。しかし、他にも同期をする方法はある。そのうちの１つは、本章の序盤で見た"missed wakeups"問題を避ける同期メソッドである。オリジナルのUnixカーネルのsleep関数は、割込を禁止する。この方法で同期をすることができる理由は、Unixは１つのCPU上で動くシステムであるからである。xv6はマルチプロセッサ上で動かす事を想定しているため、xv6は明示的なロック機構をsleep関数に導入している。FreeBSDのmsleep関数も同じアプローチを取っている。Plan 9のsleep関数は、callback関数を使っている。callback関数は、sleepする直前で取得する、スケジュール用のロックと共に動作する。具体的には、callback関数は、直前のsleepの状況をチェックするときに役に立つ。これにより、"missed wakeups"問題を避けることが出来る。Linuxカーネルのsleep関数は、waitチャネルの代わりに、明示的なプロセスキューを使っている。Linuxカーネルのプロセスキューは、内部用のロックを持っている。(一見、コードは十分でないように見える。実際にはどうなるだろうか？)
chan関数とマッチするプロセスのために、wakeup関数内で全体のプロセスリストを走査する事は、非効率的である。より良い解決策は、sleep関数やwakeup関数内のchan関数を、sleep状態のプロセスリストを持っているデータ構造体に置換することである。Plan 9のsleep関数とwakeup関数は、待ち合わせ箇所やRendezの構造体を使う。多くのスレッドライブラリは、変化可能な条件としてその構造体を参照する。つまり、sleep関数とwakeup関数の処理はwait関数やsignal関数によって呼び出される。これらのメカニズムは、同様の手法を共有する。具体的には、sleepの条件は、sleepしている間、アトミックに解放されたロックによって保護される。
セマフォは、異なった協調メカニズムである。セマフォは、２つのオペレーション(increment/decrement, up/down)を持ったint型の値である。セマフォは、いつでもインクリメントする事が可能である。しかし、セマフォの値がゼロを下回る事は許されない。よって、他プロセスによってそのセマフォがインクリメントされるまで、ゼロのセマフォをデクリメントはsleepする。そして、２つのオペレーションはキャンセルされる。int型の値は、典型的には、実際のカウンタの値(e.g. pipeバッファのバイト数, プロセスが持っているZOMBIEプロセスの数)と呼応する。抽象化の１つとして明示的なカウンタを使用する事によって、"missed wakeup"問題を避ける事が出来る。このため、wakeupの発生回数の明示的なカウンタが存在する。このカウンタは、条件変数による"spurious wakeup"問題や、"thundering herd"問題を避けることも出来る。
[Exercises] /* 下書き */
sleep関数は、デッドロックを避けるために、(lk != &ptable.lock)であることをチェックしなければならない(2017-2020)。sleep関数は次のコードを
if(lk != &ptable.lock){
acquire(&ptable.lock);
release(lk);
}
次のコードに置き換える事によって、特別な状況を無視する事が出来るだろう。
release(lk);
acquire(&ptable.lock);
.P2
これによりsleepをbreakする。どうやって？
ほとんどのプロセスのcleanupは、exitまたはwaitによって処理される。
上述のケースはexitを使っている。
このとき、freeを使ってはならない。
p->stack
これにより、プロセスは、exit関数はopenファイルの近くにいなければならなくなる。
何故？
答えはpipeと関係している。
xv6においてセマフォを実装すること。
ミューテックスを使っても良いが、sleep関数とwakeup関数は使わないこと。
xv6のsleep関数とwakeup関数をセマフォに置換する。
結果を比較せよ。
[Additional reading]
cox and mullender, semaphores.
pike et al, sleep and wakeup.
