[理工] [OS] semaphore (bounded waiting)

看板Grad-ProbAsk作者 (thisisfornote)時間9年前 (2016/12/11 16:31), 9年前編輯推噓8(8推 0噓 40→)
留言48則, 6人參與, 最新討論串1/1
http://i.imgur.com/80REHsS.jpg
想問一下 如果pi執行signal後 比pj更快執行wait(mutex) pj無法進入C.S 這樣不就可能違反bounded waiting嗎？ ----- Sent from JPTT on my InFocus M350. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.36.156 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1481445109.A.5DF.html ※ 編輯: fornote (101.10.36.156), 12/11/2016 16:32:16
→
12/11 16:41, , 1F
可以想像有個queue?
12/11 16:41, 1F
→
12/11 16:47, , 2F
FIFO queue?
12/11 16:47, 2F
推
12/11 16:58, , 3F
pj已經卡在wait， pi一signal他就不會卡在wait。
12/11 16:58, 3F
→
12/11 17:06, , 4F
嗯這我明白 那有沒有可能pi一signal pi比pj更快執行wait(
12/11 17:06, 4F
→
12/11 17:06, , 5F
mux)
12/11 17:06, 5F
→
12/11 17:13, , 6F
那pj等於跟pi同時進，他搶輸pi就等pi singal就好,等一
12/11 17:13, 6F
→
12/11 17:13, , 7F
次而已。
12/11 17:13, 7F
→
12/11 17:15, , 8F
不然你pi signal前pj就在,pj一定會在wait
12/11 17:15, 8F
推
12/11 17:15, , 9F
不可能
12/11 17:15, 9F
→
12/11 18:04, , 10F
感謝
12/11 18:04, 10F
推
12/11 18:10, , 11F
srmaphore 僅保證mutual exclusion 是否有bounded wa
12/11 18:10, 11F
→
12/11 18:10, , 12F
iting要看實作
12/11 18:10, 12F
→
12/11 18:11, , 13F
https://goo.gl/LftxrI 這篇寫很好可以參考
12/11 18:11, 13F
→
12/11 18:13, , 14F
@k2 這要看scheduler怎麼排吧 pi還是有可能繼續等
12/11 18:13, 14F
→
12/11 18:14, , 15F
說錯 pj仍有可能繼續等 如果scheduler沒排到他
12/11 18:14, 15F
推
12/11 19:08, , 16F
同步探討的bounded waiting並沒有把排程考慮進去吧！不然
12/11 19:08, 16F
→
12/11 19:08, , 17F
前面的臨界區間設計演算法都沒滿足bounded waiting了不是
12/11 19:08, 17F
→
12/11 19:08, , 18F
嗎？
12/11 19:08, 18F
推
12/11 19:43, , 19F
有滿足阿 四個演算法都有另外設計變數來達成
12/11 19:43, 19F
→
12/11 19:43, , 20F
Bound waiting
12/11 19:43, 20F
→
12/11 19:43, , 21F
ex. turn, flag...etc
12/11 19:43, 21F
→
12/11 19:45, , 22F
另外process synchronization本來就要考慮到scheduling
12/11 19:45, 22F
推
12/11 19:56, , 23F
原來如此...這樣說來用semaphore去設計臨界區間的進入區
12/11 19:56, 23F
→
12/11 19:56, , 24F
離開區還需要特別設計別的變數來保證bounded waiting嗎@@
12/11 19:56, 24F
→
12/11 19:56, , 25F
？
12/11 19:56, 25F
→
12/11 19:58, , 26F
我說的是只有這二個process的情形
12/11 19:58, 26F
→
12/11 20:03, , 27F
@newpuma yes, 像是block和wake這兩個call有維持一個
12/11 20:03, 27F
→
12/11 20:03, , 28F
fifo queue
12/11 20:03, 28F
→
12/11 20:04, , 29F
@k2 如果CPU一直沒切給pj pi的確一直有可能一直跑下去?
12/11 20:04, 29F
推
12/11 20:09, , 30F
瞭解，有點像是排程的starvation問題了 (雖然bounded wai
12/11 20:09, 30F
→
12/11 20:09, , 31F
ting也隱含這層意思)
12/11 20:09, 31F
→
12/11 20:26, , 32F
假如發生你講那種情形就程式會有bug，但不是這個設計造
12/11 20:26, 32F
→
12/11 20:26, , 33F
成的啊
12/11 20:26, 33F
→
12/11 21:35, , 34F
這樣不是就代表這個設計沒有保證bounded waiting @@?
12/11 21:35, 34F
→
12/11 22:19, , 35F
Bounded waiting不是只考慮使用同個semaphore的process
12/11 22:19, 35F
→
12/11 22:19, , 36F
嗎？
12/11 22:19, 36F
→
12/11 22:24, , 37F
現行 os 系統關於假設性的問題基本上都沒有一定答案
12/11 22:24, 37F
→
12/11 22:25, , 38F
如同洪逸筆記上 bound waiting 是假設有 queue 滿足
12/11 22:25, 38F
→
12/11 22:26, , 39F
該項 , 但真的只能假設 queue 而已嗎 ? 絕對還有別
12/11 22:26, 39F
→
12/11 22:26, , 40F
種方式 去決定要怎麼排程 只是有太多種方法了
12/11 22:26, 40F
→
12/11 22:27, , 41F
就連恐龍本也只是概念式地稍微講解
12/11 22:27, 41F
→
12/11 22:28, , 42F
在能保證不會Stravation 的情況下 , 是否能讓優先度
12/11 22:28, 42F
→
12/11 22:30, , 43F
較高的再多跑幾次 (假設quantum 有限)
12/11 22:30, 43F
→
12/11 22:31, , 44F
有很多手段都可以達到此目的
12/11 22:31, 44F
推
12/12 13:36, , 45F
洪毅上課有說～ 看起來會不滿足bounded waiting 但這不是
12/12 13:36, 45F
→
12/12 13:36, , 46F
使用者要考量的 這必須是設計semaphore的設計者要考量的
12/12 13:36, 46F
→
12/12 13:36, , 47F
（最簡單可能就是用waiting queue） 所以我們是以使用者
12/12 13:36, 47F
→
12/12 13:36, , 48F
的角度來看他能否解決cs問題 就不須考慮此
12/12 13:36, 48F
‣ 更多 fornote 的文章
文章代碼(AID): #1OJGxrNV (Grad-ProbAsk)