謝曉東 劉艷

【摘要】處理機(jī)調(diào)度是操作系統(tǒng)的重要內(nèi)容。然而當(dāng)調(diào)度算法及調(diào)度輸入趨向復(fù)雜時，學(xué)生難以理解相關(guān)內(nèi)容，容易發(fā)生錯誤。本文提出在教學(xué)中不僅需要引入時空圖來反映CPU的使用，還需要引入模擬就緒隊(duì)列來描述進(jìn)程的排隊(duì)情況，以完整地描述操作系統(tǒng)的調(diào)度過程。在教學(xué)實(shí)踐中，該方法發(fā)揮了良好的效果，幫助學(xué)生理解各種調(diào)度算法的具體運(yùn)行方式。

【關(guān)鍵詞】處理機(jī)調(diào)度教學(xué) 模擬調(diào)度算法 模擬就緒隊(duì)列

【中圖分類號】G42 【文獻(xiàn)標(biāo)識碼】A 【文章編號】2095-3089（2018）19-0225-02

一、引言

處理機(jī)調(diào)度是操作系統(tǒng)課程中重要的內(nèi)容。在操作系統(tǒng)發(fā)展歷史上，由于操作系統(tǒng)應(yīng)用目標(biāo)不同，產(chǎn)生了多種大相徑庭的調(diào)度策略和眾多的調(diào)度算法。大部分操作系統(tǒng)教材也都會介紹先來先服務(wù)、短作業(yè)優(yōu)先、時間片輪轉(zhuǎn)調(diào)度、最小松弛度優(yōu)先等經(jīng)典的調(diào)度算法[1-3]。

模擬調(diào)度算法的運(yùn)行過程，觀察算法對CPU的使用情況是理解相關(guān)策略和算法的重要一環(huán)。然而筆者在教學(xué)中發(fā)現(xiàn)，當(dāng)調(diào)度情況趨向復(fù)雜，例如參與調(diào)度進(jìn)程數(shù)目多，調(diào)度算法復(fù)雜，處理機(jī)切換頻繁時，學(xué)生對一些需要深入理解和仔細(xì)辨析的內(nèi)容產(chǎn)生混淆，理解錯誤。從教學(xué)實(shí)踐看，先來先服務(wù)及短作業(yè)優(yōu)先調(diào)度算法比較容易被學(xué)生接受和理解，而時間片輪轉(zhuǎn)調(diào)度和最小松弛度優(yōu)先算法的出錯概率大增。事實(shí)上，部分教材給出的調(diào)度示例結(jié)果也有錯誤。

目前大部分教材一般使用時空圖來分析調(diào)度過程。時空圖主要用來描述CPU運(yùn)行情況，可以觀察并計算各進(jìn)程的周轉(zhuǎn)時間、響應(yīng)時間等重要參數(shù)。然而，時空圖只關(guān)注CPU的運(yùn)行情況，忽視了處理機(jī)調(diào)度中另一重要工作：進(jìn)程/作業(yè)的排隊(duì)過程。這導(dǎo)致學(xué)生在理解調(diào)度算法時的困難，對調(diào)度過程中的復(fù)雜情形不能準(zhǔn)確理解。因此在教學(xué)過程中引入模擬就緒隊(duì)列，并給出就緒隊(duì)列在調(diào)度過程中的變化是非常必要的。

二、模擬就緒隊(duì)列及其應(yīng)用示例

將各時刻就緒隊(duì)列中進(jìn)程按隊(duì)列順序?qū)懗鼍褪悄M就緒隊(duì)列。模擬就緒隊(duì)列可以與時空圖合二為一。圖1給出了用時空圖-模擬就緒隊(duì)列來描述一個簡單的先來先服務(wù)調(diào)度過程的示例。圖中上半部分是時空圖，橫坐標(biāo)為時間軸，縱坐標(biāo)為進(jìn)程，中間短線代表對應(yīng)進(jìn)程占用的CPU時間；圖的下半部分是模擬就緒隊(duì)列，靠近橫坐標(biāo)的進(jìn)程是就緒隊(duì)列的頭，隊(duì)列按順序從上而下書寫；當(dāng)系統(tǒng)發(fā)生調(diào)度事件時，將在對應(yīng)時刻的位置重寫模擬就緒隊(duì)列。使用模擬就緒隊(duì)列可以很好地描述在調(diào)度過程中就緒隊(duì)列的變化情況，結(jié)合時空圖可以完整地呈現(xiàn)整個調(diào)度過程中的細(xì)節(jié)，從而能更好地理解調(diào)度的相關(guān)問題。

表1是教材[2]在P102中給出的一個時間片輪轉(zhuǎn)調(diào)度的例子，該教材沒有用時空圖進(jìn)行演示和說明。請注意表中粗體標(biāo)識的內(nèi)容，即時間片為1的完成時間，該結(jié)果是錯誤的。通過該結(jié)果可以逆推出如圖2的時空圖。然而，從圖中可以看到，進(jìn)程C在時刻2剛到達(dá)系統(tǒng)時就被分配了CPU，而不是根據(jù)FSCS的原則排在就緒隊(duì)列的后面。事實(shí)上，在時刻2之前，進(jìn)程A已經(jīng)排在就緒隊(duì)列的最前面，因而C只能排在A的后面并要等A完成一個時間片之后才會被調(diào)度并獲得CPU的使用權(quán)。類似的錯誤，憑空思考或僅僅通過時空圖是難以發(fā)現(xiàn)和理解，需要引入模擬就緒隊(duì)列以給出清晰的思路。

圖3給出了表一例子正確的時空圖及對應(yīng)的模擬就緒隊(duì)列。從圖中可以很清楚地看到，當(dāng)進(jìn)程C到達(dá)時，就緒隊(duì)列中已經(jīng)有進(jìn)程A了；當(dāng)進(jìn)程B的時間片用盡，從CPU中切換出來時，CPU將被分配給進(jìn)程A而不是C。因此進(jìn)程C的第一次運(yùn)行的開始時間不是如圖2中的時刻2而是時刻3。事實(shí)上，由于時刻2同時發(fā)生了進(jìn)程C到達(dá)和進(jìn)程B被切換兩個事件，這兩個事件的先后會影響就緒隊(duì)列的順序。一般我們約定進(jìn)程到達(dá)事件先于運(yùn)行進(jìn)程退出CPU事件發(fā)生，因此在時刻2-3之間，就緒隊(duì)列的順序是C-B。這個約定細(xì)節(jié)在很多教材中付之闕如。

由于調(diào)度策略的復(fù)雜性和調(diào)度輸入（進(jìn)程到達(dá)時刻及服務(wù)時間）的多變，調(diào)度過程推演的錯誤時有發(fā)生，如教材[1]P94中時間片輪轉(zhuǎn)調(diào)度算法的例子，以及P102中最早松弛度優(yōu)先算法的例子。因此在教學(xué)中引入模擬就緒隊(duì)列是十分必要的。

三、結(jié)語

處理機(jī)調(diào)度是操作系統(tǒng)核心功能之一，是操作系統(tǒng)課程教學(xué)的重要內(nèi)容。現(xiàn)有各類操作系統(tǒng)教材中，處理機(jī)調(diào)度部分重視使用時空圖這一工具來描述和解釋進(jìn)程在CPU中的運(yùn)行和切換過程，而忽視了作為調(diào)度策略實(shí)現(xiàn)的排隊(duì)器的模擬。這導(dǎo)致學(xué)生難以準(zhǔn)確理解調(diào)度的過程，事實(shí)上也使得部分教材在例子中給出了錯誤的答案。

本文提出引入模擬就緒隊(duì)列這一工具，即寫出各時刻系統(tǒng)就緒隊(duì)列中各進(jìn)程序列，以模擬排隊(duì)器在處理機(jī)調(diào)度時的工作狀態(tài)，從而彌補(bǔ)僅使用時空圖帶來的缺失。模擬就緒隊(duì)列的引入可以準(zhǔn)確地理解調(diào)度過程，避免相關(guān)錯誤，在教學(xué)中也取得很好的效果。

參考文獻(xiàn)：

[1]湯小丹，梁紅兵等編著《計算機(jī)操作系統(tǒng)》第四版，西安電子科技大學(xué)出版社2014年5月。

[2]曹先彬，陳香蘭編著《操作系統(tǒng)原理與設(shè)計》機(jī)械工業(yè)出版社2009年9月。

[3]何炎祥，李飛，李寧編著《計算機(jī)操作系統(tǒng)》，清華大學(xué)出版社2004年1月。

作者簡介：

謝曉東（1976年10月-），男，江西省贛州市人，漢族，現(xiàn)任福建省廈門市華僑大學(xué)計算機(jī)學(xué)院講師，博士，研究方向：軟件工程，數(shù)據(jù)庫。