操作系統中常用作業調度算法的分析

梅瑩瑩 韋良芬

摘要：本文把案例教學方法應用在操作系統作業調度算法中，并對常用作業調度算法中的先來先服務調度算法、短作業優先調度算法和最高響應比優先調度算法以案例的形式做了對比，并對這三種算法進行了分析和評價。此教學方法把抽象的內容融入案例中，循序漸進、能夠有效地調動學生的學習積極性和學習的主動性及熱情。

關鍵詞：操作系統;作業調度;最高響應比

中圖分類號：TN402? ? ? ?文獻標識碼：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 引言

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

2 作業調度的主要任務

作業調度就是按一定的算法從后備隊列中選擇一個作業送入內存執行，并在作業完成后處理善后工作的過程。作業調度的工作主要由作業調度程序來完成。作業調度的任務有：

1）記錄進入系統的各個作業情況，作業一旦進入系統，系統即為該作業分配作業控制塊JCB。

2）從后備作業中挑選一些作業投入運行。一般而論，系統中后備狀態作業較多，而在CPU中運行的不能很多，這就要求作業調度程序必須按規定的調度策略來選擇若干作業進入運行狀態。

3）為選中的作業做執行準備。作業從后備狀態進入執行狀態，需要建立相應的進程，分配進程所需的內存資源、外設資源，這些都交給調度程序。

4）善后工作處理。當作業因某種原因退出或執行完畢后，作業調度程序回收作業原先占用的資源，撤銷進程及JCB，并輸出結果。

3 常用作業調度算法

（1）FCFS算法

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

（2）SJF 算法

該算法以作業運行時間為衡量標準，從所有作業中選取一個運行時間最短的作業，優先為它們創建進程和分配資源。

（3）HRRN算法

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

周轉時間=完成時間—提交時間帶權周轉時間=周轉時間/運行時間響應比=（作業等待時間+作業運行時間）/作業運行時間=1+作業的等待時間/作業運行時間

4 三種算法案例對比

假設在單CPU環境下，作業提交時間及運行時間情況如下表所示：

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

（1） FCFS算法作業執行情況

[作業號 提交時間 運行時間（h） 開始時間 完成時間 周轉時間（h） 帶權周轉時間 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 平均周轉時間T （2+2.5+2.5+3.0）/4=2.5 平均帶權周轉時間W （1+5/3+5+3）/4≈2.67 ]

當時間在1：00時，僅有作業1運行。當作業1在3：00時刻運行結束，此時，作業2、3、4全部到達內存，按照先來后到的原則，所以作業的運行次序為1、2、3、4。

（2） SJF算法執行情況

[作業號 提交時間 運行時間（h） 開始時間 完成時間 周轉時間（h） 帶權周轉時間 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 平均周轉時間T （2+4+1+1.5）/4=2.125 平均帶權周轉時間W （1+8/3+2+1.5）/4≈1.79 ]

當時間在1：00時，僅有作業1運行。當作業1在3：00時刻運行結束，此時，作業2、3、4全部到達內存，按照短作業優先調度算法，由于作業3的運行時間最短，所以優先運行作業3，然后運行作業4和作業2。所以作業的運行次序為1、3、4、2。

（3） HRRN算法執行情況

5 三種算法性能評價

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

2）同FCFS算法相比，SJF算法也易于實現，強調了資源的充分利用，保證了系統的最大吞吐量（單位時間里處理作業的個數），具有較短的平均周轉時間和平均帶權周轉時間。但該算法對長作業不利，長作業往往得不到及時處理。

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

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

（2）當作業估計運行時間相同時，作業的優先權決定于其等待時間，因而實現了先來先服務;

（3）對于長作業，當其等待時間足夠長時，其優先權便可升到很高，從而也可獲得處理機，從而也避免了長作業長期等待這種現象的發生。

但HRRN算法每次都要計算作業的響應比，所以增大了系統的開銷。

6 結語

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

參考文獻：

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

[2]張堯學，史美林.計算機操作系統教程[M].北京：清華大學出版社，1993：83-87.

[3] 湯敏麗.? “互聯網+”環境下的《操作系統》課程教學改革探索——以凱里學院為例[J]. 凱里學院學報，2017（06）.

[4] 余久久.? 基于MOOC的“軟件工程”自主學習系統的設計與實現[J].西昌學院學報（自然科學版），2016（04）.

【通聯編輯：王力】