操作系统概念学习笔记 11 进程同步（一）
操作系統概念學習筆記 11
進程同步（一）
互相協作的進程之間有共享的數據，于是這里就有一個并發情況下，如何確保有序操作這些數據、維護一致性的問題，即進程同步。
從底層到高級應用，同步機制依次有臨界區、信號量、管程、原子事務。
多個進程并發訪問和操作同一數據且執行結果與訪問發生的特定順序有關，稱之為競爭條件（race condition）。
臨界區（critical section）
每個進程有一個代碼段稱為臨界區（critical section），在該區中進程可能改變共同變量、更新一個表或寫一個文件等。這種系統的重要特征是當一個進程進入臨界區，沒有其他進程可被允許在臨界區內執行，即沒有兩個進程可同時在臨界區內執行。
臨界區問題（critical-section problem）是設計一個以便進程協作的協議。每個進程必須請求允許進入其臨界區。實現請求的代碼段稱為進入區（entry section），臨界區之后可有退出區（exit section），其他代碼段成為剩余區（remainder section）。
一個典型進程Pi的通用結構：
do{進入區臨界區退出區剩余區}while(TRUE)臨界區問題的解答必須滿足三項要求：
（1）互斥（mutual exclusion）：
如果進程Pi在其臨界區內執行，那么其他進程都不能在其臨界區內執行；（2）前進（progress）：
如果沒有進程在其臨界區內執行且有進程需進入臨界區，那么只有那么不在剩余區內執行的進程可參加選擇，以確定誰能下一個進入臨界區，且這種選擇不能無限推遲；（3）有限等待（bounded waiting）：
從一個進程做出進入臨界區的請求，直到該請求允許為止，其他進程允許進入其臨界區內的次數有上限。
一個操作系統，在某個時刻，可同時存在有多個處于內核模式的活動進程，因此實現操作系統的內核代碼，會存在競爭條件。內核開發人員有必要確保其操作系統不會產生競爭條件。
有兩種方法用于處理操作系統內的臨界區問題：
搶占內核（preemptive kernel）與非搶占內核（nonpreemptive kernel）：
搶占內核允許處于內核模式的進程被搶占。
非搶占內核不允許內核模式的進程被搶占。
非搶占內核的內核數據結構從根本上不會導致競爭條件，對于搶占內核需要認真設計以確保其內核數據結構不會導致競爭條件。
但搶占內核更受歡迎，因為搶占內核更適合實時編程，因為它能允許實時進程搶占處于內核模式運行的其他進程。再者，搶占內核的響應更快，因為處于內核模式的進程在釋放CPU之前不會運行過久。
Peterson算法
Peterson算法是一種經典的基于軟件的臨界區問題算法，不能確保正確運行。
Peterson算法適用于兩個進程在臨界區與剩余區間交替執行,為了方便，當使用Pi時，Pj來標示另一個進程，即j == i - 1。Peterson算法需要在兩個進程之間共享兩個數據項：
int turn;boolean flag[2];變量turn表示哪個進程可以進入其臨界區，即如果turn==i，那么進程Pi允許在其臨界區內執行。
數組flag表示哪個進程想要進入臨界區,如果flag[i]為true，即Pi想進入其臨界區。
//進程Pi的Peterson算法 do{flag[i]=TRUE;turn=j;while(flag[j]&&turn==j);臨界區flag[i]=FALSE;剩余區}while(TRUE)可以證明，滿足三項要求。
硬件同步
通過要求臨界區用鎖來防護，就可以避免競爭條件，即一個進程在進入臨界區之前必須得到鎖，而其退出臨界區時釋放鎖。
do{請求鎖臨界區釋放鎖剩余區}while(TRUE)硬件特性能簡化編程任務且提高系統效率。
對于單處理器環境，臨界區問題可簡單地加以解決：在修改共享變量時要禁止中斷出現。這樣其他指令不可能執行，所以共享變量也不會被意外修改。這種方法通常為搶占式內核所采用。
在多處理器環境下，這種解決方法是不可行的，低效且影響系統時鐘。
特殊硬件指令以允許能原子地（不可中斷的）檢查和修改字的內容或交換兩個字的內容。如TestAndSet()，當兩個指令同時執行在不同的CPU上，那么它們會按任意順序來順序執行。
TestAndSet指令定義：
boolean TestAndSet(boolean *target){boolean rv=*target;*target=TRUE;return rv;}使用TestAndSet的互斥實現,聲明一個Boolean變量lock，初始化為false
do{while(TestAndSetLock(&lock));//do nothing//critical sectionlock=FALSE;//remainder section}while(TRUE);使用TestAndSet的有限等待互斥：任何等待進入臨界區的進程只需要等待n-1次。
boolean waiting[i] = TRUE;
boolean lock;
初始化為false
Swap指令的定義：
void Swap(boolean *a,boolean *b){booleab temp=*a;*a=*b;*b=temp;}使用Swap的互斥實現：key為每個進程局部變量，lock為全局變量,初始化為false
do{key=TRUE;while(key==TRUE)Swap(&lock,&key);//critical sectionlock=FALSE;//remainder section}while(TRUE);然而，對于硬件設計人員，在多處理器上實現原子指令TestAndSet并不簡單。
信號量（semaphore）
應用層面解決臨界區問題：信號量
信號量S是個整數變量，除了初始化外，它只能通過兩個標準原子操作：wait()和signal()來訪問。即P和V。
wait()的定義可表示為：
wait(S){while(S<=0);//no-opS--;}signal()的定義可表示為：
signal(S){S++;}在wait()和signal()操作中，對信號量整型值的修改必須不可分地執行。
用法：
通常操作系統區分計數信號量和二進制信號量。計數信號量的值域不受限制，而二進制信號量的值只能為0或1,有的系統，。由于二進制信號量是互斥的，因而可以將其應用于處理多進程的臨界區問題。
使用信號量的互斥實現：n個進程共享信號量mutex，初始值1
do{wait(mutex);//critical sectionsignal(mutex);//remainder section}while(TRUE);計數信號量可以用來控制訪問具有若干個實例的某種資源。該信號量初始化為可用資源的數量。當每個進程需要使用資源時，需要對該信號量執行wait()操作。當進程釋放資源時，需要對該信號執行signal()操作。
可以用信號量來解決各種同步問題。如先執行Pi的S1語句，然后再執行Pj的S2語句，可以通向一個信號量，初始化為0，然后執行S1完，執行signal()，在執行S2前，執行wait()。
實現：
信號量的主要缺點是要求忙等待（busy waiting）。即在進入代碼段中連續地循環。忙等待浪費了CPU時鐘，這種類型的信號量也稱為自旋鎖（spinlock），這是因為進程在其等待鎖的時還在運行(自旋鎖有其優點，進程在等待鎖時不進行上下文切換，而上下文切換可能需要花費相當長的時間。因此如果鎖占用的時間短，那么鎖就有用了，自旋鎖常用于多處理器系統中，這樣一個線程在一個處理器自旋時，另一線程可在另一個處理器上在其臨界區內執行)
為克服這一缺點，修改wait()和signal()的定義，信號量值不為正時，不是忙等而是阻塞自己，阻塞操作將一個進程放入到與信號量相關的等待隊列中，并將該進程的狀態切換成等待狀態，接著，控制轉到CPU調度程序，以選擇另一個進程來執行。
被阻塞在等待信號Ｓ上的進程，可以在其他進程執行signal()的時候操作之后重新被執行，該進程的重新執行是通過wakeup()操作來進行的將進程從等待狀態切換到就緒狀態。接著進程被放到就緒隊列中。
因而將信號量定義為如下：
typedef struct{int value; //記錄了這個信號量的值 struct process *list; //儲存正在等待這個信號量的進程（PCB鏈表指針）}semaphore;每個信號量都有一個整型值和一個進程鏈表，當一個進程必須等待信號量時，就加入到進程鏈表上，操作signal()會從等待進程鏈表中取一個進程以喚醒。
wait()實現：
wait(semaphore *S){S->value--;if(S->value <0){ //沒有資源add this process to S->list; //進入等待隊列 block(); //堵塞 }}signal()實現：
signal(semaphore *S){S->value++;if(S->value<=0){ //上面++后，S仍然還<=0，說明資源供不應求，等待者還有很多，于是喚醒等待隊列中的一個remove a process P from S->list;wakeup(P); //切換到就緒狀態 }}操作block()掛起調用他的進程。
操作wakeup(P)重新啟動阻塞進程Ｐ的執行。
這兩個操作都是由操作系統作為基本系統調用來提供的。
在具有忙等的信號量經典定義下，信號量的值絕對不能為負數，但是本實現可能造成信號量為負值。如果信號量為負值，那么其絕對值就是等待該信號量的進程的個數。
等待進程的鏈表可以利用進程控制塊PCB中的一個鏈接域來加以輕松實現。即每個信號量包括一個整型值和一個PCB鏈表的指針。
信號量的關鍵之處是它們原子的執行。必須確保沒有兩個進程能同時對一個信號量進行操作，在單處理器情況下，可以在執行wait()和signal()的時候簡單的關閉中斷，保證只有當前進程進行。
多處理器下，若禁止所有CPU的中斷，則會嚴重影響性能，SMP系統必須提供其他加鎖技術（如自旋鎖），以確保wait()與signal()可原子地執行。
死鎖與饑餓：
具有等待隊列的信號量的實現可能會導致這樣的情況：
兩個或多個進程無限地等待一個事件，而該事件只能由這些等待進程之一來產生。這里的事件是signal()操作的執行。當出現這樣的狀態時，這些進程就稱為死鎖（deadlocked）。
例如，一個由P1 P2 組成的系統，每個都訪問共享的信號量Ｓ和Ｑ，ＳＱ初值均為１：
P0:
wait(S);wait(Q);//......signal(S);signal(Q);P1:
wait(Q);wait(S);//......signal(Q);signal(S);假設，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。
生產者進程結構：
do{…//produce an item in next p…wait(empty);wait(mutex);…//add next p to buffer…signal(mutex);signal(full);}while(TRUE);消費者進程結構：
do{wait(full);wait(mutex);…//remove an item from buffer to next c…signal(mutex);signal(empty);…//consume the item in next c…}while(TRUE);讀者-寫者問題：
只讀數據庫的進程稱為讀者；更新（讀和寫）數據庫的稱為寫者。
第一讀者-寫者問題：要求沒有讀者需要保持等待除非已有一個寫者已獲得允許已使用共享數據庫。換句話說，沒有讀者會因為一個寫者在等待而會等待其他讀者的完成。
第二讀者-寫者問題：要求一旦寫者就緒，那么寫者會盡可能快得執行其寫操作。換句話說，如果一個寫者等待訪問對象，那么不會有新讀者開始讀操作。
對于這兩個問題的解答可能導致饑餓問題。對第一種情況，寫者可能饑餓；對第二種情況，讀者可能饑餓。
對于第一讀者－寫者問題的解決:
讀者進程共享以下數據結構：
semaphore mutex, wrt;int readcount;信號量mutex和wrt初始化為1，readcount初始化為0，信號量wrt為讀者和寫者進程所共有。信號量mutex用于確保在更新變量readcount時的互斥。變量readcount用來跟蹤有多少進程正在讀對象。信號量wrt供寫者作為互斥信號量，它為第一個進入臨界區和最后一個離開臨界區的讀者所使用，而不被其他讀者所使用。
寫者進程結構：
do{wait(wrt);…;//writing is performed…;signal(wrt);}while(TRUE);讀者進程結構：
do{wait(mutex);readcount++;if(readcount==1)wait(wrt);signal(mutex);…;//reading is performed…;wait(mutex);readcount--;if(readcount==0)signal(wrt);signal(mutex);}while(TRUE);推廣為讀寫鎖。
在以下情況下最為有用：
一是，當可以區分哪些進程只需要讀共享數據，哪些進程只需要寫共享數據；
二是，當讀者進程數比寫進程多時。
哲學家進餐問題：
拿起與他相近的兩只筷子，一個哲學家一次只能拿起一只筷子，同時有兩只筷子時，就能吃，吃完，會放下兩只筷子。
一種簡單的方法，每只筷子都用一個信號量來表示。一個哲學家通過執行wait()操作試圖獲取相應的筷子，他會通過執行signal()操作以釋放相應的筷子。
共享數據為：semaphore chopstick[5];其中所有chopstick的元素初始化為1。
哲學家i的結構：
do{wait(chopstick[i]);wait(chopstick[(i+1)%5]);…;//eat…;signal(chopstick[i]);signal(chopstick[(i+1)%5]);…;//think…;}while(TRUE);但這種方法會發生死鎖，例如，所有哲學家同時饑餓，且同時拿起左邊的筷子。
多種可以解決死鎖的方法：
①最多只允許4個哲學家同時坐在桌子上；
②只有兩只筷子都可用時才允許一個哲學家拿起它們（他必須在臨界區內拿起兩只筷子）；
③使用非對稱解決方法，即技術哲學家先拿起左邊的筷子，接著拿起右邊的筷子，而偶數哲學家先拿起右邊的筷子，接著拿起左邊的筷子。
總結
以上是生活随笔為你收集整理的操作系统概念学习笔记 11 进程同步（一）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 位于运算符：
- 下一篇： FreeBsdb FAMP Lamp环境