OS短作業(yè)優(yōu)先調(diào)算法C語(yǔ)言

1、 采用短作業(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)及其說(shuō)明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)

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

3、理論知識(shí)和實(shí)際有機(jī)的結(jié)合一起，獨(dú)立分析和解決實(shí)際問(wèn)題的機(jī)會(huì)。l 進(jìn)一步鞏固和復(fù)習(xí)操作系統(tǒng)的基礎(chǔ)知識(shí)。l 培養(yǎng)學(xué)生結(jié)構(gòu)化程序、模塊化程序設(shè)計(jì)的方法和能力。l 提高學(xué)生調(diào)試程序的技巧和軟件設(shè)計(jì)的能力。l 提高學(xué)生分析問(wèn)題、解決問(wèn)題以及綜合利用C語(yǔ)言進(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)程

4、的狀態(tài)：就緒、執(zhí)行 （由于不要求設(shè)置互斥資源與進(jìn)程間同步關(guān)系，故只有兩種狀態(tài)） 5. 采用可視化界面，可在進(jìn)程調(diào)度過(guò)程中隨時(shí)暫停調(diào)度，查看當(dāng)前進(jìn)程的狀態(tài)以及相應(yīng)的阻塞隊(duì)列 五、主要數(shù)據(jù)結(jié)構(gòu)及其說(shuō)明算法的基本概念和原理：本次課程設(shè)計(jì)主要是采用短作業(yè)優(yōu)先算法進(jìn)程的進(jìn)程調(diào)度過(guò)程。短作業(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ā)生某事件而被阻塞放棄

5、處理機(jī)時(shí)再度重新調(diào)度。本程序采用了非搶占式短作業(yè)優(yōu)先調(diào)度。而非搶占式這種方式，一旦把處理機(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)開(kāi)銷小，適用于大多數(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)要說(shuō)明：短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法SJ（P）F，是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于

6、作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先（SJF）的調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或若干個(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ì)有意或無(wú)意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真

7、正做到短作業(yè)游戲那調(diào)度。 該程序定義了一個(gè)進(jìn)程數(shù)據(jù)塊(struct Process_)，該數(shù)據(jù)塊有進(jìn)程名(name)、到達(dá)時(shí)間(arrivetime)、服務(wù)時(shí)間(servicetime)、開(kāi)始執(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)程的開(kāi)始執(zhí)行時(shí)間=上一個(gè)進(jìn)程的完成時(shí)間)。運(yùn)行進(jìn)程的順序需要對(duì)進(jìn)程的到達(dá)時(shí)間和服務(wù)時(shí)間進(jìn)行比較

8、。如果某一進(jìn)程是從0時(shí)刻到達(dá)的，那么首先執(zhí)行該進(jìn)程；之后就比較進(jìn)程的服務(wù)時(shí)間，誰(shuí)的服務(wù)時(shí)間短就先執(zhí)行誰(shuí)（如果服務(wù)時(shí)間相同則看它們的到達(dá)時(shí)間，到達(dá)時(shí)間短的先執(zhí)行）；如果到達(dá)時(shí)間和服務(wù)時(shí)間相同，則按先來(lái)先服務(wù)算法執(zhí)行。六、程序運(yùn)行結(jié)果1 進(jìn)入操作界面如下2輸入進(jìn)程的信息3 各時(shí)刻進(jìn)程的狀態(tài)4 進(jìn)程信息5 平均帶權(quán)周轉(zhuǎn)時(shí)間界面七、流程圖本次課程設(shè)計(jì)主要是通過(guò)比較各個(gè)進(jìn)程的優(yōu)先級(jí)以及各進(jìn)程所需要占用的CPU時(shí)間來(lái)確定哪個(gè)作業(yè)優(yōu)先運(yùn)行，短作業(yè)優(yōu)先調(diào)度算法除了能保證優(yōu)先級(jí)更高的作業(yè)優(yōu)先運(yùn)行外，還能使相同優(yōu)先級(jí)的前提下，所需CPU時(shí)間最短的那個(gè)作業(yè)優(yōu)先運(yùn)行，次外，本次課程設(shè)計(jì)還增加了阻塞時(shí)間和被阻塞時(shí)間來(lái)對(duì)

9、個(gè)進(jìn)程的運(yùn)行加以控制。 此次課程設(shè)計(jì)的總體流程圖如下：開(kāi) 始輸入進(jìn)程的個(gè)數(shù):numr隊(duì)列中是否只有一個(gè)進(jìn)程？執(zhí)行時(shí)間處理函數(shù)：Time()Y 結(jié) 束Sort()輸入進(jìn)程的信息:name starttime servicetimeN執(zhí)行判斷函數(shù)：Run()輸出最后信息：Output()八、源程序文件#include<iostream>#define MaxNum 100using namespace std; struct Process_structint Number; /進(jìn)程編號(hào)char NameMaxNum; /進(jìn)程名稱 int ArrivalTime; /到達(dá)時(shí)間int S

10、erviceTime; /開(kāi)始運(yùn)行時(shí)間int FinishTime; /運(yùn)行結(jié)束時(shí)間int WholeTime; /運(yùn)行時(shí)間 int run_flag; /調(diào)度標(biāo)志int order; /運(yùn)行次序double WeightWholeTime; /周轉(zhuǎn)時(shí)間double AverageWT_FCFS,AverageWT_SJF; /平均周轉(zhuǎn)時(shí)間 double AverageWWT_FCFS,AverageWWT_SJF; /平均帶權(quán)周轉(zhuǎn)時(shí)間ProcessMaxNum;int N; /實(shí)際進(jìn)程個(gè)數(shù)int SJF(); /短作業(yè)優(yōu)先int SJF() /短作業(yè)優(yōu)先算法int temp_time=0;

11、/當(dāng)期那時(shí)間int i=0,j;int number_schedul,temp_counter; /進(jìn)程編號(hào)，當(dāng)前已執(zhí)行進(jìn)程個(gè)數(shù)float run_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)

12、的參數(shù)number_schedul=i;Processnumber_schedul.ServiceTime=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_c

13、ounter=1;while(temp_counter<N)for(j=0;j<N;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=P

14、rocessj.WholeTime;number_schedul=j;/查找下一個(gè)被調(diào)度的進(jìn)程/對(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+;

15、Processnumber_schedul.order=temp_counter;return 0;int Pinput(); /進(jìn)程參數(shù)輸入int Poutput(); /調(diào)度結(jié)果輸出void main()int option;printf(" *主菜單*n");printf(" * 1 使用短作業(yè)優(yōu)先 *n");printf(" * 0 退出 *n");printf(" *n");/system("cls");system("color 1f");scanf("

16、%d",&option);switch(option)case 0:printf("運(yùn)行結(jié)束。n");break;case 1:printf("對(duì)進(jìn)程用短作業(yè)優(yōu)先調(diào)度。nn"); Pinput();SJF();Poutput();break;int Pinput() /進(jìn)程參數(shù)輸入int i;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&q

17、uot;,i+1);printf("請(qǐng)輸入進(jìn)程名稱:n");scanf("%s",Processi.Name); printf("請(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

18、=0;Processi.order=0;Processi.run_flag=0;system("cls");return 0;int Poutput() /調(diào)度結(jié)果輸出int i;float turn_round_time=0,f1,w=0;printf(" 進(jìn)程名稱 到達(dá)T 運(yùn)行T 開(kāi)始運(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.WeightWholeTi

19、me/Processi.WholeTime;turn_round_time+=Processi.WeightWholeTime;w+=f1;printf("時(shí)刻%d :",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);return 0;九、實(shí)驗(yàn)體會(huì)通過(guò)本次課程設(shè)計(jì)，使我對(duì)計(jì)算機(jī)操作系統(tǒng)短作業(yè)優(yōu)先調(diào)度算法這一節(jié)的知識(shí)有了更深的了解 。短作業(yè)優(yōu)先調(diào)度算法易于實(shí)現(xiàn)，并且效率很高，但是短作業(yè)只考慮到短作業(yè)的利益，而不顧長(zhǎng)作業(yè)，這樣就可能會(huì)使得長(zhǎng)作業(yè)一直處于等待狀態(tài)而不能運(yùn)行。所以