OS- -调度(一)
OS- -調度(一)
文章目錄
- OS- -調度(一)
- 一、調度
- 1.調度介紹
- 進程行為
- 何時調度
- 什么是空閑進程
- 調度算法的分類
- 調度算法的目標
- 2.批處理中的調度
- 先來先服務
- 最短作業優先
- 最短剩余時間優先
一、調度
- 當一個計算機是多道程序設計系統時,會頻繁的有很多進程或者線程來同時競爭CPU時間片。
- 當兩個 或兩個以上的進程/線程處于就緒狀態時,就會發生這種情況。如果只有一個CPU可用,那么必須選擇 接下來哪個進程/線程可以運行。
- 操作系統中有一個叫做調度程序(scheduler)的角色存在,它就是 做這件事兒的,該程序使用的算法叫做 調度算法(scheduling algorithm)。
- 盡管有一些不同,但許多適用于進程調度的處理方法同樣也適用于線程調度
- 當內核管理線程的時候, 調度通常會以線程級別發生,很少或者根本不會考慮線程屬于哪個進程。
下面我們會首先專注于進程和 線程的調度問題,然后會明確的介紹線程調度以及它產生的問題。
1.調度介紹
- 讓我們回到早期以磁帶上的卡片作為輸入的批處理系統的時代,那時候的調度算法非常簡單:依次運行 磁帶上的每一個作業。
- 對于多道程序設計系統,會復雜一些,因為通常會有多個用戶在等待服務。
- 一些 大型機仍然將 批處理和 分時服務結合使用,需要調度程序決定下一個運行的是一個批處理作業還是 終端上的用戶。
- 由于在這些機器中CPU是稀缺資源,所以好的調度程序可以在提高性能和用戶的滿意 度方面取得很大的成果。
進程行為
- 幾乎所有的進程(磁盤或網絡)I/O請求和計算都是交替運行的
- 如上圖所示,CPU不停頓的運行一段時間,然后發出一個系統調用等待I/O讀寫文件。
- 完成系統調用 后,CPU又開始計算,直到它需要讀更多的數據或者寫入更多的數據為止。當一個進程等待外部設備 完成工作而被阻塞時,才是I/O活動。
- 上面a是CPU密集型進程;b是I/O密集型進程進程,a因為在計算的時間上花費時間更長,因此稱 為計算密集型(compute-bound)或者CPU密集型(CPU-bound) , b因為I/O發生頻率比較快因此稱 為I/O密集型(I/O-bound)
- 計算密集型進程有較長的CPU集中使用和較小頻度的I/O等待。I/O 密集型進程有較短的CPU使用時間和較頻繁的I/O等待。
- 注意到上面兩種進程的區分關鍵在于CPU 的時間占用而不是I/O的時間占用。
- I/O密集型的原因是因為它們沒有在I/O之間花費更多的計算、而 不是I/O請求時間特別長。
- 無論數據到達后需要花費多少時間,它們都需要花費相同的時間來發出讀取 磁盤塊的硬件請求。
- 值得注意的是,隨著CPU的速度越來越快,更多的進程傾向于I/O密集型。這種情況出現的原因是 CPU速度的提升要遠遠高于硬盤。這種情況導致的結果是,未來對I/O密集型進程的調度處理似乎更 為重要。
- 這里的基本思想是,如果需要運行I/O密集型進程,那么就應該讓它盡快得到機會,以便發出 磁盤請求并保持磁盤始終忙碌。
何時調度
第一個和調度有關的問題是何時進行調度決策。存在著需要調度處理的各種情形。
- 首先,在創建一個新 進程后,需要決定是運行父進程還是子進程。因為二者的進程都處于就緒態下,這是正常的調度決策,可以任意選擇,也就是說,調度程序可以任意的選擇子進程或父進程開始運行。
- 第二,在進程退出時需要作出調度決定。因為此進程不再運行(因為它將不再存在),因此必須從就緒進程中選擇其他進程運行。如果沒有進程處于就緒態,系統提供的空閑進程通常會運行
什么是空閑進程
- 空閑進程(system-supplied idle process)是Microsoft公司windows操作系統帶有的系統進程,該進程是在各個處理器上運行的單個線程,它唯一的任務是在系統沒有處理其他線程時占用處理器 時間。
- System Idle Process并不是一個真正的進程,它是核心虛擬出來的,多任務操作系統都存在。
- 在沒有可用的進程時,系統處于空運行狀態,此時就是System Idle Process在正在運行。
- 你可以簡單 的理解成,它代表的是CPU的空閑狀態,數值越大代表處理器越空閑,可以通過Windows任務管理 器查看Windows中的CPU利用率
- 第三種情況是,當進程阻塞在I/O、信號量或其他原因時,必須選擇另外一個進程來運行。有時,阻塞 的原因會成為選擇進程運行的關鍵因素。
- 例如,如果A是一個重要進程,并且它正在等待B退出關鍵 區域,讓B退出關鍵區域從而使A得以運行。但是調度程序一般不會對這種情況進行考量。
- 第四點,當I/O中斷發生時,可以做出調度決策。如果中斷來自I/O設備,而I/O設備已經完成了其工作,那么那些等待I/O的進程現在可以繼續運行。由調度程序來決定是否準備運行新的進程還是重新運 行已經中斷的進程。
如果硬件時鐘以50或60 Hz或其他頻率提供周期性中斷,可以在每個時鐘中斷或第k個時鐘中斷處做 出調度決策。
根據如何處理時鐘中斷可以把調度算法可以分為兩類:
-
非搶占式(nonpreemptive)調度算法挑選一個進程,讓該進程運行直到被阻塞(阻塞在I/O上或等待另一個進程),或者直到該進程自 動釋放CPU。
-
即使該進程運行了若干個小時后,它也不會被強制掛起。這樣會在時鐘中斷發生時不會 進行調度。
-
在處理完時鐘中斷后,如果沒有更高優先級的進程等待,則被中斷的進程會繼續執行。
-
另外一種情況是搶占式調度算法,它會選擇一個進程,并使其在最大固定時間內運行。
-
如果在時間間 隔結束后仍在運行,這個進程會被掛起,調度程序會選擇其他進程來運行(前提是存在就緒進程)。
-
進 行搶占式調度需要在時間間隔結束時發生時鐘中斷,以將CPU的控制權交還給調度程序。如果沒有可 用的時鐘,那么非搶占式就是唯一的選擇。
調度算法的分類
毫無疑問,不同的環境下需要不同的調度算法。之所以出現這種情況,是因為不同的應用程序和不同的 操作系統有不同的目標。
也就是說,在不同的系統中,調度程序的優化也是不同的。這里有必要劃分出 三種環境
-
?批處理(Batch)
-
?交互式(Interactive)
-
?實時(Real time)
-
批處理系統廣泛應用于商業領域,比如用來處理工資單、存貨清單、賬目收入、賬目支出、利息計算、 索賠處理和其他周期性作業。
-
在 批處理系統中,一般會選擇使用非搶占式算法或者周期性比較長的搶占 式算法。這種方法可以減少線程切換因此能夠提升性 能。
-
在交互式用戶環境中,為了避免一個進程霸占CPU拒絕為其他進程服務,所以需要搶占式算法。
-
即使 沒有進程有意要一直運行下去,但是,由于某個進程出現錯誤也有可能無限期的排斥其他所有進程。為 了避免這種情況,搶占式也是必須的。
-
服務器也屬于此類別,因為它們通常為多個(遠程)用戶提供服 務,而這些用戶都非常著急。計算機用戶總是很忙。
-
在實時系統中,搶占有時是不需要的,因為進程知道自己可能運行不了很長時間,通常很快的做完自己 的工作并阻塞。
-
實時系統與交互式系統的差別是,實時系統只運行那些用來推進現有應用的程序,而交 互式系統是通用的,它可以運行任意的非協作甚至是有惡意的程序。
調度算法的目標
為了設計調度算法,有必要考慮一下什么是好的調度算法。
有一些目標取決于環境(批處理、交互式或 者實時)蛋大部分是適用于所有情況的
下面是一些需要考量的因素,我們會在下面一起討論。
- 在所有的情況中,公平是很重要的。對一個進程給予相較于其他等價的進程更多的CPU時間片對其 他進程來說是不公平的。當然,不同類型的進程可以采用不同的處理方式。
- 與公平有關的是系統的強制執行,什么意思呢?
- 如果某公司的薪資發放系統計劃在本月的15號,那么碰上了疫情大家生活都很拮據,此時老板說要在14號晚上發放薪資,那么調度程序必須強制使進程執行 14號晚上發放薪資的策略。
- 另一個共同的目標是保持系統的所有部分盡可能的忙碌。如果CPU和所有的I/O設備能夠一直運行, 那么相對于讓某些部件空轉而言,每秒鐘就可以完成更多的工作。
- 例如,在批處理系統中,調度程序控 制哪個作業調入內存運行。
- 在內存中既有一些CPU密集型進程又有一些I/O密集型進程是一個比較好的想法,好于先調入和運行所有的CPU密集型作業,然后在它們完成之后再調入和運行所有I/O密集型作業的做法。
- 使用后者這種方式會在CPU密集型進程啟動后,爭奪CPU ,而磁盤卻在空轉,而當I/O密集型進程啟動后,它們又要為磁盤而競爭,CPU卻又在空轉。。。。。。
- 顯然,通過結合I/O密集型和CPU密集型,能夠使整個系統運行更流暢,效率更高。
- 批處理系統
- 通常有三個指標來衡量系統工作狀態:吞吐量、周轉時間和CPU利用率,吞吐量(throughout)是 系統每小時完成的作業數量。
綜合考慮,每小時完成50個工作要比每小時完成40個工作好。
- 周轉時 間(Turnaround time)是一種平均時間,它指的是從一個批處理提交開始直到作業完成時刻為止平均 時間。該數據度量了用戶要得到輸出所需的平均等待時間。周轉時間越小越好。
- CPU利用率(CPU utilization)通常作為批處理系統上的指標。即使如此,CPU利用率也不是一 個好的度量指標,真正有價值的衡量指標是系統每小時可以完成多少作業(吞吐量),以及完成作業需 要多長時間(周轉時間)。
- 把CPU利用率作為度量指標,就像是引擎每小時轉動了多少次來比較汽車 的性能一樣。
- 而且知道CPU的利用率什么時候接近100%要比什么什么時候要求得到更多的計算能力 要有用。
-
交互式系統
-
對于交互式系統,則有不同的指標。最重要的是盡量減少響應時間。這個時間說的是從執行指令開始 到得到結果的時間。
- 再有后臺進程運行(例如,從網絡上讀取和保存E-mail文件)的個人計算機上, 用戶請求啟動一個程序或打開一個文件應該優先于后臺的工作。
- 能夠讓所有的交互式請求首先運行的就 是一個好的服務。
- 一個相關的問題是 均衡性(proportionality),用戶對做一件事情需要多長時間總是有一種固定 (不過通常不正確)的看法。
- 當認為一個請求很復雜需要較多時間時,用戶會認為很正常并且可以接受,但是一個很簡單的程序卻花費了很長的運行時間,用戶就會很惱怒。
- 可以拿彩印和復印來舉出一個 簡單的例子,彩印可能需要1分鐘的時間,但是用戶覺得復雜并且愿意等待一分鐘,相反,復印很簡單 只需要5秒鐘,但是復印機花費1分鐘卻沒有完成復印操作,用戶就會很焦躁。
- 實時系統
實時系統則有著和交互式系統不同的考量因素,因此也就有不同的調度目標。
- 實時系統的特點是必須滿 足最后的截止時間。
- 例如,如果計算機控制著以固定速率產生數據的設備,未能按時運行的話可能會導 致數據丟失。
- 因此,實時系統中最重要的需求是滿足所有(或大多數)時間期限。
- 在一些實事系統中,特別是涉及到多媒體的,可預測性很重要。偶爾不能滿足最后的截止時間不重要, 但是如果音頻多媒體運行不穩定,聲音質量會持續惡化。
- 視頻也會造成問題,但是耳朵要比眼睛敏感很 多。
為了避免這些問題,進程調度必須能夠高度可預測的而且是有規律的。
2.批處理中的調度
現在讓我們把目光從一般性的調度轉換為特定的調度算法。
下面我們會探討在批處理中的調度。
先來先服務
很像是先到先得。。。
- 可能最簡單的非搶占式調度算法的設計就是 先來先服務(first-come,first-serverd)。使用此算法,將按照請求順序為進程分配CPU。
- 最基本的,會有一個就緒進程的等待隊 列。當第一個任務從外部進入系統時,將會立即啟動并允許運行任意長的時間。它不會因為運行時間太 長而中斷。
- 當其他作業進入時,它們排到就緒隊列尾部。當正在運行的進程阻塞,處于等待隊列的第一 個進程就開始運行。
- 當一個阻塞的進程重新處于就緒態時,它會像一個新到達的任務,會排在隊列的末 尾,即排在所有進程最后。
- 這個算法的強大之處在于易于理解和編程,在這個算法中,一個單鏈表記錄了所有就緒進程。
- 要選取一 個進程運行,只要從該隊列的頭部移走一個進程即可;要添加一個新的作業或者阻塞一個進程,只要把 這個作業或進程附加在隊列的末尾即可。
這是很簡單的一種實現。
- 不過,先來先服務也是有缺點的,那就是沒有優先級的關系,
- 試想一下,如果有100個I/O進程正在排 隊,第101個是一個CPU密集型進程,那豈不是需要等100個I/O進程運行完畢才會等到一個CPU 密集型進程運行
- 這在實際情況下根本不可能,所以需要優先級或者搶占式進程的出現來優先選擇重要 的進程運行。
最短作業優先
-
批處理中,第二種調度算法是最短作業優先(Shortest Job First)
-
我們假設運行時間已知。例 如,一家保險公司,因為每天要做類似的工作,所以人們可以相當精確地預測處理1000個索賠的一批 作業需要多長時間。
-
當輸入隊列中有若干個同等重要的作業被啟動時,調度程序應使用最短優先作業算法
-
如上圖a所示,這里有4個作業A、B、C、D,運行時間分別為8、4、4、4分鐘。
-
若按圖中的次序 運行,則A的周轉時間為8分鐘,B為12分鐘,C為16分鐘,D為20分鐘,平均時間內為14分 鐘。
-
現在考慮使用最短作業優先算法運行4個作業,如上圖b所示,目前的周轉時間分別為4、8、12、 20,平均為11分鐘,可以證明最短作業優先是最優的。
-
考慮有4個作業的情況,其運行時間分別為 a、b、c、d。第一個作業在時間a結束,第二個在時間a + b結束,以此類推。平均周轉時間為(4a + 3b + 2c + d)/4。
-
顯然a對平均值的影響最大,所以a應該是最短優先作業,其次是b,然后是c , 最后是d它就只能影響自己的周轉時間了。
-
需要注意的是,在所有的進程都可以運行的情況下,最短作業優先的算法才是最優的。
最短剩余時間優先
-
最短作業優先的搶占式版本被稱作為最短剩余時間優先(Shortest Remaining Time Next)算法。
-
使用這個算法,調度程序總是選擇剩余運行時間最短的那個進程運行。
-
當一個新作業到達時,其整個時 間同當前進程的剩余時間做比較。如果新的進程比當前運行進程需要更少的時間,當前進程就被掛起, 而運行新的進程。
-
這種方式能夠使短期作業獲得良好的服務。
未完。。。
總結
以上是生活随笔為你收集整理的OS- -调度(一)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: OS--进程间通信详解(二)
- 下一篇: OS- -调度(二)