iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 9
0
自我挑戰組

作業系統概論系列 第 9

DAY9 CPU Scheduling(上)

基礎概念

  • 目的就是為了讓CPU在multiprogramming執行效率提高。
  • 行程執行中包含了CPU burst和I/O burst的循環,當一個在執行時,另一個就會等待,直到輪到它執行為止,如此循環下去。
  • 當一個行程中的CPU burst在等待時,可以先分配給其他行程使用。

CPU Scheduler

  • Short-term scheduler:從在ready queue中的行程進行選擇,並分配CPU給其中之一。
  • CPU scheduling決定行程要發生什麼事:
  1. 從running轉換到waiting狀態
  2. 從running轉換到ready的狀態
  3. 從waiting轉換到ready的狀態
  4. Terminates
    =>其中(1)和(4),是必須做完動作,不能中斷的,為nonpreemptive;而(2)和(3)是可以中斷的,為preemptive,但須注意三點:
    1-須小心是否有使用share data。
    2-是否是在kernel model下使用
    3-是否能接受interrupt

Dispather

  • 將CPU的控制權交給由short-term scheduler選擇的行程。其中包含:
  1. 環境轉換
  2. 轉換到使用者模組
  3. 轉換到適當的user program去,並重新開始program。
  • Dispatch latency:時間到了,中斷正在執行的行程,並開始另外一個。

Scheduling Criteria

  • CPU utilization:使CPU盡量保持忙碌狀態。
  • Througput:在單位時間內完成的工作量。
  • Turnaround time:一個行程從進入CPU到完成的所需時間,而時間越短越好。
  • Waiting time:行程在ready queue中已經等待多少時間,時間越短越好。
  • Response time:在time-sharing的環境中,從一個request進入到得到回應的所需時間,時間越短越好。

First-Come,First-Served(FCFS) Sheduling

  • 先到的行程先執行。
  • 很公平,但會有效率問題。易發生Convoy effect。

Shortest-Job-First(SJF) Scheduling

  • 聯繫每個行程的長度,去決定下一個CPU burst。
  • SJF is optimal:以最小平均等待時間給予一個行程。
  • 困難的地方在於並不確定每個job確切的執行時間。
  • 是最佳化的排程演算法。

決定下個CPU Burst的長度

  • 只能估算長度,但須和前一個相似。
  • shortest-remaining-time-first:如果後來的job時間比正在執行的完成時間還短,會先interrupt正在執行的,等後來的job執行完成,再接續完成被中斷的job。

Priority Scheduling

  • 每個行程都連接到一個整數數字,數字越小代表優先權越大。
  • CPU會被分配給最高優先權的行程使用。
  • 會產生問題:Starvation-因為已執行時間最短的為優先,所以低優先權的行程很有可能都不會被執行,成為「飢餓」狀態。
  • 解決辦法:Aging-讓等待時間久的行程提高優先權,才能有機會被執行。

Round Robin(RR)

  • 無論行程有無執行完畢,時間到即中斷。
  • 每個行程可以得到1/n的CPU時間,沒有一個行程會等到q(1/n)倍的時間長才執行。

Mutilevel Queue

  • Ready queue被分割成單獨的佇列:
  1. foreground(interactive)
  2. background(Batch)
  • 每個佇列擁有自己的scheduling algorithm:
  1. foreground-RR
  2. background-FCFS(不太在乎要立即回應)
  • Scheduling須在佇列間完成。
  1. Fixed queue:可能會產生「飢餓」的機會。
  2. Time slice:得到一定量的CPU時間後,在安排在行程中。

Multilevel Feedback Queue

  • 可以在多個佇列間移動;Aging方法可以利用此方式執行。
  • 由參數所定義:
  1. 佇列的數量
  2. 使用方法決定何時更新行程
  3. 使用方法決定何時降級行程
  4. 使用方法決定當行程需要服務時,哪個佇列該進入行程。

上一篇
DAY 8 Threads(下)
下一篇
DAY 10 CPU Scheduling(中)
系列文
作業系統概論30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言