處理機(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)行例程，理解先來先服務(wù)算法的調(diào)度原理和運(yùn)行結(jié)果。2、 參考先來先服務(wù)算法，嘗試實(shí)現(xiàn)其

2、他四種調(diào)度算法：短作業(yè)優(yōu)先、高響應(yīng)比、時(shí)間片輪轉(zhuǎn)、多級(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ān)的算法原理或知識(shí)內(nèi)容，程序

3、設(shè)計(jì)的思路和方法，可以用流程圖表述，程序主要數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)、主要函數(shù)之間的調(diào)用關(guān)系等)先來先服務(wù)算法：按到達(dá)時(shí)間先后，選擇最先來的作業(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)程按先來先服務(wù)排成隊(duì)列，把CPU分配給隊(duì)首進(jìn)

4、程，進(jìn)程只執(zhí)行一個(gè)時(shí)間片，時(shí)間片用完后，將已使用時(shí)間片的進(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)

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

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

7、_t)n*CLOCKS_PER_SEC+clock();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',100

8、3,"D",3,2,2,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 pcbd

9、ata210=/例題二數(shù)據(jù)1000,"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,"

10、;C",7,13,13,0,'R',1003,"D",12,9,9,0,'R',;int ready10; /就緒隊(duì)列，存放進(jìn)程在pcbdata中的位置int order10; /記錄排序使用哪個(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("

11、%s",&);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

12、'/*調(diào)度函數(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("-先來先服務(wù)算法調(diào)度：非搶占，無時(shí)間片-n");temp=pcbdat

13、aready0.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í)間-%.1fn"

14、;,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;readyj=

15、temp;printf("-短作業(yè)算法調(diào)度：非搶占，無時(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ū)ο髏_readyi=readyi;time=order0;for(l=0;l<num1;l+)/判斷到達(dá)的進(jìn)程數(shù)，用temp_num存放for(i=0;i<num&&pcbdata1readyi.time_start

16、<=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,pcbdata1t_)

17、;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");void HRF()int i,j,temp,l,temp_n

18、um;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)度：非搶占，無時(shí)間片-n");int t_ready10;int t_order10;f

19、or(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+ pcbdata2t_readyi.time_need)/pcbdata2t_rea

20、dyi.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)行");_sleep(1);printf("運(yùn)行完畢n

21、");time+=pcbdata2t_ready0.time_need;j=time-pcbdata2t_ready0.time_start;k=(float)j/pcbdata2t_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");void Timeslice()int i,j,temp,l,temp_num;double k;int time=0;int done=0;for(i=0;i<n

22、um;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;for(i=0;i<num;i+)t_readyi=readyi;time=order0;for(

23、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')printf("第%d個(gè)時(shí)間片被進(jìn)程%s使用,",l+1,pcbdat

24、at_);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);/判斷進(jìn)程是否結(jié)束if(pcbdatat_ready0.time_left<=0)printf("

25、進(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 done=0; /已完成的進(jìn)程int t_ready10;int queue10; /進(jìn)程對(duì)應(yīng)的隊(duì)列int qtime10; /進(jìn)

26、程對(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+) /按到達(dá)時(shí)間排序for(j=i+1;j<num3;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("-多級(jí)反饋算法調(diào)度：搶占式，時(shí)間片大小為2-n");for(i=0;i<num3;i+)t_r

27、eadyi=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.state='F'|(queuej-1>queuej&&pcbdata3t_readyj

28、.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,",queue0, pcbdata3t_);printf("正在運(yùn)行n ");_sleep(1);if(

29、!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_num2&&queue0>queuetemp_num2-1&& pcbdata3t_ready0.time_lef

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

31、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_ready0.state='F'elseprintf("使用時(shí)間%d,還需時(shí)間%d,進(jìn)程%s進(jìn)入隊(duì)列%d就緒n",qtime0,pcbdata3t_ready0.time_lef

32、t,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_readyj=t_readyj-1;t_readyj-1=temp;printf("-所有進(jìn)程調(diào)度完畢-n");int main()int i=0,sch=99;while(sch!=0)printf("n

33、請(qǐng)選擇其中一種調(diào)度算法：n");printf("(1)先來先服務(wù)FCFSn");printf("(2)短作業(yè)優(yōu)先SJFn");printf("(3)高響應(yīng)比HRFn");printf("(4)時(shí)間片輪轉(zhuǎn)Timeslicen");printf("(5)多級(jí)反饋隊(duì)列MRLAn");printf("(0)退出n");printf("請(qǐng)輸入上述一個(gè)數(shù)字：");scanf("%d",&sch);switch(sch)case 1

34、: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("-n&quo