黃祖賢

中南大學(xué)信息科學(xué)與工程學(xué)院，湖南長(zhǎng)沙，410083

常用進(jìn)程調(diào)度算法的模擬實(shí)現(xiàn)

黃祖賢

中南大學(xué)信息科學(xué)與工程學(xué)院，湖南長(zhǎng)沙，410083

在多道程序系統(tǒng)中，有多個(gè)進(jìn)程存在于主存中且其數(shù)目一般多于處理機(jī)數(shù)目，這會(huì)導(dǎo)致它們互相爭(zhēng)奪處理機(jī)。為了解決這一問題，需要采取合適的進(jìn)程調(diào)度策略，常見的進(jìn)程調(diào)度方法有時(shí)間片輪轉(zhuǎn)算法、最高優(yōu)先權(quán)優(yōu)先算法和短作業(yè)(進(jìn)程)優(yōu)先算法等。采用Java語言用良好清晰的界面對(duì)上述三種進(jìn)程調(diào)度算法進(jìn)行模擬實(shí)現(xiàn)，加深對(duì)進(jìn)程調(diào)度策略的理解，有利于進(jìn)一步的研究與應(yīng)用。

進(jìn)程管理;進(jìn)程調(diào)度;時(shí)間片輪轉(zhuǎn);優(yōu)先權(quán);短作業(yè)優(yōu)先；Java

1 問題的提出

操作系統(tǒng)中，進(jìn)程管理十分重要。如何有效管理、合理調(diào)度進(jìn)程資源，對(duì)提升系統(tǒng)性能，提高進(jìn)程的運(yùn)行效率顯得尤為重要。進(jìn)程調(diào)度的核心問題就是采用什么樣的算法把處理機(jī)分配給進(jìn)程，好的算法可以提高資源利用率，減少處理機(jī)的空閑時(shí)間，避免有些作業(yè)或進(jìn)程長(zhǎng)期得不到響應(yīng)的情況發(fā)生[1]。本文介紹了進(jìn)程調(diào)度中的一些基本策略，并基于Java語言對(duì)其進(jìn)行了實(shí)現(xiàn)。

2 進(jìn)程調(diào)度算法

在操作系統(tǒng)中，調(diào)度的實(shí)質(zhì)是一種資源分配。調(diào)度算法是指根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法[2]。對(duì)于不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法[3]。進(jìn)程調(diào)度是系統(tǒng)內(nèi)部的低級(jí)調(diào)度[4]。常見的進(jìn)程調(diào)度算法有先來先服務(wù)算法、最高優(yōu)先權(quán)優(yōu)先算法、時(shí)間片輪轉(zhuǎn)算法、短進(jìn)程(作業(yè))優(yōu)先調(diào)度算法等。

3 進(jìn)程調(diào)度的模擬設(shè)計(jì)

3.1 設(shè)計(jì)思想

在本設(shè)計(jì)中，用良好清晰的界面向用戶展示了進(jìn)程調(diào)度算法中的時(shí)間片輪轉(zhuǎn)算法、最高優(yōu)先權(quán)優(yōu)先算法和短作業(yè)優(yōu)先調(diào)度算法。在最終實(shí)現(xiàn)的成果中，用戶可輸入需要模擬的進(jìn)程名，到達(dá)時(shí)間和進(jìn)程的執(zhí)行時(shí)間、優(yōu)先級(jí)、需求內(nèi)存大小等信息，并且選擇需要演示的算法，算法演示界面將會(huì)顯示進(jìn)程調(diào)度的運(yùn)行結(jié)果。通過此進(jìn)程調(diào)度模擬程序，可以對(duì)上述的三種算法有進(jìn)一步的了解。

3.2 調(diào)度算法

設(shè)計(jì)程序模擬三種進(jìn)程調(diào)度算法：時(shí)間片輪轉(zhuǎn)算法、最高優(yōu)先級(jí)優(yōu)先算法(非搶占式)和短作業(yè)(進(jìn)程)優(yōu)先算法。

3.2.1 時(shí)間片輪轉(zhuǎn)算法

將所有的就緒進(jìn)程按照優(yōu)先權(quán)優(yōu)先、先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，調(diào)度程序?qū)⑼Ｖ乖撨M(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。

3.2.2 最高優(yōu)先級(jí)優(yōu)先算法(非搶占式)

在就緒進(jìn)程隊(duì)列中選取優(yōu)先級(jí)最高的執(zhí)行，相同優(yōu)先級(jí)按照先來先服務(wù)原則進(jìn)行選取，進(jìn)程開始后不可被搶占。

3.2.3 短作業(yè)(進(jìn)程)優(yōu)先算法

從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成。

3.3 功能模塊

3.3.1 進(jìn)程狀態(tài)轉(zhuǎn)換關(guān)系

進(jìn)程狀態(tài)的轉(zhuǎn)換通常有以下幾種情況(圖1)：(1)創(chuàng)建進(jìn)程→就緒狀態(tài)；(2)就緒→執(zhí)行：就緒進(jìn)程被進(jìn)程調(diào)度程序選中，投入到CPU中執(zhí)行；(3)執(zhí)行→就緒：在分時(shí)系統(tǒng)中，執(zhí)行狀態(tài)進(jìn)程使用的時(shí)間片已經(jīng)用完時(shí)，退出CPU而進(jìn)入就緒態(tài)，等待下次被進(jìn)程調(diào)度選中進(jìn)入CPU執(zhí)行；(4)執(zhí)行狀態(tài)→進(jìn)程結(jié)束。

圖1 進(jìn)程狀態(tài)轉(zhuǎn)換關(guān)系圖

3.3.2 進(jìn)程(Process)信息

主要負(fù)責(zé)保存進(jìn)程的基本信息，如進(jìn)程名、進(jìn)程要求運(yùn)行時(shí)間、進(jìn)程到達(dá)就緒隊(duì)列時(shí)間和進(jìn)程需求內(nèi)存大小等。

3.3.3 進(jìn)程控制塊(PCB)信息

主要負(fù)責(zé)保存包括進(jìn)程信息的進(jìn)程調(diào)度的基本信息，如進(jìn)程優(yōu)先級(jí)、進(jìn)程開始運(yùn)行時(shí)間、進(jìn)程運(yùn)行結(jié)束時(shí)間和已經(jīng)運(yùn)行的時(shí)間等。提供外部狀態(tài)設(shè)置和讀取接口。

3.3.4 進(jìn)程隊(duì)列(SchduleTask)類

主要負(fù)責(zé)保存進(jìn)程創(chuàng)建隊(duì)列信息、完成隊(duì)列信息和進(jìn)程總數(shù)。提供獲取隊(duì)列數(shù)據(jù)和調(diào)度進(jìn)程的接口。

3.3.5 調(diào)度(Algorithm)類

(1)向就緒隊(duì)列添加新創(chuàng)建進(jìn)程；(2)從就緒隊(duì)列取相應(yīng)進(jìn)程執(zhí)行；(3)執(zhí)行完進(jìn)程放入完成隊(duì)列；(4)提供獲取執(zhí)行狀態(tài)的外部接口，即各個(gè)隊(duì)列數(shù)據(jù)的獲取。

3.3.6 視圖類

(1)提供用戶操作接口(調(diào)度策略選擇、進(jìn)程創(chuàng)建)；(2)顯示各隊(duì)列、進(jìn)程狀態(tài)信息；(3)創(chuàng)建進(jìn)程調(diào)度類線程，調(diào)用調(diào)度類的接口。

3.4 類與算法設(shè)計(jì)

依據(jù)3.3.1節(jié)進(jìn)程狀態(tài)的轉(zhuǎn)換關(guān)系，可以制定進(jìn)程調(diào)度框架，具體實(shí)現(xiàn)流程如下圖2所示。

圖2 進(jìn)程調(diào)度框架

3.4.1 類圖

本設(shè)計(jì)采用Java語言對(duì)三種進(jìn)程調(diào)度算法進(jìn)行模擬與實(shí)現(xiàn)。利用Java語言面向?qū)ο蟮奶攸c(diǎn)，結(jié)合3.3節(jié)功能模塊的介紹與分析，設(shè)計(jì)類結(jié)構(gòu)關(guān)系如圖3所示，其中SPF、FPF、RR分別是短作業(yè)優(yōu)先算法類、最高優(yōu)先權(quán)算法類和時(shí)間片輪轉(zhuǎn)算法類。

圖3 類結(jié)構(gòu)設(shè)計(jì)

3.4.2 算法設(shè)計(jì)

(1)allArrivedProcess()函數(shù)。allArrivedProcess()函數(shù)返回所有已經(jīng)到達(dá)的進(jìn)程的集合，并將其加入就緒隊(duì)列，它是抽象類Algorithm定義的方法。該函數(shù)只有一個(gè)參數(shù)，是PCB進(jìn)程隊(duì)列(用戶初始化的進(jìn)程隊(duì)列_comingQueue)。該類的成員變量_totalRunTime記錄系統(tǒng)當(dāng)前進(jìn)程調(diào)度的總運(yùn)行時(shí)間，則參數(shù)PCB進(jìn)程隊(duì)列中的進(jìn)程加入到達(dá)(就緒)隊(duì)列有以下兩種情況：①若存在到達(dá)時(shí)間小于_totalRunTime的進(jìn)程，則將這些進(jìn)程全部加入到到達(dá)隊(duì)列當(dāng)中；②如果所有的進(jìn)程的到達(dá)時(shí)間都比_totalRunTime時(shí)間大，則選取與_totalRunTime絕對(duì)值相差最小的進(jìn)程的集合加入到達(dá)隊(duì)列。若有多個(gè)進(jìn)程的到達(dá)時(shí)間相同，則將其全部添加到到達(dá)隊(duì)列。將上述到達(dá)進(jìn)程添加至就緒隊(duì)列，并將該隊(duì)列從參數(shù)隊(duì)列中移除。

(2)schdule()函數(shù)。schdule()函數(shù)調(diào)度所有進(jìn)程，它同樣是抽象類Algorithm定義的方法。該函數(shù)只有一個(gè)參數(shù)，是SchduleTask類的對(duì)象，依據(jù)該對(duì)象中記錄的_comingQueue和_finishQueue跟蹤系統(tǒng)進(jìn)行進(jìn)程調(diào)度的情況。

(3)run()函數(shù)。run()函數(shù)執(zhí)行被調(diào)度的進(jìn)程，它是抽象類Algorithm定義的抽象方法。該方法與使用的調(diào)度算法有關(guān)，在其算法子類RR、SPF、FPF中提供具體實(shí)現(xiàn)。

(4)chooseProcess()函數(shù)。chooseProcess()函數(shù)從就緒隊(duì)列中選擇一個(gè)進(jìn)程調(diào)度執(zhí)行，它同樣是抽象類Algorithm定義的抽象方法，它只有一個(gè)參數(shù)，是PCB進(jìn)程隊(duì)列(就緒隊(duì)列)。該方法與使用的調(diào)度算法有關(guān)，在其算法子類RR、SPF、FPF中提供具體實(shí)現(xiàn)。時(shí)間片輪轉(zhuǎn)算法(RR)中，總是選擇就緒隊(duì)列中的第一個(gè)進(jìn)程；最高優(yōu)先權(quán)優(yōu)先算法(FPF)中，總是選擇就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程；短作業(yè)(進(jìn)程)優(yōu)先算法(SPF)中，總是選擇就緒隊(duì)列中作業(yè)(進(jìn)程)要求運(yùn)行時(shí)間最短的作業(yè)(進(jìn)程)。

3.5 模擬結(jié)果

采用Java語言對(duì)三種進(jìn)程調(diào)度算法進(jìn)行模擬的結(jié)果如圖4、圖5、圖6、圖7所示。其中，圖4顯示的是用戶初始化的進(jìn)程信息列表，用戶需要自定義進(jìn)程名、進(jìn)程到達(dá)時(shí)間、進(jìn)程運(yùn)行時(shí)間和進(jìn)程優(yōu)先級(jí)等。圖5顯示的是選擇時(shí)間片輪轉(zhuǎn)算法進(jìn)行進(jìn)程調(diào)度的運(yùn)行結(jié)果，展示了在時(shí)間片輪轉(zhuǎn)算法下，進(jìn)程調(diào)度的開始時(shí)間、完成時(shí)間、周轉(zhuǎn)時(shí)間以及帶權(quán)周轉(zhuǎn)時(shí)間等信息。圖6、圖7分別顯示了在最高優(yōu)先權(quán)優(yōu)先算法和短作業(yè)優(yōu)先算法下，進(jìn)程調(diào)度的開始時(shí)間、完成時(shí)間、周轉(zhuǎn)時(shí)間以及帶權(quán)周轉(zhuǎn)時(shí)間等信息。

圖4 初始化進(jìn)程信息

圖5 時(shí)間片輪轉(zhuǎn)算法模擬結(jié)果

圖6 最高優(yōu)先權(quán)優(yōu)先算法模擬結(jié)果

圖7 短作業(yè)(進(jìn)程)優(yōu)先算法模擬結(jié)果

4 結(jié) 論

通過對(duì)進(jìn)程調(diào)度策略中時(shí)間片輪轉(zhuǎn)算法、最高優(yōu)先權(quán)優(yōu)先算法以及短作業(yè)(進(jìn)程)優(yōu)先算法的模擬實(shí)現(xiàn)，有利于加深對(duì)操作系統(tǒng)中進(jìn)程的管理與應(yīng)用?？梢赃M(jìn)一步對(duì)其他的進(jìn)程調(diào)度、管理策略進(jìn)行模擬實(shí)現(xiàn)，進(jìn)一步拓展模擬進(jìn)程調(diào)度過程中的內(nèi)存分配情況等，把握系統(tǒng)需求，提高系統(tǒng)性能。

[1]郜瑜.進(jìn)程調(diào)度算法模擬實(shí)現(xiàn)與性能分析[J].科技情報(bào)開發(fā)與經(jīng)濟(jì),2007,17(1):227-230

[2]湯小丹.計(jì)算機(jī)操作系統(tǒng)[M].3版.西安:西安電子科技大學(xué)出版社,2007:91

[3]田露飛.常見進(jìn)程調(diào)度算法的比較與改進(jìn)[J].計(jì)算機(jī)光盤軟件與應(yīng)用,2014(16):46-47

[4]王俊祥.常用進(jìn)程調(diào)度算法的分析與評(píng)價(jià)[J].計(jì)算機(jī)與信息技術(shù),2006(8):74-76

(責(zé)任編輯：汪材印)

10.3969/j.issn.1673-2006.2015.08.028

2015-04-18

黃祖賢(1993-)， 女，安徽馬鞍山人，主要研究方向：計(jì)算機(jī)科學(xué)與技術(shù)。

TP316

A

1673-2006(2015)08-0094-04