操作系統(tǒng) 習題及答案 第八章 進程同步機制與死鎖

第八章進程同步機制與死鎖習題1．何謂與時間有關的錯誤？舉例說明之。并發(fā)進程執(zhí)行時一定會產生與時間有關的錯誤嗎？為什么？在并發(fā)程序中共享了公共變量，使得程序的計算結果與并發(fā)程序執(zhí)行的速度有關。這種錯誤的結果又往往是與時間有關的，所以，把它稱為“與時間有關的錯誤”。也就是，程序的正確性和結果受到程序執(zhí)行的具體時序和時間點的影響，導致不同的執(zhí)行時機產生不同的結果。例如，兩個并發(fā)程序A和B共享一個公共變量n，程序A每執(zhí)行一次循環(huán)都要作n=n+1操作，程序B則在每一次循環(huán)中打印出n的值并將n重新置0。程序A和B的語句在時間上可任意穿插或交叉執(zhí)行，則程序A的①n=n+1操作可能在程序B的②print（n）和③n=0操作之前，也可能在它們之后或它們之間（即①出現(xiàn)在②之后，而在③之前），設在開始某個循環(huán)之前n的值為5，則對于上面三種情形，執(zhí)行完一個循環(huán)后，打印機印出的值分別為6、5和5，而執(zhí)行后的n值分別為0，1，0。這樣，相同的程序在可能的三種情況下，由于程序執(zhí)行的具體時序而產生了三組不同的結果。這就是與時間有關的錯誤。并發(fā)程序執(zhí)行時不一定會產生與時間有關的錯誤。并發(fā)執(zhí)行的程序有可能是無關進程，并且正確設計和實現(xiàn)的并發(fā)系統(tǒng)可以有效避免與時間有關的錯誤。2．什么是臨界區(qū)？若系統(tǒng)中某些資源一次只允許一個進程使用，則這類資源稱為臨界資源，在進程中訪問臨界資源的程序稱為臨界區(qū)。3．若用Ｐ、Ｖ操作管理某一組相關臨界區(qū)，其信號量Ｓ的值在[-1,1]之間變化，當S=-1，S=0，S=1時，它們各自的物理含義是什么？當S=-1時，表示當前有進程正在該臨界區(qū)執(zhí)行，另一個訪問相同臨界區(qū)的進程正在等待（等待隊列進程數(shù)目是1）。當S=0時，表示當前有一個進程正在該臨界區(qū)執(zhí)行，沒有進程等待訪問該臨界區(qū)。當S=1時，表示當前空閑資源數(shù)為1，可以允許進程進入該臨界區(qū)。4．兩個并發(fā)執(zhí)行的進程A和B的程序如下：進程AWhile（true）{N=N+5;};進程BWhile（true）{打印N的值;N=0;};其中，N為整數(shù)，初值為４。若進程A先執(zhí)行了三個循環(huán)后，進程A和進程B又并發(fā)執(zhí)行了一個循環(huán)，寫出可能出現(xiàn)的打印值。正確的打印值應該是多少？請用P、V操作進行管理，使進程A和B并發(fā)執(zhí)行時不會出現(xiàn)與時間有關的錯誤?？赡艿拇蛴≈禐?9、24.正確的打印值為24.P、V操作管理如下：初始時，設置兩個信號量：S1=1，S2=0。進程A：While（true）{P(S1);N=N+5;V(S2);};進程B：While（true）{P(S2);打印N的值;N=0;V(S1);};5．a，b兩點之間有一段單行車道，現(xiàn)在設計一個自動管理系統(tǒng)，管理規(guī)則如下：允許同方向的車同時駛入ab段，但另一方向的車必須在ab段外等待；當ab之間無車輛在行駛時，到達a點（或b點）的車輛可以進入ab段，但不能從a點和b點同時駛入；當某方向在ab段行駛的車輛駛出了ab段且暫無同方向車輛進入ab段時，應讓另一方向等待的車輛進入ab段行駛。請編寫程序，用P、V操作實現(xiàn)對ab段的正確管理以保證行駛安全。初始化全局變量Ca=0,Cb=0分別表示從ab路段上從a點駛入的車輛數(shù)和ab路段上從b點駛入的車輛數(shù)。初始化三個信號量Sa=1,Sb=1,Sr=1.其中Sa控制Ca的訪問，Sb控制Cb的訪問，Sr表示當前ab路段是否已有車輛的信號量。對于從a點駛入的車輛，運行以下程序：P(Sa);//請求訪問從a點駛入的車輛數(shù)if(Ca==0)P(Sr);//ab路段沒有從a點駛入的車輛，需要獲得駛入權限Ca=Ca+1;V(Sa);從a點駛向b點;P(Sa);//請求訪問從a點駛入的車輛數(shù)Ca=Ca-1;if(Ca==0)V(Sr);V(Sa);類似地，對于從b點駛入的車輛，運行以下程序：P(Sb);if(Cb==0)P(Sr);Cb=Cb+1;V(Sb);從b點駛向a點;P(Sb);Cb=Cb-1;if(Cb==0)V(Sr);V(Sb);6．有三個并發(fā)進程R、M、P，它們共享一個緩沖器B。進程R負責從輸入設備讀信息，每讀出一個記錄后把它存放在緩沖器B中，進程M在緩沖器B中加工進程R存入的記錄，進程P把加工后的記錄打印輸出。緩沖器B中每次只能存儲一個記錄，當記錄被加工輸出后，緩沖器B中又可存儲一個新記錄。請用P、V操作為同步機制寫出它們并發(fā)執(zhí)行時能正確工作的程序。初始化三個信號量empty=1,full=0,processed=0.其中empty表示B為空的信號量，full表示B為滿的信號量，processed表示B中元素為已處理的信號量。進程R：While(true){ P(empty);//申請讀入緩沖器 讀出記錄存放入緩沖器B; V(full);}進程M：While(true){ P(full);//申請加工緩沖器中的數(shù)據(jù)在緩沖器B中加工進程R存入的記錄; P(processed);}進程P:While(true){ P(processed);//申請獲取加工后的數(shù)據(jù) 把加工后的記錄打印輸出; V(empty);}7．在公共汽車上，司機和售票員的工作流程如下所示。為保證乘客的安全，司機和售票員應密切配合協(xié)調工作，請編寫程序，用P、V操作來實現(xiàn)司機與售票員之間的同步。司機售票員啟動車輛；關門；正常行駛；售票；到站停車；開門；初始化信號量S1=0,S2=0,其中S1表示司機對售票員行動的信號，S2表示售票員對司機行動的信號。司機：While(true){ P(S2);//等待售票員關門 啟動車輛; 正常行駛; 到站停車; V(S1);//提示售票員開門}售票員：While(true){ 關門; V(S2);//提示司機已關門 售票; P(S1);//等待司機到站停車 開門;}8．某銀行有人民幣儲蓄業(yè)務，由n個柜臺人員負責。每個顧客進入銀行后先取一個號，并且等著叫號。當一個柜臺人員空閑下來，就叫下一個號。試用P，V操作正確編寫柜臺人員和顧客進程的程序。初始化信號量fnumber=1，cnumber=1，customer=0, counter=n.其中fnumber控制取號機資源，cnumber控制叫號機，customer表示當前顧客量，counter表示空閑柜臺人員數(shù)。每個柜臺人員進程程序：While(true){ P(customer);//等待有顧客 P(cnumber);//申請叫號 叫號; V(cnumber); 為顧客辦理業(yè)務; V(counter);//提示柜臺空閑}每個顧客進程程序：P(fnumber);//申請取號取號;V(fnumber);V(customer);//提示有顧客P(counter);//等待空閑柜臺辦理業(yè)務;9．設有A、B、C三個進程共享一個存儲資源F。A對F只讀不寫，B對F只寫不讀，C對F先讀后寫。（當一個進程寫F時，其他進程既不能讀F，也不能寫F，但多個進程同時讀F是允許的）。試利用或P、V操作，寫出A、B、C三個進程的框圖，要求：①執(zhí)行正確；②正常運行時不產生死鎖；③使用F的并發(fā)度要高。使用兩個信號量來實現(xiàn)這個讀寫鎖：mutex和writelock。mutex用于讀者之間的互斥，保證對讀者計數(shù)器的訪問是互斥的；writelock用于寫操作的互斥。進程A讀F框圖：進程B寫F框圖：進程C框圖：先按照進程A再按照進程B10．設有兩個優(yōu)先級相同的進程P1和P2，如下所示。信號量S1和S2的初值均為０，試問P1、P2并發(fā)執(zhí)行后，x、y、z的值各是多少？進程P1：進程P2：y=1； x=1；y=y+2； x=x+1；V(S1)； P(S1)；z=y+1； x=x+y；P(S2)； V(S2)；y=z+y； z=x+z；有以下幾種情況：x=5,y=7,z=9或x=5,y=12,z=9或x=5,y=7,z=4.11．設緩沖區(qū)大小為n，指出以下生產者-消費者問題解法中的錯誤，并改正。Producer() //生產者進程{while(true){P(mutrx)；P(empty)；Buffer(in)=nextp；in=(in+1)%n；V(mutex)；}}Consumer() //消費者進程{while(true){P(mutex)；P(full)；nextc=buffer(out)；out=(out+1)%n；V(mutex)；消費產品nextc；}}Producer()//生產者進程{while(true){P(empty);//確保有空位P(mutex);//進入臨界區(qū)Buffer[in]=nextp;//生產產品in=(in+1)%n;//移動到下一個位置V(mutex);//離開臨界區(qū)V(full);//增加可消費產品的計數(shù)}}Consumer()//消費者進程{while(true){P(full);//確保有產品可消費P(mutex);//進入臨界區(qū)nextc=Buffer[out];//消費產品out=(out+1)%n;//移動到下一個位置V(mutex);//離開臨界區(qū)V(empty);//增加空位計數(shù)消費產品nextc;}}12．有一個閱覽室，讀者進入時必須先在一張登記表上進行登記，該表為每一座位列出一個表目，包括座位號、姓名，讀者離開時撤銷登記信息。閱覽室有100個座位。試用P、V操作描述這些進程間的同步關系。由于每個讀者都會進行一樣的操作：登記->進入->閱讀->撤銷登記->離開，所以建立一個讀者模型即可。臨界資源有：座位，登記表。讀者間有座位和登記表的互斥關系，所以設信號量empty表示空座位的數(shù)量，初始為100，mutex表示對登記表的互斥訪問，初始為1。Semaphoremutex=1,empty=100;Reader()：While(true){P(empty)//申請空座位P(mutex)//申請登記表//登記V(mutex)//釋放登記表//進入閱讀P(mutex)//申請登記表//撤銷登記V(mutex)//釋放登記表V(empty)//釋放座位}13．有兩個合作進程P1、P2，它們從一臺輸入/輸出設備讀入數(shù)據(jù)，P1進程讀入數(shù)據(jù)a，P2進程讀入數(shù)據(jù)b，輸入設備是一臺獨占設備。兩個進程做如下計算：P1：x=a+b；P2：y=a-b；計算完成后結果x、y由進程P1輸出。用信號量實現(xiàn)進程P1、P2的同步算法。semaphoreS1=1，S2=0；semaphoreSb=0，Sy=0；P1(){ P(S1); 從輸入設備輸入數(shù)據(jù)a; V(S2); P(Sb); x=a+b; P(Sy); 使用打印機打印出x,y的結果;}P2(){ P(S2); 從輸入設備輸入數(shù)據(jù)b; V(Sb); y=a+b; V(Sy);}14．考慮交通死鎖情況，說明其產生死鎖的四個必要條件；給出一種可以避免死鎖發(fā)生的簡單方法。（1）該實例中死鎖的四個必要條件：四個交叉路口在同一個時間點只能通過一輛車（互斥）；車1占據(jù)路口一并等待車3通過路口三、車3占據(jù)路口三并等待車4通過路口四、車4占據(jù)路口四并等待車2通過路口二、車2占據(jù)路口二并等待車1通過路口一（即占有并等待）；當路口有車輛時其它車輛無法經過該路口（非搶占）；車1等待的路口三正在被車3占有、車3等待的路口四正在被車4占用、車4等待的路口二正在被車2占有、車2等待的路口一正在被車1占有（循環(huán)等待）（2）可以設置紅綠信號燈，前一分鐘可以讓橫向車通過，后一分鐘可以讓縱向車通過；每個一分鐘進行一次輪轉15．死鎖和“饑餓”有什么相同點和不同點？相同點：二者都是由于競爭資源而引起的，與資源的分配策略有關，因而防止餓死與死鎖可從公平性方面考慮如FCFS先到先服務算法。不同點：①從進程狀態(tài)考慮，死鎖進程都處于等待態(tài)（等待某一不可被剝奪資源被釋放）,餓死進程可能處于忙式等待(就緒隊列上等待可剝奪處理機資源)。（忙式等待：不進入等待狀態(tài)的等待實際狀態(tài)為”運行“或者”就緒“忙式等待空耗處理器資源因而是低效的,進程無法向前推進等待某一事件，但不主動放棄處理器而是不斷循環(huán)檢測資源是否可用）。②死鎖進程等待永遠不會被釋放的資源，餓死進程等待會被釋放但卻不會分配給自己的資源。③死鎖一定發(fā)生了循環(huán)等待，而餓死則不然，這也表明通過資源分配圖可以檢測死鎖存在與否，但不能檢測是否有進程餓死。④死鎖一定涉及多個進程，而饑餓或被餓死的進程可能只有一個。16．試敘述死鎖產生的原因、必要條件和解決死鎖的方法。原因1.競爭不可搶占性資源線程A已經獲得資源1，還想去獲得資源2，進程B已經獲得資源2，想去獲得資源1，但是1和2都是不可搶占的，發(fā)生死鎖2.競爭可消耗資源引起死鎖進程間通信，如果順序不當，會產生死鎖，比如線程A發(fā)消息m1給線程B，接收線程C的消息m3，線程B接收線程A的m1，發(fā)m2給線程C，以此類推，如果進程之間是先發(fā)信息的那么可以完成通信，但是如果是先發(fā)信息就會產生死鎖3.進程推進順序不當進程在運行過程中，請求和釋放資源的順序不當，也同樣會導致產生進程死鎖必要條件1.互斥條件：線程對資源的占有是排他性的，一個資源只能被一個線程占有，直到釋放2.請求和保持條件：一個線程對請求被占有資源發(fā)生阻塞時，對已經獲得的資源不釋放3.不可剝奪：一個線程在釋放資源之前，其他的線程無法剝奪占用4.循環(huán)等待：若干個執(zhí)行流請求資源的情況形成了一個閉環(huán)，發(fā)生死鎖時，線程進入死循環(huán)，永久阻塞解決方法給死鎖線程分配足夠多的資源終止系統(tǒng)中的一個或多個死鎖進程，直至打破循環(huán)環(huán)路，使系統(tǒng)從死鎖狀態(tài)解脫出來17．試舉出日常生活中死鎖的例子，并說明之。14題的交通死鎖的例子18．有3個進程共享4個資源，進程對資源的分配與釋放只能一次一個，每個進程最多需要2個資源。試問該系統(tǒng)會發(fā)生死鎖嗎？該系統(tǒng)不會發(fā)生死鎖因為最壞的情況是每個進程都占有一個資源，申請第二個資源，而此時系統(tǒng)中剩下一個資源，不管哪個進程得到該資源，都能滿足資源的需求，因此他能在有限的時間內從而釋放他占有的兩個資源，這兩個資源又可以分配給另外兩個進程，使他們運行結束，所以該系統(tǒng)不會發(fā)生死鎖。19．假設系統(tǒng)中有6個資源r1，r2，r3，r4，r5和r6，有3個進程P1，P2和P3，其活動分別為：P1： P2： P3：申請r1； 申請r2； 申請r3；申請r2； 申請r3； 申請r4；釋放r1； 釋放r2； 釋放r3；釋放r2； 釋放r3； 釋放r4；申請r5； 申請r4； 申請r6；申請r6； 申請r1； 申請r5；釋放r5； 釋放r4； 釋放r6；釋放r6； 釋放r1； 釋放r5；請分析當三個進程并發(fā)執(zhí)行時，是否會發(fā)生死鎖現(xiàn)象，請給出原因?？赡軙l(fā)生死鎖現(xiàn)象，當執(zhí)行順序出現(xiàn)：P1申請r5；P3申請r6；P1申請r6；P3申請r5；時出現(xiàn)循環(huán)等待，發(fā)生死鎖現(xiàn)象。20．考慮這樣一種資源分配策略：對資源的申請和釋放可以在任何時刻進行。如果一個進程的資源得不到滿足，則考查所有由于等待資源而被阻塞的進程，如果它們有申請進程所需要的資源，則把這些資源取出分給申請進程。 例如，考慮一個有三類資源的系統(tǒng)，Available=（4，2，2）。進程A申請（2，2，1），可以滿足；進程B申請（1，0，1），可以滿足；若A再申請（0，0，1），則被阻塞（無資源可分）。此時，若C申請（2，0，0），它可以分得剩余資源（1，0，0），并從A已分得的資源中獲得一個資源，于是，進程A的分配向量變成：Available=（1，2，1），而需求向量變成：Need=（1，0，1）。（1）這種分配方式會導致死鎖嗎？若會，舉一個例子；若不會，說明死鎖的哪一個必要條件不成立。（2）會導致某些進程的無限等待嗎？（1）不會導致死鎖，死鎖的“不可剝奪條件”被破壞（2）可能導致進程的無限等待。如果一個進程反復地因為其他進程的需求而被剝奪資源，而它的資源需求始終得不到完全滿足，那么會陷入一種被持續(xù)阻塞的狀態(tài)。21．假定一個系統(tǒng)有四種資源，R={6，4，4，2}，當前系統(tǒng)狀態(tài)如下圖所示。該狀態(tài)安全嗎？請闡述理由。資源申請進程目前占有量最大需求量尚需要量ABCDABCDP120113211P211001202P311001120P410103210P501012101系統(tǒng)剩余資源量ABCD圖8-18題21圖進程資源申請目前占有量最大需求量尚需求量ABCDABCDABCDP1201132111200P2110012020102P3110011200020P4101032102200P5010121012000系統(tǒng)剩余資源1120答：系統(tǒng)剩余資源1120能滿足進程P3的需求，故分配給P3后P3釋放資源，系統(tǒng)剩余資源分別為2220，可滿足P1，分配給P1后P1釋放資源，系統(tǒng)剩余資源分別為4232，依次類推可滿足所有進程需求，所以該狀態(tài)是安全狀態(tài)。22．一個計算機系統(tǒng)有某種資源6個，供n個進程使用，每個進程至少需要2個資源。當n為何值時，系統(tǒng)不會發(fā)生死鎖？有m個資源，每個進程最多需要x個資源，則最多允許幾個進程參與競爭，確保不會發(fā)生死鎖？進程數(shù)使用n表示當n(x-1)+1<=m時，此時不會發(fā)生死鎖n<=(m-1)/(x-1)=5/1=523．設系統(tǒng)有三種類型的資源，數(shù)量為（4，2，2）。系統(tǒng)中有進程P1、P2、P3按如下順序請求資源；進程P1申請（2，2，1）

進程P2申請（1，0，1）

進程P1申請（0，0，1）

進程P3申請（2，0，0）該系統(tǒng)按照死鎖預防中破壞“不可剝奪”條件的方案二，對上述申請序列，給出資源分配過程。指出哪些進程需要等待資源，哪些資源被剝奪。進程可能進入無限等待狀態(tài)嗎？進程P1申請（2，2，1），剩余（2，0，1）進程P2申請（1，0，1），剩余（1，0，0）進程P1申請（0，0，1），剝奪P2的第三種資源，之后還給P2最后進程P3申請24．在實際的計算機系統(tǒng)中，資源數(shù)和進程數(shù)是動態(tài)變化的。當系統(tǒng)處于安全狀態(tài)時，如下變化是否可能使系統(tǒng)進入非安全狀態(tài)？（1）增加Available （2）減少Available （3）增加Max（4）減少Max （5）增加進程數(shù) （6）減少進程數(shù)（2）（3）（5）25．假設一條河上有一座由若干個橋墩組成的橋，若一個橋墩一次只能站一個人，想要過河的人總是沿著自己過河的方向前進而不后退，且沒有規(guī)定河兩岸的人應該誰先過河。顯然，如果有兩個人P1和P2同時從兩岸沿此橋過河，就會發(fā)生死鎖。請給出解決死鎖的各種可能的方法，并闡述理由。題意分析需要保證：同一時刻兩個方向只能有一個方向的人再前進。只要方向1上還有人未通過，則方向2的人就不能上橋。同一個方向上能有多個人等待過橋，但是每次只能過一個人，其他人可以排隊。方向2的人想上橋通過，必須等方向1的全部人都通過才可以。反之也成立。通過上述分析我們不難發(fā)現(xiàn)，過橋問題實際就是讀者寫者的讀者優(yōu)先算法的一個變形。只能有一個方向的人過橋，等價于讀者與寫者只能有一種人在工作。通過互斥信號量解決二者之間的互斥關系。過橋問題通過mutex來實現(xiàn)兩個方向上的互斥，mutex設置為1，表示將方向鎖定。任意一個方向都有可能有很多人，所以設置count1/2變量來對每個方向上的人進行計數(shù)，只有第一個上橋的人才需要對方向上鎖，最后一個離開橋的人對方向解鎖。類比讀者寫者問題，只有第一個讀者才需要對讀寫進程進行加鎖，只有最后一個讀者才對讀寫進程進行解鎖。都是通過count變量來實現(xiàn)。依據(jù)雙標志先檢查法的不足，如果檢查和上鎖不是一氣呵成的，則可能會違法忙則等待，同一時刻有多個進程進入臨界區(qū)。因此必須設置一個互斥信號量來保證對檢查和上鎖一氣呵成，因此出現(xiàn)了Scount1/2信號量，保證對對應的count變量的檢查和上鎖是一氣呵成的。由于有n個橋墩，每個人只能站一個，因此最多允許一個方向上的N個人申請，所以共享變量Scount=N。此處不再區(qū)分到底是哪個方向優(yōu)先問題，兩個方向的優(yōu)先級是通過哪一個先搶占處理機來決定的，并非人為決定。Semaphoremutex=1,//對方向鎖定的互斥信號量scount1=1,//確保方向1對count1的檢查和上鎖是原子操作scount2=1,//確保方向2對count2的檢查和上鎖是原子操作scount=N;//一共有多少個橋墩intcount1=0,//1方向上有多少人count2=0;//2方向上有多少人//方向1voiddirect1(inti){wait(scount1);if(count1==0)wait(mutex);count1++;signal(scount1);wait(scount);上橋，過橋，下橋；signal(scount);wait(scount1);count1--;if(count1==0)signal(mutex);signal(scount1);}//方向2voiddirect2(inti){wait(scount2);if(count2==0)wait(mutex);count2++;signal(scount2);wait(scount);上橋，過橋，下橋；signal(scount);wait(scount2);count2--;if(count2==0)signal(mutex);signal(scount2);}//main執(zhí)行main(){cobegin{direct1(1);…direct1(n);direct2(1);…direct2(m);}}26．有3個進程P1，P2，和P3并發(fā)執(zhí)行，進程P1需使用資源r3和r1，進程P2需使用資源r1和r2，進程P3需使用資源r2和r1。（1）若對資源分配不加限制，會發(fā)生什么情況，為什么？（2）為保證進程能執(zhí)行到結束，應采用怎樣的資源分配策略？（1）可能會發(fā)生死鎖。例如：P1持有r3并等待r1，P2持有r1并等待r2，P3持有r2并等待r1，此時產生循環(huán)等待現(xiàn)象。（2）靜態(tài)分配資源、按序申請資源或采用銀行家算法進行資源分配。27．某系統(tǒng)當前有同類資源10個，進程P，Q，R所需資源總數(shù)分別為8，4，9。它們向系統(tǒng)申請資源的次序和數(shù)量如下圖所示。（1）系統(tǒng)采用銀行家算法分配資源，請給出系統(tǒng)完成第6次分配后各進程的狀態(tài)及所占資源量。（2）在以后各次的申請中，哪次的申請要求可先得到滿足？次序進程申請量次序進程申請量1R26Q22P47R33Q28P24P29R35R1圖8-19題27圖（1）初始狀態(tài)：maxallocationneedavailableP80810Q404R9091:R申請2個，可以滿足maxallocationneedavailableP8088Q404R9272:P申請4個，可以滿足maxallocationneedavailableP8444Q404R9273:Q申請2個，可以滿足maxallocationneedavailableP8442Q422R9274:P申請2個，若分配，會得到以下狀態(tài)，無法找到