處理機(jī)調(diào)度實(shí)驗(yàn)報(bào)告1

1、深圳大學(xué)實(shí)驗(yàn)報(bào)告課程名稱：操作系統(tǒng)實(shí)驗(yàn)項(xiàng)目名稱：處理機(jī)調(diào)度學(xué)院：計(jì)算機(jī)與軟件學(xué)院專業(yè)：軟件工程指導(dǎo)教師：報(bào)告人：學(xué)號(hào)：班級(jí)：實(shí)驗(yàn)時(shí)間：2013 年5月7日實(shí)驗(yàn)報(bào)告提交時(shí)間：2013 年5月22日教務(wù)處制一、實(shí)驗(yàn)?zāi)康呐c要求：實(shí)驗(yàn)?zāi)康?: 模擬在單處理器多進(jìn)程操作系統(tǒng)的 CPU 調(diào)度。幫助學(xué)生掌握多種 CPU 調(diào)度算法的知識(shí)原理和運(yùn)作機(jī)制。本實(shí)驗(yàn)為模擬實(shí)驗(yàn)，不要求實(shí)現(xiàn)真正的進(jìn)程創(chuàng)建與進(jìn)程調(diào)度。主要實(shí)現(xiàn)各種調(diào)度算法。實(shí)驗(yàn)要求 :1、閱讀理解例程，掌握例程的運(yùn)作流程。運(yùn)行例程，理解先來(lái)先服務(wù)算法的調(diào)度原理和運(yùn)行結(jié)果。2、參考先來(lái)先服務(wù)算法，嘗試實(shí)現(xiàn)其他四種調(diào)度算法：短作業(yè)優(yōu)先、高響應(yīng)比、時(shí)間片輪轉(zhuǎn)、多

2、級(jí)反饋隊(duì)列。要求至少實(shí)現(xiàn)一種算法。a) 除了多級(jí)反饋隊(duì)列，其他算法采用非搶占調(diào)度b) 短作業(yè)優(yōu)先算法使用例題一數(shù)據(jù)或程序內(nèi)置數(shù)據(jù)，要求運(yùn)行結(jié)果給出調(diào)度順序、完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間c) 高響應(yīng)比算法使用例題二的數(shù)據(jù)，要求運(yùn)行結(jié)果給出調(diào)度順序、完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間d) 時(shí)間片輪轉(zhuǎn)算法可以使用程序內(nèi)置數(shù)據(jù)，要求運(yùn)行結(jié)果給出每個(gè)時(shí)間片是被哪個(gè)進(jìn)程使用，每個(gè)進(jìn)程完成時(shí)，要修改狀態(tài)并輸出提示。e) 多級(jí)反饋隊(duì)列算法使用例題三的數(shù)據(jù)，要求運(yùn)行結(jié)果給出正確的進(jìn)程調(diào)度順序和過(guò)程描述。二、方法、步驟：(說(shuō)明程序相關(guān)的算法原理或知識(shí)內(nèi)容，程序設(shè)計(jì)的思路和方法，可以用流程圖表述，程序主要數(shù)據(jù)結(jié)構(gòu)

3、的設(shè)計(jì)、主要函數(shù)之間的調(diào)用關(guān)系等)先來(lái)先服務(wù)算法：按到達(dá)時(shí)間先后，選擇最先來(lái)的作業(yè)最先執(zhí)行實(shí)現(xiàn)思想：對(duì)作業(yè)的到達(dá)時(shí)間按大小進(jìn)行排序，然后按順序執(zhí)行短作業(yè)優(yōu)先算法：在后備隊(duì)列中，選擇服務(wù)時(shí)間最短的作業(yè)最先執(zhí)行實(shí)現(xiàn)思想：對(duì)作業(yè)按到達(dá)時(shí)間排序，接著對(duì)到達(dá)的作業(yè)，即后備隊(duì)列中的作業(yè)按服務(wù)時(shí)間排序，取服務(wù)時(shí)間最小的作業(yè)最先執(zhí)行高響應(yīng)比算法：對(duì)作業(yè)的優(yōu)先權(quán)（響應(yīng)時(shí)間/要求服務(wù)時(shí)間）進(jìn)行計(jì)算，對(duì)優(yōu)先權(quán)最高的最先執(zhí)行實(shí)現(xiàn)實(shí)現(xiàn)：計(jì)算后備隊(duì)列中作業(yè)的優(yōu)先權(quán)，并排序，優(yōu)先權(quán)最高的最先執(zhí)行時(shí)間片輪轉(zhuǎn)算法：將所有就緒進(jìn)程按先來(lái)先服務(wù)排成隊(duì)列，把CPU 分配給隊(duì)首進(jìn)程，進(jìn)程只執(zhí)行一個(gè)時(shí)間片，時(shí)間片用完后，將已使用時(shí)間片的

4、進(jìn)程送往就緒隊(duì)列的末尾，分配處理機(jī)給就緒隊(duì)列中下一進(jìn)程實(shí)現(xiàn)思想：將作業(yè)按到達(dá)時(shí)間排序，在后備隊(duì)列中選擇第一個(gè)作業(yè)，把CPU 分配給它，執(zhí)行一個(gè)時(shí)間片，時(shí)間片用完后，將作業(yè)送往后備隊(duì)列的末尾，把CPU 分配給下一個(gè)作業(yè)，直到所有作業(yè)完成多級(jí)反饋隊(duì)列調(diào)度算法：設(shè)置多個(gè)就緒隊(duì)列，各個(gè)隊(duì)列優(yōu)先級(jí)逐個(gè)降低，各個(gè)隊(duì)列時(shí)間片逐個(gè)增加，優(yōu)先級(jí)越高的隊(duì)列執(zhí)行時(shí)間片就越短，一般時(shí)間片按倍增規(guī)則，每個(gè)新進(jìn)程首先進(jìn)入第一個(gè)隊(duì)列，遵循 FCFS，在當(dāng)前隊(duì)列的時(shí)間片內(nèi)，進(jìn)程若能完成，退出，進(jìn)程若未完成，降級(jí)到第二個(gè)隊(duì)列，同樣遵循 FCFS 依次類推，若在第二個(gè)隊(duì)列的時(shí)間片內(nèi)仍未完成，再降級(jí)到第三個(gè)隊(duì)列實(shí)現(xiàn)思想：設(shè)置多個(gè)就

5、緒隊(duì)列，各個(gè)隊(duì)列優(yōu)先級(jí)逐個(gè)降低，各個(gè)隊(duì)列時(shí)間片逐個(gè)增加，優(yōu)先級(jí)越高的隊(duì)列執(zhí)行時(shí)間片就越短，一般時(shí)間片按倍增規(guī)則， 例如，第二隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍， ，第 i+1 個(gè)隊(duì)列的時(shí)間片要比第 i 個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍，整合了時(shí)間片、 FCFS、優(yōu)先級(jí)三種機(jī)制。三實(shí)驗(yàn)過(guò)程及內(nèi)容：(對(duì)程序代碼進(jìn)行說(shuō)明和分析，越詳細(xì)越好，代碼排版要整齊，可讀性要高)#include "stdio.h"#include<stdlib.h>/#include<conio.h>#include<time.h>#include<math.h>/

6、#define NULL 0#define getpch(type)(type*)malloc(sizeof(type)typedef struct pcb PCB;struct pcb/定義進(jìn)程控制塊PCBint id;char name10;/標(biāo)示符/ 名稱int time_start;int time_need;/到達(dá)時(shí)間/ 服務(wù)時(shí)間int time_left;int time_used;/剩余運(yùn)行時(shí)間/已使用時(shí)間char state;/進(jìn)程狀態(tài);/*void _sleep(int n)系統(tǒng)函數(shù)clock_t goal;goal=(clock_t)n*CLOCKS_PER_SEC+clo

7、ck();while(goal>clock();char _keygo()char c;printf(" 按任意鍵繼續(xù) n");c=getchar();return c;/*用戶函數(shù)int time_unit=2;int num=5;/實(shí)際進(jìn)程數(shù)量PCB pcbdata10=/例程內(nèi)置數(shù)據(jù)1000,"A",0,4,4,0,'R',1001,"B",1,3,3,0,'R',1002,"C",2,5,5,0,'R',1003,"D",3,2,2,

8、0,'R',1004,"E",4,4,4,0,'R',;int num1=4;PCB pcbdata110=/例題一數(shù)據(jù)1000,"Job1",1,9,9,0,'R',1001,"Job2",1,16,16,0,'R',1002,"Job3",1,3,3,0,'R',1003,"Job4",1,11,11,0,'R',;int num2=4;PCB pcbdata210=/例題二數(shù)據(jù)1000,&quo

9、t;P1",10,8,8,0,'R',1001,"P2",12,12,12,0,'R',1002,"P3",14,4,4,0,'R',1003,"P4",16,6,6,0,'R',;int num3=4;PCB pcbdata310=/例程三數(shù)據(jù)1000,"A",0,7,7,0,'R',1001,"B",5,4,4,0,'R',1002,"C",7,13,13,0,

10、9;R',1003,"D",12,9,9,0,'R',;int ready10; int order10;/就緒隊(duì)列，存放進(jìn)程在pcbdata 中的位置/記錄排序使用哪個(gè)數(shù)值作為排序?qū)ο髒oid intput()int i;printf(" 進(jìn)程總數(shù)為： ");scanf("%d",&num);for(i=0;i<num;i+)pcbdatai.id=1000+i;printf(" 輸入第 %d 個(gè)進(jìn)程名： ",i+1);scanf("%s",&pc

11、);printf(" 輸入第 %d 個(gè)進(jìn)程到達(dá)時(shí)間： ",i+1);scanf("%d",&pcbdatai.time_start);printf(" 輸入第 %d 個(gè)進(jìn)程服務(wù)時(shí)間： ",i+1);scanf("%d",&pcbdatai.time_need);pcbdatai.time_left=pcbdatai.time_need;printf("n");pcbdatai.time_used=0;pcbdatai.state='R'/*調(diào)

12、度函數(shù)void FCFS()int i,j,temp;double k;for(i=0;i<num;i+)orderi=pcbdatai.time_start;readyi=i;for(i=0;i<num;i+)/按到達(dá)時(shí)間排序for(j=i+1;j<num;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("- 先來(lái)先服務(wù)算法調(diào)度：非搶占，無(wú)時(shí)間片-n");temp=pcbdataready0.

13、time_start;for(i=0;i<num;i+)printf(" 第%d 個(gè)進(jìn)程 -%s,",i+1,); printf(" 本進(jìn)程正在運(yùn)行 ");_sleep(1);printf(" 運(yùn)行完畢 n");temp+=pcbdatareadyi.time_need;j=temp-pcbdatareadyi.time_start;k=(float)j/pcbdatareadyi.time_need;printf(" 完成時(shí)間 -%d, 周轉(zhuǎn)時(shí)間 -%d, 帶權(quán)周轉(zhuǎn)時(shí)間 -%.1f

14、n",temp,j,k);printf("-所有進(jìn)程調(diào)度完畢-n");void SJF()int i,j,temp,l,temp_num;double k;int time=0;for(i=0;i<num1;i+)orderi=pcbdata1i.time_start;readyi=i;for(i=0;i<num1;i+) /按到達(dá)時(shí)間排序 for(j=i+1;j<num1;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;

15、readyj=temp;printf("- 短作業(yè)算法調(diào)度：非搶占，無(wú)時(shí)間片-n");int t_ready10;/就緒隊(duì)列，存放進(jìn)程在 pcbdata 中的位置int t_order10;/記錄排序使用哪個(gè)數(shù)值作為排序?qū)ο骹or(i=0;i<num1;i+)t_orderi=pcbdata1readyi.time_need;/服務(wù)時(shí)間作為排序?qū)ο?t_readyi=readyi;time=order0;for(l=0;l<num1;l+)/判斷到達(dá)的進(jìn)程數(shù)，用temp_num 存放for(i=0;i<num&&pcbdata1readyi

16、.time_start<=time;i+)temp_num=i+1;/把到達(dá)的進(jìn)程按服務(wù)時(shí)間大小進(jìn)行排序for(i=0;i<temp_num;i+)for(j=i+1;j<temp_num;j+)if(t_orderi>t_orderj&&t_orderj!=0|t_orderi=0)temp=t_orderi;t_orderi=t_orderj;t_orderj=temp;temp=t_readyi;t_readyi=t_readyj;t_readyj=temp;printf(" 第%d 個(gè)進(jìn)程 -%s,",l+1,pcbdata1

17、t_); printf(" 正在運(yùn)行 ");_sleep(1);printf(" 運(yùn)行完畢 n");time+=pcbdata1t_ready0.time_need;j=time-pcbdata1t_ready0.time_start;k=(float)j/pcbdata1t_ready0.time_need;t_order0=0;printf("完 成 時(shí) 間 -%d,周 轉(zhuǎn) 時(shí) 間 -%d, 帶 權(quán) 周 轉(zhuǎn) 時(shí) 間-%.1fn",time,j,k);printf("-所有進(jìn)程調(diào)度完畢-n"

18、);void HRF()int i,j,temp,l,temp_num;double k;int time=0;for(i=0;i<num2;i+)orderi=pcbdata2i.time_start;readyi=i;for(i=0;i<num2;i+)/按到達(dá)時(shí)間排序for(j=i+1;j<num2;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("- 高響應(yīng)比算法調(diào)度：非搶占，無(wú)時(shí)間片 -n&qu

19、ot;); int t_ready10;int t_order10;for(i=0;i<num2;i+)t_orderi=1;t_readyi=readyi;time=order0;for(l=0;l<num2;l+)/判斷到達(dá)進(jìn)程數(shù)for(i=0;i<num&&pcbdata2readyi.time_start<=time;i+)temp_num=i+1;for(i=0;i<temp_num;i+)/計(jì)算已到達(dá)進(jìn)程的優(yōu)先權(quán)if(t_orderi)t_orderi=(time-pcbdata2t_readyi.time_start+pcbdata2

20、t_readyi.time_need)/pcbdata2t_readyi.time_need;for(i=0;i<temp_num;i+)/按優(yōu)先權(quán)排序for(j=i+1;j<temp_num;j+)if(t_orderi<t_orderj)temp=t_orderi;t_orderi=t_orderj;t_orderj=temp;temp=t_readyi;t_readyi=t_readyj;t_readyj=temp;printf(" 第%d 個(gè)進(jìn)程 -%s,",l+1,pcbdata2t_); printf(" 正在運(yùn)

21、行 ");_sleep(1);printf(" 運(yùn)行完畢 n");time+=pcbdata2t_ready0.time_need;j=time-pcbdata2t_ready0.time_start;k=(float)j/pcbdata2t_ready0.time_need;t_order0=0;printf("完 成 時(shí) 間-%.1fn",time,j,k);printf("- 所有進(jìn)程調(diào)度完畢-%d, 周 轉(zhuǎn) 時(shí) 間-n");-%d,帶權(quán)周轉(zhuǎn)時(shí)間void Timeslice()int i,j,temp,l,temp_n

22、um;double k;int time=0;int done=0;for(i=0;i<num;i+)orderi=pcbdatai.time_start;readyi=i;for(i=0;i<num;i+)/按到達(dá)時(shí)間排序for(j=i+1;j<num;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("- 時(shí)間片輪轉(zhuǎn)算法調(diào)度：非搶占，時(shí)間片大小為 2-n"); int t_ready10;fo

23、r(i=0;i<num;i+)t_readyi=readyi;time=order0;for(l=0;done<num;l+)/判斷到達(dá)的進(jìn)程數(shù)for(i=0;i<num&&pcbdatareadyi.time_start<=time;i+)temp_num=i+1;if(time!=order0)/將已使用時(shí)間片的進(jìn)程，即第一個(gè)移到隊(duì)列末尾for(i=1;i<temp_num;i+)temp=t_readyi;t_readyi=t_readyi-1;t_readyi-1=temp;if(pcbdatat_ready0.state!='F&

24、#39;)printf("第%d個(gè)時(shí)間片被進(jìn)程%s使用 ,",l+1,pcbdatat_);printf(" 正在運(yùn)行 n");_sleep(1);printf(" 時(shí)間片使用完，所需時(shí)間%d,",pcbdatat_ready0.time_left);time+=2;pcbdatat_ready0.time_used+=2;pcbdatat_ready0.time_left-=2;printf(" 使用時(shí)間 %d, 還需時(shí)間 %d,",2,pcbdatat_ready0.time_left);

25、/判斷進(jìn)程是否結(jié)束if(pcbdatat_ready0.time_left<=0)printf(" 進(jìn)程 %s 結(jié)束 n",pcbdatat_);done+;pcbdatat_ready0.state='F'elseprintf(" 進(jìn)程 %s 就緒 n",pcbdatat_);printf("-所有進(jìn)程調(diào)度完畢-n");void MRLA()int i,j,temp,l,temp_num,temp_num2;double k;int time=0;/系統(tǒng)時(shí)間int d

26、one=0;/已完成的進(jìn)程int t_ready10;int queue10;/進(jìn)程對(duì)應(yīng)的隊(duì)列int qtime10;/進(jìn)程對(duì)應(yīng)的時(shí)間片for(i=0;i<num3;i+)orderi=pcbdata3i.time_start;readyi=i;queuei=1;qtimei=0;for(i=0;i<num3;i+)for(j=i+1;j<num3;j+)/按到達(dá)時(shí)間排序if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf(&

27、quot;- 多級(jí)反饋算法調(diào)度：搶占式，時(shí)間片大小為for(i=0;i<num3;i+)2-n");t_readyi=readyi;time=order0;for(l=0;done<num3;l+)/判斷到達(dá)的進(jìn)程數(shù)for(i=0;i<num3&&pcbdata3readyi.time_start<=time;i+)temp_num=i+1;if(time!=order0)for(i=0;i<temp_num;i+) / 按隊(duì)列優(yōu)先級(jí)排序for(j=1;j<temp_num-i;j+)if(pcbdata3t_readyj-1.st

28、ate='F'|(queuej-1>queuej&&pcbdata3t_readyj.state!='F')temp=queuej-1;queuej-1=queuej;queuej=temp;temp=t_readyj-1;t_readyj-1=t_readyj;t_readyj=temp;temp=qtimej-1;qtimej-1=qtimej;qtimej=temp;if(pcbdata3t_ready0.state!='F')printf(" 隊(duì) 列 %d 中 的 進(jìn) 程 %s 占 用 CPU,"

29、,queue0, pcbdata3t_);printf(" 正在運(yùn)行 n");_sleep(1);if(!qtime0)/ 判斷是否有未用完的時(shí)間片qtime0=pow(2,queue0);elseprintf(" 繼續(xù)使用時(shí)間片， ");for(i=1;i<qtime0;i+)time+;for(j=0;j<num3&&pcbdata3readyj.time_start<=time;j+)temp_num2=j+1;/判斷是否有進(jìn)程進(jìn)入比本進(jìn)程更高優(yōu)先級(jí)的隊(duì)列if(temp_num!=temp_n

30、um2&&queue0>queuetemp_num2-1&& pcbdata3t_ready0.time_left-i>0)qtime0-=i;break;if(temp_num!=temp_num2&&queue0>queuetemp_num2-1&&pcbdata3t_read y0.time_left-i>0)printf(" 發(fā)生搶占，使用時(shí)間片 %d ，剩余時(shí)間片 %d ，返回隊(duì)列尾部 n",i,qtime0);elseprintf(" 時(shí) 間 片 使 用 完 ， 所

31、 需 時(shí) 間 %d,", pcbdata3t_ready0.time_left);time+;pcbdata3t_ready0.time_used+=pow(2,queue0); pcbdata3t_ready0.time_left-=pow(2,queue0);if(pcbdata3t_ready0.time_left<=0)printf(" 使用時(shí)間 %d, 還需時(shí)間 %d, 進(jìn)程 %s 結(jié)束 n",qtime0, pcbdata3t_ready0.time_left,pcbdata3t_);done+;pcbdata3t_read

32、y0.state='F'elseprintf(" 使用時(shí)間 %d, 還需時(shí)間 %d, 進(jìn)程 %s 進(jìn)入隊(duì)列 %d 就緒n",qtime0,pcbdata3t_ready0.time_left,pcbdata3t_,+queue0); qtime0=0;for(j=1;j<temp_num2;j+) /將執(zhí)行的程序返回隊(duì)尾排隊(duì) temp=queuej;queuej=queuej-1;queuej-1=temp;temp=qtimej;qtimej=qtimej-1;qtimej-1=temp;temp=t_readyj;t_read

33、yj=t_readyj-1;t_readyj-1=temp;printf("- 所有進(jìn)程調(diào)度完畢 -n");intmain()int i=0,sch=99;while(sch!=0)printf("n 請(qǐng)選擇其中一種調(diào)度算法：n");printf("(1) 先來(lái)先服務(wù) FCFSn");printf("(2) 短作業(yè)優(yōu)先 SJFn");printf("(3) 高響應(yīng)比 HRFn");printf("(4) 時(shí)間片輪轉(zhuǎn) Timeslicen");printf("(5)

34、多級(jí)反饋隊(duì)列 MRLAn");printf("(0) 退出 n");printf(" 請(qǐng)輸入上述一個(gè)數(shù)字： ");scanf("%d",&sch);switch(sch)case 1:FCFS();break;case 2:SJF();break;case 3:HRF();break;case 4:Timeslice();break;case 5:MRLA();break;case 0:printf("退出程序 n");break;_keygo();return 0;void dis_pcb(PCB * pr)printf("%s 的 PCB:n",pr->name);printf(" 標(biāo)識(shí)符 -%d, 狀態(tài) -%c, 到達(dá)時(shí)間 -%dn",pr->id,pr->state,pr->time_start); printf(" 服 務(wù) 時(shí) 間 -%d, 剩 余 運(yùn) 行 時(shí) 間 -%d, 已 用 時(shí) 間-%dn",pr->time_need,pr->time_left,pr->time_used); printf