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

進(jìn)程P2申請（1，0，1）

進(jìn)程P1申請（0，0，1）

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