1、關于作業調度算法 在計算機操作系統教材中，介紹了作業調度算法和進程調度算法。其中作業調度算法主要有先來先服務法FCFS、短作業優先法SJF、最高響應比優先法HRN、定時輪轉法和優先數法。在進程調度算法中主要介紹了先來先服務法FCFS、輪轉法RR、多級反饋輪轉法和優先數法。 需要指出的是：（1）在作業調度和進程調度中同時出現的算法，如FCFS、RR、優先數法，其使用原理是基本相同的；（2）作業調度算法和進程調度算法應嚴格與存儲管理中的“請求淘汰換頁算法”相區別，注意不要混淆。 調度算法舉例：【例1】下表給出作業l，2，3的提交時間和運行時間。采用先來先服務調度算法和短作業優先調度算法，試問作業調

2、度次序和平均周轉時間各為多少？（時間單位：小時，以十進制進行計算。）作業號提交時間運行時間1230.00.41.08.04.01.0分析 解這樣的題關鍵是要根據系統采用的調度算法，弄清系統中各道作業隨時間的推進情況。我們用一個作業執行時間圖來形象地表示作業的執行情況，幫助我們理解此題。采用先來先服務調度算法，是按照作業提交的先后次序挑選作業，先進入的作業優先被挑選。然后按照“排隊買票”的辦法，依次選擇作業。其作業執行時間圖如下： 作業作業3作業2作業1 0 0.4 1.0 8.0 12.0 13.0 時間 作業提交時間 各作業陸續完成時間采用短作業優先調度算法，作業調度時根據作業的運行時間，優

3、先選擇計算時間短且資源能得滿足的作業。其作業執行時間圖如下： 作業作業3作業2作業1 0 0.4 1.0 8.0 9.0 13.0 時間 作業提交時間 各作業陸續完成時間 由于作業1，2，3是依次到來的，所以當開始時系統中只有作業1，于是作業1先被選中。在8.0時刻，作業1運行完成，這時系統中有兩道作業在等待調度，作業2和作業3，按照短作業優先調度算法，作業3只要運行1個時間單位，而作業2要運行4個時間單位，于是作業3被優先選中，所以作業3先運行。待作業3運行完畢，最后運行作業2。作業調度的次序是1，3，2。另外，要記住以下公式：作業i的周轉時間Ti作業完成時間作業提交時間 系統中n個作業的平

4、均周轉時間，其中Ti為作業i的周轉時間。解：采用先來先服務調度策略，則調度次序為l、2、3。作業號提交時間 運行時間 開始時間 完成時間周轉時間1 0.08.00.08.0 8.02 0.44.08.0 12.0 11.63 1.01.0 12.0 13.0 12.0平均周轉時間T（811.612）/310.53采用短作業優先調度策略，則調度次序為l、3、2。作業號提交時間運行時間開始時間完成時間周轉時間1 0.0 8.0 0.0 8.0 8.03 1.0 1.08.09.08.02 0.4 4.0 9.0 13.0 12.6平均周轉時間T（8812.6）/39.53思考題1請同學們判斷這句話

5、：作業一旦被作業調度程序選中，即占有了CPU。（ ）提示：需要清楚作業調度和進程調度的區別。【例2】在一個單道的程序設計系統中，有3個作業J1、J2、J3，它們到達輸入井的時間分別為8：50、9：00、9：30，它們需要執行的時間分別為1.5小時、0.4小時、1小時。系統在10：00按響應比高者優先算法對它們進行調度，請回答：（1）作業被選中執行的次序是什么？（2）三個作業被選中時的響應比分別是多少？分析 響應比作業周轉時間/作業運行時間 1作業等待時間/作業運行時間系統在10：00，計算作業的響應比：以J1為例，它的作業計算時間是1.5小時，即90分鐘；J1從8：50到達輸入井，在10：00

6、時刻，J1的等待時間為70分鐘，因此作業J1的響應比為：170分鐘/90分鐘=1.77 同理，J2：160分鐘/24分鐘=3.5 J3：130分鐘/60分鐘=1.5 因此按照響應比高者優先算法，優先調度J2。在10：24，J2完成。這時計算J1、J3的響應比：J1：1（7024）分鐘/90分鐘=2.04 J3：1（3024）分鐘/60分鐘=1.9 按照響應比高者優先算法，優先調度J1。在11：54，J1完成，系統調度J3，J3的響應比為1（302490）分鐘/60分鐘=3.4 因此，作業被選中執行的次序是J2、J1、J3。三個作業被選中時的響應比分別是：J1，2.04；J2，3.5；J3，3.

7、4。解：（1）作業被選中執行的次序是J2、J1、J3。（2）三個作業被選中時的響應比分別是：J1，1.04；J2，2.5；J3，2.4。思考題2某作業的提交時間為10：30，需要運行的時間為1小時，假設11：00開始調度，它的響應比是 。【例3】設有進程A、B、C、D依次進入就緒隊列（相隔一個時間單位），它們的優先級（優先數大的優先級較高）如下表所示：進程CPU時間優先數A203B151C84D103試問采用“先來先服務”、“靜態優先數法”調度算法（注：優先數大的優先級高），選中進程的執行次序。解：采用先來先服務調度算法，按照進程進入就緒隊列的先后次序占有CPU，其執行次序是A-B-C-D。采

8、用靜態優先數法，進程A最先就緒，在0時刻先占有CPU運行，隨后1時刻進程B進入就緒隊列，2時刻進程C進入就緒隊列，3時刻進程D進入就緒隊列。由于采用靜態優先數法，不容許隨時間的推移改變進程的優先級，所以當進程A運行結束時，系統的就緒隊列中有B、C、D三個進程，而進程C優先級最高，于是選中C；這樣分析下去，進程的執行次序是A-C-D-B。思考題3時間片輪轉調度算法是為了（ ）。A多個終端都能得到系統的及時響應 B先來先服務C優先級高的進程先使用CPU D緊急事件優先處理參考解答思考題1：錯誤。作業被作業調度程序選中，說明作業處于運行狀態，即該作業進入內存并以進程的形式存在于系統中，但屬于該作業的進程可能處于運行、就緒和等待狀態，只有處于運行狀態的進程才能占有處理機，而其余兩種狀態的進程并不占有處理機。作業調度和進程調度的區別：一個作業從進入系統到最后完成，一般至少要經歷兩級調度：作業調度和進程調度。作業調度是宏觀上的高級調度，它的主要功能是根據一定的算法，從輸入井中選中若干個作業，分配必要的資源，如主存、外設等，為它們建立初始狀態為就緒的作業進程。進程調度是微觀上的低級調度，它的主要功能是根據一定的算法將CPU分派給就緒隊列中的一個進程。一般的操作系統都必須有進