【學習筆記】計算機操作系統（二）—

第二章進程的描述與控制

文章目錄

第二章進程的描述與控制
- 2.1 前趨圖和程序執行
- - 2.1.1 前趨圖
  - 2.1.2 程序順序執行
  - 2.1.3 程序并發執行
- 2.2 進程的描述
- - 2.2.1 進程的定義和特征
  - 2.2.2 進程的基本狀態及轉換
  - 2.2.3 掛起操作和進程狀態的轉換
  - 2.2.4 進程管理中的數據結構
- 2.3 進程控制
- - 2.3.1 操作系統內核
  - 2.3.2 進程的創建
  - 2.3.3 進程的終止
  - 2.3.4 進程的阻塞與喚醒
  - 2.3.5 進程的掛起與激活
- 2.4 進程同步
- - 2.4.1 進程同步的基本概念
  - 2.4.2 硬件同步機制
  - 2.4.3 信號量機制
  - 2.4.4 信號量的應用
  - 2.4.5 管程(Monitors)機制
- 2.5 經典進程的同步問題
- - 2.5.1 生產者-消費者問題（Producer-Consumer Problem）
  - 2.5.2 哲學家進餐問題（Dining Philosophers Problem）
  - 2.5.3 讀者-寫者問題（Reader-Writer Problem）
  - 2.5.4 可生產單種產品的多生產者-多消費者問題
  - 2.5.5 吸煙者問題 - 可生產多種產品的單生產者-多消費者問題
- 2.6 進程通信
- - 2.6.1 進程通信的類型
  - 2.6.2 消息傳遞通信的實現方式
  - 2.6.3 直接消息傳遞系統實例
- 2.7 線程(Threads)的基本概念
- - 2.7.1 線程的引入
  - 2.7.2 線程與進程的比較
  - 2.7.3 線程的狀態和線程控制塊
- 2.8 線程的實現
- - 2.8.1 線程的實現方式
  - 2.8.2 線程的實現
  - 2.8.3 線程的創建和終止
  - 2.8.4 線程的狀態與轉換 + 組織與控制

2.1 前趨圖和程序執行

2.1.1 前趨圖

前趨圖(Precedence Graph)：是指一個有向無循環圖,可記為 DAG(DirectedAcyclic Graph)，用于描述進程之間執行的先后順序。

圖中的每個結點可用來表示一個進程或程序段，乃至一條語句,
結點間的有向邊則表示兩個結點之間存在的偏序(Partial Order)或前趨關系(Precedence Relation)。
- P_i -> P_j 或（P_i, P_j) ∈ -> 表示在P_j開始執行之前P_i必須完成。P_i是P_j的直接前趨，P_j是P_i的直接后繼。
把沒有前趨的結點稱為初始結點(Initial Node)
把沒有后繼的結點稱為終止結點(Final Node)
每個結點還具有一個重量(Weight)，用于表示該結點所含有的程序量或程序的執行時間。

2.1.2 程序順序執行

通常，一個應用程序由若干個程序段組成，每一個程序段完成特定的功能，它們在執行時，都需要按照某種先后次序順序執行，僅當前一程序段執行完后，才運行后一程序段。

在這里插入圖片描述

程序順序執行時的特征

順序性:指處理機嚴格地按照程序所規定的順序執行,即每一操作必須在下一個操作開始之前結束
封閉性:指程序在封閉的環境下運行，即程序運行時獨占全機資源，資源的狀態(除初始狀態外)只有本程序才能改變它，程序一旦開始執行，其執行結果不受外界因素影響
可再現性:指只要程序執行時的環境和初始條件相同，當程序重復執行時，可獲得相同的結果。

2.1.3 程序并發執行

只有在不存在前趨關系的程序之間才有可能并發執行，否則無法并發執行。

在這里插入圖片描述

程序并發執行時的特征

間斷性。程序在并發執行時，由于它們共享系統資源，以及為完成同一項任務而相互合作，致使在這些并發執行的程序之間形成了相互制約的關系。

例如：I、C和P是三個相互合作的程序，當計算程序完成 C_i-1 的計算后，如果輸入程序 I_i 尚未完成數據的輸入，則計算程序 C_i 就無法進行數據處理，必須暫停運行。只有當使程序暫停的因素消失后(如I_i已完成數據輸入)，計算程序便可恢復執行。
相互制約將導致并發程序具有“執行–暫停–執行”這種間斷性的活動規律。
失去封閉性。其中任一程序在運行時，其環境都必然會受到其它程序的影響。
不可再現性。計算結果必將與并發程序的執行速度有關。
例如：有兩個循環程序A和B，它們共享一個變量N。

程序A每執行一次時，都要做N=N+1操作;

程序B每執行一次時，都要執行Print(N)操作，然后再將N置成“0”。

假定某時刻變量N的值為n：
- ① N=N+1在 Print(N)和N=0之前，此時得到的N值分別為n+1,n+1,0。
- ② N=N+1在 Print(N)和N=0之后，此時得到的N值分別為n,0，1。
- ③ N=N+1在 Print(N)和N=0之間，此時得到的N值分別為n，n+1，0。

2.2 進程的描述

2.2.1 進程的定義和特征

定義

進程控制塊(Process Control Block，PCB)：系統利用 PCB 來描述進程的基本情況和活動過程，進而**控制和管理進程**。

進程實體(又稱進程映像)：簡稱為進程。由程序段【程序的代碼(指令序列)】、相關的數據段【運行過程中產生的各種數據(如:程序中定義的變量)】和 PCB【進程描述信息 + 進程控制和管理信息 + 資源分配清單 + 處理機相關信息】 三部分便構成。

PCB 是給操作系統用的；程序段、數據段是給進程自己用的，與進程自身的運行邏輯有關

創建進程，實質上是創建進程實體中的PCB;
撤消進程，實質上是撤消進程實體中的PCB。

進程：

進程是進程實體的運行過程。
進程是程序的一次執行。
進程是一個程序及其數據在處理機上順序執行時所發生的活動。
進程是具有獨立功能的程序在一個數據集合上的運行過程，是系統進行資源分配和調度的一個獨立單位。

進程是動態的，進程實體(進程映像)是靜態的。

特征

動態性。由創建而產生，由調度而執行，由撤消而消亡。—— 進程實體有一定的生命期。

程序則只是一組有序指令的集合，并存放于某種介質上，其本身并不具有活動的含義，因而是靜態的。

程序: 是靜態的。
進程(Process): 是動態的。
當進程被創建時，操作系統會為該進程分配一個唯一的、不重復的“身份證號”-- PID(Process lD，進程ID)
并發性。是指多個進程實體同存于內存中，且能在一段時間內同時運行。而程序(沒有建立PCB)是不能參與并發執行的。
獨立性。在傳統的OS中，獨立性是指進程實體是一個能獨立運行、獨立獲得資源和獨立接受調度的基本單位。凡未建立PCB的程序都不能作為一個獨立的單位參與運行。
異步性。是指進程是按異步方式運行的，即按各自獨立的、不可預知的速度向前推進。

2.2.2 進程的基本狀態及轉換

三個基本狀態

就緒(Ready)狀態

就緒狀態：指進程已處于準備好運行的狀態，即進程已分配到除 CPU以外的所有必要資源后，只要再獲得CPU，便可立即執行。

就緒隊列：系統中有許多處于就緒狀態的進程，它們按一定的策略(如優先級策略)排成的一個隊列

執行(Running)狀態

執行狀態：進程已獲得 CPU，其程序正在執行的狀態。

對任何一個時刻而言，在單處理機系統中，只有一個進程處于執行狀態，
而在多處理機系統中，則有多個進程處于執行狀態。

阻塞(Block)狀態

阻塞狀態 / 等待狀態 / 封鎖狀態：正在執行的進程由于發生某事件(如等待某種系統資源的分配，或者等待其他進程的響應等)暫時無法繼續執行時的狀態，即進程的執行受到阻塞。此時引起進程調度，OS把處理機分配給另一個就緒進程，而讓受阻進程處于阻塞狀態。

阻塞隊列：將處于阻塞狀態的進程排成一個隊列。【根據阻塞原因的不同，會設置多個阻塞隊列。】

兩個常見狀態

創建狀態

進程的創建通常包括以下步驟：

申請空白 PCB：操作系統為進程分配一個空白 進程控制塊（PCB），用于存儲進程的管理和控制信息。
填寫 PCB：向 PCB 中填寫進程的基本信息，如進程 ID、優先級、狀態、程序計數器、寄存器狀態等。
分配資源：為該進程分配運行所需的資源，如內存空間、文件描述符、設備等。
轉入就緒狀態：如果資源分配成功，將進程狀態設置為 就緒狀態，并將其插入就緒隊列，等待調度執行。

創建狀態：在資源分配過程中，系統無法滿足進程的資源需求（例如內存不足），則進程的創建無法完成的狀態。【創建狀態是為了確保進程的調度只能在創建工作完成后進行，從而保證對 PCB 操作的完整性。】

終止狀態

進程的終止可以通過以下幾種方式觸發【觸發之后就進入終止狀態，進程不再執行】：

自然結束：進程完成其任務，達到程序中的結束點（如 main 函數的返回）。
無法克服的錯誤：進程在執行過程中遇到致命錯誤（如訪問非法內存、除以零等），無法繼續運行。
操作系統終止：操作系統主動終止進程，例如因為系統資源不足或進程違反系統規則。
其他進程終止：具有終止權的進程（如父進程或特權進程）主動終止目標進程。

進程終止通常分為兩個步驟：

善后處理：進程不再執行，但是操作系統會保留一個記錄，其中保存狀態碼和一些計時統計數據，供其他進程收集。
刪除進程：將進程的進程控制塊（PCB）清零，并將空白PCB歸還給系統，以便復用。

狀態轉換

在這里插入圖片描述

NULL → 創建：一個新進程產生時，該進程處于創建狀態
創建狀態 → 就緒狀態：當其獲得了所需的資源以及對其 PCB 的初始化工作完成后，由創建轉變為就緒
就緒狀態 → 執行狀態：在調度程序為處于就緒狀態的進程分配了處理機之后便可執行，由就緒轉變為執行
執行狀態 → 終止狀態：進程主動結束或被動結束（無法克服的錯誤，操作系統/其他進程終止），由執行轉變為終止
執行狀態 → 就緒狀態：正在執行的進程(當前進程)因分配的時間片已用完而被剝奪處理機暫停執行時，由執行轉為就緒
執行狀態 → 阻塞狀態：正在執行的進程由于發生某事件暫時無法繼續執行時，由執行狀態轉變為阻塞狀態。
阻塞狀態 → 就緒狀態：阻塞的進程所等待的事件已經發生，即進程已分配到除 CPU以外的所有必要資源，由阻塞轉變為就緒

進程的組織：鏈式方式和索引方式

2.2.3 掛起操作和進程狀態的轉換

掛起(Suspend)操作：當該操作作用于某個進程時，該進程將被掛起，意味著此時該進程處于靜止狀態。

如果進程正在執行，它將暫停執行。
如果進程正在就緒，則該進程此時暫不接受調度。
與掛起操作對應的操作是激活(Active)操作。

引入掛起操作的原因

終端用戶的需要。終端用戶在自己的程序運行期間可以暫停自己的程序的運行，以便研究其執行情況或對程序進行修改。
父進程請求。父進程希望掛起自己的某個子進程，以便考查和修改該子進程或者協調各子進程間的活動。
負荷調節的需要。當實時系統中的工作負荷較重，已可能影響到對實時任務的控制時，可由系統把一些不重要的進程掛起，以保證系統能正常運行。
操作系統的需要。操作系統有時希望掛起某些進程，以便檢查運行中的資源使用情況或進行記賬。

狀態轉換進階版

當進程處于未被掛起的就緒狀態時，稱此為活動就緒狀態 —— 可以接收調度，該進程表示為 Readya。

當進程處于已被 Suspend掛起的就緒狀態時，稱此為靜止就緒狀態 —— 不可以被調度，該進程表示為 Readys。

當進程處于未被掛起的阻塞狀態時，稱它此為活動阻塞狀態 —— 該進程表示為 Blockeda。

當進程處于已被 Suspend掛起的阻塞狀態時，稱此為靜止阻塞狀態—— 該進程表示為 Blockeds。

在這里插入圖片描述

創建狀態 → 活動就緒狀態：在當前系統性能和內存容量均允許的情況下，已完成對進程創建的必要操作，由創建轉變為活動就緒。
創建狀態 → 靜止就緒狀態：考慮到系統當前資源狀況和性能的要求，不分配給新建進程所需資源【主要是主存】，而被安置在外存，不參與調度，此時進程創建工作尚未完成，由創建轉變為靜止就緒。
活動就緒 → 靜止就緒。活動就緒的進程被Suspend掛起，由活動就緒轉變為靜止就緒。
靜止就緒 → 活動就緒。處于靜止就緒狀態的進程被激活原語 Active 激活后，由靜止就緒轉變為活動就緒。
活動阻塞 → 靜止阻塞。活動阻塞的進程被Suspend掛起，由活動阻塞轉變為靜止阻塞。
靜止阻塞 → 活動阻塞。處于靜止阻塞狀態的進程被激活原語 Active 激活后，由靜止阻塞轉變為活動阻塞。
靜止阻塞 → 靜止就緒。處于靜止阻塞狀態的進程在其所期待的事件出現后，由靜止阻塞變為靜止就緒。
活動阻塞 → 活動就緒。處于活動阻塞狀態的進程在其所期待的事件出現后，由活動阻塞變為活動就緒。

2.2.4 進程管理中的數據結構

操作系統中用于管理控制的數據結構

資源信息表或進程信息表：在計算機系統中，對于每個資源和每個進程都設置了一個數據結構，其中包含了資源或進程的標識、描述、狀態等信息以及一批指針。通過這些指針，可以將同類資源或進程的信息表，或者同一進程所占用的資源信息表分類鏈接成不同的隊列，便于操作系統進行查找。

一般分為以下四類:內存表、設備表、文件表和用于進程管理的進程表（進程控制塊 PCB）

進程控制塊 PCB(Process Control Block)

系統是通過 PCB感知進程的存在的。PCB已成為進程存在于系統中的唯一標志。【當系統創建一個新進程時，就為它建立了一個PCB。進程結束時又回收其PCB，進程于是也隨之消亡。】用于描述進程的當前情況以及管理進程運行的全部信息。

PCB 的作用是使一個在多道程序環境下不能獨立運行的程序(含數據)成為一個能獨立運行的基本單位，一個能與其他進程并發執行的進程。PCB作用的具體闡述:

作為獨立運行基本單位的標志。當一個程序(含數據)配置了 PCB 后，就表示它已是一個能在多道程序環境下獨立運行的、合法的基本單位，也具有取得 OS服務的權利。
能實現間斷性運行方式。
- 當進程因阻塞而暫停運行時，它必須保留自己運行時的CPU現場信息，再次被調度運行時，還需要恢復其 CPU 現場信息。
- 在有了PCB 后，系統就可將 CPU 現場信息保存在被中斷進程的 PCB 中，供該進程再次被調度執行時恢復 CPU 現場時使用。
提供進程管理所需要的信息。
- 調度程序調度到某進程運行時，只能根據該進程PCB中記錄的程序和數據在內存或外存中的始址指針，找到相應的程序和數據;
- 在進程運行過程中，當需要訪問文件系統中的文件或 I/O 設備時，也都需要借助于 PCB 中的信息。
- 可根據 PCB中的資源清單了解到該進程所需的全部資源等。
提供進程調度所需要的信息。
- 在 PCB中就提供了進程處于何種狀態的信息。
- 其他信息，如進程的優先級、進程的等待時間和已執行的時間等。
實現與其它進程的同步與通信。
- 進程同步機制是用于實現諸進程的協調運行的，在采用信號量機制時，它要求在每個進程中都設置有相應的用于同步的信號量。
- 在PCB中還具有用于實現進程通信的區域或通信隊列指針等。

進程控制塊中的信息

進程標識符：進程標識符用于唯一地標識一個進程。PID
- 外部標識符。為了方便用戶(進程)對進程的訪問。它是由創建者提供的，通常由字母、數字組成。
- 內部標識符。為了方便系統對進程的使用，每一個進程擁有一個唯一的數字標識符，通常是一個進程的序號。
處理機狀態 - 處理機的上下文：主要是由處理機的各種寄存器中的內容組成的
- ①通用寄存器，又稱為用戶可視寄存器，用戶程序可以訪問的，用于暫存信息
- ②指令計數器，其中存放了要訪問的下一條指令的地址
- ③ 程序狀態字 PSW，其中含有狀態信息，如條件碼、執行方式、中斷屏蔽標志等
- ④ 用戶棧指針，指每個用戶進程都有一個或若干個與之相關的系統棧，用于存放過程和系統調用參數及調用地址。棧指針指向該棧的棧頂。
進程調度信息：
- ①進程狀態，指明進程的當前狀態
- ②進程優先級，是用于描述進程使用處理機的優先級別的一個整數，優先級高的進程應優先獲得處理機
- ③進程調度所需的其它信息，與所采用的進程調度算法有關，比如，進程已等待CPU的時間總和、進程已執行的時間總和等
- ④事件，是指進程由執行狀態轉變為阻塞狀態所等待發生的事件，即阻塞原因。
進程控制信息 - 用于進程控制所必須的信息：
- ①程序和數據的地址，進程實體中的程序和數據的內存或外存地(首)址
- ②進程同步和通信機制，實現進程同步和進程通信時必需的機制，如消息隊列指針、信號量等
- ③資源清單，在該清單中列出了進程在運行期間所需的全部資源(除CPU 以外), 另外還有一張已分配到該進程的資源的清單
- ④鏈接指針，本進程(PCB)所在隊列中的下一個進程的 PCB 的首地址。

PCB組織方式

在這里插入圖片描述

線性方式，即將系統中所有的PCB都組織在一張線性表中，將該表的首址存放在內存的一個專用區域中。該方式實現簡單、開銷小，但每次查找時都需要掃描整張表，因此適合進程數目不多的系統。
鏈接方式，即把具有相同狀態進程的 PCB 分別通過 PCB 中的鏈接字鏈接成一個隊列。可以形成就緒隊列、若干個阻塞隊列和空白隊列等。
- 就緒隊列：往往按進程的優先級將PCB從高到低進行排列，將優先級高的進程PCB排在隊列的前面。
- 阻塞隊列：阻塞狀態進程的 PCB 根據其阻塞原因的不同，排成多個。
索引方式，即系統根據所有進程狀態的不同，建立幾張索引表。把各索引表在內存的首地址記錄在內存的一些專用單元中，在每個索引表的表目中，記錄具有相應狀態的某個 PCB 在 PCB 表中的地址。

2.3 進程控制

進程控制就是要實現進程狀態轉換

2.3.1 操作系統內核

OS內核：功能模塊安排在緊靠硬件的軟件層次中，且常駐內存【一般將OS劃分為若干層次,再將OS的不同功能分別設置在不同的層次中】

與硬件緊密相關的模塊(如中斷處理程序等)
各種常用設備的驅動程序
運行頻率較高的模塊(如時鐘管理、進程調度和許多模塊所公用的一些基本操作)

如此安排目的：

便于對這些軟件進行保護，防止遭受其他應用程序的破壞
可以提高 OS 的運行效率。

處理機的執行狀態分類: 【將應用程序與操作系統內核隔離，防止 OS本身及關鍵數據(如PCB等)遭受到應用程序有意或無意的破壞。】

① 系統態: 又稱為管態，也稱為內核態。它具有較高的特權，能執行一切指令，訪問所有寄存器和存儲區，傳統的OS都在系統態運行。
② 用戶態: 又稱為目態。具有較低特權的執行狀態，僅能執行規定的指令，訪問指定的寄存器和存儲區。一般情況下，應用程序只能在用戶態運行，不能去執行 OS 指令及訪問 OS區域，就可以防止應用程序對OS的破壞。

系統態與內核的關系

系統態是內核的執行環境：
當 CPU 運行在系統態時，操作系統內核可以訪問和控制所有硬件資源，執行所有指令（包括特權指令）。
內核代碼運行在系統態，負責管理整個系統的運行。

內核是系統態的主體：
操作系統內核是唯一能夠在系統態下運行的軟件組件。
用戶程序無法直接運行在系統態，必須通過內核提供的接口（如系統調用）請求服務。

用戶態與應用程序的關系

用戶態是應用程序的執行環境：
當 CPU 運行在用戶態時，應用程序只能執行非特權指令，無法直接訪問硬件資源或執行特權操作。
應用程序代碼運行在用戶態，依賴于操作系統提供的服務。

應用程序是用戶態的主體：
應用程序是運行在用戶態的主要軟件組件。
操作系統內核無法直接運行在用戶態，但提供了接口（如系統調用、庫函數）供應用程序訪問系統資源和服務。

OS內核包含的兩個功能

支撐功能
- 中斷處理
  - 各種類型的系統調用
  - 鍵盤命令的輸入
  - 進程調度
  - 設備驅動等
- 時鐘管理
  - 在時間片輪轉調度中，每當時間片用完時，便由時鐘管理產生一個中斷信號，促使調度程序重新進行調度
  - 在實時系統中的截止時間控制
  - 批處理系統中的最長運行時間控制等
- 原語操作
  - 原語(Primitive)，就是由若干條指令組成的，用于完成一定功能的一個過程。是“原子操作”。原語在執行過程中不允許被中斷。
  - 原子操作(Action Operation)，一個操作中的所有動作是一個不可分割的基本單位，要么全做，要么全不做。原子操作在系統態下執行，常駐內存。
    原子性實現：
    
    用“關中斷指令”和“開中斷指令”這兩個特權指令實現原子性
    - 正常情況：每執行完一條指令，就需要判斷是否有外部中斷信號
    - 原子性實現：CPU執行了關中斷指令之后，就不再例行檢查中斷信號，直到執行開中斷指令之后才會恢復檢查。即關中斷、開中斷之間的這些指令序列就是不可被中斷的，這就實現了“原子性”。
資源管理功能
- 進程管理。
  - 由于各個功能模塊的運行頻率較高：進程的調度與分派、進程的創建與撤消等
  - 由于被多種功能模塊所需要：用于實現進程同步的原語、常用的進程通信原語等
- 存儲器管理。
  - 用于實現將用戶空間的邏輯地址變換為內存空間的物理地址的地址轉換機構
  - 內存分配與回收的功能模塊
  - 實現內存保護和對換功能的模塊等。
- 設備管理。由于設備管理與硬件(設備)緊密相關，因此其中很大部分也都設置在內核中
  - 各類設備的驅動程序
  - 用于緩和CPU與I/O速度不匹配矛盾的緩沖管理
  - 用于實現設備分配和設備獨立性功能的模塊等

2.3.2 進程的創建

進程的層次結構

UNIX

父進程(Parent Process)：創建進程的進程

子進程(Progeny Process)：被創建的進程

孫進程：子進程繼續創建的進程

進程家族(組)：進程與其子孫進程共同組成的

在PCB中設置了家族關系表項【標識進程之間的家族關系】，標明自己的父進程及所有的子進程。
- 子進程可以繼承父進程所擁有的資源。進程不能拒絕其子進程的繼承權。
- 當子進程被撤消時，應將其從父進程那里獲得的資源歸還給父進程。
- 在撤消父進程時，也必須同時撤消其所有的子進程。
Windows：不存在任何進程層次結構的概念，所有的進程都具有相同的地位。
- 進程之間的關系不是層次關系，而是獲得句柄與否、控制與被控制的簡單關系：
  一個進程創建另外的進程時創建進程獲得了一個句柄，其作用相當于一個令牌，可以用來控制被創建的進程。這個句柄是可以進行傳遞的，獲得了句柄的進程就擁有控制對應進程的權力。

進程圖（Process Graph）：用于描述進程之間關系的一棵有向樹

結點：代表進程；有向邊：代表進程之間的父子關系；樹的根節點：進程家族的祖先（Ancestor）

例子：在進程P_i 創建了進程P_j之后,稱P_i是P_j的父進程，P_j是P_i的子進程。

觸發進程創建(Creation of Process)的事件:

系統內核為用戶創建一個新進程:
- 用戶登錄。在分時系統中，用戶在終端鍵入登錄命令后，若登錄成功，系統將為該用戶建立一個進程，并把它插入就緒隊列中。
- 作業調度。在多道批處理系統中，當作業調度程序按一定的算法調度到某個(些)作業時，便將它(們)裝入內存，為它(們)創建進程，并把它(們)插入就緒隊列中。
- 提供服務。當運行中的用戶程序提出某種請求后，系統將專門創建一個進程來提供用戶所需要的服務，
由用戶進程自己創建新進程
- 應用請求。使新進程以和其創建者進程并發運行的方式完成特定任務

進程創建過程：

系統中在出現了創建新進程的請求后，OS就調用進程創建原語 Creat創建一個新進程:

申請空白PC。為新進程申請獲得唯一的數字標識符，并從PCB 集合中索取一個空白 PCB。
為新進程分配其運行所需的資源，包括各種物理和邏輯資源。這些資源或從操作系統或僅從其父進程獲得。
例如，為新進程的程序和數據以及用戶棧分配必要的內存空間時，操作系統必須知道新進程所需內存的大小:
- 批處理作業，其大小可在用戶提出創建進程要求時提供;
- 應用進程創建子進程，也應是在該進程提出創建進程的請求中給出所需內存的大小;
- 交互型作業，用戶可以不給出內存要求而由系統分配一定的空間
- 如果新進程要共享某個已在內存的地址空間(即已裝入內存的共享段)，則必須建立相應的鏈接。
初始化進程控制塊(PCB)。PCB的初始化包括:
- 初始化標識信息，將系統分配的標識符和父進程標識符填入新PCB中;
- 初始化處理機狀態信息，使程序計數器指向程序的入口地址，使棧指針指向棧頂;
- 初始化處理機控制信息，將進程的狀態設置為就緒狀態或靜止就緒狀態；
  對于優先級，通常是將它設置為最低優先級，除非用戶以顯式方式提出高優先級要求。
如果進程就緒隊列能夠接納新進程，便將新進程插入就緒隊列。

2.3.3 進程的終止

觸發進程終止(Termination of Process)的事件：

正常結束，表示進程的任務已經完成，準備退出運行。
- 在批處理系統中, 可利用Holt指令。
- 在分時系統中，可利用Logs off指令。
異常結束，是指進程在運行時發生了某種異常事件，使程序無法繼續運行。常見的異常事件有:
- 越界錯，這是指程序所訪問的存儲區，已越出該進程的區域;
- 保護錯，指進程試圖去訪問一個不允許訪問的資源或文件，或者以不適當的方式進行訪問，例如，進程試圖去寫一個只讀文件；
- 非法指令，指程序試圖去執行一條不存在的指令。出現該錯誤的原因可能是程序錯誤地轉移到數據區，把數據當成了指令；
- 特權指令錯，指用戶進程試圖去執行一條只允許 OS執行的指令；
- 運行超時，指進程的執行時間超過了指定的最大值;
- 等待超時，指進程等待某事件的時間超過了規定的最大值;
- 算術運算錯，指進程試圖去執行一個被禁止的運算，例如，被0除；
- I/O 故障，這是指在 I/O過程中發生了錯誤等。
外界干預，是指進程應外界的請求而終止運行。這些干預有:
- 操作員或操作系統干預，指如果系統中發生了某事件，例如，發生了系統死鎖；
- 進程請求，指當子進程已完成父進程所要求的任務時，父進程可以提出請求結束該子進程;
- 因父進程終止，指當父進程終止時，它的所有子進程也都應當結束。因此，OS在終止父進程的同時，也將它的所有子孫進程終止

進程終止過程：

根據被終止進程的標識符，從PCB集合中檢索出該進程的PCB，從中讀出該進程的狀態;
若被終止進程正處于執行狀態，應立即終止該進程的執行(立即剝奪CPU，將CPU分配給其他進程)，并置調度標志為真，用于指示該進程被終止后應重新進行調度;
若該進程還有子孫進程，還應將其所有子孫進程也都予以終止，以防它們成為不可控的進程;
將被終止進程所擁有的全部資源或者歸還給其父進程，或者歸還給系統;
將被終止進程(PCB)從所在隊列(或鏈表)中移出，等待其它程序來搜集信息。

2.3.4 進程的阻塞與喚醒

觸發進程的阻塞與喚醒的事件：

向系統請求共享資源失敗。進程在向系統請求共享資源時，由于系統已無足夠的資源分配給它，此時進程因不能繼續運行而轉變為阻塞狀態。

例如，一進程請求使用打印機，由于系統已將打印機分配給其它進程，已無可以再可分配的打印機，這時請求者進程只能被阻塞，僅在其它進程釋放出打印機時，請求進程才被喚醒。
等待某種操作的完成。當進程啟動某種操作后，如果該進程必須在該操作完成之后才能繼續執行，則應先將該進程阻塞起來，以等待操作完成。

例如，進程啟動了某 I/O設備，如果只有在 I/O 設備完成了指定的 I/O 操作任務后進程才能繼續執行，則該進程在啟動了 I/O設備后便應自動進入阻塞狀態去等待。在I/O操作完成后，再由中斷處理程序將該進程喚醒。
新數據尚未到達。對于相互合作的進程，如果一個進程需要先獲得另一進程提供的數據后才能對該數據進行處理，只要其所需數據尚未到達，進程便只有阻塞。

例如，有兩個進程，進程 A用于輸入數據，進程B對輸入數據進行加工。假如A尚未將數據輸入完畢，則進程 B將因沒有所需處理的數據而阻塞;一旦進程A把數據輸入完畢，便可去喚醒進程 B。
等待新任務的到達。在某些系統中(特別是在網絡環境下的OS)，往往設置一些特定的系統進程，每當這種進程完成任務后便把自己阻塞起來，等待新任務的到來。

例如，在網絡環境中的發送進程，其主要任務是發送數據包，若已有的數據包已全部發送完成，而又無新的數據包發送，這時發送進程將把自己阻塞起來;僅當有新的數據包到達時，才將發送進程喚醒。

進程阻塞過程：

正在執行的進程，如果發生了觸發阻塞事件，進程便通過調用阻塞原語block將自己阻塞。【阻塞是進程自身的一種主動行為。】
進入block過程后，由于該進程還處于執行狀態，所以應先立即停止執行，把進程控制塊中的現行狀態由“執行”改為“阻塞”，并將 PCB插入阻塞隊列。【如果系統中設置了因不同事件而阻塞的多個阻塞隊列，則應將本進程插入到具有相同事件的阻塞隊列。】
進程上下文切換（Context Switching）- 運行環境信息：保留被阻塞進程的處理機狀態，按新進程的PCB中的處理機狀態設置CPU 的環境。
- 保存被阻塞進程的處理機狀態：操作系統保存該進程的執行上下文：包括程序計數器（PC）、寄存器狀態、程序狀態字（PSW）等關鍵信息，并將其存儲到該進程的進程控制塊PCB中，以便后續恢復執行。
- 加載新進程的 PCB 設置 CPU 環境：操作系統從就緒隊列中選擇一個進程進行調度，并將其 PCB 中存儲的上下文信息（如程序計數器、寄存器值等）加載到 CPU 中，從而為這個新調度的進程設置執行環境，使其能夠繼續或開始執行。
步驟：
- 找到要阻塞的進程對應的PCB
- 保護進程運行現場，將PCB狀態信息設置為“阻塞態"，暫時停止進程運行
- 將PCB插入相應事件的等待隊列

進程喚醒過程：

當被阻塞進程所期待的事件發生時，由有關進程(比如提供數據的進程)調用喚醒原語wakeup，將等待該事件的進程喚醒：

首先把被阻塞的進程從等待該事件的阻塞隊列中找到并移出
將其PCB中的現行狀態由阻塞改為就緒
再將該PCB插入到就緒隊列中，等待被調度。

block 原語和wakeup 原語是一對作用剛好相反的原語。在使用它們時，必須成對使用。

2.3.5 進程的掛起與激活

進程掛起過程：

OS將利用掛起原語suspend 將指定進程或處于阻塞狀態的進程掛起：

首先，檢查被掛起進程的狀態：
- 處于活動就緒狀態的進程，將其改為靜止就緒
- 處于活動阻塞狀態的進程，將其改為靜止阻塞;
然后，為了方便用戶或父進程考查該進程的運行情況，而把該進程的PCB復制到某指定的內存區域。
最后，若被掛起的進程正在執行，則轉向調度程序從就緒隊列中選擇另一個合適的進程開始執行

進程激活過程：

OS將利用激活原語active，將指定進程激活。

激活原語先將進程從外存調入內存，檢查該進程的現行狀態：
- 若是靜止就緒，便將之改為活動就緒;
- 若為靜止阻塞，便將之改為活動阻塞。
假如采用的是搶占調度策略，則每當有靜止就緒進程被激活而插入就緒隊列時，將由調度程序將被激活的進程與當前進程兩者的優先級進行比較：
- 如果被激活進程的優先級低，就不必重新調度;
- 如果被激活進程的優先級高，就需要立即剝奪當前進程的運行，把處理機分配給剛剛被激活的進程。

2.4 進程同步

2.4.1 進程同步的基本概念

進程同步機制的主要任務是：對多個相關進程在執行次序上進行協調，使并發執行的諸進程之間能按照一定的規則(或時序)共享系統資源，并能很好地相互合作，從而使程序的執行具有可再現性。
【多個相互關聯的進程同時運行時，需要對它們的執行順序進行安排和管理，讓它們按照一定的規矩（或時間順序）來使用系統的資源（比如內存、CPU、緩沖區等），并能夠很好地配合工作。這樣一來，不管程序運行多少次，結果都能保持一致，不會出現混亂或者錯誤。】

1. 兩種形式的制約關系

間接相互制約關系 - 臨界資源的互斥訪問：

定義：多個并發執行的程序因**共享系統資源（如CPU、打印機、磁帶機等）**而產生的相互制約關系。
特點：
- 需要對臨界資源進行互斥訪問，即同一時間只能有一個進程使用。
- 資源的分配由系統統一管理，進程需先申請資源，不能直接使用。

直接相互制約關系 - 進程間的協作與同步：

定義：某些應用程序創建多個進程，這些**進程為完成同一任務而合作，因共享特定資源（如緩沖區）**而產生的相互制約關系。
特點：
- 進程間存在協作關系，如輸入進程A向計算進程B提供數據。
- 當共享資源（如緩沖區）為空或滿時，進程會被阻塞，等待對方喚醒。

進程的異步性：

定義：進程在運行過程中是否能獲得CPU以及運行速度無法由自身控制，受系統調度和制約關系影響。
問題：
- 可能導致對共享變量或數據結構的訪問順序錯誤。
- 引發與時間相關的錯誤，導致進程每次執行結果不一致。
解決方法：
- 使用進程同步機制（如信號量、互斥鎖）協調進程執行順序。
- 確保進程對資源的訪問有序進行。

2. 臨界資源(Critical Resouce)

生產者-消費者(producer-consumer) 問題：

生產者進程與消費者進程能并發執行，在兩者之間設置了一個具有n個緩沖區的緩沖池，生產者進程將其所生產的產品放入一個緩沖區中；消費者進程可從一個緩沖區中取走產品去消費。

所有的生產者進程和消費者進程都是以異步方式運行的，但它們之間必須保持同步，既不允許消費者進程到一個空緩沖區去取產品，也不允許生產者進程向一個已裝滿產品且尚未被取走的緩沖區中投放產品。

一個數組 buffer來表示上述的具有n個緩沖區的緩沖池 - 循環緩沖。一個整型變量 counter，其初始值為 0

生產者：每投入一個產品時, 緩沖池 buffer 中暫存產品的數組單元指針 in加1【in=(in+1)%n - 循環緩沖】，counter 加1。

消費者：每取出一個產品時, 緩沖池 buffer 中已取走產品的空閑單元的數組單元指針 out加1【out=(out+1)%n - 循環緩沖】，counter 減1。

當(in+1)%n=out 時表示緩沖池滿；而in=out 則表示緩沖池空。

生產者和消費者兩進程共享下面的變量:

int in=0, out=0, count=0;
item buffer[n];

生產者：

void producer() {//在生產者進程中使用一局部變量nextp，用于暫時存放每次剛剛生產出來的產品;while(1){produce an item in nextp;...while (counter==n);buffer [in]= nextp;in = (in+1) % n;counter++;}
};

消費者：

void consumer()
{//在消費者進程中，則使用一個局部變量 nextc,用于存放每次要消費的產品。while(1){while (counter==0);nextc=buffer[out];out =(out+1)% n;counter--;consumer the item in nextc;}
};

生產者程序和消費者程序在分別看時都是正確的，而且兩者在順序執行時其結果也會是正確的，但若并發執行時就會出現差錯，問題就在于這兩個進程共享變量counter。

用機器語言實現時，形式描述：

生產者：
register1=counter；
register1=register1+1;
counter=register1;
消費者：
register2=counter；
register2=register2-1;
counter=register2;
假設:counter的當前值是5。

存在情況一：
register1=counter；(register1=5)
register1=register1+1; (register1=6)
counter=register1; (counter=6)
register2=counter；(register2=6)
register2=register2-1; (register2=5)
counter=register2; (counter=5)
存在情況二：
register1=counter；(register1=5)
register1=register1+1; (register1=6)
register2=counter；(register2=5)
register2=register2-1; (register2=4)
counter=register1; (counter=6)
counter=register2; (counter=4)
解決此問題的關鍵是應把變量counter 作為臨界資源處理，令生產者進程和消費者進程互斥地訪問變量counter。

3. 臨界區(critical section)

臨界區(critical section)：在每個進程中訪問臨界資源的那段代碼

進入區(entry section)：在臨界區前面增加一段用于進行檢查的代碼

檢查欲訪問的臨界資源是否正被訪問：
- 如果此刻臨界資源未被訪問，進程便可進入臨界區對該資源進行訪問，并設置它正被訪問的標志
- 如果此刻該臨界資源正被某進程訪問，則本進程不能進入臨界區。

退出區(exit section)：將臨界區正被訪問的標志恢復為未被訪問的標志，在臨界區后面加上的一段代碼

剩余區：除上述進入區、臨界區及退出區之外的其它部分的代碼

4.同步機制應遵循的規則

實現進程互斥地進入自己的臨界區，可用軟件方法，更多的是在系統中設置專門的同步機構來協調各進程間的運行。所有同步機制都應遵循下述準則:

空閑讓進。當無進程處于臨界區時，表明臨界資源處于空閑狀態，應允許一個請求進入臨界區的進程立即進入臨界區，可有效地利用臨界資源。
忙則等待。當已有進程進入臨界區時，表明臨界資源正在被訪問，因而其它試圖進入臨界區的進程必須等待，以保證對臨界資源的互斥訪問。
有限等待。對要求訪問臨界資源的進程，應保證在有限時間內能進入自己的臨界區，以免陷入“死等”狀態。
讓權等待。當進程不能進入自己的臨界區時，應立即釋放處理機，以免進程陷入“忙等”狀態。

2.4.2 硬件同步機制

在對臨界區進行管理時，可以將標志看做一個鎖。

初始時鎖是打開的。
每個要進入臨界區的進程必須先對鎖進行測試：
- 當鎖是未打開的時候，則必須等待，直至鎖被打開。
- 當鎖是打開的時候，則應立即把其鎖上，以阻止其它進程進入臨界區。

為防止多個進程同時測試到鎖為打開的情況，測試和關鎖操作必須是連續的，不允許分開進行。

1. 關中斷

關中斷是為了在臨界區代碼執行期間不會被中斷打斷，從而確保臨界區代碼的原子性。關中斷的具體作用包括：

避免進程切換：中斷可能導致進程切換（如時鐘中斷觸發調度），關中斷可以防止這種情況。
防止其他中斷干擾：硬件中斷（如磁盤IO完成）可能影響臨界區代碼的執行，關中斷可以屏蔽這些中斷。

關中斷的時機：在進入鎖測試之前關閉中斷，直到完成鎖測試并上鎖之后才能打開中斷。

關中斷的缺點:

濫用關中斷權力可能導致嚴重后果
關中斷時間過長，會影響系統效率，限制了處理器交叉執行程序的能力
關中斷方法也不適用于多CPU 系統，因為在一個處理器上關中斷并不能防止進程在其它處理器上執行相同的臨界段代碼。

2. 利用 Test-and-Set 指令實現互斥

借助一條硬件指令“測試并建立”指令 TS(Test-and-Set)，該指令是一條原語。

為每個臨界資源設置一個全局的布爾變量lock——代表該資源的狀態（可把它看成一把鎖）：

lock初值為FALSE，表示該臨界資源空閑。
進程在進入臨界區之前，先用TS指令測試lock：
- 如果其值為 FALSE，則表示沒有進程在臨界區內，可以進入。并將lock賦值 TRUE，關閉了臨界資源，使任何進程都不能進入臨界區；
- 如果其值為 TRUE，則表示該資源正在被使用。

偽代碼：

bool lock = false; // 全局鎖變量bool TestAndSet(bool *lock) {bool original_value = *lock; // 1. 測試 lock 的原始值*lock = true;               // 2. 設置 lock 為 truereturn original_value;      // 3. 返回原始值
}void enter_critical_section() {while (TestAndSet(&lock)) { // 忙等待// 如果 lock 為 true，等待}// 進入臨界區
}void leave_critical_section() {lock = false; // 釋放鎖
}

3. 利用 Swap 指令實現進程互斥

Swap指令稱為對換指令，在Intel 80x86 中又稱為XCHG指令。

為每個臨界資源設置一個全局的布爾變量lock，用于表示臨界區是否被占用。初始時為 FALSE，表示臨界區空閑。
每個進程在進入臨界區前，使用 Swap 指令將局部布爾變量key（ key = TRUE）與 lock 交換。根據交換后的 lock 值判斷能否進入臨界區。
- 如果交換后 lock = FALSE，說明臨界區空閑，進程可以進入。
- 如果交換后 lock = TRUE，說明臨界區已被占用，進程需要等待。

偽代碼：

bool lock = false; // 全局鎖變量void Swap(bool *a, bool *b) {bool temp = *a;*a = *b;*b = temp;
}void enter_critical_section() {bool key = true; // 局部變量do {Swap(&key, &lock); // 原子交換 key 和 lock 的值} while (key == true); // 如果 key 為 true，忙等待// 進入臨界區
}void leave_critical_section() {lock = false; // 釋放鎖
}

2.4.3 信號量機制

信號量其實就是一個變量(可以是一個整數,也可以是更復雜的記錄型變量)，可以用一個信號量來表示系統中某種資源的數量，比如:系統中只有一臺打印機，就可以設置一個初值為1的信號量

1. 整型信號量 —— P、V操作

整型信號量：一個用于表示資源數目的整型量S(整數)。除初始化外，僅能通過兩個標準的原子操作(Atomic Operation)wait(S)和signal(S)來訪問。

P 操作（荷蘭語 Proberen，意為“測試”）在英文中常被稱為 wait

wait(S) {while (S <= 0) {// 阻塞或忙等待}S--; // 申請資源，信號量減 1
}

V 操作（荷蘭語 Verhogen，意為“增加”）在英文中常被稱為 signal。

signal(S) {S++; // 釋放資源，信號量加 1// 喚醒等待該資源的進程
}

wait(S)和 signal(S)是兩個原子操作，即它們在執行時是不可中斷的。【在一個進程對信號量進行操作的過程中，其他進程不能同時對該信號量進行任何操作。】

存在的問題:不滿足“讓權等待”原則，會發生“忙等”

忙等（Busy Waiting）：線程/進程在等待某個條件（如鎖、資源、信號量）時，持續占用 CPU 資源，通過循環反復檢查條件是否滿足

讓權等待（Yield Waiting / Blocking Wait）：線程/進程在等待時主動釋放 CPU，進入阻塞狀態（如睡眠、掛起），讓其他線程/進程運行，直到條件滿足后再被喚醒。

2. 記錄型信號量

整型信號量：在整型信號量機制中的wait 操作，只要是信號量S≤0，就會不斷地測試。使進程處于“忙等”的狀態。

記錄型信號量：采取了“讓權等待”策略

增加一個用于代表資源數目的整型變量 value，還增加一個進程鏈表指針 list（隊列），用于存放因信號量不可用而被阻塞的進程。

typedef struct {int value,  //資源數目struct process_control block *list;  //鏈接等待的進程
}semaphore;

S->value 的初值表示系統中某類資源的數目，因而又稱為資源信號量

對它的每次 wait 操作，表示進程請求一個單位的該類資源，使系統中可供分配的該類資源數減少一個，因此描述為S->value–;
對它的每次 signal 操作，表示執行進程釋放一個單位資源，使系統中可供分配的該類資源數增加一個，因此描述為S->value++。

【“讓權等待”準則】：

當 S->value < 0時，表示該類資源已分配完畢，因此進程應調用 block 原語進行自我阻塞，放棄處理機，并插入到信號量鏈表S->list 中。此時 S->value 的絕對值表示在該信號量鏈表中已阻塞進程的數目。

若signal 操作加1后仍是S-> value ≤ 0，則表示在該信號量鏈表中仍有等待該資源的進程被阻塞，還應調用wakeup 原語，將S->list 鏈表中的第一個等待進程喚醒。

如果S->value 的初值為1，表示只允許一個進程訪問臨界資源，此時的信號量轉化為互斥信號量，用于進程互斥。

// 定義信號量的 wait 操作
void wait(semaphore *S) {// 將信號量的值減 1，表示占用一個資源S->value--;              // 如果信號量的值小于 0，表示沒有可用資源if (S->value < 0) {      // 將當前進程阻塞，并將其加入到信號量的等待隊列中 - block 原語進行自我阻塞(進程從運行態→阻塞態)，主動放棄處理機block(S->list);       }
}// 定義信號量的 signal 操作
void signal(semaphore *S) {// 將信號量的值加 1，表示釋放一個資源S->value++;               // 如果信號量的值小于等于 0，表示有進程在等待資源if (S->value <= 0) {      // 從信號量的等待隊列中喚醒一個進程 -  wakeup 原語喚醒等待隊列中的第一個進程(被喚醒進程從阻塞態→就緒態)wakeup(S->list);     }
}

若考試中出現 P(S)、V(S)的操作，除非特別說明，否則默認s為記錄型信號量。

3. AND型信號量

一個進程往往需要獲得多個共享資源后方能執行其任務；

AND同步機制的基本思想是: 將進程在整個運行過程中需要的所有資源，一次性全部地分配給進程，待進程使用完后再一起釋放。【對若干個臨界資源的分配采取原子操作方式:要么把它所請求的資源全部分配到進程，要么一個也不分配。】從而避免了死鎖情況的發生。

死鎖：

兩個進程A和B，它們都要求訪問共享數據（臨界資源）D和E，為這兩個數據分別設置用于互斥的信號量 Dmutex 和 Emutex，并令它們的初值都是1。相應地，在兩個進程中都要包含兩個對Dmutex和Emutex的操作：

process A:
wait(Dmutex);
wait(Emutex);
process B:
wait(Emutex);
wait(Dmutex);
若進程A和B按下述次序交替執行wait操作:
process A:wait(Dmutex);   于是Dmutex=0
process B:wait(Emutex);    于是Emutex=0
process A: wait(Emutex);    于是Emutex=-1A阻塞
process B:wait(Dmutex);    于是Dmutex=-1 B阻塞
最后，進程A和B就將處于僵持狀態。在無外力作用下，兩者都將無法從僵持狀態中解脫出來。此時的進程A和B已進入死鎖狀態

Swait(S1, S2, ..., Sn)
{while (TRUE){if (S1 >= 1 && S2 >= 1 && ... && Sn >= 1){// 所有資源都可用，分配資源for(i = 1; i <= n; i++) Si--;break; // 退出循環，任務繼續執行}else{// 有資源不可用，阻塞任務// 將任務加入等待隊列，并釋放 CPUblock();}}
}Ssignal(S1, S2, ..., Sn)
{for(i = 1; i <= n; i++){Si++; // 釋放資源}// 喚醒等待這些資源的所有任務wakeup_all();
}

4. 信號量集

信號量集核心思想：當進程申請某類臨界資源時，在每次分配之前，都必須測試資源的數量，判斷是否大于可分配的下限值，決定是否予以分配。

信號量S_i的資源分配下限 t_i ; 進程對該資源的需求值為d_i，即表示資源占用量

記錄型信號量機制：每次只能對某類臨界資源進行一個單位的申請或釋放。分配下限t_i = 1， 需求值為d_i = 1，進行S_i=S_i - 1操作。

信號量集：資源分配下限t_i，要求S_i ≥ t_i，否則不予分配。進程對該資源的需求值為d_i，進行S_i=S_i - d_i操作。

信號量對應的Swait 和 Ssignal 格式為: Swait(S_i, t_i, d_i, …, S_n, t_n, d_n); Ssignal(S_i, d_i, …, S_n, d_n);

一般“信號量集”還有下面幾種特殊情況:

Swait(S,d,d)。此時在信號量集中只有一個信號量S，但允許它每次申請d個資源, 當現有資源數少于d時，不予分配。
Swait(S,1,1)。此時的信號量集已蛻化為一般的記錄型信號量(S>1時)或互斥信號量(S =1 時)。
Swait(S,1,0)。當S≥1時，允許多個進程進入某特定區；當S=0后，將阻止任何進程進入特定區。

2.4.4 信號量的應用

利用信號量實現進程互斥 - 互斥問題，信號量初值為1

互斥信號量mutex - 進入臨界區的名額，設其初始值為1。取值范圍為(-1,0,1)。

當mutex=1時，表示兩個進程皆未進入需要互斥的臨界區;
當mutex=0時,表示有一個進程進入臨界區運行,另外一個必須等待，掛入阻塞隊列;
當mutex=-1時，表示有一個進程正在臨界區運行，另外一個進程因等待而阻塞在信號量隊列中，需要被當前已在臨界區運行的進程退出時喚醒。

注意：wait(mutex)和signal(mutex)必須成對地出現：

缺少wait(mutex)將會導致系統混亂，不能保證對臨界資源的互斥訪問
缺少signal(mutex)將會使臨界資源永遠不被釋放，從而使因等待該資源而阻塞的進程不能被喚醒

注意：對不同的臨界資源需要設置不同的互斥信號量。

利用信號量實現前趨關系 - 本質是多級同步問題，信號量初值為0

設有兩個并發執行的進程P₁和P₂。P₁中有語句S₁;P₂中有語句S₂。希望在S₁執行后再執行S₂。為實現這種前趨關系，只需使進程P₁和 P₂共享一個公用信號量S，并賦予其初值為0，將 signal(S)操作放在語句S1后面，而在S2語句前面插入 wait(S)操作，即

在進程P₁中，用S₁; signal(S);
在進程P₂中，wait(S); 用 S₂;

由于S被初始化為0,這樣,若P₂先執行必定阻塞,只有在進程P₁執行完S₁;signal(S); 操作后使S增為1時，P₂進程方能成功執行語句S₂。

S₁→S₂，S₁→S₃ 的前趨關系, 應分別設置信號量a和b，S₂→S₄，S₂→S₅，S₃→S₆，S₄→S₆和S₅→S₆，設置信號量c，d，e，f，g。
p1() { S1;   signal(a);   signal(b);}
p2() { wait(a);   S2;   signal(c);   signal(d); }
p3() { wait(b);   S3;   signal(e);}
p4() { wait(c);   S4;   signal(f);}
p5() { wait(d);   S5;   signal(g);}
p6() { wait(e);   wait(f);   wait(g);    S6;}

在“前操作”之后執行 V(S)；在“后操作”之前執行 P(S)

2.4.5 管程(Monitors)機制

1. 管程

管程定義： 代表共享資源的數據結構 以及 由對該共享數據結構實施操作的一組過程所組成的資源管理程序共同構成了一個操作系統的資源管理模塊

【將某個資源的所有信息（數據結構）以及對資源的操作（比如讀、寫、修改等）都打包在一起，并且提供了統一的訪問方式。】

管程由四部分組成:

管程的組成部分	類的組成部分	詳細描述
①管程的名稱	類名	標識這個管程是做什么的
②局部于管程的共享數據結構說明	屬性（變量）	管程內部的共享變量，類似于類的屬性，用來描述管程管理的資源狀態。
③對數據結構進行操作的一組過程	方法	管程提供的操作接口，類似于類的方法/函數，用來對共享資源進行操作。
④對共享數據設置初始值的語句	構造函數或初始化塊	管程創建時對共享數據進行初始化，類似于類的構造函數或初始化塊。

管程的基本特征:

局部于管程的數據只能被局部于管程的過程所訪問
一個進程只有通過調用管程內的過程(管程提供的特定入口)才能進入管程訪問共享數據 - 通過管程的過程間接修改管程的數據結構
每次僅允許一個進程在管程內執行某個內部過程。- 互斥特性是由編譯器負責實現

管程主要有以下特性:

模塊化，即管程是一個基本程序單位，可以單獨編譯;
抽象數據類型，指管程中不僅有數據，而且有對數據的操作;
信息掩蔽，指管程中的數據結構只能被管程中的過程訪問，這些過程也是在管程內部定義的，供管程外的進程調用，而管程中的數據結構以及過程(函數)的具體實現外部不可見。

封裝

管程將共享資源的數據結構及其操作邏輯封裝在內部，外部只能通過管程提供的接口間接訪問資源。這種機制隱藏了實現細節，實現了資源的集中管理和安全性。

互斥訪問

管程通過同步機制確保同一時間只有一個進程進入管程并操作資源。如果有多個進程想操作資源，管程會讓他們排隊。進程請求訪問時，管程檢查資源狀態：若資源被占用，則進程等待；若資源空閑，則進程進入。這避免了競爭條件，保證了資源的互斥訪問。

管程和進程不同:

區別點	進程	管程
數據結構	定義私有數據結構（如 PCB）	定義公共數據結構（如消息隊列）
操作方式	通過順序程序執行操作數據結構	主要進行同步操作和初始化操作數據結構
目的	實現系統的并發性	解決共享資源的互斥使用問題
工作方式	主動工作方式，通過調用管程中的過程操作共享數據結構	被動工作方式，由進程調用其內部過程
并發性	進程之間能并發執行	管程不能與其調用者并發
生命周期	動態性，由創建而誕生，由撤銷而消亡	靜態性，作為操作系統的資源管理模塊，供進程調用

2. 條件變量

條件變量：主要用于處理在管程內被阻塞或掛起的進程。一個進程被阻塞或掛起的條件(原因)可有多個，因此在管程中設置了多個條件變量，對這些條件變量的訪問只能在管程中進行。

管程中對每個條件變量都須予以說明，其形式為: condition x,y;
對條件變量的操作僅僅是 wait 和 signal，可表示為 x.wait 和 x.signal；
- x.wait: 正在調用管程的進程因x條件需要被阻塞或掛起，則調用 x.wait , 將自己插入到x條件的等待隊列上，并釋放管程，直到x條件變化。此時其它進程可以使用該管程。
- x.signal: 正在調用管程的進程發現x條件發生了變化，則調用 x.signal，重新啟動一個因x條件而阻塞或掛起的進程，如果存在多個這樣的進程，則選擇其中的一個，如果沒有，繼續執行原進程，而不產生任何結果。
每個條件變量保存了一個鏈表, 用于記錄因該條件變量而阻塞的所有進程。

假設有兩個進程 P 和 Q：

進程 Q 因為某個條件 x 不滿足而被阻塞了。
進程 P 運行在管程中，執行了 x.signal() 操作，喚醒了等待條件 x 的進程 Q。

問題是：進程 P 和進程 Q 都被激活了，該讓誰先執行，誰等待？

方式一：P 等待，Q 先執行

P 執行 x.signal() 后，立即把自己掛起，進入等待狀態。
Q 被喚醒后，繼續執行，直到 Q 離開管程或因為其他條件再次被阻塞。
然后，P 才能繼續執行。
Hoare 管程采用這種方式。

方式二：P 先執行，Q 等待

P 執行 x.signal() 后，繼續執行，直到 P 離開管程或因為其他條件被阻塞。
然后，Q 才能被重新啟動并執行。
MESA 管程采用這種方式。

方式三：折中 - 規定 signal 操作必須是管程中過程的最后一個操作。

P 執行 x.signal() 后，必須立即退出管程，沒有其他操作了。
Q 被喚醒后，可以立即執行，而不需要和 P 競爭。
Hansan 管程采用這種方式。

2.5 經典進程的同步問題

2.5.1 生產者-消費者問題（Producer-Consumer Problem）

在這里插入圖片描述

1. 利用記錄型信號量解決生產者-消費者問題

// 全局變量定義
int in = 0, out = 0;          // in 和 out 是緩沖區的索引，in 指向下一個空位，out 指向下一個待消費的位置
item buffer[n];               // 緩沖區，大小為 n
semaphore mutex = 1;          // 互斥信號量，實現對緩沖區的互斥訪問
semaphore empty = n;          // 空槽位信號量，初始值為緩沖區的大小 n  -  同步信號量，表示空閑緩沖區的數量
semaphore full = 0;           // 滿槽位信號量，初始值為 0 - 同步信號量，表示產品的數量，也即非空緩沖區的數量// 生產者函數
void producer() {do {// 生產一個 itemitem nextp = produce_item();  // 假設 produce_item() 是一個生產 item 的函數wait(empty);                 // 消耗一個空閑緩沖區wait(mutex);                 // 進入臨界區，實現對緩沖區的互斥訪問 - ***實現互斥的P操作一定要在實現同步的P操作之后***buffer[in] = nextp;          // 將生產的 item 放入緩沖區in = (in + 1) % n;           // 更新 in 索引，循環使用緩沖區signal(mutex);               // 離開臨界區，釋放互斥鎖signal(full);                // 增加滿槽位信號量，通知消費者有新的 item 可用 - 增加一個產品} while (TRUE);                  // 無限循環
}// 消費者函數
void consumer() {do {wait(full);                  //  消耗一個產品(非空緩沖區)wait(mutex);                 // 進入臨界區，實現對緩沖區的互斥訪問item nextc = buffer[out];    // 從緩沖區中取出一個 itemout = (out + 1) % n;         // 更新 out 索引，循環使用緩沖區signal(mutex);               // 離開臨界區，釋放互斥鎖signal(empty);               // 增加空槽位信號量，通知生產者有空槽位可用 - 增加一個空閑緩沖區consume_item(nextc);         // 消費 item（假設 consume_item() 是一個消費 item 的函數）} while (TRUE);                  // 無限循環
}// 主函數
void main() {// 并發執行生產者和消費者cobeginproducer();                  // 啟動生產者consumer();                  // 啟動消費者coend
}

1. empty = n

表示初始時緩沖區中有 n 個空槽位（即 n 個資源未被使用）。
生產者生產一個 item 時會占用一個空槽位，因此需要先 wait(empty)，檢查是否有空槽位可用。
如果 empty > 0，生產者可以繼續生產；如果 empty = 0，表示緩沖區已滿，生產者需要等待。

2. full = 0

表示初始時緩沖區中沒有已生產的 item（即沒有資源被操作）。
消費者消費一個 item 時會釋放一個空槽位，因此需要先 wait(full)，檢查是否有已生產的 item 可以消費。
如果 full > 0，消費者可以繼續消費；如果 full = 0，表示緩沖區為空，消費者需要等待。

實現互斥的P操作一定要在實現同步的P操作之后

2. 利用 AND 信號量解決生產者-消費者問題

// 定義共享變量和信號量
int in = 0, out = 0;                // 生產者和消費者的索引
item buffer[n];                     // 容量為 n 的緩沖區
semaphore mutex = 1, empty = n, full = 0; // 互斥信號量 mutex，空槽位信號量 empty，已生產項信號量 full// 生產者函數
void producer() {do {// 生產一個 itemitem nextp = produce_item();  // 假設 produce_item() 是一個生產 item 的函數// 等待空槽位和互斥鎖Swait(empty, mutex);         // 等待空槽位（empty--），同時獲取互斥鎖（mutex--）// 將 item 放入緩沖區buffer[in] = nextp;in = (in + 1) % n;           // 更新生產者索引// 釋放互斥鎖和增加已生產項Ssignal(mutex, full);        // 釋放互斥鎖（mutex++），并增加已生產項（full++）} while (TRUE);                  // 無限循環，持續生產
}// 消費者函數
void consumer() {do {// 等待已生產項和互斥鎖Swait(full, mutex);          // 等待已生產項（full--），同時獲取互斥鎖（mutex--）// 從緩沖區取出 itemitem nextc = buffer[out];out = (out + 1) % n;         // 更新消費者索引// 釋放互斥鎖和增加空槽位Ssignal(mutex, empty);       // 釋放互斥鎖（mutex++），并增加空槽位（empty++）// 消費 itemconsume_the_item(nextc);     // 模擬消費 item} while (TRUE);                  // 無限循環，持續消費
}

用 Swait(empty，mutex)來代替 wait(empty)和 wait(mutex);
用 Ssignal(mutex, full)來代替 signal(mutex)和 signal(full);
用 Swait(full,mutex)代替 wait(full)和 wait(mutex)；
用 Ssignal(mutex，empty)代替Signal(mutex)和 Signal(empty)。

3. 利用管程解決生產者-消費者問題

// 定義生產者消費者問題的 Monitor —— Monitor 內部的所有方法是互斥執行的，即同一時刻只能有一個線程執行 Monitor 中的方法。
Monitor ProducerConsumer {item buffer[N];         // 容量為 N 的緩沖區int in, out;    // 共享變量：緩沖區的讀寫索引condition notfull;      // 條件變量：緩沖區未滿condition notempty;     // 條件變量：緩沖區不為空int count;          // 緩沖區中當前的 item 數量 - 由于 Monitor 互斥性，count 的修改和訪問不會發生競爭條件，即使它在多個線程之間共享。public:// 向緩沖區中放入 itemvoid put(item x) {// 如果緩沖區已滿，則等待 "未滿" 條件if (count >= N) {cwait(notfull);   // 阻塞當前線程，等待緩沖區未滿}// 將 item 放入緩沖區buffer[in] = x;in = (in + 1) % N;    // 更新生產者索引，實現循環緩沖區count++;              // 增加緩沖區中的 item 數量// 通知消費者緩沖區不為空csignal(notempty);    // 喚醒等待 "不為空" 條件的線程}// 從緩沖區中取出 itemvoid get(item &x) {// 如果緩沖區為空，則等待 "不為空" 條件if (count <= 0) {cwait(notempty);  // 阻塞當前線程，等待緩沖區不為空}// 從緩沖區中取出 itemx = buffer[out];out = (out + 1) % N;  // 更新消費者索引，實現循環緩沖區count--;              // 減少緩沖區中的 item 數量// 通知生產者緩沖區未滿csignal(notfull);     // 喚醒等待 "未滿" 條件的線程}// 初始化緩沖區和條件變量ProducerConsumer() {in = 0;out = 0;count = 0;}
} PC;  // 定義 Monitor 實例 PC// 生產者線程函數
void producer() {item x;  // 定義 item 變量 x，用于存儲生產的 itemwhile (TRUE) {  // 無限循環，持續生產 itemproduce an item in x;  // 生產一個 item 并存入 xPC.put(x);             // 將 item x 放入緩沖區}
}// 消費者線程函數
void consumer() {item x;  // 定義 item 變量 x，用于存儲從緩沖區中取出的 itemwhile (TRUE) {  // 無限循環，持續消費 itemPC.get(x);             // 從緩沖區中取出一個 item 并存入 xconsume the item in x; // 消費 item x}
}// 主函數
void main() {cobegin                  // 啟動并發執行producer();          // 啟動生產者線程consumer();          // 啟動消費者線程coend                    // 并發執行結束
}

生產者線程 (producer)：
- 生產者不斷生產 item，并將其放入緩沖區。
- 使用 PC.put(x) 方法將生產出的 item x 放入緩沖區。
消費者線程 (consumer)：
- 消費者不斷從緩沖區中取出 item，并消費它。
- 使用 PC.get(x) 方法從緩沖區中取出 item x。
通過 Monitor PC 保證了緩沖區的線程安全訪問。

條件變量的使用：
- 使用 cwait 阻塞線程，等待條件滿足。
- 使用 csignal 喚醒等待條件的線程。

2.5.2 哲學家進餐問題（Dining Philosophers Problem）

問題設定

場景：5 位哲學家圍坐在一張圓桌旁，桌上擺放 5 根筷子（每兩位哲學家之間共享一根）。
哲學家行為：
- 思考（Thinking）：哲學家長時間思考，不占用任何筷子。
- 饑餓（Hungry）：哲學家感到饑餓，試圖拿起 左右兩邊最靠近他的筷子 準備進餐。
- 進餐（Eating）：如果成功拿到兩根筷子，哲學家開始進餐，進餐結束后放下筷子繼續思考。【只有在拿到兩只筷子時才能進餐】
每個哲學家進程需要同時持有兩個臨界資源才能開始吃飯。需要避免臨界資源分配不當造成的死鎖現象

在這里插入圖片描述

1. 利用記錄型信號量解決哲學家進餐問題

//--------------------有死鎖風險------------------
// 定義5個信號量，分別表示5根筷子，初始值均為1（表示筷子可用）
semaphore chopstick[5] = {1, 1, 1, 1, 1};// 哲學家i的行為
do {// 嘗試獲取左邊的筷子（i號筷子）wait(chopstick[i]);// 嘗試獲取右邊的筷子（(i+1)%5號筷子）wait(chopstick[(i + 1) % 5]);// 哲學家成功拿到兩根筷子，開始進餐eat();// 進餐結束后，釋放左邊的筷子（i號筷子）signal(chopstick[i]);// 進餐結束后，釋放右邊的筷子（(i+1)%5號筷子）signal(chopstick[(i + 1) % 5]);// 哲學家開始思考think();
} while (TRUE); // 無限循環

假如五位哲學家同時饑餓而各自拿起左邊的筷子時，就會使五個信號量chopstick均為0;當他們再試圖去拿右邊的筷子時，都將因無筷子可拿而無限期地等待。對于這樣的死鎖問題，可采取以下幾種解決方法:

至多只允許有四位哲學家同時去拿左邊的筷子

Semaphore philospher=4;
Semaphore chopsticks[5]={1,1,1,1,1};
Philospher i(){while(1){P(philospher);P(chopsticks[i];P(chopsticks[(i+1)%5];開始進餐;V(chopsticks[i]);V(chopsticks[(i+1)%5]);V(philospher);
}

一次僅有一位哲學家可以訪問臨界資源筷子 - 一個哲學家在拿筷子拿到一半時被阻塞，也不會有別的哲學家會繼續嘗試拿筷子。

semaphore chopsticks[5]={1,1,1,1,1};//五個哲學家進程
semaphore mutex=1;    //互斥資源，設置的互斥信號量
philosopher i(){while(1){//用p v操作框起來，保證了左右兩邊都有筷子P(mutex);P(chopsticks[i]);//去左邊的筷子P(chopsticks[(i+1)%5]);//取右邊的筷子       開始進餐；V(mutex);       //先釋放互斥鎖可以保證其他哲學家取用筷子不會被阻礙V(chopsticks[i]);v(chopsticks[(i+1)%5]);思考；
}

規定奇數號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子;而偶數號哲學家則相反。

semaphore chopsticks[5]={1,1,1,1,1};//五個哲學家進程
void process(int i){while(1){if(i%2==0)//偶數號先拿右邊的筷子{P(chopsticks[(i+1)%5]);//取右邊的筷子P(chopsticks[i]);//去左邊的筷子開始進餐；V(chopsticks[(i+1)%5]);V(chopsticks[i]);}else  //奇數號先拿左邊的筷子{P(chopsticks[i]);//去左邊的筷子P(chopsticks[(i+1)%5]);//取右邊的筷子開始進餐；V(chopsticks[i]);V(chopsticks[(i+1)%5]);    }   }
}

2. 利用 AND 信號量解決哲學家進餐問題

// 聲明并初始化5個信號量，表示5根筷子，初始狀態均為可用（1）
semaphore chopstick[5] = {1, 1, 1, 1, 1};// 哲學家i的循環行為
do {// 思考階段think();// 同步請求兩根筷子（防止死鎖的關鍵點）// Sswait(chopstick[(i+1)%5], chopstick[i]) 是一個原子操作：// 1. 先嘗試獲取右邊的筷子（(i+1)%5號）// 2. 再嘗試獲取左邊的筷子（i號）// 如果任一筷子不可用則阻塞，避免循環等待Sswait(chopstick[(i + 1) % 5], chopstick[i]);// 成功獲取兩根筷子后開始進餐eat();// 原子性地同時釋放兩根筷子// Ssignal會按請求順序的逆序釋放資源：// 1. 先釋放左邊的筷子（i號）// 2. 再釋放右邊的筷子（(i+1)%5號）Ssignal(chopstick[(i + 1) % 5], chopstick[i]);} while (TRUE);  // 無限循環

2.5.3 讀者-寫者問題（Reader-Writer Problem）

問題描述

在這里插入圖片描述

與消費者進程不同,讀者進程在讀數據后并不會將數據清空，并不會改變數據，因此多個讀者可同時訪問共享數據

讀進程與寫進程同時共享數據，可能導致讀出的數據不一致的問題

兩個寫進程同時共享數據，可能導致數據錯誤覆蓋的問題

多個 讀者（Readers） 和多個 寫者（Writers） 共享同一個數據對象（如文件、數據庫、共享內存等）。
讀者：只讀取數據，不會修改數據（可并發執行）。
寫者：會寫入數據，必須獨占訪問（互斥訪問）。
關鍵約束條件：
1. 讀寫互斥：一個寫者不能和任何讀者或其他寫者同時訪問數據。
2. 優先級：
  - 讀者優先：只要存在讀者，寫者會被阻塞。
    ? 讀者不會等待：多個讀者可以并發讀，無需互斥。
    ? 可能導致寫者饑餓：如果一直有新的讀者到來，寫者可能永遠無法執行。
    🔹 適用場景：讀操作遠多于寫操作，且要求高讀取并發性（如數據庫查詢）。
  - 寫者優先：當有寫者在等待時，新來的讀者必須等待正在執行的讀者完成，舊讀者完成后，寫者先執行，之后才允許新讀者進入。
    
    ? 寫者不會被餓死：只要有寫者在等待，新讀者就不能進入臨界區。
    ? 讀者可能等待較久：但不會完全餓死。
    🔹 適用場景：寫操作頻率較高，且要求數據一致性（如日志系統、內存緩存）。
  - 公平策略：通過FIFO調度讀者和寫者——即讀者和寫者按到達順序執行，確保公平性。
    🔹 適用場景：讀寫比例均衡的系統

1. 利用記錄型信號量解決讀者-寫者問題

//------------------------------讀者優先--------------------------
semaphore rmutex = 1;   // 保護 readcount 的互斥鎖（讀者間互斥）
semaphore wmutex = 1;   // 讀寫互斥鎖（保證寫者獨占）
int readcount = 0;      // 當前正在讀取的讀者數量//--------------------- 讀者線程 ---------------------//
void reader() {do {// 1. 進入臨界區，保護 readcountwait(rmutex);        if (readcount == 0)  // 如果是第一個讀者，需要占用寫鎖wait(wmutex);     // 阻止寫者進入readcount++;          // 增加讀者計數signal(rmutex);       // 釋放 readcount 鎖// 2. 執行讀操作（此時允許多個讀者并發讀）/* perform read operation */  // 3. 離開臨界區，更新 readcountwait(rmutex);         readcount--;          if (readcount == 0)   // 如果是最后一個讀者，釋放寫鎖signal(wmutex);    // 允許寫者進入signal(rmutex);       } while (TRUE);           // 循環執行
}//--------------------- 寫者線程 ---------------------//
void writer() {do {wait(wmutex);          // 獲取寫鎖（獨占訪問）/* perform write operation */  // 執行寫操作signal(wmutex);        // 釋放寫鎖} while (TRUE);            // 循環執行
}//--------------------- 主程序 ---------------------//
void main() {cobegin                     // 并發執行讀者和寫者reader();writer();coend
}

信號量作用：
- rmutex：保護 readcount 變量，防止多個讀者同時修改導致競爭。
  - 互斥修改 readcount
    - 通過 wait(rmutex)/signal(rmutex) 確保同一時間只有一個線程能修改 readcount。
  - 避免重復獲取 wmutex
    - 第一個讀者（readcount == 0）會獲取 wmutex，后續讀者跳過這一步。
    - 最后一個讀者（readcount == 0）會釋放 wmutex。
    - rmutex 保證這一判斷和操作的原子性，防止多個讀者競爭 wmutex。
- wmutex：實現讀寫互斥，保證寫者獨占訪問
讀者邏輯：
- 進入時：第一個讀者獲取 wmutex，后續讀者只需遞增 readcount。
- 退出時：最后一個讀者釋放 wmutex，允許寫者執行。
寫者邏輯：
- 必須獨占 wmutex，因此會等待所有讀者完成（readcount == 0）

2. 利用信號量集解決讀者-寫者問題

增加了一個限制，即最多只允許RN個讀者同時讀

//------------------------------寫者優先--------------------------
int RN;                   // 最大支持的讀者數量
semaphore L = RN;         // 控制讀者并發數（初始值為RN）
semaphore mx = 1;         // 寫鎖（保證寫操作的互斥性）// ========== 讀者線程 ==========
void reader() {do {// Swait(L,1,1): 申請一個L信號量（若L≥1則減1，否則阻塞）Swait(L, 1, 1);           // 占用一個讀者名額// Swait(mx,1,0): 檢查mx是否為0（不阻塞，僅測試）Swait(mx, 1, 0);          // 檢查是否有寫者正在寫/* 執行讀操作（多個讀者可并發讀） */// Ssignal(L,1): 釋放一個L信號量（讀者退出）Ssignal(L, 1);            // 釋放讀者名額} while (TRUE);
}// ========== 寫者線程 ==========
void writer() {do {// Swait(mx,1,1; L,RN,0): 同時申請mx鎖并檢查無讀者（L==RN）Swait(mx, 1, 1; L, RN, 0);  // 1. 獨占mx鎖；2. 確保無活躍讀者（L==RN）/* 執行寫操作（寫者獨占訪問） */// Ssignal(mx,1): 釋放mx鎖Ssignal(mx, 1);            // 允許其他寫者或讀者進入} while (TRUE);
}// ========== 主程序 ==========
void main() {cobeginreader();  // 啟動讀者線程writer();  // 啟動寫者線程coend
}

RN
- 表示系統允許的 最大讀者并發數，初始化時 L = RN 表示所有讀者名額可用。
Swait(L,1,1)（讀者線程）
- 申請一個讀者名額：若 L ≥ 1 則減少 L，否則阻塞。
- 保證當前活躍讀者數 不超過 RN。
Swait(mx,1,0)（讀者線程）
- 非阻塞檢查寫鎖：僅測試 mx 是否為 0（無寫者），不影響信號量值。
- 確保 無寫者正在寫 時才允許讀。
Swait(mx,1,1; L,RN,0)（寫者線程）
- 同時滿足兩個條件：
  - mx = 1：獲取寫鎖（保證互斥）。
  - L = RN：確保 所有讀者名額均未被占用（即無活躍讀者）。
- 寫者優先于新讀者（防止讀者饑餓）。
  寫者通過 Swait(mx,1,1; L,RN,0) 嚴格搶占資源
  - 寫者在進入臨界區時，必須同時滿足兩個條件：
    - (1) 獲得寫鎖 mx（保證互斥）。
    - (2) 檢查讀者信號量 L == RN（即當前沒有活躍的讀者）。
  - 這意味著：
    - 只要有讀者在讀寫者必須等待（L < RN 時寫者會被阻塞）。
    - 但在寫者競爭時，新的讀者無法搶占資源（因為 L 已經被占用）。
Ssignal 操作
- 讀者退出時釋放 L，允許新讀者進入。
- 寫者退出時釋放 mx，允許其他寫者或讀者競爭。

2.5.4 可生產單種產品的多生產者-多消費者問題

在這里插入圖片描述

2.5.5 吸煙者問題 - 可生產多種產品的單生產者-多消費者問題

在這里插入圖片描述

2.6 進程通信

進程通信(Inter-Process Communication, IPC)是指進程之間的信息交換。

2.6.1 進程通信的類型

高級通信機制可歸結為四大類: 共享存儲器系統、管道通信系統、消息傳遞系統以及客戶機-服務器系統。

1、共享存儲器系統 (Shared-Memory System)

相互通信的進程共享某些數據結構或共享存儲區，進程之間能夠通過這些空間進行通信。可分成以下兩種類型:

低級通信：基于共享數據結構的通信方式。【如在生產者-消費者問題中的有界緩沖區】
操作系統僅提供共享存儲器，由程序員負責對公用數據結構的設置及對進程間同步的處理。僅適于傳遞相對少量的數據，通信效率低下。
高級通信：基于共享存儲區的通信方式。
需要通信的進程在通信前，先向系統申請獲得【共享存儲區域：在內存中劃出的且所有進程都可進行讀或寫交換信息的，且訪問是互斥的】共享存儲區域中的一個分區，并將其附加到自己的地址空間中，便可對其中的數據進行正常讀、寫交換信息，實現通信；讀寫完成或不再需要時，將其歸還給共享存儲區。數據的形式和位置甚至訪問控制都是由進程負責，而不是OS。可傳輸大量數據。

在這里插入圖片描述

2、管道(pipe)通信系統

“管道”，是指用于連接一個讀進程和一個寫進程以實現它們之間通信的一個共享文件，又名 pipe 文件。可有效地傳送大量數據。
本質是在內存中開辟一個大小固定的內存緩沖區，讀寫數據先進先出。管道是循環隊列

輸入的發送進程(即寫進程)：以字符流形式將大量的數據送入管道;
輸出的接收進程(即讀進程)：從管道中接收(讀)數據。

管道機制必須提供以下三方面的協調能力:

①互斥：即當一個進程正在對 pipe 執行讀/寫操作時，其它(另一)進程必須等待。【各進程要互斥地訪問管道(由操作系統實現)】
②同步：
- 指當寫(輸入)進程把一定數量的數據寫入 pipe，便去睡眠等待，直到讀(輸出)進程取走數據后再把它喚醒。
  寫進程往管道里寫數據：如果管道滿了，寫進程會"阻塞"（睡眠等待），等讀進程取走數據后(管道未滿)，就可 “叫醒”（喚醒）繼續寫。
- 當讀進程讀一空 pipe 時，也應睡眠等待，直至寫進程將數據寫入管道后才將之喚醒。
  讀進程從管道里讀數據：如果管道是空的，讀進程會 “阻塞”（睡眠等待），等寫進程往里寫了新數據后(管道未空)，就可 “叫醒”（喚醒）繼續讀。
③確定對方是否存在：只有確定了對方已存在時才能進行通信。

管道只能采用華雙工通信，某一時間段內只能實現單向的傳輸。如果要實現雙向同時通信，則需要設置兩個管道。

管道中的數據一旦被讀出，就徹底消失。因此，當多個進程讀同一個管道時，可能會錯亂。對此，通常有兩種解決方案:①一個管道允許多個寫進程，一個讀進程(2014年408真題高教社官方答案);②允許有多個寫進程，多個讀進程，但系統會讓各個讀進程輪流從管道中讀數據(Linux的方案)。

3、消息傳遞系統 (Message passing system)

進程不借助任何共享存儲區或數據結構，是以格式化的消息(message)為單位，將通信的數據封裝在消息中，并利用操作系統提供的一組通信命令(原語)，在進程間進行消息傳遞，完成進程間的數據交換。

基于消息傳遞系統的通信方式屬于高級通信方式，可分成兩類:

直接通信方式，是指發送進程利用OS所提供的發送原語，直接把消息發送給目標進程:
間接通信方式，是指發送和接收進程都通過共享中間實體(稱為郵箱)的方式進行消息的發送和接收，完成進程間的通信。

4、客戶機-服務器系統 (Client-Server system)

主要的實現方法分為三類:套接字、遠程過程調用和遠程方法調用

套接字
- 概念：
  - 一個套接字就是一個通信標識類型的數據結構，包含了通信目的的地址、通信使用的端口號、通信網絡的傳輸層協議、進程所在的網絡地址，以及針對客戶或服務器程序提供的不同系統調用(或 API函數)等。
  - 是進程通信【同一臺計算機內部的進程通信】和網絡通信【網絡環境中不同計算機間的進程通信】的基本構件。
  - 每個套接字擁有唯一的套接字號(也稱套接字標識符)，系統中所有的連接都持有唯一的一對套接字及端口連接，能區分來自不同應用程序進程或網絡連接的通信
- 套接字是為客戶/服務器模型而設計的，通常，套接字包括兩類:
  - 基于文件型: 通信進程都運行在同一臺機器的環境中，套接字是基于本地文件系統支持的，一個套接字關聯到一個特殊的文件，通信雙方通過對這個特殊文件的讀寫實現通信，其原理類似于前面所講的管道。
  - 基于網絡型: 該類型通常采用的是非對稱方式通信，即發送者需要提供接收者命名。
    通信雙方的進程運行在不同主機的網絡環境下，被分配了一對套接字，一個屬于接收進程(或服務器端)，一個屬于發送進程(或客戶端)。
    發送進程(或客戶端)發出連接請求時，隨機申請一個套接字，主機為之分配一個端口，與該套接字綁定，不再分配給其它進程。
    
    接收進程(或服務器端) 擁有全局公認的套接字和指定的端口(如ftp 服務器監聽端口為 21，http服務器監聽端口為 80)，并通過監聽端口等待客戶請求。任何進程都可以向接收進程發出連接請求和信息請求。
    - 接收進程(或服務器端)一旦收到請求，就接受來自發送進程(或客戶端)的連接，完成連接，即在主機間傳輸的數據可以準確地發送到通信進程，實現進程間的通信;
    - 當通信結束時，系統通過關閉接收進程(或服務器端)的套接字撤銷連接。
遠程過程調用和遠程方法調用
- 概念：
  - 遠程過程(函數)調用 RPC(Remote Procedure Call)，是一個通信協議，用于通過網絡連接的系統。
  - 該協議允許運行于一臺主機(本地)系統上的進程調用另一臺主機(遠程)系統上的進程。
  - 如果涉及的軟件采用面向對象編程，那么遠程過程調用亦可稱做遠程方法調用。
- 角色：
  - 進程有兩個：本地客戶進程 ? 遠程服務器進程，這兩個進程通常也被稱為網絡守護進程，主要負責在網絡間的消息傳遞
    
    一般情況下，這兩個進程都是處于阻塞狀態，等待消息。
  - 存根(stub)有兩個：一般也是處于阻塞狀態，等待消息。
    - 📌在本地客戶端，每個能夠獨立運行的遠程過程都擁有一個客戶存根(Client Stub)
      客戶存根(Client Stub): 偽裝成遠程服務，讓本地代碼以為在調用本地方法，其實是將本地調用轉為網絡請求。
      
      ?? 核心職責
      
      偽裝成遠程服務
      在代碼中，客戶端存根會暴露和遠程服務完全相同的接口方法（例如GetUser(id)）。
      開發者調用client.GetUser(123)時，并不知道該方法實際會觸發網絡通信，仿佛在調用本地代碼。
      
      本地調用 → 網絡請求的轉換
      接收本地參數：存根獲取方法名（GetUser）和參數（id=123）。
      序列化參數：將參數轉換為網絡傳輸格式（如Protobuf / JSON）。
      協議封裝：按協議（如HTTP/gRPC）構造協議頭并打包請求數據。
      
      隱藏網絡細節
      開發者無需處理：Socket連接、數據分包、超時重試、負載均衡等底層問題。
    - 📌在每個遠程進程所在的服務器端，其所對應的實際可執行進程也存在一個服務器存根(Server Stub)。
      服務器存根(Server Stub)：接收、解析客戶端請求，并驅動真實業務邏輯執行，最終封裝結果返回給客戶端
      
      ?? 核心職責
      
      接收網絡請求
      監聽特定協議（如 HTTP/gRPC）的端口，接收客戶端發來的二進制數據流。
      
      反序列化請求
      解析協議頭（如 gRPC 的 Content-Type），提取方法名和參數。
      將二進制數據還原為編程語言對象（如 Protobuf → Go 結構體）。
      
      調用真實服務
      根據方法名（如 GetUser）找到服務端注冊的業務實現類（如 UserService）。
      傳入反序列化后的參數，執行實際邏輯（如查詢數據庫）。
      
      封裝響應
      將業務結果（或異常）序列化為網絡格式（如 Protobuf/JSON）。
      按協議組裝響應頭（如 HTTP 狀態碼、gRPC 的 grpc-status）。
- 步驟：
  - 本地過程調用者以一般方式調用遠程過程在本地關聯的客戶存根，傳遞相應的參數，然后將控制權轉移給客戶存根;
  - 客戶存根執行，完成包括過程名和調用參數等信息的消息建立，將控制權轉移給本地客戶進程;
  - 本地客戶進程完成與服務器的消息傳遞，將消息發送到遠程服務器進程:
  - 遠程服務器進程接收消息后轉入執行，并根據其中的遠程過程名找到對應的服務器存根，將消息轉給該存根;
  - 服務器存根接到消息后，由阻塞狀態轉入執行狀態，拆開消息從中取出過程調用的參數，然后以一般方式調用服務器上關聯的過程;
  - 在服務器端的遠程過程(真實服務-業務邏輯的代碼)運行完畢后，將結果返回給與之關聯的服務器存根:
  - 該服務器存根獲得控制權運行，將結果打包為消息，并將控制權轉移給遠程服務器進程;
  - 遠程服務器進程將消息發送回客戶端;
  - 本地客戶進程接收到消息后，根據其中的過程名將消息存入關聯的客戶存根，再將控制權轉移給客戶存根;
  - 客戶存根從消息中取出結果，返回給本地調用者進程，并完成控制權的轉移。

2.6.2 消息傳遞通信的實現方式

進程通信分為直接和間接兩種通信方式

1、直接消息傳遞系統 - 直接通信

發送進程利用OS所提供的發送命令(原語)，直接把消息發送給目標進程。

直接通信原語

對稱尋址方式：要求發送進程和接收進程都必須以顯式方式提供對方的標識符。
發送一個消息給接收進程 send(receiver, message); - 將消息message發送給接收進程receiver
接收 Sender 發來的消息 receive(sender,message); - 接收由sender發來的消息message。

缺點：一旦改變進程的名稱，則可能需要檢查所有其它進程的定義，有關對該進程舊名稱的所有引用都必須查找到修改為新名稱【不利于實現進程定義的模塊化】
非對稱尋址方式：在接收進程的原語中，不需要命名發送進程，只填寫表示源進程的參數；發送進程仍需要命名接收進程。

發送一個消息給進程P send(P,message);
接收來自任何進程的消息 receive (id,message); id變量可為發送方進程 id 或名字。

消息的格式 : 可采用變長的消息格式，即進程所發送消息的長度是可變的。

進程的同步方式 - 協調通信 ：三種情況:

①發送進程阻塞，接收進程阻塞。這種情況主要用于進程之間緊密同步，發送進程和接收進程之間無緩沖時。
②發送進程不阻塞、接收進程阻塞。應用最廣。
- 發送進程平時不阻塞，可以盡快地把一個或多個消息發送給多個目標;
- 接收進程平時則處于阻塞狀態，直到發送進程發來消息時才被喚醒。
③發送進程和接收進程均不阻塞。較常見的。平時，發送進程和接收進程都在忙于自己的事情，僅當發生某事件使它無法繼續運行時，才把自己阻塞起來等待。

通信鏈路
發送進程和接收進程之間建立一條通信鏈路進行通信。

建立通信鏈路有兩種方式：
- 由發送進程在通信之前用顯式的“建立連接”命令(原語)請求系統為之建立一條通信鏈路，在鏈路使用完后拆除鏈路。這種方式主要用于計算機網絡中。
- 發送進程無須明確提出建立鏈路的請求，只須利用系統提供的發送命令(原語)，系統會自動地建立一條鏈路。這種方式主要用于單機系統中。
鏈路分成兩種:
- 單向通信鏈路，只允許發送進程向接收進程發送消息，或者相反;
- 雙向通信鏈路，既允許由進程A向進程B發送消息，也允許進程 B同時向進程A發送消息。

在這里插入圖片描述

2、信箱通信 - 間接通信

進程之間的通信，需要通過某種中間實體(如共享數據結構等)來完成。
該實體建立在隨機存儲器的公用緩沖區上，用來暫存發送進程發送給目標進程的消息;
接收進程可以從該實體中取出發送進程發送給自己的消息，通常把這種中間實體稱為郵箱(或信箱);
每個郵箱都有一個唯一的標識符。
實現實時通信，又可實現非實時通信。

信箱結構

在邏輯上，可以將其分為兩個部分: 消息的傳遞可以單向傳遞，也可以是雙向的

信箱頭，用以存放有關信箱的描述信息，如信標識符、信的擁有者、信箱口信箱的空格數等;
信箱體，由若干個可以存放消息(或消息頭)的信箱格組成，信箱格的數目以及每格的大小是在創建信箱時確定的。

在這里插入圖片描述

信箱通信原語

郵箱的創建和撤消。
- 進程可利用郵箱創建原語來建立一個新郵箱，創建者進程應給出郵箱名字、郵箱屬性(公用、私用或共享);
  對于共享郵箱，還應給出共享者的名字。
- 當進程不再需要讀郵箱時，可用郵箱撤消原語將之撤消。
消息的發送和接收。當進程之間要利用郵箱進行通信時，必須使用共享郵箱，并利用系統提供的下述通信原語進行通信。
- 將一個消息發送到指定郵箱 Send(mailbox，message);
- 從指定郵箱中接收一個消息 Receive(mailbox,message);

在這里插入圖片描述

信箱的類型
郵箱可由操作系統創建，也可由用戶進程創建，創建者是郵箱的擁有者。據此，可把郵箱分為以下三類:

私用郵箱。
- 用戶進程可為自己建立一個新郵箱，并作為該進程的一部分。
- 郵箱的擁有者有權從郵箱中讀取消息，其他用戶則只能將自己構成的消息發送到該郵箱中。
- 采用單向通信鏈路的郵箱來實現。
- 當擁有該郵箱的進程結束時,郵箱也隨之消失。
公用郵箱。
- 由操作系統創建，并提供給系統中的所有使用。
  核準進程（Authorized Process）是指經過系統安全機制驗證，具備特定權限或資源訪問資格的進程。其核心目的是防止未授權的代碼或用戶執行特權操作
- 核準進程既可把消息發送到該郵箱中，也可從郵箱中讀取發送給自己的消息。
- 采用雙向通信鏈路的郵箱來實現。
- 公用郵箱在系統運行期間始終存在。
共享郵箱。
- 由某進程創建，在創建時或創建后指明它是可共享的，同時須指出共享進程(用戶)的名字。
- 郵箱的擁有者和共享者都有權從郵箱中取走發送給自己的消息。

在利用郵箱通信時,在發送進程和接收進程之間, 存在以下四種關系:

一對一關系。發送進程和接收進程可以建立一條兩者專用的通信鏈路，使兩者之間的交互不受其他進程的干擾。
多對一關系。允許一個服務(接收)進程與多個用戶(發送)進程之間進行交互，也稱為客戶/服務器交互(client/server interaction)。
一對多關系。允許一個發送進程與多個接收進程進行交互，使發送進程可用廣播方式向接收者(多個)發送消息。
多對多關系。允許建立一個公用郵箱，讓多個進程都能向郵箱中投遞消息; 也可從郵箱中取走屬于自己的消息。

2.6.3 直接消息傳遞系統實例

消息緩沖隊列通信機制被廣泛應用于本地進程之間的通信中。

發送進程利用Send 原語將消息直接發送給接收進程
接收進程則利用 Receive 原語接收消息。

1、消息緩沖隊列通信機制中的數據結構

消息緩沖區

type struct message_buffer {int sender;                                        // 發送者進程標識符int size;                                            // 消息長度char *text;                                        // 消息正文struct message_buffer *next;            // 指向下一個消息緩沖區的指針
}

PCB中有關通信的數據項。
- 消息隊列隊首指針，用于對消息隊列進行操作
- 用于實現同步的互斥信號量mutex
- 資源信號量sm

type struct processcontrol_block {...struct message_buffer *mq;   // 消息隊列隊首指針semaphore mutex;                // 消息隊列互斥信號量semaphore sm;                     // 消息隊列資源信號量...
}PCB ;

2、發送原語

發送進程在利用發送原語發送消息之前，應先在自己的內存空間設置一發送區a
把待發送的消息正文、發送進程標識符、消息長度等信息填入發送區a中
調用發送原語，把消息發送給目標(接收)進程。
發送原語首先根據發送區a中所設置的消息長度來申請一緩沖區
接著把發送區a中的信息復制到緩沖區中
將緩沖區掛在接收進程的消息隊列(臨界資源)上。

void send(receiver, a)  // receiver為接收進程標識符，a為發送區首址
{// 根據 a.size 申請緩沖區;getbuf(a.size, i);   // 將發送區a中的信息復制到消息緩沖區i中;copy(i.sender, a.sender);  i.size = a.size;copy(i.text, a.text);i.next = 0;// 獲得接收進程內部的標識符j;getid(PCBset, receiver.j);wait(j.mutex);// 將消息緩沖區插入消息隊列;insert(&j.mq, i);signal(j.mutex);signal(j.sm);
}

3、接收原語

接收進程調用接收原語receive(b)
從自己的消息緩沖隊列中摘下第一個消息緩沖區
并將其中的數據復制到以b為首址的指定消息接收區內
釋放消息緩沖區。

void receive(b){// j為接收進程內部的標識符;j = internal name;wait(j.sm);wait(j.mutex);// 將消息隊列中第一個消息移出;remove(j.mq, i);signal(j.mutex);// 將消息緩沖區i中的信息復制到接收區 b;copy(b.sender, i.sender);b.size = i.size;copy(b.text, i.text);// 釋放消息緩沖區;releasebuf(i);
}

2.7 線程(Threads)的基本概念

引入進程的目的是為了使多個程序能并發執行，以提高資源利用率和系統吞吐量。

引入線程的目的是為了減少程序在并發執行時所付出的時空開銷，使OS具有更好的并發性。

2.7.1 線程的引入

1、進程的兩個基本屬性

進程是一個可擁有資源的獨立單位：一個進程要能獨立運行，它必須擁有一定的資源，包括用于存放程序正文、數據的磁盤和內存地址空間，以及它在運行時所需要的 I/O 設備、已打開的文件、信號量等;
進程同時又是一個可獨立調度和分派的基本單位。每個進程在系統中有唯一的PCB，系統可根據其PCB感知進程的存在，也可以根據其 PCB 中的信息，對進程進行調度，還可將斷點信息保存在其PCB中。反之，再利用進程 PCB 中的信息來恢復進程運行的現場。

調度（Scheduling）：決定哪個就緒進程將來獲得CPU（決策過程）。

分派（Dispatching）：執行調度的決策，實際將CPU分配給該進程（動作過程），使其從就緒態轉為運行態的過程。

2、程序并發執行所需付出的時空開銷

為使程序能并發執行，系統必須進行以下的一系列操作:

創建進程，系統在創建一個進程時，必須為它分配其所必需的、除處理機以外的所有資源，如內存空間、I/O設備，以及建立相應的PCB
撤消進程，系統在撤消進程時，又必須先對其所占有的資源執行回收操作，然后再撤消PCB
進程切換，對進程進行上下文切換時，需要保留當前進程的CPU環境，設置新選中進程的 CPU 環境，因而須花費不少的處理機時間。

2.7.2 線程與進程的比較

由于線程具有許多傳統進程所具有的特征，所以又稱之為輕型進程(Light-Weight Process)或進程元

把傳統進程稱為重型進程(Heavy-Weight Process)，相當于只有一個線程的任務。

1、調度的基本單位

進程作為獨立調度和分派的基本單位——進程是能獨立運行的基本單位。在每次被調度時，都需要進行上下文切換，開銷較大。
線程作為調度和分派的基本單位——線程是能獨立運行的基本單位。當線程切換時，僅需保存和設置少量寄存器內容，切換代價遠低于進程。

在同一進程中，線程的切換不會引起進程的切換，但從一個進程中的線程切換到另一個進程中的線程時，必然就會引起進程的切換。

傳統進程機制中，進程是資源分配、調度的基本單位
引入線程后，進程是資源分配的基本單位，線程是調度的基本單位

2、并發性

進程之間可以并發執行
在一個進程中的多個線程之間（甚至所有線程）可并發執行
不同進程中的線程也能并發執行

例子：在文字處理器中可以設置三個線程

第一個線程用于顯示文字和圖形
第二個線程從鍵盤讀入數據
第三個線程在后臺進行拼寫和語法檢查

3、擁有資源

進程可以擁有資源，并作為系統中擁有資源的一個基本單位。
線程擁有少量資源【一組寄存器和堆】, 以保證獨立運行。
- 在每個線程中都應具有一個用于控制線程運行的線程控制塊 TCB
- 用于指示被執行指令序列的程序計數器
- 保留局部變量
- 少數狀態參數
- 返回地址。
允許多個線程共享該進程所擁有的資源:
- 屬于同一進程的所有線程都具有相同的地址空間——線程可以訪問該地址空間中的每一個虛地址
- 可以訪問進程所擁有的資源，如已打開的文件、定時器、信號量機構等的內存空間和它所申請到的I/O設備等。

4、獨立性

在同一進程中的不同線程之間的獨立性要比不同進程之間的獨立性低得多。

【為防止進程之間彼此干擾和破壞】每個進程都擁有一個獨立的地址空間和其它資源，除了共享全局變量外，不允許其它進程的訪問。
同一進程中的不同線程之間可以相互合作，它們共享進程的內存地址空間和資源。

5、系統開銷

進程創建或撤消時大于線程所付出的開銷:

在創建或撤消進程時，系統都要為之分配和回收進程控制塊、分配或回收其它資源，如內存空間和 I/O 設備等。
在進程切換時，涉及到進程上下文的切換，系統開銷大; 線程間并發，如果是同一進程內的線程切換，則不需切換進程環境，系統開銷小。
在一些OS中，線程的切換、同步和通信都無需操作系統內核的干預。

6、支持多處理機系統

在多處理機系統中，對于傳統的進程，即單線程進程，不管有多少處理機，該進程只能運行在一個處理機上。
在多處理機系統中，對于多線程進程，可以將一個進程中的多個線程分配到多個處理機上，使它們并行執行。

2.7.3 線程的狀態和線程控制塊

1、線程運行的三個狀態

執行狀態，表示線程已獲得處理機而正在運行;
就緒狀態，指線程已具備了各種執行條件，只須再獲得CPU便可立即執行;
阻塞狀態，指線程在執行中因某事件受阻而處于暫停狀態。

2、線程控制塊 TCB

每個線程配置了一個線程控制塊TCB,將所有用于控制和管理線程的信息記錄在線程控制塊中。

線程控制塊通常有這樣幾項:

① 線程標識符，為每個線程賦予一個唯一的線程標識符;
② 一組寄存器，包括程序計數器PC、狀態寄存器和通用寄存器的內容;
③ 線程運行狀態，用于描述線程正處于何種運行狀態;
④ 優先級，描述線程執行的優先程度;
⑤ 線程專有存儲區，用于線程切換時存放現場保護信息，和與該線程相關的統計信息等;
⑥ 信號屏蔽，即對某些信號加以屏蔽；
⑦ 堆棧指針，每個線程需設置一個堆棧，用它來保存局部變量和返回地址【在線程運行時，經常會進行過程調用，而過程的調用通常會出現多重嵌套的情況，就必須將每次過程調用中所使用的局部變量以及返回地址保存起來。】。在TCB中須設置兩個指向堆棧的指針:
- 指向用戶自己堆棧的指針：當線程運行在用戶態時，使用用戶自己的用戶棧來保存局部變量和返回地址
- 指向核心棧的指針：當線程運行在核心態時使用系統的核心棧。

3、多線程 OS 中的進程屬性

進程是一個可擁有資源的基本單位。在多線程OS中，進程仍是作為系統資源分配的基本單位，任一進程所擁有的資源都包括:
- 用戶的地址空間
- 實現進程(線程)間同步和通信的機制
- 已打開的文件
- 已申請到的I/O 設備
- 一張由核心進程維護的地址映射表，該表用于實現用戶程序的邏輯地址到其內存物理地址的映射。
多個線程可并發執行。通常一個進程都含有若干個相對獨立的線程(至少要有一個線程)。
- 把傳統進程的執行方法稱為單線程方法。
- 將每個進程支持多個線程執行的方法稱為多線程方法。
進程已不是可執行的實體。在多線程OS中，是把線程作為獨立運行(或稱調度)的基本單位。
- 進程仍具有與執行相關的狀態——所謂進程處于“執行”狀態，實際上是指該進程中的某線程正在執行。
- 對進程所施加的與進程狀態有關的操作也對其線程起作用。
  例如，在把某個進程掛起時，該進程中的所有線程也都將被掛起；又如，在把某進程激活時，屬于該進程的所有線程也都將被激活、

2.8 線程的實現

2.8.1 線程的實現方式

1、內核支持線程 KST(Kernel Supported Threads) - 內核空間

特點：
- 在內核空間中實現的：在OS中的所有進程【無論是系統進程還是用戶進程】，都是在操作系統內核的支持下運行的。
- 內核支持線程KST同樣也是在內核的支持下運行的，它們的創建、阻塞、撤消和切換等，也都是在內核空間實現的。
- 在內核空間也為每一個內核線程設置了一個線程控制塊，內核根據該控制塊感知某線程的存在，并對其加以控制和管理。
- 調度是以線程為單位進行的
優點：
- 在多處理器系統中，內核能夠同時調度同一進程中的多個線程并行執行;
- 并發能力強：如果進程中的一個線程被阻塞了，內核可以調度該進程中的其它線程占有處理器運行，也可以運行其它進程中的線程;
- 內核支持線程具有很小的數據結構和堆棧，線程的切換比較快，切換開銷小;
- 內核本身也可以采用多線程技術，可以提高系統的執行速度和效率。
缺點：
- 對于用戶的線程切換而言，其模式切換的(CPU 需要變態)開銷較大：在同一個進程中，從一個線程切換到另一個線程時，需要從用戶態轉到核心態進行，這是因為用戶進程的線程在用戶態運行，而線程調度和管理是在內核實現的，系統開銷較大。

2、用戶級線程 ULT(User Level Threads) - 用戶空間

特點：
- 用戶級線程是與內核無關：對線程的創建、撤消、同步與通信等功能，都無需內核的支持，內核完全不知道用戶級線程的存在。
- 是在用戶空間中實現的：線程的任務控制塊都是設置在用戶空間，線程所執行的操作也無需內核的幫助 - 不需要CPU變態。
- 是應用程序通過線程庫實現的。
- 調度是以進程為單位進行的。
優點：
- 線程切換不需要轉換到內核空間，開銷小。
  - 所有線程管理數據結構（TCB） 存放在進程的用戶空間，切換時 不涉及內核模式（避免用戶態→內核態切換開銷）。
  - 線程切換由用戶級線程庫直接管理，不依賴操作系統內核。
- 調度算法可以是進程專用的。在不干擾 OS 調度的情況下，每個進程可定制獨立的線程調度策略。
- 用戶級線程的實現與OS平臺無關。對于線程管理的代碼是屬于用戶程序的一部分，所有的應用程序都可以對之進行共享。線程機制不依賴 OS 內核支持。即使 OS 本身不支持線程（如早期 Unix），用戶程序仍可模擬多線程（基于協程、狀態機）。

在這里插入圖片描述

用戶級線程（ULT）和內核級線程（KLT）對比：

優點	用戶級線程（ULT）	內核級線程（KLT）
切換速度	快（無內核介入）	慢（需切換至內核態）
調度控制	進程可自定義調度策略	由 OS 統一調度
多核并行	不真正并行（OS 僅調度單進程）	可多核并行
跨平臺性	強（不依賴內核支持）	依賴 OS 線程機制（如 Windows CreateThread）

缺點	用戶級線程（ULT）	內核級線程（KLT）
系統調用阻塞	整個進程/某一個線程阻塞，所有線程暫停	僅阻塞當前線程，其他線程可運行
多核并行	多個線程不可在多核處理機上并行運行（單進程單CPU分配）	線程可分配到不同核心并行執行

3、組合

把用戶級線程和內核支持線程兩種方式進行組合，提供了組合方式ULT/KST線程。在組合方式線程系統中，

內核支持多個內核支持線程的建立、調度和管理;
也允許用戶應用程序建立、調度和管理用戶級線程。

組合方式線程中，同一個進程內的多個線程可以同時在多處理器上并行執行，而且在阻塞一個線程時并不需要將整個進程阻塞。

由于用戶級線程和內核支持線程連接方式的不同，從而形成了三種不同的模型:

多對一模型，即將用戶線程映射到一個內核控制線程。
- 這些用戶線程一般屬于一個進程，運行在該進程的用戶空間，對這些線程的調度和管理也是在該進程的用戶空間中完成。
  僅當用戶線程需要訪問內核時，才將其映射到一個內核控制線程上，但每次只允許一個線程進行映射。
- 優點：線程管理的開銷小，效率高
- 缺點：如果一個線程在訪問內核時發生阻塞，則整個進程都會被阻塞; 此外，在任一時刻，只有一個線程能夠訪問內核，多個線程不能同時在多個處理機上運行。
一對一模型，即將每一個用戶級線程映射到一個內核支持線程。
- 為每一個用戶線程都設置一個內核控制線程與之連接。
- 優點：當一個線程阻塞時，允許調度另一個線程運行，所以它提供了比多對一型更好的并發功能。此外，在多處理機系統中，它允許多個線程并行地運行在多處理機系統上。
- 缺點：每創建一個用戶線程，相應地就需要創建一個內核線程，開銷較大，因此需要限制整個系統的線程數。
多對多模型，即將許多用戶線程映射到同樣數量或更少數量的內核線程上。
- 內核控制線程的數目可以根據應用進程和系統的不同而變化，可以比用戶線程少，也可以與之相同。
- 該模型結合上述兩種模型的優點
  - 可以像一對一模型那樣，使個進程的多個線程并行地運行在多處理機系統上
  - 也可像多對一模型那樣，減少線程的管理開銷和提高效率。

? 在這里插入圖片描述

2.8.2 線程的實現

不論是進程還是線程，都必須直接或間接地取得內核的支持。

1、內核支持線程的實現

系統在創建一個新進程時，便在內核空間為它分配一個任務數據區 PTDA(Per Task Data Area)，其中包括若干個線程控制塊 TCB 空間。
在每一個TCB中可保存線程標識符、優先級、線程運行的 CPU狀態等信息。
每當進程要創建一個線程時，便為新線程分配個TCB，將有關信息填入該TCB中，并為之分配必要的資源。
當PTDA中的所有TCB 空間已用完，而進程又要創建新的線程時，只要其所創建的線程數目未超過系統的允許值(通常為數十至數百個)，系統可再為之分配新的 TCB 空間。
在撤消一個線程時，也應回收該線程的所有資源和 TCB。
有的系統中為了減少在創建和撤消一個線程時的開銷，在撤消一個線程時并不立即回收該線程的資源和 TCB——當以后再要創建一個新線程時，便可直接利用已被撤消但仍保持有資源的 TCB作為新線程的TCB。
內核支持線程的調度和切換與進程的調度和切換十分相似，也分搶占式方式和非搶占方式兩種。
在線程的調度算法上，同樣可采用時間片輪轉法、優先權算法等。

2、用戶級線程的實現

用戶級線程是在用戶空間實現的。
所有的用戶級線程都具有相同的結構，它們都運行在一個中間系統上。當前有兩種方式實現中間系統，即運行時系統和內核控制線程。
- 運行時系統（Runtime System）
  本質：一組用于管理和控制線程的函數（過程）的集合，包含：
  - 線程生命周期管理（創建、撤銷）
  - 線程同步與通信（互斥鎖、信號量、條件變量）
  - 線程調度（選擇合適的就緒線程執行）
  作用：
  - 使用戶級線程無需依賴內核（純用戶空間實現）。
  - 充當用戶級線程與內核之間的接口（但本身不進入內核）。
  線程切換機制：
  - 傳統進程切換：必須進入內核態（user → kernel），由 OS 完成上下文切換。
  - 用戶級線程切換：
    - 完全在用戶空間完成，由運行時系統的線程切換函數處理：
      保存當前線程狀態（CPU 寄存器、棧指針）到線程的私有堆棧。
      選擇新線程（根據調度算法從就緒隊列中選取）。
      加載新線程狀態（從堆棧恢復寄存器、更新棧指針和程序計數器）。
    - 優勢：線程的切換無須進入內核，切換操作簡單且速度極快。
  系統資源：
  - 進程是利用OS提供的系統調用來請求系統資源的，系統調用通過軟中斷(如tap)機制進入OS內核，由內核來完成相應資源的分配。
  - 用戶級線程是不能利用系統調用的。當線程需要系統資源時，是將該要求傳送給運行時系統，由后者通過相應的系統調用來獲得系統資源。
- 內核控制線程, 又稱為輕型進程 LWP(Light Weight Process)
  本質：介于 用戶級線程（ULT） 和 內核級線程（KLT） 之間的橋梁，用于賦予 ULT 部分內核支持線程的能力。
  
  特點：
  - 每個 LWP 擁有獨立的 TCB（棧、寄存器狀態、優先級），但共享進程資源（如內存、文件描述符）。
  - 通過系統調用訪問內核（與內核級線程類似），但由用戶線程運行時系統動態綁定。
  - 通過 LWP，ULT 獲得與內核通信的能力（如 I/O 請求）。
  LWP 的核心機制:
  - LWP 線程池（緩沖池）
    - 背景：用戶級線程可能數量龐大（如協程池），而內核無法直接管理 ULT。
    - 解決方案：進程維護一個 LWP 池（數量遠少于 ULT），動態分配給 ULT 使用。
    - 工作方式：
      
      當一個 ULT 需要訪問內核（如系統調用），它必須綁定到一個 空閑的 LWP。
      如果 LWP 池耗盡（例：5 個 ULT 請求 I/O，但僅有 4 個 LWP），則超出的 ULT 必須等待。
  - LWP 與內核線程的關系
    - LWP一對一綁定到內核級線程（KLT）：
      
      內核只能看到 LWP（即 KLT），無法感知 ULT 的存在。
      調度單位是 LWP（內核按 LWP 分配 CPU 時間片）。
    - ULT 通過 LWP 間接訪問內核：當 ULT 執行系統調用時，需綁定到 LWP，由 LWP 代理請求內核。
  阻塞
  - 在內核級線程執行操作時，如果內核級線程發生阻塞，則與之相連接的多個LWP也將隨之阻塞，進而使連接到 LWP 上的用戶級線程也被阻塞。
  - 如果進程中只包含了一個LWP，該進程實際上也應阻塞。
  - 如果在一個進程中含有多個LWP，則當一個LWP阻塞時，進程中的另一個LWP可繼續執行。
  - 即使進程中的所有LWP全部阻塞，進程中的線程也仍然能繼續執行，只是不能再去訪問內核。

2.8.3 線程的創建和終止

1、線程的創建

應用程序在啟動時，通常僅有一個線程在執行，人們把線程稱為“初始化線程”，主要功能是用于創建新線程。
在創建新線程時，需要利用一個線程創建函數(或系統調用)，并提供相應的參數——如指向線程主程序的入口指針、堆棧的大小，以及用于調度的優先級等。
在線程的創建函數執行完后，將返回一個線程標識符供以后使用。

2、線程的終止

線程終止的兩種情況

正常終止
- 線程主動完成任務后，調用終止函數（如 pthread_exit）退出。
強制終止
- 線程因異常（如段錯誤、未捕獲信號）或被其他線程終止（如 pthread_cancel）。

線程終止后的資源處理

資源不會立即釋放：
- 線程終止后，其占用的資源（如棧、寄存器狀態、線程描述符）可能被保留。
- 需其他線程顯式調用分離函數（如 pthread_detach）才能釋放資源。
未分離的線程可被復用：
- 其他線程可通過連接（join）操作獲取已終止線程的狀態，并回收資源。
- 若線程未被分離，其資源會一直保留，直到被連接（pthread_join）。

系統線程的特殊性

長期運行的線程：

某些系統線程（如內核守護線程）一旦啟動，會持續運行，不被顯式終止。
通常由操作系統管理，用戶無法直接干預其生命周期。

線程連接（Join）機制

作用：允許一個線程等待另一個線程終止，并獲取其退出狀態。
阻塞與非阻塞：
- 若目標線程仍在運行：調用 pthread_join 的線程會阻塞，直到目標線程終止。
- 若目標線程已終止：調用線程立即繼續執行，并回收資源。
連接后資源釋放：成功連接后，目標線程的資源會被系統回收。
? pthread_join 是唯一獲取線程返回值的方式（如果不關心返回值，可以傳 NULL）。
只有 非分離（non-detached）線程 才能被 join

分離（Detach）機制

作用：顯式聲明線程終止后自動釋放資源，無需其他線程連接。
使用場景：如果 不關心線程的返回值，并且 希望線程結束后自動釋放資源，可調用 pthread_detach 避免資源泄露。
不可逆性：線程一旦**被分離**，不能再通過 join 連接。

關鍵函數對比

操作	函數（POSIX線程）	效果
終止線程	`pthread_exit`	線程主動退出，資源保留到被連接或分離。
強制終止線程	`pthread_cancel`	請求終止目標線程，終止行為取決于線程的取消狀態（延遲或異步）。
等待線程終止并回收	`pthread_join`	阻塞調用者直到目標線程終止，回收資源。
分離線程	`pthread_detach`	線程終止后自動釋放資源，無需連接。