【操作系統(tǒng)課程設(shè)計】Linux環(huán)境下使用C語言實(shí)現(xiàn)先來先服務(wù)調(diào)度算法

《【操作系統(tǒng)課程設(shè)計】Linux環(huán)境下使用C語言實(shí)現(xiàn)先來先服務(wù)調(diào)度算法》由會員分享，可在線閱讀，更多相關(guān)《【操作系統(tǒng)課程設(shè)計】Linux環(huán)境下使用C語言實(shí)現(xiàn)先來先服務(wù)調(diào)度算法（13頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、更多課程設(shè)計、論文、畢業(yè)設(shè)計請?jiān)L問： 作業(yè)模擬調(diào)度實(shí)驗(yàn) 1 課程設(shè)計的目的 通過該題目的設(shè)計過程，可以初步掌握作業(yè)調(diào)度的原理、軟件開發(fā)方法并提高解決實(shí)際問題的能力。了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，練習(xí)并掌握UNIX提供的vi編輯器來編譯C程序，學(xué)會利用gcc、gdb編譯、調(diào)試C程序。 2 課程設(shè)計的開發(fā)語言 程序設(shè)計所選用的程序設(shè)計語言為C語言。 3 功能描述 先來先服務(wù)算法比較有利于長作業(yè)，而不利于短作業(yè)。 （1）短作業(yè)（SJF）的調(diào)度算法可以照顧到實(shí)際上在所有作業(yè)

2、中占很大比例的短作業(yè)，使它能比長作業(yè)優(yōu)先執(zhí)行。SPF優(yōu)先調(diào)度算法：是從就緒隊(duì)列中選出一估計運(yùn)行時間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時，再重新調(diào)度。為了和FCFS調(diào)度算法進(jìn)行比較，我們利用FCFS算法中所使用的實(shí)例并改用SJ（P）F算法重新調(diào)度，再進(jìn)行性能分析。采用SJF算法后，不論是平均周轉(zhuǎn)時間還是平均帶權(quán)周轉(zhuǎn)時間都有較明顯的改善，尤其是對短作業(yè)D，其周轉(zhuǎn)時間由FCFS算法的11降為SJF算法中的3；而平均帶權(quán)周轉(zhuǎn)時間是從5.5降到1.5。這說明SJF調(diào)度算法能有效地降低作業(yè)的平均等待時間和提高系統(tǒng)的吐量。短作業(yè)優(yōu)先調(diào)度算法對比先來先服務(wù)，不論是

3、平均周轉(zhuǎn)時間還是平均帶權(quán)周轉(zhuǎn)時間，都有較明顯的改善，尤其是對短作業(yè)。該算法對長作業(yè)不利，而且未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)會被及時處理。 如作業(yè)C的周轉(zhuǎn)時間由10增至16，帶權(quán)周轉(zhuǎn)時間由2增至3.1。更嚴(yán)重的是，如果有一長作業(yè)（進(jìn)程）進(jìn)入系統(tǒng)的后備隊(duì)列（就緒隊(duì)列），由于調(diào)度程序總是優(yōu)先調(diào)度那些（即使是后進(jìn)來的）短作業(yè)（進(jìn)程），將致使長作業(yè)（進(jìn)程）得不到調(diào)度。 （2）該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進(jìn)程），會得到及時處理； （3）由于作業(yè)（進(jìn)程）的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定，而用戶又可能會有意或無意地縮短其作業(yè)的估計執(zhí)行時間，致使該算法不

4、一定能真正做到短作業(yè)優(yōu)先調(diào)度。 高響應(yīng)比優(yōu)先調(diào)度算法在批處理系統(tǒng)中，用作作業(yè)調(diào)度的短作業(yè)優(yōu)先算法是一個比較好的算法。其主要缺點(diǎn)是作業(yè)的運(yùn)行得不到保證。如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權(quán)機(jī)制，并使以速率a增加，則長作業(yè)在等待一定的時間后，必須有機(jī)會分配到處理機(jī)。該優(yōu)先權(quán)的變化可描述為： 優(yōu)先權(quán)=（等待時間+要求服務(wù)時間）/要求服務(wù)時間 由于等待時間加上要求服務(wù)時間，就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比Rp = 等待時間加要求服務(wù)時間/要求服務(wù)時間=響應(yīng)時間/要求服務(wù)時間 由上式可以看出： （1）如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其

5、優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)； （2）當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，因而實(shí)現(xiàn)了先來先服務(wù)； （3）對于長作業(yè)，當(dāng)其等待時間足夠長時，其優(yōu)先權(quán)便可升到很高，從而也可獲得處理機(jī)。 該算法既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后順序，也不會使作業(yè)長期得不到服務(wù)。因此，該算法實(shí)現(xiàn)了一種較好的折衷。當(dāng)然，再利用該算法時，每要進(jìn)行調(diào)度之前，都需先進(jìn)行響應(yīng)應(yīng)比的計算，這會增加系統(tǒng)的開銷。 4 方案論證 4.1 概要設(shè)計 假設(shè)在單道批處理環(huán)境下有四個作業(yè)JOB1、JOB2、JOB3、JOB4，已知它們進(jìn)入系統(tǒng)的時間、估計運(yùn)行時間。分別采用先來先服務(wù)（FCFS），最短作業(yè)

6、優(yōu)先（SJF）、響應(yīng)比高者優(yōu)先（HRN）的調(diào)度算法，計算出作業(yè)的平均周轉(zhuǎn)時間和帶權(quán)的平均周轉(zhuǎn)時間 。 作業(yè) i 的周轉(zhuǎn)時間：Ti=Tci-Tsi 作業(yè)的平均周轉(zhuǎn)時間：T= 作業(yè)i的帶權(quán)周轉(zhuǎn)時間：Wi=Ti/Tri 作業(yè)的平均帶權(quán)周轉(zhuǎn)時間：W= 先來先服務(wù)調(diào)度算法（FCFS）：每次調(diào)度都是從后備作業(yè)隊(duì)列中，選擇一個或多個最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。在進(jìn)程調(diào)度中采用FCFS算法時，這每次調(diào)度是從就緒隊(duì)列中，選擇一個最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件阻賽后，才放棄處理機(jī)。 短作業(yè)（進(jìn)

7、程）優(yōu)先調(diào)度算法SJ（P）F，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。該調(diào)度算法是從后備（就緒）隊(duì)列中選擇一個或若干個估計運(yùn)行時間最短的作業(yè)（進(jìn)程），將它們調(diào)度內(nèi)存運(yùn)行。 響應(yīng)比高者優(yōu)先（HRN）：每次從后備隊(duì)列中選擇一個或若干個估計響應(yīng)比最高的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。 響應(yīng)比Rp=作業(yè)響應(yīng)時間/運(yùn)行時間 =作業(yè)等待時間+作業(yè)運(yùn)行時間 =1+作業(yè)等待時間 每個作業(yè)由一個作業(yè)控制塊JCB表示，JCB可以包含如下信息：作業(yè)名、提交時間、所需的運(yùn)行時間、所需的資源、作業(yè)狀態(tài)、鏈指針等等。

8、 作業(yè)的狀態(tài)可以是等待W(Wait)、運(yùn)行R(Run)和完成F(Finish)三種狀態(tài)之一。每個作業(yè)的最初狀態(tài)總是等待W。 各個等待的作業(yè)按照提交時刻的先后次序排隊(duì)，總是首先調(diào)度等待隊(duì)列中隊(duì)首的作業(yè)。 每個作業(yè)完成后要打印該作業(yè)的開始運(yùn)行時刻、完成時刻、周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，這一組作業(yè)完成后要計算并打印這組作業(yè)的平均周轉(zhuǎn)時間、帶權(quán)平均周轉(zhuǎn)時間。 4.2 詳細(xì)設(shè)計 4.2.1 程序設(shè)計過程中的部分算法 （1）用類C語言定義相關(guān)的數(shù)據(jù)類型 定義頭文件： #include #include #define getpc

9、h(type) (type*)malloc(sizeof(type)) 定義結(jié)構(gòu)體： struct worktime{ float Tb; //作業(yè)運(yùn)行時刻 float Tc; //作業(yè)完成時刻 float Ti; //周轉(zhuǎn)時間 float Wi; //帶權(quán)周轉(zhuǎn)時間 }; struct jcb { //定義作業(yè)控制塊JCB char name[10]; //作業(yè)名 float s

10、ubtime; //作業(yè)提交時間 float runtime; //作業(yè)所需的運(yùn)行時間 char resource; //所需資源 float Rp; //后備作業(yè)響應(yīng)比 char state; //作業(yè)狀態(tài) struct worktime wt; struct jcb* link; //鏈指針 }*jcb_ready=NULL,*j; （2）各模塊偽碼 void SJFget

11、() // 獲取隊(duì)列中的最短作業(yè) { JCB *front,*mintime,*rear; //定義JCB指針 int ipmove=0; mintime=jcb_ready; rear=mintime->link; while(rear!=NULL) if((rear!=NULL)&&(T>=rear->subtime)&&(mintime->runtime)>(rear->runtime)) { //隊(duì)列不空時，給作業(yè)排隊(duì)

12、 front=mintime; mintime=rear; rear=rear->link; ipmove=1; } else rear=rear->link; if (ipmove==1){ //隊(duì)首作業(yè)完成，后續(xù)作業(yè)重新排隊(duì) front->link=mintime->link; mintime->link=jcb_ready; } jcb_ready=mi

13、ntime; } void HRNget() // 獲取隊(duì)列中的最高響應(yīng)作業(yè) { JCB *front,*mintime,*rear; int ipmove=0;//初始化 mintime=jcb_ready; rear=mintime->link; while(rear!=NULL) if ((rear!=NULL)&&(T>=rear->subtime)&&(mintime->Rp)<(rear->Rp)) { //隊(duì)尾

14、不空時，作業(yè)按運(yùn)行時間排隊(duì) front=mintime; mintime=rear; rear=rear->link; ipmove=1; } else rear=rear->link; if (ipmove==1){ //隊(duì)首作業(yè)完成，改變指針 front->link=mintime->link; mintime->link=jcb_ready;

15、} jcb_ready=mintime; } 開 始 4.2.2 主程序流程圖 : 初始化所有的JCB 使JCB按作業(yè)提交的時刻的先后順序排隊(duì) 時間量?。裕海剑? 調(diào)度隊(duì)首的作業(yè)投入運(yùn)行：（更改隊(duì)首指針，使作業(yè)的狀態(tài)為R，記住作業(yè)開始運(yùn)行的時刻Tb等） 計算并打印運(yùn)行作業(yè)i的完成時刻Tc，周轉(zhuǎn)時間Ti，帶權(quán)周轉(zhuǎn)時間Wi （完成時刻Tc=開始運(yùn)行時刻+運(yùn)行時間 周轉(zhuǎn)時間Ti=完成時刻-提交時刻 帶權(quán)周轉(zhuǎn)時間Wi=周轉(zhuǎn)時間運(yùn)行時間） 更改時間量T的值 （T：=T+作業(yè)i的運(yùn)行時間）

16、 隊(duì)列為空 ? 計算并打印這組作業(yè)的平均周轉(zhuǎn)時間及帶權(quán)平均周轉(zhuǎn)時間 結(jié) 束 圖1 調(diào)度算法流程圖 圖2 5 運(yùn)行結(jié)果 圖3 運(yùn)行結(jié)果 6 心得體會 經(jīng)過一周的努力，我的課程設(shè)計基本完成了，這次課程設(shè)計培養(yǎng)了我耐心、慎密、全面地考慮問題的能力，從而加快了問題解決的速度、提高了個人的工作效率，以及鍛煉圍繞問題在短時間內(nèi)得以解決的頑強(qiáng)意志。 在編寫

17、程序的過程中，我的能力得到了提高，同時養(yǎng)成了科學(xué)、嚴(yán)謹(jǐn)?shù)淖黠L(fēng)和習(xí)慣。為此我要感謝信息學(xué)院開設(shè)了這門操作系統(tǒng)課程設(shè)計，為我們提供了進(jìn)一步學(xué)習(xí)算法、操作系統(tǒng)和鞏固C語言程序計設(shè)這個平臺并。同時還要感謝對同一題目進(jìn)行攻關(guān)的同學(xué)們給予的幫助，沒他們的幫助可能有很多問題我個人不能進(jìn)行很好的解決。在此我對他們幫助給予衷心的感謝。 7 附錄 #include "stdio.h" #include #define getpch(type) (type*)malloc(sizeof(type)) struct worktime{ float Tb;

18、 //作業(yè)運(yùn)行時刻 float Tc; //作業(yè)完成時刻 float Ti; //周轉(zhuǎn)時間 float Wi; //帶權(quán)周轉(zhuǎn)時間 }; struct jcb { /*定義作業(yè)控制塊JCB */ char name[10]; //作業(yè)名 float subtime; //作業(yè)提交時間 float runtime; //作業(yè)所需的運(yùn)行時間

19、 char resource; //所需資源 float Rp; //后備作業(yè)響應(yīng)比 char state; //作業(yè)狀態(tài) struct worktime wt; struct jcb* link; //鏈指針 }*jcb_ready=NULL,*j; typedef struct jcb JCB; float T=0; void sort() /* 建立對作業(yè)進(jìn)行提交時間排列函數(shù)*/

20、 { JCB *first, *second; int insert=0; if((jcb_ready==NULL)||((j->subtime)<(jcb_ready->subtime))) /*作業(yè)提交時間最短的,插入隊(duì)首*/ { j->link=jcb_ready; jcb_ready=j; T=j->subtime; j->Rp=1; } else /* 作業(yè)比較提交時間,插入適當(dāng)?shù)奈恢弥?/ { first=jcb_rea

21、dy; second=first->link; while(second!=NULL) { if((j->subtime)<(second->subtime)) /*若插入作業(yè)比當(dāng)前作業(yè)提交時間短,*/ { /*插入到當(dāng)前作業(yè)前面*/ j->link=second; first->link=j; second=NULL;

22、insert=1; } Else /* 插入作業(yè)優(yōu)先數(shù)最低,則插入到隊(duì)尾*/ { first=first->link; second=second->link; } } if (insert==0) first->link=j; } } void SJFget() /* 獲取隊(duì)

23、列中的最短作業(yè) */ { JCB *front,*mintime,*rear; int ipmove=0; mintime=jcb_ready; rear=mintime->link; while(rear!=NULL) if((rear!=NULL)&&(T>=rear->subtime)&&(mintime->runtime)>(rear->runtime)) { front=mintime; mintime=rear; rear=rear-

24、>link; ipmove=1; } else rear=rear->link; if (ipmove==1){ front->link=mintime->link; mintime->link=jcb_ready; } jcb_ready=mintime; } void HRNget() /* 獲取隊(duì)列中的最高響應(yīng)作業(yè) */ { JCB *front,*mintime,*rear;

25、 int ipmove=0; mintime=jcb_ready; rear=mintime->link; while(rear!=NULL) if ((rear!=NULL)&&(T>=rear->subtime)&&(mintime->Rp)<(rear->Rp)) { front=mintime; mintime=rear; rear=rear->link; ipmove=1; } e

26、lse rear=rear->link; if (ipmove==1){ front->link=mintime->link; mintime->link=jcb_ready; } jcb_ready=mintime; } void input() /* 建立作業(yè)控制塊函數(shù)*/ { int i,num; printf("\n 請輸入作業(yè)數(shù):?"); scanf("%d",&num); for(i=0;i

27、 { printf("\n 作業(yè)號No.%d:\n",i); j=getpch(JCB); printf("\n 輸入作業(yè)名:"); scanf("%s",j->name); printf("\n 輸入作業(yè)提交時刻:"); scanf("%f",&j->subtime); printf("\n 輸入作業(yè)運(yùn)行時間:"); scanf("%f",&j->runtime); printf("\n"); j->sta

28、te=w; j->link=NULL; sort(); /* 調(diào)用sort函數(shù)*/ } } int space() { int l=0; JCB* jr=jcb_ready; while(jr!=NULL) { l++; jr=jr->link; } return(l); } void disp(JCB* jr,int select) /*建立作業(yè)顯示函數(shù),用于顯示當(dāng)前作業(yè)*/ { if (select==3) printf("\n

29、作業(yè) 服務(wù)時間 響應(yīng)比 運(yùn)行時刻 完成時刻 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 \n"); else printf("\n 作業(yè) 服務(wù)時間 運(yùn)行時刻 完成時刻 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 \n"); printf(" |%s\t",jr->name); printf(" |%.2f\t ",jr->runtime); if (select==3) printf(" |%.2f ",jr->Rp); if (j==jr){ printf(" |%.2f\t",jr->wt.Tb);

30、 printf(" |%.2f ",jr->wt.Tc); printf(" |%.2f \t",jr->wt.Ti); printf(" |%.2f",jr->wt.Wi); } printf("\n"); } void check(int select) /* 建立作業(yè)查看函數(shù) */ { JCB* jr; printf("\n **** 當(dāng)前正在運(yùn)行的作業(yè)是:%s",j->name); /*顯示當(dāng)前運(yùn)行作業(yè)*/ disp(j,select); jr=jcb_ready; pr

31、intf("\n ****當(dāng)前就緒隊(duì)列狀態(tài)為:\n"); /*顯示就緒隊(duì)列狀態(tài)*/ while(jr!=NULL) { jr->Rp=(T-jr->subtime)/jr->runtime; disp(jr,select); jr=jr->link; } destroy(); } int destroy() /*建立作業(yè)撤消函數(shù)(作業(yè)運(yùn)行結(jié)束,撤消作業(yè))*/ { printf("\n 作業(yè) [%s] 已完成.\n",j->name); free

32、(j); } void running(JCB* jr) /* 建立作業(yè)就緒函數(shù)(作業(yè)運(yùn)行時間到,置就緒狀態(tài)*/ { if (T>=jr->subtime) jr->wt.Tb=T; else jr->wt.Tb=jr->subtime; jr->wt.Tc=jr->wt.Tb+jr->runtime; jr->wt.Ti=jr->wt.Tc-jr->subtime; jr->wt.Wi=jr->wt.Ti/jr->runtime; T=jr->wt.Tc; } int main() /*主函數(shù)*/ { i

33、nt select=0,len,h=0; float sumTi=0,sumWi=0; input(); len=space(); printf("\n\t1.FCFS 2.SJF 3.HRN\n\n請選擇作業(yè)調(diào)度算法:?"); scanf("%d",&select); while((len!=0)&&(jcb_ready!=NULL)) { h++; printf("\n 執(zhí)行第%d個作業(yè) \n",h); j=jcb_ready; jcb_ready=j->link

34、; j->link=NULL; j->state=R; running(j); sumTi+=j->wt.Ti; sumWi+=j->wt.Wi; check(select); if (select==2&&h

35、har(); } printf("\n\n 作業(yè)已經(jīng)完成.\n"); printf("\t 此組作業(yè)的平均周轉(zhuǎn)時間：%.2f\n",sumTi/h); printf("\t 此組作業(yè)的帶權(quán)平均周轉(zhuǎn)時間：%.2f\n",sumWi/h); getchar(); } 參考文獻(xiàn) [1]湯子瀛，哲鳳屏.計算機(jī)操作系統(tǒng)[M].西安電子科技大學(xué)學(xué)出版社. [2]王清，李光明.計算機(jī)操作系統(tǒng)[M].冶金工業(yè)出版社. [3]孫鐘秀. 操作系統(tǒng)教程[M]. 高等教育出版社 [4]曾明. Linux操作系統(tǒng)應(yīng)用教程[M]. 陜西科學(xué)技術(shù)出版社. [5]張麗芬，劉利雄.操作系統(tǒng)實(shí)驗(yàn)教程[M]. 清華大學(xué)出版社. [6]孟靜，操作系統(tǒng)教程－－原理和實(shí)例分析[M]. 高等教育出版社. [7]周長林，計算機(jī)操作系統(tǒng)教程[M]. 高等教育出版社 [8]張堯?qū)W，計算機(jī)操作系統(tǒng)教程[M]，清華大學(xué)出版社 [9]任滿杰，操作系統(tǒng)原理實(shí)用教程[M]，電子工業(yè)出版社