關(guān)于作業(yè)調(diào)度算法

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

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

3、源能得滿足的作業(yè)。其作業(yè)執(zhí)行時(shí)間圖如下：作業(yè)作業(yè)3作業(yè)2作業(yè)100.41.08.09.013.0時(shí)間作業(yè)提交時(shí)間各作業(yè)陸續(xù)完成時(shí)間由于作業(yè)1，2，3是依次到來的，所以當(dāng)開始時(shí)系統(tǒng)中只有作業(yè)1,于是作業(yè)1先被選中。在8.0時(shí)刻，作業(yè)1運(yùn)行完成，這時(shí)系統(tǒng)中有兩道作業(yè)在等待調(diào)度，作業(yè)2和作業(yè)3，按照短作業(yè)優(yōu)先調(diào)度算法，作業(yè)3只要運(yùn)行1個(gè)時(shí)間單位，而作業(yè)2要運(yùn)行4個(gè)時(shí)間單位，于是作業(yè)3被優(yōu)先選中，所以作業(yè)3先運(yùn)行。待作業(yè)3運(yùn)行完畢，最后運(yùn)行作業(yè)2。作業(yè)調(diào)度的次序是1，3，2。另外，要記住以下公式：作業(yè)i的周轉(zhuǎn)時(shí)間耳=作業(yè)完成時(shí)間一作業(yè)提交時(shí)間系統(tǒng)中n個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間T二（YT）x1，其中Ti為作業(yè)

4、i的周轉(zhuǎn)時(shí)間。i=1in解：采用先來先服務(wù)調(diào)度策略，則調(diào)度次序?yàn)?、2、3。作業(yè)號提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間10.08.00.08.08.020.44.08.012.011.631.01.012.013.012.0平均周轉(zhuǎn)時(shí)間T=(8+11.6+12)/3=10.53采用短作業(yè)優(yōu)先調(diào)度策略，則調(diào)度次序?yàn)?、3、2。作業(yè)號提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間10.08.00.08.08.031.01.08.09.08.020.44.09.013.012.6平均周轉(zhuǎn)時(shí)間T=(8+8+12.6)/3=9.53思考題1請同學(xué)們判斷這句話：作業(yè)一旦被作業(yè)調(diào)度程序選中，即占有了CPU。(

5、)提示：需要清楚作業(yè)調(diào)度和進(jìn)程調(diào)度的區(qū)別?！纠?】在一個(gè)單道的程序設(shè)計(jì)系統(tǒng)中，有3個(gè)作業(yè)JI、J2、J3,它們到達(dá)輸入井的時(shí)間分別為8：50、9：00、9：30，它們需要執(zhí)行的時(shí)間分別為1.5小時(shí)、0.4小時(shí)、1小時(shí)。系統(tǒng)在10：00按響應(yīng)比高者優(yōu)先算法對它們進(jìn)行調(diào)度，請回答：作業(yè)被選中執(zhí)行的次序是什么？三個(gè)作業(yè)被選中時(shí)的響應(yīng)比分別是多少？分析響應(yīng)比二作業(yè)周轉(zhuǎn)時(shí)間/作業(yè)運(yùn)行時(shí)間=1+作業(yè)等待時(shí)間/作業(yè)運(yùn)行時(shí)間系統(tǒng)在10：00，計(jì)算作業(yè)的響應(yīng)比：以J1為例，它的作業(yè)計(jì)算時(shí)間是1.5小時(shí)，即90分鐘；J1從8：50到達(dá)輸入井，在10：00時(shí)刻，J1的等待時(shí)間為70分鐘，因此作業(yè)J1的響應(yīng)比為：1+

6、70分鐘/90分鐘=1.77同理，J2：1+60分鐘/24分鐘=3.5J3：1+30分鐘/60分鐘=1.5因此按照響應(yīng)比高者優(yōu)先算法，優(yōu)先調(diào)度J2。在10：24，J2完成。這時(shí)計(jì)算J1、J3的響應(yīng)比：J1：1+(70+24)分鐘/90分鐘=2.04J3：1+(30+24)分鐘/60分鐘=1.9按照響應(yīng)比高者優(yōu)先算法，優(yōu)先調(diào)度J1。在11：54，J1完成，系統(tǒng)調(diào)度J3，J3的響應(yīng)比為1+(30+24+90)分鐘/60分鐘=3.4因此，作業(yè)被選中執(zhí)行的次序是J2、J1、J3。三個(gè)作業(yè)被選中時(shí)的響應(yīng)比分別是：J1，2.04；J2，3.5；J3，3.4。解：作業(yè)被選中執(zhí)行的次序是J2、J1、J3。三個(gè)

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

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