進程間通信（一）：進程之間的沖突與處理方式
——《現代操作系統第二章第三節》
1、問題的提出
我們想象一個假脫機打印程序，當一個進程需要打印一個文件時，它會將該文件放在一個假脫機目錄下。另一個進程負責周期性地檢查是否有文件需要被打印，如果有就打印並將其在目錄中刪除。簡單設想，脫機目錄中有很多槽位，每個槽位中存放文件名，假設它們有兩個共享的變量：out，指向下一個要被打印的文件；in，指向下一個空閒的槽位。如圖，下一個被打印的應該是4號槽，下一個入隊的應該是7號槽。
現在，假設進程A、B將把文件A、B入隊，假設A先讀到的信息是7，並且A將7存入自己的一個記憶變量中，而這時，系統認為已經分給了A足夠的時間，於是中斷A切換置進程B。進程讀到的信息是7，將7存入自身的一個記憶變量中，並將int更新至8。至此B已經完成了所有的入隊操作，轉而去干其他的事情。當A繼續執行時，它還認為應該將文件存到7號槽，於是A文件成功地覆蓋住了B文件，而我們的B文件，永遠都不會被打印。問題就出現了。
2、抽象一些概念
競爭條件：類似於上述情況，即兩個或者多個進程讀寫某些共享數據，而最後的結果取決於進程的運行的精確時序，稱為競爭條件。（把條件理解成情況，競爭情況，貌似更加容易理解一些=。=）
互斥：互斥是一種手段，它使共享數據的進程無法同時對其共享的數據進行處理。
臨界區：即訪問共享內存的程序片。也就是說，通過合理的安排，使得兩個進程不可能同時處在臨界區中，就能避免競爭條件。
忙等待：連續測試一個變量直至某值出現位止。（如語句while(t!=0){},那麼當t不為零時，while()之後的語句將永遠不會執行，這種情況書中好像也叫掛起）
自旋鎖：用於忙等待的鎖。（在3-（3）中，turn即使自旋鎖）
3、忙等待的互斥（幾種實現互斥的方法）
（1）屏蔽中斷
原理：進程進入臨界區後立即屏蔽所有中斷，離開後打開中斷。
缺點：a、多核的系統無效（其他進程任然可以占用其他的CPU繼續訪問公共內
存）
b、用戶程序來控制中斷會很危險（使想一下，一個進程屏蔽中斷後不再
打開中斷，那你的系統就GG了）
結論：屏蔽中斷對系統本身是一項很有用的技術，但對用戶進程不是一種合適的
通用互斥機制。
（2）鎖變量
原理：屏蔽中斷的軟件實現機制。
假定一個共享（鎖）變量，初值為0，代表臨界區內無進程，進程進入臨
界區後將其改變為1，代表臨界區內有進程；倘若進程在進入臨界區之前，
鎖變量值為1，該進程將等待其值變為0。
未能實現的原因：與假脫機目錄的疏漏一樣，如果一個進程進入臨界區，但是在
它把鎖變量置1之前被中斷，另一個進程進入臨界區後將0置1，這樣，
當前一個進程再次運行時它也將鎖變量置1，這樣臨界區內依然存在兩
個進程。
（3）嚴格輪換
原理：共享turn變量，用來記錄輪到那個進程進入臨界區。
當turn=0時，只有進程0能進入臨界區，進程0在離開臨界區前將turn
置1，從而標志，輪到進程1進入臨界區。
缺點：嚴格地輪換，可能導致臨界區外的進程阻塞需要進入臨界區的進程（例
如：當turn=0時，意味著只有進程0能進入臨界區，這時如果進程0還要
100年才會進入臨界區，而進程1需要馬上進入，那進程1還要白白等100
年.）
總結：當一個進程比另一個進程慢了許多的情況下，不宜用這種方式。
（4）Peterson解法
這是Peterson本人發明的一種簡單的互斥算法。
我們分情況跑一遍程序：
a、進程0通過調用enter_region()進入臨界區，此時1也想調用enter_region()
來進入臨界區，但interested[0]為TRUE，因此被while循環掛起，當進程0出臨
界區時調用leave_region()，將interested[0]設為FALSE，進程1即可及時進入臨界
區。
b、當進程0在調用enter_region()過程的任意時刻被中斷，進程1進入臨界區
後進程0再次進行時，依然會被掛起。（實際上while循環體中的兩條判斷句就
保證了，當一個進程在臨界區中時，另一個想進入臨界區的進程必然會被掛起）。
（5）TSL指令
原理簡述：
TSL（test and set lock）,是十分適合多處理器計算機實現互斥的硬件支持。它會
在一個進程進入臨界區時，鎖住內存總線，從而禁止其他CPU在本指令結束之前
訪問內存。
對於TSL指令，本文之做簡單的原理性描述（雖然老師上課講的比較詳細），想進
一步了解關於TSL指令，可以看一下書中本節內容，有詳細闡述。
4、綜述
要想擬定一個方案，使它既能避免競爭條件，又能保證進程運行與協作的效率，必須要滿足4個條件。
(1)、任何兩個進程不能同時處於臨界區
(2)、不應對CPU的速度和數量做任何假定
(3)、臨界區外運行的進程不能阻塞其他進程
(4)、不得使進程無限期等待進入臨界區
（下圖為避免競爭條件的模型圖）
