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

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