iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 10
0
自我挑戰組

OS作業系統學習系列 第 10

第十天 CPU Scheduling--下

第十天 CPU Scheduling--下

昨天講完Multiple-Processor Scheduling,今天來說說Real-Time CPU Scheduling。

Real-Time CPU Scheduling(即時應用排程):
Real-Time system分為兩種:

  1. soft real-time system:會盡量完成工作,但不保證
  2. hard real-time system:所有工作要在時間內完成

而影響real-time system的主要因素為latency:

  • interrupt latency:中斷造成得時間延遲
  • dispatch latency:process轉換耗費的時間、決定哪個process用CPU

在real-time system中,根據優先權做排程(priority-based scheduling)是很重要的(只在soft real-time有保證)。假設process的執行時間是t、deadline是d、週期時間是p,如果t < d < p,check的頻率就是1/p。

而我們之前提到,一個作業系統中有很多個作業系統(guest OS),這是在虛擬化的環境下執行。如果每個guest OS做自己的排程,就會有下列幾個問題:

  • 不知道自己沒有能力控制CPU
  • Response time沒有自己單一控制CPU來得好
  • 不同的作業系統,處理時間不一樣

而在real-time scheduling中運用的演算法有:

  1. Rate Monotonic Scheduling:
    是最常用的演算法,依據頻率高低決定優先權,週期短(頻率高)有高優先權,週期長(頻率低)較低優先權。以下為例題跟運算:
    https://ithelp.ithome.com.tw/upload/images/20181024/20112132qQhtFy89N3.png

    但這個演算法有時會把deadline給miss掉,所以有了下一個演算法來彌補

  2. Earliest Deadline First Scheduling:
    依據誰的deadline先到,誰的優先權就越高。以下有範例即運算:
    https://ithelp.ithome.com.tw/upload/images/20181024/20112132s2QiplDOi0.png

  3. Proportional Share Scheduling:
    這種演算法比較注重公平性,假設T是CPU時間、N是application要分享CPU的時間(N < T),這樣每個application都收到N / T時間,但事前需要把資源比例分配好。

那上面那麼多演算法,我們要怎們選擇呢?這時我們可以用以下幾種評估方式:

  1. Deterministic modeling:
    是以分析的方式,選擇哪種演算法適合。但是我們沒有那麼多時間,可以用運算waiting time的時間做分析。
  2. Queueing modeling:
    已排隊的情形來決定,他有一個重要的公式—Little’s Law,以下是他的說明:
    https://ithelp.ithome.com.tw/upload/images/20181024/201121327z0BVmu1O8.png
    n是平均queue的長度
    W是在queue平均waiting time
    λ是平均進到queue的速度
  3. Simulations:
    在模擬環境中執行看結果,以下有舉例:
    https://ithelp.ithome.com.tw/upload/images/20181024/201121329oOeyUSBTV.png
  4. Implementation:
    實作出來,但是會耗費金錢且有高風險,不知道做出來是不是真的是最好的。

以上我們就講完CPU Scheduling啦!


上一篇
第九天 CPU Scheduling--中
下一篇
第十一天 Process Synchronization(同步)--上
系列文
OS作業系統學習30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言