Re: [理工] OS_busy-waiting

[forever3580 (阿基基)]

※ 引述《f111222003 (lai1003)》之銘言：
為什麼說semaphore的busy waiting

在製作層次的entry section無法完全避免呢

如果把Peterson或bankery的algo

其中while敘述後的no-op 改成block
然後其他程式完成後再wakeup

這樣也不能避免嗎



你這樣改 會出現一個問題
考慮一個情形
若現在所有人都要進去
假設現在除了p1再拿號碼牌之外
所有人都執行到
while(choosing()) block; //當有人拿號碼牌必須等他
則此時除了p1大家都被block
這時候p1順順的執行下去
會卡在第二個while (即判斷誰能先進去)
則此時 所有人都會被block
大家都會無法繼續執行下去
就算在拿完號碼牌後加一個wakeup
到最後
仍然只有兩個process進到第二個while
若兩個process皆非理想上先進去cs的
則所有process仍卡在block中



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.216.105
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1447394889.A.BEF.html
※ 編輯: forever3580 (223.139.216.105), 11/13/2015 14:15:24
※ 編輯: forever3580 (223.139.216.105), 11/13/2015 14:17:38
推 f111222003: 懂了 謝謝^^
→ f111222003: 不好意思 又想到如果第二個while block前先wake別人
→ f111222003:  讓其他人測試呢 這樣就總會輪到可以成功進去的那個pr
→ f111222003: ocess進入了
我有點沒懂你的意思
但如果你的意思是每個人經過都執行wake
那當你wake第一個人進去
而他還沒出來
你又在wake第二個人
而他是本來應該第二個人進去的
所以他也能通過條件再進去
那這時就不能保證只有一個人進到cs
不知道這樣有沒有回答到你的問題
※ 編輯: forever3580 (223.139.216.107), 11/13/2015 18:09:08
推 f111222003: 在while條件失敗後 process在block前去wake別人 讓其
→ f111222003: 他人去嘗試 如果有人在vs內 因為他的number還沒改成0
→ f111222003:  所以其他人也進不去 不過這樣好像變回另一種形式busy
→ f111222003:  waiting了
我也不知道這樣算不算busy waiting
但是這樣還是有一個問題
你可能沒看懂我上面的回答
我講清楚一點好了
假設 ID 為 A<B<C
此時A B C 三個程式都拿到1號號碼
但A還沒ASSIGN
而B進到第一個WHILE時因為A而被BLOCK
而C此時通過第一個WAKEUP時 叫醒 B
這時B會通過第二個WHILE而進到 CS
然後A此時也通過第一跟第二個WHILE 進到CS
這時候就會有兩個程式在CS了
※ 編輯: forever3580 (118.171.146.189), 11/14/2015 23:44:22
→ f111222003: C wake up B,
→ f111222003: B不是還會在第一個while嗎(如果A還在choosing)
對欸 抱歉我那時候沒有想清楚
那你這樣的設計我也想不出有什麼問題欸
而且我覺得這樣也不會算busy waiting

我唯一想的到比較好的解釋就是
你的設計也許是正確的
但是你這樣會浪費掉非常多的時間在做block 跟 wakeup
所以效率極差
如果是這樣的話就解釋得通了
因為 如果要non busy waiting的話
你也可以用disable interrupt
但是為什麼說不行
原因是因為他效率太低
同理 你這樣的設計可能是正確的
但是他不被用在解決同步問題的理由就跟disable interrupt一樣
它的效率極低 你看他的for 迴圈 是有可能發生每當j+1就block一次的問題
所以 結論還是 busy waiting 是無法被避免的
※ 編輯: forever3580 (114.40.58.3), 11/15/2015 22:52:15
※ 編輯: forever3580 (114.40.58.3), 11/16/2015 00:04:46