10/31 (水)
寧日なし
先月の末は仕事の谷間で時間の余裕があったのだが、
ここ三週間ほど仕事が増えて青息吐息状態。
仕様書書き・プロトタイプ作成・雑用で一日が終わって行く。
とりあえず今やっている HP-UX 11i for IA-64 プログラムの IA-64 移植は、
来月の前半にケリをつけないとまずいナリ。
10/10 (水)
[Linux] Competely Fair Scheduler
Linux kernel 2.6.23 が公開されたが、 その最大の目玉は 新しいスレッドスケジューラ Competely Fair Scheduler (CFS)だろう。 CFS の情報とソースはボチボチ追いかけていたのだが、 自分の理解できたところまでを備忘録としてメモしておく。
O(1) Scheduler
これまでの O(1) scheduler は、 First-In First-Out (FIFO) のタスク(スレッド)キューが優先度の数だけ存在し、 優先度の高いキューから先に選択され、 同一優先度ではキューの先に入っているスレッドから後にあるものが 順に CPU時間を握っていく。 スレッドのタイムスライスが長大な場合は ある程度の時間でいったん CPU 実行権を手放して、 同一優先度のタスクキューの最後にまわるという最適化が入っている。
全てのスレッドが CPU-bound ならこれでも問題ない。 しかし、 他のイベントの待ち合わせをしている I/O-bound なスレッドが 問題になる(ここで I/-bound なスレッドと呼ぶのは、 ディスクや入力デバイス以外に他のスレッドからのプロセス間通信などを 待っているものも含める)。 I/O-bound スレッドは「待ち」を開始する read/write や select/poll などの システムコールを呼び出した時点で タスクキューから取り外され待ちスレッドの行列に移されるが、 イベントが到着するとタスクキューの最後に追加される。 CPU-bound なスレッドと I/O-bound なスレッドが混在しているなら、 イベントが到着した I/O-bound スレッドは CPU-bound なスレッドを 追い越して実行を開始したいのだが、 同一優先度にいる前の方のスレッドが処理を完了するまで待つ必要がある。
もう一つの問題は、 O(1) scheduler は tick を単位とした CPU 時間の計算を行っているため、 tick (アーキテクチャによって異なるが i386 は 10 ミリ秒) よりも 短い時間でスレッドが切り替わると「CPU の時間を使った」と見なされない点である。
Competely Fair Scheduler (CFS)
新しいスレッドスケジューラ Competely Fair Scheduler (CFS) は、 以下の特徴を持つ。
- 原則として CPU 時間が割り当てられなかった「待ち時間」が最も長いスレッドが
次に実行されるスレッドになる。
スレッド(
struct task_struct) はstruct sched_entitiyを一つずつ持っており、 この中のメンバ変数wait_runtimeが「待ち時間」になる。
- jiffies の替わりに CPU 毎に存在する fair_clock が使われている。
ナノ秒単位の時間管理がされている(ようだ)。
- タスクのリストを表現するのに、
従来の double linked list の替わりに red-black tree を使っている。
従ってタスクキューではなくタスクツリーとでも呼ぶべきかもしれない。
概念的には 優先度と wait_runtime 順に並べられた double linked list を使用することは可能だが、 新しいタスクを追加するコストが スレッド数 N に対して O(N) になってしまい現実的ではない。
CFS タスクツリーの実体は
kernel/sched.c の 180 行目で定義されている struct cfs_rq という構造体のようだ。
リーフには struct sched_entitiy へのポインタが格納されている。
Red-black tree は struct sched_entitiy の fair_key という
メンバ変数をキーに従って並べられている。
882 /*
883 * CFS stats for a schedulable entity (task, task-group etc)
884 *
885 * Current field usage histogram:
886 *
887 * 4 se->block_start
888 * 4 se->run_node
889 * 4 se->sleep_start
890 * 4 se->sleep_start_fair
891 * 6 se->load.weight
892 * 7 se->delta_fair
893 * 15 se->wait_runtime
894 */
895 struct sched_entity {
896 long wait_runtime;
897 unsigned long delta_fair_run;
898 unsigned long delta_fair_sleep;
899 unsigned long delta_exec;
900 s64 fair_key;
901 struct load_weight load; /* for load-balancing */
902 struct rb_node run_node;
903 unsigned int on_rq;
904
905 u64 exec_start;
906 u64 sum_exec_runtime;
907 u64 prev_sum_exec_runtime;
908 u64 wait_start_fair;
909 u64 sleep_start_fair;
910
911 #ifdef CONFIG_SCHEDSTATS
912 u64 wait_start;
913 u64 wait_max;
914 s64 sum_wait_runtime;
915
916 u64 sleep_start;
917 u64 sleep_max;
918 s64 sum_sleep_runtime;
919
920 u64 block_start;
921 u64 block_max;
922 u64 exec_max;
923
924 unsigned long wait_runtime_overruns;
925 unsigned long wait_runtime_underruns;
926 #endif
927
928 #ifdef CONFIG_FAIR_GROUP_SCHED
929 struct sched_entity *parent;
930 /* rq on which this entity is (to be) queued: */
931 struct cfs_rq *cfs_rq;
932 /* rq "owned" by this entity/group: */
933 struct cfs_rq *my_q;
934 #endif
935 };
fair_key は大雑把に rq->fair_clock - p->wait_runtime に設定されていて、 これに優先度の補正が付いているように見える。
疑問
とりあえず疑問のリスト。
- スレッドが「ブロックされていた時間」は単純に wait_runtime に加算されていない。 重み付けのルールが良く分からん。
- NICE 値による優先度がどこまで反映されるのかが良くわからん。
- futex で複数のスレッドが競合状態に入った後に futex_wake_op されると ロック状態のスレッドが一度に wake するがロックを取れるスレッドは一つだけである。 ロックを取れなかったスレッドが CFS のスケジューリングの中で不利に 扱われることはないか？
10/6 (土)
Takano氏の結婚披露宴
Takano氏が結婚お披露会に参加。 場所は渋谷区恵比寿の Royal Palace です。 普段はハワイ料理の店みたいですね。
メリケンに行く氏の壮行会を上げたのが 2005年の8月6日で早二年。 当地で結婚して凱旋帰国ですよ。 友が皆我より偉く見ゆる日よ、 花を買い来て親しむ妻がいないけど…
写真は貼るのはいろいろプライバシーの問題がありそうなのでやめておく。
10/4 (木)
[Linux][Prog] perfmonctl システムコール
IA-64/Linux に存在する perfmonctl システムコールでいろいろ遊んでいるが、 頑張ると VTune や OProfile よりも面白いプロファイラーが作れそうだ (2007年7月11日)。
OProfile のようなサンプリング型のパフォーマンスモニタリングツールは、 パフォーマンスモニタは特定のイベントをレジスタ(PMR)上でカウントして、 PMR がオーバフローしたことを契機に割り込みを起こしてデータを収集している。
- システムワイドな計測を行っている場合には、 PMR がオーバーフローしたタイミングでデータを回収し、 過去のデータと合算して行く。
- プロセス単位での性能測定をしている場合、 コンテキストスイッチ単位で PMR の値を退避して合計することができる。
- 関数単位/ホットスポット単位での計測を行っている場合、
PMR がオーバーフローして割り込みを起こした位置を記録する。
オーバーフローカウンタを1にすると全てのイベントが拾えるが、 それでは割り込みが多すぎて現実的な動作にならないため、 千回に1回・1万回に1回というように設定してサンプリングすることになる。
最後の関数単位/ホットスポット単位には幾つかの問題がある。
- PMR のカウンティングには遅延が存在するため、 イベントが発生した命令のアドレスは大雑把にしか分からない。 例えば TLB ミスをサンプリングする場合、 load/store 命令でない命令で TLB ミスが発生しているようにみえることがある。
- カーネルやドライバは CPUの割り込みマスクを弄って、
外部割込みを禁止している区間を設けている。
割り込み禁止区間で PMR がオーバーフローした場合、
割り込みが許可されるまでペンディングさせられる。
そのため VTune などを使うと、
spin_unlock_irqrestoreなどの位置で大量発生しているように見えるが、 実際はそうではないはず。
OProfile は(少なくともIA-64版では)ソースと計測データを取る限り、 この問題にヒットしているようだ。
ところが Montecito のパフォーマンスモニタでは、 IP Event Address Register (IP-EAR) という機能があり、 パフォーマンスモニタイベントの発生した命令アドレスを最大 16 個まで記録しておくことができる。 この IP-PER の記録する命令アドレスは 1. の遅延がなく、 割り込み時の iip とは別物なので 2. の問題が解決している。
VTune の VDK のソースコードには IP-EAR をデータ取得するコードが入っているが、 実際の計測に使っているか確かではない。
というわけで perfmonctl システムコールを使って、 割り込み禁止区間を含めたドライバの内部解析ツールを作成中。 しかし、 Data Event Address Register (D-EAR) の収集まではうまく行くのだが、 Event Trace Buffer (ETB) を記録すると正しい分岐命令履歴が取れないようだ。 む〜。
10/2 (火)
[Prog] 自信喪失
C 言語の基本的な文法を誤って記憶していたよ…
do-while 文の中で continue を使った場合の 動作なのだが…
do {
label1:
if (condition1) {
continue;
}
label2:
} while (condition2);
言語仕様としては label2 に処理が移るのが正しいのだが、 label1 に処理が移ると信じ込んでいた orz
