技術文章 » 作業系統複習知識點（第三章）

作業系統複習知識點（第三章）

2022-01-10 22:00:20

處理機排程

1.高階排程、中級排程、低階排程

  • 高階排程：根據某種演演算法，把外存上處於後備佇列中的那些作業調入記憶體。(作業排程)
  • 中級排程：為了提高記憶體利用率和系統吞吐量，使那些暫時不能執行的程序不再佔用記憶體資源，將它們調至外存等待，把程序狀態改為就緒駐外存狀態或掛起狀態。（程序排程）
  • 低階排程：儲存處理機的現場資訊，按某種演演算法先取程序，再把處理器分配給程序。

2.作業、作業步、作業流

  • 作業：包含通常的程式和資料，還配有作業說明書，系統根據該說明書對程式的執行進行控制。批次處理系統中是以作業為基本單位從外存調入記憶體的。
  • 作業步：是指每個作業執行期間都必須經過若干個相對獨立互相關聯的順序加工的步驟。
  • 作業流：是指若干個作業進入系統後依次存放在外存上形成的輸入作業流；在作業系統的控制下，逐個作業程序處理，於是形成了處理作業流。

3.JCB（作業控制塊）

  • 每當作業進入系統時，系統便為每個作業建立一個作業控制塊JCB，根據作業型別將它插入到相應的後備佇列中。
  • 作業控制塊（JCB）的內容
    • 作業號
    • 作業類別
    • 使用者名稱及使用者賬號
    • 作業狀態
    • 提交到系統的時間
    • 優先順序別（或者響應比）
    • 作業所在的外存設定
    • 資源需求
    • 執行長度
    • 已經執行時間
    • 其他資訊（收費標準，JCB佇列指標）

4.在搶佔排程方式中，搶佔的原則是什麼？

  • 時間片原則（分時系統的排程演演算法：時間片輪轉法）
  • 優先權原則（實時系統的排程演演算法：最早截止時間優先即EDF）
  • 短作業優先權原則（批次處理系統的排程演演算法：短作業優先）

5.作業排程演演算法

  • FCSF先來先服務排程演演算法

    • 作業等待時間得長短。比較有利於長作業（程序），而不利於短作業（程序）。

  • SJF短作業優先排程演演算法

    • 優點：能有效的降低作業的平均等待事件，提高系統吞吐量。
    • 缺點：對長作業不利；該演演算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業（程序）會被及時處理；由於作業（程序）的長短含主觀因素，不一定能真正做到短作業優先。

 週轉時間 = 作業完成時刻 - 作業到達時刻

 帶權週轉時間 = 週轉時間 / 服務時間

  • 高響應比優先排程演演算法

  • 高響應比優先排程演演算法主要用於作業排程，該演演算法是對FCFS排程演演算法和SJF排程演演算法的一種綜合平衡，同時考慮每個作業的等待時間和估計的執行時間。在每次進行作業排程時，先計算後備作業佇列中每個作業的響應比，從中選出響應比最高的作業投入執行。

作業到達時間服務時間
A 06
B32
C44
D41

1.先執行A作業，其餘再通過響應比判斷執行哪個；

作業到達時間服務時間開始時間結束時間週轉時間帶權週轉時間
A060661
B32
C44
D41

 2.根據響應比，執行D作業；

  • R（B） = 1 + （6 - 3）/ 2 = 2.5
  • R（C） = 1 + （6 - 4）/ 4 = 1.5
  • R（D）= 1 + （6 - 4） / 1 = 3
作業到達時間服務時間開始時間結束時間週轉時間帶權週轉時間
A060661
B32
C44
D416733

3.根據響應比，執行B作業；

  • R（B） = 1 + （7 - 3）/ 2 = 2
  • R（C） = 1 + （7 - 4）/ 4 = 0.75
作業到達時間服務時間開始時間結束時間週轉時間帶權週轉時間
A060661
B3271073.5
C44
D416733

4.執行最後C作業。

作業到達時間服務時間開始時間結束時間週轉時間帶權週轉時間
A060661
B3271073.5
C441014102.5
D416733

響應比Rp = （等待時間+要求服務時間）/ 要求服務時間 =1 +（等待時間 / 要求服務時間）

等待時間 = 上一個作業調入完成時間 - 該作業到達的時間

  • 當作業的等待時間相同時，則要求服務時間越短，其響應比越高，有利於短作業；
  • 當要求服務時間相同時，作業的響應比由其等待時間決定，等待時間越長，其響應比越高，因而它實現的是先來先服務；
  • 對於長作業，作業的響應比可以隨等待時間的增加而提高，當其等待時間足夠長時，其響應比便可升到很高，從而也可獲得處理機，克服了飢餓狀態，兼顧了長作業。

6.死鎖

  • 死鎖的概念

    • 死鎖是指多個程序因競爭資源而造成的一種僵局，若無外力作用，這些程序都將永遠不能再向前推進。死鎖一定是「迴圈等待對方手裡的資源」導致的，因此如果有死鎖現象，那至少有兩個或兩個以上的程序同時發生死鎖。另外，發生死鎖的程序一定處於阻塞態

  • 死鎖的必要條件

    • 互斥條件：只有對必須互斥使用的資源的爭搶才會導致死鎖（如哲學家的筷子、印表機裝置）。像記憶體、揚聲器這樣可以同時讓多個程序使用的資源是不會導致死鎖的（因為程序不用阻塞等待這種資源）。
    • 不剝奪條件：程序所獲得的資源在未使用完之前，不能由其他程序強制奪走，只能主動釋放。
    • 請求和保持條件：程序已經保持了至少一個資源但又提出了新的資源請求，而該資源又被其他程序佔有，此時請求程序被阻塞，但又對自己已有的資源保持不放。
    • 迴圈等待條件：存在一種程序資源的迴圈等待鏈，鏈中的每一個程序已獲得的資源同時被下一個程序所請求。發生死鎖時一定有迴圈等待，但是發生迴圈等待時不一定。

  • 產生死鎖的原因

    • 對臨界資源的競爭：各程序對不可剝奪的資源的競爭可能引起死鎖。
    • 程序推進順序非法：請求和釋放資源的順序不當，同樣會導致死鎖。例如,並行執行的程序P1、P2兩者分別申請並佔有了資源R1、R2，之後程序P1又緊接著申請資源R2，而程序P2又申請資源R1，兩者會因為申請的資源被對方佔有而阻塞，從而發生了死鎖。

  • 解決死鎖問題的方法

    • 預防死鎖（最容易實現）
      • 摒棄「請求和保持」條件
      • 摒棄「不剝奪」條件
      • 摒棄「環路等待」條件
    • 避免死鎖（銀行家演演算法）
    • 檢測和解除死鎖

7.銀行家演演算法

  • 安全序列：是指一個程序式列{P1，…，Pn}是安全的，即對於每一個程序Pi(1≤i≤n），它以後尚需要的資源量不超過系統當前剩餘資源量與所有程序Pj (j < i )當前佔有資源量之和。
  • 安全狀態：如果存在一個由系統中所有程序構成的安全序列P1，…，Pn，則系統處於安全狀態。安全狀態一定是沒有死鎖發生。
  • 不安全狀態：如果分配了資源以後，系統找不出任何一個安全序列，就進入了不安全狀態。這就意味著可能所有程序都無法順利進行下去。如果系統處於不安全狀態，不一定發生死鎖，但發生死鎖一定是在不安全狀態

資料結構：

  • 可利用資源向量Available：是個含有m個元素的陣列，其中的每一個元素代表一類可利用的資源數目。如果Available[j]=K，則表示系統中現有Rj類資源K個。
  • 最大需求矩陣Max：這是一個n×m的矩陣，它定義了系統中n個程序中的每一個程序對m類資源的最大需求。如果Max[i,j]=K，則表示程序i需要Rj類資源的最大數目為K。
  • 分配矩陣Allocation：這也是一個n×m的矩陣，它定義了系統中每一類資源當前已分配給每一程序的資源數。如果Allocation[i,j]=K，則表示程序i當前已分得Rj類資源的數目為K。
  • 需求矩陣Need：這也是一個n×m的矩陣，用以表示每一個程序尚需的各類資源數。如果Need[i,j]=K，則表示程序i還需要Rj類資源K個，方能完成其任務。

下面是三者之間的關係:

Need[i,j]=Max[i,j]-Allocation[i,j]

(尚需資源數=最大資源需求數-已分配資源數)

銀行家演演算法步驟:

請求向量Request(i)：是程序Pi的請求向量，如果Request(i)[j]=k，表示程序Pi需要K個R(j)型別的資源。當Pi發現資源請求後系統將進行下列步驟:

  1. 如果Request(i)[j] <= Need[i,j],即請求量未超過尚需量，繼續執行步驟2,否則認為出錯，因為它所請求的資源數已超過它所宣佈的最大值。
  2. 如果Request(i)[j] <= Available[i,j]，即請求量未超過可分配資源量，繼續執行步驟3，否則，表示尚無足夠資源，Pi需等待。
  3. 系統試探著把資源分配給程序Pi，並需要修改下面資料結構中的數值；                           

Available[j] = Available[j] - Request(i)[j];（可利用資源數減少）

Allocation[i,j] = Allocation[i,j] + Request(i)[j];（已分配資源數增加）

Need[i,j] = Need[i,j] - Request(i)[j];（尚需資源數減少）

      4.系統執行安全性演演算法，檢查此次資源分配後，系統是否處於安全狀態。若安全，才正式將資源分配給程序Pi，已完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓程序Pi等待。

安全性演演算法步驟：

（1）設定兩個向量：

  • 工作向量Work：表示系統可供程序繼續執行所需的各類資源數目，它有m個元素，開始時，Work=Available;
  • Finish:表示系統是否有足夠的資源分配給程序，使之執行完成。開始時，Finish[i] = false；當有足夠資源分配給程序時，再令Finish[i] = true。

（2）從程序集合中找到一個能滿足下述條件的程序：

              1.Finish[i] = false

              2.Need[i,j] <= Work[j]（程序所需資源量未超過可分配資源量）;

              3.若都滿足，執行步驟（3），否則執行步驟（4）

（3）當程序Pi獲得資源後，可順利執行至完成，並釋放分配給它的資源，故應執行：

            Work[j] = Work[j] + Allocation[i,j]；

Finish[i] = true；

go to step （2）；

（4）所有程序的Finish[i] = true，表示系統處於安全狀態；否則，系統處於不安全狀態。

                           

舉例：