iT邦幫忙

1

【小黑馬作業系統教室】(14) (Ch5) 程式排程問題,以古代皇上見大臣做為比喻

嗨嗨,大家好,我是心原一馬,
講完了「記憶體管理」,
我們回頭來看OS中另一個重要的章節,「排程」。

上一篇: 【小黑馬作業系統教室】(13) (Ch9) Page replacement algorithm- 過目即忘的可憐記憶

動機- 什麼是排程?

讓我們回顧【文科生都能懂的小黑馬作業系統教室】(4)這篇的比喻,

  • CPU- 電腦用來運作程式的地方,我們可以把它比喻為「老師」
  • process- 電腦程式(如瀏覽器、LINE、word、powerpoint),我們可以把它比喻為「老師處理學生問題的過程」(比如說: 要老師批改學生的作業、有課業問題要問老師)
  • context switch- 老師快速穿梭教室間,輪流處理學生問題。

想像現在有一群學生要排隊問老師問題好了,
每個學生需要的問問題時間可能不同,
有的學生可能只是要問小問題,只需要1分鐘,
有的學生可能有很多問題想問,需要30分鐘,
那麼老師選擇接下來讓哪個學生問問題就是排程
(scheduler 選擇接下來換哪支程式給CPU執行)

然而,將CPU比喻成老師,process比喻成學生,
排程比喻為老師選擇接下來讓哪個學生問問題並不完全恰當,
因為實際上CPU不負責選擇接下來換哪支程式執行,
CPU只負責執行程式,
選擇接下來換哪支程式給CPU執行的角色為scheduler。
小馬在網上找到一篇關於作業系統的排程的筆記
小馬覺得相當貼切,
在此引用這篇筆記,
將它整理至此。

比喻: 皇上見大臣

在古代,臣子想要見皇帝一面是需要先跟太監報備的,
如果太監不喜歡這個臣子,
那麼他恐怕就很難見到皇帝一面。
那麼,在這個例子中-

  • 皇帝: CPU
  • 太監: 排班程式(scheduler)
  • 眾臣: 程式(process)

故事是這樣的,

假設現在皇帝正在跟 1 號大臣討論賦稅的問題。2 號的大臣匆匆趕來,他想跟皇帝
討論選妃的事,太監覺得不是什麼大不了的事,就請 2 號大臣在外頭等候聽宣。
這時 3 號大臣也來了,他說十萬火急,因為匈奴入侵中原了... 太監一聽,此事
非同小可,所以他立刻帶著 3 號大臣進去面聖,而 1 號大臣就被帶出到外頭候著。
這時 4 號大臣也跑來,他想問問皇帝冬天要不要去遊江南避寒。這種芝麻小事,
太監也會叫他在外頭候著。當皇帝跟 3 號大臣擬定戰略部署後, 3 號大臣便離去。
這時太監便開始想,到底這時該讓誰去面聖 ? 是賦稅、選妃、還是下江南遊樂重要?

注意,排程問題有分「可搶先(preemptive)」與「不可搶先(non-preemptive)」兩種,
在故事中,
皇上還沒處理完1號大臣的問題,
就先換處理3號大臣的問題,
這就是可搶先的例子。
如果皇上必須先處理完1號的問題,
或1號大臣忘記拿資料先回家拿(比喻: 程式做I/O),
才換3號進來面聖,
那就是不可搶先的例子。(雖然2號比3號先來)

常見的scheduling algorithm

一、先來先到排程法(first-come-first-served, FCFS)

如果太監依照大家來的順序一個接著一個帶去見皇帝,
稱為FCFS排程法。

  • 例子: 1號大臣(24分鐘)、2號大臣(3分鐘)、3號大臣(3分鐘),在時間點0時,依序來了2、3、1號大臣。

https://ithelp.ithome.com.tw/upload/images/20191226/20117114SRpEcN4olh.png
那麼對於每個大臣來說,
1號等待時間為6分鐘,
2號等待時間為0分鐘,
3號等待時間為3分鐘,
平均等待時間(average waiting time,簡稱AWT)為(6+0+3)/3=3分鐘。

  • 潛在問題: convoy effect(護衛效應),指的是如果執行時間短的程式排在執行程式長的程式後面,造成的平均等待時間很長。
  • 例子: 1號大臣(24分鐘)、2號大臣(3分鐘)、3號大臣(3分鐘),在時間點0時,依序來了1、2、3號大臣。

https://ithelp.ithome.com.tw/upload/images/20191226/2011711412DHXopqrZ.png
若將上例大臣來的順序稍微改一下,
那麼對於每個大臣來說,
1號等待時間為0分鐘,
2號等待時間為24分鐘,
3號等待時間為27分鐘,
AMT= (0+24+27)/3=17分鐘,平均等待時間則高達17分鐘,
因此,先來先到排程法很可能為了等執行時間長的程式,對效能有不良的影響。

二、最短工作優先排程法(shortest job first,簡稱SJF)

優先執行可以最快結束的程式,改良convoy effect的問題,
亦分為「可搶先(preemptive)」與「不可搶先(non-preemptive)」兩種。

  1. 可搶先: 故事中,當 2 號大臣來時,太監發現 2 號大臣只帶了兩張妃子畫像。反正很快,太監便帶 2 號大臣先給皇上選妃,讓1號暫時先去等候。
  2. 不可搶先:等 1 號討論完之後,太監再看看目前等候的臣子(2,3,4),誰可以最快跟皇帝討論完,就帶誰進去面聖。

三、優先等級排程法(priority scheduling)

亦分為「可搶先(preemptive)」與「不可搶先(non-preemptive)」兩種。
原故事中的太監即屬於可搶先的優先等級排程法

但是潛在的問題便是如果一直有其它大臣有重要事情來找皇上,
那對於小事來找皇上的大臣,可能排隊很久也見不到皇上,
用電腦語言來說即為:

  • 潛在問題: starvation(餓死),專業術語,指的是程式一直沒有被執行到的狀況。原因是若優先權高的程式一直不斷的來,那麼優先權低的程式就可能永遠執行不到。
  • 解決方法: aging(年齡增長),意思是每隔一段時間,就增加沒有被執行程式的優先權,避免有些程式永遠等不到CPU執行。

四、知更鳥式排程法(Round-Robin,簡稱RR)

太監每隔10分鐘就進去對皇帝說,皇上,十分鐘到了,先輪下一位大臣吧...

以上便是常見的排程演算法及常見的議題,
以下準備一些問題給大家自我檢測吧。

自我檢測題

  • (基礎題)什麼是convoy effect?
  • (基礎題)什麼是starvation?
  • (for 資工本科學生題目) 1. 在SJF演算法中,我們會優先讓程式所需執行時間最短的程式給CPU執行。這邊所指的執行時間稱為CPU burst time。參考下方的程式生命週期圖,請問下列何者應為一次CPU burst time的定義?
    (A)一隻程式從new state直到terminated為止,在running state的時間總和
    (B)一隻程式從一個I/O結束到下一個I/O開始前,在running state的時間總和
    (C)一隻程式從ready state進入running state的瞬間算起,直到下次被context switch 換到ready state之前的時間

https://ithelp.ithome.com.tw/upload/images/20191216/201171144xjagEV3Ul.png

    1. 承上,關於不可搶先(non-preemptive)排程法,指的是…
      (A)程式必須執行完畢(terminated)才可以換其它程式執行
      (B)程式在running state中,不可被切換至其它狀態
      (C)程式不可以在CPU burst time結束前被其它程式搶先
      (D)程式不可以在做I/O的時候被其它程式打斷

(往下翻以跟小馬核對答案…)




















  1. (B)
  2. (C)
    (如答案有誤或題目敘述有瑕疵還請不吝告知)

尚未有邦友留言

立即登入留言