第 2 章 進程管理

【考綱內容】

1.進程與線程：
(1) 進程 / 線程的基本概念；
(2) 進程 / 線程的狀態與轉換；
(3) 線程的實現：內核支持的線程；線程庫支持的線程；
(4) 進程與線程的組織與控制；
(5) 進程間通信：共享內存；消息傳遞；管道；信號

2.CPU 調度與上下文切換：
(1) 調度的基本概念；
(2) 調度的目標；
(3) 調度的實現：調度器 / 調度程序（scheduler）；調度的時機與調度方式（搶占式 / 非搶占式）；閑逛進程；內核級線程與用戶級線程調度；
(4) CPU 調度算法；
(5) 多處理機調度；
(6) 上下文及其切換機制

3.同步與互斥：
(1) 同步與互斥的基本概念；
(2) 同步與互斥的基本方法：軟件實現方法；硬件實現方法；
(3) 鎖；
(4) 信號量；
(5) 條件變量；
(6) 經典同步問題：生產者 - 消費者問題；讀者 - 寫者問題；哲學家進餐問題

4.死鎖：
(1) 死鎖的概念；
(2) 死鎖預防；
(3) 死鎖避免；
(4) 死鎖檢測和解除

【考情統計】

年份	單選題數	綜合題數	總分值	考點
2009	1	1	9	典型調度算法、死鎖原因、P/V 操作
2010	4	0	8	進程控制、典型調度算法、信號量機制、饑餓問題
2011	4	1	16	典型調度算法、線程概念和多線程模型、銀行家算法、同步機制、P/V 操作
2012	4	0	8	進程概念與特征、線程概念和多線程模型、調度基本概念、進程概念、線程概念、線程實現、線程組織、銀行家算法
2013	2	1	11	典型調度算法、銀行家算法、P/V 操作
2014	4	1	16	進程狀態與轉移、典型調度算法、進程通信、死鎖、P/V 操作
2015	2	1	13	進程狀態與轉換、進程控制、死鎖避免、死鎖檢測、P/V 操作
2016	5	1	16	調度的基本概念、典型調度算法、死鎖原因、硬件同步、互斥機制、管程機制、饑餓問題
2017	2	1	12	調度的方式、典型調度算法、調度算法、P/V 操作
2018	6	0	12	進程的狀態與轉移、調度的方式、典型調度算法、狀態轉換、互斥機制、銀行家算法、管程機制、同步機制
2019	4	1	16	線程概念和多線程模型、典型調度算法、死鎖原因、銀行家算法、死鎖預防、死鎖解除、P/V 操作
2020	4	1	15	進程概念與特征、調度算法的目標、典型調度算法、銀行家算法、互斥機制、臨界資源、P/V 操作
2021	4	1	15	進程狀態、進程組織、典型調度算法、調度的方式、調度時機、互斥機制、臨界資源
2022	3	1	14	進程組織、典型調度算法、銀行家算法、進程狀態
2023	2	2	13	進程狀態、典型調度算法、硬件同步
2024	3	1	14	進程終止、進程切換、線程、P/V 操作綜合題

【考點解讀】

????????本章是選擇題和綜合題考查的重點章節。進程與線程一節中，歷年考查的形式為概念相關的選擇題。一般考查 1 道選擇題，與其他章節內容結合考查時可能命制 2 道選擇題。處理器調度與上下文切換一節中，著重考查調度相關的概念選擇題和典型調度算法相關的計算選擇題，一般考查 1 道選擇題。2016 年的 408 試卷比較特殊，針對調度的概念考查了一次綜合題，請考生注意。
????????進程同步是十分重要的一節，408 統考幾乎每年都會考查 1 道 7 分左右的綜合應用題，此外還會以客觀題的形式考查臨界資源與臨界區、同步與互斥等基本概念。如果考生充分掌握信號量機制的應用，得分并不困難。死鎖一節中，平均每年考查 1 道選擇題，其中對銀行家算法的考查尤為側重，值得考生重點關注。另外，進程間信號通信機制、多處理機調度是 2025 考研 408 大綱中新增考點。

【復習建議】

關于本章考生應：

1.理解進程的概念與特征、線程的概念、多線程模型。

2.重點掌握進程的狀態轉移，進程的控制相關內容。

3.了解進程的組織，其中 PCB 相關內容需要理解。

4.理解線程和進程之間的相同點和不同點。

5.了解進程通信的四種方式，尤其注意管道、共享內存和消息傳遞機制。

6.了解調度的機制、時機、方式和實現，這有助于考生對調度有一個全面的了解。

7.重點掌握調度算法的目標。

8.重點掌握典型調度算法。本章列舉的七種調度算法中，除了多級隊列（注意不是多級反饋隊列）以外，都應該熟練掌握。

9.甘特圖是分析調度的工具，建議熟練運用于涉及調度的計算中。

10.理解進程同步、臨界區、臨界資源的基本概念。

11.重點掌握同步機制的四個設計準則，它們為后續知識作了重要鋪墊。

12.了解實現臨界區互斥的基本方法，重點關注其中的 Peterson 算法。

13.重點掌握信號量的類型及其應用，可以應用信號量實現進程的同步、互斥和前驅關系。

14.重點掌握生產者 - 消費者問題、哲學家進餐問題、讀者 - 寫者問題等經典同步問題，力求熟練使用 P/V 操作解決復雜的多進程同步問題。

15.了解管程的定義、組成和基本特性。

16.理解死鎖的定義和原因，重點掌握死鎖產生的四個必要條件。

17.了解資源問題和資源分配圖。

18.理解死鎖預防、死鎖檢測和解除的概念和方法。

19.重點掌握死鎖避免的概念和方法，重點關注其中的安全狀態和銀行家算法。

2.1 進程與線程

????????本節的目標是對進程的概念、組織、控制、通信問題以及線程的概念、線程實現方式有一個全面的認識。進程和線程是操作系統的基本概念，也是考試重點考查的內容。盡管本節考查的知識范圍廣，但難度適中，對于進程和線程的理解到位后，很多知識點記憶負擔不大。考生在學習本節內容時，可以先嘗試對進程和線程建立起一個總體的認識，通過本節的各個例子和提示加深理解，嘗試回答下列問題（答案見本章末總結）。
????????(1) 什么是進程，有什么特點？是否可以舉出一個實際的例子？
????????(2) 一個進程由哪些部分組成，為什么要提出進程這一概念？
????????當考生可以回答上述問題時，說明已經對本節知識點有了一定的理解，接下來需要針對各個知識點進行系統性學習，當能回答以下問題時，說明已經系統地掌握了本節（題目可以在各個小節中找到答案）。
????????(1) 進程在其生命周期中，有哪些狀態？這些狀態間哪些狀態是可以轉移的，什么場合下可以轉移？
????????(2) 進程控制有哪些原語？以進程創建為例，能否說出進程創建原語發生在哪些場合，具體執行過程是什么？
????????(3) PCB 中有哪些內容，為什么需要這些內容？
????????(4) 進程通信有哪些方式？

2.1.1 進程的概念和特征

1. 進程的概念

????????自誕生以來，操作系統就需要運行各種各樣的程序。為了管理這些程序的運行，操作系統提出了進程（Process）這一概念。進程（Process）是計算機中一個執行的程序實例，每個進程對應一個運行中的程序。是操作系統資源分配和調度的獨立單位，是操作系統中最基礎與最重要的概念之一。有了進程這一概念，應用程序在運行時仿佛獨占了 CPU，而不用考慮何時需要將 CPU 讓給其他程序；進程的管理等任務則交給操作系統。
????????一個進程包括了以下內容：程序段（Program Code）、數據段和進程控制塊。其中，程序段和數據段是一組指令、數據和對其組織描述的總和；操作系統通過進程控制塊（參見本節進程控制塊）描述程序的 “狀態”。
????????程序段與數據段存儲在磁盤上，是靜態的；進程是指將這些程序與數據從磁盤加載到內存后的執行過程，是動態的，多個進程可以對應于同一段程序代碼。
????????【舉例】“int a = 1;” 包含了指令與數據，而我們寫程序時有序地將代碼組織起來，就是在對其組織進行描述。Windows 操作系統中一個 exe 文件就是一個程序，執行該程序就會創建一個對應進程，執行多次該文件會創建出多個對應進程，所以進程是動態的，是一次執行過程。
這里列舉更多角度下對進程的定義：
????????(1) 進程是程序的一次執行過程 。
????????(2) 進程是一個程序及其數據在處理器上順序執行時所發生的活動 。
????????(3) 進程是具有獨立功能的程序在一個數據集合上運行的過程，它是系統進行資源分配和調度的獨立單位 。
????????(4) 進程是正在計算機上執行的程序實例 。
????????(5) 進程是能分配給處理器并由處理器執行的實體 。
????????(6) 進程是由一組執行的指令、一個當前狀態和一組相關的系統資源表征的活動單元 。
????????(7) 進程由程序段、數據段、進程控制塊三部分組成。
????????【舉例】在現實世界中，我們準備好了各種的食材（數據）并編寫了一個料理配方（每個步驟的操作 + 將操作合理地組織），這就對應了一個程序。按照料理配方開始料理食材的過程，就對應了一個進程。顯然，我們可以使用一個料理配方對兩批食材同時處理，這就相當于開啟了兩個進程；在料理一批食材的過程中，安排多個人同時進行料理，這就相當于開啟了多個線程。

2. 進程控制塊

????????進程控制塊（Process Control Block，PCB），是操作系統為每個進程配備的一個記錄型數據結構。PCB 上包含了操作系統管理進程所需要的信息，用于管理操作系統中存在的所有進程，是進程的組成部分之一。進程與線程的組織一節會詳細介紹 PCB 的主要內容、功能。
????????【提示】考生第一次接觸到 PCB 這個概念時，可以類比學生檔案。一個班級（對應操作系統）會有一份記錄所有學生信息的表格（對應 PCB），每個學生有一個獨一無二的學號（對應進程標識符）以及其他重要信息，如是否報到（對應進程狀態）等。操作系統用 PCB 來記錄和管理所有進程，就像班級管理者利用學生檔案來記錄和管理每一位學生。

3. 進程的特點

????????與程序相比，進程主要有以下 4 個特點。理解進程的并發性、獨立性和異步性時，可以和批處理系統中作業的順序執行進行對比學習。

(1) 動態性

????????進程的實質是程序在多道系統中的一次執行（Execution），從創建到消亡，是動態的、具有生命周期的。與此相對，程序只是一串二進制位，靜態存儲于硬盤等介質之中，并不具有動態性。

(2) 并發性

????????引入進程概念后，操作系統中可以有多個進程并發執行。當多個進程并發執行時，會有以下 3 個特性：

(a) 間斷性

????????并發的進程會有間斷運行的特點。當多個進程協同完成同一任務時，需要進行同步等操作，進而導致進程的暫停。例如，兩個進程?Pa?、Pb??協作處理一組數據。Pa??需要對?Pb??處理后的數據進行進一步處理，那么?Pa??在得到?Pb??數據前，會陷入阻塞態。Pa??進程的執行過程可以描述為：執行 —— 阻塞 —— 就緒 —— 執行。

(b) 失去封閉性

????????當系統中存在多個進程并發執行時，這些并發進程將會共享系統中的各類資源。任意進程都可能改變某個資源的狀態，從而影響到其他進程。失去封閉性意味著進程的執行結果與執行速度有關，使得進程的執行有不可再現性。失去封閉性導致了不可再現性。

(c) 不可再現性

????????并發執行的進程，在相同的初始環境和條件下，可能得到不同的結果。這是因為進程失去了封閉性。例如，進程?Pa??和?Pb??共享一個整數型共享變量 M，Pb??的工作是對 M 進行三次加一操作，Pa??的工作是讀出 M 的值，則?Pb??進程運行的快慢會直接導致?Pa??讀出的結果不同。
????????【提示】重溫并發（Concurrent）和并行（Parallel）兩個概念。并發是多個進程在同一時間段內運行，在同一時刻僅有一個進程處于執行態；并行則是同一時刻多個進程處于執行態。在單處理器多道程序系統中，進程可以并發執行；在多處理器系統中，進程不但可以并發執行，還能并行執行。

(3) 獨立性

????????進程是操作系統調度和資源分配的最小單位，即一個進程能夠獨立運行。各個進程獲得的資源獨立于其他進程。

(4) 異步性

????????因為異步性，進程的執行、暫停等變得不可預知，進程以不可預知的狀態向前推進。
????????【提示】進程的并發性導致了進程的異步性。通過使用多種同步手段（參見本章同步與互斥），可以保證在異步性的前提下得到確定（可再現）的結果。

2.1.2 進程的狀態與轉移

1. 進程的五種狀態

????????由于進程的并發特征，進程在操作系統中呈現出間斷運行的規律，因此進程在其生命周期中會經歷不同的狀態。408 考試大綱中要求掌握進程的五種狀態：創建狀態、就緒狀態、執行狀態、阻塞狀態、終止狀態，如圖 2.1 所示。其中，就緒狀態、執行狀態、阻塞狀態三個狀態稱為基本狀態，因為在一個進程的生命周期中，這三種基本狀態可以多次切換，而創建狀態和終止狀態在整個周期中只能有一次。所以在討論進程的狀態轉移問題時，常常用三狀態模型一詞對其描述。簡潔起見，后文使用創建態、就緒態、執行態、阻塞態、終止態指代上述五種狀態。

(1) 創建（New）態

????????當進程第一次被創建時所處的狀態。在此狀態下，進程等待著由此狀態轉換為 “就緒態”。操作系統決定進程由創建態轉換為就緒態時，一般會考慮系統資源的占用情況。若當前系統資源緊張，系統會推遲處于創建態的進程轉換為就緒態。

(2) 就緒（Ready）態

????????當一個進程獲得了其他所有資源，等待處理器的分配時，其狀態為就緒態。在此狀態下，進程排隊等待系統為其分配處理器資源。就緒態是很常見的狀態，處理器作為 “珍貴” 的資源，很難同時分配給所有就緒態的進程。
????????【提示】盡管計算機可以有多個處理器，但是依然難以滿足所有進程對處理器資源的請求。在一個單處理器的計算機中，任意時刻最多只能有一個進程處于執行態，其他進程只能處于其他狀態。由于處于就緒態的進程很多，這些進程一般被放在就緒隊列中等待調度。后續的處理器調度章節中，會詳細討論將處理器分配給進程的各種調度算法。

(3) 執行（Running）態

????????當一個進程被分配處理器并開始執行時，就進入了執行態。進程中的程序代碼得以在處理器上運行。
????????【提示】內核態下，進程能同時訪問內核和用戶地址、不受限制地訪問硬件，執行特權指令；用戶態下，進程不能訪問內核的指令和數據。這種模式的設計保證了安全性。

(4) 阻塞（Block）態

????????阻塞態是指進程在執行過程中因為發生某些事件而導致無法繼續執行的狀態。將進程轉換為阻塞態是因為：操作系統不希望進程因為等待未到來的數據或條件而導致處理器的空閑，系統效率下降。
????????【提示】導致進程進入阻塞態的事件很多，可能是進程發生了 I/O 操作，等待關鍵數據從磁盤讀入內存；可能是進程申請訪問臨界資源但該臨界資源被其他進程占有（詳見本章進程同步一節）。

(5) 終止（Terminated）態

????????當進程結束時，就會進入終止態。進入終止態的原因可能是進程正常地結束，也可能是被用戶強制結束（例如 Linux 中向進程發送 KILL 信號，或 Windows 下在任務管理器中結束進程）。該狀態下，操作系統開始回收該進程占有的資源。
????????【拓展】① 終止態中有一個術語：僵尸進程（Zombie Process）。用來描述那些已經處于終止態但卻未被從系統進程表中刪除的進程。Unix 系統中，有父進程的子進程可能會發生這種情況。僵尸進程會占用進程號，對系統的危害是：可能導致系統中沒有可用的進程號而無法產生新進程。② 父進程已經結束運行，但它的子進程還在運行，將這些子進程稱為孤兒進程。孤兒進程會被進程號為 1 的 init 進程所收養，并由 init 進程完成其狀態收集等善后工作。孤兒進程對系統沒有危害。
進程的五種狀態特點對比如表 2.1 所示。

2. 進程的狀態轉換

進程可能出現的狀態轉換及對應的原因如表 2.2 所示。表 2.2 中進程狀態轉換說明如下：
(1)?創建態→就緒態：進程創建成功后，首先會被設置為就緒態，插入就緒隊列中。
(2)?就緒態→執行態：處于就緒態的進程被調度后，轉換為執行態并分配處理器，運行。
(3)?執行態→就緒態：處于執行態的進程在其運行過程中，由于分配給它的處理器時間片用完而讓出處處理器，變為就緒態。
????????【提示】還有很多情況會導致這種狀態轉換。在搶占式操作系統中，當有優先級更高的進程變為就緒態時，當前正在使用處理器的進程會讓出處處理器并由執行態變為就緒態。
(4)?執行態→阻塞態：當處于執行態進程請求某資源且必須等待時，會（主動）轉換為阻塞態。
(5)?阻塞態→就緒態：當處于阻塞態的進程得到之前請求的全部資源后，會被喚醒（被動）并轉換為就緒態。
(6)?執行態→終止態：當處于執行態的進程運行完畢、發生錯誤、被用戶或操作系統強制終止時，會轉換為終止態。
????????【提示】阻塞態無法直接轉換為執行態，這取決于調度算法的設計。調度算法調度的對象就是就緒隊列中的進程，故一個進程結束阻塞態后，會先轉換為就緒態。

2.1.3 進程組織

????????進程是操作系統資源分配的最小單位，在未引入線程概念的操作系統中，同樣是調度的最小單位。一個進程包含了代碼段、數據段以及進程控制塊 PCB。

1. 進程控制塊 PCB

① PCB 的功能概述

PCB 主要有以下五個功能。
????????(1)?作為獨立運行基本單位的標志：當一個程序（含數據）配置了 PCB 后，就表示該程序能夠在支持多道程序的系統上獨立運行。
????????(2)?實現進程的間斷運行：在多道程序環境下，進程的運行是斷斷續續的。當一個進程由執行態轉換為其他狀態時，必須要保留該進程運行時的處理器現場信息，用于之后的處理器現場恢復。如果沒有 PCB 來保存進程停止運行時的現場信息，那么該進程便失去了間斷運行的能力。
????????(3)?提供進程管理的重要信息：例如，當調度程序希望某個進程運行時，會通過 PCB 中的對應指針，找到該進程存儲在內 / 外存上的程序和數據。PCB 中還會記錄進程打開文件、擁有資源等多種信息，用以實現進程管理的多種功能。
????????(4)?提供進程調度所需要的信息：PCB 上存儲了進程的狀態，用于幫助調度程序合理地完成調度。有些調度算法還需獲知進程的等待時間等信息，這些信息往往也存儲于 PCB 中。
????????(5)?實現與其他進程的同步與通信：操作系統為實現進程間的同步與通信，在 PCB 中也設置了相應的數據結構。例如，采用信號量機制實現進程同步時，信號量就是位于 PCB 中。

② PCB 中的內容

不同的操作系統內核對于 PCB 這一數據結構的實現不盡相同，PCB 中內容如表 2.3 所示，總體分為四類：
????????(1)?標識符：標識符是唯一標識，以數字或數字加字母的形式存儲在 PCB 中。Linux 中，每個進程都有一個稱為 PID（Process ID）的進程標識符。

????????(2)?處理器狀態信息：處理器狀態信息又稱為處理器上下文，記錄進程在執行態下關鍵寄存器的信息，用于進程切換后恢復處理器上的重要信息。涉及的寄存器主要有：①通用寄存器；②程序計數器 (Program Counter, PC)；③程序狀態字 (Program State Word, PSW)；④用戶棧指針。
????????【提示】PCB 中存儲的寄存器數量和種類都不是固定的，取決于處理器的設計。PCB 存儲的寄存器信息用于上下文切換，故 PCB 也被稱為切換幀 (Switch Frame)，就好像在進程停止運行前對處理器上的各種重要信息做了一個 “快照”，當操作系統想要重新讓暫停的進程繼續運行時，只需要把之前保存的信息恢復到處理器即可。
????????(3)?處理器調度信息：該類信息的存儲取決于操作系統使用何種調度方法來將處理器分配給進程，該類信息一般包括：
(a)?進程調度狀態：記錄執行態、就緒態、阻塞態等。
(b)?進程調度優先級：在多個進程就緒時，用于決定哪個進程先獲得處理器資源。
(c)?調度的相關信息：這取決于調度算法。例如進程已使用的處理器時間、進程等待處理器的時間等，這些信息用于實現操作系統的調度算法。
(d)?事件：指進程由執行態轉換為阻塞態的原因。記錄進程的阻塞原因，可以幫助操作系統更好地設計各個進程的優先級。
????????(4)?進程控制信息：用于進程控制所必須的信息，包括：
(a)?代碼段和數據段的地址：在 PCB 中通過指針的方式標明其在內存或外存中的位置。
(b)?進程同步和通信機制：用來實現進程同步的信號量、消息隊列指針等。
(c)?資源清單：記錄操作系統分配給該進程的全部資源，用于資源分配和回收等。
(d)?鏈接指針：PCB 所在隊列中下一個進程的 PCB 首地址。操作系統為了能對 PCB 加以有效管理，一般按照進程所處的狀態將各 PCB 存儲于不同的隊列（如就緒隊列、若干阻塞隊列）中，這些隊列往往以鏈表的方式實現，這也是 PCB 中存儲下一個 PCB 首地址的原因。

2.1.4 進程控制

????????本小節我們討論操作系統如何管理進程，包括創建和結束進程、轉換進程等。計算機在進程的控制方面，往往使用原語 (Primitive) 完成。原語，也有教材稱作原子操作 (Atomic Operation)，是指由若干條指令組成用于完成某個行為的過程。原語是不可中斷的，即一個原語中的指令要么全部被執行，要么全部不執行。在進程同步一章中，還會學習 P/V 原語。原語保證了使用者能夠得到確定的結果。
????????【提示】請考生思考兩個問題。第一，為什么需要把多個指令設計成一個原語，例如 GetAndSet 指令能不能由 get 指令加上 set 指令代替？假設一個設備一次只能由一個進程使用，操作系統使用 flag 變量標記是否有進程使用該設備，0 代表空閑，1 代表忙碌。一個進程使用該設備需要進行兩步操作：①獲得 flag 值，如果 flag==0 則進行下一步，否則等待；②將 flag 值置為 1 并使用該設備。此時?PA?，PB??均想要使用該設備，如果上述兩個步驟不是原語操作，則可能發生這樣的執行序列：PA??成功執行①；PB??成功執行①；PA??成功執行②并開始使用設備；PB??成功執行②并開始使用設備。這樣就發生了錯誤，因為兩個進程都認為自己可以使用設備。如果上述兩個步驟是原語操作，就不會出現這種錯誤。
????????第二，為什么在進程控制的過程中要使用原語？因為進程創建、進程喚醒等一系列控制操作均包含了多個步驟，要確保這些步驟全部進行或全部不進行才能得到正確的結果。假設需要進行進程喚醒操作，該操作至少分為兩個步驟：①將待喚醒進程的狀態設置為就緒態；②將該進程放入就緒隊列中。倘若①和②不是原語操作，在執行完①后，發生中斷，則此時一個就緒態的進程卻被放在了阻塞隊列中，這樣就發生了錯誤。

1. 進程的創建

① 進程創建的場合

進程創建的場合主要有以下四類：
(1)?用戶登錄時。
(2)?高級調度發生時：即作業由外存等待隊列被調度到內存中，進行初始化的場合。
(3)?系統響應用戶程序提出的請求時：此時操作系統會創建對應的服務進程。情況 1、2、3 均是操作系統內核為用戶創建進程。
(4)?現有進程創建新進程時：用戶進程可以通過創建新進程來提高程序并發度。例如用戶希望同時從鍵盤接受輸入、處理數據、將數據轉為統計圖顯示在屏幕上，就可以在數據處理進程之外新建鍵盤輸入進程和統計圖展示進程。

② 進程創建原語的執行過程

(1) 為在創建中的新進程分配一個進程標識符（PID），作為進程的唯一標識；為進程分配空白 PCB，用于記錄進程的各類資源與信息。
(2) 為該新進程分配所需資源。包括各類的物理資源和邏輯資源，如內存、文件、I/O 設備和處理器時間等。
(3) 初始化 PCB 上的內容。包括進程標識符、父進程標識符、處理器狀態信息和處理器控制信息。
(4) 若上述過程順利，將該新進程狀態設置為就緒態，放入就緒隊列，等待調度；若不順利，分配資源不足時，則創建該新進程的父進程置為阻塞態，新進程仍處于創建狀態。
【提示】各種操作系統在進程創建原語的設計上不盡相同，以 Linux 為例，除了 PID 為 0 的進程以外，其余的進程都是由 PID 為 0 的進程創建而來的，而這個 “0” 進程是內核進程，相比于其他進程的數據結構都是動態分配的，它的數據結構是靜態的。Linux 提供了 fork、vfork 和 clone 三種函數用于進程創建，這里簡單了解即可。

2. 進程的終止

進程是一個動態的執行過程，這意味著一個進程必然會迎來它的結束。

① 進程終止的場合

(1)?進程運行完畢，正常退出。
【舉例】Linux 系統中的 exit 系統調用，就是用于向操作系統匯報當前進程的工作已經完成，可以終止并回收資源。C 語言中，main 函數執行 return 0 后也會運行完畢，正常退出。
(2)?進程運行中發生出現無法恢復的異常（如整數除以零、訪問越界等）而退出。
(3)?被其他進程或操作系統殺死。
【舉例】Linux 系統中，得知其他進程的 PID 后，就可以使用 kill 系統調用可以向這一進程發送信號來強制結束對應的進程。

② 終止原語的執行過程

(1) 根據進程的進程號（PID），找到進程對應的 PCB，獲取進程的狀態。
(2) 修改該進程的狀態，置為終止態。
(3) 若該進程運行期間調用了進程創建指令，創建了子進程， 則要把其子進程也進行終止。
(4) 將分配給該進程的所有資源收回：①如果該進程有父進程，則將資源歸還給其父進程，這個進程會成為僵尸進程，其 PCB 會被保留；②如果沒有父進程，則將資源歸還給操作系統。
(5) 將被終止進程的 PCB 從所在隊列中移除；若該進程原先處于執行態，則應再從就緒隊列中調度一個進程執行。

3. 進程的阻塞和喚醒

????????當進程請求資源失敗（資源不足、資源未到達等）或等待某個事件發生時，該進程無法繼續執行，便會執行阻塞原語，讓出處理器資源，變為阻塞態。當進程請求的資源到達或等待的事件發生時，相關進程可調用喚醒原語，通知之前因等待而變為阻塞態的進程，使其變為就緒態。
????????【提示】進程阻塞的過程是主動的，由進程自己調用阻塞原語來自 我阻塞（因此進程只能從運行態轉為阻塞態，不能由就緒態轉為阻塞態）；而進程喚醒的過程是被動的，由其他進程調用喚醒原語來喚醒自己。此外，正常情況下，阻塞原語和喚醒原語一定是成對出現的，這樣才能保證進程不會被無限期阻塞。

① 進程阻塞發生在以下幾個場合

(1)?進程向系統請求臨界資源（詳見進程同步一節）失敗。
????????【舉例】考慮一臺計算機擁有 3 臺打印機資源且均已經被分配給其他進程，此刻進程?PA??請求使用 1 臺打印機，則?PA??會調用阻塞原語。等其他進程釋放了打印機資源，才會喚醒?PA??繼續執行。
(2)?進程等待某種操作的完成：進程在執行過程中，一些操作有著嚴格的先后順序。
????????【舉例】在進程啟動了 I/O 設備希望讀取數據后，該進程必須等待 I/O 設備將數據讀取完畢，才能進行之后的操作。這個等待期間，進程會觸發阻塞原語進入阻塞態，等待 I/O 操作完成后，再由中斷處理程序將進程喚醒。
(3)?新數據尚未到達。
????????【舉例】考慮進程?PA?、PB??相互協作的情況，如果?PA??需要?PB??的相關數據才能繼續運行，則?PA??在等待數據時會進入阻塞態，直到?PB??向?PA??提供數據并將其喚醒。
(4)?等待新任務的到達：當前進程無任務需要處理，但等待著下一個任務的到來，就可以在等待的過程中將自己阻塞。
????????【舉例】例如網絡操作系統中的某些系統進程，在完成任務后，會自我阻塞并等待新任務到來。

② 阻塞原語的執行過程

(1) 根據進程的 PID，找到進程對應的 PCB，獲取進程的狀態。
(2) 若該進程此時為執行態，則將其置為阻塞態，將其 PCB 插入到阻塞隊列中。
(3) 進行上下文切換，從就緒隊列中選擇一個進程，將其轉換為運行態并為其分配處理器，使其可以運行。

③ 進程喚醒發生在以下幾個場合：
(1) 進程向系統請求臨界資源失敗后，使用該臨界資源的進程釋放了該資源。
(2) 進程等待的操作已經發生。
(3) 進程等待的數據到達。
(4) 進程獲得了一個新的任務。
【提示】進程喚醒發生的場合與阻塞發生的場合相對應，記住阻塞發生的場合，自然能想到進程喚醒發生的場合。
④ 喚醒原語的執行過程：
(1) 找到阻塞隊列中對應進程的 PCB。
(2) 更改該進程狀態為就緒態，將該進程的 PCB 放入就緒隊列中。

4. 進程切換

????????進程切換，指操作系統內核掛起當前運行的進程，調度就緒進程占用處理器運行。進程切換的過程中，通過 PCB 保存處理器狀態信息。
????????【提示】因為進程切換需操作系統內核的支持，所以進程切換必然發生在內核態而非用戶態。
????????為什么需要進程切換？操作系統對計算機的各類資源進行管理，而這些資源又是有限的。為了滿足每個進程使用資源的請求，操作系統需要進行處理器調度，即決定哪些資源在哪些時間里歸哪些進程使用，而進程切換，就是實現處理器調度的手段之一。
①?上下文切換（Context Switch）
????????上下文切換，指保存和恢復處理器上的信息，狹義上，可以認為是保存當前使用處理器進程的相關信息，并將待調度進程的處理器信息恢復到處理器上。“上下文” 一詞，可以理解為進程的工作環境。考慮進程?PA??要進行進程切換，必須把當前時刻處理器上的重要信息（如寄存器信息）記錄，就好像是一張快照。無論之后的其他進程怎樣設置處理器上的數據，在?PA??重新占有處理器時，操作系統把之前的上下文恢復，從?PA??的角度而言，就好像沒有任何進程使用過處理器一樣。
????????【提示】因考綱中使用 “上下文切換” 這一說法，故下文統一使用該種說法。
????????【舉例】有兩個進程?PA?、PB?。PA??正在占用處理器運行，處理器中的寄存器里存有它的數據，比如 PC 寄存器存儲了該進程執行的代碼地址、CR3 寄存器存儲了該進程的頁表基地址。此時操作系統決定暫停?PA?，讓進程?PB??使用處理器，之后有機會再讓?PA??繼續運行。那么，當?PA??再一次使用處理器時，如何保證處理器中寄存器的內容不變呢？倘若不在?PA??放棄處理器時保留該瞬間的一些信息，其他進程使用處理器時就會把這些信息搞得一團糟。可以想象，當?PA??重新占有處理器時，曾經處理器中的信息已經改變，那么這個進程就不能繼續正常運行了。
②?上下文切換的時機
????????上下文切換發生在操作系統從執行態進程處獲得控制權的任意時刻。中斷、陷阱、系統調用，這些事件都會導致控制權移交給操作系統。上下文切換是進程調度的實現手段之一，是進程調度的一個環節，需結合進程調度的相關內容進一步理解。在 2.2.2 調度的時機這一小節，會討論調度可以發生的場合和不可以發生的場合，這些場合同樣適用于分析上下文切換。
③?上下文切換過程：
(1) 保存處理器的上下文，例如上文提到的一些重要寄存器。這些信息存儲在進程對應的 PCB 中。
(2) 修改進程狀態，并將該進程的 PCB 放入對應的隊列。
(3) 調度程序選擇另一個進程執行。
(4) 讀取待調度進程的 PCB，修改其運行狀態為執行態。
(5) 更新內存管理的數據結構。
【提示】這一步涉及地址轉換知識，請學習內存管理一章后再做了解。
(6) 恢復待調度程序的上下文環境。
(7) 根據程序計數器 (PC) 指向的位置找到下一行執行的代碼，恢復該進程。
④?模式切換：
????????模式切換指處理器在不同模式間轉換的過程，如果當前操作系統擁有內核態和用戶態兩個狀態，那么模式切換即指從內核態轉換為用戶態或用戶態轉換為內核態的過程。
模式切換發生在中斷處理的過程中。當處理器檢查中斷信號并發現存在未處理的中斷時，需要執行對應的中斷處理程序。具體過程為：將 PC 置為中斷處理程序的起始地址，從用戶態轉換為內核態來獲得執行特權指令的權限。這一過程中，需要將①中斷處理可能改變的信息；②恢復程序運行需要用到的信息保存到被中斷程序的 PCB 中。
????????【提示】上下文切換不是模式切換。模式切換確實涉及上下文環境的保存，但和進程切換是不相同的，模式切換可以不改變正處于執行態進程的狀態，這種情況下，保存和恢復上下文環境的開銷更小。

2.1.5 線程概念和多線程模型

1. 線程的定義

????????線程（Threads），是比進程更小的概念，也稱輕量級進程（Light Weight Process, LWP），是將進程進一步細分的單位。在多道程序操作系統中，引入了進程的概念，用于解決單處理器環境中程序的并發執行問題。為了進一步提高程序的并發執行程度，又引入了線程的概念，一個進程可以同時擁有多個線程，借助多個線程實現程序的并發執行（而不必借助進程），事實也證明線程的引入確實能改善操作系統的性能，所以多數現代操作系統都引入并實現了線程這一概念。
????????【提示】后文會提到用戶級線程和內核級線程，一般教材中提到的輕量級進程特指通過內核實現的線程，注意區分。
????????未引入線程概念時，進程有兩個特點：是資源所有權和調度 / 執行的單位。前者指一個進程擁有對資源的控制和所有權，包括內存、I/O 通道、I/O 設備等；后者指進程是一個可以被操作系統調度的獨立實體。線程可以理解為在調度 / 執行這一屬性上對進程進一步細分。
????????【提示】在引入線程前，進程是操作系統調度的最小單位；在引入線程且是由操作系統內核支持的線程后，線程是操作系統調度的最小單位。同時，進程仍然是操作系統分配資源的最小單位，線程的引入并未改變進程資源所有權這一特點。

2. 引入線程的優勢

(1) 進一步提高并發性

????????線程可以進一步細化進程中的各種任務，提高任務的并發性。在單處理機系統中，線程模型可以分離同一個進程內的 CPU 計算和 I/O 訪問，讓它們并發進行。在多處理機系統中，引入線程模型前，無論有多少處理機，一個進程都只能占用一個處理機；引入線程模型后，每個線程都能占用一個處理機，這使得多處理機系統的優勢得以充分發揮。
????????【提示】線程和進程在很多概念和設計理念上，是極其相似的。例如進程的提出，就是想讓多個作業能夠同時在操作系統中運行，防止一些作業阻塞時浪費處理器資源的情況，而線程則是讓一個作業的多種活動進一步細分，例如一個作業需要請求外存數據以及進行大量的計算，在請求資源且未得到回復時，另一個線程仍然可以進行計算，無需因為等待結果的返回而阻塞。

(2) 共享地址空間與可用數據

????????進程間由于相互的 “隔離”，無法直接共享數據，這就帶來了進程間通信的問題。而線程模型的引入，使得并行實體擁有了共享地址空間、數據的能力，換言之，線程之間可以直接共享數據而不需要經由操作系統內核，在速度上有很大優勢。

(3) 線程更輕量級

????????線程無論是創建、切換還是撤銷，都遠快于進程。在很多操作系統中，一個線程的創建較進程的創建快 10 - 100 倍。在短時間需要反復開啟或撤銷大量線程時，線程的輕量級是十分有優勢的。

(4) 提高交互性

????????線程還能提高圖形界面程序的交互性，避免程序 “卡死”。例如，一個運行中的文字編輯器就可以是一個由多線程構成的進程。假設這個進程只有兩個功能：接收用戶的輸入以及將當前的文件存儲到外存。若該進程未引入線程概念，當用戶命令其存儲文件時，進程就會進行 I/O 請求直到 I/O 響應，在此期間對于用戶的任何操作，編輯器均不會做出響應。如果該進程引入線程概念并開啟兩個線程（分別對應文件存儲工作和與用戶交互工作），那么在一個線程請求并等待響應時，另一個線程還能接受用戶請求，從而使用戶得到更好的體驗。

3. 線程的組織

????????一個操作系統中的多個進程之間具有很大的獨立性，而進程中的多個線程則不同，它們擁有完全相同的地址空間，這意味著它們可以共享全局數據。一個多線程的進程模型如圖 2.2 所示。每個線程訪問的地址空間，都由其所在進程擁有。同一進程的不同線程間甚至可以修改對方的堆棧上的數據，這種情況下，多個線程間是沒有保護的。但是，“沒有保護” 不是線程的缺點，而是使得線程間能夠共享數據的優點。同一個進程的多個線程是屬于同一用戶的，該用戶創建多個線程的目的是讓其彼此更好地配合完成作業，因此用戶在編程時就會避免多個線程之間可能出現的互相干擾行為，使這些線程間不會因為 “沒有保護” 而相互干擾。

(1) 線程的三個基本狀態

????????和傳統的進程相似，線程也有三個基本狀態：執行態、阻塞態、就緒態。線程狀態之間的轉換和進程狀態之間的轉換是一樣的，可參考圖 2.1。
(a)?執行態：在該狀態下，線程獲得處理器并運行。
(b)?就緒態：表示線程可以被調度執行，被分配處理器就可以立刻執行工作。
(c)?阻塞態：指線程在執行過程中，因為某些事件而阻塞并等待。
【舉例】線程申請了 I/O 操作并等待結果的返回，則它進入阻塞態。

(2) 線程控制塊 TCB

????????和進程類似的，每個線程也具有一個對應的線程控制塊（Thread Control Block, TCB），用于控制和管理線程的狀態、保存線程的信息。線程控制塊中通常有以下幾類信息：
(a)?線程標識符（TID）：每個線程的唯一標識符。
(b)?寄存器信息：用來記錄包括通用寄存器、程序計數器、狀態寄存器等關鍵寄存器的信息。
(c)?線程執行狀態：用于記錄線程的執行狀態。
(d)?優先級：用于線程調度。
(e)?線程專有存儲區：用于線程切換時保存現場信息。
(f)?信號屏蔽：每個線程擁有各自的信號屏蔽字。
(g)?堆棧指針：TCB 中分別設置了兩個指向堆棧的指針，分別指向用戶自己的堆棧和核心棧。每個線程都有自己的堆棧，在線程運行過程中，會進行過程調用（或稱函數調用），就可以把過程調用相關的局部變量以及調用完成之后的返回地址存儲在堆棧中。
????????【提示】核心棧是線程運行在內核態時使用的。
????????【舉例】有三個過程（函數）?FA?、FB?、FC?：FA??調用了?FB?，FB??調用了?FC?，在?FC??執行時，FA?、FB?、FC??三個過程的變量和返回地址都會存儲在堆棧上。

4. 線程的實現

????????如圖 2.3 所示，根據操作系統的不同，線程的實現方式也不完全相同，主要分為兩類：內核級線程（Kernel Supported Threads, KST）和用戶級線程（User - Level Threads, ULT）。

【提示】不同文獻對線程實現方式的英文稱呼不盡相同，有的文獻還會使用 Kernel - Level Thread 來表示內核級線程。

(1) 用戶級線程

????????線程的管理由應用程序實現，在用戶空間下完成。操作系統內核感知不到線程的存在，在該種方式下，調度的最小單位依然是進程，線程的調度則由其所在進程實現。

(2) 內核級線程

????????線程和進程一樣，均需要操作系統內核的支持，其創建、阻塞、撤銷和切換都是在內核空間下實現的，內核通過 TCB 來對線程進行感知和控制。在該種方式下，線程是調度的最小單位。

5. 用戶級線程

① 用戶級線程的優點

(1) 可以在不支持線程的操作系統中實現線程。具體實現上，主要通過用戶空間的線程庫實現，應用程序使用線程庫進行多線程設計，進程通過調用函數開啟多線程。
(2) 可以允許進程自主定制調度算法。操作系統只負責把處理器與其他資源分配給進程，由進程繼續將這些資源分配給該進程創建的線程，線程的調度與資源分配都由進程自主完成，可以更好地安排各個線程的工作，也使得線程具有更好的擴展性。
(3) 線程的切換完全在本進程中完成而沒有內核的參與，所以這種實現方式的效率更高。
【提示】所有線程相關的數據結構都在進程的用戶地址空間，所以線程的切換不需要轉換成內核態，這就避免了兩次狀態轉換帶來的開銷。

② 用戶級線程的缺點

(1) 一旦某個線程被阻塞，該線程所屬的整個進程都會被阻塞。
(2) 如果只使用用戶級線程，一個多線程程序不能利用多處理器技術。因為操作系統只會為一個進程分配一個處理器，所以一個進程中只能有一個線程處于執行態。
【提示】對于這兩個缺點，也有對應的解決方法，例如將多線程程序轉換為多進程程序、使用 jacketing 技術克服阻塞等，此處了解即可。

6. 內核級線程

① 內核級線程的優點

(1) 在多處理系統中，內核可以調度一個進程內的多個線程到多個處理器上運行。
(2) 當一個線程被阻塞，內核可以調度該進程中的另一個線程到處理器上運行。
(3) 操作系統內核自身可以使用多線程。

② 內核級線程的缺點

(1) 線程切換時，需要內核介入。模式切換帶來了額外開銷。
【提示】《操作系統精髓與設計原理》中提到，在 Null Fork 和 Signal - Wait 兩個測試中，用戶級線程的性能優于內核級線程，內核級線程的性能優于進程，且兩兩之間都有一個數量級以上的性能差距。

7. 用戶級線程和內核級線程的組合方式

????????有些操作系統把內核級線程和用戶級線程兩種方式組合，比如使用內核級線程，然后將用戶級線程與內核級線程進行多路復用。采用這種方法時，編程人員可以決定有多少個內核級線程與多少個用戶級線程對應。內核只識別內核級線程并對其進行調度，而這些內核級線程會被多個用戶級線程多路復用。用戶級線程和內核級線程之間有以下三種關系，考生可以結合圖 2.3 中的 (c) 理解：

① 一對一模型

????????一個用戶級線程映射到一個內核級線程，相比于多對一模型，具有更好的并發，當一個線程被阻塞時，其余線程能夠繼續執行。缺點是太多的內核級線程會增加開銷，影響程序性能。

② 多對一模型

????????將多個用戶級線程映射到一個內核級線程。這一模型的優點在于效率較高，線程切換在用戶態就能完成；缺點在于如果一個用戶級線程發生了阻塞，整個進程都將被阻塞；此外，由于同一進程的多個用戶級線程共同映射到一個內核級線程上，這導致用戶級線程無法在多處理機系統上并行運行。
【提示】在一對一模型的實現下，同一進程的不同線程間切換時，需要涉及內核狀態轉換；在多對一模型實現下，同一進程的不同線程間切換時，不需要涉及內核狀態轉換。

③ 多對多模型

????????多對多模型。將 x 個用戶級線程映射到 y 個內核級線程，其中 x > y。這種模型可以認為是上述兩類模型的折中，避免了上述兩個模型的缺點：編程人員可以創建任意多個用戶級線程，這些線程也能在多核系統上并發運行。
【提示】若 x = y，則該模型退化為一對一模型；若 x < y，則該模型退化為一對一模型且有若干內核級線程的浪費。

2.1.6 進程和線程的對比

進程和線程有著很多類似的特征，傳統進程相當于一個單線程進程，進程和線程的對比如表 2.4 所示。

表 2.4? 線程和進程的對比

對比項	進程	線程
調度	不再是調度的最小單位（引入內核線程后）	是調度的最小單位
擁有資源	進程都是資源分配的基本單位	線程只擁有少量資源
并發性	多個進程間可以并發執行	一個進程的多個線程也能并發執行
獨立性	只共享全局變量	只有少數資源不能共享，例如線程的棧區
系統開銷	通信、進程切換開銷大	通信、切換開銷小
多處理機	單個進程只能運行在一個處理機上	多線程進程可以充分利用多處理機
其他	進程間相互不影響	用戶級線程的阻塞會影響整個進程

????????(1)?調度的最小單位：在未實現線程的傳統操作系統中，進程是處理器調度的最小單位；在實現了線程的操作系統中，線程是處理器調度的最小單位。
????????【提示】上述線程特指內核級線程，用戶級線程并不是處理器調度的最小單位。詳見上文線程的實現。
????????(2)?并發性：在未實現線程的傳統操作系統中，只有進程之間可以并發執行；在實現了線程的操作系統中，一個進程中的所有線程和不同進程中的不同線程均可以并發執行，從而提高了操作系統的并發性、資源利用率和系統吞吐量。
????????【舉例】未引入線程概念時，一個音樂播放進程只能播放音樂；引入線程后，該進程可以開啟多個線程，分別實現音樂播放、顯示歌詞等任務，實現多個任務的并發執行。
????????(3)?擁有資源：進程可以擁有資源且是資源分配的最小單位。線程的資源依賴于創建它的進程，每個線程除了一些最核心的資源是私有的，包括線程控制塊 TCB、少量寄存器（程序計數器）和棧區外，剩下的資源全部依賴于進程，并與該進程的其他線程共享。
????????(4)?獨立性：線程間的獨立性要比進程間的獨立性低得多，多個線程可以共享進程的內存地址空間和資源；進程之間除了共享全局變量外，每個進程都擁有獨立的地址空間和不同資源。
????????【提示】進程的高獨立性是為了防止進程與進程間的有意或無意的破壞，而一個進程的多個線程因為同屬于一個所有者，不會相互破壞。降低獨立性有利于提高線程間的通訊效率以及進一步提高并發性，同一進程的線程間可以便捷地實現通信，而進程間通信往往需要操作系統內核的支持。
????????(5)?系統開銷：線程的創建、撤銷以及切換的代價遠小于進程。此外，因為線程的獨立性低，線程間的同步、通信的實現代價也小于進程。
????????【舉例】Solaris2 OS 中，線程的創建比進程的創建快 30 倍，切換比進程快 5 倍。

2.1.7 進程通信

????????進程與進程在運行過程中需要相互協作和交換信息，例如：父進程安排子進程處理一批數據并將結果返回給自己。這就涉及一個重要的問題：如何進行通信？進程通信問題，稱為 IPC（Inter Process Communication）問題。
實現進程通信需要解決三個問題：
(1) 進程通過何種方式把信息傳遞給其他進程。
(2) 保證多個進程在關鍵活動上不會重疊。
【舉例】多個進程同時請求修改同一塊共享內存，但是這塊內存需要互斥訪問，此時就發生了重疊，需要操作系統考慮并解決誰先訪問、誰后訪問、如何保證互斥的問題。
(3) 進程按照正確的順序推進。
【舉例】父進程安排子進程處理數據，得到子進程返回的數據后才能進行下一步計算，如何控制父進程和子進程按照用戶希望的順序執行？這也是操作系統需考慮和解決的問題。
????????為什么會有上述的問題？進程之間是平等且互相隔離的，進程難以察覺到其他進程的存在，也難以察覺到自己被操作系統調度。當進程的狀態轉換為執行態以外的狀態時，該進程的整個 “世界” 就停止了。所以在一個進程的視角中，自己獨占了整個計算機的資源，從開始到結束一直在運行。只有這臺計算機上的操作系統如 “上帝” 一樣，能夠看清楚無數個進程在以什么樣的模式被組織與調度。

1. 進程通信機制綜述

????????通信機制可以進一步細分為低級通信方式與高級通信方式。①低級通信方式：通信效率低；通信對用戶不透明，編程人員在使用時需要考慮更多方面的問題（數據的傳輸、進程間的互斥、同步等）。②高級通信方式：可以高效地實現大規模數據的傳輸；由操作系統以系統調用形式提供，實現細節、通信過程等問題對編程人員透明，從而減少編程負擔。這里主要介紹進程通信的 5 種方法：信號量機制、共享存儲機制、消息傳遞機制、管道通信機制和信號機制。這些進程通信機制的總結如表 2.5 所示。
【提示】本部分內容為宏觀上的總結，考生可以在學習完本章進程同步一節后再回顧一遍。

(1) 信號量（Semaphore）機制

????????信號量機制，可以有效地解決進程同步和互斥問題，進程通過執行 P/V 操作控制信號量，屬于低級通信方式。
????????【舉例】實際使用時，編程人員會將信號量和實際資源聯系在一起。若有 3 個打印機資源，就設置一個值為 3 的信號量。占用打印機時，進程執行 P 操作，使得信號量值減 1；釋放打印機資源時，進程執行 V 操作，使得信號量加 1。

(2) 共享存儲（Shared Memory）機制

????????根據共享公用數據結構還是存儲區，可以將該機制細分為以下兩種方式。
????????(a)?共享數據結構的通信方式：該種實現下，進程間共享同一個數據結構，編程人員需要考慮進程間的同步互斥問題，傳輸效率低，屬于低級通信方式。
????????(b)?共享存儲區的通信方式：該種實現下，操作系統在內存中開辟一塊共享存儲區，多個進程可以對該內存區域進行讀寫，傳輸效率高，屬于高級通信方式。當進程希望對共享存儲區進行存取時，會將自己的虛地址空間映射到共享存儲區，并向操作系統提出申請。
????????【舉例】某個網站同時只能有一個用戶登錄，該網站有一個留言板功能，不同的用戶之間想交流時就輪流登錄在留言板上寫下自己的話。留言板就類似于上文提到的共享存儲區。

(3) 消息傳遞（Message Passing）機制

????????上文提到，雖然進程間相互獨立難以感知，但是操作系統是可以有效管理所有進程的。進程間可以調用由操作系統實現的通信命令來傳遞消息。實現消息傳遞即分別實現 Send 和 Receive 兩個原語，用于消息的發送和接收。消息傳遞系統是高級通信方式，可以細分為以下兩類：
????????(a)?直接通信方式：發送進程直接將消息發送給接收進程，將信息掛載到接收進程的消息隊列上，接收進程從自己的消息隊列中獲取消息。
????????(b)?間接通信方式：操作系統額外創建一片空間用于存儲各種消息，類似一個信箱，發送進程和接收進程依靠這個中間實體實現信息的發送和接收。這種方式也被稱為信箱通信模式，在計算機網絡中被廣泛運用。在信箱通信方式下，通過不阻塞發送，阻塞接收的方式實現進程的同步。
????????【提示】就同一個信息的復制次數而言，間接通信方式需要兩次復制：第一次是將信息從發送者進程的存儲區復制至操作系統內核開辟的存儲區，第二次是將信息從操作系統內核開辟的存儲區復制到接收者進程的存儲區；直接通信方式只需一次復制，即操作系統內核直接將消息從發送者進程的存儲區復制到接收者進程的存儲區；共享存儲區通信方式則可以實現 0 復制，亦即發送者可以直接在共享存儲區生成信息，生成后無需任何操作就能被接收者讀取。
????????回憶第一章所述，微內核操作系統將一部分操作系統的功能實現為用戶態進程，換言之，很多系統調用都需要交給另一個進程來執行，它們的實現方式就是進程通信。因此，進程通信的效率很大程度上決定了微內核操作系統的效率。最早的微內核操作系統采用間接通信方式，每個系統調用都需要兩次復制，因此效率較低；后來的微內核操作系統引入了直接通信方式，將兩次復制減為一次，大大提高了運行效率。

(4) 管道（Pipeline）通信機制

????????該方式下，使用一種共享文件來實現進程間通信。這種共享文件稱為管道（或 pipe 文件），可連接一個讀進程和一個寫進程。寫進程以字符流的形式，將數據送入管道，讀進程通過管道將數據讀出。操作系統實現管道機制需要提供三種機制：同步機制、互斥機制，和通信進程間確定對方存在的機制。管道具有以下特點：
(a)?同步：讀進程和寫進程需要相互配合，寫進程向管道中寫入一定量數據后，會進入阻塞狀態，等待讀進程將數據讀出后將其喚醒；讀進程在將管道中數據讀完后，也會進入阻塞狀態，等待寫進程對管道寫操作完畢后將其喚醒。
(b)?互斥：當有一個進程在對一個管道讀 / 寫時，其他想要讀 / 寫該管道的進程必須等待 。
(c) 管道需要通信雙方確定對方的存在，否則會陷入阻塞。考生可以使用 Linux 的 FIFO 管道進行簡單實驗，創建一個 FIFO 文件并向管道中寫入隨機內容，在未出現讀進程前，寫入進程是處于阻塞狀態的。
(d) 管道是一個固定大小的緩沖區（如 4KB），在內核中實現，其大小不受磁盤大小影響。
(e) 管道的實質是一個共享文件，讀進程將管道視為輸出文件，寫進程將管道視為輸入文件，管道通信可以利用文件系統機制實現。
(f) 讀數據操作是一次性的，管道中的數據一旦被讀取就會被拋棄。
(g) 管道是半雙工通信的，某一時刻，數據只能單向傳輸，若希望實現雙向傳輸（即全雙工），可以使用兩個管道，如圖 2.4 所示。另外，管道以字符流進行讀出和寫入，子進程會繼承父進程的管道并利用管道與父進程通信。

(5) 信號（Signal）通信機制（2025 考研 408 大綱新增內容）

????????信號是一種具有單向事件通知能力的軟中斷，在 Linux 系統中有非常廣泛的使用 。操作系統通過發送指定信號來通知進程某個事件發生，以迫使進程執行信號處理程序。信號處理完畢后，被中斷進程將恢復執行 。
信號可以由用戶、操作系統內核和進程產生：
①?用戶：用戶能通過輸入特定字符來請求內核產生信號。例如：在 Unix、Linux 和其他類 Unix 操作系統中，用戶按下中斷鍵（通常是 Ctrl + C），操作系統會給前臺進程組中的所有進程發送中斷信號 SIGINT。
②?操作系統內核：當進程運行遇到錯誤時，操作系統內核檢測到錯誤事件會發送信號給出錯進程。例如：當數組下標越界時，操作系統內核會發送段錯誤 SIGSEGV 信號給進程。
③?進程：進程之間可以通過系統調用產生信號進行通信。
【提示】在 Linux 系統中總共有 62 個信號：①編號為 1 ~ 31 的信號稱為標準信號，這些信號在 Unix 和類 Unix 操作系統中是標準化的，每個信號都有其特定的用途；②編號為 34 ~ 64 的信號稱為實時信號，這些信號是 Linux 獨有的，用于應用程序之間自定義的進程間通信。

????????在 Linux 系統中，32 號和 33 號信號被系統保留，沒有賦予標準的名稱和用途。
操作系統內核一般會通過如下 3 種方式之一來處理信號：
①?直接忽略：進程可以將信號處理函數設置為 SIG_IGN 來通知內核忽略大部分信號，但信號 SIGKILL 和信號 SIGSTOP 除外，不可忽略。
②?執行內核默認處理函數：對于未注冊信號處理函數的信號，進程會執行其默認操作（大多為終止進程或直接忽略信號）。
③?執行信號處理函數：進程可以通過系統調用（signal 或 sigaction）為特定信號注冊處理函數，內核接收到信號時會將信號編號作為參數調用該函數。信號處理函數可以執行任何合法的操作，例如：清理資源、保存狀態、通知其他進程等。
【提示】進程間信號通信機制是通過用戶注冊的信號處理函數來實現的。
常見的信號、信號值及功能如表 2.6 所示：

表 2.6 常見的信號、信號值及功能

信號名稱	信號值	信號功能
SIGINT	2	中斷信號，通常由用戶按下 Ctrl + C 組合鍵產生，用于中斷前臺進程的執行
SIGILL	4	用于報告進程執行了 “非法指令”（例如：非法操作碼、非法操作數、特權指令等）
SIGKILL	9	強制終止信號，無法被捕獲、忽略或阻塞，用于立即終止進程
SIGCHLD	17	在子進程狀態（終止、暫停、恢復執行）發生改變時通知父進程
SIGSTOP	19	停止信號，無法被捕獲或忽略，用于暫停一個進程的執行

2.1.8 習題精編

1.下列關于進程敘述，錯誤的說法是（ ）。
A. 進程是動態的，而程序是靜態的
B. 在內存中的程序段就是進程
C. 在進程的生命周期中，存在多種狀態
D. 進程可以占有處理機運行，而程序不行

1.【參考答案】?B
【解析】?進程由程序段、數據段、進程控制塊 PCB 三部分組成。B 選項認為程序段就是進程，這種觀點片面且錯誤，進程運行需將程序段裝入內存，但內存中的程序段并非進程。A 選項強調進程的動態性，C 選項強調進程的狀態，D 選項表明進程是處理器調度單位，這些說法均正確。

2.進程在處理器上執行時，錯誤的說法是（ ）。
A. 進程是一個動態的過程，終有結束的時刻
B. 多個進程可以并發地在處理機上執行
C. 并行的進程之間都存在著相互依賴和制約的關系
D. 進程的并發執行可能導致程序的結果與進程執行速度有關

2.【參考答案】?C
【解析】?并行的進程之間，可利用信號量等機制實現同步、互斥等關系，但并非所有并行（或并發）進程間都存在相互依賴或制約關系。例如，系統中音樂播放進程和聊天進程運行時可毫無聯系。A、B、D 選項是對進程特點的正確敘述。

3.下列關于并發進程特性的陳述，正確的是（ ）。
A. 進程是一個動態過程，其生命周期是連續的
B. 并發進程執行完畢后，一定能夠得到相同的結果
C. 并發進程對共享變量的操作結果與執行速度無關
D. 并發進程的結果具有不可再現性

3.【參考答案】?D
【解析】?A 選項前半句正確，后半句錯誤，失去封閉性會使并發進程的執行結果與執行速度相關，這也導致并發進程具有不可再現性，所以 B、C 選項錯誤，D 正確。

4.進程的基本特征不包括（ ）。
A. 動態性
B. 并發性
C. 共享性
D. 異步性

4.【參考答案】?C
【解析】?進程的基本特征為動態性、并發性、獨立性和異步性，C 選項共享性錯誤，進程間的隔離程度較高。

5.有若干并發進程均將一個共享變量 count 中的值減 1 一次，那么有關 count 中的值說法正確的是（ ）。
I. 肯定有不正確的結果
II. 肯定有正確的結果
III. 若控制這些并發進程互斥執行 count 減 1 的操作，count 中的值正確
A. I、III
B. II、III
C. III
D. 上述說法都不正確

5.【參考答案】?C
【解析】?只有當每個進程互斥修改 count 時，才能得到確定且正確的結果，所以 III 正確；若不控制進程互斥修改 count，結果是未知的（可能正確也可能錯誤），I、II 錯誤，因此選項 C 正確。

6.關于子進程和父進程的說法，下面正確的是（ ）。
A. 一個父進程可以創建若干個子進程，一個子進程可以從屬于若干父進程
B. 父進程被撤銷時，其所有的子進程也應該被相應撤銷
C. 子進程被撤銷時，其所屬的父進程也被撤銷
D. 一個進程必定有父進程或子進程

6.【參考答案】?B
【解析】?一個父進程可創建若干子進程，一個子進程只從屬于一個父進程，A 錯誤。當父進程被撤銷時，操作系統會收回分配給該進程的所有資源，并終止其創建的子進程，B 正確。子進程被撤銷時，其父進程不會被撤銷，C 錯誤。在 Unix 系統中，除進程 0 外，并非任意一個進程都一定有父進程或子進程，D 錯誤。

7.并發進程失去了封閉性是指（ ）。
A. 多個相對獨立的進程以各自的速度推進
B. 并發進程的執行結果與速度無關
C. 并發進程執行時，在同時刻發生的錯誤
D. 并發進程共享變量，其執行結果與速度有關

7.【參考答案】?D
【解析】?進程的封閉性指進程執行結果只取決于自身，不受外界因素影響，即執行結果確定。當進程失去封閉性后，其執行結果會受速度影響，選項 D 正確。

8.下面的敘述中，錯誤的是（ ）。
A. 就緒態、執行態和阻塞態，是進程的三個基本狀態
B. 因為并發進程的間斷性，進程在其生命周期中，呈現出多種狀態
C. 每個進程的創建態、終止態只能有一次
D. 進程申請處理器卻未得到滿足時，其狀態應該是阻塞態

8.【參考答案】?D
【解析】?進程申請處理器資源時，表明該進程已獲得除處理器外的全部資源，此時應處于就緒態而非阻塞態，D 選項錯誤。阻塞態下，進程需等待 I/O 數據返回或所等待事件發生，才會轉換為就緒態參與處理器競爭。

9.進程的哪一種狀態，是進程的基本狀態且可以從另外兩個基本狀態轉換而來（ ）。
A. 執行態
B. 就緒態
C. 阻塞態
D. 終止態

9.【參考答案】?B
【解析】?進程的三個基本狀態是就緒態、阻塞態和執行態，其中就緒態可由阻塞態和執行態轉換而來，就緒態不能轉換為阻塞態，阻塞態也不能轉換為執行態，所以正確答案是 B 選項。

10.在支持多道程序設計的操作系統中，調度程序會調度各個進程并發使用處理器，下列事件中，不一定能引起進程調度的是（ ）。
A. 處于執行態的進程進行 I/O 操作并等待結果返回
B. 一個新進程被創建并轉換為就緒態
C. 處于執行態的進程發生錯誤
D. 處于執行態的進程時間片耗盡

10.【參考答案】?B
【解析】?當進程被創建并放入就緒隊列時，不一定會引起調度，所以選 B。A、C、D 三種情況，均是執行中的進程因某些事件放棄處理器，此時操作系統必須調度下一個進程使用處理器。

11.下列事件中，會引起進程由執行態轉換為就緒態的是（ ）。
A. 時間片耗盡
B. 進程等待某一事件的完成
C. 進程進行 I/O 請求并等待結果
D. 進程運行結束

11.【參考答案】?A
【解析】?B、C 使進程轉換為阻塞態，D 使進程變為終止態，時間片耗盡使進程由執行態轉換為就緒態，A 正確。

12.下列事件中，會引起進程由執行態轉換為就緒態的是（ ）。
A. 一個新進程被創建并進入就緒隊列
B. 進程發生錯誤
C. 被高優先級進程搶占處理器
D. 進程等待的事件發生

12.【參考答案】?C
【解析】?A 選項（創建新進程）不一定會導致當前運行進程的處理器被搶占，所以 A 選項錯誤，C 選項正確。進程發生錯誤會導致進程終止，B 選項錯誤；進程等待的事件發生時，會從阻塞態轉換為就緒態，D 選項錯誤。

13.下列事件中，不會引起進程轉換為阻塞態的是（ ）。
A. 進程等待某個事件的發生
B. 進程等待 I/O 請求的數據
C. 進程等待處理器使用權
D. 擁有前后驅關系的兩個進程，后繼進程等待前驅進程的信號

13.【參考答案】?C
【解析】?進程等待處理器使用權時處于就緒狀態；等待其他事件和資源時處于阻塞狀態。A、B、D 選項均涉及 “等待” 處理器以外的事件或資源，會使進程進入阻塞狀態；C 選項進程等待處理器時處于就緒態，不會轉換為阻塞態，故選 C。

14.關于進程的狀態和狀態轉換，以下哪一種說法是正確的（ ）。
A. 進程由創建而產生，由調度而執行，因得不到資源而掛起，以及由撤銷而消亡
B. 在具有掛起狀態的進程管理中，處于掛起就緒狀態的進程會因為申請資源失敗而進入掛起阻塞狀態
C. 進程在運行期間，不斷地從一個狀態轉換到另一個狀態，它可以多次處于就緒狀態和執行狀態，也可多次處于阻塞狀態，但可能排在不同的阻塞隊列
D. 正在執行的進程，若時間片用完，會進入阻塞狀態

14.【參考答案】?C
【解析】?進程因得不到資源會進入阻塞態而非掛起態，掛起是指操作系統將進程從內存移到輔存，發生在中級調度過程中，A 錯誤。就緒掛起狀態無法轉換到阻塞掛起狀態，B 錯誤。時間片用完后，進程通常轉換為就緒狀態，D 錯誤。

15.在進程狀態切換時，引起內存與輔存之間交換數據的是（ ）。
A. 運行到就緒
B. 運行到等待
C. 運行到掛起
D. 就緒到運行

15.【參考答案】?C
【解析】?進程的三個基本狀態間的轉換都發生在內存中，所以 A、B、D 選項均不符合。掛起狀態是將內存中的進程移動到輔存中，C 正確。建議考生先學習進程調度的三個層次相關內容，再做此題。

16.進程控制塊是進程的重要組成部分，下列內容中，PCB 中不應該包括（ ）。
A. 進程標識符（PID）
B. 處理器狀態信息
C. 進程狀態
D. 互斥信號量

16.【參考答案】?D
【解析】?互斥信號量由操作系統管理，并不記錄在 PCB 中，所以本題選 D。

17.進程控制塊 PCB 中不可能包含的信息是（ ）。
A. 進程優先級
B. 進程狀態
C. 進程執行的代碼
D. 進程名

17.【參考答案】?C
【解析】?進程執行的代碼屬于代碼段，和 PCB 一樣是進程的組成部分，但不會包含在 PCB 中，所以本題選 C；A、B、D 選項內容均可出現在 PCB 中。

18.進程創建原語中，不需要包含的步驟是（ ）。
A. 分配空白 PCB
B. 分配處理器資源
C. 初始化 PCB 上內容
D. 分配內存資源

18.【參考答案】?B
【解析】?進程從創建到轉換為就緒態的過程中，不包括分配處理器這一步驟，分配處理器資源發生在調度過程中，所以 B 選項錯誤。

19.下列選項中，導致創建新進程的操作是（ ）。
I. 用戶登陸
II. 高級調度發生時
III. 操作系統響應用戶提出的請求
IV. 用戶打開了一個瀏覽器程序
A. 僅 I、IV
B. 僅 II 和 IV
C. 僅 I、II 和 IV
D. 全部

19.【參考答案】?D
【解析】?進程創建的場景可歸為四類：用戶登錄時、高級調度發生時、系統響應用戶請求時以及現有進程創建新進程時。I、II、III 顯然正確，IV 中用戶打開一個瀏覽器程序，通常也會創建一個或多個進程，所以答案選 D。

20.進程創建過程必需的內容是（ ）。
I. 建立進程控制塊
II. 為進程分配 CPU
III. 為進程分配內存
IV. 將進程鏈入就緒隊列
A. 僅 I、III
B. 僅 I
C. I、II、III
D. I、III、IV

20.【參考答案】?A
【解析】?II 不是進程創建必需的，分配處理器的行為發生在調度過程中（就緒態轉換為執行態的過程）。IV 也不是進程創建必需的，在多數操作系統中，新進程創建后，若系統資源充足且就緒隊列未滿，通常會被鏈入就緒隊列等待 CPU 調度；若資源不足或就緒隊列已滿，新進程可能會處于掛起態或阻塞態，直至資源可用或就緒隊列有空位。I、III 是進程創建必需的。

21.下列關于用戶進程被創建后的陳述，錯誤的是（ ）。
A. 一定會先進入就緒隊列
B. 進程在其生命周期中，可能不會經歷阻塞態
C. 當時間片耗盡后，進程轉換為終止態
D. 操作系統會回收處于終止態進程的資源

21.【參考答案】?C
【解析】?一般情況下，時間片耗盡時，進程大多會轉換為就緒態，只有當時間片耗盡且進程恰好運行結束時，才可能轉換為終止態，C 錯誤。

22.一個進程在運行中，釋放了一臺磁帶機資源和一臺打印機資源，這個行為可能會導致（ ）。
A. 某進程由就緒態轉換為執行態
B. 自身狀態由執行態轉換為就緒態
C. 某進程由阻塞態轉換為就緒態
D. 系統中所有等待打印機資源的進程被喚醒

22.【參考答案】?C
【解析】?進程釋放資源，可能會喚醒之前因請求該資源而阻塞的進程，使其由阻塞態轉換為就緒態，A 錯誤，C 正確。釋放打印機和磁帶資源與釋放處理器并轉換為就緒態并無關聯，B 錯誤。因為只釋放了一臺打印機資源，最多喚醒一個等待該資源的進程，D 錯誤。

23.進程被喚醒時一定會發生（ ）。
A. 該進程立即占用處理器運行
B. 進程的 PCB 移動到就緒隊列之首
C. 優先級改變
D. 進程變為就緒態

23.【參考答案】?D
【解析】?進程被喚醒時，狀態會轉換為就緒態，且其 PCB 會進入就緒隊列，D 正確。A 發生在就緒態轉換為執行態的過程中。B、C 不是必然發生的，取決于操作系統的具體實現。

24.下列關于線程的敘述中，正確的是（ ）。
A. 一個進程只有一個線程
B. 線程之間的通信需要依靠操作系統內核實現
C. 線程只擁有少量私有資源，所以不能獨立被調度
D. 屬于不同進程的線程，它們的地址空間相互獨立

24.【參考答案】?D
【解析】?進程可以包含多個線程，A 錯誤；同一進程內的多個線程共享進程的用戶地址空間，無需依賴內核實現線程間通信，B 錯誤；C 選項前半句正確，后半句錯誤，線程是調度的最小單位。

25.下面的敘述中，正確的是（ ）。
A. 線程的切換，一定會引起進程的切換
B. 線程的切換，不會引起進程的切換
C. 用戶級線程的切換，需要操作系統內核支持
D. 內核級線程的切換，需要操作系統內核支持

25.【參考答案】?D
【解析】?同一進程內的線程切換不會引起進程的切換，不同進程內的線程切換會引起進程切換，所以 A、B 均不正確。用戶級線程的切換由進程完成，操作系統內核感知不到用戶級線程的存在，C 錯誤。內核級線程的切換需要操作系統內核的支持，D 正確。

26.下面的敘述中，正確的是（ ）。
A. 一個進程一定包含多個線程
B. 線程是將進程進一步細分的單位，可以脫離進程獨立運行
C. 引入線程可以進一步提升進程的并行性
D. 線程間相互 “隔離”，無法直接共享數據

26.【參考答案】?C
【解析】?一個進程可以只包含一個線程，A 錯誤。線程是對進程的進一步細分，但線程不是資源分配的基本單位，需依靠進程的資源，不能脫離進程獨立運行，B 錯誤。同一進程的多個線程之間能夠共享進程的大部分資源，D 錯誤。

27.下面的敘述中，正確的是（ ）。
A. 同一進程的多個線程可以并發執行，不同進程的多個線程只能串行執行
B. 同一進程的多個線程只能串行執行，不同進程的多個線程可以并發執行
C. 多線程程序設計上，可以將程序的 I/O 部分和計算部分拆分成兩個線程，以發揮線程優勢
D. 同一進程的線程間通信代價很低，但線程創建操作的代價和進程創建相似

27.【參考答案】?C
【解析】?同一進程和不同進程的多個線程均可并發執行，A、B 錯誤。線程創建、銷毀的代價低于進程，D 錯誤。

28.同一進程的不同線程之間，不能共享的是（ ）。
A. 進程的代碼段
B. 進程的全局變量
C. 進程的用戶地址空間
D. 進程中各個線程的棧指針

28.【參考答案】?D
【解析】?同一進程內的多個線程共享進程的代碼段、全局變量和用戶地址空間。線程的棧指針是私有的，存放在線程控制塊 TCB 中。

29.下列關于多對一線程模型的論述中，正確的敘述是（ ）。
A. 指將多個內核級線程映射到一個用戶級線程
B. 當一個線程被阻塞時，同一進程內的多個線程均會被阻塞
C. 多處理器操作系統中，同一進程的多個線程可以并行執行
D. 操作系統內核可以感知用戶線程的存在

29.【參考答案】?B
【解析】?多對一模型是指將多個用戶級線程映射到一個內核級線程，操作系統無法感知多個用戶級線程的存在，A、D 錯誤。由于多個用戶級線程只對應一個內核級線程，一個線程的阻塞會導致整個進程的阻塞，B 正確。即使在多處理器操作系統中，多對一線程模型下多個線程也無法并發執行，任意時刻最多只能有一個用戶級線程運行，C 錯誤。

30.針對用戶級線程和內核級線程的特點，錯誤的是（ ）。
A. 用戶級線程實現簡單，可以在所有操作系統上實現
B. 用戶級線程的調度由進程管理和控制
C. 即使實現了用戶級線程，內核調度的對象依然是進程
D. 內核級線程的切換由操作系統內核負責，較用戶級線程切換開銷更低

30.【參考答案】?D
【解析】?內核級線程的實現依賴操作系統支持，而用戶級線程切換在所屬進程內完成，無需內核參與，所以內核級線程開銷高于用戶級線程，D 選項錯誤。

31.關于內核級線程優缺點的描述中，錯誤的是（ ）。
A. 相較于進程，線程切換的系統開銷更小
B. 需要操作系統內核支持
C. 線程阻塞會導致該進程的其他線程一同阻塞
D. 在多處理器系統上，同一進程的多個線程可以并行執行

31.【參考答案】?C
【解析】?若一個進程由多個內核級線程構成，其中一個線程阻塞不會致使整個進程阻塞，C 選項正確。

32.關于用戶級線程優缺點的描述中，錯誤的是（ ）。
A. 操作系統的調度單位依舊是進程
B. 線程間切換代價小
C. 不需要操作系統內核支持
D. 在多處理器系統上，同一進程的多個線程可以實現并行執行

32.【參考答案】?D
【解析】?用戶級線程由進程管理，操作系統無法感知，調度單位仍是進程，A 選項正確。相較于進程，線程切換代價小，且用戶級線程無需內核支持，切換代價較內核級線程更小，B、C 正確。用戶級線程的不足在于多個線程無法并行執行，D 錯誤。

33.以下描述中，哪個不是多線程系統的特長（ ）。
A. 利用線程并行地執行矩陣乘法運算
B. Web 服務器利用線程請求 HTTP 服務
C. 鍵盤驅動程序為每一個正在運行的應用配備一個線程，用來響應相應的鍵盤輸入
D. 基于 GUI 的 debugger 用不同線程處理用戶的輸入、計算、跟蹤等操作

33.【參考答案】?C
【解析】?系統中通常只有一個鍵盤，且用戶鍵盤輸入速度較慢，用一個線程響應鍵盤輸入即可。其余選項可借助線程優勢提高效率。

34.用戶級線程的優點不包括（ ）。
A. 線程切換不需要內核態（或系統態）特權
B. 支持不同的應用程序采用不同的調度算法
C. 在不同操作系統上不經修改就可直接運行
D. 同一個進程內的多個線程可以同時調度至多個處理器執行

34.【參考答案】?D
【解析】?用戶級線程切換由用戶空間的線程庫完成，與操作系統內核無關，無需內核態特權，A 正確。用戶級線程中，應用程序可自行決定線程調度方式，B 正確。只要有線程庫，用戶級線程可在任意操作系統運行，無需修改代碼，C 正確。用戶級線程對操作系統不可見，操作系統以進程為單位調度，這些線程不能在多個 CPU 上同時運行，D 錯誤。

35.下面的說法中，正確的是（ ）。
A. 內核級線程和用戶級線程的切換需要內核介入
B. 進程是調度的單位，線程是資源分配的單位
C. 進程總是資源分配的基本單位，線程只擁有少量資源
D. 進程總是調度和資源分配的最小單位，線程無法脫離進程運行

35.【參考答案】?C
【解析】?用戶級線程切換無需操作系統內核介入，A 錯誤。進程是資源分配基本單位，引入線程后，線程是調度最小單位，B 錯誤、C 正確。線程可以是調度最小單位，D 選項前半句錯誤。

36.下列關于進程和線程的敘述，正確的是（ ）。
A. 線程間的地址空間互相隔離
B. 線程間可以共享用戶地址空間
C. 線程是一部分程序段，多個線程構成一個進程
D. 線程間通信主要利用管道、共享存儲、消息傳遞等機制

36.【參考答案】?B
【解析】?同一進程內的線程共享進程的用戶地址空間，A 錯誤。線程是進程的進一步細分單位，并非簡單對代碼段的劃分，C 錯誤。D 選項提及的方法主要用于進程間通信，因線程共享進程地址空間，線程間通信更簡便，同一進程下的多個線程共享該進程地址空間，B 正確。

37.進程之間通信的機制不包括（ ）。
A. 共享存儲區
B. 管道
C. 消息傳遞
D. 訪問對方進程地址空間

37.【參考答案】?D
【解析】?進程的地址空間相互隔離，進程不能直接訪問其他進程的地址空間，D 錯誤。

38.兩個進程協作完成一個任務，不能實現數據傳遞的手段是（ ）。
A. 程序段的全局變量
B. 共享數據結構
C. 共享存儲區
D. 管道機制

38.【參考答案】?A
【解析】?進程地址空間相互隔離，其他進程無法直接訪問某進程的全局變量，A 正確。B、C、D 是進程的通信方式。

39.管道通信是以（ ）進行寫入和讀出的。
A. 消息為單位
B. 自然字符流
C. 文件
D. 報文

39.【參考答案】?B
【解析】?管道是特殊文件，讀寫進程以字符流形式進行讀寫操作，B 正確。

40.下列關于管道 (Pipe) 通信的敘述中，正確的是（ ）。
A. 一個管道可實現雙向數據傳輸
B. 管道的容量僅受磁盤容量大小限制
C. 進程對管道進行讀操作和寫操作都可以被阻塞
D. 一個管道只能有一個讀進程或一個寫進程對其操作

40.【參考答案】?C
【解析】?管道是半雙工的，同一時刻數據只能單向流動，A 錯誤。管道是固定大小的緩沖區（如 4KB） ，在內核中實現，其大小不受磁盤大小影響，B 錯誤。管道空時讀進程阻塞，滿時寫進程阻塞，C 正確。一個管道可有多個讀進程和寫進程，但不能同時進行寫操作，D 錯誤。

41.下面關于進程互斥的論述中不正確的是（ ）。
A. 信號量是一種進程互斥技術
B. 管程是一種進程互斥技術
C. 消息機制可用于實現進程互斥
D. 消息機制不能支持進程間的互斥

41.【參考答案】?D
【解析】?設置值為 1 的信號量可實現進程互斥，A 正確。管程中每次只允許一個進程進入，實現進程互斥，B 正確。消息緩沖通信中，消息隊列是臨界資源，通過執行 P、V 操作實現進程互斥，C 正確，D 錯誤。

2.1.9 真題演練

42.【2010】下列選項中，導致創建新進程的操作是（ ）。
I. 用戶登錄成功
II. 設備分配
III. 啟動程序執行
A. 僅 I 和 II
B. 僅 II 和 III
C. 僅 I 和 III
D. I、II 和 III

42.【參考答案】?C
【解析】?引發新進程創建的情況主要有：用戶登錄、高級調度發生、系統響應用戶程序請求、現有進程派生。用戶登錄成功后，操作系統會為其創建進程，I 正確。設備分配無需創建新進程，設置對應數據結構即可，II 錯誤。啟動程序執行會導致新進程創建，III 正確。

43.【2011】在支持多線程的系統中，進程 P 創建的若干個線程不能共享的是（ ）。
A. 進程 P 的代碼段
B. 進程 P 中打開的文件
C. 進程 P 的全局變量
D. 進程中某線程的棧指針

43.【參考答案】?D
【解析】?線程擁有保證自身獨立運行的必要資源，線程控制塊 TCB 中記錄專屬堆棧指針，用于保存局部變量和返回地址，對其他線程透明、不可共享，D 正確。

44.【2012】下列關于進程和線程的敘述中，正確的是（ ）。
A. 不管系統是否支持線程，進程都是資源分配的基本單位
B. 線程是資源分配的基本單位，進程是調度的基本單位
C. 系統級線程和用戶級線程的切換都需要內核的支持
D. 同一進程中的各個線程擁有各自不同的地址空間

44.【參考答案】?A
【解析】?無論是否引入線程，進程都是資源分配基本單位，線程擁有少量資源，可訪問進程全部資源，A 正確。引入線程前，進程是獨立調度基本單位；引入系統級線程后，線程是獨立調度基本單位，B 錯誤。操作系統內核無法感知用戶級線程，只能支持內核級線程切換，C 錯誤。進程有獨立地址空間，同一進程的線程共享一個地址空間，D 錯誤。

45.【2014】一個進程的讀磁盤操作完成后，操作系統針對該進程必做的是（ ）。
A. 修改進程狀態為就緒態
B. 降低進程優先級
C. 給進程分配用戶內存空間
D. 增加進程時間片大小

45.【參考答案】?A
【解析】?進程向操作系統請求讀磁盤后進入阻塞態，I/O 操作完成后需喚醒進程，將其狀態轉為就緒態。注意題目 “必做” 一詞，進程讀磁盤操作完成后可做之事眾多，如提高進程優先級，但這并非必須。

46.【2014】下列關于管道（Pipe）通信的敘述中，正確的是（ ）。
A. 一個管道可實現雙向數據傳輸
B. 管道的容量僅受磁盤容量大小限制
C. 進程對管道進行讀操作和寫操作都可能被阻塞
D. 一個管道只能有一個讀進程或一個寫進程對其操作

46.【參考答案】?C
【解析】?管道半雙工，實現雙向傳輸需兩個管道，A 錯誤。管道是特殊文件，容量一般為內存一頁，不受磁盤容量限制，B 錯誤。管道可多個讀、寫進程操作，但同一時刻只能一個進程操作，滿時寫進程阻塞，空時讀進程阻塞，C 正確。

47.【2015】下列選項中，會導致進程從執行態變為就緒態的事件是（ ）。
A. 執行 P（wait）操作
B. 申請內存失敗
C. 啟動 I/O 設備
D. 被高優先級進程搶占

47.【參考答案】?D
【解析】?執行 P 操作后只會繼續運行或被阻塞，不會轉為就緒態，A 不符合。申請內存失敗進程進入阻塞態，直到有可用內存，B 不符合。啟動 I/O 設備后進程自動進入阻塞態直到 I/O 任務完成，C 不符合。被高優先級進程搶占后，進程仍具備運行條件，由運行態轉為就緒態，D 符合。

48.【2018】下列選項中，可能導致當前進程 P 阻塞的事件是（ ）。
I. 進程 P 申請臨界資源
II. 進程 P 從磁盤讀數據
III. 系統將 CPU 分配給高優先權的進程
A. 僅 I
B. 僅 II
C. 僅 I、II
D. I、II、III

48.【參考答案】?C
【解析】?進程 P 申請臨界資源，資源充足則繼續執行，不足則進入阻塞態，I 可能。進程 P 從磁盤讀數據屬 I/O 操作，數據到達前進程 P 處于阻塞態，II 可能。系統將 CPU 分配給高優先級進程，進程 P 進入就緒態，III 錯誤。

49.【2019】下列關于線程的描述中，錯誤的是（ ）。
A. 內核級線程的調度由操作系統完成
B. 操作系統為每個用戶級線程建立一個線程控制塊
C. 用戶級線程間的切換比內核級線程間的切換效率高
D. 用戶級線程可以在不支持內核級線程的操作系統上實現

49.【參考答案】?B
【解析】?用戶級線程的管理在用戶空間完成，操作系統內核感知不到其存在，僅調度進程；內核級線程管理在內核空間，需內核支持，A 正確。操作系統無法感知用戶級線程，由進程創建并管理相應線程控制塊，B 錯誤。用戶級線程切換在用戶空間進行，無需內核介入，比內核級線程切換效率高，C 正確。用戶級線程管理依賴進程，引入線程庫即可，無需內核支持，D 正確。

50.【2019】下列選項中，可能將進程喚醒的事件是（ ）。
I. I/O 結束
II. 某進程退出臨界區
III. 當前進程的時間片用完
A. 僅 I
B. 僅 III
C. 僅 I、II
D. I、II、III

50.【參考答案】?C
【解析】?本題考查進程狀態轉換的觸發事件。I/O 結束，若此前有進程因申請 I/O 操作受阻而阻塞，CPU 會喚醒該進程，使其由阻塞態轉為就緒態，I 符合；某進程退出臨界區，若有進程等待臨界區資源，則會被喚醒，II 符合；當前進程時間片用完，轉換為就緒態，不存在喚醒事件，III 不符合。所以選 C。

51.【2020】下列關于父進程與子進程的敘述中，錯誤的是 ( )。
A. 父進程與子進程可以并發執行
B. 父進程與子進程共享虛擬地址空間
C. 父進程與子進程有不同的進程控制塊
D. 父進程與子進程不能同時使用同一臨界資源

51.【參考答案】?B
【解析】?A 選項正確，如父進程創建子進程處理部分數據，父子進程可并發執行。父進程與子進程僅共享代碼段和部分資源，虛擬地址空間各自獨立，不共享，B 錯誤。PCB 是每個進程獨有的數據結構，父子進程不同，擁有不同的進程控制塊，C 正確。判斷父子進程相關性質時，可將子進程視作普通進程，若答案對普通進程成立，對子進程也成立，據此可判斷 A、C、D 正確。

52.【2021】下列操作中，操作系統在創建新進程時，必須完成的是 ( )。
I. 申請空白的進程控制塊
II. 初始化進程控制塊
III. 設置進程狀態為執行態
A. 僅 I
B. 僅 I、II
C. 僅 I、III
D. 僅 II、III

52.【參考答案】?B
【解析】?進程創建過程：①為進程分配進程標識符（PID）和空白 PCB；②分配所需資源；③初始化 PCB 內容；④若順利，設進程狀態為就緒態，放入就緒隊列等待調度；若資源不足，設為阻塞態。申請空白進程控制塊對應①，初始化進程控制塊對應②、③，I、II 正確。進程創建時狀態為就緒態或阻塞態，非執行態，III 錯誤，故選 B。

2.2 處理器調度與上下文切換

????????本節主要圍繞著一個核心展開：調度。上下文切換是進程調度的實現方式，在上一節的進程控制小節已經進行過詳細講述，如有遺忘可以重溫。考生在學習本節知識的過程中，請先嘗試回答下列問題：
(1) 什么是處理器調度？
(2) 為什么要進行處理器調度？

????????本節前半部分（調度的概念、時機、方式實現、調度算法的目標）重點在概念的理解與記憶，后半部分（典型調度算法、甘特圖）重點在理解概念的基礎上運用調度算法分析實際問題。對于重點調度算法，書中設置了多道例題和詳細的解析。

請考生在學習過程中嘗試回答下列問題（題目可以在各個小節中找到答案）：
(1) 什么是搶占式調度算法，什么又是非搶占式調度算法？
(2) 調度算法有沒有最優解決策略，在設計調度算法時，設計者看重哪些要素和指標？
(3) 有哪些典型的調度算法？針對這些調度算法，可不可以說出它們各自的優缺點？

2.2.1 調度的基本概念

????????宏觀上講，調度的發生意味著競爭的產生，資源不足以讓所有需求者同時使用，就必須決定使用的先后次序，這個決定的過程，就是一種調度，可以理解成一種資源分配的行為。在計算機的世界中，也存在著 “珍貴” 的資源，處理器就是其中一種，操作系統需要為處理器實現調度。

1.處理器調度
????????在多道程序設計系統中，允許多個進程或線程的存在，那么不可避免地會遇到多個進程或線程同時競爭處理器的情況。例如，計算機只有一個處理器，且有兩個或更多進程處于就緒態，競爭就出現了，此時只能選擇一個進程上處理器運行。在操作系統中，完成上述選擇工作的部分是 “調度程序（scheduler）”，調度程序使用的選擇算法稱為 “調度算法（scheduling algorithm）”。類似的，線程級別的調度和進程級別的調度有著很大的相似性，許多適用于進程調度的處理方法也同樣適用于線程調度。
????????【提示】請考生區別 “進程調度” 和 “上下文切換”。調度是一種資源分配的行為，包括了調度程序的決策和上下文切換；上下文切換是調度的實現手段，執行調度程序的決策。

2.三種調度層次
????????在多道程序系統中，一個作業從被提交并加入等待隊列開始，到運行結束這一過程，可能會發生三種層次的調度，分別是作業調度、內存調度和進程調度，根據調度發生的層次，依次稱為高級調度，中級調度和低級調度，如圖 2.5 所示。
(1)?高級調度（High Level Scheduling）
????????高級調度，又稱長程調度或作業調度，調度的對象是外存中等待的作業，行為是將作業由外存調度到內存中。當作業調入內存后，操作系統會為該作業創建進程，分配所需資源，執行進程初始化的一系列操作。高級調度能夠限制同時運行的進程數量，避免低級調度開銷過大；也能根據系統當前的 CPU 和 IO 利用率選取合適的計算密集型或 I/O 密集型作業，以免資源競爭過于激烈或某項資源利用率過低。
????????從調度對象可以知道，這種調度主要是針對批處理系統的，分時操作系統和實時操作系統不涉及該層次調度。一個作業只會有一次調入和一次調出，兩次的時間差就是作業執行完畢所花費的時間，所以這種調度的頻率是最低的。

(2)?中級調度（Intermediate Scheduling）
????????中級調度，又稱內存調度，該調度的對象是暫時不能運行的進程，行為是將目標進程的相關數據在內存和外存間移動。在現代操作系統中，這種調度實際上是換頁功能的一部分。如果當前運行中的進程已經占用了大量內存（系統缺頁率過高），那么中級調度就會將部分進程切換為對應的掛起狀態。掛起狀態的進程不參與低級調度，同時頁面置換機制也會傾向于將這些進程使用的內存頁面換入磁盤中，這就緩解了內存緊張的問題，進而提高內存利用率和系統吞吐量。中級調度還會在適當的時機激活此前掛起的進程，使其重新參與調度。這種調度一般發生在系統內存資源不足的情況下，所以發生頻率要根據計算機內存資源多少和當前內存中進程所占資源多少兩個因素共同確定。
????????【拓展】中級調度中涉及進程的就緒掛起態和阻塞掛起態，考生結合圖 2.6 了解即可。當進程從內存被調入外存時，如果調入前進程狀態為就緒態，則調入后進程狀態轉換為就緒掛起態；如果調入前進程狀態為阻塞態，則調入后進程狀態轉換為阻塞掛起態。我們將引入了掛起狀態的模型稱為七狀態模型。

(3)?低級調度（Low Level Scheduling）
????????低級調度，又稱進程調度，調度的對象是進程（或內核級線程），行為是決定將處理器資源先分配給哪個進程。根據選用的進程調度算法，調度程序會決定就緒隊列中的哪個進程應獲得處理器資源，并由分派程序將處理器分配給被選中的進程。進程調度是最基本的一種調度，是發生頻率最高的調度，多道批處理、分時和實時操作系統中，都要實現進程調度。在典型調度算法一節，我們會重點討論這一級別的調度。

三級調度的總結對比如表 2.7 所示。

表 2.7 三級調度對比

調度層次	調度目標	發生頻率	進程狀態的改變
高級調度	將作業由外存調度到內存中，為其創建進程	低	作業→創建態→就緒態
中級調度	將進程數據暫存在輔存中（或恢復到內存中）	中	就緒態→就緒掛起態；阻塞態→阻塞掛起態
低級調度	調度進程輪流使用處理器	高	就緒態→執行態

2.2.2 調度的時機

調度發生于以下幾種情況：
(1) 創建一個新進程之后。當創建完進程后，調度程序需要決定是運行當前進程還是運行其父進程，兩個進程都是處于就緒態的，可以調度其中任意一個進程。
(2) 進程退出后。在一個進程退出后，其占有的資源會被釋放，可以立即供其他進程使用，所以需要執行調度。
(3) 進程時間片用盡。當前進程放棄處理器，調度程序從就緒隊列中選擇進程進行調度。
(4) 可搶占式系統中進程進入就緒隊列。
????????【舉例】可搶占優先級調度算法中，有優先級更高的進程進入就緒隊列時，會發生調度，由優先級最高的進程占有處理器；可搶占式短進程優先調度算法中，有進程進入就緒隊列且該進程要求的運行時間少于目前占有處理器進程的剩余運行時間時，會發生調度。
(5) 阻塞發生時。當一個進程在執行的過程中發生了讓其阻塞的情況，例如 I/O 操作、信號量阻塞等等。為了不浪費資源，可以進行調度，選擇其他的就緒進程運行。
????????【提示】當阻塞發生時，阻塞的原因對調度是有指導意義的。考慮PA?、PB?兩個進程。PA?因為嘗試訪問臨界區而被阻塞，此時PB?正在臨界區內執行，那么調度程序可以選擇先調度PB?，從而更快 “喚醒”PA?來繼續執行任務。
(6) I/O 中斷發生時。當 I/O 中斷發生時，需要進行調度。
????????【舉例】進程PA?因為申請 I/O 操作而被阻塞。當 I/O 設備執行完畢PA?安排的工作，就可以選擇喚醒阻塞的PA?，讓其繼續執行。當然，也可以不進行調度，讓當前占據處理器的進程繼續執行。

????????大多數情況下，調度和進程切換都會立即執行；但下列情況下并非如此，需要等待對應事件結束后才能進行調度和進程切換。
(1) 中斷處理過程中。中斷發生后，需要將待恢復數據（PC、PSW、通用寄存器等）保存在被中斷進程的核心棧中，如果此時發生調度或上下文切換，會導致中斷無法恢復。
(2) 原語執行過程中。原語的執行具有不可中斷的特性。

2.2.3 調度的方式

????????調度的方式分為非搶占式調度和搶占式調度，主要區別在于操作系統能否 “違背” 一個進程的意愿，主動打斷其運行并將處理器資源分配給其他進程。

1.非搶占式調度
在非搶占式調度中，操作系統選擇一個進程并讓其運行，直到其發生阻塞或者完成任務釋放資源為止。在這種調度策略下，進程自愿進入等待狀態或終止時發生調度。
(1)?調度發生的時機：
????????(a) 進程運行完畢，放棄處理器的使用權。
????????(b) 進程發生某種事件而無法繼續運行，放棄處理器使用權。
????????(c) 進程發生阻塞需要等待繼續運行的條件，放棄處理器使用權。
(2)?非搶占式調度的優點：
????????(a) 調度算法設計更簡單，調度成本更低（例如，沒有執行態與就緒態之間的轉換開銷）。
????????(b) 高吞吐的調度策略。
????????【提示】調度行為本身，是一個 “白白” 消耗系統資源的行為，因為調度程序占用處理器資源這一行為對作業的完成是沒有任何貢獻的。搶占式調度會觸發更多次的調度，因而系統整體的吞吐量會變低。

2.搶占式調度
????????搶占式調度算法中，系統可以根據某種調度的原則，暫停一個進程的執行并將處理器資源分給另一個進程。搶占式調度算法使得系統可以實現實時交互，但是更復雜的實現會帶來更大的系統開銷。
(1)?搶占遵循的常用原則：
????????(a)?優先級：優先級高的進程可以搶占優先級低的進程，這個搶占行為可以發生在進程調度的時機上。例如，當有新進程被加入就緒隊列中，如果它擁有比當前運行進程更高的優先級，則可以搶占。
????????(b)?短進程優先：請求處理器時間短的進程，可以搶占請求時間長的進程，同樣的，這個搶占行為發生在可以進程調度的時機。
????????【提示】這種情況下，可以認為進程要求時間的長短決定了進程優先級的高低。
????????(c)?時間片輪轉原則：每個進程依次占用處理器資源，一個進程耗盡當前分配的時間片后，其他就緒進程可以在進程調度發生時進行搶占，被搶占的進程如果未運行完畢，則會轉換為就緒態，進入就緒隊列，等待下一次使用處理器資源。
(2)?搶占式調度的優點：
????????(a) 搶占式調度方法，可以防止一個進程長時間獨占處理器的惡意行為。
????????(b) 與非搶占式調度相比，處理器利用率更高。
????????(c) 搶占式調度的等待時間和響應時間更短，用戶體驗好，有利于實時系統和分時系統。
????????(d) 每次中斷后都需要考慮調度，這使得操作系統更加靈活（對比非搶占式系統需要嚴格執行到一個程序的結束或阻塞）。
????????(e) 操作系統確保所有正在運行的進程的處理器使用率相似，改善了平均響應時間。

2.2.4 調度算法的目標

????????調度算法沒有最優解。不同情況下，人們根據需要選擇不同的調度算法。用戶看重的指標不一樣，因而對調度算法優化的方向也不同。這里針對幾種操作系統介紹其應用環境和典型的調度算法。

1.操作系統的使用場景

????????(1)?批處理系統：常用于商業領域，用來處理存貨清單等周期性作業。這類系統無需與用戶交互，目標是盡快完成作業，因此對調度算法要求平均周轉時間短、系統吞吐率高、處理器利用率高。在這種情況下，非搶占式調度策略和不把響應時間作為首要考慮目標的搶占式調度算法都可考慮。這些調度算法降低調度頻率和每次執行調度算法的開銷，從而提升 CPU 利用率和吞吐量。

????????(2)?分時系統：常用于個人電腦等需頻繁與用戶交互的領域。用戶希望快速得到響應，因此應優先考慮響應時間短的調度算法。

????????(3)?實時系統：如股票交易系統、航天器自動控制系統等。此類系統為保證任務在規定時間內完成，需要特殊設計的調度算法，且搶占式調度算法居多。

2.調度算法的指標
????????以下指標從不同角度評價調度算法，不同調度算法圍繞其中一個或多個指標設計。部分指標關注調度算法性能，可量化；部分難以量化。

(1)?資源利用率：為提高計算機資源利用率，應讓各種資源處于忙碌狀態。處理器資源重要，其利用率計算如公式 2.1：

(2)?周轉時間：指作業（進程）從提交到完成消耗的時間，包括等待高級調度、在就緒隊列等待、運行和 I/O 耗時。周轉時間短，用戶能更快得到結果，操作系統希望平均周轉時間最短，體現更高效率。

(a) 周轉時間T，作業從提交到完成的時間，公式 2.2，tfinish?表示作業完成時間，tarrive?表示作業到達時間。

(b) 平均周轉時間Tˉ，公式 2.3，其中n表示作業總數，Ti?表示作業i的周轉時間。

(c) 帶權周轉時間W，作業周轉時間T與實際運行時間ts?之比，公式 2.4?。

(d) 平均帶權周轉時間Wˉ，綜合考慮每個作業帶權周轉時間，公式 2.5，Ti?表示進程i的帶權周轉時間，ti?表示操作系統為進程i提供的服務時間。

【提示】帶 “平均” 的指標描述調度算法整體性能，其他指標描述特定進程性能。典型調度算法小節會用 FCFS 和 SPF 算法舉例計算。

(3)?吞吐量：指單位時間內完成的作業數，受運行作業長度影響，短作業多則系統吞吐率高。

(4)?響應時間：用戶提交請求開始，直到系統首次對作業做出響應所花費的時間。分時操作系統中是重要衡量指標，低響應時間給用戶更好體驗。

(5)?等待時間：進程在隊列中等待資源的時間，等待時間 = 周轉時間 - 運行時間。對用戶和操作系統而言，平均等待時間長都不利，反映調度算法設計欠佳。

難以量化的指標則包括：

(1)?公平性：相似進程應獲相似服務，如獲得合理處理器時間，避免進程長時間得不到處理器資源（饑餓）。需注意 “相似” 是相對的，有些調度算法為進程定義不同優先級，先調度高優先級進程。

(2)?平衡性：指處理器密集型作業和 I/O 密集型作業的調度平衡，保證計算機各資源盡可能忙碌。

????????【提示】特殊用途操作系統還需考慮特殊指標，如移動設備能耗、實時系統實時性等。

????????綜上，好的調度算法需考慮操作系統應用場景、用戶偏好、系統運行效率等。典型調度算法一節將討論不同算法的目標、優缺點和適用場景。

2.2.5 調度的實現

1.調度的主要任務
進程調度需完成三點任務：

(1) 保存處理器現場信息。上下文切換后其他進程會使用這些資源，需提前將處理器上的程序計數器、通用寄存器等寄存器內容保存在進程控制塊中。

(2) 按進程調度算法確定下一個分配處理器的進程，將其狀態改為執行態，準備分配處理器資源。

(3) 將處理器資源分配給進程，根據進程控制塊信息恢復其運行環境，使其能從上一次中斷的斷點繼續運行。

2.進程調度機制

為實現上述任務，進程調度機制應包含以下三個部分：

(1)?排隊器：進程調度系統中，根據進程不同狀態維護多個進程隊列，如就緒隊列、阻塞隊列。調度時通過這些隊列快速選擇下一個分配處理器資源的進程。排隊器在進程狀態轉為就緒態時，將其插入就緒隊列。

(2)?分派器：根據進程調度程序選擇的進程，從就緒隊列取出并分配處理器資源。

(3)?上下文切換器：分配處理器給新進程時進行上下文切換。操作系統先保存當前使用處理器進程的上下文到進程控制塊，裝入分派程序上下文保證其運行，再取出下一個要分配處理器的進程，從分派程序上下文轉換到該進程上下文，使其開始運行。

3.閑逛進程（Idle Process）
????????閑逛進程無明確工作，用于解決調度特殊情況。就緒隊列無其他進程可調度時，系統調用閑逛進程使用處理器，運行中檢查中斷是否發生。閑逛進程優先級最低，有其他進程進入就緒隊列就會引發處理器調度。
【提示】Unix 操作系統下 PID 為 0 的進程就是閑逛進程。

4.兩種線程的調度

(1)?用戶級線程調度：此方式下，由各個進程管理其包含的線程，操作系統內核感知不到線程存在，調度仍以進程為單位。進程獲得處理器后，利用進程內調度程序調度各個用戶級線程運行。

(2)?內核級線程調度：該方式下，由操作系統管理各個線程并調度，需內核參與，增加額外開銷。好處是線程阻塞不會導致同屬一個進程的其他線程阻塞，且能利用多處理器技術。

2.2.6 CPU 調度算法

????????處理器調度層次有三個層次的調度，以下介紹典型 CPU 調度算法，即三個層次調度中調度算法的具體實現。部分算法適用于多種層次調度，如先來先服務調度算法。

1.先來先服務調度算法（First - come First - serve, FCFS）
????????FCFS 是最簡單樸素的算法，也叫先進先出算法（First In First Out, FIFO），適用于作業調度和進程調度。作業調度時，系統按作業放入外存隊列順序依次調入內存執行；進程調度時，從就緒隊列選最先進入的進程，轉為執行態并分配處理器資源，直到下一個調度時機。該算法雖不會成為操作系統主要調度算法，但一些復雜調度算法（如優先級隊列調度算法）包含其思想。

(1)?優點：邏輯簡單。

(2)?缺點：①效率差；②無法實現人機交互；③未考慮進程間差異，如進程緊急程度；④更偏向處理器密集型進程和長進程。

????????【提示】FCFS 算法偏向長進程和處理器密集型進程原因：長進程排隊并使用處理器直到作業完成或阻塞，使用處理器時間長；I/O 密集型進程遇 I/O 操作會阻塞重新排隊，處理器密集型進程阻塞少，排隊次數少，等待時間也會少。

????????【例 2.1】有P1?，P2?，P3?，P4?，P5?五個進程，其到達時間和執行時間如表 2.8 所示。在單處理器且使用 FCFS 算法的情況下，分析該調度算法的各項指標。分析系統吞吐率時，每個進程對應一個作業，進程完成意味著作業完成。

2.短進程（作業）優先調度算法
????????短進程（作業）優先調度算法，適用于作業調度和進程調度。進程調度時稱短進程優先調度算法（Shortest Process First, SPF），依據就緒隊列中進程預估的處理器使用時間，每次調度選剩余處理器使用時間最短的進程；作業調度時稱短作業優先調度算法（Shortest Job First, SJF） ，按外存隊列中作業要求的執行時間調度，選預估剩余處理器使用時間最短的作業。

(1)?優點：相較于 FCFS，性能有所提升，SPF 的平均等待時間和平均周轉時間最優。

????????【提示】實際上 SPF/SJF 是較為理想的調度算法，但現實中難以實現，主要原因有二：一是進程難以準確預估運行所需時間；二是程序可能謊報運行時間惡意競爭處理器使用權。不過該算法可作為評測其他調度算法優劣的標桿。

(2)?缺點：①算法需進程（作業）預估運行時間，可能出現估算不準或進程 “謊報” 時間的問題；②該算法偏向短進程，若等待調度過程中不斷有短進程創建，長進程可能被無限期擱置，產生饑餓現象；③算法僅依據進程（作業）耗時長短分配處理器，未考慮進程間的差異性。

根據是否可搶占，短進程調度算法分為：

(1)?非搶占式短進程優先調度算法：調度時，選擇當前就緒隊列中要求處理器時間最少的進程分配處理器，該進程運行期間不會被搶占，直至主動放棄處理器。

(2)?搶占式短進程優先調度算法：調度時，選擇當前就緒隊列中要求處理器時間最少的進程分配處理器。若該進程運行時，就緒隊列出現要求時間更短的進程，此進程會被搶占處理器資源，當前運行進程狀態轉為就緒態。

【提示】部分教材對上述兩種情況做更細致區分，SPF 專指非搶占式短進程優先算法，搶占式算法稱最短剩余時間優先調度算法（Shortest Remaining Time, SRT），因為搶占式算法比較的是進程剩余執行時間。分析題目時，要留意調度算法名稱及是否可搶占的描述。

【例 2.2】有P1?，P2?，P3?，P4?，P5?五個進程，其到達時間和執行時間如表 2.8 所示。在單處理器且使用 SPF（非搶占式）算法的情況下，分析該調度算法的各項指標。

【例 2.3】有P1?，P2?，P3?，P4?，P5?五個進程，其到達時間和執行時間如表 2.8 所示。在單處理器且使用 SPF（搶占式）調度算法的情況下，試求這 5 個進程的平均周轉時間。

????????計算過程中，可以利用甘特圖確定各個進程的結束時間（Tfinish?），各個進程的到達時間（Tarrive?）是已知的，利用T=tfinish??tarrive?計算出各個進程的周轉時間；各個進程執行時間（Ts?）是已知的，繼續使用W=ts?T?計算出各個進程的帶權周轉時間；最后按題目要求算出這五個進程的平均帶權周轉時間即可。計算完畢后，考生可以思考這樣一個問題，短進程優先調度算法的兩種形式（可搶占式、不可搶占式）的性能哪種更好，為什么是這樣？

????????關于甘特圖的知識，可以參見甘特圖小節。在分析進程調度算法時，主要考慮處理器個數和調度算法特征。通過上面的例題，請考生注意區分短進程優先調度算法中，可搶占和不可搶占的情況。關于調度相關的知識，難點主要在于計算，考生可以繼續利用表 2.8 數據和其他調度算法去計算 2.2.3 小節中調度算法的各個指標。
3.?優先級調度算法（Priority - scheduling Algorithm, PSA ）
????????優先級調度算法，可用于作業調度、進程調度。前兩種調度算法未考慮進程間差異性，PSA 則為解決該問題而提出。此算法下，作業（進程）優先級由外界賦予，系統依此進行調度。

????????【舉例】對于緊急進程，可設更高優先級，下次進程調度時，系統優先為其分配處理器資源。作業調度時也如此，系統從外存隊列挑選優先級最高作業，裝入內存，創建進程分配資源，設進程狀態為就緒態，放入就緒隊列。

根據是否可搶占，優先級調度算法分為以下兩種：

????????(1)?非搶占式優先級調度算法：每次分配處理器的進程會持續運行至釋放處理器資源，如程序運行完畢或因某些事件退出等，此時調度程序選等待隊列中優先級最高程序分配時間片。

????????(2)?搶占式優先級調度算法：每次選最高優先級進程分配處理器資源，若進程運行中就緒隊列出現更高優先級進程，該進程會搶占處理器資源，當前運行進程狀態由執行態變為就緒態。

在調度程序運行過程中，根據優先級是否動態變化，分為靜態優先級和動態優先級。

(1)?靜態優先級：指各進程優先級在調度程序運行初始就確定，運行期間不變。設計優先級一般依據以下幾點：

????????(a) 系統進程優先級通常高于用戶進程優先級。

????????(b) I/O 密集型進程優先級高于處理器密集型進程。

????????(c) 對資源要求少的進程優先級高于對資源要求多的進程。

????????(d) 用戶自定義優先級。

(2)?動態優先級：指調度程序運行中，各進程優先級動態變化。下面將提到的高響應比優先調度算法，就通過考慮進程等待時間實現動態優先級。

4.高響應比優先調度算法（Highest Response Ratio Next, HRRN ）
????????高響應比優先調度算法，適用于作業調度、進程調度。該算法綜合考慮進程（作業）等待時間和運行時間來調度。根據公式 2.6 確定進程（作業）優先級。可看出，因等待時間變化，優先級也動態變化，進程等待時間增加，優先級變高，更易被調度。不難發現，兩進程要求時間相同時，優先級由等待時間決定，符合 FCFS 算法；兩進程等待時間相同時，短進程優先級更高，類似 SJF，有較好平均等待時間和平均周轉時間，且不會出現饑餓現象，長進程等待足夠時間，優先級會高于短進程。

5.時間片輪轉（Round Robin, RR ）調度算法

????????RR 算法將處理器使用時間劃分成一個個時間片，公平地分給每一個等待處理器資源的就緒進程，時鐘中斷發生時，系統會修改當前進程在時間片內的剩余時間，當一個進程分配的時間片耗盡后，其會重新進入就緒隊列等待下一次分配時間片。該算法可以適用于分時操作系統中的進程調度。系統會將所有就緒進程按照 FCFS 算法來維護就緒隊列，每個時間片結束后操作系統都會結束當前進程，并調度下一個就緒程序運行。在這種策略下，每個進程都能公平地使用處理器資源，也保證了進程的響應時間。

①RR 算法的調度時機：

(1) 一個時間片耗盡，在時鐘中斷發生時，調度程序調度下一個就緒進程上處理器運行，將當前進程放回到就緒隊列末尾。

(2) 一個時間片未耗盡，但進程已完成工作，或因阻塞等原因放棄處理器資源，調度程序會選擇下一個就緒程序進行進程調度。

②時間片大小的確定：
????????RR 算法涉及對于時間片長短的選擇，這對于 RR 算法的性能有著巨大的影響。當時間片很小時，操作系統需要頻繁地進行進程調度，大大增加系統開銷，使整體性能變差。當時間片足夠大，使得每個進程只用一個時間片就可以完成任務時，該算法就退化成了 FCFS 算法。影響時間片大小的主要因素包括響應時間、系統開銷和進程數量等，設計一個合理的時間片大小應該考慮各個進程的實際情況，使得每個進程在一個時間片內，至少可以完成一次交互。

6.多級隊列調度算法
????????多級隊列調度算法，可以適用于進程調度。該算法將就緒隊列設置為多個，根據就緒進程的特點和類型，將其分配在不同的就緒隊列中。針對每個就緒隊列，可以采用不同的調度算法。例如，每個隊列選擇上述調度算法的一種，這種調度算法，不但可以凸顯出各種調度算法的優勢，也能在一定程度上彌補這些算法的缺點。在多處理器系統中，可以利用該調度算法，為每個處理器資源指定一個就緒隊列，這樣既可以根據進程類型和緊急程度等因素為進程分配更合理的就緒隊列，還有利于需要多組線程或進程協作完成任務的情況，即將這些線程或進程分配到不同的就緒隊列中，使得它們可以同時獲得處理器資源。

7.多級反饋隊列（Multilevel Feedback Queue）調度算法
多級反饋隊列調度算法，可以適用于進程調度，這種調度算法能夠較好地滿足各類進程對于處理器資源的需求，是公認較好的一種調度算法。

①算法實現過程：

(1) 該算法將就緒隊列分成多個，為這些隊列依次分配遞減等級的優先級。第一個就緒隊列擁有最高的優先級，第二個就緒隊列的優先級次于第一個就緒隊列，以此類推。在每個就緒隊列中，根據該隊列的優先級，劃分大小不同的時間片，高優先級的隊列中，時間片小，低優先級的隊列中，時間片大。
????????【提示】有時間片并不意味著是時間片輪轉算法，因為進程在運行完一個時間片的時間后，會被放入下一級就緒隊列而不是當前隊列中。關于時間片大小的確定，一般來說，第一級隊列的時間片大小能夠滿足大多數進程人機交互所需要的時間即可，后續隊列的時間片可以按照每級增加一倍的規律增長。

(2) 當一個作業的進程被創建并分配資源后，先將其加入第一個隊列的末尾，依據 FCFS 算法等待分配時間片。如果該進程被調度執行后在一個時間片內未完成其任務，將會被降級到下一個隊列，重新進行上述過程，直到進程被降級到最低優先級的隊列中。此時進程不會繼續降級，將在該就緒隊列中遵循時間片輪轉調度算法等待調度。

(3) 按照隊列的優先級進行調度。等級高的就緒隊列中的進程會被優先調度，對于第 i 級隊列，只有當 1 到 i - 1 隊列中不存在就緒進程，才可以調度該隊列中進程。如果當前使用處理器資源的進程來自第 i 級隊列，而此時第一級隊列中進入了新的就緒進程，那么會立刻進行搶占式進程調度，并將此時正在運行的程序放回 i 級隊列隊尾。

②多級反饋隊列調度算法如何滿足各類用戶：

(1) 終端型用戶：多為交互型作業，所需時間較少，大多數在第一級隊列中就能快速完成，而第一級隊列具有最高的優先級，這樣使得任務的周轉時間短。

(2) 短批處理作業用戶：作業長度稍長，在前幾級隊列中就可以完成，周轉時間較短。

(3) 長批處理作業用戶：作業長度長，但是也會在前幾級隊列中等待并獲得時間片，執行部分程序，不會長時間得不到執行。

8.調度算法對比

????????????????????????????????????????????????????????表2.13 調度算法對比2

調度算法	特點
先來先服務	優點：邏輯簡單 缺點：完全不考慮進程特點 利于：長進程、處理器密集型進程 不利于：短進程、I/O 密集型進程
短進程優先	缺點：進程預計運行時間難以計算 優點：擁有最優的平均等待時間和平均周轉時間 利于：短進程 不利于：長進程
優先級	通過設置進程優先級以區分進程特點 利于：高優先級進程 不利于：低優先級進程
高響應比優先	優先級動態變化，利于短進程但可以消除饑餓 利于：短進程 不利于：長進程
時間片輪轉	公平的將處理器分配給每個進程
多級反饋隊列	能較好滿足各類進程對處理器的需求 長進程、I/O 密集型進程隨著運行會逐步下沉到低優先級隊列

2.2.7 甘特圖

????????甘特圖（Gantt chart），由亨利?勞倫斯?甘特（Henry Laurence Gantt）提出，用于顯示和管理項目的進度。本節我們學習甘特圖以輔助解題，甘特圖在分析進程調度、多進程并發執行等場景時，有著直觀清晰的優點。
在設計一個甘特圖時，要通過進程列表（并發執行的進程）和時間刻度表示出特定行為（輸入、運行等）的順序與持續時間。一個典型的甘特圖中，橫軸表示時間，一個塊表示一個單位的時間；縱軸表示進程，可以清晰地看到某個進程開始執行和結束的時間；線條的不同花紋表示不同的任務，這些任務的執行需要計算機硬件的支持。分析場景時，可以將描述中資源、進程、任務三個要素抽取出來，對應甘特圖的三個維度。
????????【提示】下面提到的 “單資源” 是指同類型的資源只有一個。例如現有一個處理器和一個輸出設備，即是 “單資源” 的情況，在單資源情況下，使用每種資源時都要保證不能有重疊。
甘特圖有如下三種場景：

①場景 A：多進程單任務單資源

????????(1) 資源：一個處理器，運行先來先服務調度算法（FCFS）。

????????(2) 進程：有三個進程 {A,B,C}，分別在 0 時刻、5 時刻和 6 時刻進入就緒隊列。

????????(3) 任務：每個進程均預計使用處理器運行 4 個時間單位。

????????(4) 甘特圖：如2.13所示。

②場景 B：多進程多任務單資源

????????(1) 資源：一個處理器，運行先來先服務調度算法（FCFS）；一個輸出設備。

????????(2) 進程：有兩個進程 {A,B}，分別在 0 時刻、3 時刻進入就緒隊列。

????????(3) 任務：每個進程均預計使用處理器運行 4 個單位時間，之后使用輸出器 2 個單位時間進行輸出。

????????(4) 甘特圖：如圖 2.14 所示。

③場景 C：多進程多任務多資源

????????(1) 資源：兩個處理器，均運行先來先服務調度算法（FCFS）；一個輸出設備。

????????(2) 進程：有兩個進程 {A,B}，分別在 0 時刻、3 時刻進入就緒隊列。

????????(3) 任務：每個進程均預計使用處理器運行 4 個單位時間，之后使用輸出器 2 個單位時間進行輸出。

????????(4) 甘特圖：如圖 2.15 所示。

【例 2.4】某單 CPU 系統中有輸入和輸出設備各 1 臺，現有 3 個并發執行的作業，每個作業的輸入、計算和輸出時間如下表所示，則執行完 3 個作業需要的時間最少是 ( )。

A. 15ms????????B. 17ms????????C. 22ms????????D. 27ms

解：選 B。甘特圖如圖 2.16、2.17、2.18 所示，多種執行方式均可以在 17ms 內執行完畢。

2.2.8 多處理機調度

????????【提示】此部分內容是 2025 考研 408 大綱中新增的內容，以概念的了解記憶為主。其實真的不難，耐心看一遍，應該就能理解。

????????多處理機系統 MPS（MultiProcessor System）指由多個處理機（CPU）通過高速總線或通信線路等互連技術，共享輸入 / 輸出設備、主存儲器等資源，在統一的操作系統控制下，協同工作的計算機系統。

????????多處理系統 MPS 具有增加系統吞吐量、節省成本（達到相同的處理能力，n 個處理機比 n 臺獨立計算機更節省成本）、提高系統可靠性（某個 CPU 故障，系統依然可以正常運行）等優點。

多處理機系統 MPS 的類型

(1) 根據系統中處理機的結構和功能，將多處理系統 MPS 分為對稱和非對稱 2 種類型：

????????①對稱多處理機系統 SMP（Symmetric MultiProcessor System）：系統中所用 CPU 在硬件結構和功能上都是相同的，各 CPU 之間地位平等，不存在主從之分。目前絕大部分的 MPS 屬于 SMPS。

????????②非對稱多處理機系統 ASMP（Asymmetric MultiProcessor System）：在系統中存在多種硬件結構和功能上不同的 CPU，CPU 之間存在主從之分。

(2) 根據系統中各處理機之間是否相互獨立，將多處理系統 MPS 分為緊密耦合和松弛耦合 2 種類型：

????????①緊密耦合 MPS：由操作系統集中統一管理系統中的資源，多處理機通過高速總線互連。

????????②松弛耦合 MPS：各處理機（或計算機）之間相對獨立，通過通信線路互連。

2.多處理機系統的進程調度
????????多處理機系統中的進程調度與系統結構相關。對于對稱多處理機系統，因為 CPU 都是相同的，進程被調到任一處理機上均可。對于非對稱多處理機系統，要選擇合適的 CPU 運行進程。

3.多處理機系統的進程分配方式

(1) 對稱多處理機系統（SMP）中的進程分配方式
????????在 SMP 系統中，將所有處理機組織成一個處理機池，選擇處理機池中的處理機分配給進程，有以下 2 種分配方式：

????????①靜態分配：一個進程在其生命周期內被固定分配到同一個處理機上運行。這種方式的優點是系統開銷小，缺點是各處理機之間可能會忙閑不均。

????????②動態分配：一個進程在其生命周期內被隨機分配到處于空閑的處理機上運行。這種方式解決了各處理機間忙閑不均的問題。并且，對于緊密耦合 MPS 不會增加開銷，而對于松弛耦合 MPS 會增加開銷。

(2) 非對稱多處理機系統中的進程分配方式
非對稱 MPS 大多采用主從式結構，由主機負責進程調度，從機負責運行用戶程序。

4.多處理機系統的進程 / 線程調度方式

????????(1) 自調度方式：處理機在空閑時，從公共的就緒隊列（整個系統中只設置一個）中選擇進程 / 線程來運行。可沿用單處理機環境中的調度算法（例如：先來先服務 FCFS）。其缺點是存在系統瓶頸、效率低、線程切換頻繁等問題。

????????(2) 成組調度方式：將同屬于一個進程的一組線程同時分配到一組處理機上運行。為了解決自調度方式中線程切換頻繁的問題而提出的，其調度性能比自調度方式更好。成組調度中處理機時間的分配有以下 2 種方式：

????????①給所有進程（應用程序）平均分配處理機時間：對于含有 n 個處理機和 m 個進程（應用程序）的系統，每個進程最多有 n 個線程，則分配給每個進程去占用 n 個處理機的時間最多為m1?。

????????②給所有線程平均分配處理機時間，比按進程分配更高效。

(3) 專用處理機分配方式：進程在其生命周期內被分配一組專用的處理機。

(4) 動態調度：進程的線程數量在運行期間可以動態變化。操作系統負責給作業分配處理機，作業再負責將得到的處理機分配給對應的任務線程。缺點是調度開銷大。

2.2.9 習題精編

1.某單處理器系統支持多道程序設計，若此刻有多個就緒態進程，則下列敘述中錯誤的是（ ）
A. 進程調度的目標是讓進程輪流使用處理器
B. 當一個進程運行結束后，會調度下一個就緒進程運行
C. 上下文切換是進程調度的實現手段
D. 處于臨界區的進程在退出臨界區前，無法被調度

1.【參考答案】D
【解析】當一個臨界區內有進程，則其他想要進入該臨界區的進程會被阻塞，不進入該臨界區的進程依然可以被調度；一個進程退出臨界區前，可以發生調度，只是調度對象不能是要進入該臨界區的進程，故 D 選項錯誤。

2.下列各級調度中，發生頻率最高的是（ ）。
A. 低級調度
B. 中級調度
C. 高級調度
D. 三者發生頻率相近

2.【參考答案】A
【解析】低級調度，又稱進程調度，該調度的對象是進程（或內核級線程），行為是決定將處理器資源分配給哪個進程。根據選用的進程調度算法，調度程序會決定就緒隊列中的哪個進程應獲得處理器資源，并由分派程序將處理器分配給被選中的進程。進程調度是最基本的一種調度，是發生頻率最高的調度，所以 A 選項正確。

3.下列場合中，一定會發生調度的時機有（ ）。
I. 新進程被創建時
II. 進程運行完畢
III. 可搶占式系統中高優先級進程進入就緒隊列
IV. 時間片耗盡
V. 進程運行中發生錯誤
A. I、II、III 和 IV
B. II、III、IV 和 V
C. I、III、IV 和 V
D. 全部都是

3.【參考答案】B
【解析】一個新進程被創建，可以是調度的時機，但并不是一定，I 錯誤。II、III、IV、V 四種情況，都是運行的進程主動或被動放棄處理器，需要調度下一個就緒進程。

4.在非剝奪調度方式下，必定會引起進程調度的情況是（ ）。
A. 一個新進程被創建
B. 一個進程從執行態進入阻塞態
C. 一個進程從阻塞態進入就緒態
D. 一個進程從就緒態進入阻塞態

4.【參考答案】B
【解析】題目條件要求在非剝奪調度方式下，所以 A、C 不正確；倘如在剝奪調度方式下，A、C 選項陳述的時機是有可能發生調度的。一個進程阻塞后，必須要調度進程，所以 B 選項正確；D 選項的情況不會發生，就緒態進程無法直接進入阻塞態。

5.下列調度算法中，一定是搶占式調度的是（ ）。
A. 時間片輪轉
B. 先來先服務
C. 優先級
D. 短進程優先

5.【參考答案】A
【解析】先來先服務一定是非搶占式，時間片輪轉一定是搶占式，優先級和短進程優先既可以是非搶占的，也可以是搶占的。

6.下列調度算法中，既可以設計成搶占式調度，也可以設計成非搶占式調度的是（ ）。
A. 短進程優先
B. 優先級
C. 高響應比優先
D. A、B、C 均可

6.【參考答案】D
【解析】A、B、C 均可設計成搶占式和非搶占式調度算法，高響應比優先和短進程優先都可以理解成優先級的一種實現方式。考生可以思考一下各種調度算法設計成可搶占式和非搶占式的區別，再翻看知識點解析檢查。

7.以下哪些指標是調度算法設計時可以考慮的（ ）。
I. 公平性
II. 資源利用率
III. 互斥性
IV. 平均周轉時間
A. I、II
B. I、II、IV
C. I、III、IV
D. 全部都是

7.【參考答案】B
【解析】互斥性不是調度算法考慮的，III 排除；調度算法的目標是更好地選取下一個運行的進程，一般考慮公平性、資源利用率、平衡性、周轉時間、系統吞吐率、響應時間和等待時間等因素，所以選擇包含 I、II、IV 的 B 選項。

8.下列關于時間片輪轉調度算法的敘述，錯誤的是（ ）。
A. 考慮了調度的公平性
B. 能夠及時對多個用戶做出響應
C. 系統的平均周轉時間是最優的
D. 每次時間片耗盡時，會進行調度

8.【參考答案】C
【解析】系統平均周轉時間最優的調度算法是短進程優先調度算法。A、B、D 三個選項都是時間片輪轉調度算法的特點。

9.下面關于調度算法的敘述中，不正確的是（ ）。
A. 可以提高處理器利用率
B. 可以提高設備利用率
C. 進程調度發生地越頻繁，系統吞吐量越高
D. 調度算法需要對多個指標進行折中

9.【參考答案】C
【解析】進程調度程序本身也是需要占用處理器資源的，如果調度程序運行得太過頻繁，反而不利于增加系統吞吐量，可以理解為調度程序搶占了本該屬于進程運行的計算機資源，所以 C 選項錯誤。

10.一個單處理器單道操作系統上，有 4 個作業，到達時間和執行時間如下表所示，調度算法選用先來先服務。求系統平均周轉時間（ ）。

A. 2
B. 3.5
C. 4.5
D. 8

10.【參考答案】C
【解析】平均周轉時間為每個進程周轉時間的平均值。先求出各個進程的周轉時間，再求平均值即可。本題答案為(2+4+5+7)/4=4.5。

11.關于進程優先級的論述中，錯誤的是（ ）。
A. 系統進程的優先級一般高于用戶進程
B. I/O 密集型進程優先級高于處理器密集型進程
C. 對資源要求少的進程優先級一般高于對資源要求多的進程
D. 優先級可以由用戶自定義，但是只能是靜態的

11.【參考答案】D
【解析】優先級分為靜態優先級和動態優先級，用戶可以自定義各個進程的靜態優先級，也可以定義動態優先級的計算公式：例如高響應比優先調度算法，就是一種動態優先級調度算法，響應比計算公式可以由用戶定義，故 D 選項錯誤。A、B、C 選項都是確定優先級時常用的原則。

12.一個好的 CPU 調度算法應當可以（ ）。
A. 降低系統吞吐率
B. 提高系統 CPU 利用率
C. 提高進程周轉時間
D. 提高進程等待時間

12.【參考答案】B
【解析】好的 CPU 調度算法可以提高 CPU 的利用率，B 正確。CPU 利用率提高，相同時間會完成更多的任務，系統吞吐量增加，進程周轉時間降低，等待時間降低，A、C、D 錯誤。

13.下列選項中，不應該提高進程優先級的場合是（ ）。
A. 進程發生 “饑餓” 現象
B. 用戶需要一個進程在規定時間內完成
C. 進程等待的 I/O 操作完成，進入就緒隊列
D. 進程時間片耗盡

13.【參考答案】D
【解析】進程發生饑餓時，應當增加其優先級，使其有機會使用處理器；當用戶需要一個進程在規定時間完成時，也應該給予其高優先級以讓該進程可以立即運行；I/O 操作完成后，可以適當提高進程優先級，A、B、C 均是提高優先級的場合。當時間片耗盡后，顯然不應該提高其優先級，否則該進程可能再次使用處理器，導致其他進程無法得到處理器資源。一般來說，D 選項的情況下應該降低優先級。

14.某服務器系統中，一個低優先級進程被提交后等待了 6 年尚未被運行，這一現象在操作系統的 CPU 調度中被稱為（？），（？）調度算法可以避免這一問題。以上問題的正確選項是（ ）。
I. 同步
II. 饑餓
III. 并行
IV. 死鎖
I. 靜態優先級
II. 最短剩余時間優先
III. 短進程優先
IV. 高響應比優先
A. I、IV
B. II、I
C. III、IV
D. II、IV

14.【參考答案】D
【解析】進程長時間得不到處理器資源被稱為饑餓，高響應比優先調度算法考慮了進程的等待時間，故一個進程經過長時間的等待，優先級一定會變得很高，從而被分配處理器資源。

15.高響應比優先的進程調度算法綜合考慮了進程的等待時間和計算時間，響應比的定義是（ ）。
A. 進程周轉時間與等待時間之比
B. 進程周轉時間與計算時間之比
C. 進程等待時間與計算時間之比
D. 進程計算時間與等待時間之比

15.【參考答案】B
【解析】響應比=1+S/T（S：等待時間；T：運行時間）。

16.某系統內存中，共有五個進程，該系統的就緒隊列、阻塞隊列中最多能同時存在的 PCB 數量分別是（ ）。
A. 5 個、5 個
B. 5 個、4 個
C. 4 個、5 個
D. 4 個、1 個

16.【參考答案】C
【解析】就緒隊列中最多能有 4 個就緒進程，且另一個進程一定在運行態。阻塞隊列中可以有 5 個進程。

17.下列調度算法中，有利于處理器密集型進程，不利于 I/O 密集型進程的是（ ）。
A. 先來先服務
B. 時間片輪轉
C. 多級反饋隊列
D. 優先級

17.【參考答案】A
【解析】先來先服務算法利于處理器密集型不利于 I/O 密集型，因為處理器密集型進程可以長時間占用處理器，I/O 密集型進程一旦進行 I/O 操作，就需要重新進入就緒隊列排隊，所以選擇 A 選項。

18.下列關于調度算法的敘述中，錯誤的是（ ）。
A. 優先級調度算法偏向于用戶的緊急作業
B. 短進程優先調度算法不利于長作業
C. 時間片輪轉算法利于人機交互
D. 多級反饋隊列調度算法偏向長作業

18.【參考答案】D
【解析】用戶的緊急作業會被賦予更高的優先級，A 選項正確；短進程優先調度算法利于短進程，長進程則可能長時間得不到處理器，B 選項正確；時間片輪轉算法利于人機交互，因為響應時間很短，C 選項正確。多級反饋隊列調度算法可以很好的滿足各種作業，D 選項錯誤。

19.現在有三個同時到達的作業J1?，J2?和J3?，它們的執行時間分別是T1?，T2?，T3?，且T1?<T2?<T3?。系統按單道方式運行且采用短作業優先調度算法，則平均周轉時間是（ ）。
A.?T1?+T2?+T3?
B.?(T1?+T2?+T3?)/3
C.?(T1?+2T2?+3T3?)/3
D.?(3T1?+2T2?+T3?)/3

19.【參考答案】D
【解析】執行順序是J1??J2??J3?。J1?的周轉時間是T1?，J2?的周轉時間是T1?+T2?，J3?的周轉時間是T1?+T2?+T3?。平均周轉時間計算得到 D 選項。

20.某單處理器單道操作系統中，使用優先級調度算法，有三個進程在 0 時刻到達，則平均周轉時間為（ ）。

A.?t1?+t2?+t3?
B.?(t1?+t2?+t3?)/3
C.?(3t1?+2t2?+t3?)/3
D.?(t1?+2t2?+3t3?)/3

20.【參考答案】D
【解析】執行順序是作業 3 - 作業 2 - 作業 1。作業 3 的響應時間是t3?，作業二的響應時間是t3?+t2?，作業三的響應時間是t3?+t2?+t1?。平均周轉時間計算得到 D 選項。

21.時間片輪轉調度算法中，時間片的大小會影響算法效率。當時間片過小時，算法效率（ ）；當時間片過大時，該算法轉換為（ ）調度算法。
A. 不變；先來先服務
B. 下降；優先級
C. 提高；高響應比優先
D. 其他

21.【參考答案】B、A
【解析】若時間片過小，則調度程序運行頻率會很高，因此占用大量的處理器資源，導致效率下降。若時間片大到每一個進程都能在一個時間片內運行完畢，則會變成先來先服務調度算法。

22.下列各個調度算法中，能夠較好滿足各類進程的是（ ）。
A. 多級反饋隊列調度算法
B. 短進程優先調度算法
C. 最短剩余時間優先調度算法
D. 先來先服務調度算法

22.【參考答案】A
【解析】B、C 調度算法對長進程不利，D 調度算法對 I/O 密集型進程不利，多級反饋隊列調度算法可以較好地滿足各類進程。

23.某單處理器單道操作系統中，0 時刻 5 個批處理作業同時到達。分別使用短作業優先調度算法和先來先服務調度算法（按 3 - 1 - 2 - 5 - 4 順序調度）時，平均周轉時間分別為（ ）。

A. 8.4、12.4
B. 8.4、12.6
C. 8.6、12.4
D. 8.6、12.6

23.【參考答案】B
【解析】使用短作業優先調度算法時，平均周轉時間計算表達式為(5×1+4×2+3×4+2×5+1×7)/5=42/5=8.4。使用先來先服務調度算法時，平均周轉時間計算表達式為(5×4+4×7+3×1+2×5+1×2)/5=63/5=12.6。

24.下列關于時間片輪轉算法的敘述中，不正確的是（ ）。
A. 在時間片輪轉算法中，系統將 CPU 的處理時間劃分成一個個時間片
B. 就緒隊列中的各個進程輪流在 CPU 上運行，每次運行一個時間片
C. 時間片結束時，運行進程自動讓出 CPU 并進入阻塞隊列
D. 如果時間片長度很小，則調度程序搶占 CPU 的次數頻繁，增加了系統開銷

24.【參考答案】C
【解析】時間片耗盡后，進程變為就緒態，進入就緒隊列，C 選項錯誤。

25.多級反饋（Feed Back）進程調度算法不具備的特性是（ ）。
A. 資源利用率高
B. 響應速度快
C. 系統開銷小
D. 并行度高

25.【參考答案】C
【解析】多級反饋隊列中的各級隊列可以使用不同的調度算法，從而較好地滿足各個進程。C 選項不正確，因為多級反饋隊列調度算法相較其他算法，實現上較為復雜，開銷也會變大。

26.以下進程使用最短剩余時間調度算法進行調度，進程周轉時間之和為（ ）。

A. 25
B. 26
C. 27
D. 28

26.【參考答案】C
【解析】注意此算法是可搶占算法，周轉時間總和為4+1+8+12+2=27。
P1?：0 時刻到達。0 - 1 時刻運行，1 時刻被搶占，2 - 4 時刻運行，周轉時間為 4。
P2?：1 時刻到達。1 - 2 時刻運行，周轉時間為 1。
P3?：2 時刻到達。6 - 10 時刻運行，周轉時間為 8。
P4?：3 時刻到達。10 - 15 時刻運行，周轉時間為 12。
P5?：4 時刻到達。4 - 6 時刻運行，周轉時間為 2。

27.設有 4 個作業同時到達，若采用最短作業優先調度算法，則作業的平均周轉時間為（ ）。

A. 1.5h
B. 10.5h
C. 8.75h
D. 10.25h

27.【參考答案】C
【解析】執行順序是作業 1 - 作業 4 - 作業 2 - 作業 3。不涉及搶占的調度算法較為簡單，確定執行順序后，每個進程的周轉時間就等于運行時間 + 該進程之前的所有進程運行時間之和。平均周轉時間為(4×2+3×3+2×5+1×8)/4=35/4=8.75。

28.在單道程序環境中，有 4 個作業 A、B、C、D，它們的提交時間與預計運行時間如下表。如果按短作業優先算法調度，它們的運行順序為（ ）。

A. A - B - C - D
B. B - C - D - A
C. B - A - D - C
D. A - B - D - C

28.【參考答案】D
【解析】A 作業最先到達且就緒隊列中無其他作業，故 A 作業先運行。當 A 作業運行結束后，B、C、D 均到達，再按照執行時間決定順序為 B - D - C。

29.某單處理器單道操作系統中，使用多級反饋隊列調度算法，隊列 1、2、3 優先級遞減，具體見下表。則這 4 個作業的周轉時間之和為（ ）。

A. 25
B. 27
C. 28
D. 29

29.【參考答案】A
【解析】多級反饋隊列調度算法涉及搶占和進程在各級隊列間的移動。
周轉時間之和為10+1+2+12=25。
J1?：0 時刻到達。0 - 2 時刻運行，2 時刻進入 2 級隊列，7 - 10 時刻運行，周轉時間為 10。
J2?：2 時刻到達。2 - 3 時刻運行，周轉時間為 1。
J3?：3 時刻到達。3 - 5 時刻運行，周轉時間為 2。
J4?：4 時刻到達。5 - 7 時刻運行，7 時刻進入 2 級隊列；10 - 14 時刻運行，14 時刻進入 3 級隊列；14 - 16 時刻運行。周轉時間為 12。

30.一個動態優先級調度算法（優先數大的優先級低，優先級相同時選序號小的進行調度），根據等待時間和運行時間對優先數進行動態變化，算法如下：
① 處于就緒隊列中的進程的優先數p根據等待時間t（單位秒）進行變化，p=p?t；
② 處于運行狀態的進程的優先數p根據運行時間t（單位秒）進行變化，p=p+2×t；
③ 優先數p每隔 1 秒重新計算；
④ 采用搶占式調度策略。
根據下表給出的 5 個進程的到達時間和執行時間，回答下面的問題。（時間單位：秒）

(1) 畫出 5 個進程執行的順序圖。
(2) 根據以上的調度算法，分別計算出每個進程的周轉時間和響應時間。

2.2.10 真題演練

31.【2009】下列進程調度算法中，綜合考慮進程等待時間和執行時間的是（ ）。
A. 時間片輪轉調度算法
B. 短進程優先調度算法
C. 先來先服務調度算法
D. 高響應比優先調度算法

31.【參考答案】D
【解析】時間片輪轉調度算法將處理機時間劃分成固定長度的時間片，考慮了進程的執行時間而未考慮等待時間，A 不符合；短進程優先調度算法僅考慮了進程執行時間，B 不符合；先來先服務調度算法僅考慮了調度的公平性，C 不符合；高響應比調度算法通過等待時間和執行時間動態調整進程的優先級，D 符合。

32.【2010】下列選項中，降低進程優先級的合理時機是（ ）。
A. 進程的時間片用完
B. 進程剛完成 I/O，進入就緒隊列
C. 進程長期處于就緒隊列中
D. 進程從就緒態轉為運行態

32.【參考答案】A
【解析】在進程的時間片用完后，進程由運行態變為就緒態，重新等待分配處理機，此時降低其優先級也可保證其他就緒進程使用處理機，A 選項正確；進程完成 I/O 后進入就緒隊列等待使用處理機，應該提高其優先級，B 選項錯誤；進程長期處于就緒隊列中說明一直未得到處理機使用權，應該提高其優先級以防止發生饑餓現象，C 選項錯誤；在實行搶占式調度算法的機器上，在進程剛從就緒態轉化為運行態時，若降低優先級，可能會導致進程剛進入運行態就被搶占，降低了處理器效率，D 選項錯誤。
降低進程優先級的合理時機還有：在進程運行結束后應該降低該進程優先級，否則，剛運行結束的進程因為高優先級，會再次搶占處理器。

33.【2011】下列選項中，滿足短任務優先且不會發生饑餓現象的調度算法是（ ）。
A. 先來先服務
B. 高響應比優先
C. 時間片輪轉
D. 非搶占式短任務優先

33.【參考答案】B
【解析】A 和 C 沒有考慮任務的長短，錯誤。D 考慮了任務的長短，但短進程優先有導致饑餓現象的風險，倘若就緒隊列中一直有短任務進程進入，則長任務進程會一直等待。高響應比調度算法通過等待時間和執行時間動態調整進程的優先級：優先級等待時間要求服務時間要求服務時間。短任務計算優先級時因為分母更小，會比長任務優先，但長進程只要等待的時間足夠長，一定會比短任務優先級高，故不會發生饑餓。

34.【2012】一個多道批處理系統中僅有P1?和P2?兩個作業，P2?比P1?晚 5ms 到達，它們的計算和 I/O 操作順序如下：
P1?：計算 60ms，I/O 80ms，計算 20ms
P2?：計算 120ms，I/O 40ms，計算 40ms
若不考慮調度和切換時間，則完成兩個作業需要的時間最少是（ ）。
A. 240ms
B. 260ms
C. 340ms
D. 360ms

34.【參考答案】B
【解析】P1?先于P2?到達，則P1?先執行；因為是多道批處理系統，P2?到達后可以和P1?并發執行。使用甘特圖分析，結果如下圖所示。

?

35.【2013】某系統正在執行三個進程P1?、P2?和P3?，各進程的計算（CPU）時間和 I/O 時間比例如下表所示。為提高系統資源利用率，合理的進程優先級設置應為（ ）。

A.?P1?>P2?>P3?
B.?P3?>P2?>P1?
C.?P2?>P1?=P3?
D.?P1?>P2?=P3?

35.【參考答案】B
【解析】解題時需要思考如何提高系統資源利用率 — 盡可能保證處理器和 I/O 設備并行工作。
優先執行 I/O 時間占比高的進程P3?，在P3?阻塞時，其他進程可以占有處理器，從而實現系統資源的并發。如果考生感覺這樣理解不直觀，可以思考如果只存在P1?和P3?進程，優先級應該如何設置。顯然，先執行P3?可以實現更高的系統資源利用率。優先級設計原則總結如表 2.14 所示。

優先級設計	????????????????????????????????????????????????????????設計原則
靜態優先級	1. 系統進程高于用戶進程 2. I/O 密集型高于處理器密集型 3. 資源要求低的進程高于資源要求高的進程 4. 用戶自定義需求：如要求某任務準時完成，會設置高優先級
動態優先級	高響應比優先調度算法：等待時間越長，運行時間越短，優先級越高 多級反饋隊列調度算法：進入就緒隊列次數越多，優先級越低

36.【2014】下列調度算法中，不可能導致饑餓現象的是（ ）。
A. 時間片輪轉
B. 靜態優先級調度
C. 非搶占式短作業優先
D. 搶占式短作業優先

36.【參考答案】A
【解析】搶占式和非搶占式短作業優先調度算法中，若不斷有短進程進入就緒隊列，長進程就可能會發生饑餓現象。靜態優先級調度中，如果不斷有高優先級進程進入就緒隊列，低優先級進程可能會發生饑餓。時間片輪轉算法保證了各個進程公平使用處理機，不會發生饑餓。

37.【2016】某單 CPU 系統中有輸入和輸出設備各 1 臺，現有 3 個并發執行的作業，每個作業的輸入、計算和輸出時間均分別為 2ms、3ms 和 4ms，且都按輸入、計算和輸出的順序執行，則執行完 3 個作業需要的時間最少是（ ）。
A. 15ms
B. 17ms
C. 22ms
D. 27ms

37.【參考答案】B
【解析】利用甘特圖解題，無論作業的執行順序如何，都能在 17ms 執行完畢，如圖 2.19 所示。

38.【2017】假設 4 個作業到達系統的時刻和運行時間如下表所示。系統在t=2時開始作業調度。若分別采用先來先服務和短作業優先調度算法，則選中的作業分別是（ ）。

A.?J2?、J3?
B.?J1?、J4?
C.?J2?、J4?
D.?J1?、J3

?38.【參考答案】D
【解析】根據題目可知，進行作業調度時，可以調度的作業有J1?、J2?、J3?。采用先來先服務算法時，會選取J1?，因為J1?最先到達；采用最短作業優先調度算法時，選取J3?，因為J3?的運行時間最短。

39.【2018】某系統采用基于優先權的非搶占式進程調度策略，完成一次進程調度和進程切換的系統時間開銷為 1μs。在T時刻就緒隊列中有 3 個進程P1?、P2?和P3?。其在就緒隊列中的等待時間、需要的 CPU 時間和優先權見下表。若優先權值大的進程優先獲得 CPU，從T時刻起系統開始進程調度，則系統的平均周轉時間為（ ）。

A. 54μs
B. 73μs
C. 74μs
D. 75μs

39.【參考答案】D
【解析】①P2?的優先權最高，所以會先調度P2?，花費 1μs，切換成進程P2?；②2μs 到 25μs，執行進程P2?；③第 26μs，根據優先權，切換到進程P3?；④第 27μs 到 62μs，執行進程P3?；⑤第 63μs，切換到進程P1?；⑥第 64μs 到 75μs，執行進程P1?；
進程P1?的周轉時間=30μs+75μs=105μs；進程P2?的周轉時間=15μs+25μs=40μs；進程P3?的周轉時間=18μs+62μs=80μs。系統的平均周轉時間=(105μs+40μs+80μs)/3=75μs。

40.【2019】系統采用二級反饋隊列調度算法進行進程調度。就緒隊列Q1?采用時間片輪轉調度算法，時間片為 10ms；就緒隊列Q2?采用短進程優先調度算法；系統優先調度Q1?隊列中的進程，當Q1?為空時系統才會調度Q2?中的進程；新創建的進程首先進入Q1?；Q1?中的進程執行一個時間片后，若未結束，則轉入Q2?。若當前Q1?、Q2?為空，系統依次創建進程P1?、P2?后即開始進程調度。P1?、P2?需要的 CPU 時間分別為 30ms 和 20ms，則進程P1?、P2?在系統中的平均等待時間為（ ）。
A. 25ms
B. 20ms
C. 15ms
D. 10ms

40.【參考答案】C
【解析】系統依次創建進程P1?、P2?后，二者依次進入到隊列Q1?，按照時間片輪轉調度算法，兩個進程先后被分配一個時間片 (10ms) 時間運行。根據二級反饋隊列調度算法的性質，在各自的時間片用完后，兩個進程先后進入Q2?隊列。根據Q2?隊列采用的短進程優先調度算法，此時需要考慮兩個進程的剩余執行時間 (P1?剩余 20ms，P2?剩余 10ms) 并選擇P2?進行調度。P2?運行結束后，調度P1?。具體時間節點為：①1ms 到 10ms 執行P1?；②11ms 到 20ms 執行P2?；③21ms 到 30ms 執行P2?；④31ms 到 50ms 執行P1?。P1?等待時間為 20ms (11ms 到 30ms)；P2?等待時間為 10ms (1ms 到 10ms)。平均等待時間為(20ms+10ms)/2=15ms，故選 C。

41.【2020】下列與進程調度有關的因素中，在設計多級反饋隊列調度算法時需要考慮的是（ ）。
I. 就緒隊列的數量
II. 就緒隊列的優先級
III. 各就緒隊列的調度算法
IV. 進程在就緒隊列間的遷移條件
A. 僅 I、II
B. 僅 III、IV
C. 僅 II、III、IV
D. I、II、III、IV

41.【參考答案】D
【解析】本題實際在考查多級反饋隊列調度算法的特點。首先該調度算法需要定義多個就緒隊列，所以 I 需要考慮；第二，當多個就緒隊列均有進程排隊時，需要確定先調度哪個隊列的進程，也就是確定各個隊列優先級，所以 II 需要考慮；第三，各個就緒隊列的調度算法可以是不同的，所以要為每個就緒隊列確定一個調度算法，III 需要考慮；第四，多級反饋隊列調度算法需要一個進程可以在不同隊列間遷移，這能體現出 “反饋” 這一特點，如果不遷移就成了多級隊列調度算法，所以 IV 需要考慮。

42.【2021】下列內核的數據結構程序中，分時系統實現時間片輪轉調度需要使用的是（ ）。
I. 進程控制塊
II. 時鐘中斷處理程序
III. 進程就緒隊列
IV. 進程阻塞隊列
A. 僅 II、III
B. 僅 I、IV
C. 僅 I、II、III
D. 僅 I、II、IV

42.【參考答案】C
【解析】進程控制塊是描述進程狀態和特性的數據結構，記錄了進程占用 CPU 的時間，所以 I 需要使用；使用時間片輪轉調度算法時，在每次時鐘中斷時，時鐘中斷處理程序會判斷當前運行進程時間片是否耗盡，如果耗盡會進行進程調度，所以 II 需要；當一個進程的時間片耗盡且仍未完成，則該進程進入進程就緒隊列，所以 III 需要；時間片輪轉調度算法不涉及阻塞狀態，所以 IV 不需要，正確答案選 C。

43.【2021】下列事件中，可引起進程調度程序執行的是（ ）。
I. 中斷處理結束
II. 進程阻塞
III. 進程執行結束
IV. 進程的時間片用完
A. 僅 I、III
B. 僅 II、IV
C. 僅 III、IV
D. I、II、III、IV

43.【參考答案】D
【解析】I 正確，例如時鐘中斷發生時，若當前進程時間片用盡，則會發生進程調度；II 正確，例如此刻運行的進程進行了 I/O 操作，在數據到來之前，該進程會主動阻塞，操作系統會進行進程調度；III 正確，當一個進程運行結束后，需要調度其他進程占有處理器運行，如果沒有其他就緒進程，則會調度閑逛進程；IV 正確，是進程調度的時機之一；所以正確答案是 D。

44.【2016】某進程調度程序采用基于優先數（priority）的調度策略，即選擇優先數最小的進程運行，進程創建時由用戶指定一個 nice 作為靜態優先數。為了動態調整優先數，引入運行時間 cpuTime 和等待時間 waitTime，初值均為 0。進程處于執行態時，cpuTime 定時加 1，且 waitTime 置 0；進程處于就緒態時，cpuTime 置 0，waitTime 定時加 1。請回答下列問題。
(1) 若調度程序只將 nice 的值作為進程的優先數，即 priority = nice，則可能會出現饑餓現象，為什么？
(2) 使用 nice、cpuTime 和 waitTime 設計一種動態優先數計算方法，以避免產生饑餓現象，并說明 waitTime 的作用。

44.【參考答案】
(1) 根據第一問的描述，如果調度程序只將 nice 值作為進程的優先數，則本調度算法為靜態優先級調度算法。如果有進程的優先級過低，而就緒隊列中不斷有高優先級進程進入，則該低優先級進程會一直無法使用處理機，從而發生饑餓現象。
(2) 解決饑餓現象的手段之一，就是引入動態優先數，通過動態調整進程的優先數來使得每個進程都可以在有限時間內使用處理機。當設計動態優先數時，不難想到可以類比高響應比優先調度算法，保證設計出來的動態優先數有三個特點：兩個進程如果其他指標均相同，由 nice 決定優先數；低優先數進程通過長時間等待優先數會減小；進程使用處理機運行后優先數會變大。最終設計出的計算公式為：
????????????????????????????????????????priority=(β×cpuTime)÷(1+nice+α×waitTime)
其中，常數β>0，常數α>0。公式中的除數需要加 1，從而避免除數為 0。α和β用于調整waitTime和cpuTime的影響程度。waitTime用來提高那些長時間等待處理器資源的進程的優先級，防止其饑餓。