推 mqazz1:看懂了 謝謝 實在太強了.. 08/09 15:11
※ 引述《mqazz1 (無法顯示)》之銘言：
: 恐龍八版exercises 6.1題
: do
: {
: flag[i] = TRUE;
: while(flag[j])
: {
: if(turn==j)
: {
: flag[i] = false;
: while(turn == j) { };
: flag[i] = true;
: }
: }
: CS
: turn = j;
: flag[i] = false;
: }while(TRUE);
: 這題要證mutual exclusion, progress, bound waiting都成立
: 請問這應該怎麼證?
: 謝謝
mutual exclusion：成立
劇本一：如果現在i在CS裡
則此時flag[i]==true且turn==i
此時j來到會把自己設為false並卡在while(turn == j)此行busy waiting
劇本二：交互執行
兩個process都進入while(flag[對方])這個loop裡
因為此時turn一定在其中一人那
則只有turn不為自己者會進去if，另一方可想為在此loop內不做任何事
而進去if者因為沒有改變到turn值且只會先改變flag[自己]
這個舉動必會讓對方不進入if且可以離開while(flag[對方])這個loop進入CS內
且自己因為turn值沒有被改變會卡在while(turn==對方)做busy waiting
progress：成立
條件一：不失一般性假設現在j不想進CS，即flag[j]==false
則i不會進入while(flag[j])這個loop而直接進入CS
條件二：交互執行
上面證過一定會讓一方進入CS且不會造成deadlock
bounded waiting：不成立
劇本：若現在有一方卡在while(turn==對方)做busy waiting，而另一邊離開CS想再進去
不失一般性假設現在j在busy waiting，也就是while(turn==i){};
代表現在turn==i且flag[j]=false
若在i把turn改為j的瞬間，cpu切給j
此時j因為判斷完turn==j而離開while迴圈未執行下一步
在這一瞬間，cpu又切給i，此時的flag[j]依然為false
此時i重新嘗試要進入時將不會進入while(flag[j])迴圈而再次進入CS內
以上，有錯煩請指正:)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.24.185.245