[商管] 103交大資管 資結

[liang0962054 (waiting for you)]

http://imgur.com/hD3CA83
想請問一下這題，我第一個想到的方法是os的SJRF，也就是preemptive SJF，
用這個方法的話，data structure感覺可以以Queue來回答，但time complexity
就不知道該怎麼回答了，還是應該要用其他的方法來解決這題？

麻煩大家了，謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.34.156.140
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485177472.A.DCB.html
推 yupog2003: 如果用SRJF，priority queue用min-heap來做的話，也許
→ yupog2003: 每次挑process出來是O(1)，有process進來queue等待時要
→ yupog2003: 花O(logn)進入queue裡面，這樣回答不知道可不可以？
感覺可以欸~
再請問一下，在worst case的情況下，preemptive最多可以幾次? (剛剛忘記一起問了)
※ 編輯: liang0962054 (1.34.156.140), 01/23/2017 22:43:14
→ yupog2003: 我覺得可以到n-1次，P1 burst time好長好長，P2很快就
→ yupog2003: 來，但是burst time都好長好長，只比P1短了一點
→ yupog2003: 每次都給他剛好可以preemptive是有可能的
→ yupog2003: P1 burst time = 10000000000, arrival time = 0
→ yupog2003: P2 burst time = 1000000000, arrival time = 10
→ yupog2003: P3 burst time = 100000000, arrival time = 100
→ yupog2003: 這樣湊可以湊出每次來都要preemptive
→ yupog2003: 不知道是不是出題老師想要的答案就是了...