關于調度算法

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

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

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

4、轉時間，其中Ti為作業(yè)i的周轉時間。解：采用先來先服務調度策略，則調度次序為l、2、3。作業(yè)號提交時間 運行時間 開始時間 完成時間周轉時間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采用短作業(yè)優(yōu)先調度策略，則調度次序為l、3、2。作業(yè)號提交時間運行時間開始時間完成時間周轉時間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、業(yè)一旦被作業(yè)調度程序選中，即占有了CPU。（ ）提示：需要清楚作業(yè)調度和進程調度的區(qū)別。【例2】在一個單道的程序設計系統(tǒng)中，有3個作業(yè)J1、J2、J3，它們到達輸入井的時間分別為8：50、9：00、9：30，它們需要執(zhí)行的時間分別為1.5小時、0.4小時、1小時。系統(tǒng)在10：00按響應比高者優(yōu)先算法對它們進行調度，請回答：（1）作業(yè)被選中執(zhí)行的次序是什么？（2）三個作業(yè)被選中時的響應比分別是多少？分析 響應比作業(yè)周轉時間/作業(yè)運行時間 1作業(yè)等待時間/作業(yè)運行時間系統(tǒng)在10：00，計算作業(yè)的響應比：以J1為例，它的作業(yè)計算時間是1.5小時，即90分鐘；J1從8：50到達輸入井，在10：00時刻

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

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

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