【正文】 第 5章 處理器調(diào)度 引言 5． 1 三級調(diào)度的概念 5． 2 作業(yè)調(diào)度 5． 3 進程調(diào)度 5． 4 常用的調(diào)度算法 5． 5 實例分析： UNIX進程調(diào)度 引言 處理器是計算機系統(tǒng)中一個十分重要的資源。隨著多道程序設(shè)計技術(shù)出現(xiàn)，處理器的管理也日趨復(fù)雜。對于不同類型的操作系統(tǒng)，處理器的管理方法各不相同。不同的處理器管理方法將為用戶提供不同性能的操作系統(tǒng)。因此，根據(jù) 操作系統(tǒng)目標(biāo) 的不同， 處理器的管理策略 是不盡相同的。 本章將以處理器管理為核心，討論與處理器調(diào)度有關(guān)的概念，并介紹常用的調(diào)度算法。 5． 1 三級調(diào)度的概念 在多道程序系統(tǒng)中 ， 一個作業(yè)被提交后 ， 并不一定能立即執(zhí)行 ， 必須經(jīng)過處理器調(diào)度 ， 方可為其創(chuàng)建進程 ， 分配內(nèi)存 ， 從而進入執(zhí)行狀態(tài) ， 稱為作業(yè)調(diào)度或高級調(diào)度 。 而作業(yè)的執(zhí)行歸結(jié)為進程的調(diào)度 ， 又稱為低級調(diào)度 。 在比較完善的系統(tǒng)中 ， 為了提高內(nèi)存的利用率 ， 往往還設(shè)置了對換調(diào)度 ， 即中級調(diào)度 。 5． 1． 1 作業(yè)的狀態(tài)及其轉(zhuǎn)換 作業(yè) 是用戶在一次解題或一個事務(wù)處理過程中要求計算機系統(tǒng)所做的工作的集合。 作業(yè)由用戶 程序、所需的數(shù)據(jù)及作業(yè)說明書 三部分組成。 計算機系統(tǒng)完成一個作業(yè)過程中所做的一項相對獨立的工作稱為一個 作業(yè)步 。 在多道程序系統(tǒng)中，一個作業(yè)在它的生命期內(nèi)要經(jīng)歷 提交、后備、運行和完成 四個主要的階段。 5． 1． 1 作業(yè)的狀態(tài)及其轉(zhuǎn)換 ?提交狀態(tài)： 當(dāng)用戶將自己的作業(yè)提交給操作員，操作員通過某種輸入方式將用戶提交的作業(yè)輸入到外存上時，稱此階段為作業(yè)處于提交狀態(tài)。作業(yè)輸入方式通常有 5種： ?聯(lián)機輸入方式： 該方式大多用在交互式系統(tǒng)中，用戶和系統(tǒng)通過交互式會話來輸入作業(yè)。在聯(lián)機方式中，外圍設(shè)備直接和主機相連接，一臺主機可連接一臺或多臺外圍設(shè)備。 ?脫機輸入方式： 脫機輸入方式利用低檔 I/O處理器作為外圍處理器進行輸入處理，提高了主機的資源利用率。 5． 1． 1 作業(yè)的狀態(tài)及其轉(zhuǎn)換 ?聯(lián)機輸入方式： 該方式大多用在交互式系統(tǒng)中，用戶和系統(tǒng)通過交互式會話來輸入作業(yè)。在聯(lián)機方式中，外圍設(shè)備直接和主機相連接，一臺主機可連接一臺或多臺外圍設(shè)備。 ?脫機輸入方式： 脫機輸入方式利用低檔 I/O處理器作為外圍處理器進行輸入處理，提高了主機的資源利用率。 5． 1． 1 作業(yè)的狀態(tài)及其轉(zhuǎn)換 ?直接耦合方式： 該方式是把主機和外圍低檔機通過一個公用的大容量外存直接耦合起來，從而省去了在脫機輸入時依靠人工干預(yù)來傳遞給后援存儲器的過程。 ? SPOOLing系統(tǒng)： 在 SPOOLing系統(tǒng)中，多臺外圍設(shè)備通過通道或 DMA器件將主機與外存連接起來，作業(yè)的輸入過程由主機中的操作系統(tǒng)控制。 ?網(wǎng)絡(luò)輸入方式： 該方式以上述幾種輸入方式為基礎(chǔ)。當(dāng)用戶需要把在網(wǎng)絡(luò)中某一臺主機上輸入的信息傳遞到同一網(wǎng)絡(luò)中的另一臺主機上進行操作或執(zhí)行時，就構(gòu)成了網(wǎng)絡(luò)輸入方式。 5． 1． 1 作業(yè)的狀態(tài)及其轉(zhuǎn)換 ?后備狀態(tài)： 當(dāng)操作系統(tǒng)為輸入并存放在外存輸入井上的作業(yè)建立一個作業(yè)控制塊（ JCB， Job Control Block）之后，作業(yè)就進入了后備狀態(tài)。作業(yè)從建立JCB到被作業(yè)調(diào)度程序選中運行，所處的狀態(tài)叫做后備狀態(tài)。 ?運行狀態(tài)： 作業(yè)調(diào)度程序從處于后備狀態(tài)的作業(yè)隊列中按一定的算法選中一個作業(yè)調(diào)入內(nèi)存，并為之建立相應(yīng)的進程后，由于此時的作業(yè)已具有獨立運行的資格，如果處理器空閑，便可立即開始執(zhí)行，稱此時的作業(yè)進入了運行狀態(tài)。 ?完成狀態(tài)： 當(dāng)作業(yè)（進程）運行正常完成或異常結(jié)束時，便自我終止（正常完成），或被迫終止（異常終止），此時作業(yè)便進入完成狀態(tài)。 5． 1． 1 作業(yè)的狀態(tài)及其轉(zhuǎn)換 ?作業(yè)狀態(tài)及其轉(zhuǎn)換如下圖所示： 提交狀態(tài) 后備狀態(tài) 完成狀態(tài) 運行狀態(tài) 5． 1． 2 調(diào)度的層次 ?高級調(diào)度： 高級調(diào)度又稱作業(yè)調(diào)度。作業(yè)調(diào)度程序決定把哪些后備隊列中的作業(yè)調(diào)入內(nèi)存，并為其創(chuàng)建進程，分配必要的資源，最后將所創(chuàng)建的進程插入就緒隊列，以使該作業(yè)的進程獲得競爭處理器的權(quán)利。在批處理系統(tǒng)中或者是操作系統(tǒng)中的批處理部分都配有作業(yè)調(diào)度。 ?中級調(diào)度： 中級調(diào)度又稱交換調(diào)度，它的主要功能是按一定的算法在內(nèi)存和外存之間進行進程對換，其目的是為了使內(nèi)存緊張的情況得以緩解。交換調(diào)度的主要工作是將內(nèi)存中處于阻塞狀態(tài)的某些進程換至外存，騰出內(nèi)存空間以便將外存上已具備運行條件的進程換入內(nèi)存，準(zhǔn)備運行。進程在其整個生命期間可能要經(jīng)歷多次換進換出，在分時系統(tǒng)中常采用交換調(diào)度。 5． 1． 2 調(diào)度的層次 ?低級調(diào)度： 低級調(diào)度又稱進程調(diào)度。其主要任務(wù)是按照某種策略和方法選取一個處于就緒狀態(tài)的進程占用處理器。它決定就緒隊列中哪個進程先獲得處理器，然后再由分派程序執(zhí)行將處理器分配給進程的操作。 5． 1． 3 調(diào)度模型 從上述操作系統(tǒng)的調(diào)度類型可知，雖然操作系統(tǒng)的調(diào)度機制不盡相同，有的操作系統(tǒng)僅設(shè)有低級調(diào)度，有的操作系統(tǒng)則擁有高級調(diào)度和低級調(diào)度，有的操作系統(tǒng)三級調(diào)度一應(yīng)俱全。但是操作系統(tǒng)中的任何一種調(diào)度都涉及進程隊列，因此根據(jù)操作系統(tǒng)的不同性能，一般有三種相應(yīng)的調(diào)度隊列模型。 5． 1． 2 調(diào)度的層次 ?一級調(diào)度隊列模型： 一級調(diào)度模型僅設(shè)置了進程調(diào)度。在這種調(diào)度模型中，用戶輸入的命令和數(shù)據(jù)都直接送入內(nèi)存。操作系統(tǒng)會為每一個作業(yè)建立一個或多個進程，并將它們插入就緒隊列，然后按照時間片輪轉(zhuǎn)方式進行調(diào)度。一級調(diào)度隊列模型如下圖所示： 5． 1． 2 調(diào)度的層次 就緒隊列 阻塞隊列 進程調(diào)度 時間片完 事件發(fā)生 等待事件 交互用戶 進程完成 5． 1． 2 調(diào)度的層次 ?二級調(diào)度隊列模型： 在二級調(diào)度隊列中，不僅有進程調(diào)度，還有作業(yè)調(diào)度。作業(yè)調(diào)度從外存中選擇一批作業(yè)調(diào)入內(nèi)存，為其創(chuàng)建進程并送入就緒隊列。同時，當(dāng)操作系統(tǒng)任務(wù)較多時，阻塞隊列有可能很長。為了提高執(zhí)行效率，通常設(shè)置若干個阻塞隊列，不同隊列對應(yīng)于引起進程阻塞的不同原因。二級調(diào)度隊列模型如下圖所示： 5． 1． 2 調(diào)度的層次 ：： 后備作業(yè)隊列 等待事件 2 阻塞隊列 2 就緒隊列 事件 1發(fā)生 等待事件 1 阻塞隊列 1 時間片完 事件 2發(fā)生 等待事件 n 阻塞隊列 n 事件 n發(fā)生 作業(yè)調(diào)度 進程調(diào)度 ：： 5． 1． 2 調(diào)度的層次 ?三級調(diào)度隊列模型： 三級調(diào)度隊列模型同