Dekker's Algorithmとメモリオーダリング

Dekker's Algorithm

しかし、排他制御を実現するのにLoad Linked/Store ConditionalやTest and Setなどの特別な命令を使わない方法も存在する。次に述べるのはDekker's Algorithmという方法である。

最初はプロセサAとプロセサBの札メモリA、Bはゼロとしておき、

プロセサAが、

(1)　St      [A]←1
(2)　Ld      R1←[B]

プロセサBは、

(3)　St      [B]←1
(4)　Ld      R1←[A]

と、自分の札メモリに1を書き込み、その後、相手の札メモリを読む。このようにすると、これらの命令のメモリへのアクセス順序と、プロセサA、Bが読む値は、

(1)(2)(3)(4)    プロセサA:0、プロセサB:1
(1)(3)(2)(4)    プロセサA:1、プロセサB:1
(1)(3)(4)(2)    プロセサA:1、プロセサB:1
(3)(1)(2)(4)    プロセサA:1、プロセサB:1
(3)(1)(4)(2)    プロセサA:1、プロセサB:1
(3)(4)(1)(2)    プロセサA:1、プロセサB:0

の6通りのいずれかである。

双方のプロセサが1を書き込むので、プロセサA、Bともに1を読むケースが多いが、1を読んだ場合は、札メモリを一旦0にリセットして、上記の処理を繰り返す。そして、Ld命令で0を読んだときはクリティカルセクションの使用権を獲得するということにすると、特別な命令なしにクリティカルセクションの排他制御を行うことができる。

メモリオーダリング

しかし、本来、プロセサAの

(1)　St      [A]←1
(2)　Ld      R1←[B]

の2つの命令の実行には依存関係が無い。したがって、1つのプロセサで見ると、どちらの命令を先に実行しても良い。このため、第164回で説明したロードストア機構(図6.24)のようにロードキューとストアキューを設けて実行可能な命令から先に実行していくハードウェアでは、この順番でSt命令とLd命令が実行されるとは限らない。また、札メモリA、Bのバンクが異なる場合は、アービトレーションのやり方によっては、実行順序が逆転することがある。

しかし、前記のDekkerのアルゴリズムを使って排他制御を行っている場合は、このLd命令とSt命令の実行順序が逆転してしまうと、正しく動作しなくなってしまう。

一方、普通の処理を行う場合は、ストアはそのうちにメモリにデータを書き込んでやれば良く、緊急に書き込みを完了する必要はないが、依存関係の無いロード命令は先に実行して、その結果を使う後続の命令の実行を早めるほうが性能的には有利であり、順序を逆転して実行したいというジレンマがある。

また、Opteronのようなリングバスで、アクセスするアドレスのホームノードの位置から、(1)のSt命令は時計廻り(2)のLd命令は反時計廻りに処理が伝達されると、どちらの命令が先に実行されたように見えるかは見ているプロセサの位置に依存し、システム内で一意には決まらない。

このため、最近のプロセサでは、順序性の保証を諦め、プログラムに書かれたロードストア命令の順序と実際にメモリアクセス命令が実行される順序や、他のプロセサから見たメモリ書き換え順序は無関係で、ハードウェアが適当と考える順序で実行してしまう(けど文句あっか? と居直る)というものが多い。このようなプロセサも、1つのプロセサで実行されているプログラムに対してはロードとストアの順序はプログラム順で正しく実行されているように並べ変えて見せるので、単一プロセサで動作するプログラムのロジックに問題は発生しないが、複数のプロセサが関係する場合は、順序の違いが見えてしまい、Dekker's Algorithmのようなプログラムは正しく動作しない。

まあ、Dekker's Algorithm はかなり特殊な例なので、これが動かなくともそれほど困らないが、I/Oアダプタの制御レジスタに指令を書き込んで、その応答を状態レジスタから読み出すというようなデバイスドライバプログラムの場合、この順序が逆転してしまうとI/Oデバイスが動作しなくなってしまう。

このため、このようなメモリアクセスの順序を保証しないシステムでは、本当に順序保証が必要なケースに対応するため、メモリバリア命令という特別な命令を設けている。メモリバリア命令を実行すると、ハードウェアはロード/ストアキューに溜まっているロードストア命令の完了を待ち、その後、メモリバリア命令以降のロードストア命令の実行を開始する。したがって、前記の例のSt命令とLd命令の間にメモリバリア命令を挟めば、一般的なメモリアクセスに対してはロードストア命令の実行順序を保証しないハードウェアでもDekker's Algorithmを正しく実行でき、I/Oドライバにも問題は出ないようにできるようになっている。

しかし、詳細に見ると、Dekker's Algorithmの場合は、LdがStを追い越しては困るが、一般のプログラムでは、依存性がなければLdが先行するStを追い越しても問題にならない。このように問題がないケースまで禁止するのは性能上のロスが増えるので、例えば、それ以前のStが完了しないと、以降のLdは実行しないというように、前後のメモリアクセスの種類を特定し、ld-st、st-ldのように種類ごとのメモリバリア命令を持つプロセサもある。

また、一般にI/Oドライバのようなケースでは、ドライバの中での一般的なメモリアクセスの順序はロードストアキューなどのメカニズムによりプログラム順と矛盾のないように見えるので、実際のハードウェアでの実行順序は任意で良いが、I/Oアダプタのレジスタアクセスの場合には、一般に厳密にプログラムに書かれた命令順にアクセスしなければならない場合が多い。もちろん、順序の保証が必要な箇所に適当なメモリバリア命令を挟んでデバイスドライバプログラムを書けばよいのであるが、一々メモリバリア命令を挿入するのは面倒である。このようなプログラマの負担を軽減し、間違いを減らす目的で、最近のプロセサでは、I/Oアダプタの制御レジスタをマッピングするメモリページの属性としてプログラム順のアクセス、その他の一般的なメモリページはアクセス順不定というように、ページ単位のメモリ管理機構と連動してメモリオーダリングを切り替えるという方法を採用しているプロセサもある。