操作系統(tǒng)短作業(yè)優(yōu)先調(diào)度算法

1、課程設(shè)計(jì)采用短作業(yè)優(yōu)先調(diào)度算法調(diào)度程序?qū)W號(hào)：姓名：專業(yè)：指導(dǎo)老師：日期：一、實(shí)驗(yàn)題目3二、課程設(shè)計(jì)的目的3三、設(shè)計(jì)內(nèi)容3四、設(shè)計(jì)要求3五、主要數(shù)據(jù)結(jié)構(gòu)及其說明4六、程序運(yùn)行結(jié)果5七、流程圖7八、源程序文件9九、實(shí)驗(yàn)體會(huì)13十、參考文獻(xiàn)13摘要在多道程序環(huán)境下，主存中有著多個(gè)進(jìn)程，其數(shù)目往往多于處理機(jī)數(shù)目。這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行。分配處理機(jī)的任務(wù)是由處理機(jī)調(diào)度程序完成的。由于處理機(jī)是最重要的計(jì)算機(jī)資源，提高處理機(jī)的利用率及改善系統(tǒng)性能（吞吐量、響應(yīng)時(shí)間），在很大程度上取決于處理機(jī)調(diào)度性能的好壞，因而，處理機(jī)調(diào)度便成為操作系統(tǒng)設(shè)計(jì)的中心問題之一

2、。在多道程序系統(tǒng)中，一個(gè)作業(yè)被提交后必須經(jīng)過處理機(jī)調(diào)度后，方能獲得處理機(jī)執(zhí)行。對(duì)于批量型作業(yè)而言，通常需要經(jīng)歷作業(yè)調(diào)度和進(jìn)程調(diào)度兩個(gè)過程后方能獲得處理機(jī)。作業(yè)調(diào)度是對(duì)成批進(jìn)入系統(tǒng)的用戶作業(yè)，根據(jù)作業(yè)控制塊的信息，按一定的策略選取若干個(gè)作業(yè)使它們可以去獲得處理器運(yùn)行的一項(xiàng)工作。而對(duì)每個(gè)用戶來說總希望自己的作業(yè)的周轉(zhuǎn)時(shí)間是最小的，短作業(yè)優(yōu)先（SJF）便是其中一種調(diào)度方法。本次課程設(shè)計(jì)主要是模擬短作業(yè)優(yōu)先（SJF）調(diào)度算法。采用短作業(yè)優(yōu)先算法的的進(jìn)程調(diào)度程序二、課程設(shè)計(jì)的目的操作系統(tǒng)課程設(shè)計(jì)是計(jì)算機(jī)專業(yè)重要的教學(xué)環(huán)節(jié)，它為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，將課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合一起，獨(dú)立分析和

3、解決實(shí)際問題的機(jī)會(huì)。進(jìn)一步鞏固和復(fù)習(xí)操作系統(tǒng)的基礎(chǔ)知識(shí)。培養(yǎng)學(xué)生結(jié)構(gòu)化程序、模塊化程序設(shè)計(jì)的方法和能力。提高學(xué)生調(diào)試程序的技巧和軟件設(shè)計(jì)的能力。提高學(xué)生分析問題、解決問題以及綜合利用C語言進(jìn)行程序設(shè)計(jì)的能力。三、設(shè)計(jì)內(nèi)容設(shè)計(jì)并實(shí)現(xiàn)一個(gè)采用短作業(yè)優(yōu)先算的進(jìn)程調(diào)度算法演示程序四、設(shè)計(jì)要求1,每一個(gè)進(jìn)程有一個(gè)PCB,其內(nèi)容可以根據(jù)具體情況設(shè)定。2.進(jìn)程數(shù)、進(jìn)入內(nèi)存時(shí)間、要求服務(wù)時(shí)間、優(yōu)先級(jí)等均可以在界面上設(shè)定3,可讀取樣例數(shù)據(jù)（要求存放在外部文件中）進(jìn)行進(jìn)程數(shù)、進(jìn)入內(nèi)存時(shí)間、時(shí)間片長(zhǎng)度、進(jìn)程優(yōu)先級(jí)的初始化4,可以在運(yùn)行中顯示各進(jìn)程的狀態(tài)：就緒、執(zhí)行（由于不要求設(shè)置互斥資源與進(jìn)程間同步關(guān)系，故只有兩種

4、狀態(tài)）5,采用可視化界面，可在進(jìn)程調(diào)度過程中隨時(shí)暫停調(diào)度，查看當(dāng)前進(jìn)程的狀態(tài)以及相應(yīng)的阻塞隊(duì)列五、主要數(shù)據(jù)結(jié)構(gòu)及其說明算法的基本概念和原理：本次課程設(shè)計(jì)主要是采用短作業(yè)優(yōu)先算法進(jìn)程的進(jìn)程調(diào)度過程。短作業(yè)優(yōu)先調(diào)度算法，是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。他們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度，短作業(yè)優(yōu)先的調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將他們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先調(diào)度算法則是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給他，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)再度重新調(diào)度。本程序采用了非搶占式短作業(yè)優(yōu)先調(diào)度。而非搶占式這種方式，

5、一旦把處理機(jī)分配給某進(jìn)程后，便讓該進(jìn)程一直執(zhí)行，直至該進(jìn)程完成或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配給其它進(jìn)程，決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求一一立即執(zhí)行，因而可能造成難以預(yù)料的后果。因此，在要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，不宜采用這種調(diào)度方式。本課程設(shè)計(jì)主要是在滿足要求多道單處理機(jī)的情況下進(jìn)行短作業(yè)的優(yōu)先調(diào)度。算法的簡(jiǎn)要說明：短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法SJ（P）F,是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先（SJF）的調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或

6、若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程（SPF）調(diào)度算法則是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)再重新調(diào)度。優(yōu)點(diǎn)是SJ（P）F調(diào)度算法能有效地降低作業(yè)（進(jìn)程）的平均等待時(shí)間，提高系統(tǒng)吞吐量。缺點(diǎn)是該算法對(duì)長(zhǎng)作業(yè)不利；完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進(jìn)程）長(zhǎng)期不被調(diào)度；由于作業(yè)（進(jìn)程）的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)問，致使該算法不一定能真正做到短作業(yè)游戲那調(diào)度。該程序定義了一個(gè)進(jìn)程數(shù)據(jù)塊（structProce

7、ss_）該數(shù)據(jù)塊有進(jìn)程名（name）、到達(dá)時(shí)間（arrivetime）、服務(wù)時(shí)間（servicetime）、開始執(zhí)行時(shí)間（starttime）、完成時(shí)間（finishtime）、周轉(zhuǎn)時(shí)間（zztime）、帶權(quán)周轉(zhuǎn)時(shí)間（dqzztime）、執(zhí)行順序（order）。用到的公式有：完成時(shí)間=到達(dá)時(shí)間+服務(wù)時(shí)間；周轉(zhuǎn)時(shí)間=完成時(shí)間+到達(dá)時(shí)間；帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間；（第一次執(zhí)行的進(jìn)程的完成時(shí)間二該進(jìn)程的到達(dá)時(shí)間；下一個(gè)進(jìn)程的開始執(zhí)行時(shí)間=上一個(gè)進(jìn)程的完成時(shí)間）。運(yùn)行進(jìn)程的順序需要對(duì)進(jìn)程的到達(dá)時(shí)間和服務(wù)時(shí)間進(jìn)行比較。如果某一進(jìn)程是從0時(shí)刻到達(dá)的，那么首先執(zhí)行該進(jìn)程；之后就比較進(jìn)程的服務(wù)時(shí)間，誰

8、的服務(wù)時(shí)間短就先執(zhí)行誰（如果服務(wù)時(shí)間相同則看它們的到達(dá)時(shí)間，到達(dá)時(shí)間短的先執(zhí)行）；如果到達(dá)時(shí)問和服務(wù)時(shí)間相同，則按先來先服務(wù)算法執(zhí)行。六、程序運(yùn)行結(jié)果1進(jìn)入操作界面如下C:DOCUMEHTS,SETTINGSADIINISTRATOR、桌面LKQzDebugz.exen|x嚕用短作業(yè)優(yōu)先XKK*XKK*XKK*XKK*XKK*XKK*XKK*XKK*XXK*XXK*XXK*XXK*X2輸入進(jìn)程的信息* 1使用短作業(yè)優(yōu)先* 0退出*11111XlllIWlliW11111117X11II1111'111111111111務(wù)進(jìn)程用短作業(yè)優(yōu)先調(diào)度.請(qǐng)輸入進(jìn)程個(gè)數(shù)：53各時(shí)刻進(jìn)程的狀態(tài)函C:D

9、OCUIEKTSAUDSETTISGSADIHriSTRATORffiLSQzDebuEYx1使用短作業(yè)優(yōu)先0退出務(wù)進(jìn)程用短作業(yè)優(yōu)先調(diào)度口請(qǐng)輸入進(jìn)程個(gè)數(shù);5箸輸入到達(dá)時(shí)間:請(qǐng)輸入服務(wù)時(shí)間工4內(nèi)人一T進(jìn)隹:人進(jìn)程名旅、輸入到達(dá)時(shí)間:請(qǐng)輸入服務(wù)時(shí)間:3請(qǐng)輸入到達(dá)時(shí)間:卷輸入服務(wù)時(shí)間:3請(qǐng)輸入到達(dá)時(shí)間=3請(qǐng)輸入服務(wù)時(shí)間:2請(qǐng)掇入一個(gè)進(jìn)程:請(qǐng)輜入進(jìn)程名就e請(qǐng)輸入到達(dá)時(shí)間:請(qǐng)輸入服務(wù)時(shí)間二24進(jìn)程信息匚%"C:DOCU1EHTSAffDSETTIBGSADIINISTRATOR®LXQzDebuEz_exe"進(jìn)程名稱到達(dá)T運(yùn)行T開始運(yùn)行T結(jié)束T執(zhí)行順序周轉(zhuǎn)T0帶權(quán)周轉(zhuǎn)1Q.

10、0000001:a12i313：b2134200.0000004：c3246306.0000006：d4268466.0000008：&43B1150-0.000000average_turn_i»ouind_timcr=3.600000weight_avei*age_tupn_i'ound_time產(chǎn)-L.766667Pressan9keytocontinue.5平均帶權(quán)周轉(zhuǎn)時(shí)間界面Cvei*age_tuvn_Foumd_tiner=J.b/修修bififht_average_turn_round_timer=l.766667七、流程圖本次課程設(shè)計(jì)主要是通過比較各個(gè)

11、進(jìn)程的優(yōu)先級(jí)以及各進(jìn)程所需要占用的CPU寸間來確定哪個(gè)作業(yè)優(yōu)先運(yùn)行，短作業(yè)優(yōu)先調(diào)度算法除了能保證優(yōu)先級(jí)更高的作業(yè)優(yōu)先運(yùn)行外，還能使相同優(yōu)先級(jí)的前提下，所需CPU寸間最短的那個(gè)作業(yè)優(yōu)先運(yùn)行，次外，本次課程設(shè)計(jì)還增加了阻塞時(shí)間和被阻塞時(shí)間來對(duì)個(gè)進(jìn)程的運(yùn)行加以控制。此次課程設(shè)計(jì)的總體流程圖如下：八、源程序文件#include<iostream>#defineMaxNum100usingnamespacestd;structProcess_structintNumber;/進(jìn)程編號(hào)charNameMaxNum;進(jìn)程名稱intArrivalTime;到達(dá)時(shí)間intServiceTime;開始

12、運(yùn)行時(shí)間intFinishTime;運(yùn)行結(jié)束時(shí)間intWholeTime;/運(yùn)行時(shí)間intrun_flag;/調(diào)度標(biāo)志intorder;/運(yùn)行次序doubleWeightWholeTime;/周轉(zhuǎn)時(shí)間doubleAverageWT_FCFS,AverageWT_SJF;/平均周轉(zhuǎn)時(shí)間doubleAverageWWT_FCFS,AverageWWT_SJF;平均帶權(quán)周轉(zhuǎn)時(shí)間ProcessMaxNum;intN;/實(shí)際進(jìn)程個(gè)數(shù)intSJF();/短作業(yè)優(yōu)先intSJF()/短作業(yè)優(yōu)先算法inttemp_time=0;當(dāng)期那時(shí)間inti=0,j;intnumber_schedul,temp_coun

13、ter;/進(jìn)程編號(hào)，當(dāng)前已執(zhí)行進(jìn)程個(gè)數(shù)floatrun_time;run_time=Processi.WholeTime;j=1;while(j<N)&&(Processi.ArrivalTime=Processj.ArrivalTime)判斷是否有兩個(gè)進(jìn)程同時(shí)到達(dá)if(Processj.WholeTime<Processi.WholeTime)run_time=Processi.WholeTime;i=j;j+;/查找下一個(gè)被調(diào)度的進(jìn)程/對(duì)找到的下一個(gè)被調(diào)度的進(jìn)程求相應(yīng)的參數(shù)number_schedul=i;Processnumber_schedul.Servic

14、eTime=Processnumber_schedul.ArrivalTime;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime+Processnumber_schedul.WholeTime;Processnumber_schedul.run_flag=1;temp_time=Processnumber_schedul.FinishTime;Processnumber_schedul.order=1;temp_counter=1;while(temp_counter<N).for(j=0;j<N;

15、j+)if(Processj.ArrivalTime<=temp_time)&&(!Processj.run_flag)run_time=Processj.WholeTime;number_schedul=j;break;for(j=0;j<N;j+)if(Processj.ArrivalTime<=temp_time)&&(!Processj.run_flag)if(Processj.WholeTime<run_time)run_time=Processj.WholeTime;number_schedul=j;/查找下一個(gè)被調(diào)度的進(jìn)程/

16、對(duì)找到的下一個(gè)被調(diào)度的進(jìn)程求相應(yīng)的參數(shù)Processnumber_schedul.ServiceTime=temp_time;Processnumber_schedul.FinishTime=Processnumber_schedul.ServiceTime+Processnumber_schedul.WholeTime;Processnumber_schedul.run_flag=1;temp_time=Processnumber_schedul.FinishTime;temp_counter+;Processnumber_schedul.order=temp_counter;return0

17、;intPinput();/進(jìn)程參數(shù)輸入intPoutput();/調(diào)度結(jié)果輸出voidmain()intoption;printf("*主菜單*n")；printf("1使用短作業(yè)優(yōu)先*n");printf("*n");printf("*n")；/system("cls");system("color1f");scanf("%d",&option);switch(option)case0:printf("運(yùn)行結(jié)束。n");br

18、eak;case1:printf("對(duì)進(jìn)程用短作業(yè)優(yōu)先調(diào)度。nn");Pinput();SJF();Poutput();break;intPinput()/進(jìn)程參數(shù)輸入inti;printf("請(qǐng)輸入進(jìn)程個(gè)數(shù):n");scanf("%d",&N);for(i=0;i<N;i+)printf("*n");printf("請(qǐng)輸入一個(gè)進(jìn)程:n",i+1);printf("請(qǐng)輸入進(jìn)程名稱:n");scanf("%s",Processi.Name);p

19、rintf("請(qǐng)輸入到達(dá)時(shí)間:n");scanf("%d”,&Processi.ArrivalTime);printf("請(qǐng)輸入服務(wù)時(shí)間:n");scanf("%d",&Processi.WholeTime);Processi.ServiceTime=0;Processi.FinishTime=0;Processi.WeightWholeTime=0;Processi.order=0;Processi.run_flag=0;system("cls");return0;intPoutput(

20、)/調(diào)度結(jié)果輸出inti;floatturn_round_time=0,f1,w=0;printf("詡加名稱到達(dá)T運(yùn)行T開始運(yùn)行T結(jié)束T執(zhí)行順序周轉(zhuǎn)T帶權(quán)周轉(zhuǎn)Tn");for(i=0;i<N;i+)Processi.WeightWholeTime=Processi.FinishTime-Processi.ArrivalTime;f1=Processi.WeightWholeTime/Processi.WholeTime;turn_round_time+=Processi.WeightWholeTime;w+=f1;printf("時(shí)亥1J%d:"

21、,Processi.ServiceTime,Processi.Name);printf("%s%d%d%d%d%d%f%fn",Processi.Name,Processi.ArrivalTime,Processi.WholeTime,Processi.ServiceTime,Processi.FinishTime,Processi.order,Processi.WeightWholeTime,f1);printf("average_turn_round_timer=%fn",turn_round_time/N);printf("weight_average_turn_round_timer=%fn",w/N);return0;九、實(shí)驗(yàn)體會(huì)通過本次課程設(shè)計(jì)，使我對(duì)計(jì)算機(jī)操作系統(tǒng)短作業(yè)優(yōu)先調(diào)度算法這一節(jié)的知識(shí)有了更深的了解。短作業(yè)優(yōu)先調(diào)度算法