気になったことのあれこれ。2.6.11のコードリーディングをしていく。CPUのアーキテクチャは書籍に沿ってIntelのx86とする。今回はプロセススケジューリングについて見ていく。概要Linuxでは複数のプロセス間を非常に短いインターバルで切り替えることで、複数のプロセスを同時に実行しているように見せる(マルチプロセス)。いつどのプロセスに切り替えるのか、プロセススケジューリングと呼ばれる処理を見ていく。https://www.adamh.cz/blog/2016/07/context-switch-on-the-arm-cortex-m0/方針プロセススケジューリングは以下のような条件を満たす必要がある。優先度の調整スケジューリングはタイムシェアリングを基礎としており、CPU時間をスライスという概念に分割し、それぞれを実行可能プロセスに割り当てることで同時多重に実行する。当然ながら瞬間的には単一のプロセッサでは単一のプロセスしか実行できない。現在動作中のプロセスがタイムスライス(クォンタムとも呼ばれる)を使い切った時はプロセス切り替えを行う。スケジュールは優先度を用いて行い、プロセス毎に保持している値を用いてどのCPUで実行するのが効率的かなどをスケジューラに通知する。優先度は定期的に動的に変更され長時間動作しているプロセスの優先度は減少し、短時間しか動作していないプロセスの優先度は増加していく。プロセスは大まかに2種類に分類される。I/OバウンドCPUバウンドこれはあるリソースに対して頻繁にアクセスを行うことを意味する。ユーザインタラクティブなプロセスを意味し、マウスやキーボード操作を行うプロセスのこと。入力への応答は50~150ミリ秒である必要がある。主な対話型プロセスの例としてシェル、テキストエディタ、GUIアプリケーションなどが挙げられる。ユーザ処理がなくバックグラウンドなどで処理されることの多い、コンパイラ、DBの検索エンジン、科学計算などを例として挙げられる。優先度を下げられることをが多い。ビデオやサウンド関係、ロボット制御などが挙げられ、短い応答時間と高いスループットが要求される。Linuxのスケジューリングアルゴリズムではリアルタイムプロセスは認識できるが、(2.6.11時点では)対話型プロセスやバッチプロセスを判断するのは容易ではない(現在のCFSスケジューラでは容易に判断が可能)。プロセスプリエンプションプロセスはプリエンプト可能で、あるタスクの状態がTASK_RUNNINIGに遷移する際にカレントプロセスと比較し、その優先度が高ければカレントプロセスに割り込んでスケジューリングを行い、他のプロセスに実行を移す。プリエンプトはタイムスライスを消費し切ったタイミングでも発生し、プロセスの状態にTIF_NEED_RESCHEDを設定することで次のタイマ割り込みの際に再度スケジューリングが発生する。実行権が別のプロセスに遷移した際も、そのプロセスは待ち状態になるわけではなくTASK_RUNNINGのままCPUを使用しないような状態となる。タイムスライスタイムスライスはプロセスに割り当てる実行時間のことで、プロセス切り替えを行うインターバルにもなるため、短過ぎる時間を設定するとプロセス切り替えを頻繁に発生しシステムのパフォーマンスに多大な影響を与える。長過ぎた場合にもシステムに悪影響を及ぼす(インタラクティブであるはずのプロセスの反応速度が遅くなるなど)。スケジューリングアルゴリズム初期バージョンのスケジューリングアルゴリズムはシンプルでスケジューリング処理の度に全プロセスの優先度を再計算し最適なプロセスを実行対象として選択するものだった。プロセス数の増加に比例し当該処理のコストは増加するため、多数のプロセスが動作するようなハイエンドシステムではコストがかかり過ぎるモノだった。2.6からは実行対象を選択する処理はプロセス数に依存せず一定の時間で完了する。加えてプロセッサ毎に実行可能なプロセスのキューを保持しているためプロセッサが複数搭載されている場合にも対応している。I/OバウンドまたはCPUバウンドであるかも判断が可能となっている。Linuxはswapperプロセス(PIDが0でスリープするだけのプロセス)を保持しており、スケジューラは必ず実行可能なプロセスを選択可能であることが保証されている。マルチプロセッサ環境では各CPUがそれぞれにswapperプロセスを保持する。スケジューリングの種類は以下のように定義されている。従来のタイムシェアリングプロセス。先入れ先出しのリアムタイムプロセス。スケジューラがプロセスに対してCPUを割り当てても実行可能プロセスキュー内の位置を変更せず、そのリアルタイムプロセスの優先度よりも高い優先度を持つプロセスが存在しない限りCPUを使用し続ける。ラウンドロビン型のリアルタイムプロセス。スケジューラがプロセスにCPUを割り当てると、そのディスクリプタをキューの末尾に移動する。スケジューラは同じ優先度を持つ全てのSCHED_RRプロセスに平等にCPU割り当てる。SCHED_NORMAL(従来のタイムシェアリングプロセス)静的優先度このアルゴリズムではプロセスは全て静的優先度を保持しており、この優先度を用いて相対的な位置付けを行う。新たに生成されるプロセスは親プロセスから優先度を引き継ぎ、ユーザプロセスであればnice()やsetpriority()システムコールで値を変更することが可能である。基礎タイムスライス基礎タイムスライスとはタイムスライスを使用した後に再度割り当てるタイムスライス時間のことを意味する。基礎タイムスライスは優先度に依存しており優先度が高い(値が低い)場合より長いタイムスライスが割り当てられる。他に動的優先度を持ち、動的優先度は100(最も高い優先度)~139(最も低い優先度)の範囲の値を取る。この動的優先度はスケジューラが次に実行するプロセスを選択する際に使用する。動的優先度は静的優先度に加えて、ボーナス値という値を考慮し算出する。ボーナス値はプロセスの平均休止時間を考慮し決定され、0~10の値を取る。平均休止時間はプロセス起動からの休止した時間(ナノ秒)の平均だが、単純に休止した時間から算出されるわけではなくTASK_INTERRUPTIBLEとTASK_UNINTERRUPTIBLEで異なった算出方法を用いる。平均休止時間は1秒より大きくなることはない。平均休止時間はI/OバウンドかCPUバウンドかの判断にも用いられる。アクティブプロセス及びインアクティブプロセス優先度の高いプロセスほど大きなタイムスライスを与えられるが、優先度の低いプロセスにもタイムスライスは付与されており、どのプロセスにも必ず実行権をまわってくる。実行可能プロセスにはタイムスライスを使い切っていないプロセスと使い切ったプロセスで以下の2種類に分類される。付与されたタイムスライスを使用しきっていない実行可能プロセス。付与されたタイムスライスを使用し切っており、全ての実行可能プロセスがタイムスライスを使用し切るまで実行を禁止される実行可能プロセス。アクティブプロセスはactiveキュー(リスト)に繋がれ管理され、インアクティブプロセスはexpiredキューで管理される。タイムスライスを全て消費したプロセスはactiveキューからexpiredキューに移される。SCHED_RR(ラウンドロビン型リアルタイムプロセス)リアムタイムプロセスはプロセス毎にリアルタイム優先度を保持しており、1(最高優先)~99(最低優先)を値を取る。リアルタイムプロセスの中で最も高い優先度を設定されたプロセスを実行すると、それ以外のリアルタイムプロセスは実行を抑制される。実行中のリアルタイムプロセスは常にアクティブプロセスとして処理される。以下のいずれかの事象が起こった際にリアルタイムプロセスから他のプロセスに実行が移る。高いリアルタイム優先度を保持したリアルタイムプロセスが実行可能状態に遷移した(実行がそのプロセスに移る)プロセスが自身の実行を中断し、TASK_INTERRUPTIBLEまたはTASK_UNINTERRUPTIBLE状態に遷移した。プロセスが中断されTASK_STOPPEDまたはTASK_TRACED状態に遷移した。プロセスが強制終了され、EXIT_ZOMBIEまたはEXIT_DEAD状態に遷移した。プロセスがsched_yield()システムコールを発行し、自発的にプロセッサを明け渡した。リアルタイムプロセスがラウンドロビン型でタイムスライスを使い切った。`nice()システムコールまたはsetpriority()システムコールをラウンドロビン型のリアルタイムプロセスに適応すると静的優先度が変更されるが、リアルタイム優先度が変更されることはない。構造体システムに搭載されている全てのCPUは個別のランキュー(アクティブプロセスやインアクティブプロセスを保持する構造体)を持ち、CPU毎の変数であるrunqueues変数に格納される。指定したタスクに対応するランキューを取得runqueues変数には上記あるようなマクロが用意されている。runqueue構造体は以下のように定義されている。実行可能プロセス専用キューから削除予定のプロセスリスト#endif};システム上の実行可能プロセスは必ずそれぞれのCPUが保持している上記のランキューのいずれかに属しており、そのCPUのみが当該プロセスを実行することが可能となる。ロードバランシングなどで実行可能プロセスはCPUが持つランキュー間を移動(マイグレーション)することもある。以下のようにactive及びexpiredはarraysのどちらかを指す。https://www.oreilly.co.jp/books/9784873113135/activeが指すリストが保持する全てのプロセスがタイムスライスを使い切った際にactive及びexpiredが指すリストを入れ替える。prio_array_t構造体は以下のように定義されており、上記の図の用にqueueメンバで優先度別にプロセスのリストを管理しているのがわかる。優先度別のビットマップで、リストにプロセスが存在しているか否かを保持している。task_structプロセスディスクリプタに用いられる構造体であるtask_structのメンバでスケジューリングに関係するメンバは以下。:};sched_fork()プロセスをforkする際に呼び出されるsched_fork()関数内では上記のメンバが一部使用されている。変わらず、より公平なスケジューリングを行うことが可能となる。local_irq_enable();}スケジューラが使用する関数scheduler_tick()タイマ割り込みでtickに呼び出されるscheduler_tick()は以下のように定義されている。CPU間でのロードバランシング}try_to_wake_up()この関数は休止または中断しているプロセスを起床し、プロセスの状態をTASK_RUNNINGに設定した後、CPUのランキューにプロセスを挿入する。当該関数の定義は以下。プロセスが直近に実行されていないかどうか。カレントプロセスに再スケジューリング用のフラグを立てる。success;}activatedメンバに設定される値には以下のように意味がある。プロセスは"TASK_RUNNING"状態だった。プロセスは"TASK_INTERRUPTIBLE"または"TASK_STOPPED"だった。加えてシステムコールまたはカーネルスレッドによって起床中である。プロセスは"TASK_INTERRUPTIBLE"または"TASK_STOPPED"だった。加えて割り込みハンドラまたは遅延処理によって起床中である。プロセスは"TASK_UNINTERRUPTIBLE"だった。上記で呼ばれているactive_task()関数は以下のように定義されている。実行可能プロセスの総数をインクリメント}recalc_task_prio()上記で見たactivate_task()関数内部で呼ばれているrecalc_task_prio()は平均休止時間と動的優先度を更新する。動的優先度の更新}schedule()プロセスのスケジューリング処理を行う関数でカーネル内の複数箇所から呼び出される。実行キューからプロセスを取り出しCPUを割り当てる。当該関数が呼び出される方法として以下の2つが挙げられる。直接的な呼び出し必要な資源の利用などが不可能でカレントプロセスを停止させる必要がある際に以下のような流れでスケジューラを呼び出す。カレントプロセスをキューに挿入。カレントプロセスにTASK_INTERRUPTIBLEまたはTASK_UNINTERRUPTIBLEを設定する。schedule()関数を呼び出す。(他のプロセスに実行が移る)(他のプロセスから実行権が返ってくる)資源の利用が可能であるかを確認し、できなければ2へ。資源の利用が可能であればカレントプロセスをキューから取り出し実行する。上記のように繰り返し資源が利用可能であるかを確認し、利用が不可能であれば再度スケジューリング処理を呼び出す。長時間繰り返し処理を行うデバイスドライバの多くはTIF_NEED_RESCHEDフラグを確認し、もし当該フラグが設定されていれば直接的にスケジューリング処理を呼び出す。遅延的な呼び出しカレントプロセスにTIF_NEED_RESCHEDフラグを設定することで遅延的なスケジューラの呼び出しを行うことが可能で、ユーザプロセスに実行を戻す際などに必ず当該フラグを確認するので、近いうちにスケジューリング処理が走ることになる。遅延的にスケジューラを呼び出すタイミングは以下。カレントプロセスがタイムスライスを使用し切った場合。scheduler_tick()が当該フラグを設定する。プロセスの起床時にその優先度がカレントプロセスの優先度を上回る場合。try_to_wake_up()が当該フラグを設定する。sched_setscheduler()システムコールが発行された場合。関数定義スケジューリングを行うschedule()関数の定義は以下。activeキューとexpiredキューを入れ替える。再度スケジューリング処理を行う。}プロセスの切り替えを実際に行うcontext_switch()の定義は以下。カーネルスレッドの場合はmmを持たない。同じカーネル空間をマッピングしているためカーネルはメモリ空間を保持する必要がない。カレントプロセスのメモリディスクリプタをそのまま使用する。»Profile低レイヤ好きのソフトウェアエンジニア。(1)はてなブログをはじめよう!k--onishiさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。