作者wheels ()
看板Grad-ProbAsk
標題Re: [理工] [OS]CS DISIGN.恐龍本習題Mcguire's algo
時間Mon Nov 28 12:30:57 2011
※ 引述《i78524 (Shulei)》之銘言：
: 這次想請教大家CS DISIGN的演算法，恐龍本後面習題的Mcguire's algorithm
: 這個algo整個看不懂...有沒有什麼比較好的情境可以看懂他？(或是有解釋文章之類的)
: 為了不要浪費版面，code和問題部份以圖片呈現
: (目前比較大的問題在其中一段)
: (code最上面的注解來自於網路上抓到的chaly77714大的os筆記，恐龍似乎沒有對這個程
: 式的控制變數提太多...)
: 問題圖片網址：
: http://i.imgur.com/wLhmd.jpg
: 好煩喔...看這支程式從早上10點看到下午3點一點進展都沒有 (又浪費一天...)
: 這個演算法真的比麵包店難懂很多...(而且我覺得這段看懂之後一定還有其他問題...)
: 根本快崩潰了...
: 都11月底了連這個都還看不懂...真是難過
: 懇請各位高手大德幫忙，拜託了，真的拜託了！ 謝謝大家...
這個code的前段主要分成兩個while loop，
第一個的離開條件是"從擁有turn的編號開始到自己都沒有人want-in"，
如果有的話就會卡在這個while loop裡面。
這個while loop只會檢查turn到自己，
所以如果現在6號先檢查完發現沒有人想進去，它就會變in-cs，
接著如果5號也想進去，因為1到4號依然沒有人想進去，它也會變in-cs，
依次類推，可能會很多個process都把自己改成in-cs。
第二個while loop，也就是你看不懂的那一段，
離開條件有兩種，第一種是在j==n時離開，
這種情況代表現在沒有其它process有in-cs狀態，
所以下一個if會跟著檢查現在擁有turn的人是不是idle，或者自己就有turn，
如果都成立就進去break，離開do while loop。
第二種離開條件是有其它人有in-cs的狀態，那麼這時j會還沒到n就離開，
所以下一個if的第一個條件一定是false而不會break，
接著會回到do while的頂端去把自己改回want-in狀態重新檢查。
你的code在critical section前面少了一段turn = i;
也就是要把turn值改成自己，
不然如果現在是因為擁有turn的人idle才讓自己進來的，
這樣可能會造成turn值無法以process編號的順序傳遞下去，
這樣在bounded waiting時可能會無法驗證。
這個解法其實就是Peterson's solution with n processes
只是後來的Peterson's solution變成2 processes的了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.136
※ 編輯: wheels 來自: 140.112.30.136 (11/28 12:32)
推 i78524:wheels大，謝謝你還特地開一篇來解釋他！ 11/28 12:54
→ i78524:我終於弄清楚第2個WHILE的的功用了 11/28 12:54
→ i78524:trace過n次之後現在我完全弄懂整支程式了 11/28 12:55
→ i78524:這題是請我們把這個CS設計改成monitor，所以我本來應該是 11/28 12:55
→ i78524:正確無誤，想不到在bound wait還有小缺失... 11/28 12:56
→ i78524:謝謝您的提醒與指教，真是太感謝您了 :) 11/28 12:56
→ i78524:(因為第8版課本題目code中CS上面並沒有 turn = i 這一段) 11/28 12:59
→ wheels:其實後來想想如果以bounded waiting的定義來說，沒有加那行 11/28 21:21
→ wheels:可能會允許某個process i在process j前進入2次，這個2次也 11/28 21:21
→ wheels:算是有限次數，所以應該也沒有違反。那行應該是洪逸自己加 11/28 21:22
→ wheels:的吧XD 11/28 21:22