處理機調(diào)度實驗報告1

1、深 圳 大 學 實 驗 報 告 課程名稱： 操作系統(tǒng) 實驗項目名稱： 處理機調(diào)度 學院： 計算機與軟件學院 專業(yè)： 軟件工程 指導教師： 報告人： 學號： 班級： 實驗時間： 2013年 5 月 7 日 實驗報告提交時間： 2013年 5 月 22 日 教務處制一、實驗目的與要求：實驗目的: 模擬在單處理器多進程操作系統(tǒng)的CPU調(diào)度。幫助學生掌握多種CPU調(diào)度算法的知識原理和運作機制。本實驗為模擬實驗，不要求實現(xiàn)真正的進程創(chuàng)建與進程調(diào)度。主要實現(xiàn)各種調(diào)度算法。實驗要求:1、 閱讀理解例程，掌握例程的運作流程。運行例程，理解先來先服務算法的調(diào)度原理和運行結(jié)果。2、 參考先來先服務算法，嘗試實現(xiàn)其

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

3、設計的思路和方法，可以用流程圖表述，程序主要數(shù)據(jù)結(jié)構(gòu)的設計、主要函數(shù)之間的調(diào)用關(guān)系等)先來先服務算法：按到達時間先后，選擇最先來的作業(yè)最先執(zhí)行實現(xiàn)思想：對作業(yè)的到達時間按大小進行排序，然后按順序執(zhí)行短作業(yè)優(yōu)先算法： 在后備隊列中，選擇服務時間最短的作業(yè)最先執(zhí)行實現(xiàn)思想： 對作業(yè)按到達時間排序，接著對到達的作業(yè)，即后備隊列中的作業(yè)按服務時間排序，取服務時間最小的作業(yè)最先執(zhí)行高響應比算法：對作業(yè)的優(yōu)先權(quán)（響應時間/要求服務時間）進行計算，對優(yōu)先權(quán)最高的最先執(zhí)行實現(xiàn)實現(xiàn)： 計算后備隊列中作業(yè)的優(yōu)先權(quán)，并排序，優(yōu)先權(quán)最高的最先執(zhí)行時間片輪轉(zhuǎn)算法：將所有就緒進程按先來先服務排成隊列，把CPU分配給隊首進

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

5、仍未完成，再降級到第三個隊列實現(xiàn)思想：設置多個就緒隊列，各個隊列優(yōu)先級逐個降低，各個隊列時間片逐個增加，優(yōu)先級越高的隊列執(zhí)行時間片就越短，一般時間片按倍增規(guī)則， 例如，第二隊列的時間片要比第一個隊列的時間片長一倍，第i+1個隊列的時間片要比第i個隊列的時間片長一倍，整合了時間片、 FCFS、優(yōu)先級三種機制。三實驗過程及內(nèi)容：(對程序代碼進行說明和分析，越詳細越好，代碼排版要整齊，可讀性要高)#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/定義進程控制塊PCBint id; /標示符char name10;/名稱int time_start; /到達時間 int time_need; /服務時間int time_left; /剩余運行時間int time_used; /已使用時間char state; /進程狀態(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ù)量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; /就緒隊列，存放進程在pcbdata中的位置int order10; /記錄排序使用哪個數(shù)值作為排序?qū)ο髒oid intput()int i;printf("進程總數(shù)為：");scanf("%d",&num);for(i=0;i<num;i+)pcbdatai.id=1000+i;printf("輸入第%d個進程名：",i+1);scanf("

11、%s",&);printf("輸入第%d個進程到達時間：",i+1);scanf("%d",&pcbdatai.time_start);printf("輸入第%d個進程服務時間：",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+) /按到達時間排序for(j=i+1;j<num;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("-先來先服務算法調(diào)度：非搶占，無時間片-n");temp=pcbdat

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

14、;,temp,j,k);printf("-所有進程調(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+) /按到達時間排序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)度：非搶占，無時間片-n");int t_ready10;/就緒隊列，存放進程在pcbdata中的位置int t_order10; /記錄排序使用哪個數(shù)值作為排序?qū)ο骹or(i=0;i<num1;i+)t_orderi=pcbdata1readyi.time_need;/服務時間作為排序?qū)ο髏_readyi=readyi;time=order0;for(l=0;l<num1;l+)/判斷到達的進程數(shù)，用temp_num存放for(i=0;i<num&&pcbdata1readyi.time_start

16、<=time;i+)temp_num=i+1;/把到達的進程按服務時間大小進行排序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個進程-%s,",l+1,pcbdata1t_)

17、;printf("正在運行");_sleep(1);printf("運行完畢n");time+=pcbdata1t_ready0.time_need;j=time-pcbdata1t_ready0.time_start;k=(float)j/pcbdata1t_ready0.time_need;t_order0=0;printf("完成時間-%d,周轉(zhuǎn)時間-%d,帶權(quán)周轉(zhuǎn)時間-%.1fn",time,j,k);printf("-所有進程調(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+) /按到達時間排序for(j=i+1;j<num2;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("-高響應比算法調(diào)度：非搶占，無時間片-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+)/判斷到達進程數(shù)for(i=0;i<num&&pcbdata2readyi.time_start<=time;i+)temp_num=i+1;for(i=0;i<temp_num;i+) /計算已到達進程的優(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個進程-%s,",l+1,pcbdata2t_);printf("正在運行");_sleep(1);printf("運行完畢n

21、");time+=pcbdata2t_ready0.time_need;j=time-pcbdata2t_ready0.time_start;k=(float)j/pcbdata2t_ready0.time_need;t_order0=0;printf("完成時間-%d,周轉(zhuǎn)時間-%d,帶權(quán)周轉(zhuǎn)時間-%.1fn",time,j,k);printf("-所有進程調(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+) /按到達時間排序for(j=i+1;j<num;j+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("-時間片輪轉(zhuǎn)算法調(diào)度：非搶占，時間片大小為2-n");int t_ready10;for(i=0;i<num;i+)t_readyi=readyi;time=order0;for(

23、l=0;done<num;l+)/判斷到達的進程數(shù)for(i=0;i<num&&pcbdatareadyi.time_start<=time;i+)temp_num=i+1;if(time!=order0)/將已使用時間片的進程，即第一個移到隊列末尾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個時間片被進程%s使用,",l+1,pcbdat

24、at_);printf("正在運行n ");_sleep(1);printf("時間片使用完，所需時間%d,",pcbdatat_ready0.time_left);time+=2;pcbdatat_ready0.time_used+=2;pcbdatat_ready0.time_left-=2;printf("使用時間%d,還需時間%d,",2,pcbdatat_ready0.time_left);/判斷進程是否結(jié)束if(pcbdatat_ready0.time_left<=0)printf("

25、進程%s結(jié)束n",pcbdatat_);done+;pcbdatat_ready0.state='F'elseprintf("進程%s就緒n",pcbdatat_);printf("-所有進程調(diào)度完畢-n");void MRLA()int i,j,temp,l,temp_num,temp_num2;double k;int time=0; /系統(tǒng)時間int done=0; /已完成的進程int t_ready10;int queue10; /進程對應的隊列int qtime10; /進

26、程對應的時間片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+)if(orderi>orderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf("-多級反饋算法調(diào)度：搶占式，時間片大小為2-n");for(i=0;i<num3;i+)t_r

27、eadyi=readyi;time=order0;for(l=0;done<num3;l+)/判斷到達的進程數(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+) /按隊列優(yōu)先級排序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("隊列%d中的進程%s占用CPU,",queue0, pcbdata3t_);printf("正在運行n ");_sleep(1);if(

29、!qtime0) /判斷是否有未用完的時間片qtime0=pow(2,queue0);elseprintf("繼續(xù)使用時間片，");for(i=1;i<qtime0;i+)time+;for(j=0;j<num3&&pcbdata3readyj.time_start<=time;j+)temp_num2=j+1;/判斷是否有進程進入比本進程更高優(yōu)先級的隊列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ā)生搶占，使用時間片%d，剩余時間片%d，返回隊列尾部n",i,qtime0);elseprintf("時間片使用完，所需時間%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("使用時間%d,還需時間%d,進程%s結(jié)束n",qtime0, pcbdata3t_ready0.time_left,pcbdata3t_);done+;pcbdata3t_ready0.state='F'elseprintf("使用時間%d,還需時間%d,進程%s進入隊列%d就緒n",qtime0,pcbdata3t_ready0.time_lef

32、t,pcbdata3t_,+queue0);qtime0=0;for(j=1;j<temp_num2;j+) /將執(zhí)行的程序返回隊尾排隊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("-所有進程調(diào)度完畢-n");int main()int i=0,sch=99;while(sch!=0)printf("n

33、請選擇其中一種調(diào)度算法：n");printf("(1)先來先服務FCFSn");printf("(2)短作業(yè)優(yōu)先SJFn");printf("(3)高響應比HRFn");printf("(4)時間片輪轉(zhuǎn)Timeslicen");printf("(5)多級反饋隊列MRLAn");printf("(0)退出n");printf("請輸入上述一個數(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("標識符-%d,狀態(tài)-%c,到達時間-%dn",pr->id,pr->state,pr->time_start);printf("服務時間-%d,剩余運行時間-%d,已用時間-%dn",pr->time_need,pr->time_left,pr->time_used);printf("-n&quo