2.3_3 進程互斥的硬件實現方法

學習提示：

1.理解各方法的原理

2.了解各方法的優缺點

（一）中斷屏蔽方法

??利用“開/關中斷指令”實現（與原語的實現思想相同，即在某進程開始訪問臨界區到結束訪問為止都不允許被中斷，也就不能發生進程切換，因此也不可能發生兩個同

時訪問臨界區的情況）

??優點：簡單、高效。

??缺點：不適用于多處理機；只適用于操作系統內核進程，不適用于用戶進程（因為開/關中斷指令只能運行在內核態，這組指令如果能讓用戶隨意使用會很危險）

為什么“不適用于多處理機”——因為關中斷只對當前處理機有用。例如在處理機A上執行關中斷，那么處理機B仍然是正常狀態，處理機B上的進程仍然能夠訪問該臨界區。

（二）TestAndSet指令

??簡稱TS指令，也有地方稱為TestAndSetLock指令，或TSL指令。

??TSL指令是用硬件實現的，執行的過程不允許被中斷，只能一氣呵成。以下是用C語言描述的邏輯。

??若剛開始lock是false，則TSL返回的old值為false，while循環條件不滿足，直接跳過循環，進入臨界區。

??若剛開始lock是true，則執行TSL后old返回的值為true，while循環條件滿足，會一直循環，直到當前訪問臨界區的進程在退出區進行“解鎖”。

??相比軟件實現方法，TSL指令把“上鎖”和“檢查”操作用硬件的方式變成了一氣呵成的原子操作。

??優點：實現簡單，無需像軟件實現方法那樣嚴格檢查是否會有邏輯漏洞；適用于多處理機環境。

??缺點：不滿足“讓權等待”原則，暫時無法進入臨界區的進程會占用CPU并循環執行TSL指令，從而導致“忙等”。

（三）Swap指令

??有的地方叫Exchange指令，或簡稱XCHG指令。

??Swap指令是用硬件實現的，執行的過程不允許被中斷，只能一氣呵成。以下是用C語言描述的邏輯。

??邏輯上來看 Swap 和 TSL 并無太大區別，都是先記錄下此時臨界區是否已經被上鎖（記錄在 old 變 量上），再將上鎖標記 lock 設置為 true，最后檢查 old，如果 old 為 false 則說明之前沒有別的進程對臨界區上鎖，則可跳出循環，進入臨界區。

??所以，Swap指令的優點、缺點，和TSL大體上也是一樣的。

??優點：實現簡單，無需像軟件實現方法那樣嚴格檢查是否會有邏輯漏洞；適用于多處理機環境。

??缺點：不滿足“讓權等待”原則，暫時無法進入臨界區的進程會占用CPU并循環執行Swap指令，從而導致“忙等”。

總結

（四）互斥鎖

??解決臨界區最簡單的工具就是互斥鎖（mutex lock）。一個進程在進入臨界區時應獲得鎖；在退出臨界區時釋放鎖。函數acquire()獲得鎖，而函數release()釋放鎖。

??每個互斥鎖有一個布爾變量available，表示鎖是否可用。如果鎖是可用的，調用acquire()會成功，且鎖不再可用。當一個進程試圖獲取不可用的鎖時，會被阻塞，直到鎖被釋放。

acquire() {		//獲得鎖while(!available);	//忙等待available = false;	//獲得鎖
}release() {		//釋放鎖available = true;	//釋放鎖
}

??acquire()或release()的執行必須是原子操作，因此互斥鎖通常采用硬件機制來實現。

??互斥鎖的主要缺點是忙等待，當有一個進程在臨界區中，任何其他進程在進入臨界區時必須連續循環調用acquire()。當多個進程共享同一CPU時，就浪費了CPU周期。因此，互斥鎖通常用于多處理機系統，一個線程可以在一個處理機上等待，不影響其他線程的執行。

??需要連續循環忙等的互斥鎖，都可稱為自旋鎖（spin lock），如TSL指令、Swap指令、單標志法。

特性：

??1.需忙等，進程時間片用完才下處理機，違反“讓權等待”。

??2.優點：等待期間不用切換進程上下文，多處理器系統中，若上鎖的時間短，則等待代價很低。

??3.常用于多處理器系統，一個核忙等，其他核照樣工作，并快速釋放臨界區。

??4.不太適用于單處理機系統，忙等的過程中不可能解鎖。