操作系統(tǒng) 習(xí)題及答案 第四章 進(jìn)程線程調(diào)度

第四章進(jìn)程線程調(diào)度習(xí)題1．試述進(jìn)程調(diào)度的主要任務(wù)。為什么說(shuō)它把一臺(tái)物理機(jī)變成多臺(tái)邏輯上的處理機(jī)？進(jìn)程調(diào)度的主要任務(wù)是使CPU運(yùn)行能夠在多個(gè)進(jìn)程之間高效切換，以實(shí)現(xiàn)并發(fā)執(zhí)行和有效使用處理器。進(jìn)程調(diào)度把一臺(tái)物理機(jī)變成多臺(tái)邏輯上的處理機(jī)，因?yàn)檎{(diào)度程序能使計(jì)算機(jī)同時(shí)處理多個(gè)進(jìn)程，讓每個(gè)進(jìn)程都認(rèn)為自己獨(dú)占了處理器。2．搶占式進(jìn)程調(diào)度是指系統(tǒng)能夠強(qiáng)制性地使執(zhí)行進(jìn)程放棄處理機(jī)。試問(wèn)分時(shí)系統(tǒng)采用的是搶占式還是非搶占式進(jìn)程調(diào)度？實(shí)時(shí)系統(tǒng)呢？分時(shí)系統(tǒng)采用的是搶占式進(jìn)程調(diào)度。因?yàn)樵诜謺r(shí)系統(tǒng)中，所有用戶(hù)共享計(jì)算機(jī)，系統(tǒng)要保證各個(gè)用戶(hù)能公平地使用到計(jì)算資源，因此需要事先設(shè)定一個(gè)時(shí)間片，時(shí)間片結(jié)束后強(qiáng)行搶占資源。實(shí)時(shí)系統(tǒng)如硬實(shí)時(shí)系統(tǒng)或軟實(shí)時(shí)系統(tǒng)，一般也采用搶占式調(diào)度，以保證高優(yōu)先級(jí)的任務(wù)能及時(shí)響應(yīng)。3．在CPU按優(yōu)先級(jí)調(diào)度的系統(tǒng)中：（1）沒(méi)有運(yùn)行進(jìn)程是否一定就沒(méi)有就緒進(jìn)程？沒(méi)有運(yùn)行進(jìn)程并不意味著就沒(méi)有就緒進(jìn)程，因?yàn)橛锌赡芩芯途w進(jìn)程正處于等待狀態(tài)。（死鎖不存在就緒進(jìn)程處于等待狀態(tài)，等待狀態(tài)就不是就緒狀態(tài)）不存在就緒進(jìn)程處于等待狀態(tài)，等待狀態(tài)就不是就緒狀態(tài)（2）沒(méi)有運(yùn)行進(jìn)程，沒(méi)有就緒進(jìn)程或兩者都沒(méi)有是否可能？各是什么情況？沒(méi)有運(yùn)行進(jìn)程：等待外設(shè)或其他資源的響應(yīng)；沒(méi)有就緒進(jìn)程：恰好滿(mǎn)負(fù)載，均在運(yùn)行；都沒(méi)有：參見(jiàn)（1）（3）運(yùn)行進(jìn)程是否一定是自由進(jìn)程中優(yōu)先數(shù)最高的？不一定，在動(dòng)態(tài)優(yōu)先級(jí)調(diào)度中可能存在調(diào)度后其他進(jìn)程優(yōu)先級(jí)提升的情況。4．對(duì)某系統(tǒng)進(jìn)行監(jiān)測(cè)后表明平均每個(gè)進(jìn)程在I/O阻塞之前的運(yùn)行時(shí)間為T(mén)。一次進(jìn)程切換需要的時(shí)間為S，這里S實(shí)際上就是開(kāi)銷(xiāo)。對(duì)于采用時(shí)間片長(zhǎng)度為Q的時(shí)間片輪轉(zhuǎn)法，請(qǐng)給出以下各種情況的CPU利用率的計(jì)算公式。（1）Q=∞100%T/（T+S）（2）Q>T100%T/（T+S）（3）S<Q<TQ/(Q+S)（4）Q=S50%（5）Q趨近于00%5．大多數(shù)時(shí)間片輪轉(zhuǎn)調(diào)度程序使用一個(gè)固定大小的時(shí)間片，請(qǐng)給出選擇小時(shí)間片的理由。然后，再給出選擇大時(shí)間片的理由。選擇小的時(shí)間片可以減少響應(yīng)時(shí)間并提高交互性；而選擇大的時(shí)間片可以減少調(diào)度開(kāi)銷(xiāo)。6．有5個(gè)批處理作業(yè)A到E幾乎同時(shí)到達(dá)一計(jì)算中心。它們的估計(jì)運(yùn)行時(shí)間分別為10，6，2，4和8分鐘。其優(yōu)先數(shù)(由外部設(shè)定)分別為3，5，2，1和4，其中5級(jí)為最高優(yōu)先級(jí)。對(duì)于下列每種調(diào)度算法，計(jì)算其平均進(jìn)程周轉(zhuǎn)時(shí)間，可忽略進(jìn)程切換的開(kāi)銷(xiāo)。（1）時(shí)間片輪轉(zhuǎn)法假設(shè)q=2：進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間A0100101824283030B06212202222C02466D046141616E0881622262828avg=20.4102/5（2）優(yōu)先級(jí)調(diào)度進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間A010142424B06066C02242626D04263030E0861414avg=20100/5（3）先來(lái)先服務(wù)（按照次序10，6，2，4，8運(yùn)行）進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間A01001010B06101616C02161818D04182222E08223030avg=19.296/5（4）最短作業(yè)優(yōu)先進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間A010203030B0661212C02022D04266E08122020avg=1470/5對(duì)（1），假設(shè)系統(tǒng)具有多道處理能力，每個(gè)作業(yè)均獲得公平的CPU時(shí)間，對(duì)（2）到（4）假設(shè)任一時(shí)刻只有一個(gè)作業(yè)運(yùn)行，直到結(jié)束。所有的作業(yè)都是CPU密集型作業(yè)。7．有5個(gè)待運(yùn)行作業(yè)，它們的估計(jì)運(yùn)行時(shí)間分別是9，6，3，5和X。采用哪種次序運(yùn)行各作業(yè)將得到最短的平均響應(yīng)如果是響應(yīng)時(shí)間的話，假設(shè)作業(yè)一旦得到調(diào)度就有響應(yīng)，那么，適用時(shí)間片輪轉(zhuǎn)，且時(shí)間片越小越好。本題的解法是適用平均周轉(zhuǎn)時(shí)間。時(shí)間？（答案依賴(lài)于X）如果是響應(yīng)時(shí)間的話，假設(shè)作業(yè)一旦得到調(diào)度就有響應(yīng)，那么，適用時(shí)間片輪轉(zhuǎn)，且時(shí)間片越小越好。本題的解法是適用平均周轉(zhuǎn)時(shí)間。采用SJF（短作業(yè)優(yōu)先）的方式：如果X>9，則運(yùn)行順序?yàn)?→5→6→9→X。如果6<X<=9，運(yùn)行順序?yàn)?→5→6→X→9。如果5<X<=6，運(yùn)行順序?yàn)?→5→X→6→9。如果3<X<=5，運(yùn)行順序?yàn)?→X→5→6→9。如果X<=3，運(yùn)行順序?yàn)閄→3→5→6→9。8．列出并簡(jiǎn)單定義線程調(diào)度的四種技術(shù)。負(fù)載分配：系統(tǒng)維護(hù)一個(gè)就緒進(jìn)程的全局隊(duì)列，每個(gè)處理器只要空閑就從隊(duì)列中選擇一個(gè)線程。組調(diào)度：一組相關(guān)的線程基于一對(duì)一的原則，同時(shí)調(diào)度到一組處理器上運(yùn)行。專(zhuān)用處理器分配：通過(guò)把線程指定到處理器來(lái)定義隱式的調(diào)度。在程序執(zhí)行過(guò)程中，每個(gè)程序被分配給一組處理器，處理器的數(shù)目與程序中線程的數(shù)目相等。當(dāng)程序終止時(shí)，處理器返回到總的處理器池中，可供分配給另一個(gè)程序。動(dòng)態(tài)調(diào)度：在執(zhí)行期間，進(jìn)程中線程的數(shù)目可以改變。9．列出并簡(jiǎn)單定義四類(lèi)實(shí)時(shí)調(diào)度算法。靜態(tài)表驅(qū)動(dòng)調(diào)度算法：執(zhí)行關(guān)于可行調(diào)度的靜態(tài)分析。分析的結(jié)果是一個(gè)調(diào)度，它用于確定在運(yùn)行時(shí)一個(gè)任務(wù)何時(shí)必須開(kāi)始執(zhí)行。靜態(tài)優(yōu)先級(jí)驅(qū)動(dòng)搶占調(diào)度算法：同樣，執(zhí)行一個(gè)靜態(tài)分析，但是沒(méi)有指定調(diào)度，而且用于給任務(wù)指定優(yōu)先級(jí)，使得可以使用傳統(tǒng)的優(yōu)先級(jí)驅(qū)動(dòng)的搶占式調(diào)度器?；趧?dòng)態(tài)規(guī)劃調(diào)度調(diào)度算法：在運(yùn)行時(shí)動(dòng)態(tài)地確定可行性，而不是在開(kāi)始運(yùn)行前離線地確定。一個(gè)到達(dá)的任務(wù)，只有當(dāng)能夠滿(mǎn)足它的時(shí)間約束時(shí)，才可以被接受執(zhí)行?？尚行苑治龅慕Y(jié)果是一個(gè)調(diào)度或規(guī)劃，可用于確定何時(shí)分派這個(gè)任務(wù)。動(dòng)態(tài)盡力調(diào)度調(diào)度算法：不執(zhí)行可行性分析。系統(tǒng)試圖滿(mǎn)足所有