マルチプロセッサ用リアルタイムOSの解説

第02回 マルチプロセッサ用リアルタイムOSの構造

 

第1回では,マルチプロセッサの多様性について解説しました.今回は,マルチプロセッサ用リアルタイムOSの構造について,スケジューリングとレディキューの構造の観点で解説します.FDMP型(機能分散マルチプロセッサ)OSとSMP型(対称型マルチプロセッサ)OSで採用されるスケジューリング方法とレディキューの構造について見ていきます.
シングルプロセッサ用リアルタイムOSの例で,スケジューリングとレディキューについて簡単に復習をしたいと思います.

シングルプロセッサの場合には,同時に実行できるタスクは実際には一つです.一つしかないプロセッサを,あたかも複数あるかのように見せる機能のことを,マルチタスク機能といいます.リアルタイムOSはマルチタスク機能を使って,あたかもプロセッサが複数あるかのように複数のタスクを並列実行させています.つまりマルチタスク機能の実現には,複数のタスクを時分割で実行しなくてはいけません。このタスクの実行順序を決めることをスケジューリングと呼び,その方式をスケジューリング・アルゴリズムといいます。一般にスケジューリングとは,「いつ」「どのタスク」を実行するかを決定することを指しますが,将来どのタスクを実行するかの計画をあらかじめ立てているわけではなく,次に実行するタスクを決めることをスケジューリングと呼んでいます。
シングルプロセッサ用のリアルタイムOSであるTOPPERS/ASPカーネルのスケジューリング方法は,多くのリアルタイムOSが採用している「プリエンプティブな優先度ベーススケジューリング」です.(「リアルタイムOSの内部構造を見てみよう」第2回を参照)
そして,スケジューリングを実現するために,実行可能状態のタスクを管理しているのがレディキューで,システム全体で1つ存在します(図1).


null

【図1 シングルプロセッサにおけるレディキュー】


では,マルチプロセッサ用リアルタイムOSでは,どのようになるのでしょうか?
FDMP型OSでのリアルタイムOSでは,タスクは静的に割り付けられたプロセッサでのみ処理を行います.タスクは動的に他のプロセッサに移動しませんので,レディキューは各プロセッサごとに持ち,プロセッサごとに個別に管理することが可能です.また,各プロセッサはシングルプロセッサと同様にスケジューリングを行えばいいことになります.プロセッサを2つ持つマルチプロセッサに,FDMP型OSを適用した場合を図2に示します.プロセッサごとにレディキューを持ちますので,全体で2つのレディキューを持ちます.


null

【図2 FDMP型におけるレディキュー】

SMP型OSでは.タスクはどのプロセッサでも実行できるという特徴がありました.そこで,SMP型OSでは,システム内に存在するタスクをすべて1か所で管理し,システム中の優先度の高いタスクから順に,プロセッサ個数分のタスクを各プロセッサに割り付けます.プロセッサを2つ持つマルチプロセッサに,SMP型OSを適用した場合を図3に示します.タスクはシステム全体で管理しますので,レディキューは全体で1つです.


null

【図3 SMP型におけるレディキュー】

つまり,このようなスケジューリングを行うためには,システム内の全タスクを管理するレディキューを1つ用意し,レディキューの先頭からプロセッサ個数分のタスクを実行させるスケジューリング方法が採用されます.タスクは基本的にどのプロセッサでも実行可能と書きましたが,システムによっては,タスクの実行できるプロセッサを固定する機能を持つものもあります.
このSMP型OSでのスケジューリング方法には,問題点が2つ考えられます.


このSMP型OSが最も適しているアーキテクチャは,Homo-UMAでした.このアーキテクチャは,共有メモリにアクセスが集中するため,多くの場合コヒーレントキャッシュを持ちます.(第1回参照)

null

【図4 Homo−UMA型アーキテクチャ】

図4のようにプロセッサごとに個別のキャッシュを持っている場合,タスクが移動するとキャッシュペナルティが発生してしまうため,可能な限りタスクを移動させず同じプロセッサで実行した方が有利です.たとえば次の例を見てみましょう.

<実行プロセッサの固定に関する問題>
SMP型OSの中には,タスクが実行できるプロセッサを固定する機能を持つものがあります.この場合に生じる問題を見てみましょう.




【図5 実行プロセッサの固定による問題(1)】


プロセッサ1でTaskB(優先度:中)が,プロセッサ2でTaskC(優先度:低)が実行しているとします(図5).ここに,プロセッサ1に実行を固定したTaskA(優先度:高)がやってきたとします.すると,プロセッサ1で実行中のTaskBよりTaskAは優先度が高いため,タスク切り替えが発生し,TaskAはプロセッサ1で実行状態となります.ここで,優先度を厳密に守ろうとすると, 2番目に優先度の高いTaskBがプロセッサ2で実行状態となりTaskCは追い出されます.ここで,TaskBはプロセッサ1からプロセッサ2へ移動します(図6).タスクの所属するプロセッサを変更し,プロセッサ間を移動することをマイグレートといいます.マイグレートについては,後日解説します.




【図6 実行プロセッサの固定による問題(2)】


次にTaskAの実行が終了すると,プロセッサ1が空きますので,プロセッサ1でTaskCが実行状態となります.もともとTaskCはプロセッサ2で実行していたので,ここでもマイグレートが発生します(図7).




【図7 実行プロセッサの固定による問題(3)】


このように,タスクの実行をあるプロセッサに固定した場合には,タスクのマイグレートが頻発し,キャッシュペナルティが発生する可能性を考えなくてはいけません,OSによっては,このようなキャッシュペナルティを考慮に入れてスケジューリングを行っているものもあります.

次に2つめのSMP型OSで発生する問題点について見ていきます.
割込みハンドラが発生した場合について見てみましょう.この例では,プロセッサ1でTaskA(優先度:高),プロセッサ2でTaskB(優先度:低)が実行しています.そこへ,プロセッサ1に割込みハンドラHandler1が発生しました.割込みハンドラはタスクより優先度が高いので,割込みハンドラ実行中にはタスクは実行することができません.

シングルプロセッサ向けリアルタイムOS(例えば,TOPPERS/ASPカーネル)では,割込みハンドラが発生しても,それまで実行中であったタスクの状態は,“実行状態”のまま変更しません.シングルプロセッサの場合にはこれで何も問題はなかったのですが,マルチプロセッサとなると少し状況が変わってきます.図8の例で,割込みハンドラが発生してもTaskAの状態は“実行状態”のままです.よって,スケジューラはTaskAが実行しているものと思い込んで,他のプロセッサがあいていても,また他のプロセッサでTaskAより優先度の低いタスクが実行していても,TaskAを他のプロセッサに割り当てることはしません.具体的には,図8では,プロセッサ2でTaskAより優先度の低いTaskBが実行していますが,TaskAは実行することができず,割込みハンドラの処理中は,TaskAとTaskBの間には優先度逆転が発生してしまいます.


null

【図8 タスクの割込みハンドラ下敷き問題】


もちろん,割込みハンドラが発生した場合に,TaskAの状態を実行状態から実行可能状態に変更するという方針もとることができます.そうすれば,スケジューラはTaskAが邪魔をされて実行できなくなったことを感知し,プロセッサ2で実行させるようにするので,上記の優先度逆転の問題は発生しません.
しかし上記方針をとると,TaskAが実行するためにプロセッサ2にマイグレートします.そして,割込みハンドラの処理が終了するとプロセッサ1が空きます.すると,先ほどまでプロセッサ2で実行していたTaskBがプロセッサ1で実行することになった場合,ここでもマイグレートが発生します.このようにマイグレートが頻発する可能性があり,キャッシュペナルティが発生します.また,割込み発生時に毎回タスクの状態変更という処理が追加されるため,割込み応答時間が長くなってしまいます.以上を考慮すると,割込みハンドラの発生の度にタスクの状態を変更する方針は,あまり現実的とはいえません.
どちらの方針をとるのがアプリケーションにとって有効かどうかは,OSからは判断できません.OSを設計するときの検討事項の1つになります.

今回は,FDMP型とSMP型のマルチプロセッサ向けリアルタイムOSのスケジュール方法の概要を見てきました.次回は,共有資源の操作方法について解説します.