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

第04回 ロック

 

今回は共有メモリ型マルチプロセッサにおける,ロックの必要性とFMPカーネルでのプロセッサ間排他制御の機構について説明します.
リアルタイムOS上のオブジェクト(タスクやセマフォなど)は,管理ブロックと呼ばれるデータ構造で管理されています,そして,その管理ブロックはメモリ上に設けられます.管理ブロックは,一般的に複数の要素で構成されています.
たとえば,TOPPERS/ASPの場合,管理ブロックは構造体で定義され,その要素は構造体のメンバとして管理されています.たとえばセマフォ管理ブロックのメンバには,セマフォ資源数の初期値,セマフォ最大資源数などがありました.(リアルタイムOSの内部構造を見てみよう 第20回参照)

システムコールによっては,管理ブロックの複数の箇所をアクセスする場合があります.たとえば,タスクAが起床待ちのタスクBに対して,wup_tskを発行する場合について考えてみます.

タスクAはタスクBのタスク管理ブロックを操作します.wup_tskシステムコールの中では,複数回タスクコントロールブロックにアクセスし,複数の要素を操作します(図1).
タスクコントロールブロックの複数回の操作は,不可分に行われなくては不整合が生じてしまいます.
シングルプロセッサの場合は,この不可分な操作を阻害するものは割込みでした(図2).タスクAがタスク管理ブロックにアクセスした後割込みが発生し,タスクBの管理ブロックを操作してしまったとします.すると,割込み処理終了後,タスクAがタスクBの管理ブロックを処理しようとした時には,不整合が起きている可能性があります.また,割込みが発生したことにより,ディスパッチが発生し,他のタスクがタスクBの管理ブロックを触ってしまうことも考えられます.

null

【図1 タスク起床時の管理ブロックの操作】



【図2 割込みによる不可分な操作の阻害】

よって,TOPPERS/ASPの場合は,不可分に行わなくてはいけない処理をしている間,割込み禁止にすることで,処理を邪魔されないようにしています(図3).割込み禁止にしておけば,割込みもディスパッチも発生しませんので,タスクの処理が阻害される心配はありません.つまり,不可分に処理を行うことができます(図4).



【図3 TOPPERS/ASPカーネルの例 



【図4 TOPPERS/ASPカーネルの例◆

では,マルチプロセッサの場合はどうでしょうか?シングルプロセッサの場合は割込み禁止にしておけば,不可分に操作を行うことができました.しかし,マルチプロセッサの場合は,割込み禁止にしても,その最中に他のプロセッサの処理を止めることはできません.マルチプロセッサでは,一般に,あるプロセッサで割り込みを禁止しても,他のプロセッサの割込みまでは禁止することはできません.たとえ,全プロセッサで割込みを禁止したとしても,その時点で動作している割込みハンドラやタスクの処理までは止めることができません(図5).

null

【図5 マルチプロセッサにおける不都合点】

図5のように,プロセッサ1では割込み禁止にしているので,タスク1_1が独占して処理を行います.しかし,マルチプロセッサのアーキテクチャが共有メモリ型で,その操作方法が直接操作法の場合,図5のように,プロセッサ2はプロセッサ1が割込み禁止状態であることとは独立して,共有メモリ上にある管理ブロックを操作することができてしまいます.
そこでプロセッサ間の排他制御をする仕組みが必要となってきます.プロセッサ間の排他制御はロックで実現できます.
共有メモリ上にある管理ブロックの操作を排他制御するために,ロックの仕組みを使用します.ロック自身も共有メモリ上に置きます.管理ブロック操作前にロックを取得し,操作後に開放します.他のプロセッサがロックを取得している間は,ロック待ちとなります.

不可分な操作の実現例を図6に示します.

null

【図6 不可分な操作の実現例】

図6の例では,まず割込み禁止にしてプロセッサ内を排他制御し,次にロックの取得を行い,プロセッサ間を排他制御しています.このようにして,共有メモリ上の管理ブロックの操作を不可分に行っています.

具体的に,プロセッサ間排他制御を行っている様子を,図7に示します.



【図7 プロセッサ間排他制御の例】

図7では,プロセッサ1が共有メモリ上のタスク管理ブロックを操作するために,まず割込み禁止にしてプロセッサ内の排他制御を行い,次にロックを取得してプロセッサ間排他制御を行います.プロセッサ1がタスク管理ブロックを操作している間に,プロセッサ2も同じ管理ブロックを操作するために,割込み禁止にしてロックを要求しました.しかし,ロックはプロセッサ1が取得しているため,プロセッサ2はロック待ちとなり,管理ブロックの操作をすることはできません.プロセッサ1が管理ブロックの操作を完了し,ロックを解放すると,プロセッサ2がロックを取得することができ,管理ブロックの操作を開始します.
ロックは一般にハードウェアによるサポートを必要とします.通常,1つ以上のアトミック命令を使用します.(「テスト・アンド・セット」,「ロードリンクト ストアコンディショナル」,「フェッチ・アンド・アッド」,「コンペア・アンド・スワップ」など).これらのアトミック命令は,ロックが獲得されていないことをチェックするとともに,不可分な処理としてロックを獲得することができます.現在のマルチプロセッサのほとんどがハードウェア的な排他制御機構を持ち,そのためのアセンブリ命令を備えています.

アトミック命令とは,実際にはいくつかの操作を組み合わせた命令ですが,他のプロセッサから見てそれらがひとつの処理に見えるものをいいます.アトミック命令の中の一部の操作が失敗した場合は,アトミック命令全体が失敗したことになり,システムの状態はアトミック命令を発行する前の状態に戻ります.
ロックの実現のために必要な処理を図8に示します.

null

【図8 ロック取得のための処理】

,らまでの処理は不可分に行われなければ,不整合が生じてしまう可能性があります.アトミック命令例えば,Test&Set命令はこれらの処理を不可分に行うための命令です.これらのアトミック命令は,ロックが獲得されていないことをチェックするとともに,不可分な処理としてロックを獲得することができます.

ロックは,アトミック命令を用いて,スピンロックで実現するのが一般的です.スピンロックとは,アトミック命令の結果を用いてロックが取得できるまで,ロックの取得を試みる方法です(図9).取得を試みている間は,プロセッサは常に実行状態です.

null

【図9 スピンロック】


プロセッサ内とプロセッサ間の排他制御を実現する方法を以下にまとめます.

・プロセッサ内排他制御
  割込み禁止
・プロセッサ間排他制御
  ロックの取得(アトミック命令を用いたスピンロックで実現)
では,プロセッサ間排他制御が必要な場合には,どの順番で排他制御を行えばよいでしょうか?

割込み応答時間と最悪実行時間を抑えるためには,プロセッサ間ロックの取得とプロセッサ内での排他制御のための割込み禁止を適切に行う必要があります.先ほどのセマフォ管理ブロックを操作する例では,割込み禁止にしてから,ロックを取得する例を示しました.この方法では,プロセッサ内排他制御を行ってから,プロセッサ間排他制御をおこないます.しかし,別の方法を取ることもできます.ロックを取得してプロセッサ間排他制御を行ってから,割込み禁止にしてプロセッサ内を排他制御する方法です.
プロセッサ内排他制御とプロセッサ間排他制御はどちらを先に行えばいいのでしょうか?

割込み禁止中にプロセッサ間ロック取得待ちをしようとすると,割込み禁止時間が長くなってしまいます(図10).

null

【図10 割込み禁止を先にした例】

ロックを取得している間に,割込み処理を行うと,他のプロセッサを無駄に待たせてしまいます(図11).


null

【図11 ロックの取得を先にした例】

どちらを先に排他制御しても問題が発生してしまいます.同時に排他制御することが理想ですが,実現は難しいので,擬似的にソフトウェアで実現します.

では,具体的にTOPPERS/FMPカーネルでの実装例を見てみます.
ロックの取得は,割込み禁止にしてプロセッサ内排他制御を行ってから行います.しかし,そのままではロックの取得がすぐに行われない場合は,割込み遅延時間がどんどん長くなってしまいます.そこで,スピンロックによりロックの取得を試みている間は,施行毎に割込みをチェックし,割込み要求がある場合は,いったん割込みを許可する.という方法をとっています(図12).

null

【図12 TOPPERS/FMPカーネルでの実装例】


どちらかの排他制御を先に行うことで生じる問題点を,このような実装で解決しようとしています.