第一回活動報告

日時・場所

2008/11/4 13:00〜15:00
＠電気系会議室1A

学習内容

プロセススケジューリング

詳解LINUXカーネル第三版　では７章全体が対応
（ただしO(1)スケジューリングについて書かれている）

O(N)スケジューリング

Linuxカーネル2.4のスケジューリング方法。
タイムスライスを割り当てる方式。動くプロセスが無くなったら、それまで溜まっていたタイムスライスを1/nしたうえで新たにタイムスライスを補給する。
runqueueがひとつだけあり、その中から優先度の高いものを探索するので、探索はプロセス数Nに応じた時間O(N)かかるためO(N)スケジューリングと呼ばれる。

O(1)スケジューリング

本に載っているスケジューリング方法。Linuxカーネル2.6。
未実行リスト(active queue)にあるプロセスのうち、優先度の高いプロセスから順番に実行し、実行済みリスト(expired queue)に格納。
未実行プロセスがなくなったら実行済みリストを未実行リストと入れ替え、また'未実行リスト''より実行する。
このとき、未実行リストからプロセスを探索するのにO(1)の時間しか必要としないのでO(1)スケジューリングと呼ばれる。
IBMの記事

CFS (Completely Fair Scheduler)

新しいスケジューリング方式、2.6.23から採用。タイムスライス方式とはだいぶ異なっている。
runqueueは赤黒木によって実装されている。
実行されていないプロセスは待ち時間が平等に増加し、実行されているプロセスは待ち時間が減少する。
単位時間をプロセス数Nで分割し、その時間が来たときに最も待ち時間が溜まっていたプロセスが実行される。
優先度によって、実行中プロセスの待ち時間の減少速度が変化する。

･･･という話だと思った。ちゃんと読まないと分からないのであとでまた編集します。

IBMの記事
Wikipedia
O(1)の弱点とCFSの概要
論文誌？
すら度
ttp://kerneltrap.org/node/8059
ttp://kerneltrap.org/node/8208
ttp://kerneltap.org/node/11773

次回以降の予定

第N回	日付	内容	担当
第二回	11/18	第八章　メモリ管理	b_naka
第三回	11/25	第三章　プロセス（第一章含む？）	tencube
第四回	12/2	第五章　カーネルの同期処理	hayamiz
第五回	12/9	第十九章　プロセス間通信	yuyarin
第六回	12/16	第十二章　VFS	.a.u
？	？	第九章　プロセスアドレス空間	これは読んどきたいわー