第2回 LILO CodeReading勉強会（1日目）に参加しました
ひらさん、enoさん、並びに参加者の皆さん、お疲れ様でした。
ほどよい難易度でした。スケジューラの主要な要素と大まかなアルゴリズムは理解しました!! まだ実際のコードは読んでいないのですが、実装はきっとずいぶん複雑なんだろうなぁ。。。
以下、個人的なメモです。急いでメモしたので間違ってたらすみません。
- 参加者の自己紹介。遠距離から来てる人が多い!! 札幌、東京、広島。
- Linuxカーネルの中のソフトウェアデザイン。今回はスケジューラのソフトウェアデザイン。
- 並列状態と応答性能はトレードオフ。
- ひらさんの自己紹介。LinuxKernelHackJapan代表(二代目)。ひらメソッド。ドキュメントピラミッド。書籍とソースコードの溝を埋めたい。書籍 ⇔ LKH-jp ⇔ ソースコード。Linuxカーネル中級者の育成。
- アルゴリズムシミュレーション。アルゴリズムの動作を動きで理解する。
- Linux2.6スケジューラ。スレッド切り替えの機構。スケジューラの方針、スケジューラの実装。4.3BSDスケジューラの問題。Linux2.6スケジューラではそれをどのように解決したか。
- x86CPU。演算器、レジスタセット。最小限のみ説明(ex. レジスタセットは、eax、ebx、ecx、eipのみ)。論理アドレス空間は住所、物理メモリ空間は土地とか家に対応。
- Linuxカーネルの概要。アプリとどう違うのか。アプリ ⇔ システムコール ⇔ カーネル。スレッド管理、メモリ管理、ファイルシステム、デバイス制御、ネットワーク処理等々。
- x86アセンブラの概要。
- キャッシュ。4KB単位でロードされる。メモリアクセスが600サイクル。キャッシュアクセスが2〜3サイクル。キャッシュミスすると演算器はほとんど空まわりしている。
- マルチスレッド。まずはシングルスレッド。足し算スレッドから引き算スレッドにコンテキストを切り替え。スレッドのコンテキストの退避、復元。
- 応答 vs スループット。2.6では、1秒間に1000回チェックしている。頻繁に切り替えると応答性は上がるが、スループットは下がる。
- マルチスレッドのキャッシュ特性。マルチプロセッの場合、スレッドをCPUにマッピングするとキャッシュのヒット率が上がる。ロードバランシング。スレッドを暇なCPUに移動する。モバイル向けに、1つのCPUにスレッドを集めて、不用なCPUの電源を落とす(現状CPUの対応は未？)。
- スケジューラの方針と実装。基本的な動作。タイマ割り込み(tick)。1秒間に1000回。1. 実行中のスレッドを調べる。2. スレッド切り替えルールに基いてスレッドを切り替える。
- 伝統的UNIXスケジューラ。4.3BSD優先度スケジューラ。問題ありあり。32個の優先度スロット(4つの優先度を1つのスロットにマッピング)。優先度スロット探索の高速化のために、優先度ビットマップを設ける。どのビットが立っているかを調べるだけで、一番優先度の高いスレッドが存在するスロットがわかる。I/O waitキュー。スレッドの状態遷移。スケジューラはスレッドの優先度を基準に切り替えを行っている。4tick毎にスレッドの優先度を再計算する。100tick(4.3BSDの場合、1秒)毎に全てのスレッドの優先度を再計算、再接続。→ 重たい処理。問題。実時間保証がない。スケーラビリティがない。
- で、Linux2.6スケジューラはこれらの問題を解決している。O(1)スケジューラ。
- スレッドの分類。実時間スレッド。応答型スレッド、バッチ型スレッド。スケジューラクラスの導入。SCHED_FIFO(実時間:先入れ先出し)、SCHED_RR(実時間:ラウンドロビン)、SCHED_OTHER(応答型:時分割)、SCHED_BATCH(バッチ型)
- 優先度スロット140個。0〜99は実時間型スレッド、100〜139は応答型、バッチ型スレッド。優先度ビットマップも140bit。
- クォンタム(CPU上で実行を許された時間)を各スレッドに与える。優先度スロットは、activeとexpireのふたつを用意。クォンタムを使いきったスレッドは、expireに繋がれる。activeのタスクがいなくなったら、activeとexpireを切り替える。実時間スレッドは、expireに入ることはない。
- 並列性と応答性の進化。ジャイアントロッキングカーネル → マルチスレッディングカーネルに進化。カーネル内のロックの粒度を細かくする。どのOSもだいたいジャイアントロックから細かいロックに移行するのに10年くらいかかっている。プリエンプティブカーネル。ロックのタイミングでプリエンプションする。実時間特性を持つスレッドをサポートする。
- ハードリアルタイム。飛行機の翼の制御。自動車のエンジン制御。ソフトリアルタイム。動画再生。
- 懇親会。昔話率高し。factor。GNUの実装あるんだ。BSD gameのしか知らなかった。サウンドビジュアル言語。Max/MSP。Pure Data。DSPする。BUG社、FIX社(BUG社:開発、FIX社:サポート)。冗談のようなホントの話。
