Re: [理工] 作業系統 ch5 process scheduling

[A4P8T6X9 (殘廢的名偵探)]

※ 引述《mozzan (mozzan)》之銘言：
: 這是恐龍第八版的習題 (ch5 process scheduling)
: 5.16
: Consider a preemptive priority scheduling algorithm based on dynamically
: changing priority. Larger priority numbers imply higher priority.
: When a process is waiting for the CPU (in the ready, but not running), its
: priority changes at rate A; when it is running. its priority changes at a rate
: B. All processes are given a priority of 0 when they enter the ready queue.
: The parameter A and B can be set to give many different scheduling algorithm.
: a. What is the algorithm that result form B > A > 0  (A : FCFS)
: b. What is the algorithm that result form A < B < 0  (A : LIFO)
: 另外題庫還有
: c. What is the algorithm that result form A > B > 0  (A : LIFO)
: d. What is the algorithm that result form B < A < 0  (A : FCFS)
: a和b 沒問題
: 其他都不太了解為甚麼，像 A > B > 0
: 剛進入Ready queue的為0，原先在Ready queue和Runing的priority應該都較高
: 為何答案卻是 LIFO
: 而 B < A < 0
: 就更不懂了，煩請大家解惑，感謝

要以 process 執行時間相對長的方面來思考，如果執行時間都超短，那麼不管是哪一個都是
FCFS 因為瞬間就好了，也沒有換不換的問題了。

在此先假設一個前提：執行時間短的基本上都會先完成，相對來說執行時間短的參考度比
較低，所以討論偏重執行時間長的。

值得一提的是題目中還有假設進入ready queue中的process priority都會設成零，言下
之意便是即使在 CPU 中養了很久有很高的 priority ，一離開也變成浮雲了。

那麼，以 c 來說等待中的 process 權限會上升得比較快，如果大家都不能一下子就完
成，後面進來的總有機會追過前面 process 的 priority，所以後面有機會進去 CPU執
行，如果後面相對時間短，那麼就是 LIFO 了，當然如果後面時間是長的，那麼前面會先
做完，可是根據我們假設短的本來就會先做完，參考度低，不看，在後面進來的總有更短
的，所以整體來看還是 LIFO。

以 d 來說，進去執行的，一下就會被踢出來，可是他一進入 ready 他又是 0 所以又可
以進入 CPU，就是 FCFS 了。

參考看看 ~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 221.120.2.85
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1404045411.A.F83.html
推 mozzan:請問您c的假設是以兩個process在競爭嗎?
→ A4P8T6X9:不只，如果第二個時間長，那個在後面的總有短的。
推 mozzan:大概了解，但c我的理解是這邊的LIFO指的是後面的可能超前
→ mozzan:而好像不一定是指"Last"，不一定指最後進來Ready的那一個
→ mozzan:是這樣嗎?
→ A4P8T6X9:在後面超前完成那一個時間點，不就是 LIFO?
→ mozzan:因為我一直以為是像stack的，像是b，最後進來的為0，馬上可
→ mozzan:以Run，如果之後沒有其他Process進到Ready，就一直跑到結束
→ mozzan:直覺看起來似乎就真的是最後進來的Process，第一個結束