補充知識

1. PSW程序狀態字寄存器
2. PC程序計數器：存放下一條指令的地址
3. IR指令寄存器：存放當前正在執行的指令
4. 通用寄存器：存放其他一些必要信息

進程

進程：進程是進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位。

進程實體 = 程序段 + 相關數據段 + 進程控制塊PCB

PCB是給OS用的，程序段和數據段都是給進程自己使用的

①創建進程 = 創建進程實體中的PCB

撤銷進程 = 撤銷進程的PCB

②進程映像（進程實體） 是靜止的，進程是動態的

③PCB是進程存在的唯一標識。OS管理時所需要的信息都放在PCB中

進程的特征

1. 動態性（最基本特征）：進程是程序的一次執行，具有一定的生命周期，是動態的產生、變化和消亡的
2. 并發性：多個進程實體同存于內存中，能在一段時間內同時運行
3. 獨立性：進程實體是一個能獨立運行、獨立獲得資源和獨立接受調度的基本單位
4. 異步性：由于進程的相互制約，使得進程按各自獨立的、不可預知的速度向前推進（OS提供“進程同步機制”來解決異步問題）
5. 結構性：每個進程都會配置一個PCB

進程的狀態

• 運行態 —— 單處理機中，每個時刻只有一個進程處于運行態
• 就緒態
• 阻塞態 / 等待態 ：進程正在等待某一事件而暫停運行（等待某資源為可用，等待輸入/輸出完成）
• 創建態

—— 創建進程：申請一個空白PCB → 向PCB里填寫用于控制和管理進程的信息 → 為該進程分配運行時所必需的資源 → 把該進程轉入就緒態并插入就緒隊列

• 終止態 ：處理資源釋放和回收（回收PCB）

補充知識

• 一個進程可以執行exit系統調用，請求OS終止該進程 → “終止態”

• 在進程PCB中，會有一個變量state來表示進程的當前狀態

• 同一程序運行在不同的數據集上，形成不同的進程

• 一個計算機系統中，進程的最大數目主要受到 內存大小 限制

• 在一個多道系統中，若就緒隊列不空，就緒的進程數目越多，處理器的效率不變

---

①進程控制塊PCB

• 進程描述信息：進程標識符PID、用戶標識符UID
• 進程控制和管理信息：進程當前狀態、進程優先級、代碼運行入口地址、程序的外存地址、進入內存時間、處理機占用時間、信號量使用
• 資源分配清單：代碼段指針、數據段指針、堆棧段指針、文件描述符、鍵盤、鼠標
• 處理及相關信息：通用寄存器值、地址寄存器值、控制寄存器值、標志寄存器值、狀態字

進程組織方式

①鏈接方式：按照進程狀態將PCB分為多個隊列；操作系統持有指向各個隊列的指針

②索引方式：根據進程狀態的不同，建立幾張索引表；操作系統持有指向各個索引表的指針

②程序段

程序的代碼（指令序列）

③數據段

運行過程中產生的各種數據。如：程序中定義的變量

---

進程控制

進程控制：對系統中的所有進程實施有效的管理，具有創建新進程、撤銷已有進程、實現進程狀態轉換等功能

原語：進程控制用的程序段（執行期間不允許中斷）

進程的創建

①允許一個進程（父進程）創建另一個進程（子進程）

1. 子進程繼承父進程所擁有的資源；
2. 撤銷子進程時，需把從父進程獲取的資源還給父進程；
3. 撤銷父進程時，同時撤銷子進程
4. 父進程與子進程共享一部分資源，但不能共享虛擬地址空間
5. 父進程創建子進程：父進程與子進程同時執行（并發）
6. 主程序調用子程序：主程序暫停在調用點，子程序開始執行，直到子程序返回，主程序才開始執行

②引起進程的創建（創建態→就緒態）：終端用戶登陸系統、作業調度、系統提供服務、用戶程序的應用請求

• 申請一個空白PCB（PCB有限）
• 為進程分配所需資源
• 初始化PCB
• 將新進程插入就緒隊列

進程的終止

①引起進程的終止（…態→終止態→無）：正常結束、異常結束、外界干預

• 根據被終止進程的標識符，檢索出該進程的PCB
• 若被終止進程處于運行態，立即終止該進程的執行（剝奪CPU），將處理機資源分配給其他進程
• 將其所有子孫進程終止
• 將該進程所擁有的全部資源，歸還給父進程或OS
• 將該PCB刪除

進程的阻塞（Block原語）和喚醒（Wakeup原語）

①引起進程的阻塞（運行態→阻塞態）：請求系統資源失敗、等待某種操作的完成、新數據尚未到達、無新任務可做 等期待的某些事件未發生

• 找到被阻塞進程的標識號對應的PCB
• 若該進程為運行態，則保護其現場，將其狀態轉為阻塞態，停止運行
• 把該PCB插入相應事件的等待隊列

②引起進程的喚醒（阻塞態→就緒態）：I/O操作已完成、新數據已到達 等期待的某些事件發生

• 在該事件的等待隊列中找到相應進程的PCB
• 將其從等待隊列中移出，并置其狀態為就緒態
• 把該PCB插入就緒隊列，等待調度程序調度

進程的切換

①允許進程的切換：當前進程時間片到、有更高優先級的進程達到、當前進程主動阻塞、當前進程終止

• 將運行環境信息存入PCB
• 把該PCB移入相應隊列
• 選擇另一個進程執行，并更新其PCB
• 根據PCB恢復新進程所需的運行環境

進程的通信

∵各個進程擁有的內存地址空間相互獨立，故需要進行通信，即進程之間的信息交換

1.共享存儲

共享存儲：存在一塊可直接訪問的共享空間，通過對這片共享空間進行讀/寫操作（各個進程的訪問是互斥的）來實現信息交換

其中，讀/寫操作需要使用 同步互斥工具（P操作、V操作）

①基于數據結構的共享（低級）

速度慢，限制多

②基于存儲區的共享（高級）

注：OS只負責為通信進程提供可共享使用的存儲空間和同步互斥工具

數據交換由用戶自己安排讀/寫指令完成

2.消息傳遞

消息傳遞：進程間的數據交換以格式化的消息為單位

需要使用 發送消息Send 和 接收消息Receive 兩個原語

消息頭：發送進程ID、接收進程ID、消息長度等格式化的信息

①直接通信方式

直接把消息發送給接收進程（需指明接收進程的ID）

②間接通信方式（信箱通信方式）

把消息發送到某個中間實體（需指明要發送到的信箱）

3.管道通信（單向）

1. 管道通信允許兩個進程按 生產者-消費者 方式進行通信
2. 數據在管道中 先進先出（循環隊列）
3. 半雙工通信：在某一時間段內只能實現單向的傳輸
4. 管道文件：一個固定大小的緩沖區
5. 管道機制需提供的能力：互斥（由OS實現）、同步、確定對方的存在

管道只能由創建進程所訪問，當父進程創建一個管道后，由于管道是一種特殊文件，子進程會繼承父進程的打開文件，因此子進程也會繼承父進程的管道，并使用這個管道與父進程進行通信。

• 只要管道不是空的，讀進程就能從管道中讀出數據
• 若數據被讀空，則讀進程阻塞，直到寫進程往管道中寫入新的數據，再將讀進程喚醒
• 只要管道沒滿，寫進程就能往管道中寫入數據
• 若管道被寫滿，則寫進程阻塞，直到讀進程讀出數據，再將寫進程喚醒

從管道讀數據是一次性操作，數據一旦被讀取，就徹底消失，同時釋放空間以便寫更多數據。這種普通管道只允許單向通信，若要實現父子進程雙向通信，則需要定義兩個管道。

解決方案：①一個管道允許多個寫進程，一個讀進程

②允許多個寫進程，多個讀進程，但系統會讓各個讀進程輪流從管道中讀數據

4.共享文件

---

---

線程

• 引入進程的目的：使多道程序并發執行，提高資源利用率和系統吞吐量
• 引入線程的目的：減小程序在并發執行時所付出的時空開銷，提高OS的并發性能

線程（輕量級進程）：是一個基本的CPU執行單元，是程序執行流的最小單元。

線程 = 線程ID + 程序計數器 + 寄存器集合 + 堆棧

線程控制塊TCB：記錄線程執行的寄存器和棧等現場狀態。

線程控制塊TCB = 線程標識符TID + 寄存器 + 線程運行狀態 + 優先級 + 線程專有存儲區 + 堆棧指針

寄存器：程序計數器PC（線程目前執行到哪）、狀態寄存器、通用寄存器（線程運行的中間結果）

線程運行狀態：用于描述線程正處于何種狀態

優先級：線程調度、資源分配的參考

線程專有存儲區：線程切換時用于保存現場

堆棧指針：用于過程調度時保存局部變量及返回地址等

①線程是進程中的一個實體，是被系統獨立調度和分派的基本單位

②線程自己不擁有系統資源，只擁有一點兒在運行在必不可少的資源，但它可與同屬于一個進程的其他線程共享進程所擁有的全部資源，可獨立執行程序

③一個線程可以創建和撤銷另一個線程，同一進程中的多個線程之間可以并發執行

④引入線程后，進程只作為除CPU外的系統資源的分配單元，而線程是作為處理及的分配單元

線程與進程的比較	線程（引入線程的操作系統）	進程（傳統操作系統）
調度	線程是獨立調度的基本單位 線程切換代價小。 在同一進程內進行線程切換不會引起進程切換	進程是擁有資源和獨立調度的基本單位。 每次調度都會引起上下文切換，開銷大
并發性	進程之間可以并發執行 一個進程中的多個線程也可并發執行	進程之間可以并發執行
擁有資源	線程不擁有系統資源	進程是系統中擁有資源的基本單位
獨立性	某進程中的線程對其他進程不可見。 同一進程內的不同線程共享進程的地址空間和資源	每個進程都擁有獨立的地址空間和資源
系統開銷	線程切換只需保存和設置少量寄存器內容，開銷很小； 同一進程內的多個線程的同步與通信不需要OS的干預	系統開銷很大
支持多處理機系統	多線程進程：進程中的多個線程可以分配到多個處理機上執行	單線程進程：進程只能允許在一個處理機上

線程的實現方式

①用戶級線程ULT

用于早期OS：只支持進程，不支持線程

• 在用戶級線程中，內核意識不到線程的存在，應用程序可以通過使用線程庫設計成多線程程序
• 設置了用戶級線程的系統，仍以 進程 為單位進行調度

優點：①線程切換不需要轉換到內核空間，系統開銷小，效率高

②用戶級線程的實現與OS平臺無關

缺點：①當一個用戶級線程被阻塞后，整個進程都會被阻塞，并發度不高

②多個線程不可在多核處理機上并行運行

②內核級線程KLT = 內核支持的線程

內核級線程是處理機分配的基本單位

• 線程切換需要CPU變態
• 內核級線程是在內核的支持下運行的

優點：①多個線程可并行執行，并發能力強；

②如果進程中的一個線程被阻塞，可運行其他進程中的線程；

③采用多線程技術

缺點：同一進程中的線程切換，需要從用戶態轉到核心態進行，系統開銷較大

③組合方式

線程庫：為程序員提供創建和管理線程的API

1. 在用戶空間中提供一個沒有內核支持的庫
2. 實現由操作系統直接支持的內核級的一個庫

多線程模型

①多對一模型

情況：1.以不同的參數或數據多次執行同一個應用程序（多對一）

2.進程在執行過程中可以加載執行不同的程序（一對多）

優點：線程管理在用戶空間進行，不需要切換，效率較高

缺點：并發性不高。若一個線程在訪問內核時發生阻塞，則整個進程都會被阻塞

②一對一模型

情況：執行一條命令或運行一個應用程序

優點：當一個線程被阻塞后，允許調度另一個線程允許（因為內核級線程是處理及分配的單位），故并發能力較強

缺點：每創建一個用戶線程，相應的需創建一個內核線程，開銷較大

③多對多模型

情況：并發執行不同的應用程序

特點：克服了多對一模型并發度不高的特點，克服了一對一模型的一個用戶進程占用太多內核級線程而開銷太大的缺點

擁有上述兩種模型的優點

補充知識

• 多線程：在一個程序中可以定義多個線程并同時運行它們，每個線程可以執行不同的任務
• 多任務：針對操作系統，代表OS可以同時執行的程序個數
• 多線程：針對一個程序，代表一個程序可以同時執行的線程個數，而每個線程可以完成不同的任務
• 一個系統中可能所有進程都處于等待態（死鎖）

---

---

進程的調度

補充知識

• 進程處于臨界區（訪問臨界資源的那段代碼）時不能進行處理機調度
• 內核程序臨界區：訪問某種內核數據結構（例：進程的就緒隊列）

①高級調度（作業調度）

作用：按照一定的原則從外存上處于后備隊列的作業中挑選一個（或多個），分配內存、輸入/輸出設備等必要的資源

多道批處理系統大多配有作業調度，而其它系統中通常不需要配置作業調度

②中級調度（內存調度）

目的：提高內存利用率和系統吞吐量

將那些暫時不能運行的進程調至外存等待，此時進程的狀態—— 掛起態

作用：把外存上的那些已具備運行條件的就緒進程再重新調入內存，并修改其狀態為就緒態，掛在就緒隊列上等待

③低級調度（進程調度）

作用：按照某種算法從就緒隊列中選擇一個進程為其分配處理機

進程調度是最基本的一種調度，在各個操作系統中都必須配置

狹義進程調度：從就緒隊列中選出一個要運行的進程

廣義進程調度：包含了選擇一個進程和進程切換兩個步驟

三級調度的聯系

作業調度從外存的后備隊列中選擇一批作業進入內存，為它們建立進程，這些進程被送入就緒隊列；

進程調度從就緒隊列中選出一個進程，并把其狀態改為運行態，把CPU分配給它；

中級調度是為了提高內存的利用率，系統將那些暫時不能運行的進程掛起來。

1. 作業調度為進程活動做準備，進程調度使進程正常活動起來
2. 中級調度將暫時不能運行的進程掛起，中級調度處于作業調度和進程調度之間
3. 調度頻率：作業<中級<進程

---

🤨調度算法評價標準

①CPU利用率

CPU利用率 = CPU有效工作時間 / ( CPU有效工作時間 + CPU空閑等待時間 ）

②系統吞吐量

單位時間內CPU完成作業的數量

③周轉時間

從作業提交到作業完成所經歷的時間

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

平均周轉時間 = （作業1的周轉時間 + … + 作業n的周轉時間）/ n

帶權周轉時間 = 作業周轉時間 / 作業實際運行時間

平均帶權周轉時間 = （作業1的帶權周轉時間 + … + 作業n的帶權周轉時間）/n

④等待時間

進程：進程處于等處理機的時間之和

作業：需考慮建立進程后的等待時間，和作業在外存后備隊列中等待的時間

⑤響應時間 ——衡量調度算法的重要準則之一

從用戶提交請求到系統首次產生響應所用的時間

---

調度程序（調度器）

用于調度和分派CPU的組件（排隊器、分派器、上下文切換器）

①觸發“調度程序”的情況

1. 非搶占式調度策略，只有運行進程阻塞或退出才觸發
2. 搶占式調度策略，每個時鐘中斷或k個時鐘中斷會觸發

②觸發“調度程序”

1. 創建新進程
2. 進程退出
3. 運行進程阻塞
4. I/O中斷發生

🎃不能進行進程的調度與切換的情況

1. 在處理中斷的過程中
2. 進程在操作系統內核臨界區中
3. 其他需要完全屏蔽中斷的原子操作過程中

🎃應該進行進程調度與切換的情況

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

1. 進程正常終止
2. 運行過程中發生異常而終止
3. 進程主動請求阻塞（等待I/O）

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

1. 分給進程的時間片用完
2. 有更緊急的事需要處理（I/O中斷）
3. 有更優先級的進程進入就緒隊列

進程切換往往在調度完成后立刻發生，會保存原進程當前斷點的現場信息，回復被調度進程的現場信息

當進程處于臨界區時，說明進程正在占用處理機，只要不破壞臨界資源的使用規則，就不會影響處理機的調度（即，在進程處于臨界區時可以進行處理機調度）

😊進程調度方式

• 非搶占調度方式（非剝奪方式）

主動放棄處理機

優點：實現簡單、系統開銷小，適用于早期批處理系統

缺點：不能用于分時系統和大多數實時系統

• 搶占調度方式（剝奪方式）

適合分時系統和實時操作系統。

優點：遵循優先權、短進程優先和時間片原則

閑逛進程（能耗低、優先級最低、不需要CPU之外的資源、不會被阻塞）

在進程切換時，若系統中沒有就緒進程，就會調度閑逛進程運行

可以是0地址指令，占一個完整的指令周期（指令周期末尾例行檢查中斷）

---

調度算法

調度算法名稱	先來先服務FCFS	短作業優先SJF	優先級調度	高響應比優先調度	時間片輪轉RR	多級隊列調度	多級反饋隊列調度
算法過程	選擇最先進入后備隊列的作業	選擇運行時間最短的作業	選擇優先級最高的作業	選擇響應比最高的作業	選擇就緒隊列中的第一個進程
適用	作業、進程調度	作業、進程調度	作業、進程調度；實時操作系統	作業、進程調度	進程調度；分時系統		進程調度
是否導致“饑餓”	不會導致饑餓	會饑餓	會饑餓	不會饑餓			會饑餓
調度方式	非搶占式	非搶占式	非搶占式、搶占式優先級調度；	非搶占式	搶占式		搶占式
公式				響應比Rp= (等待時間+要求服務時間) / 要求服務時間		最高優先級 →系統進程→ →交互式進程→ →批處理進程→ 最低優先級	（如表格下圖）
優點	算法簡單公平	平均等待時間、平均周轉時間最少		有利于短作業	公平，響應快		- 公平，不必實現估計進程的運行時間 - 可靈活調整對各類進程的偏好程度 - 終端型作業用戶：短作業優先 - 短批處理作業用戶：周轉時間較短 - 長批處理作業用戶：不會長期得不到處理
缺點	- 效率低 - 長作業有利，短作業不利 - 利于CPU繁忙型作業，不利于I/O繁忙型作業	- 長作業不利，短作業有利 - 可能導致長作業饑餓 - 不能保證緊迫性作業會被及時處理 - 不一定能真正做到短作業優先調度		計算響應比的開銷大	- 不區分任務的緊急程度 - 處理機在進程間過于頻繁的切換 - 開銷增大		無
補充		短進程優先算法SPF 搶占式版本：最短剩余時間優先算法SRTN	- 靜態優先級：創建進程時確定 - 動態優先級：根據進程情況的變化動態調整 - 進程優先級設置： 1. 系統進程>用戶進程 2. 交互性進程>非交互型進程(前臺>后臺) 3. I/O型進程>計算型進程		時間片的長短： 系統的響應時間、就緒隊列中的進程數目、系統的處理能力	同一隊列中的進程可以設置不同的優先級； 不同的隊列本身也可以設置不同的優先級

進程切換

任何進程都是在操作系統內核的支持下運行的

1.上下文切換

切換CPU到另一個進程需要保存當前進程狀態并恢復另一個進程的狀態

2.上下文切換的消耗

3.上下文切換與模式切換

模式切換：用戶態和內核態之間的切換

調度：決定資源分配給哪個進程的行為（決策）

切換：實際分配的行為（執行）