1、深 圳 大 學 實 驗 報 告 課程名稱： 操作系統(co zu x tn) 實驗(shyn)項目名稱： 處理機調度(diod) 學院： 計算機與軟件學院 專業： 軟件工程 指導教師： 報告人： 學號： 班級： 實驗時間： 2013年 5 月 7 日 實驗報告提交時間： 2013年 5 月 22 日 教務處制一、實驗目的與要求：實驗目的: 模擬在單處理器多進程操作系統的CPU調度。幫助學生掌握多種CPU調度算法的知識原理和運作機制。本實驗為模擬實驗，不要求實現真正的進程創建與進程調度。主要實現各種調度算法。實驗要求:閱讀理解例程，掌握例程的運作流程。運行例程，理解先來先服務算法的調度原理和運行

2、結果。參考先來先服務算法，嘗試實現其他四種調度算法：短作業優先、高響應比、時間片輪轉、多級反饋隊列。要求至少實現一種算法。除了多級反饋隊列，其他算法采用非搶占調度短作業優先算法使用例題一數據或程序內置數據，要求運行結果給出調度順序、完成時間、周轉時間、帶權周轉時間高響應比算法使用例題二的數據，要求運行結果給出調度順序、完成時間、周轉時間、帶權周轉時間時間片輪轉算法可以使用程序內置數據，要求運行結果給出每個時間片是被哪個進程使用，每個進程完成時，要修改狀態并輸出提示。多級反饋隊列算法使用例題三的數據，要求運行結果給出正確的進程調度順序和過程描述。二、方法、步驟：(說明程序相關的算法原理或知識內容

3、，程序設計的思路和方法，可以用流程圖表述，程序主要數據結構的設計、主要函數之間的調用關系等)先來先服務算法：按到達時間先后，選擇最先來的作業最先執行實現思想：對作業的到達時間按大小進行排序，然后按順序執行短作業優先算法： 在后備隊列中，選擇服務時間最短的作業最先執行實現思想： 對作業按到達時間排序，接著對到達的作業，即后備隊列中的作業按服務時間排序，取服務時間最小的作業最先執行高響應比算法：對作業的優先權（響應時間/要求服務時間）進行計算，對優先權最高的最先執行實現實現： 計算后備隊列中作業的優先權，并排序，優先權最高的最先執行時間片輪轉算法：將所有就緒進程按先來先服務排成隊列，把CPU分配給

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

5、間片內仍未完成，再降級到第三個隊列實現思想：設置多個就緒隊列，各個隊列優先級逐個降低，各個隊列時間片逐個增加，優先級越高的隊列執行時間片就越短，一般時間片按倍增規則， 例如，第二隊列的時間片要比第一個隊列的時間片長一倍，第i+1個隊列的時間片要比第i個隊列的時間片長一倍，整合了時間片、 FCFS、優先級三種機制。三實驗過程及內容：(對程序代碼進行說明和分析，越詳細越好，代碼排版要整齊，可讀性要高)#include stdio.h#include/#include#include#include/#define NULL 0#define getpch(type)(type*)malloc(si

6、zeof(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; /進程狀態;/*系統函數void _sleep(int n)clock_t goal;goal=(clock_t)n*CLOCKS_PER_SEC+clock();while(goalclock();char _keygo()char c;pr

7、intf(按任意鍵繼續n);c=getchar();return c;/*用戶函數int time_unit=2;int num=5; /實際進程數量PCB pcbdata10=/例程內置數據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,0,R,1004,E,4,4,4,0,R,;int num1=4;PCB pcbdata110=/例題一數據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,;i

8、nt num2=4;PCB pcbdata210=/例題二數據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=/例程三數據1000,A,0,7,7,0,R,1001,B,5,4,4,0,R,1002,C,7,13,13,0,R,1003,D,12,9,9,0,R,;int ready10; /就緒隊列，存放進程在pcbdata中的位置int order10; /記錄排序使用哪個數值作為排序對象void intput()int i;pr

9、intf(進程總數為：);scanf(%d,&num);for(i=0;inum;i+)pcbdatai.id=1000+i;printf(輸入第%d個進程名：,i+1);scanf(%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;pcbdata

10、i.state=R;/*調度函數void FCFS()int i,j,temp;double k;for(i=0;inum;i+)orderi=pcbdatai.time_start;readyi=i;for(i=0;inum;i+) /按到達時間排序for(j=i+1;jorderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf(-先來先服務算法調度：非搶占，無時間片-n);temp=pcbdataready0.time_start;for(i=0;inum;i+)prin

11、tf(第%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,周轉時間-%d,帶權周轉時間-%.1fn,temp,j,k);printf(-所有進程調度完畢-n);void SJF()int i,j,temp,l,temp_num;double k;int time=0;for(i=

12、0;inum1;i+)orderi=pcbdata1i.time_start;readyi=i;for(i=0;inum1;i+) /按到達時間排序for(j=i+1;jorderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf(-短作業算法調度：非搶占，無時間片-n);int t_ready10;/就緒隊列，存放進程在pcbdata中的位置int t_order10; /記錄排序使用哪個數值作為排序對象for(i=0;inum1;i+)t_orderi=pcbdata1re

13、adyi.time_need;/服務時間作為排序對象t_readyi=readyi;time=order0;for(l=0;lnum1;l+)/判斷到達的進程數，用temp_num存放for(i=0;inum&pcbdata1readyi.time_start=time;i+)temp_num=i+1;/把到達的進程按服務時間大小進行排序for(i=0;itemp_num;i+)for(j=i+1;jt_orderj&t_orderj!=0|t_orderi=0)temp=t_orderi;t_orderi=t_orderj;t_orderj=temp;temp=t_readyi;t_read

14、yi=t_readyj;t_readyj=temp;printf(第%d個進程-%s,l+1,pcbdata1t_);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,周轉時間-%d,帶權周轉時間-%.1fn,time,j,k);printf(-所有進程調度完畢-n);void HRF()

15、int i,j,temp,l,temp_num;double k;int time=0;for(i=0;inum2;i+)orderi=pcbdata2i.time_start;readyi=i;for(i=0;inum2;i+) /按到達時間排序for(j=i+1;jorderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf(-高響應比算法調度：非搶占，無時間片-n);int t_ready10;int t_order10;for(i=0;inum2;i+)t_orderi

16、=1;t_readyi=readyi;time=order0;for(l=0;lnum2;l+)/判斷到達進程數for(i=0;inum&pcbdata2readyi.time_start=time;i+)temp_num=i+1;for(i=0;itemp_num;i+) /計算已到達進程的優先權if(t_orderi)t_orderi=(time-pcbdata2t_readyi.time_start+ pcbdata2t_readyi.time_need)/pcbdata2t_readyi.time_need;for(i=0;itemp_num;i+) /按優先權排序for(j=i+1;

17、jtemp_num;j+)if(t_orderit_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);time+=pcbdata2t_ready0.time_need;j=time-pcbdata2t_ready0.time_start;k=(float)j/pcbdata2t_ready

18、0.time_need;t_order0=0;printf(完成時間-%d,周轉時間-%d,帶權周轉時間-%.1fn,time,j,k);printf(-所有進程調度完畢-n);void Timeslice()int i,j,temp,l,temp_num;double k;int time=0;int done=0;for(i=0;inum;i+)orderi=pcbdatai.time_start;readyi=i;for(i=0;inum;i+) /按到達時間排序for(j=i+1;jorderj)temp=orderi;orderi=orderj;orderj=temp;temp=re

19、adyi;readyi=readyj;readyj=temp;printf(-時間片輪轉算法調度：非搶占，時間片大小為2-n);int t_ready10;for(i=0;inum;i+)t_readyi=readyi;time=order0;for(l=0;donenum;l+)/判斷到達的進程數for(i=0;inum&pcbdatareadyi.time_start=time;i+)temp_num=i+1;if(time!=order0)/將已使用時間片的進程，即第一個移到隊列末尾for(i=1;itemp_num;i+)temp=t_readyi;t_readyi=t_readyi-

20、1;t_readyi-1=temp;if(pcbdatat_ready0.state!=F)printf(第%d個時間片被進程%s使用,l+1,pcbdatat_);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);/判斷進程是否結束if(pcbda

21、tat_ready0.time_left=0)printf(進程%s結束n,pcbdatat_);done+;pcbdatat_ready0.state=F;elseprintf(進程%s就緒n,pcbdatat_);printf(-所有進程調度完畢-n);void MRLA()int i,j,temp,l,temp_num,temp_num2;double k;int time=0; /系統時間int done=0; /已完成的進程int t_ready10;int queue10; /進程對應的隊列int qtime10; /進程對應的時間片fo

22、r(i=0;inum3;i+)orderi=pcbdata3i.time_start;readyi=i;queuei=1;qtimei=0;for(i=0;inum3;i+) /按到達時間排序for(j=i+1;jorderj)temp=orderi;orderi=orderj;orderj=temp;temp=readyi;readyi=readyj;readyj=temp;printf(-多級反饋算法調度：搶占式，時間片大小為2-n);for(i=0;inum3;i+)t_readyi=readyi;time=order0;for(l=0;donenum3;l+)/判斷到達的進程數for(

23、i=0;inum3&pcbdata3readyi.time_start=time;i+)temp_num=i+1;if(time!=order0)for(i=0;itemp_num;i+) /按隊列優先級排序for(j=1;jqueuej&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.

24、state!=F)printf(隊列%d中的進程%s占用CPU,queue0, pcbdata3t_);printf(正在運行n );_sleep(1);if(!qtime0) /判斷是否有未用完的時間片qtime0=pow(2,queue0);elseprintf(繼續使用時間片，);for(i=1;iqtime0;i+)time+;for(j=0;jnum3&pcbdata3readyj.time_startqueuetemp_num2-1& pcbdata3t_ready0.time_left-i0)qtime0-=i;break;if(temp_num!=temp

25、_num2&queue0queuetemp_num2-1&pcbdata3t_ready0.time_left-i0)printf(發生搶占，使用時間片%d，剩余時間片%d，返回隊列尾部n,i,qtime0);elseprintf(時間片使用完，所需時間%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(使用時間%d,還需時間%

26、d,進程%s結束n,qtime0, pcbdata3t_ready0.time_left,pcbdata3t_);done+;pcbdata3t_ready0.state=F;elseprintf(使用時間%d,還需時間%d,進程%s進入隊列%d就緒n,qtime0,pcbdata3t_ready0.time_left,pcbdata3t_,+queue0);qtime0=0;for(j=1;jname);printf(標識符-%d,狀態-%c,到達時間-%dn,pr-id,pr-state,pr-time_start);printf(服務時間-%d,剩余運行時間-%d,已用時間-%dn,pr-time_need,pr-time_left,pr-time_used);printf(-n);void dis_pcb_all()int i;printf(*當前所有進程狀態*n);for(i=0;inum;i+)dis_pcb(&pcbdatai);void dis_ready()int i;printf(當前就緒隊列為：);for(i=0;inum-1;i+)printf(%s-,);printf(%sn,pcbdataord