コード内のバイナリセマフォの使用

Question

ある計算では、とbの2つの配列
a[i]=f(i) for 0 ≤ i < n and b[i] = g(a[i]) for 0 ≤ i < nが生成されます。この計算がXとYの2つの並列プロセスに分解され、Xが配列aを計算し、Yが配列bを計算すると仮定します。このプロセスは、2つのバイナリセマフォーRとSを使用します。どちらも0に初期化されます。配列aは、2つのプロセスで共有されます。プロセスの構造を以下に示す。以下のいずれかがExitXとEntryYの正しい実装を表し

Process X:       
private i;       
for (i=0; i < n; i++) {    
    a[i] = f(i);      
    ExitX(R, S);      
}         

Process Y: 
private i; 
for (i=0; i < n; i++) { 
    EntryY(R, S); 
    b[i]=g(a[i]); 
} 

？

（A）

ExitX(R, S) { 
    P(R); 
    V(S); 
} 

EntryY (R, S) { 
    P(S); 
    V(R); 
} 

（B）

ExitX(R, S) { 
    V(R); 
    V(S); 
} 

EntryY(R, S) { 
    P(R); 
    P(S); 
} 

（C）

ExitX(R, S) { 
    P(S); 
    V(R); 
} 

EntryY(R, S) { 
    V(S); 
    P(R); 
} 

（D）

ExitX(R, S) { 
    V(R); 
    P(S); 
} 
EntryY(R, S) { 
    V(S); 
    P(R); 
} 

私はプロセスYでクリティカルセクションがXでクリティカルセクションが実行されるまで（a[i]が最初に満たされ、b[i]に使用する必要があります）を実行すべきではない、そうX後、次に実行されるための答えは（B）あるべきと考えています（B）によると、Yのクリティカルセクションのエントリでは、S=1となるので、今度はYのクリティカルセクションを実行できます。

質問：正解は（C）ですが、どこが間違っていますか？

Answer 1

バイナリセマフォでない場合、 'B'は動作します。その場合、Xは要素を作成し、単一のセマフォを増やし、セマフォを待ってそのセマフォを使用することができます。セマフォは、処理可能なアイテムの数をカウントできます。そして、1つのセマフォーで十分です。

ただし、バイナリセマフォがあります。したがって、最大1つしかカウントできません。 Xは要素を作成し、セマフォを通知しますが、セマフォの値を "2"（またはそれ以上）に上げることができないため、要素の作成を続行できません。したがって、その単一の要素がYによって認識されるのを待たなければなりません。そして、待機は、現在の要素が処理されるときにXに信号を送るセカンドセマフォを導入します。必要であればPはセマフォが増加するのを待っている（そしてVが増加している）のを待つことを覚えておくことが重要です。そのような操作がないので、Xは1つのセマフォが0に戻るのを待つことができません。

これは 'C'がやっていることです、Sは実質的に 'データ準備完了'信号であり、Rは '確認応答'です。 Xは準備ができていて、確認応答を待ちます。 Yは準備が整うのを待っている間に肯定応答を送信します。

Answer 2

まず、2つのセマフォーが必要な理由について検討します。その理由は、Xループは、Yはiを終了する前にi+1を開始することはできませんi

Xループを終了する前

1. Yループがiを起動することはできません、我々は調整するためにここに二つのことを持っています。

2つのセマフォがあり、それぞれが1つ上のポイントを管理します。

セマフォが達成されると、PをExitXから呼び出す必要があります。 EntryYはVに電話する必要があります。 Bは既にここに行っています。 2を達成するには、VをExitXに、PをEntryYに設定する必要があります。

だから、Aを見ると、誰も何も増やしていないので、デッドロックです。

Cがジョブを実行します。そのセマフォのいずれかPが呼び出される前にXとY両方が二回Vを打つ可能性があるため、

Dは、かなり右ではありません。