3

この問題を想定します: 2 つのプログラム、A と B、A の 1 つのプロセス、M の M プロセス、var という名前の 1 つの共有変数

A
main(){ 
   int i, a[50]; 
   for(i=0;i<50;i++) 
       var = a[i]; 
} 



B
main(){ 
   int i, b[50]; 
   for(i=0;i<50;i++) 
       b[i] = var; 
}

ここで、A のループごとに、M 個の B プロセスのそれぞれが共有変数を (1 回だけ!) 読み取り、それを配列に格納するようにする必要があります。したがって、最終的に各 B プロセスは、b 配列に a 配列のコピーを持ちます。これはセマフォの問題であり、解決策は疑似コードである可能性があるため、言語は関係ありません。

機能しない初期ソリューション: 0 で初期化されたセマフォ B を使用しています。A が何かを書き込むたびに、B を M ずつ増やして、down(A) を実行しています。各 B ループの開始時に、down(B) を実行します。次に、B の各ループの最後で、M 人のリーダーが var を読み込んで格納したかどうかを確認し、そうであれば、up(A) を実行しています。

明らかに、上記により、単一の B プロセスが、M リーダーを介して分散されるはずだったすべての M の使用を「消費」することができます。では、どうすれば (賢く)、各 B が各 var を 1 回だけ読み取るようにすることができるでしょうか? M ごとに 1 つずつ、M セマフォの配列が機能しますが、演習で求められているものではない可能性が高くなります。

4

2 に答える 2

1

これは、4 つのセマフォで行うことができます。1 つは「偶数ロケーションを読み取る」ことを意味します。1つは「Bが偶数の場所を書いた」ことを意味します。1つは「奇妙な場所を読む」ことを意味します。最後の意味は「Bが奇妙な場所を書いた」という意味です。

A は a[0] を読み取り、最初のセマフォに M 回通知し、2 番目のセマフォを M 回待機します。B は b[0] を書き込み、次に 2 番目のセマフォを 1 回通知します。

次に、A は a[1] を読み取り、3 番目のセマフォに M 回通知し、4 番目のセマフォを M 回待機します。B は b[1] を書き込み、4 番目のセマフォを 1 回通知します。

次に、配列の奇数/偶数要素を処理しながら、セマフォを切り替えます。

これは現実的なシナリオとは思えないため、明らかに宿題の質問です。

于 2013-02-03T15:19:36.473 に答える
0

実装例

// Before A and any B run, init 2 x M x 50 semaphores
// (set to 0, but usually they're automatically initialized by the system to
// something equivalent to 0, meaning no-access)

// Create [M][50] semaphores and init to no access for Bs
for (i=0 ; i<M ; i++)
  for (j=0 ; j<50 ; j++)
     asems[i][j] = 0; // no access for Bi index j


// Create [M][50] semaphores to block A before it goes to next iteration
for (i=0 ; i<M ; i++)
  for (j=0 ; j<50 ; j++)
     bsems[i][j] = 0; // no access for A until all B's say ok for that index


// A

for (i=0 ; i<50 ; i++) { 
   var = a[i];

   // release a-sems and, then, wait for b-sems in two separate loops
   // or you may have a deadlock if you use one loop only...
   // (since we don't know if B[i] always ends before B[i+1])
   for (j=0 ; j<M ; j++) {
      release ( asems[j][i] )
   }
   for (j=0 ; j<M ; j++) {
      wait ( bsems[j][i] )
   }
}

// a B

ME = id  // id is the B's unique id from 0 to 49

for (i=0 ; i<50 ; i++) { 
  wait ( asems[ME][i] )
  b[i] = var
  relase ( bsems[ME][i] )
}

[50] ([M][50] ではなく) セマフォのみを使用する、より複雑なアルゴリズムを作成できます。通常、待機と解放はそれに似たもの (システムによって処理される) によって提示され、それぞれクリティカル セクションで実行されます。

wait ( sem ) {
   wait_in_sem_fifo_until (sem > 0) 
   sem--
}

release ( sem ) {
   sem++
}
于 2013-02-03T15:07:19.343 に答える