數(shù)據(jù)結(jié)構(gòu)作業(yè)的狀態(tài)與處理流程PPT課件

1、其他算法其他算法1.最短剩余時(shí)間優(yōu)先算法最短剩余時(shí)間優(yōu)先算法SRTF（Shortest Remaining Time First）: 把把SJF算法改為搶占式的算法改為搶占式的SJF算法算法 一個(gè)新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要一個(gè)新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要的的CPU時(shí)間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來(lái)還需時(shí)間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來(lái)還需的的CPU時(shí)間短，時(shí)間短，SRTF強(qiáng)占當(dāng)前正在執(zhí)行作業(yè)的強(qiáng)占當(dāng)前正在執(zhí)行作業(yè)的CPU。 此算法不但適用于作業(yè)此算法不但適用于作業(yè)JOB調(diào)度，同樣也適調(diào)度，同樣也適用于進(jìn)程調(diào)度。用于進(jìn)程調(diào)度。第1頁(yè)/共9頁(yè) 當(dāng)新進(jìn)程加入就緒隊(duì)列時(shí)，如果它需要的運(yùn)行時(shí)間

2、比當(dāng)前運(yùn)行的進(jìn)程所需的剩余時(shí)間還短，則執(zhí)行切換。進(jìn) 程到達(dá)時(shí)間運(yùn)行時(shí)間108214329435圖4-7 最短剩余時(shí)間優(yōu)先法調(diào)度結(jié)果表4-3 進(jìn)程列表第2頁(yè)/共9頁(yè) 在兩道環(huán)境下有四個(gè)作業(yè)，已知它們進(jìn)入系統(tǒng)的時(shí)間、估計(jì)運(yùn)行時(shí)間。系統(tǒng)采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法， 作業(yè)被調(diào)度運(yùn)行后不再退出。 當(dāng)一新作業(yè)投入運(yùn)行后，可按照作業(yè)運(yùn)行時(shí)間長(zhǎng)短調(diào)整作業(yè)執(zhí)行的次序。 請(qǐng)給出這四個(gè)作業(yè)的執(zhí)行時(shí)間序列，并計(jì)算出平均周轉(zhuǎn)時(shí)間及帶權(quán)平均周轉(zhuǎn)時(shí)間作業(yè)調(diào)度算法應(yīng)用例子第3頁(yè)/共9頁(yè)兩道批處理系統(tǒng)中最短作業(yè)優(yōu)先作業(yè)算法計(jì)算結(jié)果作作業(yè)業(yè)進(jìn)進(jìn)入入時(shí)時(shí)間間估估計(jì)計(jì)運(yùn)運(yùn)行行時(shí)時(shí)間間（分分鐘鐘）開(kāi)開(kāi)始始時(shí)時(shí)間間結(jié)結(jié)束束時(shí)時(shí)間間周周轉(zhuǎn)

3、轉(zhuǎn)時(shí)時(shí)間間（分分鐘鐘）帶帶權(quán)權(quán)周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間JOB110：003010：0011：05654.167JOB210：052010：0510：25201JOB310：10510：2510：30204JOB410：201010：3010：40202作作業(yè)業(yè)平平均均周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間 T = 31.25作作業(yè)業(yè)帶帶權(quán)權(quán)平平均均周周轉(zhuǎn)轉(zhuǎn)時(shí)時(shí)間間 W = 2.7912511.167第4頁(yè)/共9頁(yè)四個(gè)作業(yè)的執(zhí)行時(shí)間序列為：JOB1JOB1：1010：00001010：0505，1010：40401111：0505JOB2JOB2：1010：05051010：2525JOB3JOB3：1010：2525101

4、0：3030JOB4JOB4：1010：30301010：4040兩道批處理系統(tǒng)中最短作業(yè)優(yōu)先作業(yè)算法計(jì)算結(jié)果（續(xù)1）第5頁(yè)/共9頁(yè)例題 一個(gè)計(jì)算機(jī)系統(tǒng)中擁有6臺(tái)打印機(jī)，現(xiàn)有N個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程要求兩臺(tái)，試問(wèn)，N的值如何選取時(shí)系統(tǒng)中絕對(duì)不會(huì)出現(xiàn)死鎖？ N=6-1第6頁(yè)/共9頁(yè)假定某計(jì)算機(jī)系統(tǒng)有R1和R2兩類(lèi)可在使用資源（其中R1有兩個(gè)單位，R2有一個(gè)單位），它們被進(jìn)程P1和P2所共享，且已知兩個(gè)進(jìn)程均以 申請(qǐng)R1 申請(qǐng)R2 申請(qǐng)R1 釋放R1 釋放R2 釋放R1 所以的順序使用兩類(lèi)資源。試求出系統(tǒng)運(yùn)行過(guò)程中可能達(dá)到的死鎖點(diǎn)，并劃出死鎖點(diǎn)的資源分配圖（或進(jìn)程資源圖）。第7頁(yè)/共9頁(yè)解答： 當(dāng)兩個(gè)進(jìn)程都執(zhí)行完第一步（申請(qǐng)R1）后，無(wú)論哪一個(gè)進(jìn)程執(zhí)行完第二步（申請(qǐng)R2），都會(huì)造成死鎖。由于系統(tǒng)沒(méi)有空閑資源，而