第四章：進(jìn)程同步 學(xué)習(xí)筆記
一、 核心概念
1. 進(jìn)程同步的必要性
在并發(fā)環(huán)境下，多個(gè)進(jìn)程（或線程）共享系統(tǒng)資源（如CPU、內(nèi)存、文件、I/O設(shè)備等）。若對(duì)它們的執(zhí)行順序不加控制，可能會(huì)導(dǎo)致競爭條件，即多個(gè)進(jìn)程對(duì)同一共享數(shù)據(jù)進(jìn)行操作，而最終結(jié)果取決于進(jìn)程執(zhí)行的特定時(shí)序，導(dǎo)致結(jié)果的不確定性和錯(cuò)誤。
2. 臨界區(qū)問題
- 臨界資源：一次僅允許一個(gè)進(jìn)程使用的資源（如打印機(jī)、共享變量）。
- 臨界區(qū)：進(jìn)程中訪問臨界資源的那段代碼。
- 一個(gè)良好的進(jìn)程同步機(jī)制需要滿足三個(gè)條件：
- 互斥：同一時(shí)間只有一個(gè)進(jìn)程可以進(jìn)入臨界區(qū)。
- 前進(jìn)（空閑讓進(jìn)）：如果沒有進(jìn)程在臨界區(qū)內(nèi)，且已有進(jìn)程申請(qǐng)進(jìn)入，那么應(yīng)允許其中一個(gè)申請(qǐng)者進(jìn)入。
- 有限等待：一個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)后，應(yīng)在有限時(shí)間內(nèi)獲得許可，避免“饑餓”。
二、 進(jìn)程同步的軟件與硬件方法
1. 軟件方法（算法）
- Peterson算法：一個(gè)經(jīng)典的、基于軟件的雙進(jìn)程互斥算法，通過設(shè)置turn和flag數(shù)組來實(shí)現(xiàn)互斥和有限等待。它證明了純軟件方法可以實(shí)現(xiàn)互斥，但通常只適用于兩個(gè)進(jìn)程，且在現(xiàn)代多核/多處理器環(huán)境下可能因內(nèi)存訪問順序（內(nèi)存模型）問題而失效。
- Dekker算法：早期的雙進(jìn)程互斥算法。
2. 硬件方法
- 關(guān)中斷：進(jìn)入臨界區(qū)前關(guān)中斷，離開后開中斷。簡單有效（對(duì)單核CPU），但不適用于多處理器系統(tǒng)，且將權(quán)力交給用戶進(jìn)程是危險(xiǎn)的。
- 硬件指令：利用特殊的原子（不可分割）指令，如Test-and-Set指令和Swap指令。這些指令在硬件層面保證了讀-改-寫操作的原子性，是實(shí)現(xiàn)鎖等高級(jí)同步原語的基礎(chǔ)。
三、 高級(jí)同步機(jī)制（同步原語）
1. 信號(hào)量
由Dijkstra提出，是操作系統(tǒng)提供的一種功能強(qiáng)大的同步工具。
- 整型信號(hào)量：一個(gè)整型變量
S，僅能通過兩個(gè)原子操作訪問： wait(S)或P(S)：當(dāng)S<=0時(shí)循環(huán)等待；否則S--。
signal(S)或V(S)：S++。
- 記錄型信號(hào)量：為解決整型信號(hào)量“忙等”（占用CPU循環(huán)檢查）問題，引入一個(gè)等待隊(duì)列。
wait操作在資源不足時(shí)將進(jìn)程阻塞并放入隊(duì)列；signal操作釋放資源后，若隊(duì)列不空則喚醒一個(gè)等待進(jìn)程。 - 應(yīng)用：
- 互斥信號(hào)量：初始值通常為1（表示一個(gè)可用資源），用于實(shí)現(xiàn)互斥。
- 同步（資源計(jì)數(shù)）信號(hào)量：初始值可以是N（表示有N個(gè)可用資源），用于控制對(duì)多個(gè)實(shí)例的資源的訪問。
2. 管程
一種高級(jí)語言層面的同步機(jī)制，將共享變量及其相關(guān)的操作（過程）封裝在一個(gè)模塊中。管程內(nèi)部任何時(shí)刻只能有一個(gè)進(jìn)程（或線程）活動(dòng)，由編譯器負(fù)責(zé)實(shí)現(xiàn)互斥。進(jìn)程通過調(diào)用管程的過程來訪問共享資源。為了處理更復(fù)雜的同步條件，管程引入了條件變量及相關(guān)操作（wait和signal）。
四、 經(jīng)典同步問題
1. 生產(chǎn)者-消費(fèi)者問題
- 描述：一組生產(chǎn)者進(jìn)程向固定大小的緩沖區(qū)放入數(shù)據(jù)，一組消費(fèi)者進(jìn)程從中取出數(shù)據(jù)。
- 同步要點(diǎn)：
- 緩沖區(qū)空時(shí)，消費(fèi)者必須等待生產(chǎn)者。
- 緩沖區(qū)滿時(shí)，生產(chǎn)者必須等待消費(fèi)者。
- 對(duì)緩沖區(qū)的訪問（修改指針）必須互斥。
- 解決方案：通常使用三個(gè)信號(hào)量：
mutex（互斥，初值1）、empty（空緩沖區(qū)數(shù)，初值N）、full（滿緩沖區(qū)數(shù)，初值0）。
2. 讀者-寫者問題
- 描述：多個(gè)讀者和寫者共享一個(gè)數(shù)據(jù)對(duì)象（如文件）。允許多個(gè)讀者同時(shí)讀，但寫者必須獨(dú)占訪問（即寫時(shí)不允許任何其他讀者或?qū)懻撸?br />- 變體：
- 讀者優(yōu)先：只要有一個(gè)讀者在讀，后續(xù)讀者可以直接讀，可能導(dǎo)致寫者“饑餓”。
- 寫者優(yōu)先：一旦有寫者等待，新到的讀者必須等待，直到所有等待的寫者完成。
- 解決方案：使用信號(hào)量或讀寫鎖。
3. 哲學(xué)家進(jìn)餐問題
- 描述：五個(gè)哲學(xué)家圍坐圓桌，交替思考和吃飯。每人左右各有一根筷子，吃飯需要同時(shí)拿起左右兩根筷子。
- 挑戰(zhàn)：如何設(shè)計(jì)協(xié)議，防止死鎖（如每人拿起左邊筷子后無限等待右邊）和饑餓。
- 解決方案：
- 限制最多允許4個(gè)哲學(xué)家同時(shí)拿筷子。
- 要求哲學(xué)家同時(shí)拿起兩根筷子（原子操作）。
- 非對(duì)稱策略：奇數(shù)號(hào)哲學(xué)家先拿左筷再拿右筷，偶數(shù)號(hào)反之。
五、 與計(jì)算機(jī)系統(tǒng)服務(wù)的關(guān)系
進(jìn)程同步機(jī)制是操作系統(tǒng)內(nèi)核提供的最核心的系統(tǒng)服務(wù)之一。它直接支撐著：
- 并發(fā)執(zhí)行服務(wù)：操作系統(tǒng)通過進(jìn)程/線程管理提供并發(fā)執(zhí)行的能力，而同步機(jī)制是保證這種并發(fā)正確、有序進(jìn)行的基礎(chǔ)。沒有同步，并發(fā)將導(dǎo)致混亂。
- 資源共享服務(wù)：操作系統(tǒng)管理著所有系統(tǒng)資源。同步機(jī)制（如信號(hào)量、鎖）是操作系統(tǒng)提供給用戶進(jìn)程安全、有序地共享這些資源（內(nèi)存、文件、設(shè)備）的“工具包”。
- 進(jìn)程間通信服務(wù)：許多IPC機(jī)制，如消息隊(duì)列、共享內(nèi)存，其底層實(shí)現(xiàn)都嚴(yán)重依賴于同步機(jī)制來保證數(shù)據(jù)傳遞的正確性。例如，共享內(nèi)存區(qū)必須通過信號(hào)量或鎖來保護(hù)。
- 死鎖處理服務(wù)：同步機(jī)制使用不當(dāng)（如對(duì)多個(gè)信號(hào)量的申請(qǐng)順序不一致）是導(dǎo)致死鎖的主要原因。操作系統(tǒng)在提供同步原語的也需要提供死鎖的預(yù)防、避免、檢測與解除策略（詳見后續(xù)章節(jié)），這共同構(gòu)成了完整的并發(fā)控制服務(wù)體系。
- 系統(tǒng)調(diào)用接口：
wait,signal, 以及各種鎖（如互斥鎖、讀寫鎖、條件變量）的API，都是操作系統(tǒng)通過系統(tǒng)調(diào)用暴露給應(yīng)用程序的系統(tǒng)服務(wù)。應(yīng)用程序通過調(diào)用這些服務(wù)來編寫正確的并發(fā)程序。
**：第四章的進(jìn)程同步，是操作系統(tǒng)課程從理論走向?qū)嵺`的關(guān)鍵橋梁。它不僅僅是幾個(gè)算法和問題，更是理解操作系統(tǒng)如何作為資源管理者和服務(wù)提供者**的核心視角。掌握進(jìn)程同步，就是掌握了讓多個(gè)任務(wù)在計(jì)算機(jī)中高效、和諧共舞的指揮棒，這是構(gòu)建任何復(fù)雜、可靠軟件系統(tǒng)的基石。
