第5回 並行処理とソフトウェアによる排他制御
こんにちは。今回は並行性とは切っても切れない排他制御に関して話したいと思います。
改めて説明すると、排他制御とはタスクのように並行動作する複数のプログラムが同じデータにアクセスする場合、同時にそのデータにアクセスしてはならないタイミングがあり、その競合を防ぐことです。たとえばあるタスクがデータを生産して、他のタスクがそのデータを消費する場合、データを生産している最中にそのデータを使わせない、データを消費している最中に新たなデータを生産させないための制御です。
排他制御の必要性に関しては皆さんもいろいろ聞いてきているかもしれませんが、今回は最初に現実の組込みソフトウェア、それもリアルタイムOS自身の排他制御の必要性に関して話します。
現役のRTOSの実例を出すには差し障りも多いので、例によって昔のRTOSの例です。時期はおそらく1985年頃の話です。
その当時開発していた製品ソフトウェアに機能を追加すると、1日に1回程度システムダウンを起こすようになってしまいました。結局原因を突き止めるのに3日ほど要しましたが、原因は当時使用していたRTOSがタスク切り替え時の排他制御を行っていないことに伴う不具合でした。その時に使用していた CPUはi8086でしたが、このCPUは実行する命令のアドレスをCS（コードセグメントレジスタ）とIP（インストラクションポインタ）の2つの16ビットレジスタの組み合わせ（CSを4ビット左シフトしたものとIPの和です）で20ビットのアドレスを指定していました。つまりプログラムのアドレスはCS:IPの両者の整合性のもとで成り立っていました。しかしOSの割り込みを許可している部分で実行命令のアドレスを変更する部分に先にIPレジスタを書き換えてから、CSレジスタを書き換えている箇所があり、その2つの命令の間に割り込みが発生することにより、不正なアドレスのメモリを実行しようとして暴走していたのです。これはCSレジスタとIPレジスタの排他制御ができていなかったことが原因でしたが、そのためにシステムダウンまで引き起こすことになりました。結局この不具合はCSレジスタを書き換えると次の命令実行では割り込みを禁止するというi8086の機能を利用し、レジスタを書き換える順番をCSレジスタを書き換えてからIPレジスタを書き換えるようにOSの修正を行い修正することができましたが、排他制御の重要性を実感できた良い経験でした。
つまりこのケースではCSとIPがアトミックデータ（これ以上分割できない最小単位のデータ）であるにも関わらず、その扱いが出来ていなかったということです。
もう一つ排他制御の重要性に関する組込みシステム開発時の実例をお話ししておきます。
実は基本的なことなのですが、CやC++言語などの高級言語で書いても現実のCPUが実行するのはそのCPUが命令と認識できるビットのパターン（機械語）であり、高級言語の1命令が機械語で1命令になるとは限りません。というより複数命令になる場合のほうが多いです。
機械語であればほとんどの命令は、1つの命令実行中に割り込まれないことは保障されていますが、高級言語の1命令は複数機械語命令になるのですから、当然1つの命令の実行中に割り込まれます。なお、ここでいう割り込みとはタスクのスイッチや文字通り割り込みなど、並列処理が切り替わることをいいます。
ここでたとえば次のようなプログラムがあったとします。
タスク_Aとタスク_Bは実行されるタイミングは様々な場合がありますが、とにかく何らかのタイミングで両方のタスクが実行された後だとします。ほとんどの場合はflagの値は初期値0、タスク_Aがビット0をオン、タスク_Bがビット1をオンにしているわけですから、この時点でflagの値は0x3になっているはずです。もちろん0x3になっている場合が多いのですが、たまに0x1や0x2になっている場合もあります。
理由は下に書いていますが、まず原因を考えてみてください。ヒントはCISC系ではあまり発生しない（ただし後述の通り，アクセスするアドレスによっては，あるいは最適化のオプションによっては発生する場合はあります）や、RISC系はよく発生する、です。実際にCISCで正常に動作していた類所のソフトウェアをRISCに移植したとたんに同様の現象が発生しました。
volatile unsigned long flag = 0x0;
タスク_A( )
{
. . .
flag |= 0x1; /* ビット0 オン */
. . .
}
タスク_B( )
{
. . .
flag |= 0x2; /* ビット1 オン */
. . .
}
原因は次の通りです。
下に上記C言語が機械語（厳密には機械語ニーモニックコード）に変換されたあとの様子を示します。機械語はCPUによって異なりますが、ここでは一例としてMIPS風のニーモニックコードを示します。
C言語では一命令に見えたOR演算が3命令になっています。
割り込みであれ、タスクであれ並列処理が切り替わる前後ではコンテキスト（ここではレジスタセットなど）が保存復元されるので、下記の処理がオーバーラップしている場合には、両方のタスクが書き戻すflagの値が異なることになり、あとで実行されたタスクの値がflagに残ることになります。
タスク_A
ld reg1, flag ; flagの値をreg1にコピーする
or reg1, 0x1 ; ビット0をオン
st reg1, flag ; reg1の値をflagにコピーする
タスク_B
ld reg1, flag ; flagの値をreg1にコピーする
or reg1, 0x2 ; ビット1をオン
st reg1, flag ; reg1の値をflagにコピーする
具体的にいうと、タスク_Aがflagの値を読み取ってreg1に保存した直後にタスク_Bに切り替わる場合、まずタスク_Aのレジスタの値をタスク_AのTCBに保存しますが、この時はflagが0だったのでreg1も0です。タスク_Bを実行する前にタスク_BのTCBから保存してある値をレジスタに復元します。そして値が0のflagの値をreg1にコピーして、OR演算によりreg1の値を0x2にしてその値をflagに書き戻すので、その時点でflagの値は0x2になっています。
そしていずれタスク_Aに処理は戻りますが、その時はまず先ほどTCBに保存したコンテキストを復元するところから処理を再開します。するとreg1の値は再び0に戻り、それに対してORを行うためregi1の値は0x1になり、それをflagに書き戻すとflagの値は0x1になってしまい、タスク_Bがセットしたビット1のデータは消えてしまいました。
逆にタスク_Bが実行中にタスク_Aに割り込まれた場合はflagの値は0x2になり、タスク_Aが書き込んだビット0の値が消えてしまいます。上の命令の実行がオーバーラップしない場合は、両方のタスクがセットしたデータはどちらも残るためflagの値は正しく3になります。
タスクでなく割り込みの場合は、コンテキストを保存する場所がTCBでなく割り込みスタックになる以外は同様の動きになり、おなじく不具合が発生します。
ではどうすればいいでしょうか？
上記のようなデータの数が少なく、RTOSを使用しているのであれば、セマフォにより排他制御すればいいかもしれません。
次回セマフォに関して説明しますが、セマフォを使用してもスケジューラに制御が移るとは限らないので、セマフォ呼び出しによるオーバーヘッドも関数呼び出し程度で済むかもしれません。しかし上記のようなデータが多い場合はそのオーバーヘッドも無視することが出来ませんし、RTOSを使用していない場合は、そもそもセマフォを使用できません。
一種の妥協の産物として解決策の一例を次に示しますが、一言で言うと割り込み禁止/許可を使用します。
割り込み処理_A( )
{
DI；
flag |= 0x1; /* OR処理 */
EI；
}
割り込み処理_B( )
{
DI;
flag |= 0x2; /* OR処理 */
EI;
}
DIやEIを次のようにマクロで定義しておき、インラインアセンブラと組み合わせれば、メモリ上のデータとのビット演算命令を備えるCPU（この場合OR命令は機械語でも1命令なので排他制御不要）でも、メモリとのビット演算命令を持たないCPUでもソースコードを統一することが出来ます。
#ifndef M16C // ビット演算命令なし
#define DI asm(“^t fclr i”)
#define EI asm(“\t fset i”)
#else
#define DI
#define EI
#endif
なお、ここで注意しなければならないことは、メモリとのビット演算命令を備えるCPUであっても、コンパイラの最適化オプションやあるいはnearとfarがあるような区別があるCPUの場合は、データのアドレスがnear領域の場合は排他制御不要でも、far領域の場合は排他制御が必要になるなどの場合もあり、生成された機械語の確認は欠かすことはできません。
この割り込み禁止/許可を使用する方法は、割り込み禁止を使用するとシステムのリアルタイム性に影響を与えるので注意して使用しなければなりませんが、それ以外に大きな使用上の制限があります。
それはマルチコアやマルチCPUでは割り込み禁止が役に立たないということです。同じアーキテクチャのCPUで構成されるマルチCPUシステムの場合は、ハードウェアレベルで提供される古典的なTAS命令やCAS命令や、新しいCPUではMIPSのLL、SC命令セット、パワーアーキテクチャ系のLWARX、STWCX命令セットなどのTASやCAS相当のハードウェアレベルでマルチCPUの排他制御を行うための処理を自由に作れるマルチCPUサポート命令セットを使用して排他制御を行うことも可能です。
しかし組込みシステムの場合はリアルタイム性確保のためにAMP（非対称型マルチプロセッサ）が採用されることが多く、上記ハードウェアレベルでのマルチCPUサポート命令は同じアーキテクチャのCPU間での制御が前提であるため、これもまた利用できない場合が多いという問題があります。
ただしシステムの排他制御が必要なCPUがすべて同じ仕組みを利用できる場合には、これから説明するソフトウェアによる排他制御に比べて、
・ソフトウェアが単純になる
・CPUの個数に左右されない
という利点があるためハードウェアレベルのCPUサポート命令を使用するべきです。
他の手段として、排他制御が必要な複数のCPUに渡って同時に割り込みを禁止にできるような独自デバイスを作るという解決策もありますが、結局CPU間のそのデバイスの割り込み禁止にするためのアクセスの排他制御をどうするかという問題をハードウェアレベルで解決しなければならないため、簡単な解決策とは言えません。
排他制御にハードウェアの助けを借りられない場合に有効なのが、スピンロックやビジーウェイトと呼ばれるソフトウェアによる排他制御です。
これは古くからの方法であり、CPUの使用効率の面で問題はありますが、マルチコア対応のLinuxの排他制御にも使われるなど、実は現在でもかなり有用な方法で、使われています。
ソフトウェアによる排他制御には複数のアルゴリズムがあり、いくつかのやり方があります。
リスト1が1965年にDekkerが発表した、ソフトウェアで2つの並行処理の排他制御を行うためのアルゴリズムです。
リスト1. Dekkerのアルゴリズム
そしてリスト2が1981年にPetersonが発表した、より簡潔なアルゴリズムです。
リスト2. Petersonのアルゴリズム
どちらも特殊な命令なしに排他制御を行うためのアルゴリズムです。
リストは2つの並行処理の排他制御を行うためのアルゴリズムですが、3つ以上の並行処理の排他制御を行うことが可能なように拡張することも可能です。
リストの解説を行うと分量が多くなるために、このアルゴリズムがどのように動作するのかを考えてみてください。なお、命令のリオーダーが起こらないこと、機械語レベルの代入命令、比較命令はアトミック命令であることは前提です。
図1にソフトウェアによる排他制御を使用した例を示します。
図1. ソフトウェアによる排他制御の使用例
この例ではRISCで実行されるVxWorks側とCISCで実行されるWindows側の排他制御にPetersonの排他制御を使用しています。
なお、図ではデータをコピーする間ずっと相手をブロックしているようで、ブロックしている時間が長すぎるように感じますが、実際には両者のデータの受け渡しにはリングバッファを用いるので、本当に相手をブロックしている時間はリングバッファのポインタを書き換えている間だけです。
次回はVxWorksなどのRTOSが提供する排他制御、そして同期にも使われる、最も基本的な仕組みであるセマフォを中心にお話ししたいと思います。
第5回おわり
■著者プロフィール
南角 茂樹（なんかく しげき）
大阪電気通信大学 総合情報学部 メディアコンピュータシステム学科 准教授、同大学院総合情報学研究科（コンピュータサイエンス専攻）、エイシップ・ソリューションズ株式会社 研究顧問。
慶應義塾大学工学部数理工学科卒業後、大手電機会社を経て現職。組み込みシステムおよびリアルタイムOSを専門とし、著書、解説記事、発表・講演、登録特許等多数。
ページの先頭へ戻る »
