作業系統概念學習筆記 11 程序同步（一）作業系統概念學習筆記 11

互相協作的程序之間有共享的資料，于是這裡就有一個并發情況下，如何確定有序操作這些資料、維護一緻性的問題，即程序同步。

從底層到進階應用，同步機制依次有臨界區、信号量、管程、原子事務。

多個程序并發通路和操作同一資料且執行結果與通路發生的特定順序有關，稱之為競争條件（race condition）。

每個程序有一個代碼段稱為臨界區（critical section），在該區中程序可能改變共同變量、更新一個表或寫一個檔案等。這種系統的重要特征是當一個程序進入臨界區，沒有其他程序可被允許在臨界區内執行，即沒有兩個程序可同時在臨界區内執行。

臨界區問題（critical-section problem）是設計一個以便程序協作的協定。每個程序必須請求允許進入其臨界區。實作請求的代碼段稱為進入區（entry section），臨界區之後可有退出區（exit section），其他代碼段成為剩餘區（remainder section）。

一個典型程序pi的通用結構：

臨界區問題的解答必須滿足三項要求：

（1）互斥（mutual exclusion）：

如果程序pi在其臨界區内執行，那麼其他程序都不能在其臨界區内執行；

（2）前進（progress）：

如果沒有程序在其臨界區内執行且有程序需進入臨界區，那麼隻有那麼不在剩餘區内執行的程序可參加選擇，以确定誰能下一個進入臨界區，且這種選擇不能無限推遲；

（3）有限等待（bounded waiting）：

從一個程序做出進入臨界區的請求，直到該請求允許為止，其他程序允許進入其臨界區内的次數有上限。

一個作業系統，在某個時刻，可同時存在有多個處于核心模式的活動程序，是以實作作業系統的核心代碼，會存在競争條件。核心開發人員有必要確定其作業系統不會産生競争條件。

有兩種方法用于處理作業系統内的臨界區問題：

搶占核心（preemptive kernel）與非搶占核心（nonpreemptive kernel）：

搶占核心允許處于核心模式的程序被搶占。

非搶占核心不允許核心模式的程序被搶占。

非搶占核心的核心資料結構從根本上不會導緻競争條件，對于搶占核心需要認真設計以確定其核心資料結構不會導緻競争條件。

但搶占核心更受歡迎，因為搶占核心更适合實時程式設計，因為它能允許實時程序搶占處于核心模式運作的其他程序。再者，搶占核心的響應更快，因為處于核心模式的程序在釋放cpu之前不會運作過久。

peterson算法是一種經典的基于軟體的臨界區問題算法，不能確定正确運作。

peterson算法适用于兩個程序在臨界區與剩餘區間交替執行,為了友善，當使用pi時，pj來标示另一個程序，即j == i - 1。peterson算法需要在兩個程序之間共享兩個資料項：

變量turn表示哪個程序可以進入其臨界區，即如果turn==i，那麼程序pi允許在其臨界區内執行。

數組flag表示哪個程序想要進入臨界區,如果flag[i]為true，即pi想進入其臨界區。

可以證明，滿足三項要求。

通過要求臨界區用鎖來防護，就可以避免競争條件，即一個程序在進入臨界區之前必須得到鎖，而其退出臨界區時釋放鎖。

硬體特性能簡化程式設計任務且提高系統效率。

對于單處理器環境，臨界區問題可簡單地加以解決：在修改共享變量時要禁止中斷出現。這樣其他指令不可能執行，是以共享變量也不會被意外修改。這種方法通常為搶占式核心所采用。

在多處理器環境下，這種解決方法是不可行的，低效且影響系統時鐘。

特殊硬體指令以允許能原子地（不可中斷的）檢查和修改字的内容或交換兩個字的内容。如testandset()，當兩個指令同時執行在不同的cpu上，那麼它們會按任意順序來順序執行。

testandset指令定義：

使用testandset的互斥實作,聲明一個boolean變量lock，初始化為false

使用testandset的有限等待互斥：任何等待進入臨界區的程序隻需要等待n-1次。

boolean waiting[i] = true;

boolean lock;

初始化為false

swap指令的定義：

使用swap的互斥實作：key為每個程序局部變量，lock為全局變量,初始化為false

然而，對于硬體設計人員，在多處理器上實作原子指令testandset并不簡單。

應用層面解決臨界區問題：信号量

信号量s是個整數變量，除了初始化外，它隻能通過兩個标準原子操作：wait()和signal()來通路。即p和v。

wait()的定義可表示為：

signal()的定義可表示為：

在wait()和signal()操作中，對信号量整型值的修改必須不可分地執行。

通常作業系統區分計數信号量和二進制信号量。計數信号量的值域不受限制，而二進制信号量的值隻能為0或1,有的系統，。由于二進制信号量是互斥的，因而可以将其應用于處理多程序的臨界區問題。

使用信号量的互斥實作：n個程序共享信号量mutex，初始值1

計數信号量可以用來控制通路具有若幹個執行個體的某種資源。該信号量初始化為可用資源的數量。當每個程序需要使用資源時，需要對該信号量執行wait()操作。當程序釋放資源時，需要對該信号執行signal()操作。

可以用信号量來解決各種同步問題。如先執行pi的s1語句，然後再執行pj的s2語句，可以通向一個信号量，初始化為0，然後執行s1完，執行signal()，在執行s2前，執行wait()。

信号量的主要缺點是要求忙等待（busy waiting）。即在進入代碼段中連續地循環。忙等待浪費了cpu時鐘，這種類型的信号量也稱為自旋鎖（spinlock），這是因為程序在其等待鎖的時還在運作(自旋鎖有其優點，程序在等待鎖時不進行上下文切換，而上下文切換可能需要花費相當長的時間。是以如果鎖占用的時間短，那麼鎖就有用了，自旋鎖常用于多處理器系統中，這樣一個線程在一個處理器自旋時，另一線程可在另一個處理器上在其臨界區内執行)

為克服這一缺點，修改wait()和signal()的定義，信号量值不為正時，不是忙等而是阻塞自己，阻塞操作将一個程序放入到與信号量相關的等待隊列中，并将該程序的狀态切換成等待狀态，接着，控制轉到cpu排程程式，以選擇另一個程序來執行。

被阻塞在等待信号Ｓ上的程序，可以在其他程序執行signal()的時候操作之後重新被執行，該程序的重新執行是通過wakeup()操作來進行的将程序從等待狀态切換到就緒狀态。接着程序被放到就緒隊列中。

因而将信号量定義為如下：

每個信号量都有一個整型值和一個程序連結清單，當一個程序必須等待信号量時，就加入到程序連結清單上，操作signal()會從等待程序連結清單中取一個程序以喚醒。

wait()實作：

signal()實作：

操作block()挂起調用他的程序。

操作wakeup(p)重新啟動阻塞程序Ｐ的執行。

這兩個操作都是由作業系統作為基本系統調用來提供的。

在具有忙等的信号量經典定義下，信号量的值絕對不能為負數，但是本實作可能造成信号量為負值。如果信号量為負值，那麼其絕對值就是等待該信号量的程序的個數。

等待程序的連結清單可以利用程序控制塊pcb中的一個連結域來加以輕松實作。即每個信号量包括一個整型值和一個pcb連結清單的指針。

信号量的關鍵之處是它們原子的執行。必須確定沒有兩個程序能同時對一個信号量進行操作，在單處理器情況下，可以在執行wait()和signal()的時候簡單的關閉中斷，保證隻有目前程序進行。

多處理器下，若禁止所有cpu的中斷，則會嚴重影響性能，smp系統必須提供其他加鎖技術（如自旋鎖），以確定wait()與signal()可原子地執行。

具有等待隊列的信号量的實作可能會導緻這樣的情況：

兩個或多個程序無限地等待一個事件，而該事件隻能由這些等待程序之一來産生。這裡的事件是signal()操作的執行。當出現這樣的狀态時，這些程序就稱為死鎖（deadlocked）。

例如，一個由p1 p2　組成的系統，每個都通路共享的信号量Ｓ和Ｑ，ＳＱ初值均為１：

p0:

p1:

假設，p0執行wait(s)，接着p1執行wait(q),p0再執行wait(q)時，必須等待，直到p1執行signal(q),而此時p1也在等待p0執行signal(s),兩個操作都不能進行，p0和p1就死鎖了。

與死鎖相關的另一個問題是無限期阻塞（indefinite blocking）或饑餓（starvation）：即程序在信号量内無限期等待。

舉個例子來了解死鎖與饑餓的差別：

死鎖(deadlock)

指的是兩個或者兩個以上的程序互相競争系統資源，導緻程序永久阻塞。

例如：

1、桌子上有慢慢一桌子的美食，但是隻有一雙筷子。

2、甲拿了一根，然後在找另一根。

3、乙拿了一根，然後也在找另一根。

4、因為他們都掌握了對方必需的資源，導緻最後他們倆誰都吃不到美食。

饑餓(starvation)

指的是等待時間已經影響到程序運作，此時成為饑餓現象。如果等待時間過長，導緻程序使命已經沒有意義時，稱之為“餓死”。

1、小明要告訴媽媽明天開家長會。

2、小明媽媽因為工作太忙，在公司加班，沒有回家。

3、于是第二天，小明的媽媽就錯過了家長會。（“餓死”）

4、其實小明的媽媽沒有出現“死鎖”。隻是小明的優先級過低，不如工作重要。

假設緩沖池有n個緩沖項，每個緩沖項能存在一個資料項。信号量mutex提供了對緩沖池通路的互斥要求，并初始化為1。信号量empty和full分别用來表示空緩沖項和滿緩沖項的個數，信号量empty初始化為n；而信号量full初始化為0。

生産者程序結構：

消費者程序結構：

隻讀資料庫的程序稱為讀者；更新（讀和寫）資料庫的稱為寫者。

第一讀者-寫者問題：要求沒有讀者需要保持等待除非已有一個寫者已獲得允許已使用共享資料庫。換句話說，沒有讀者會因為一個寫者在等待而會等待其他讀者的完成。

第二讀者-寫者問題：要求一旦寫者就緒，那麼寫者會盡可能快得執行其寫操作。換句話說，如果一個寫者等待通路對象，那麼不會有新讀者開始讀操作。

對于這兩個問題的解答可能導緻饑餓問題。對第一種情況，寫者可能饑餓；對第二種情況，讀者可能饑餓。

對于第一讀者－寫者問題的解決:

讀者程序共享以下資料結構：

信号量mutex和wrt初始化為1，readcount初始化為0，信号量wrt為讀者和寫者程序所共有。信号量mutex用于確定在更新變量readcount時的互斥。變量readcount用來跟蹤有多少程序正在讀對象。信号量wrt供寫者作為互斥信号量，它為第一個進入臨界區和最後一個離開臨界區的讀者所使用，而不被其他讀者所使用。

寫者程序結構：

讀者程序結構：

推廣為讀寫鎖。

在以下情況下最為有用：

一是，當可以區分哪些程序隻需要讀共享資料，哪些程序隻需要寫共享資料；

二是，當讀者程序數比寫程序多時。

拿起與他相近的兩隻筷子，一個哲學家一次隻能拿起一隻筷子，同時有兩隻筷子時，就能吃，吃完，會放下兩隻筷子。

一種簡單的方法，每隻筷子都用一個信号量來表示。一個哲學家通過執行wait()操作試圖擷取相應的筷子，他會通過執行signal()操作以釋放相應的筷子。

共享資料為：semaphore chopstick[5];其中所有chopstick的元素初始化為1。

哲學家i的結構：

但這種方法會發生死鎖，例如，所有哲學家同時饑餓，且同時拿起左邊的筷子。

多種可以解決死鎖的方法：

①最多隻允許4個哲學家同時坐在桌子上；

②隻有兩隻筷子都可用時才允許一個哲學家拿起它們（他必須在臨界區内拿起兩隻筷子）；

③使用非對稱解決方法，即技術哲學家先拿起左邊的筷子，接着拿起右邊的筷子，而偶數哲學家先拿起右邊的筷子，接着拿起左邊的筷子。