セマフォとは？共有プロセスのプログラミング方法と例題

(1)のソースコード

//プロセス1
while (true){
  (空欄1)
  l=l-1;
  (空欄2)
}

//プロセス2
while (true){
  (空欄3)
  print("%d \n",l);
  (空欄4)
}

//出力結果
1
0
-1
-2
-3

(2)のソースコード

//プロセス3
int i;
for(i=0;i<10;i++){
  p(s3);
  n=n+1;
  if((空欄5)){
    (空欄6)
    }else{
    (空欄7);
  }
}

//プロセス4
int i;
for(i=0;i<10;i++){
  (空欄8)
  print("%d \n",n);
  (空欄9)
}

//出力結果
2
4
6
8
10
12
14
16
18
20

セマフォとは

複数のプロセスの間で、リソースへのアクセスを制御するための同期手段を言います。

同期にはP操作とV操作を使用します。P操作はプロセスの実行とセットで行います。V操作は、あるプロセスの実行が完了し、待機している別のプロセスを実行したいときに使います。それぞれのプロセスでは、セマフォ変数(ここでは\(s_{i}\))をデクリメント(P操作)、インクリメント(V操作)します。\(s_{i}\)の値が0のときはプロセス実施不可で、1のときは実施可能になります。

本取り決めが無いとあるプロセスが連続で実行されたり、全く実行されないプロセスも出てきます。問で示したような出力結果にはならないことが考えられます。

これをセマフォ変数を適切に設定し、プロセス1を実行すれば次にプロセス2を実行。プロセス2が完了すればプロセス1に戻るを繰り返すことになります。

実際に、問いを解いてみることでP操作とV操作の使い方を見てみましょう。

解答例

(1)セマフォを用いたデクリメントの出力

まず、変数\(l\)の初期値が1で、出力結果に1が表示されていることを確認します。これは、変数\(l\)を出力するプロセス2が先に実行されていると考えられます。

このため、\(s_{1}=1,s_{2}=0\)とし、プロセス2のprintfの前の行(空欄3)にP操作(\P(s_{1})\)を配置することが適切と考えられます。

printfを実行後はプロセス1を実行すればよく、S操作\(S(s_{1})\)を(空欄4)に入れます。その後、プロセス1でP操作\(P(s_{1})\)を実行すれば良いです。(空欄1)

プロセス1側の操作が完了すれば、プロセス2を実行するため、S操作\(S(s_{2})\)を実行すれば良いです。(空欄2)

以上より、下記のコードになります。(s1=0,s2=1)

//プロセス1
while (true){
  P(s2); //空欄1
  l=l-1;
  V(s1); //空欄2
}

//プロセス2
while (true){
  P(s1); //空欄3
  print("%d \n",l);
  V(s2); //空欄4
}

//出力結果
1
0
-1
-2
-3

(2)2の倍数を出力するセマフォ

(1)と同様に考えます。

出力結果に0が無いため、プロセス3を先に実行することが分かります。よって、\(s_{3}=1,s_{4}=0\)になります。

インクリメントは1ずつに対し、出力は2の倍数ごとです。1のときは出力しない分岐が必要のため、if文の中の(空欄5)には、i%2==0 が入ります。

if成立時は、printfで出力するためプロセス4を使用する必要があるため、(空欄6)にはV操作\(V(s_{4})\)が入ります。非成立時は、もう一度+1する必要があるためプロセス1を再度動かすためのV操作\(V(s_{3})\)が入ります。(空欄7)

プロセス4では、printfで出力する前にP操作\(P(s_{4})\)をします。(空欄8)出力が完了後は、プロセス3に戻るため、V操作\(V(s_{3})\)が入ります。(空欄9)

以上より、下記のコードになります。

//プロセス3
int i;
for(i=0;i<10;i++){
  p(s3);
  n=n+1;
  if((n%2==0)){
    V(s4)
    }else{
    V(s3);
  }
}

//プロセス4
int i;
for(i=0;i<10;i++){
  P(s4)
  print("%d \n",n);
  V(s3)
}

//出力結果
2
4
6
8
10
12
14
16
18
20

最後に

本問は、応用情報技術者試験でも出題されることがあります。加えて、最近ホットな並列処理を正常に実行するための考え方の一端を勉強することができます。

概念だけでなく、本問を通して実際にプログラミングできるようになれば幸いです。