1、.第三章 作業(yè)講解1、有5個(gè)作業(yè)進(jìn)入就緒隊(duì)列等待運(yùn)行，預(yù)計(jì)它們的運(yùn)行時(shí)間分別為9、6、3、5與X，它們以什么樣的調(diào)度順序運(yùn)行時(shí)會(huì)取得最小的響應(yīng)時(shí)間？（答案與X值有關(guān)）答：短作業(yè)優(yōu)先調(diào)度算法是使響應(yīng)時(shí)間最小的調(diào)度算法：0 < X 3時(shí)，調(diào)度順序?yàn)椋?X、3、5、6、93 < X 5時(shí)，調(diào)度順序?yàn)椋?3、X、5、6、95 < X 6時(shí)，調(diào)度順序?yàn)椋?3、5、X、6、96 < X 9時(shí)，調(diào)度順序?yàn)椋?3、5、6、X、9X > 9時(shí)，調(diào)度順序?yàn)椋?3、5、6、9、X2、假設(shè)一個(gè)系統(tǒng)中有4個(gè)進(jìn)程，它們的到達(dá)時(shí)間和服務(wù)時(shí)間如表所示，忽略I/O以及其他開銷時(shí)間，若分別按先來先服

2、務(wù)（FCFS）、非搶占及搶占的短進(jìn)程優(yōu)先（SPF）、高響應(yīng)比優(yōu)先（HRRN）、時(shí)間片輪轉(zhuǎn)（RR，時(shí)間片=1）、多級(jí)反饋隊(duì)列調(diào)度算法（FB，第i級(jí)隊(duì)列的時(shí)間片=2i-1）進(jìn)行CPU調(diào)度，請(qǐng)給出各進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間A05B12C39D67算法時(shí)間進(jìn)程平均時(shí)間ABCDFCFS完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間55176316131.4423172.4310.251.97SPF（非搶占）完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間55176323202.221481.149.751.835SPF（搶占）完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間771.432123

3、202.221481.149.251.435HRRN完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間55176316131.4423172.4310.251.97RR（q=1）完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間12122.4431.523202.2222162.2912.752.1FB（q=2i-1）完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間13132.6652.523202.2221152.1413.252.3653、若有4個(gè)周期性任務(wù)，任務(wù)A要求每30ms執(zhí)行一次，執(zhí)行時(shí)間為15ms；任務(wù)B要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為5ms；任務(wù)C要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為15ms；任務(wù)D要求每100ms執(zhí)行一次，執(zhí)行時(shí)間為10m

4、s，應(yīng)如何按最低松弛度優(yōu)先算法對(duì)它們進(jìn)行CPU調(diào)試？ （要求畫出0-150ms時(shí)段的調(diào)度時(shí)序圖，并列出每次切換時(shí)每個(gè)任務(wù)的松弛度）答：對(duì)于上面的4個(gè)周期性任務(wù)，利用最低松弛度優(yōu)先算法進(jìn)行調(diào)度的情況如圖所示：1301401501201100908070604030201010050B2,C2A6,B4C4A5A4A3A2A1,B1C1,D1B3,C3D2到達(dá)時(shí)間必須完成時(shí)間A5,B3C3A4A3A2A1B2,C2D1B1,C180651401451251109095503530150松弛度D2=55A5=10B3=20D2=65A4=10D1=10B2=15B2=45C2=35D1=40A2=1

5、5B1=15D1=60A1=15B1=45C1=35D1=90B3=5D2=60B3=35C3=25D2=80A4=15B2=5A3=10B2=30D1=25A2=10D1=50B1=30C1=20D1=75D1B3A3C2D2A5C3A4B2A2B1C1A1任務(wù)執(zhí)行806515514011014512595503530150904、3個(gè)進(jìn)程共享4個(gè)同類型的資源，每個(gè)進(jìn)程最大需要2個(gè)資源，請(qǐng)問該系統(tǒng)是否會(huì)因?yàn)楦?jìng)爭(zhēng)該資源而死鎖？答：該系統(tǒng)不會(huì)因?yàn)楦?jìng)爭(zhēng)該類資源而死鎖。因?yàn)?，必有一個(gè)進(jìn)程可獲得2個(gè)資源故能順利完成，并釋放出其所占用的2個(gè)資源給其他進(jìn)程使用，使它們也順利完成。5、不安全狀態(tài)是否必然導(dǎo)致

6、系統(tǒng)進(jìn)入死鎖狀態(tài)？舉例說明。答：不安全狀態(tài)不一定導(dǎo)致進(jìn)入死鎖狀態(tài)。因?yàn)?，安全性檢查中使用的向量Max是進(jìn)程執(zhí)行前提供的，而在實(shí)際運(yùn)行過程中，一進(jìn)程需要的最大資源量可能小于Max，如一進(jìn)程對(duì)應(yīng)的程序中有一段進(jìn)行錯(cuò)誤處理的代碼，其中需要n個(gè)A種資源，若該進(jìn)程在運(yùn)行過程中沒有碰到相應(yīng)的錯(cuò)誤，而不需要調(diào)用該段錯(cuò)誤處理代碼，則它實(shí)際上將完全不會(huì)請(qǐng)求這n個(gè)A種資源。6、在銀行家算法中，若出現(xiàn)下面的資源分配情況：ProcessAllocationNeedAvailableP00 0 3 20 0 1 21 5 2 2P11 0 0 01 6 5 0P21 3 5 42 3 5 6P30 1 3 20 5 5

7、 2P40 0 1 40 6 5 8試問：1）該狀態(tài)是否安全（要求列出安全性算法檢查表）？ 2）若進(jìn)程P2提出請(qǐng)求Request(1,2,2,2)后，系統(tǒng)能否將資源分配給它（要求根據(jù)分配算法列出檢查過程）？ 3）如果系統(tǒng)立即滿足P2的上述請(qǐng)求，請(qǐng)問，系統(tǒng)是否立即進(jìn)入死鎖狀態(tài)，請(qǐng)說明原因？答：1）利用安全性算法對(duì)上面的狀態(tài)進(jìn)行分析，找到了一個(gè)安全序列P0、P3、P1、P2、P4，故系統(tǒng)是安全的。資源情況進(jìn)程WorkA B C DNeedA B C DAllocationA B C DWork+AllocationA B C DFinishP0P3P1P2P41 5 2 21 5 5 41 6 8

8、 62 6 8 63 9 13 100 0 1 20 5 5 21 6 5 02 3 5 60 6 5 80 0 3 20 1 3 21 0 0 01 3 5 4 0 0 1 41 5 5 41 6 8 62 6 8 63 9 13 103 9 14 14TrueTrueTrueTrueTrue2）P2發(fā)出請(qǐng)求向量Request(1,2,2,2)后，系統(tǒng)按銀行家算法進(jìn)行檢查：Request2(1,2,2,2)<=Need2(2,3,5,6)Request2(1,2,2,2)<=Available(1,5,2,2)系統(tǒng)先假定可為P2分配資源，并修改Available，Allocati

9、on2和Need2向量： Available=（0，3，0，0） Allocation2=(2,5,7,6) Need2=（1，1，3，4）進(jìn)行安全性檢查：此時(shí)對(duì)所有的進(jìn)程，條件Needi<=Available(0,3,0,0)都不成立，即Available不能滿足任何進(jìn)程的請(qǐng)求，故系統(tǒng)進(jìn)入不安全狀態(tài)。此時(shí)當(dāng)進(jìn)程P2提出請(qǐng)求Request(1,2,2,2)后，系統(tǒng)不能將資源分配給它。3）系統(tǒng)立即滿足進(jìn)程P2的請(qǐng)求（1，2，2，2）后，并沒有馬上進(jìn)入死鎖狀態(tài)。因?yàn)?，此時(shí)上述進(jìn)程并沒有申請(qǐng)新的資源，并因得不到資源而進(jìn)入阻塞狀態(tài)。只有當(dāng)上述進(jìn)程提出新的請(qǐng)求，并導(dǎo)致所有沒有執(zhí)行完的多個(gè)進(jìn)程因得不

10、到資源而阻塞時(shí)，系統(tǒng)才進(jìn)入死鎖狀態(tài)。7、進(jìn)程資源的使用情況和可用情況如表所示，請(qǐng)畫出資源分配圖，并對(duì)資源圖進(jìn)行簡(jiǎn)化，這種情況下系統(tǒng)會(huì)發(fā)生死鎖嗎？進(jìn)程當(dāng)前分配數(shù)待分配的請(qǐng)求可用資源R1R2R3R1R2R3R1R2R3P1P2P3P4231001310001100010010010000存在兩種化簡(jiǎn)序列1）p2-p1-p4-p3；2）p2-p4-p1-p38、要使下表中描述的狀態(tài)安全，可用資源的最小數(shù)目應(yīng)為多少？（注意，問題問的是可用資源的數(shù)目，而不是存在的資源數(shù)）。進(jìn)程當(dāng)前分配數(shù)最大分配數(shù)R1R1P1P2P3P411323297答：如果R1有一個(gè)資源可用，能保證P2運(yùn)行完。然后P2釋放它現(xiàn)在使用

11、的資源，使得R1類型的資源2個(gè)可用，這將允許P1執(zhí)行完。P1釋放它使用的資源后，R1類型的資源數(shù)增加為3個(gè)可用。只有3個(gè)R1類型的資源，如果P3、P4請(qǐng)求分配最大數(shù)目的資源，P3與P4就仍然處于死鎖狀態(tài)。如果一開始就有3個(gè)R1類型資源，而不是1個(gè)，P4就可以獲得5個(gè)R1的可用資源并運(yùn)行完。再加上P4原來占用的2個(gè)R1資源，就可以讓P3運(yùn)行。所以使該狀態(tài)安全的所需可用資源的最小個(gè)數(shù)為3。9、在時(shí)間片輪轉(zhuǎn)法中，應(yīng)如何確定時(shí)間片的大?。看穑簳r(shí)間片長(zhǎng)度可按如下方法確定：1）系統(tǒng)對(duì)相應(yīng)時(shí)間的要求；2）就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越?。ó?dāng)響應(yīng)時(shí)間一定時(shí)）；3）系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個(gè)時(shí)

12、間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長(zhǎng)；10、在解決死鎖問題的幾個(gè)方法中，哪種方法最易于實(shí)現(xiàn)？哪種方法能使資源利用率最高？答：解決死鎖問題可歸納為三種方法：預(yù)防死鎖、避免死鎖、檢測(cè)死鎖和解除死鎖。其中預(yù)防死鎖最容易實(shí)現(xiàn)的；避免死鎖使資源的利用率最高。課本上習(xí)題8、在批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中，各采用哪幾種進(jìn)程（作業(yè)）調(diào)度算法？答：批處理系統(tǒng)可采用的進(jìn)程調(diào)度算法有：高優(yōu)先權(quán)優(yōu)先調(diào)度算法、多級(jí)反饋隊(duì)列調(diào)度算法、FCFS、SJF 分時(shí)系統(tǒng)可采用的進(jìn)程調(diào)度算法有：基于時(shí)間片的輪轉(zhuǎn)算法、搶占式優(yōu)先權(quán)調(diào)度算法、多級(jí)反饋隊(duì)列調(diào)度算法實(shí)時(shí)系統(tǒng)可采用的進(jìn)程調(diào)度算法有：非搶占式優(yōu)

13、先權(quán)調(diào)度算法、搶占式優(yōu)先權(quán)調(diào)度算法、最早截止時(shí)間優(yōu)先算法、最低松弛度優(yōu)先算法（后兩種都屬于高優(yōu)先權(quán)優(yōu)先的實(shí)時(shí)調(diào)度算法）5、在銀行家算法中，若出現(xiàn)下面的資源分配情況：ProcessAllocationNeedAvailableP00 0 3 20 0 1 21 6 2 2P11 0 0 01 6 5 0P21 3 5 42 3 5 6P30 0 3 20 6 5 2P40 0 1 40 6 5 6試問：1）該狀態(tài)是否安全？ 2）若進(jìn)程P2提出請(qǐng)求Request(1,2,2,2)后，系統(tǒng)能否將資源分配給它？ 3）如果系統(tǒng)立即滿足P2的上述請(qǐng)求，請(qǐng)問，系統(tǒng)是否立即進(jìn)入死鎖狀態(tài)？答：1）利用安全性算法

14、對(duì)上面的狀態(tài)進(jìn)行分析，找到了一個(gè)安全序列P0、P3、P4、P1、P2，故系統(tǒng)是安全的。資源情況進(jìn)程WorkA B C DNeedA B C DAllocationA B C DWork+AllocationA B C DFinishP0P3P4P1P21 6 2 21 6 5 41 6 8 61 6 9 102 6 9 100 0 1 20 6 5 20 6 5 61 6 5 02 3 5 60 0 3 20 0 3 20 0 1 41 0 0 0 1 3 5 41 6 5 41 6 8 61 6 9 102 6 9 103 9 14 14TrueTrueTrueTrueTrue2）P2發(fā)出請(qǐng)求向量Request(1,2,2,2)后，系統(tǒng)按銀行家算法進(jìn)行檢查：Request2(1,2,2,2)<=Need2(2,3,5,6)Request2(1,2,2,2)<=Available(1,6,2,2)系統(tǒng)先假定可為P2分配資源，并修改Available，Allocation2和Need2向量： Available=（0，4，0，0） Allocation2=(2,5,7,6) Need2=（1，1，3，4）進(jìn)行安全性檢查：此時(shí)對(duì)所有的進(jìn)程