推 genius945:推 11/30 00:51
推 kiwidoit:推 11/30 01:13
→ kiwidoit:想得很仔細!! 11/30 01:13
推 TNC:原來如此，我想太少了 11/30 09:45
※ 引述《TNC (code)》之銘言：
: consider the following program
: boolean block[2];
: int turn;
: void p(int id){
: while(true)
: blocked[id]=true;
: while(trun!=id){
: while(blocked[1-id]) do noop;
: turn = id;
: }
: /*critical section*/
: block[id] = false;
: /*remainder section*/
: }
: }
: void main()
: {
: blocked[0]=false;
: blocked[1]=false;
: turn = 0;
: parbegin(p(0),p(1));
: }
: is mutual exclusion satisfied?!
progress成立，但mutual exclusion跟bounded waiting都不成立。
mutual exclusion在此情況下不成立：
假設現在turn = 1
但是process 1只剛進while(true) loop，
卻還沒把自己的block設成true，cpu就被process 0搶走了。
此時block[1] = false。
然後process 0很順利的進到while(turn != 0)的loop中，
並且剛驗證完block[1] = false離開bust waiting的while loop，
在還沒把turn改成自己之前，process 1搶到cpu，此時turn依然為1。
於是process 1不會進while(turn != 1)的loop裡面就進去critical section了。
接著process 0又搶回cpu，然後把turn改成自己，順利的離開while loop，
也就又進到critical section中了。
progress成立：
因為
1.不想進去的人不會把自己改成true，另一個就不會被卡住。
2.有turn的人一定可以直接進去，不會有deadlock。
bounded waiting不成立：
情境同mutual exclusion時，只是改成一個在CS中一個在busy waiting中。
離開的那一個剛把自己改成flase時，另一個搶cpu到離開busy waiting。
然後另一個又搶到cpu因為自己有turn所以可以直接再進去CS。
: 我想問的是parbegin是什麼意思?!
: 是說直接從程式的某個部分開始跑嗎?
就是並行無誤。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.24.157.177