作業系統之行程管理（2）

3、行程通信

什么是行程通信？

行程通信就是行程之間的資訊交換，行程是分配系統資源的單位（包括記憶體地址空間），因此各個行程擁有的記憶體地址空間相互獨立，為了保證安全，一個行程并不能直接訪問另一個行程的地址空間，但是行程之間的資訊交換又是不可避免的，為了保證執行緒安全，就會出現一些行程通信的方法：共享存盤、訊息傳遞和管道通信，

3.1、共享存盤

為兩個行程設立一個共享存盤區，兩個行程需要互斥（通過PV操作）的訪問共享空間，

共享存盤分為 基于資料結構 和 基于存盤區 兩種：

基于資料結構：只能放固定資料結構的資料，速度慢，限制多，是一種低級通信方式，

基于存盤區：資料形式由行程控制，是高級通信方式，

3.2、訊息傳遞

行程間通過 “發送訊息”、“接受訊息”這兩個原語來進行資料交換

類似與郵件，有一個訊息信箱作為行程間訊息的中轉站，行程要先將訊息發送到信箱中去，行程收到訊息后將訊息掛到訊息佇列上，

訊息類似于網路報文，分為訊息頭和訊息體兩部分，訊息頭包括發送行程id，接受行程id，訊息型別，訊息長度等（和計網完全類似），

3.3、管道通信

總結：

4、處理機調度概念與層次

什么是調度？

當有一堆任務要處理，但由于資源有限，這些事情沒法同時處理，這就需要確定某種規則來決定處理這些任務的順序，這就是“調度”研究的問題，

什么是處理機調度？

在多道程式系統中，行程的數量往往是多于處理機的個數的，這樣不可能同時并行地處理各個行程，處理機調度，就是從就緒佇列中按照一定的演算法選擇一個行程并將處理機分配給它運行，以實作行程的并發執行，

4.1、調度的三個層次

• 高級調度

高級調度(作業調度)，按一定的原則從外存上處于后備佇列的作業中挑選-一個(或多個)作業，給他們分配記憶體等必要資源，并建立相應的行程(建立PCB)，以使它(們)獲得競爭處理機的權利，

由于記憶體空間有限，有時無法將用戶提交的作業全部放入記憶體，因此就需要確定某種規則來決定將作業調入記憶體的順序，

高級調度是輔存(外存)與記憶體之間的調度，每個作業只調入一次，調出一次，作業調入時會建立相應的PCB.作業調出時才撤銷PCB，高級調度主要是指調入的問題，因為只有調入的時機需要作業系統來確定，但調出的時機必然是作業運行結束才調出，

• 中級調度

中級調度(記憶體調度)，就是要決定將哪個處于掛起狀態的行程重新調入記憶體，

一個行程可能會被多次調出、調入記憶體，因此中級調度發生的頻率要比高級調度更高，

引入了虛擬存盤技術之后，可將暫時不能運行的行程調至外存等待，等它重新具備了運行條件且記憶體又稍有空閑時，再重新調入記憶體，這么做的目的是為了提高記憶體利用率和系統吞吐量，

暫時調到外存等待的行程狀態為掛起狀態，值得注意的是，PCB并不會一 起調到外存， 而是會常駐記憶體，PCB中會記錄行程資料在外存中的存放位置，行程狀態等資訊，作業系統通過記憶體中的PCB 來保持對各個行程的監控、管理，被掛起的行程PCB會被放到的掛起佇列中，

• 低級調度

低級調度(行程調度)，其主要任務是按照某種方法和策略從就緒佇列中選取-一個行程，將處理機分配給它，

行程調度是作業系統中最基本的一種調度， 在一般的作業系統中都必須配置行程調度，
行程調度的頻率很高，一般幾十毫秒一次，

• 高級、中級、低級調度的對比
  

4.2、知識總結

5、行程調度

5.1、行程調度的時機

行程調度(低級調度)，就是按照某種演算法從就緒佇列中選擇一個行程為其分配處理機，

（1）需要進行行程調度與切換的情況

• 當前運行的行程主動放棄處理機

行程正常終止，運行程序中發生例外而終止，行程主動請求阻塞(如等待I/O)，

• 當前運行的行程被動放棄處理機

分給行程的時間片用完，有更緊急的事需要處理( 如I/O中斷)，有更高優先級的行程進入就緒佇列，

（2）不能進行行程調度與切換的情況

• 在處理中斷的程序中，中斷處理程序復雜，與硬體密切相關，很難做到在中斷處理程序中進行行程切換，
• 行程在作業系統內核程式臨界區中，
• 在原子操作程序中，原子操作不可中斷，要一氣呵成，(如之前講過的修改PCB中行程狀態標志，并把PCB放到相應佇列)

5.2、行程調度的方式

（1）非剝奪調度方式，又稱非搶占方式，即，只允許行程主動放棄處理機，在運行程序中即便有更緊迫的任務到達，當前行程依然會繼續使用處理機，直到該行程終止或主動要求進入阻塞態，

實作簡單，系統開銷小但是無法及時處理緊急任務，適合于早期的批處理系統

（2）剝奪調度方式，又稱搶占方式，當一個行程正在處理機上執行時，如果有一.個更重要或更緊迫的行程需要使用處理機，則立即暫停正在執行的行程，將處理機分配給更重要緊迫的那個行程，

可以優先處理更緊急的行程，也可實作讓各行程按時間片輪流執行的功能(通過時鐘中斷)，適合于分時作業系統、實時作業系統，

5.3、行程切換的時機

“狹義的行程調度”與“行程切換”的區別:
狹義的行程調度指的是從就緒佇列中選中一個要運行的行程，(這 個行程可以是剛剛被暫停執行的行程，也可能是另一個行程，后一種情況就需要行程切換)

行程切換是指一個行程讓出處理機，由另一個行程占用處理機的程序，

廣義的行程調度包含了選擇一個行程和行程切換兩個步驟，

行程切換的程序主要完成了:
1.對原來運行行程各種資料的保存
2.對新的行程各種資料的恢復
(如:程式計數器、程式狀態字、各種資料暫存器等處理機現場資訊，這些資訊一般保存在行程控制塊)

注意:行程切換是有代價的，因此如果過于頻繁的進行行程調度、切換，必然會使整個系統的效率降低，使系統大部分時間都花在了行程切換上，而真正用于執行行程的時間減少，

5.4、行程調度的演算法

• 評價指標

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-xDL4lcck-1601999200221)(C:\Users\hanxu\AppData\Roaming\Typora\typora-user-images\image-20200920163704672.png)]

①CPU利用率:指CPU“忙碌”的時間占總時間的比例，即利用率=忙碌的時間/總時間

②系統吞吐量:單位時間內完成作業的數量

對于計算機來說，希望能用盡可能少的時間處理完盡可能多的作業

系統吞吐量=總共完成了多少道作業/總共花了多少時間
Eg:某計算機系統處理完10道作業，共花費100秒，則系統吞吐量為? 10/100=0.1道/秒

③周轉時間，是指從作業被提交給系統開始，到作業完成為止的這段時間間隔，

對于計算機的用戶來說，他很關心自己的作業從提交到完成花了多少時間，

周期時間=作業在外存后備佇列上等待作業調度(高級調度)的時間+行程在就緒佇列上等待行程調度(低級調度)的時間+行程在CPU上執行的時間+行程等待I/O操作完成的時間，

后三項在一個作業的整個處理程序中，可能發生多次，

(作業)周轉時間=作業完成時間-作業提交時間

平均周轉時間 =各作業周轉時間之和/作業數

④等待時間，指行程/作業處于等待處理機狀態時間之和，等待時間越長，用戶滿意度越低，

對于行程來說，等待時間就是指行程建立后等待被服務的時間之和，在等待IO完成的期間其實行程也是在被服務的，所以不計入等待時間，

對于作業來說，不僅要考慮建立行程后的等待時間，還要加上作業在外存后備佇列中等待的時間，

一個作業總共需要被CPU服務多久，被I/O設 備服務多久一般是確定不變的，因此調度演算法其實只會影響作業/行程的等待時間，

⑤回應時間，指從用戶提交請求到首次產生回應所用的時間，

對于計算機用戶來說，會希望自己的提交的請求（比如通過鍵盤輸入了一個除錯命令）盡早地開始被系統服務、回應，

• 調度的演算法

Tips:各種調度演算法的學習思路
1.演算法思想
2.演算法規則
3.這種調度演算法是用于作業調度還是行程調度?
4.搶占式?非搶占式?
5.優點和缺點
6.是否會導致饑餓

調度演算法需要針對不同環境來討論，

5.4.1、批處理系統中的調度

a、先來先服務(FCFS, First Come First Serve)

• 演算法思想
  主要從“公平”的角度考慮(類似于我們生活中排隊買東西的例子)
• 演算法規則
  按照作業/行程到達的先后順序進行服務
• 用于作業/行程調度
  用于作業調度時，考慮的是哪個作業先到達后備佇列;用于行程調度時，考慮的是哪個行程先到達就緒佇列
• 是否可搶占?
  非搶占式的演算法
• 優缺點
  優點:公平、演算法實作簡單
  缺點:排在長作業(行程)后面的短作業需要等待很長時間，帶權周轉時間很大，對短作業來說用戶體驗不好，即，FCFS演算法對長作業有利，對短作業不利
• 是否會導致饑餓
  不會

b、短作業優先(SJF, Shortest Job First )

• 演算法思想
  追求最少的平均等待時間，最少的平均周轉時間、最少的平均帶權周轉時間
• 演算法規則
  最短的作業/行程優先得到服務(所謂“最短”，是指要求服務時間最短)
• 用于作業/行程調度
  既可用于作業調度，也可用于行程調度，用于行程調度時稱為“短行程優先(SPF, Shortest Process First)演算法”
• 是否可搶占?
  SJF和SPF是非搶占式的演算法，但是也有搶占式的版本–最短剩余時間優先演算法(SRTN, Shortest Remaining Time Next)
• 優缺點
  優點:“ 最短的”平均等待時間、平均周轉時間
  缺點:不公平，對短作業有利，對長作業不利，可能產生饑餓現象，另外，作業/行程的運行時間是由用戶提供的，并不一定真實，不一定能做到真正的短作業優先
• 是否會導致饑餓
  會，如果源源不斷地有短作業/行程到來，可能使長作業/行程長時間得不到服務，產生“饑餓”現象，如果一直得不到服務，則稱為“餓死”

c、高回應比優先(HRRN, Highest Response Ratio Next)

• 演算法思想
  要綜合考慮作業/行程的等待時間和要求服務的時間

• 演算法規則
  在每次調度時先計算各個作業/行程的回應比，選擇回應比最高的作業/行程為其服務
  

• 用于作業/行程調度
  既可用 于作業調度，也可用于行程調度

• 是否可搶占?
  非搶占式的演算法，因此只有當前運行的作業/行程主動放棄處理機時，才需要調度，才需要計算回應比

• 優缺點
  綜合考慮了等待時間和運行時間(要求服務時間)
  等待時間相同時，要求服務時間短的優先(SJF 的優點)
  要求服務時間相同時，等待時間長的優先(FCFS 的優點)
  對于長作業來說，隨著等待時間越來越久，其回應比也會越來越大，從而避免了長作業饑餓的問題

• 是否會導致饑餓
  不會

三者比較：

5.4.2、互動式系統

a、時間片輪轉調度演算法(RR)

• 演算法思想
  公平地、輪流地為各個行程服務，讓每個行程在一-定時間間隔內都可以得到回應
• 演算法規則
  按照各行程到達就緒佇列的順序，輪流讓各個行程執行一一個時間片(如100ms)，若行程未在一個時間片內執行完，則剝奪處理機，將行程重新放到就緒佇列隊尾重新排隊，
• 用于作業/行程調度
  用于行程調度(只有作業放入記憶體建立了相應的行程后，才能被分配處理機時間片)
• 是否可搶占?
  若行程未能在時間片內運行完，將被強行剝奪處理機使用權，因此時間片輪轉調度演算法屬于搶占式的演算法，由時鐘裝置發出時鐘中斷來通知CPU時間片已到
• 優缺點
  優點:公平:回應快，適用于分時作業系統:
  缺點:由于高頻率的行程切換，因此有一定開銷; 不區分任務的緊急程度，
• 是否會導致饑餓
  不會

b、優先級調度演算法

• 演算法思想
  隨著計算機的發展，特別是實時作業系統的出現，越來越多的應用場景需要根據任務的緊急程度來決定處理順序
• 演算法規則
  調度時選擇優先級最高的作業/行程
• 用于作業/行程調度
  既可用于作業調度，也可用于行程調度，甚至，還會用于在之后會學習的I/O調度中
• 是否可搶占?
  搶占式、非搶占式都有，區別在于:非搶占式只需在行程主動放棄處理機時進行調度即可，而搶占式還需在就緒佇列變化時，檢查是否會發生搶占，
• 優缺點
  優點:用優先級區分緊急程度、重要程度，適用于實時作業系統，可靈活地調整對各種作業/行程的偏好程度，
  缺點:若源源不斷地有高優先級行程到來，則可能導致饑餓
• 是否會導致饑餓
  會

c、多級反饋佇列調度演算法

• 演算法思想
  對其他調度演算法的折中權衡
• 演算法規則
  • 設定多級就緒佇列，各級佇列優先級從高到低，時間片從小到大
  • 新行程到達時先進入第1級佇列，按FCFS原則排隊等待被分配時間片，若用完時間片行程還未結束，則行程進入下一級佇列隊尾，如果此時已經是在最下級的佇列，則重新放回該佇列隊尾
  • 只有第k級佇列為空時，才會為k+1級隊頭的行程分配時間片
• 用于作業/行程調度
  用于行程調度
• 是否可搶占?
  搶占式的演算法，在k級佇列的行程運行程序中，若更上級的佇列(1~k-1級)中進入了一個新行程，則由于新行程處于優先級更高的佇列中，因此新行程會搶占處理機，原來運行的行程放回k級佇列隊尾，
• 優缺點
  對各型別行程相對公平(FCFS的優點) ;每個新到達的行程都可以很快就得到回應(RR的優點) ;短行程只用較少的時間就可完成(SPF的優點) :不必實作估計行程的運行時間(避免用戶作假) ;可靈活地調整對各類行程的偏好程度，比如CPU密集型行程、I/O密集型行程(拓展:可以將因I/O而阻塞的行程重新放回原佇列，這樣I/O型行程就可以保持較高優先級)
• 是否會導致饑餓
  會

三者比較和總結：