基本概念
進程異步性特征：各并發執行的進程以各自獨立的，不可預知的速度向前推進。
進程同步又稱作直接制約關系，他是指為完成某種任務而建立的兩個或者多個進程，這些進程因為需要在某些位置上協調他們的工作順序而產生的制約關系。（源于進程需要相互合作）
但是因為進程本身的異步性，因此需要操作系統進行處理。
兩種資源共享方式：互斥共享、同時共享
臨界資源：一個時間段內只允許一個進程使用的資源
進程互斥：當某一個進程訪問某臨界資源時，另一個想要訪問臨界資源的進程必須等待。
do
{進入區臨界區退出區剩余區
}while(true)
- 進入區：判斷能夠進入臨界區，如果可以進入，則設置正在訪問臨界資源的標志，阻止其他進程進入臨界區
- 臨界區/段：訪問臨界資源的代碼
- 退出區：解除正在訪問臨界資源的標志
- 剩余區：其他處理
實現進程互斥應該遵循的原則：
- 空閑讓進：臨界區空閑時可以允許一個進程進入臨界區
- 忙則等待：如果已經有進程進入臨界區則其他試圖進入臨界區的進程必須等待
- 優先等待：對于請求訪問的進程，應該保證能在有限時間內進入臨界區（保證不會饑餓）
- 讓權等待：如果進程不能進入臨界區，應該立即釋放處理機，防止進程忙等待
實現進程互斥的軟件實現
單標志法
每個進程進入臨界區的權限只能被另一個進程賦予
違背空閑讓進、讓權等待
雙標志先檢查法
對flag數組的訪問因為進程的異步性有可能導致違反忙則等待原則
雙標志后檢查法
可能違背空閑讓進、有限等待原則
Peterson算法
違背讓權等待的原則，可能需要“忙等”。但是比前面幾種方法好。
進程互斥的硬件實現
中斷屏蔽方法
利用“開/關中斷指令”實現。即在某進程開始訪問臨界區到結束訪問為止都不允許被中斷，也就不能發生進程切換，因此也不可能發生兩個同時訪問臨界區的情況。
優點：簡單、高效
缺點：不適用多處理機；只適用操作系統內核進程，不適用于用戶進程（因為開/關中斷指令只能運行在內核態）
TestAndSet指令（TS）
也叫做TestAndSetLock(TSL)
上鎖和檢查操作變成了原子操作
優點：實現簡單；適用多機處理環境
缺點：不滿足讓權等待原則
Swap指令
也叫做Exchange指令，或者簡稱XCHG指令
優點：實現簡單，適合多機系統
缺點：不滿足讓權等待
信號量機制
信號量其實就是一個變量，可以用一個信號量來表示系統中某種資源的數量4
原語：一種特殊的程序段，其執行只能一氣呵成，不可被中斷。（用來解決檢查和上鎖無法一氣呵成的問題）
信號量S
Wait(S) P操作
Signal(S) V操作
整型信號量
對信號量的操作只能有三種，初始化、P、V
不滿足讓權等待原則，會發生忙等
記錄型信號量
S.value<0時表示該類資源已經分配遠比，因此該進程自我阻塞。
當進行V操作發現S.value<=0時，表示在將這個資源還給系統之前有進程在阻塞等待資源，因此喚醒一個進程。
滿足進程互斥的所有原則
信號量機制實現進程互斥
信號量機制實現進程同步
為了保證進程執行的順序：
- 設置同步信號量S，初始化為0
- 在需要首先進行的操作后執行
V(S)操作 - 在條件滿足情況下執行的操作前執行
P(S)操作
如果有多個約束關系就設置多個信號量
信號量機制實現前驅關系
對于每條邊設置一個信號量，然后同進程同步（這也是一種進程同步）
生產者-消費者問題
系統中有一組生產者進程和一組消費者進程，生產者進程每次生產一個產品放入緩沖區，消費者進程每次從緩沖區中取出一個產品并適用。
生產者、消費者共享一個初始為空、大小為n的緩沖區
對臨界資源的訪問必須互斥訪問，緩沖區也是一種臨界資源（否則多個進程同時向緩沖區寫入數據可能造成數據的覆蓋）
PV操作題目分析：
- 關系分析，找出題目中描述的各個進程，分析他們之間的同步、互斥關系
- 確定P、V操作的大體順序：因為生產者每次要消耗一個空閑緩沖區，并且生產一個產品。消費者每次要消耗一個產品，并釋放一個空閑緩沖區。
- 設置信號量
對于臨界資源的訪問一定要滿足訪問條件以后再進行訪問，否則有可能導致死鎖。即先滿足進程同步條件再進行互斥操作
平時設計的時候要盡可能縮小互斥訪問PV操作覆蓋的區域，即盡可能減少臨界區中的操作，不僅是為了避免死鎖，同時還是為了提高進程的并行性。
多生產者-多消費者問題
多類生產者和多類消費者
當緩沖區資源只為1的時候我們有可能可以不專門設置訪問緩沖區的互斥信號量。不過出于良好的習慣我們還是在訪問緩沖區的時候專門加上互斥信號量。需要注意的是對互斥信號量的P操作一定要在進程同步的P操作之后，否則會引起死鎖。
我們在分析的時候理解為事件的行為（對資源的占用等等），而不是進程之間的行為。
吸煙者問題
讀者-寫者問題
潛在的問題：只要有都進程還在讀，寫進程就要一直阻塞等待，可能“餓死”。因此，這種算法中讀進程是優先的。
哲學家進餐問題
每個哲學家進程需要同時持有兩個臨界資源才能開始吃飯，所以需要避免資源分配不當導致死鎖。
- 最多只允許四個哲學家進餐
- 對于奇數號的哲學家必須先拿左邊的筷子，偶數號的哲學家必須先拿右邊的筷子
- 只允許一個哲學家拿筷子
)
