第4章習(xí)題及答案

PAGEPAGE12第四章習(xí)題及解答4-3什么是進(jìn)程？進(jìn)程與程序的主要區(qū)別是什么？答：進(jìn)程是一個具有一定獨(dú)立功能的程序關(guān)于某個數(shù)據(jù)集合的一次活動。進(jìn)程與程序的主要區(qū)別是：(1)程序是指令的有序集合，是一個靜態(tài)概念。進(jìn)程是程序在處理機(jī)的一次執(zhí)行過程，是一個動態(tài)概念。進(jìn)程是有生命期的，因創(chuàng)建而產(chǎn)生，因調(diào)度而執(zhí)行，因得到資源而暫停，因撤消而消亡；(2)進(jìn)程是一個獨(dú)立的運(yùn)行單元，是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單元，而程序則不是。(3)進(jìn)程與程序之間無一一對應(yīng)關(guān)系。一個程序可以對應(yīng)多個進(jìn)程，一個進(jìn)程至少包含一個程序。4-4圖4.2標(biāo)明程序段執(zhí)行的先后次序。其中：I表示輸入操作，C表示計算操作，P表示打印操作，下角標(biāo)說明是對哪個程序進(jìn)行上述操作。請指明：哪些操作必須有先后次序?其原因是什么？哪些操作可以并發(fā)執(zhí)行?其原因又是什么？答：(1)① In、Cn和Pn之間有先后順序要求，這是由于程序本身的邏輯要求。②使用同一設(shè)備的不同的程序段，如C1…Cn，I1…In，P1…Pn，之間有先后順序要求，這是由于設(shè)備某一時刻只能為一個程序服務(wù)。(2)不同程序使用不同設(shè)備時，占用不同設(shè)備，無邏輯關(guān)系，可以并發(fā)執(zhí)行，如I2和C1；I3、C2和P1。運(yùn)行就緒等待41運(yùn)行就緒等待4123(1)什么原因會導(dǎo)致發(fā)生變遷2、變遷3、變遷4？答：發(fā)生變遷2的原因：時間片到發(fā)生變遷3的原因：請求I/O或其他系統(tǒng)調(diào)用發(fā)生變遷4的原因：I/O完成或其他系統(tǒng)調(diào)用完成(2)在什么情況下，一個進(jìn)程的變遷3能立即引起另一個進(jìn)程發(fā)生變遷1？答：一個進(jìn)程的變遷3能立即引起另一個進(jìn)程發(fā)生變遷的條件是，就緒隊列非空。(3)下列因果變遷是否可能發(fā)生？若可能，需要什么條件？a.2→1；b.3→2；c.4→1答：a.2→1不需要條件，一定會發(fā)生。b.3→2不可能發(fā)生。c.4→1可能發(fā)生，條件：就緒隊列為空，或在可剝奪調(diào)度方式下，轉(zhuǎn)變?yōu)榫途w狀態(tài)的進(jìn)程優(yōu)先級最高。4-10某系統(tǒng)jincheng狀態(tài)除了3個最基本狀態(tài)外，又增加了創(chuàng)建狀態(tài)、完成狀態(tài)、因等消息而轉(zhuǎn)變?yōu)榈却隣顟B(tài)3種新的狀態(tài)，試畫出增加新狀態(tài)后的進(jìn)程狀態(tài)變遷圖，并說明發(fā)生每一個變遷的原因。運(yùn)行運(yùn)行等待就緒創(chuàng)建等消息完成進(jìn)程狀態(tài)變遷原因：運(yùn)行—>等待：請求I/O；等待—>就緒：請求完成；運(yùn)行—>就緒：時間片到；就緒—>運(yùn)行：CPU空閑，進(jìn)程調(diào)度程序工作；創(chuàng)建—>就緒：進(jìn)程創(chuàng)建；運(yùn)行—>等消息：等待消息；等消息—>就緒：收到消息；運(yùn)行—>完成：任務(wù)完成4-12n個并發(fā)進(jìn)程共用一個公共變量Q，寫出用信號燈實現(xiàn)n個進(jìn)程互斥時的程序描述，給出信號燈值的取值范圍,并說明每個取值的物理意義。解：(1)程序描述main(){intmutex=1;//公共變量Q的互斥信號燈cobegin P1; P2; … Pn;coend}Pi(){ … P(mutex); 使用Q； V(mutex); …}(2)信號燈值的取值范圍：[(n–1)，1](3)mutex每個取值的物理意義：mutex=1說明沒有進(jìn)程進(jìn)入臨界段執(zhí)行；mutex=0說明有一個進(jìn)程進(jìn)入臨界段執(zhí)行；mutex=1說明有一個進(jìn)程進(jìn)入臨界段執(zhí)行，另有一個進(jìn)程正在等待進(jìn)入；mutex=(n–1)說明有一個進(jìn)程進(jìn)入臨界段執(zhí)行，另有(n–1)個進(jìn)程正在等待進(jìn)入。4-P2sP3P4sP1P2P2sP3P4sP1P2P3ffP1(a)(b)圖4.32圖(a)解：main(){ints12=0,s13=0,s14=0;//s12表示進(jìn)程P2可否執(zhí)行；s13表示進(jìn)程P3可否執(zhí)行；s14表示進(jìn)程P4可否執(zhí)行//cobeginP1;P2;P3;P4;coend}P1(){p1execute;V(s12);V(s13);V(s14);}P2(){P(s12);p2execute;}P3(){P(s13);p3execute;}P4(){P(s14);p4execute;}圖(b)main(){ints13=0,s23=0;//s13表示進(jìn)程P1執(zhí)行完成否；s23表示進(jìn)程P2執(zhí)行完成否//cobeginP1;P2;P3;coend}P1(){P1execute;V(s13);}P2(){P2execute;V(s23);}P3(){P(s13);P(s23);P3execute;}4-15如圖4.34所示，get、copy和put三個進(jìn)程共用兩個緩沖區(qū)s和t(其大小每次存放一個記錄)，get進(jìn)程負(fù)責(zé)不斷地把輸入記錄輸入緩沖區(qū)s中，copy進(jìn)程負(fù)責(zé)從緩沖區(qū)s中取出記錄復(fù)制到緩沖區(qū)t中，而put進(jìn)程負(fù)責(zé)從緩沖區(qū)t中取出記錄打印。試用PV操作實現(xiàn)這三個進(jìn)程之間的同步，并寫出程序描述。putput緩沖區(qū)s緩沖區(qū)tgetcopy圖4.34解：main(){ints1=1,s2=0;//s1表示緩沖區(qū)S是否為空，s2表示是否已滿//ints3=1,s4=0;//s3表示緩沖區(qū)T是否為空，s4表示是否已滿//cobeginget;copy;put;coend}get(){while(1){P(s1);inputdatatobufferS;V(s2);}}copy(){while(1){P(s2);copydatafrombufferS;V(s1);P(s3);inputcopy-datatobufferT;V(s4);}}put(){while(1){P(s4);outputdatatobufferS;V(s3);}}4-16什么是進(jìn)程的互斥與同步？同步和互斥這兩個概念有什么聯(lián)系和區(qū)別？答：在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問某一存儲區(qū)域時，就不允許其他進(jìn)程讀出或者修改該存儲區(qū)的內(nèi)容，否則，就會發(fā)生后果無法估計的錯誤。進(jìn)程之間的這種相互制約關(guān)系稱為互斥。所謂同步，就是并發(fā)進(jìn)程在一些關(guān)鍵點上可能需要互相等待與互通消息，這種相互制約的等待與互通信息稱為進(jìn)程同步。同步和互斥這兩個概念都屬于同步范疇，描述并發(fā)進(jìn)程相互之間的制約關(guān)系。同步是指并發(fā)進(jìn)程按照他們之間的約束關(guān)系，在執(zhí)行的先后次序上必須滿足這種約束關(guān)系。而互斥是同步的一種特例，是指并發(fā)進(jìn)程按照他們之間的約束關(guān)系，在某一點上一個時刻只允許一個進(jìn)程執(zhí)行，一個進(jìn)程做完了，另一個進(jìn)程才能執(zhí)行，而不管誰先做這個操作。4-22什么是線程？線程和進(jìn)程有什么區(qū)別?答：線程也稱為輕量級進(jìn)程，它是比進(jìn)程更小的活動單位，它是進(jìn)程中的一個執(zhí)行路徑，一個進(jìn)程可能有多個執(zhí)行路徑，即線程。線程和進(jìn)程的主要區(qū)別如下。(1)線程是進(jìn)程的一個組成部分，一個進(jìn)程可以有多個線程，而且至少有一個可執(zhí)行的線程。(2)進(jìn)程是資源分配的基本單位，它擁有自己的地址空間和各種資源；線程是處理機(jī)調(diào)度的基本單位，它只能和其他線程共享進(jìn)程的資源，而本身并沒有任何資源。(3)進(jìn)程的多個線程都在進(jìn)程的地址空間內(nèi)活動。這樣，在以線程為單位進(jìn)行處理機(jī)調(diào)度和切換時，切換時間較短；而以進(jìn)程為單位進(jìn)行處理機(jī)調(diào)度和切換時，由于涉及到資源轉(zhuǎn)移及現(xiàn)場保護(hù)等問題，將導(dǎo)致切換時間變長和資源利用率下降。(4)線程和進(jìn)程一樣，都有自己的狀態(tài)和相應(yīng)的同步機(jī)制，但是，由于線程沒有自己單獨(dú)的程序和數(shù)據(jù)空間，因而不能像進(jìn)程那樣將程序和數(shù)據(jù)交換到外存去。(5)進(jìn)程的調(diào)度和控制大多由操作系統(tǒng)的內(nèi)核完成，而線程的控制既可以由操作系統(tǒng)內(nèi)核完成，也可以由用戶控制完成。4-27試畫出Linux系統(tǒng)的進(jìn)程狀態(tài)變遷，并說明這些變遷可能的原因。服務(wù)請求(如：請求I/O服務(wù)請求(如：請求I/O等)進(jìn)程調(diào)度服務(wù)完成/事件來到運(yùn)行TASK_RUNNING就緒TASK_RUNNING被搶占等待TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE創(chuàng)建TASK_RUNNING進(jìn)程創(chuàng)建終止TASK_ZOMBIE進(jìn)程終止(1)進(jìn)程創(chuàng)建當(dāng)系統(tǒng)或用戶需要創(chuàng)建一個新進(jìn)程時，調(diào)用fork()系統(tǒng)調(diào)用，被創(chuàng)建的新進(jìn)程被置為就緒狀態(tài)TASK_RUNNING。(2)進(jìn)程調(diào)度當(dāng)調(diào)度時機(jī)來到時，進(jìn)程調(diào)度程序從進(jìn)程運(yùn)行隊列中選擇優(yōu)先級最高的進(jìn)程，將其投入運(yùn)行，設(shè)置狀態(tài)為運(yùn)行狀態(tài)。(3)被搶占正在CPU上運(yùn)行的進(jìn)程，當(dāng)其優(yōu)先級低于處于就緒狀態(tài)的某一個進(jìn)程的優(yōu)先級時，它被搶占而被迫讓出CPU的控制權(quán)，此時，該進(jìn)程的狀態(tài)轉(zhuǎn)為就緒狀態(tài)。(4)進(jìn)程等待若正在運(yùn)行的進(jìn)程因等待某一事件而暫時不能運(yùn)行下去時，進(jìn)入相應(yīng)的等待隊列，設(shè)置為等待狀態(tài)。(5)進(jìn)程喚醒當(dāng)某個進(jìn)程等待的原因撤銷時，該進(jìn)程被喚醒，將其從等待隊列中移出，進(jìn)入就緒隊列。(6)進(jìn)程終止當(dāng)正在運(yùn)行的進(jìn)程完成其任務(wù)時，通過exit()系統(tǒng)調(diào)用終止自己而進(jìn)入終止?fàn)顟B(tài)。4-29某公園有一個長凳，其上最多可以坐5個人。公園里的游客遵循以下規(guī)則使用長凳：(1)如果長凳還有空間可以坐，就坐到長凳上休息，直到休息結(jié)束，離開長凳。(2)如果長凳上沒有空間，就轉(zhuǎn)身離開。試用信號燈的P、V操作描述這一場景。答：main(){intcount=5;//長凳上可坐的人數(shù)intmutex=0;//訪問count的互斥信號燈cobeginguesti; //i=1,2,3,4……coend}guesti{ P(mutex); if(count==0){ V(mutex); return; } count--; V(mutex); 休息； P(mutex); Count++; V(mutex);}4-316個進(jìn)程合作完成一項計算任務(wù)的并發(fā)描述如圖4-38所示，程序中，s1、s2、s3、s4、s5、s6分別是同步信號燈，x、y、z是共享數(shù)據(jù)變量。試給出變量z的最終結(jié)果，并畫出6個進(jìn)程合作的進(jìn)程流圖。ints1=s2=s3=0;ints1=s2=s3=0;ints4=s5=0;intx=y=z=0;main(){CobeginP1();P2();P3();P4();P5();P6();Coend}P3(){P(s1);y=y*2;P3(){P(s1);y=y*2;V(s3);V(s3);}P2(){P(s1);x=x+2;z=x;V(s2);V(s2);}P1(){x=1;y=1;V(s1);V(s1);}P6(){P(s5);P(s4);P6(){P(s5);P(s4);z=x+y+z;}}P5(){P(s2);P(s3);z=z+y;V(s5);}P4(){P(s2);P(s3);x=x+y;V(s４);}答：Z=124-32現(xiàn)有3個并發(fā)進(jìn)程P1、P2和P3，如圖4.39所示。3個并發(fā)進(jìn)程共享兩個單緩沖區(qū)B1和B2。進(jìn)程P1負(fù)責(zé)不斷從輸入設(shè)備讀數(shù)據(jù)，若讀入的數(shù)據(jù)為正數(shù)，則直接送入B2，否則應(yīng)先將數(shù)據(jù)送入B1，經(jīng)P2取出加工后再送入B2，P3從B2中取信息輸出。請使用信號燈和P、V操作描述進(jìn)程P1、P2、P3實現(xiàn)同步的算法。答：緩沖區(qū)B1設(shè)置信號燈s1、t1，s1表示緩沖區(qū)B1是否空閑，t1表示緩沖區(qū)B1是否有數(shù)據(jù)，緩沖區(qū)B2設(shè)置信號燈s2、t2，s2表示緩沖區(qū)B2是否空閑，t2表示緩沖區(qū)B2是否有數(shù)據(jù)。P2(){While(未結(jié)束){P2(){While(未結(jié)束){P(t1);取B1數(shù)據(jù)；V(s1);P(s2);數(shù)據(jù)放入B2;V(t2);}P1(){While(未結(jié)束）讀取數(shù)據(jù)；If(數(shù)據(jù)>0){P(s2);數(shù)據(jù)放入B2;V(t2);}else{P(s1);數(shù)據(jù)放入B1;V(t1);}P3(){P3(){While(未結(jié)束){P(t2);取B2數(shù)據(jù)；V(s2);輸出數(shù)據(jù)；}Ints1=s2=1;Intt1=t2=0;CobeginP1();p2();p3();Coend}4-34某商場有一個地下停車場，有N個停車位，車輛只能通過一個指定的通道進(jìn)出停車場，通道處只能容一輛車通過，請設(shè)計信號燈和P、V操作給出進(jìn)、出車輛兩種進(jìn)程的程序描述。答：main(){intcount1=count2=0;/*計數(shù)器*/ intmutex1=mutex2=1;/*兩個計數(shù)器的互斥訪問信號燈*/intmutex=1;/*通道互斥訪問信號燈*/ cobeginin();out();coend }in(){P(empty); P(mutex1);C