操作系統(tǒng)調(diào)度與死鎖理論題答案

1、第三章處理機調(diào)度與死鎖1 .高級調(diào)度與低級調(diào)度的主要任務(wù)是什么？為什么要引入中級調(diào)度？(1)高級調(diào)度又稱為作業(yè)調(diào)度。它是批處理系統(tǒng)中使用的一種調(diào)度。其主要任務(wù)是按照某種算法從外存的后備隊列上選擇一個或多個作業(yè)調(diào)入內(nèi)存，并為其創(chuàng)建進程、分配必要的資源，然后再將所創(chuàng)建的進程控制塊插入就緒隊列中。(2)低級調(diào)度又稱進程調(diào)度。它是距離硬件最近的一級調(diào)度。其主要任務(wù)是按照某種算法從就緒隊列上選擇一個(或多個)進程，使其獲得CPU。(3)引入中級調(diào)度的目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。其功能是，讓那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源，而是調(diào)其到外存上等候。此時的進程狀態(tài)為掛起狀態(tài)。當(dāng)這些進程重

2、新具備運行條件且內(nèi)存空閑時，由中級調(diào)度選擇一部分掛起狀態(tài)的進程調(diào)入內(nèi)存并將其狀態(tài)變?yōu)榫途w狀態(tài)。2 .處理機調(diào)度算法的共同目標(biāo)是什么？批處理系統(tǒng)的調(diào)度目標(biāo)又是什么？共同目標(biāo)：資源利用率，公平性，平衡性，策略強制執(zhí)行。批處理系統(tǒng)的調(diào)度目標(biāo)：平均周轉(zhuǎn)時間短，系統(tǒng)吞吐量高，處理機利用率高。6 .為什么要引入高響應(yīng)比優(yōu)先調(diào)度算法？它有何優(yōu)點？在批處理系統(tǒng)中，F(xiàn)CFS算法所考慮的只是作業(yè)的等待時間，而忽視了作業(yè)的運行時間。而SJF算法正好與之相反，只考慮作業(yè)的運行時間，而忽視了作業(yè)的等待時間。高響應(yīng)比優(yōu)先調(diào)度算法則是既考慮了作業(yè)的等待時間，又考慮作業(yè)運行時間的調(diào)度算法，因此既照顧了短作業(yè)，又不致使長作業(yè)的

3、等待時間過長，從而改善了處理機調(diào)度的性能7 .試說明低級調(diào)度的主要功能。保存處理機的現(xiàn)場信息、按某種算法選取進程、把處理機分配給進程。12 .試比較FCF序口SJRW種進程調(diào)度算法。相同點：兩種調(diào)度算法都可用于作業(yè)調(diào)度與進程調(diào)度不同點：FCFS調(diào)度算法每次都從后備隊列中選擇一個或多個最先進入該隊列的作業(yè)，將它們調(diào)入內(nèi)存、分配資源、創(chuàng)建進程、插入到就緒隊列。該算法有利于長作業(yè)/進程，不利于短作業(yè)/進程。SJF算法每次調(diào)度都從后備隊列中選擇一個或若干個運行時間最短的作業(yè)，調(diào)入內(nèi)存中運行。該算法有利于短作業(yè)/進程，不利于長作業(yè)/進程。13 .在時間片輪轉(zhuǎn)法中，應(yīng)如何確定時間片的大?。繒r間片應(yīng)略大于一

4、次典型的交互需要的時間。一般因考慮三個因素：系統(tǒng)對相應(yīng)時間的要求、就緒隊列中進程的數(shù)目和系統(tǒng)的處理能力。20.按調(diào)度方式可將實時調(diào)度算法分為哪幾種？非搶占式和搶占式。非搶占式又分為非搶占式輪轉(zhuǎn)調(diào)度算法和非搶占式優(yōu)先調(diào)度算法，搶占式又分為基于時鐘中斷的搶占式優(yōu)先級調(diào)度算法和立即搶占的優(yōu)先級調(diào)度算法。27.何謂死鎖？產(chǎn)生死鎖的原因和必要條件是什么？死鎖是指多個進程在運行過程中因爭奪資源而造成的一種僵局，當(dāng)進程處于這種保持狀態(tài)時，若無外力作用，它們都將無法再向前推進。產(chǎn)生死鎖的原因為競爭資源和進程間推進順序非法。其必要條件是：互斥條件、請求和保持條件、不剝奪條件、環(huán)路等待條件。29.請詳細說明可通過

5、哪些途徑預(yù)防死鎖。(1)推棄“請求和保持”條件，就是如果系統(tǒng)有足夠資源，便一次性把進程需要的所有資源分配給它；(2)挨棄“不剝奪”條件，就是已經(jīng)擁有資源的進程，當(dāng)它提出新資源請求而不能立即滿足時，必須釋放它已保持的所有資源，待以后需要時再重新申請；(3)挨棄“環(huán)路等待”條件，就是將所有資源按類型排序標(biāo)號，所有進程對資源的請求必須嚴格按序號遞增的次序提出。21.在銀行家算法的例子中，如果P0發(fā)出的請求向量由Request0(0,2,0改為Request0(0,1,0)問系統(tǒng)可否將資源分配給它？ProcessAllocationNeedAvailableABCABCABCP00,2,07,3,32

6、,2,0P13,0,20,2,0P23,0,26,0,0P32,1,10,1,1P40,0,24,3,1進程/資源情況WorkNeedAllocationWork+AllocationFinishABCABCABCABCP12,2,00,2,03,0,25,2,2Ture5,2,20,1,12,1,17,3,3Ture7,3,37,3,30,2,07,5,3TureP2P47,5,36,0,03,0,210,5,5Ture10,5,54,3,10,0,210,5,7Ture可以.首先,Request0(0,1,0)<=Need0(7,4,3),Request0(0,1,0)<=Av

7、ailable(2,3,0);分配后可修改得一資源數(shù)據(jù)表(表略),進行安全性檢查，可以找到一個安全序列P1,P3,P0,P2,P4,因此，系統(tǒng)是安全的，可以立即將資源分配給P0.31.在銀行家算法中，若出現(xiàn)下述資源分配情況，試問:ProcessAllocationNeedAvailablePo003200121622Pi10001750P213542356P303320652P400140656(1)該狀態(tài)是否安全？若進程P2提出請求Request(1,2,2,2后，系統(tǒng)能否將資源分配給它？解：(1)進程/資源情況_(WorkNeedAllocationWork+AllocationJFini

8、shABCDABCDABCDABCDP01,6,2,20,0,1,20,0,3,21,6,5,4TureP311,6,5,40,6,5,20,3,3,21,9,8,6TureP41,9,8,60,6,5,60,0,1,41,9,9,10Turepi1,9,9,101,7,5,01,0,0,02,9,9,10TureP22,9,9,102,3,5,61,3,5,43,12,14,11Ture據(jù)安全性檢查，可以找到一個安全序列P0,P3,P4,P1,P2,因此該狀態(tài)是安全的。(2) P2發(fā)出請求向量Request(1,2,2,2),系統(tǒng)進行如下檢查A.Request2(1,2,2,2)<=N

9、eed2(2,3,5,6)B.Request2(1,2,2,2)<=Available(1,6,2,2);C.系統(tǒng)暫時先假定可以為P2分配資源，修改有關(guān)數(shù)據(jù)，如下圖所示：ProcessAllocationNeedAvailableABCDABCDABCDP00,0,3,20,0,1,20,4,0,0P11,0,0,01,7,5,0P22,5,7,61,1,3,4P30,3,3,20,6,5,2P40,0,1,40,6,5,6D.進行安全性檢查，可用資源(0,4,0,0)已經(jīng)不能滿足任何一個進程需要,故系統(tǒng)進入不安全狀態(tài)，因此，系統(tǒng)不能將資源分配給P2例：有三類資源A(17)、B(5)、C

10、(20有5個進程P1-P5OT0時刻系統(tǒng)狀態(tài)如下:最大需求M已分配AP1559212P2536402P34011405P4425204P5424314問(2)、T0時刻，P2:Request(0,3,4)能否分配，為什么？(3)、在(2)的基礎(chǔ)上P4:Request(2,0,1)能否分配，為什么?(4)、在(3)的基礎(chǔ)上P1:Request(0,2,0)能否分配，為什么?解：(2) P2:Request(0,3,4)<Need2(1,3,4)Request(0,3,4)>Available(2,3,3),不能分配(3) Request4(2,0,1)<Need4(2,2,1)

11、Request4(2,0,1)>Available(2,3,3)假設(shè)分配，則能大需求(M)已分配(A)還需要P1559212347P2536402134P34011405006P4425405020P5424314110進行安全性檢查進程workneedallocationWork+allocfinishiP4032020204437trueP54371103147411trueP3741100640511416trueP21141613440215418trueP111541834721217520true由上表可知存在安全序列P4,P5,P3,P2,P1。因此系統(tǒng)是安全的可以將P4所申請的資源進行分配。（4）在（3）的基礎(chǔ)上，若進程P1請求資源（0,2,0）,按銀行家算法進行檢查:P1請求資源（0,2,0）<P1資源需求量（3,4,7）P1請求資源（0,2,0）W剩余資源數(shù)（0,3,2）試分配并修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，由此形成的