操作系統(tǒng)中常用作業(yè)調(diào)度算法的分析

梅瑩瑩 韋良芬

摘要：本文把案例教學(xué)方法應(yīng)用在操作系統(tǒng)作業(yè)調(diào)度算法中，并對常用作業(yè)調(diào)度算法中的先來先服務(wù)調(diào)度算法、短作業(yè)優(yōu)先調(diào)度算法和最高響應(yīng)比優(yōu)先調(diào)度算法以案例的形式做了對比，并對這三種算法進(jìn)行了分析和評價。此教學(xué)方法把抽象的內(nèi)容融入案例中，循序漸進(jìn)、能夠有效地調(diào)動學(xué)生的學(xué)習(xí)積極性和學(xué)習(xí)的主動性及熱情。

關(guān)鍵詞：操作系統(tǒng);作業(yè)調(diào)度;最高響應(yīng)比

中圖分類號：TN402? ? ? ?文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2019）18-0269-02

Abstract： This paper applies the case teaching method to the operating system job scheduling algorithm， and compares the first-come-first service scheduling algorithm， the short job priority scheduling algorithm and the highest response ratio priority scheduling algorithm in the common job scheduling algorithm. And the three algorithms were analyzed and evaluated. This teaching method integrates the abstract content into the case， step by step， and can effectively mobilize the students' enthusiasm for learning and the initiative and enthusiasm of learning.

Key words： operating system; job scheduling; highest response ratio

1 引言

“操作系統(tǒng)”這門課程屬于理論性強(qiáng)，十分抽象，知識點瑣碎，不好理解的一門計算機(jī)專業(yè)的專業(yè)課程。學(xué)生學(xué)習(xí)起來枯燥，老師講解也增加了難度。如何提高學(xué)生的學(xué)習(xí)興趣，激發(fā)學(xué)生的學(xué)習(xí)熱情，使學(xué)生能更好地掌握這門課程成為各大學(xué)校老師們關(guān)注的問題。本文以案例的方式講授作業(yè)調(diào)度，使學(xué)生能夠直觀的理解作業(yè)調(diào)度算法。常見的作業(yè)調(diào)度算法有：先來先服務(wù)調(diào)度算法（FCFS）、多作業(yè)優(yōu)先調(diào)度算法（SJF）和最高響應(yīng)比優(yōu)先調(diào)度算法（HRRN）。

2 作業(yè)調(diào)度的主要任務(wù)

作業(yè)調(diào)度就是按一定的算法從后備隊列中選擇一個作業(yè)送入內(nèi)存執(zhí)行，并在作業(yè)完成后處理善后工作的過程。作業(yè)調(diào)度的工作主要由作業(yè)調(diào)度程序來完成。作業(yè)調(diào)度的任務(wù)有：

1）記錄進(jìn)入系統(tǒng)的各個作業(yè)情況，作業(yè)一旦進(jìn)入系統(tǒng)，系統(tǒng)即為該作業(yè)分配作業(yè)控制塊JCB。

2）從后備作業(yè)中挑選一些作業(yè)投入運行。一般而論，系統(tǒng)中后備狀態(tài)作業(yè)較多，而在CPU中運行的不能很多，這就要求作業(yè)調(diào)度程序必須按規(guī)定的調(diào)度策略來選擇若干作業(yè)進(jìn)入運行狀態(tài)。

3）為選中的作業(yè)做執(zhí)行準(zhǔn)備。作業(yè)從后備狀態(tài)進(jìn)入執(zhí)行狀態(tài)，需要建立相應(yīng)的進(jìn)程，分配進(jìn)程所需的內(nèi)存資源、外設(shè)資源，這些都交給調(diào)度程序。

4）善后工作處理。當(dāng)作業(yè)因某種原因退出或執(zhí)行完畢后，作業(yè)調(diào)度程序回收作業(yè)原先占用的資源，撤銷進(jìn)程及JCB，并輸出結(jié)果。

3 常用作業(yè)調(diào)度算法

（1）FCFS算法

FCFS是最簡單的調(diào)度算法，每次從就緒的隊列中選擇一個最先進(jìn)入該隊列的進(jìn)程，分配處理機(jī)，運行進(jìn)程。該進(jìn)程直到運行完成或者阻塞，才讓出處理機(jī)為其他進(jìn)程服務(wù)。

（2）SJF 算法

該算法以作業(yè)運行時間為衡量標(biāo)準(zhǔn)，從所有作業(yè)中選取一個運行時間最短的作業(yè)，優(yōu)先為它們創(chuàng)建進(jìn)程和分配資源。

（3）HRRN算法

HRRN算法是FCFS和SJF的結(jié)合，克服了兩種算法的缺點，該算法既考慮了作業(yè)的等待時間，又考慮了作業(yè)的運行時間。

周轉(zhuǎn)時間=完成時間—提交時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/運行時間響應(yīng)比=（作業(yè)等待時間+作業(yè)運行時間）/作業(yè)運行時間=1+作業(yè)的等待時間/作業(yè)運行時間

4 三種算法案例對比

假設(shè)在單CPU環(huán)境下，作業(yè)提交時間及運行時間情況如下表所示：

[作業(yè)號 提交時間 運行時間（h） J1 1：00 2 J2 2：00 1.5 J3 2：30 0.5 J4 3：00 1 ]

（1） FCFS算法作業(yè)執(zhí)行情況

[作業(yè)號 提交時間 運行時間（h） 開始時間 完成時間 周轉(zhuǎn)時間（h） 帶權(quán)周轉(zhuǎn)時間 J1 1：00 2.0 1：00 3：00 2 1 J2 2：00 1.5 3：00 4：30 2.5 5/3 J3 2：30 0.5 4：30 5：00 2.5 5 J4 3：00 1.0 5：00 6：00 3.0 3 運行先后次序 1 2 3 4 平均周轉(zhuǎn)時間T （2+2.5+2.5+3.0）/4=2.5 平均帶權(quán)周轉(zhuǎn)時間W （1+5/3+5+3）/4≈2.67 ]

當(dāng)時間在1：00時，僅有作業(yè)1運行。當(dāng)作業(yè)1在3：00時刻運行結(jié)束，此時，作業(yè)2、3、4全部到達(dá)內(nèi)存，按照先來后到的原則，所以作業(yè)的運行次序為1、2、3、4。

（2） SJF算法執(zhí)行情況

[作業(yè)號 提交時間 運行時間（h） 開始時間 完成時間 周轉(zhuǎn)時間（h） 帶權(quán)周轉(zhuǎn)時間 J1 1：00 2.0 1：00 3：00 2 1 J2 2：00 1.5 4：30 6：00 4 8/3 J3 2：30 0.5 3：00 3：30 1 2 J4 3：00 1.0 3：30 4：30 1.5 1.5 運行先后次序 1 3 4 2 平均周轉(zhuǎn)時間T （2+4+1+1.5）/4=2.125 平均帶權(quán)周轉(zhuǎn)時間W （1+8/3+2+1.5）/4≈1.79 ]

當(dāng)時間在1：00時，僅有作業(yè)1運行。當(dāng)作業(yè)1在3：00時刻運行結(jié)束，此時，作業(yè)2、3、4全部到達(dá)內(nèi)存，按照短作業(yè)優(yōu)先調(diào)度算法，由于作業(yè)3的運行時間最短，所以優(yōu)先運行作業(yè)3，然后運行作業(yè)4和作業(yè)2。所以作業(yè)的運行次序為1、3、4、2。

（3） HRRN算法執(zhí)行情況

5 三種算法性能評價

1）從實例分析來看FCFS算法，實現(xiàn)較為簡單，但是只考慮了長作業(yè)，沒有考慮短作業(yè)，此算法不利于短作業(yè)的運行。

2）同F(xiàn)CFS算法相比，SJF算法也易于實現(xiàn)，強(qiáng)調(diào)了資源的充分利用，保證了系統(tǒng)的最大吞吐量（單位時間里處理作業(yè)的個數(shù)），具有較短的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。但該算法對長作業(yè)不利，長作業(yè)往往得不到及時處理。

3）HRRN算法結(jié)合了FCFS算法和SJF算法，相對公平，系統(tǒng)的吞吐率增大。從實例中可以看出：

（1）如果作業(yè)的等待時間相同，則作業(yè)估計運行的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè);

（2）當(dāng)作業(yè)估計運行時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，因而實現(xiàn)了先來先服務(wù);

（3）對于長作業(yè)，當(dāng)其等待時間足夠長時，其優(yōu)先權(quán)便可升到很高，從而也可獲得處理機(jī)，從而也避免了長作業(yè)長期等待這種現(xiàn)象的發(fā)生。

但HRRN算法每次都要計算作業(yè)的響應(yīng)比，所以增大了系統(tǒng)的開銷。

6 結(jié)語

對于講授操作系統(tǒng)課程的老師來說，這種講授方法言簡意賅，對于操作系統(tǒng)的學(xué)習(xí)者來說，采用案例的方式，把抽象的內(nèi)容融入案例中，循序漸進(jìn)、調(diào)動學(xué)生的學(xué)習(xí)積極性和學(xué)習(xí)的主動性及熱情，實踐表明此方法教學(xué)效果良好，深得學(xué)生好評。

參考文獻(xiàn)：

[1]湯小丹等.計算機(jī)操作系統(tǒng)（第4版）[M].西安：西安電子科技大學(xué)出版社，2014：95-98.

[2]張堯?qū)W，史美林.計算機(jī)操作系統(tǒng)教程[M].北京：清華大學(xué)出版社，1993：83-87.

[3] 湯敏麗.? “互聯(lián)網(wǎng)+”環(huán)境下的《操作系統(tǒng)》課程教學(xué)改革探索——以凱里學(xué)院為例[J]. 凱里學(xué)院學(xué)報，2017（06）.

[4] 余久久.? 基于MOOC的“軟件工程”自主學(xué)習(xí)系統(tǒng)的設(shè)計與實現(xiàn)[J].西昌學(xué)院學(xué)報（自然科學(xué)版），2016（04）.

【通聯(lián)編輯：王力】