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