synchronization - TestAndSet() 命令を使用した相互排除

Question

Silberschatz、Galvin、および Gagne による書籍「Operating System Principles」には、同期に関する章の TestAndSet() 命令に関する次の定義が含まれています。

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = TRUE;
    return rv;
}

上記の命令を使用した相互排除の実装も、次のように提供されます。

do {
    while(TestAndSetLock(&lock))
        ; // do nothing
        // critical section
    lock = FALSE;
        // remainder section
} while(TRUE);

では、 targetを TRUEに設定する条件がない場合、相互排除はどのように達成されるのでしょうか。

次の状況を考えてみましょう。プロセス P0 が共有変数ロックを TRUE に設定し、そのクリティカルセクションに入ります。別のプロセス P1 が上記の while ループで TestAndSet() を呼び出し、無条件にロックを FALSE に設定しながら TRUE を返します (P0 がロックを持っているため)。while ループで 2 回目に TestAndSet() が呼び出されると、FALSE が返され、P0 がクリティカルセクションにあるにもかかわらず、P1 がクリティカルセクションに入ります。次に、相互排除に違反します。

私はいくつかの検索を行い、TestAndSet() の次の代替定義を含む (ノースカロライナ州立大学 CS 部門の) Mithun Acharya と Robert Funderlic による論文に出くわしました。

   boolean Test-and-Set(boolean target)
    begin
        if(target == false):
            target = true;
        return target;
    end

これは私にとってより理にかなっています。比較のためにそれを含めました。また、この論文には参考文献の 1 つとして Silberschatz の本がリストされているためです。

教科書で見つけた定義 (最初に提供したもの) を使用して相互排除を達成する方法がわかりません。誰か助けてもらえますか?

score 17 · Accepted Answer

アトミックな TestAndSet について直感的に考える方法を次に示します。

スレッドは、クリティカル領域に入る前にそれを使用します。2 つのケースのみ:

ロックが保持されています (*target は TRUE): TRUE を返し、*target は TRUE のままです
ロックは保持されていません: FALSE を返し、*target は TRUE に設定されます

したがって、別のスレッドがクリティカル領域にあるため、*target (TRUE) は値がどうあるべきかを反映しています。または「私」は今、この重要な領域に入っているので、*target を TRUE に設定します。

score 6 · Accepted Answer

示されている実装は、次のようにより明確に記述できます。

while(TestAndSet(&lock))
{
   // spin in this loop until TestAndSet returns false
}
do_critical_section_stuff();
lock = FALSE;
// We've now left the critical section

OPはそれを次のように誤解していたと思います：

while(TestAndSet(&lock))
{
   lock = FALSE;
}
do_critical_section_stuff();

これは明らかな理由で適切に機能しません。

score 5 · Accepted Answer

あ、その質問もありました。私の理解を共有させてください。

最初に *target は FALSE になります (それは与えられたものです)。while(TestAndSetLock(&lock)) ; // do nothing P がロックを取得してクリティカルセクションに入るためにパスする必要があることは事実です。(ロックの取得は単なる仮説であり、while ループを通過できる場合はロックを取得します)

誰かがロックを持っているということは、ターゲットがTRUEであることを意味し、ロックを自由に取得できるのはターゲットがFALSEであることを意味します。最初はこんな感じなので、

P1 (最初に関数を呼び出した人は幸運です)、彼はターゲットが FALSE であることを確認し、それを true に設定し、RETURN FALSE を設定することで、while ループの待機を回避します。

現在、ターゲットは TRUE です。その他の事実は、TestAndSet(boolean_ref lock) は呼び出された値を返し、 TestAndSet ( boolean_ref lock)は常にターゲットをTRUE に設定するため、誰かが別の場所でターゲットを FALSE に設定する必要があります (したがって、 lock は FALSE に設定できます)

他の P が来て、ターゲットが TRUE であることを確認し、呼び出すTestAndSet(boolean_ref lock)と、P1 がターゲットを false に設定するまで常に TRUE を返します。

そして、このサイトからこの素敵なグラフィカルな説明を見つけました。ここからダウンロードできます

score 3 · Accepted Answer

最初に引用した TestAndSet 関数は、ターゲットが false の場合にのみ実行されます。つまり、ターゲットが false になるまでスレッドはブロックされます。私はその教科書を持っていませんが、テキストのどこかに言及されていると確信しています。

TestAndSet は、OS の最下位レベルで (または CPU の命令セットによっても) 実装する必要がある「アトミック」関数であることに注意してください。ユーザーアプリケーションに実装されている場合、テストとセットの間でコンテキストスイッチが発生し、破損が発生する可能性があります。

明確化: target が false の場合に関数が実行されるという事実だけは確かです。TestAndSet には 2 つのタイプがあります。1 つはターゲットが True に設定されている場合にのみ返される (ブロック)、もう 1 つは False を返す可能性がある、つまりすぐに返される (別のスレッドによるポーリングを有効にする) ものです。あなたが引用したものは、実行を開始した直後に戻るように見えるため、ブロックしていると思います。これは、「IF」ステートメントがCPUやOSカーネルなどの下位レベルのメカニズムによって実行されることを意味します。

score 1 · Accepted Answer

testAndset メソッドを使用するには、まず Lock という変数を false に設定します。

HdwareData lock = new HdwareData(false);

score 0 · Accepted Answer

TestAndSet(&lock) の相互排除の実装を見ると、TestAndSet が true を返す限り、プロセス (P) はクリティカルセクションに入らないと言えます。プロセスは、(条件が) 失敗するまでループ条件で実行を続けます。

別のプロセスがリソースをロックしている限り、条件は成功します (TestAndSet は true を返します)。別のプロセスがリソースをロックしている場合、lock の値は true です。lock = false を設定することにより、他のプロセスがリソースの保持を解放するとすぐに、TestAndSet は false を返します。

TestAndSet が false を返すと、while ループの条件が失敗し、プロセス P がクリティカルセクションに入ります。

TestAndSet はアトミック操作です。つまり、中断することなく実行されます。これは、ロックとの競合状態を防ぐために行われます。

synchronization - TestAndSet() 命令を使用した相互排除

8 に答える 8

Related

Reference