OS4進程管理2同步與互斥

內(nèi)容綱要上節(jié)回顧進程互斥進程同步進程間通信1/14/20251回顧進程的概念進程的控制數(shù)據(jù)結(jié)構(gòu)進程的狀態(tài)轉(zhuǎn)換1/14/20252進程的基本狀態(tài)運行態(tài)阻塞態(tài)就緒態(tài)？1/14/20253進程的基本狀態(tài)問題1：為什么不能從阻塞態(tài)變?yōu)檫\行態(tài)呢？問題2：為什么不能從就緒態(tài)變?yōu)樽枞麘B(tài)呢？問題3：如果系統(tǒng)中有N個進程，運行的進程最多幾個，最少幾個；就緒進程最多幾個最少幾個；等待進程最多幾個，最少幾個？1/14/20254PCB表系統(tǒng)把所有PCB組織在一起，并把它們放在內(nèi)存的固定區(qū)域，就構(gòu)成了PCB表；PCB表的大小決定了系統(tǒng)中最多可同時存在的進程個數(shù)，稱為系統(tǒng)的并發(fā)度。PCB表被系統(tǒng)訪問的頻率很高，因此是全部或部分常駐內(nèi)存的。操作系統(tǒng)專門開辟一個PCB表區(qū)，每個PCB是一片連續(xù)的存儲單元。PCB表組織方式鏈接方式索引方式1/14/20255PCB表實現(xiàn)：鏈接方式鏈接方式是經(jīng)常采用的方式。其原理是：按照進程的不同狀態(tài)分別將其放在不同的隊列。Linux操作系統(tǒng)就是應(yīng)用這種進程控制塊組織方式。運行隊列指針就緒隊列指針PCBPCBPCB0阻塞隊列1指針阻塞隊列2指針PCB0PCBPCBPCB0PCBPCBPCB0PCB鏈接隊列示意圖1/14/20256PCB表實現(xiàn)：索引方式系統(tǒng)根據(jù)所有進程的狀態(tài)建立幾張索引表。阻塞索引表就緒索引表執(zhí)行指針就緒表指針阻塞表指針PCB1PCB2PCB3PCB4PCB5PCB6PCB7

PCB索引結(jié)構(gòu)示意圖1/14/20257本講內(nèi)容上節(jié)回顧進程互斥進程同步進程間通信1/14/20258進程互斥進程的并發(fā)特性獨立性異步性對有限的資源的共享和競爭引起進程的相互制約臨界資源1/14/20259臨界資源的概念何謂臨界資源？兩個或兩個以上的進程不能同時使用的資源臨界資源實例一些獨占設(shè)備，如打印機、磁帶機等一些共享變量、表格、鏈表等1/14/202510臨界資源的概念何謂臨界區(qū)？每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)。在臨界區(qū)前面增加一段用于進行檢查的代碼，把這段代碼稱為進入?yún)^(qū)；相應(yīng)地，在臨界區(qū)后面再加一段用于退出臨界區(qū)的代碼，稱為退出區(qū)。進程中除去上述進入?yún)^(qū)和退出區(qū)，其它部分的代碼，稱為剩余區(qū)。這樣，可將一個訪問臨界資源的進程描述如下：

repeat

進入?yún)^(qū)；臨界區(qū)；退出區(qū)；剩余區(qū)；

untilfalse;1/14/202511互斥執(zhí)行時必須滿足的4條準則不能假設(shè)各并發(fā)進程的相對執(zhí)行速度。并發(fā)進程中的某個進程不在臨界區(qū)時，它不能阻止其他進程進入臨界區(qū)。并發(fā)進程中的若干進程申請進入臨界區(qū)時，只能允許一個進程進入。并發(fā)進程中的某個進程申請進入臨界區(qū)時開始，應(yīng)在有限時間內(nèi)得以進入臨界區(qū)。準則1、2、3保證并發(fā)進程享有平等的、獨立的競爭和使用公有資源的權(quán)力，并且保證每一個時刻至多只有一個進程在臨界區(qū)。準則4則是在并發(fā)進程不發(fā)生死鎖的重要保證，否則，由于某個并發(fā)進程長期占有臨界區(qū)，其他進程則因為不能進入臨界區(qū)而進入相互等待狀態(tài)。1/14/202512互斥的加鎖實現(xiàn)解決思想設(shè)定監(jiān)控變量（lock），通過其值變化控制進程操作進程AWhile(lock!=0)NULL;lock＝1;Critical_region();lock＝0；進程BWhile(lock!=0)NULL;lock=1; Critical_region();lock=0;lock＝0依然存在競爭條件，不能根本解決互斥問題致命缺陷：不具有操作的原子性1/14/202513鎖變量的缺陷示例進程AWhile(lock!=0);進程BWhile(lock!=0);lock＝0進程Alock＝1;Critical_Region();進程Block=1; Critical_Region();發(fā)生進程調(diào)度，互斥的進程開始運行發(fā)生進程調(diào)度，A并不知道B也進入臨界區(qū)發(fā)生進程調(diào)度，B并不知道A也進入臨界區(qū)1/14/202514互斥的加鎖實現(xiàn)缺陷：不能保證同一時間只有一個進程進入臨界區(qū)解決方法：某些機器在硬件中提供了“testandset”的指令，保證對臨界區(qū)進入條件的判斷(lock!=0)與資源狀態(tài)的修改操作(lock=1)的不可分離性1/14/202515鎖的具體實現(xiàn)方法1：關(guān)中斷l(xiāng)ock(){disableInterupts;}Unlock(){enableInterrupts;}1/14/202516鎖的具體實現(xiàn)方法2：原子指令序列

用硬件實現(xiàn)test-and-set指令，涉及從一個內(nèi)存單元的讀出與寫入在單處理機上很容易實現(xiàn)可以應(yīng)用到多處理機上，但要考慮Cache一致性協(xié)議，相對復(fù)雜一些1/14/202517信號量機制基本概念信號量（Semaphore）：一個整數(shù)，表示并發(fā)進程可以使用的資源數(shù)。Down與Up原語（P/V、S/W原語）Dijkstra于1965年提出Probern和Verhogen原語信號量是一種廣義上的“鎖”原語：OS以關(guān)中斷形式實現(xiàn)的不可打斷操作1/14/202518信號量與P/V原語基本性質(zhì)信號量的初值是一個正整數(shù)當信號量大于0時，說明“環(huán)境安全”，可繼續(xù)運行當信號量小于0時，說明“互斥等待”，只能阻塞推廣到一般情況，信號量可解決復(fù)雜的同步互斥問題1/14/202519信號量與P/V原語P原語將信號量sem減1

如果sem減一后小于0，那么將進程加入等待隊列1/14/202520信號量與P/V原語V原語將信號量加1，并喚醒等待的進程1/14/202521最基本互斥機制的實現(xiàn)進程Awhile(TRUE){nocritical_region();P(mutex);critical_region();V(mutex);nocritical_region();}int

mutex=1進程Bwhile(TRUE){nocritical_region();P(mutex);critical_region();V(mutex);nocritical_region();}1/14/202522本講內(nèi)容上節(jié)回顧進程互斥進程同步進程間通信1/14/202523同步問題實例：一并發(fā)程序任務(wù)：

f,s,t,g:存放記錄的內(nèi)存區(qū)域進程Get,Copy,Put完成f到g的記錄搬移工作（每次搬一個記錄）1/14/202524可能的進程執(zhí)行順序1/14/202525合理的進程執(zhí)行順序1/14/202526進程同步同步關(guān)系分析兩個或者多個進程在運行順序上存在固定的規(guī)則由于分時操作系統(tǒng)的不確定性，導(dǎo)致同步關(guān)系無法保持必須進行顯式的程序控制，保證同步關(guān)系的正確1/14/202527同步vs.互斥同步與互斥的差別互斥：體現(xiàn)為排他性，可表現(xiàn)為“0－1”關(guān)系同步：體現(xiàn)為時序性，比互斥更加復(fù)雜和多變解決思路保證解決辦法對互斥和同步的適用性1/14/202528同步的概念進程互斥時執(zhí)行順序可以是任意的；同步是相互制約的。直接制約：一組在異步環(huán)境下的并發(fā)進程，各自的執(zhí)行結(jié)果互為對方的執(zhí)行條件，從而限制各進程的執(zhí)行速度的過程稱為并發(fā)進程間的直接制約。1/14/202529同步的解決辦法1私有信號量：這些信號量只與制約進程和被制約進程有關(guān)而不是與整組并發(fā)進程有關(guān)。公有信號量：互斥時使用。1/14/202530同步的解決辦法2（P/V原語）圖：緩沖區(qū)隊列1/14/202531生產(chǎn)者－消費者問題分析互斥關(guān)系分析任何時刻，只能有一個進程在緩沖區(qū)中操作引入互斥信號量（二元信號量）信號量為0，表明已有進程進入臨界區(qū)；同步關(guān)系分析對于“生產(chǎn)者”而言，緩沖區(qū)滿則應(yīng)等待引入同步信號量“empty”，為0表示緩沖區(qū)滿對于“消費者”而言，緩沖區(qū)空則應(yīng)等待引入同步信號量“full”，為0表示緩沖區(qū)空1/14/202532生產(chǎn)者－消費者信號量解法Producer進程intitem;While(TRUE){Produce-Item(&item);P(&empty);P(&mutex);Enter-item(item);V(&mutex);V(&full);}＃defineN100typedef

int

semphsemph

mutex=1;semphempty=N;semphfull=0;Comsumer進程intitem;While(TRUE){P(&full);P(&mutex);Remove-item(&item)V(&mutex);V(&empty);Consume-item(item);}思考1：mutex和empty兩個信號量之間有什么區(qū)別嗎？思考2：多信號量的操作順序有要求嗎？1/14/202533本講內(nèi)容上節(jié)回顧進程互斥進程同步進程間通信1/14/202534進程通信的基本概念進程間的信息交換稱為進程通信。進程間的通信分為兩種控制信息的傳送（低級通信）大量信息的傳送（高級通信）1/14/202535低級通信進程的互斥與同步為低級通信方式，相應(yīng)地，也稱wait、signal操作為低級的通信原語。1/14/202536高級通信進程間有時需要傳遞大量信息來同步相互之間的動作，而不是通過幾個共享變量因此，除了基本的同步與互斥之外，為了滿足進程間的高級通信需求，OS需要提供更為豐富的進程間通信方式1/14/202537進程間通信的方式主從式會話式消息或郵箱機制共享存儲區(qū)方式1/14/202538主從式通信的特點主進程可以自由的使用從進程的資源或者數(shù)據(jù)；從進程的動作受到主進程的控制；主進程和從進程的關(guān)系是固定的。例子：終端控制進程和終端進程1/14/202539會話式會話方式中，通信進程雙方可分別稱為使用進程和服務(wù)進程，其中使用進程調(diào)用服務(wù)進程提供的服務(wù)。

使用進程在調(diào)用服務(wù)前必須得到服務(wù)進程許可；

服務(wù)進程根據(jù)使用進程需求提供服務(wù)，但對服務(wù)的控制由自身完成；

使用進程和服務(wù)進程在通信時有固定連接關(guān)系。例子：用戶進程和磁盤管理進程之間的通信。1/14/202540消息或郵箱機制無論接收進程是否準備好接收信息，發(fā)送進程都將信息送入緩沖區(qū)或者信箱。特點：只要存在空緩沖區(qū)或者郵箱，發(fā)送進程則發(fā)送信息；發(fā)送進程和接收進程之間沒有直接連接關(guān)系；發(fā)送進程和接收進程之間存在緩沖區(qū)或郵箱存放被傳送的信息。1/14/202541消息緩沖機制兩通信進程之間的關(guān)系:在發(fā)送進程把消息寫入緩沖區(qū)和把緩沖區(qū)掛入消息隊列時，應(yīng)禁止其他進程對該消息緩沖區(qū)隊列的訪問。否則，將引起消息隊列的混亂。同理，當接收進程正從消息隊列中取消息緩沖區(qū)消息時，也應(yīng)禁止其他進程對該隊列的訪問。間接制約設(shè)置公用信號量:mutex

，其初值為1。當消息緩沖區(qū)隊列中無消息存在時，接收進程不能接收到任何消息。直接制約設(shè)置私用信號量:SM為接收進程的私用信號量，表示等待接收的消息個數(shù)，其初值為0。1/14/202542消息緩沖機制進程之間通信的實現(xiàn):向系統(tǒng)申請一個消息緩沖區(qū)將發(fā)送區(qū)消息m送入新申請的消息緩沖區(qū)把消息緩沖區(qū)掛入接收進程的消息隊列摘下消息隊列中的消息n

將消息n從緩沖區(qū)復(fù)制到接收區(qū)釋放緩沖區(qū)開始結(jié)束開始結(jié)束臨界區(qū)P(mutex)V(mutex)臨界區(qū)P(mutex)V(mutex)P(SM)V(SM)Send(m):Receive(n):1/14/202543郵箱通信郵箱通信的基本思想:郵箱通信是由發(fā)送進程申請建立一個與接收進程連接的郵箱,發(fā)送進程把消息送往郵箱,接收進程從郵箱取走消息,從而完成進程間信息交換。郵箱由郵箱頭和郵箱體組成。其中郵箱頭描述郵箱名稱、郵箱大小、郵箱方向以及擁有該郵箱的進程名等。郵箱體主要用來存放消息（如圖）。設(shè)置郵箱的最大好處就是發(fā)送進程和接收進程之間沒有處理時間上的限制。1/14/