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