第2章-處理器管理-習(xí)題答案

第2章處理器管理習(xí)題1.1選擇題1、 下列選項中，不屬于進程關(guān)鍵要素的是（D）。A．程序 B．?dāng)?shù)據(jù)和棧C．進程控制塊 D．原語2、操作系統(tǒng)管理程序運行的狀態(tài)，具備較高的特權(quán)級別，稱為（C）。A．用戶態(tài) B．目態(tài) C．管態(tài) D．普通態(tài)3、在操作系統(tǒng)中，PSW的中文全稱是（A）。A．程序狀態(tài)字B．進程標(biāo)識符 C．作業(yè)控制塊 D．進程控制塊4、當(dāng)系統(tǒng)中或系統(tǒng)外發(fā)生異步事件時，CPU暫停正在執(zhí)行的程序，保留現(xiàn)場后轉(zhuǎn)去執(zhí)行相應(yīng)事件的處理程序，處理完成后返回斷點，繼續(xù)執(zhí)行被打斷的進程，這一過程稱為（D）。A．作業(yè)調(diào)度 B．頁面置換 C．磁盤調(diào)度 D．中斷5、以下關(guān)于進程的說法，錯誤的是（B）。A．進程是程序在處理器上的一次執(zhí)行過程B．一個進程是由若干作業(yè)組成的C．在線程出現(xiàn)后，進程仍然是操作系統(tǒng)中資源分配的基本單位D．進程具有創(chuàng)建其他進程的功能6、在下述關(guān)于父進程和子進程的敘述中，正確的是（D）。A．父進程創(chuàng)建了子進程，因此父進程執(zhí)行完了，子進程才能運行B．子進程執(zhí)行完了，父進程才能運行C．撤消子進程時，應(yīng)該同時撤消父進程D．一個子進程只有一個父進程，但一個父進程可以有多個子進程7、任何兩個并發(fā)進程之間（D）。A．一定存在互斥關(guān)系B．一定存在同步關(guān)系C．一定彼此獨立無關(guān)D．可能存在同步或互斥關(guān)系8、調(diào)度程序每次把CPU分配給就緒隊列首進程使用一個時間片，就緒隊列中的每個進程輪流地運行一個時間片。當(dāng)這個時間片結(jié)束時，強迫一個進程讓出處理器，讓它排列到就緒隊列的尾部，等候下一輪調(diào)度。這種進程調(diào)度方式稱為（D）調(diào)度。A．最高響應(yīng)比優(yōu)先B．先來先服務(wù)C．短作業(yè)優(yōu)先D．時間片輪轉(zhuǎn)9、若當(dāng)前進程因時間片用完而讓出處理器時，該進程應(yīng)轉(zhuǎn)變?yōu)椋ˋ）狀態(tài)。A．就緒B．等待C．運行D．完成10、在一個單核單處理器的系統(tǒng)中，若有3個進程，且假定當(dāng)前時刻有一個進程處于運行態(tài)，則處于就緒態(tài)的進程最多有（B）個。A．1B．2C．3D．411、下列作業(yè)調(diào)度算法中，（D）與作業(yè)的運行時間和等待時間有關(guān)。A．先來先服務(wù)算法 B．短作業(yè)優(yōu)先算法C．均衡調(diào)度算法 D．最高響應(yīng)比調(diào)度算法12、一作業(yè)

8：00到達系統(tǒng)，估計運行時間為1小時，若9：00開始執(zhí)行該作業(yè)，其響應(yīng)比是（A）。A．2B．1C．3D．0.513、臨界區(qū)是指并發(fā)進程中訪問共享變量的（D）段。A．管理信息B．信息存儲C．?dāng)?shù)據(jù)D．程序14、設(shè)與某資源關(guān)聯(lián)的信號量初值為3，當(dāng)前值為-1。若M表示該資源的可用個數(shù)，N表示等待該資源的進程數(shù)，則M、N分別是（A）。A．0、1 B．1、0C．1、2 D．2、015、設(shè)某個信號量S的初值為5。若執(zhí)行某個V(S)時，發(fā)現(xiàn)（A）時，則喚醒相應(yīng)等待隊列中等待的一個進程。A．S的值小于或等于0 B．S的值大于或等于5C．S的值小于5D．S的值大于516、以下不屬于產(chǎn)生死鎖原因的是（B）。A．因為系統(tǒng)資源不足B．采用的進程調(diào)度算法效率低下C．進程運行推進的順序不合適D．資源分配不當(dāng)17、在多進程的并發(fā)系統(tǒng)中，不會因競爭（C）而產(chǎn)生死鎖。A．打印機 B．磁帶機 C．CPU D．磁盤18、當(dāng)每類資源只有一個資源實例時，下列說法中不正確的是（C）。A．有環(huán)必死鎖B．死鎖必有環(huán)C．有環(huán)不一定死鎖D．死鎖進程一定全在環(huán)中19、有關(guān)死鎖的論述中，（C）是正確的。A．系統(tǒng)中僅有一個進程進入了死鎖狀態(tài)B．多個進程由于競爭CPU而進入死鎖C．多個進程由于競爭互斥使用的資源又互不相讓而進入死鎖D．由于進程調(diào)用V操作而造成死鎖20、進程-資源分配圖是用于（D）。A．死鎖的預(yù)防 B．解決死鎖的靜態(tài)方法C．死鎖的避免 D．死鎖的檢測與解除1.2填空題1、Linux操作系統(tǒng)按照事件來源和實現(xiàn)手段將中斷分為（硬中斷）、（軟中斷）。2、系統(tǒng)調(diào)用是通過（中斷）來實現(xiàn)的；發(fā)生系統(tǒng)調(diào)用，處理器的狀態(tài)常從目態(tài)變?yōu)楣軕B(tài)。3、在Linux系統(tǒng)中，創(chuàng)建進程的原語是（fork）。4、進程的基本三狀態(tài)模型并不足夠描述進程的真實的情況，進程的五狀態(tài)模型增加了兩個狀態(tài)，包括（新建狀態(tài)）和（終止?fàn)顟B(tài)）。5、系統(tǒng)中進程存在的唯一標(biāo)志是（進程控制塊PCB）。6、進程上下文包括了進程本身和運行環(huán)境，是對進程執(zhí)行活動全過程的靜態(tài)描述。進程上下文分成三個部分：（用戶級上下文（進程的用戶地址空間內(nèi)容））、（寄存器級上下文（硬件寄存器內(nèi)容））和（系統(tǒng)級上下文（與該進程相關(guān)的核心數(shù)據(jù)結(jié)構(gòu)））。7、進程調(diào)度方式通常有（搶占）和（非搶占）兩種方式。8、若信號量S的初值定義為10，則對S調(diào)用執(zhí)行了16次P操作和15次V操作后，S的值應(yīng)該為（9）。1.3簡答題1、請簡單敘述進程三態(tài)模型中的進程狀態(tài)轉(zhuǎn)化情況。答：就緒態(tài)→運行態(tài)：當(dāng)調(diào)度程序選擇一個新的進程運行時，進程會由就緒態(tài)切換到運行態(tài)；運行態(tài)→就緒態(tài)：當(dāng)運行進程用完了獲得的時間片時，進程就會被中斷，由運行態(tài)切換到就緒態(tài)，或是因為一高優(yōu)先級進程處于就緒狀態(tài)，正在運行的低優(yōu)先級進程會被中斷而由運行態(tài)切換到就緒態(tài)；運行態(tài)→等待態(tài)：以下幾種情況會導(dǎo)致進程會由運行態(tài)切換到等待態(tài)，例如當(dāng)一進程必須等待時，或是操作系統(tǒng)尚未完成服務(wù)，進程對一資源的訪問尚不能進行時，還有初始化I/O且必須等待結(jié)果時，在進程間通信時，進程等待另一進程提供輸入時等；等待態(tài)→就緒態(tài)：當(dāng)進程所等待的事件發(fā)生時，例如資源申請獲得滿足時，或是等待的數(shù)據(jù)或信號到來時，進程就可能由等待態(tài)切換到就緒態(tài)。2、進程創(chuàng)建來源于以下事件：提交一個批處理作業(yè)；在終端上交互式的登錄；操作系統(tǒng)創(chuàng)建一個服務(wù)進程；進程孵化新進程；等等。請描述進程的創(chuàng)建過程。答：①系統(tǒng)在進程表中增加一項，并從PCB池中取一個空白PCB；②為新進程的進程映像分配地址空間。傳遞環(huán)境變量，構(gòu)造共享地址空間；③為新進程分配資源，除內(nèi)存空間外，還有其他各種資源；④查找輔存，找到進程正文段并裝到正文區(qū)；⑤初始化進程控制塊，為新進程分配進程標(biāo)識符，初始化PSW；⑥加入就緒進程隊列，將進程投入運行；⑦通知操作系統(tǒng)的某些模塊，如記賬程序、性能監(jiān)控程序。3、請簡述時間片輪轉(zhuǎn)調(diào)度算法的工作流程和確定時間片大小需要考慮的因素。答：1、時間片輪轉(zhuǎn)調(diào)度算法的工作流程：系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則排成一個隊列，每次調(diào)度時把CPU分配給隊首進程，并令其執(zhí)行一個時間片。當(dāng)執(zhí)行的時間片用完時，由系統(tǒng)中的定時器發(fā)出時鐘中斷請求，調(diào)度程序停止該進程的執(zhí)行，并將它送到就緒隊列的末尾，等待下一次執(zhí)行。進行進程切換，把處理器分配給就緒隊列中新的隊首進程。2、時間片大小的確定要從進程個數(shù)、切換開銷、系統(tǒng)效率和響應(yīng)時間等方面考慮：時間片取值太小，多數(shù)進程不能在一個時間片內(nèi)運行完畢，切換就會頻繁，開銷顯著增大，從系統(tǒng)效率來看，時間片取大一點好。時間片取值太大，隨著就緒隊列里進程數(shù)目增加，輪轉(zhuǎn)一次的總時間增大，對進程的響應(yīng)速度放慢了。為滿足響應(yīng)時間要求，要么限制就緒隊列中進程數(shù)量，要么采用動態(tài)時間片法，根據(jù)負(fù)載狀況及時調(diào)整時間片的大小。4、有兩個優(yōu)先級相同的并發(fā)運行的進程P1和P2，各自執(zhí)行的操作如下，信號量S1和S2初值均為0，x、y和z的初值為0。CobeginP1：beginy:=0;y:=y+4;V(S1);z:=y+3;P(S2);y:=z+yendP2：beginx:=2;x:=x+6;P(S1);x:=x+y;V(S2);z:=z+x;endCoend試問P1、P2并發(fā)執(zhí)行后，x、y、z的值有幾種可能，各為多少？答：1：x=12，y=11，z=19。2：x=12，y=23，z=19。3：x=12，y=11，z=7。5、為什么說最高響應(yīng)比優(yōu)先作業(yè)調(diào)度算法是對先來先服務(wù)以及短作業(yè)優(yōu)先這兩種調(diào)度算法的折中？答：先來先服務(wù)的作業(yè)調(diào)度算法，重點考慮的是作業(yè)在后備作業(yè)隊列里的等待時間，因此對短作業(yè)不利；短作業(yè)優(yōu)先的調(diào)度算法，重點考慮的是作業(yè)所需的CPU時間，因此對長作業(yè)不利。最高響應(yīng)比優(yōu)先作業(yè)調(diào)度算法，總是在需要調(diào)度時，考慮作業(yè)已經(jīng)等待的時間和所需運行時間之比，即：1+（作業(yè)已等待時間/作業(yè)所需CPU時間）比值的分母是一個不變的量。隨著時間的推移，一個作業(yè)的“已等待時間”會不斷發(fā)生變化，也就是分子在不斷地變化。顯然，短作業(yè)比較容易獲得較高的響應(yīng)比。這是因為它的分母較小，只要稍加等待，整個比值就會很快上升。另一方面，長作業(yè)的分母雖然很大，但隨著它等待時間的增加，比值也會逐漸上升，從而獲得較高的響應(yīng)比?？梢娮罡唔憫?yīng)比優(yōu)先作業(yè)調(diào)度算法，既照顧到了短作業(yè)的利益，也照顧到了長作業(yè)的利益，是對先來先服務(wù)以及短作業(yè)優(yōu)先這兩種調(diào)度算法的一種折中。6、請對比操作系統(tǒng)中“死鎖”和“饑餓”問題。答：死鎖是因進程競爭資源，但系統(tǒng)擁有資源的數(shù)量有限，或并發(fā)進程推進的順序不當(dāng)而造成的一種永遠等待資源的僵局。饑餓是指每個資源占用者都在有限時間內(nèi)釋放占用的資源，但申請進程仍然長時間得不到資源的現(xiàn)象，常常是策略不公平的體現(xiàn)。7、一個計算機有6臺設(shè)備X，有n個進程競爭使用，每個進程最多需要兩臺。n最多為多少時，系統(tǒng)不存在死鎖的危險？答：由于每個進程最多需要兩臺設(shè)備X，考慮極端情況：每個進程已經(jīng)都申請了一臺。那么只要還有一臺空閑，就可以保證所有進程都可以完成。也就是說當(dāng)有條件：n+1=6（即n=5）時，系統(tǒng)就不存在死鎖的危險。8、3個進程P1、P2和P3并發(fā)工作。進程P1需用資源S3和S1；進程P2需用資源S1和S2；進程P3需用資源S2和S3。（1）若對資源分配不加限制，會發(fā)生死鎖情況，請畫出發(fā)生死鎖時，3個進程和3個資源之間的進程資源分配圖。（2）為保證進程正確工作，應(yīng)采用怎樣的資源分配策略。答：（1）不加限制會出現(xiàn)死鎖情況：（2）可以采用的方法有多種，下面是幾種可行的方法：分配資源時，一次性分配該進程運行過程中所需的所有資源。破壞了死鎖的必要條件之一“請求和保持條件”。申請資源時，如果不能立即獲得新的資源，則釋放已經(jīng)獲得的資源。破壞死鎖的必要條件之一“不可剝奪條件”。對所有的資源進行編號，每個進程在申請資源時，嚴(yán)格按照資源編號遞增的次序申請資源。這種方法是破壞了死鎖的必要條件之一“環(huán)路等待條件”。1.4解答題1、某系統(tǒng)有三個作業(yè)：作業(yè)到達時間所需CPU時間18.81.529.00.439.51.0系統(tǒng)確定在它們?nèi)康竭_后，開始采用響應(yīng)比高者優(yōu)先調(diào)度算法，并忽略系統(tǒng)調(diào)度時間。試問對它們的調(diào)度順序是什么？各自的周轉(zhuǎn)時間是多少？請寫出計算過程，并填寫下面表格。答：三個作業(yè)是在9.5時全部到達的。這時它們各自的響應(yīng)比如下：作業(yè)1的響應(yīng)比

=（9.5

–

8.8）/

1.5

=

0.46作業(yè)2的響應(yīng)比

=（9.5

–

9.0）/

0.4

=

1.25作業(yè)3的響應(yīng)比

=（9.5

–

9.5）/

1.0

=

0因此，最先應(yīng)該調(diào)度作業(yè)2運行，因為它的響應(yīng)比最高。它運行了0.4后完成，這時的時間是9.9。再計算作業(yè)1和3此時的響應(yīng)比：作業(yè)1的響應(yīng)比

=（9.9

–

8.8）/

1.5

=

0.73作業(yè)3的響應(yīng)比

=（9.9

–

9.5）/

1.0

=

0.40因此，第二個應(yīng)該調(diào)度作業(yè)1運行，因為它的響應(yīng)比最高。它運行了1.5后完成，這時的時間是11.4。第三個調(diào)度的是作業(yè)3，它運行了1.0后完成，這時的時間是12.4。整個實施過程如下。作業(yè)到達時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間18.81.59.911.42.629.00.49.59.90.939.51.011.412.42.9作業(yè)的調(diào)度順序是2→1→3。各自的周轉(zhuǎn)時間為：作業(yè)1為0.9；作業(yè)2為2.6；作業(yè)3為2.9。2、有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的非搶式調(diào)度算法，進程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列中，作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。作業(yè)到達時間所需CPU時間優(yōu)先數(shù)A10:0040分鐘5B10:2030分鐘3C10:3050分鐘4D10:5020分鐘6列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間，并計算平均作業(yè)周轉(zhuǎn)時間。答：(1)每個作業(yè)運行將經(jīng)過兩個階段：作業(yè)調(diào)度(SJF算法)和進程調(diào)度(優(yōu)先數(shù)搶占式)。另外，批處理最多容納2道作業(yè)，更多的作業(yè)將在后備隊列等待。10:00，作業(yè)A到達并投入運行。10:20，作業(yè)B到達且優(yōu)先權(quán)高于作業(yè)A，故作業(yè)B投入運行而作業(yè)A在就緒隊列等待。10:30，作業(yè)C到達，因內(nèi)存中已有兩道作業(yè)，故作業(yè)C進入作業(yè)后備隊列等待。10:50，作業(yè)B運行結(jié)束，作業(yè)D到達，按短作業(yè)優(yōu)先算法，作業(yè)D被裝入內(nèi)存進入就緒隊列。而由于作業(yè)A的優(yōu)先級高于作業(yè)D，故作業(yè)A投入運行。11:10，作業(yè)A運行結(jié)束，作業(yè)C被調(diào)入內(nèi)存，且作業(yè)C的優(yōu)先級高于作業(yè)D，故作業(yè)C投入運行。12:00，作業(yè)C運行結(jié)束，作業(yè)D投入運行。12:20，作業(yè)D運行結(jié)束。各作業(yè)周轉(zhuǎn)時間為：作業(yè)A70，作業(yè)B30，作業(yè)C90，作業(yè)D90。(2)平均作業(yè)周轉(zhuǎn)時間為70分鐘。作業(yè)進入內(nèi)存時間運行結(jié)束時間作業(yè)周轉(zhuǎn)時間平均作業(yè)周轉(zhuǎn)時間A10:0011:107070B10:2010:5030C11:1012:0090D10:5012:20903、有一個垃圾分揀機器人系統(tǒng)，擁有兩個機器手臂，可分別自動在垃圾箱里面分揀可回收易拉罐和塑料瓶。設(shè)分揀系統(tǒng)有二個進程P1和P2，其中P1驅(qū)動左臂揀易拉罐；P2驅(qū)動右臂揀塑料瓶。規(guī)定每個手臂每次只能揀一個物品；當(dāng)一個手臂在揀時，不允許另一個手臂去揀；當(dāng)一個手臂揀了一個物品后，必須讓另一個手臂去揀。試用信號量和P、V操作實現(xiàn)兩進程P1和P2能并發(fā)正確執(zhí)行的程序。答：實質(zhì)上是兩個進程的同步問題，設(shè)信號量S1和S2分別表示可揀易拉罐和塑料瓶，不失一般性，若令先揀易拉罐。varS1,S2:semaphore;S1:=1;S2:=0;cobegin{processP1beginrepeatP(S1);揀易拉罐V(S2);untilfalse;endprocessP2beginrepeatP(S2);揀塑料瓶V(S1);untilfalse;end}coend.4.桌上有一只空盤子，允許存放一只水果。爸爸可向盤中放蘋果和桔子，兒子專等著取盤中的桔子然后吃掉，女兒專等著取盤中的蘋果然后吃掉。規(guī)定盤子一次只能放一只水果，盤子中水果沒有被取走時，爸爸不可放新水果；盤子中沒有水果時，女兒和兒子來取水果時將需等待。請用信號量和P、V原語實現(xiàn)爸爸、兒子、女兒3個并發(fā)進程的同步。答：設(shè)置3個信號量：intS=1;//盤子是否為空，開始為空intSa=0;//盤子是否有蘋果intSb=0;//盤子是否有桔子CobeginFather(){While(1){ P(S); 水果放入盤中；If(放入的是桔子)V(Sb);ElseV(Sa);}Son(){ While(1) { P(Sb); 從盤中取出桔子； V(S); 吃桔子； }}Daughter(){ While(1) { P(Sa); 從盤中取出蘋果； V(S); 吃蘋果； }}Coend5、內(nèi)存中有一組緩沖區(qū)被多個生產(chǎn)者進程、多個消費者進程共享使用，總共能存放10個數(shù)據(jù)，生產(chǎn)者進程把生成的數(shù)據(jù)放入緩沖區(qū)，消費者進程從緩沖區(qū)中取出數(shù)據(jù)使用。緩沖區(qū)滿時生產(chǎn)者進程就停止將數(shù)據(jù)放入緩沖區(qū)，緩沖區(qū)空時消費者進程停止取數(shù)據(jù)。數(shù)據(jù)的存入和取出不能同時進行，試用信號量及P、V操作來實現(xiàn)該方案。答：semaphoremutex,empty,full;mutex=1; //互斥信號量empty=10; //生產(chǎn)者進程的同步信號量full=0; //消費者進程的同步信號量 cobeginprocessPi//生產(chǎn)者進程{while(1){生產(chǎn)數(shù)據(jù)x;P(empty) //看看是否還有空間可放P(mutex); //互斥使用放入;V(full); ///增1(可能喚醒一個消費者)V(mutex); }}processCj//消費者進程{while(1){P(full) //看看是否有數(shù)據(jù)P(mutex); //互斥使用取出;V(emtpy); //增1(可能喚醒一個生產(chǎn)者)V(mutex); }}coend6、假定系統(tǒng)有三個并發(fā)進程read,move和print共享緩沖器B1和B2。進程read負(fù)責(zé)從輸入設(shè)備上讀信息，每讀出一個記錄后把它存放到緩沖器B1中。進程move從緩沖器B1中取出一記錄，加工后存入緩沖器B2。進程print將B2中的記錄取出打印輸出。緩沖器B1和B2每次只能存放一個記錄。要求三個進程協(xié)調(diào)完成任務(wù)，使打印出來的與讀入的記錄的個數(shù)，次序完全一樣。請用信號量和P、V操作，寫出它們的并發(fā)程序。答：beginSR,SM1,SM2,SP:semaphore;B1,B2:record;SR:=1;SM1:=0;SM2:=1;SP:=0cobeginprocessreadX:record;beginR:(接收來自輸入設(shè)備上一個記錄)X:=接收的一個記錄；P(SR)；B1:=X;V(SM1);gotoR;end;ProcessmoveY:record;beginM:P(SM1);Y:=B1;V(SR)加工YP(SM2)；B2:=Y;V(SP);gotoM;end;ProcessprintZ:record;beginP:P(SP);Z:=B2;V(SM2)打印ZgotoP;end;coend;end;7、用銀行家算法避免系統(tǒng)死鎖：進程已占有資源數(shù)最大需求數(shù)ABCDABCDP130114111P201000212P311104210P411011111P500002110當(dāng)前系統(tǒng)資源總量為A類6個、B類3個、C類個4、D類2個。（1）系統(tǒng)是否安全？請分析說明理由。（2）若進程B請求(0,0,1,0)，可否立即分配？請分析說明理由。答：(1)由已知條件可得Need和Avaiable矩陣如下：進程分配矩陣尚需矩陣(Need)可用資源數(shù)向量(Avaiable)P1301111001020P201000112P311103100P411010010P500002110利用銀行家算法對此時刻的資源分配情況進行分析如下表：進程WorkNeedAllocationWork+AllocationFinishP41020001011012121trueP12121110030115132trueP25132011201005232trueP35232310011106342trueP56342211000006342true從上述分析可知，存在一個安全序列D，A，B，C，E，（答案不唯一），故當(dāng)前系統(tǒng)是否安全的。 （2）若進程B請求(0,0,1,0)，試分配并修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，則系統(tǒng)狀態(tài)變?yōu)椋哼M程分配矩陣尚需矩陣(Need)可用資源數(shù)向量(Avaiable)P1301111001010P201100102P311103100P411010010P500002110利用銀行家算法對此時刻的資源分配情況進行分析如下表：進程WorkNeedAllocationWork+AllocationFinishP41010001011012111trueP12111110030115122trueP25122010201105232trueP35232310011106342trueP56342211000006342true從上述分析可知，存在安全序列D，A，B，C，E，（答案不唯一）故系統(tǒng)仍是否安全的，因此可