セマフォとスレッドの問題について

質問

この問題は東京大学大学院の問題なのですが、問題の求めているものがよくわかりません。
セマフォとスレッドなどは勉強して理解しているのですがこの問題はどのようにして解くのでしょうか？

8つのスレッドT1,T2,・・・,T8がある。それぞれのスレッドTiはステートメントSi()を実行するが、Sj()に関連付けされたセマフォSjのオペレーションP(Sj),V(Sj)などを利用して同期・排他制御を行う。(i,j=1,・・・,8)。ステートメントSi間の実行順序に添付した図のような依存性がある場合、それぞれのスレッドTiが実装する同期方法をSi(),P(Sj),V(Sj)などを用いて説明せよ(i,j=1,・・・,8)。
例えば、S1()はS2()とS3()より前に実行する必要があるが、S2()とS3()は同時実行可能である。また、S7()はS4()とS5()が終了しないと実行できない。全てのセマフォは初期化されていると仮定してよい。

回答No.1

noname#134443 · ベストアンサー

初めて回答する者です。よろしくお願いします。

最初にS1ですべてのロックを獲得(P操作)し、
そのあと、S2～S8のスレッドを起動します。
(それぞれのスレッドはロックが解放されるまで待機します。)
最後にS1のロックを解放(V操作)します。

関数S1()
{
P(S1)
P(S2)
P(S3)
P(S4)
P(S5)
P(S6)
P(S7)
P(S8)
//スレッド起動し、待機。
S2()
S3()
S4()
S5()
S6()
S7()
S8()
//S1処理が終了したことをロックの解放によって知らせる。
V(S1)
}

S1の処理が終わるまでP(S1)にて待ちます。
S1の処理がV(S1)にて終われば次の処理(S2の処理)が進んでいきます。

それぞれのスレッド処理の終わりにロックを解放します。

関数S2()
{
P(S1)
V(S1)
V(S2)
}

同様に考えていきます。
関数S3()
{
P(S1)
V(S1)
V(S3)
}
関数(S4)
{
P(S2)
V(S2)
V(S4)
}
関数(S5)
{
P(S3)
V(S3)
V(S5)
}
関数(S6)
{
P(S3)
V(S3)
V(S6)
}
関数(S7)
{
P(S4)
V(S4)
P(S5)
V(S5)
V(S7)
}
関数(S8)
{
P(S6)
V(S6)
P(S7)
V(S7)
V(S8)
}
こんな感じでしょうか。