第三章（上）處理機調度與死鎖知識梳理

一、 處理機調度的基本概念與層次

處理機調度是操作系統的核心功能之一，其核心目標是在多道程序環境下，合理地分配和回收處理機資源，以提高系統效率和資源利用率，滿足不同用戶和任務的需求。

1. 調度的三個層次：

• 高級調度（作業調度）：
• 對象： 作業（Job）。

• 功能： 決定將外存上處于后備隊列的哪些作業調入內存，為其創建進程、分配必要的資源，并放入就緒隊列。

• 發生頻率： 低，通常幾分鐘一次。

• 中級調度（內存調度）：
• 對象： 進程。

• 功能： 將暫時不能運行的進程（如因等待I/O）調至外存等待（掛起狀態），當內存有富余或進程具備運行條件時，再重新調入內存。目的是提高內存利用率和系統吞吐量。

• 發生頻率： 中等。

• 低級調度（進程調度）：
• 對象： 進程（或內核級線程）。

• 功能： 按照某種算法，從就緒隊列中選取一個進程，將處理機分配給它。這是操作系統中最基本、最頻繁的調度。

• 發生頻率： 很高，幾十毫秒一次。

二、 進程調度

1. 進程調度的任務與機制：
任務： 保存當前進程的現場信息，按算法選擇新進程，恢復新進程的現場并使其運行。
機制： 包括排隊器（組織就緒隊列）、分派器（切換上下文）、上下文切換器。

2. 調度方式：
非搶占式（非剝奪式）： 一旦把處理機分配給某進程，該進程會一直運行直至完成或發生阻塞事件主動讓出。實現簡單，但無法處理緊急任務。
搶占式（剝奪式）： 允許調度程序根據某種原則（如優先級、時間片）暫停正在執行的進程，將處理機分配給更重要的進程。能提供更好的響應性和公平性，是現代系統的主流方式。

3. 進程切換與上下文切換：
進程切換必然發生上下文切換，但上下文切換不一定是由進程切換引起（也可能是同一進程內的線程切換）。

三、 調度算法（本章重點）

調度算法的評價指標：CPU利用率、系統吞吐量、周轉時間、等待時間、響應時間。

1. 先來先服務（FCFS）：
規則： 按作業/進程到達的先后順序進行服務。
特點： 算法簡單，公平。但不利于短作業，平均等待時間較長。

2. 短作業優先（SJF）/短進程優先（SPF）：
規則： 對預計運行時間最短的作業/進程優先服務。
特點： 能獲得最小的平均等待/周轉時間。但可能導致長作業“饑餓”，且運行時間難以準確預估。

3. 高響應比優先（HRRN）：
規則： 在每次調度時，計算每個就緒作業的響應比 R = (等待時間 + 要求服務時間) / 要求服務時間，選擇R最高的作業。
特點： 是FCFS和SJF的折中，既考慮了等待時間（防止饑餓），又考慮了運行時間。

4. 時間片輪轉（RR）：
規則： 將所有就緒進程按FCFS原則排成一個隊列，每次調度將CPU分配給隊首進程，但僅執行一個時間片。時間片用完后，由計時器發出時鐘中斷，調度程序將該進程送到就緒隊列末尾，并讓新的隊首進程執行。
特點： 專為分時系統設計，公平、響應快。時間片大小是關鍵：太大退化為FCFS；太小則上下文切換開銷過大。

5. 優先級調度算法（PSA）：
規則： 為每個進程賦予一個優先級，調度時選擇優先級最高的進程。優先級可以靜態設定或動態調整（如根據等待時間增長而提高）。
特點： 可用于實時系統。可能導致低優先級進程饑餓。

6. 多級隊列調度算法（MQ）：
* 規則： 將就緒隊列劃分為多個獨立隊列，每個隊列有自己的調度算法（如系統進程隊列用RR，交互進程隊列用FCFS）。隊列之間通常采用固定優先級或時間片劃分的方式進行調度。

7. 多級反饋隊列調度算法（MFQ）：
規則： 是MQ與時間片輪轉的結合與進化。設置多個優先級不同的隊列，新進程進入最高優先級隊列。每個隊列的時間片大小不同，優先級越高的隊列時間片越小。進程在當前隊列的一個時間片內未完成，則被降級到下一級隊列。只有高優先級隊列為空時，才調度低優先級隊列的進程。
特點： 是公認的綜合性較好的一種調度算法，能較好地滿足各種類型用戶的需求：短作業優先完成、長作業不會長期得不到服務、I/O密集型進程能獲得較高響應優先級。

四、 死鎖概述

1. 死鎖的定義：
在多道程序系統中，由于競爭資源或進程間通信不當，導致一組進程中的每一個進程都在無限期地等待被該組中另一個進程所占有的資源，從而導致所有進程都無法向前推進的現象。

2. 產生死鎖的必要條件（四個，必須同時成立）：
互斥條件： 資源在一段時間內只能被一個進程使用。
請求和保持條件（占有并等待）： 進程在持有至少一個資源的又請求新的資源，而該資源被其他進程占有，此時請求進程被阻塞，但對自己已獲得的資源保持不放。
不可剝奪條件（非搶占）： 進程已獲得的資源在未使用完之前，不能被其他進程強行奪走，只能由該進程主動釋放。
循環等待條件： 存在一個進程-資源的環形等待鏈。

3. 處理死鎖的基本方法：
預防死鎖： 破壞死鎖四個必要條件中的一個或多個（靜態策略）。
破壞“請求和保持”：一次性申請所有資源（資源預分配）。

• 破壞“不可剝奪”：允許剝奪資源。

• 破壞“循環等待”：對資源類型進行線性排序，要求進程按序申請。

• 避免死鎖： 在資源動態分配過程中，用某種方法（如銀行家算法）防止系統進入不安全狀態（動態策略）。
• 檢測與解除死鎖： 允許死鎖發生，通過檢測機構及時發現，并采取撤銷進程或剝奪資源等措施解除死鎖。
• 忽略死鎖： 如大多數操作系統對死鎖問題采取不理睬的策略，因為死鎖并非頻繁發生，且預防和避免的代價較高。

---

本章（下）預告： 將深入講解銀行家算法的原理與示例、死鎖的檢測與解除的具體方法，并結合實例進行綜合分析。

---

腦圖關鍵詞索引：
調度層次（高/中/低） -> 進程調度（任務/方式/切換） -> 調度算法（FCFS, SJF, HRRN, RR, PSA, MQ, MFQ） -> 死鎖（定義，四必要條件，處理策略：預防/避免/檢測解除/忽略）。