1、實(shí)驗(yàn)報(bào)告二進(jìn)程調(diào)度算法的設(shè)計(jì)姓名：xxxx 學(xué)號(hào)：xxxxx 班級(jí)：xxxx、實(shí)習(xí)內(nèi)容? 實(shí)現(xiàn)短進(jìn)程優(yōu)先調(diào)度算法（SPF? 實(shí)現(xiàn)時(shí)間片輪轉(zhuǎn)調(diào)度算法（RR二、實(shí)習(xí)目的? 通過(guò)對(duì)進(jìn)程調(diào)度算法的設(shè)計(jì)，深入理解進(jìn)程調(diào)度的原理。? 進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。? 進(jìn)程調(diào)度分配處理機(jī)，是控制協(xié)調(diào)進(jìn)程對(duì)CPU的競(jìng)爭(zhēng)，即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把 CPU的使用權(quán)交給被選中的進(jìn)程。三、實(shí)習(xí)題目1.先來(lái)先服務(wù)（FCFS調(diào)度算法? 原理：每次調(diào)度是從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入就緒隊(duì)列的進(jìn)程，把處理器分 配給該進(jìn)程，使之得到執(zhí)行。該進(jìn)程一旦占有了

2、處理器，它就一直運(yùn)行下去，直到 該進(jìn)程完成或因發(fā)生事件而阻塞，才退出處理器。? 將用戶作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊(duì)列，并按照先來(lái)先 服務(wù)的方式進(jìn)行調(diào)度處理，是一種最普遍和最簡(jiǎn)單的方法。它優(yōu)先考慮在系統(tǒng)中等 待時(shí)間最長(zhǎng)的作業(yè)，而不管要求運(yùn)行時(shí)間的長(zhǎng)短。? 按照就緒進(jìn)程進(jìn)入就緒隊(duì)列的先后次序進(jìn)行調(diào)度，簡(jiǎn)單易實(shí)現(xiàn)，利于長(zhǎng)進(jìn)程，CPU2.繁忙型作業(yè)，不利于短進(jìn)程，排隊(duì)時(shí)間相對(duì)過(guò)長(zhǎng)。按進(jìn)程到達(dá)的時(shí)間來(lái)排序。進(jìn)程調(diào)度按一定時(shí)間片（q）輪番運(yùn)行各個(gè)進(jìn)程? 進(jìn)程按到達(dá)時(shí)間在就緒隊(duì)列中排隊(duì)，調(diào)度程序每次把CPU分配給就緒隊(duì)列首進(jìn)程使用一個(gè)時(shí)間片，運(yùn)行完一個(gè)時(shí)間片釋放CPU排到就緒隊(duì)列末尾參

3、加下一輪調(diào)度,CPU分配給就緒隊(duì)列的首進(jìn)程。新進(jìn)程就緒隊(duì)列度*匾理機(jī)時(shí)間片用完 喚醒I阻塞隊(duì)列阻塞? 固定時(shí)間片輪轉(zhuǎn)法：1所有就緒進(jìn)程按FCFS規(guī)則排隊(duì)。2 處理機(jī)總是分配給就緒隊(duì)列的隊(duì)首進(jìn)程。3如果運(yùn)行的進(jìn)程用完時(shí)間片，則系統(tǒng)就把該進(jìn)程送回就緒隊(duì)列的隊(duì)尾，重新排隊(duì)。4因等待某事件而阻塞的進(jìn)程送到阻塞隊(duì)列。5系統(tǒng)把被喚醒的進(jìn)程送到就緒隊(duì)列的隊(duì)尾。? 可變時(shí)間片輪轉(zhuǎn)法：1進(jìn)程狀態(tài)的轉(zhuǎn)換方法同固定時(shí)間片輪轉(zhuǎn)法。2響應(yīng)時(shí)間固定，時(shí)間片的長(zhǎng)短依據(jù)進(jìn)程數(shù)量的多少由T=NX (q+t)給出的關(guān)系調(diào)整。3根據(jù)進(jìn)程優(yōu)先級(jí)的高低進(jìn)一步調(diào)整時(shí)間片，優(yōu)先級(jí)越高的進(jìn)程，分配的時(shí)間片越長(zhǎng)。3. 算法類型：先米先眼務(wù)(F

4、CFS)調(diào)度算法廣簡(jiǎn)單的調(diào)度極X短進(jìn)鐘輪轉(zhuǎn)注等時(shí)閶片輪轉(zhuǎn)不等時(shí)聞片輪轉(zhuǎn)優(yōu)先權(quán)法槍占式優(yōu)先楓 非搶占式優(yōu)先駅 特態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先叔J多瓢反橫吐列算4. 模擬程序可由兩部分組成，先來(lái)先服務(wù)(FCFS)調(diào)度算法，時(shí)間片輪轉(zhuǎn)。流程圖如圖所示:en um Statusru nnin g,ready,block用枚舉類型來(lái)列舉進(jìn)程的狀態(tài)enum Algorithmspf,rr用枚舉類型來(lái)列舉兩種進(jìn)程調(diào)度算法typedef class PCB/define PCB class which storein formatio n of PCB 進(jìn)程號(hào)、已經(jīng)運(yùn)行時(shí)間、還需要的public:int id,cput

5、ime,alltime,startblock,blocktime;/進(jìn)程的狀態(tài)時(shí)間、何時(shí)開(kāi)始阻塞及阻塞時(shí)間的變量Status state;/class PCB *n ext;/指向下一個(gè)進(jìn)程的指針PCB() PCB,*PCBptr,*PCBpp;定義類類型來(lái)存儲(chǔ)一個(gè)進(jìn)程的相關(guān)信息，并用鏈表的方式來(lái)存放進(jìn)程五、實(shí)現(xiàn)代碼為:#define MAX 100#include<stdio.h>#include<stdlib.h>int m,b,n,x;int rt10; /到達(dá)時(shí)間int st10; /服務(wù)時(shí)間int ct10; /完成時(shí)間int cyt10; /周轉(zhuǎn)時(shí)間ai-=

6、t;b+=t;cnti=cnti+1;ncalledprintf("processname:%dnumber:%d nendtime:%dn",i+1,cnti,b,ai);printf("*ntime:%dnleft");RR算法 *void RR(int N)int i,t,k;int aMAX;存放進(jìn)程的剩余時(shí)間int cntMAX; 存放進(jìn)程調(diào)度次數(shù)printf("pleaseinput the time else b=b+ai;cnti=cnti+1;ai=0;printf("processpiece(t):");

7、scanf("%d", &t);name:%dncalled number:%d nend time:%dnleft time:%d n",i+1,cnti,b,ai);for(i=O;i<N;i+)*n");printf("printf("please input the serive time*of process %d:n",i+1);scanf("%d", &ai); cnti=0;k=1;else continue;for(i=0;i<N;i+)if(ai!=0)wh

8、ile(k)for(i=0;i<N;i+)if(ai!=0) if(ai>=t) k=1;break;elsecontinue;if(i>=N)k=0; printf("all donen");the process have been*SPF算法 */定義進(jìn)程結(jié)構(gòu)體struct proint num; / 進(jìn)程號(hào)int arriveTime; /int service; /struct pro *next;/函數(shù)聲明struct pro* creatList();的到達(dá)時(shí)間排列到達(dá)時(shí)間執(zhí)行時(shí)間創(chuàng)建鏈表，按照進(jìn)程void insert(struct pro

9、 *head,struct pro *s);/插入節(jié)點(diǎn)struct pro* searchByAT(struct pro *head,intAT); /查找第一個(gè)到達(dá)時(shí)間大于 AT的節(jié)點(diǎn)，返回 其前一個(gè)指針void run(struct pro *head);/按短進(jìn)程優(yōu)先算法調(diào)度，并輸岀其運(yùn)行情況void del(struct pro* p);/刪除 p 的下一個(gè)節(jié)點(diǎn)int getCount(struct pro *head,int time);/查看當(dāng)前就緒隊(duì)列中的進(jìn)程數(shù)name(number):n");scanf("%d",&(s->num);

10、printf("pleaseinput process arrivetimen");scanf("%d",&(s->arriveTime);printf("pleaseinput servicetimen");scanf("%d",&(s->service);s->next=NULL;insert(head,s);return head;void insert(struct pro *head,struct pro *s)/插入節(jié)點(diǎn)structpro*p=searchByAT(he

11、ad,s->arriveTime);s->next=p->next;p->next=s;return;struct pro* creatList() /進(jìn)程的到達(dá)時(shí)間排列structpro*pro*)malloc(sizeof(struct pro);struct pro* s;int i;創(chuàng)建鏈表，按照head=(structhead->next=NULL;for(i=0;i<x;i+)s=(structpro*)malloc(sizeof(struct pro);printf("plaeseinputprocessstruct pro* sea

12、rchByAT(struct pro *head,int AT)/查找第一個(gè)到達(dá)時(shí)間大于 AT的節(jié)點(diǎn)，返回其前 一個(gè)指針struct pro *p,*q;p=head;q=head->next;while(q!=NULL&&q->arriveTime<=AT)p=q;q=q->next;return p;void del(struct pro* p) /刪除p的下一個(gè)printf("n節(jié)點(diǎn)struct pro *tmp; tmp=p_>next; p->next=tmp->next; free(tmp);return; int

13、 getCount(struct pro *head,int time) /查看當(dāng)前就緒隊(duì)列中的進(jìn)程數(shù)int count=0;struct pro *p,*q;p=head;q=p->next;while(q!=NULL&&q->arriveTime<=time)count+;p=q;q=q->next;return count;struct pro* SPF(struct pro *head,int count)/在頭節(jié)點(diǎn)后的count個(gè)節(jié)點(diǎn)中選擇service 最小的，返回其前一個(gè)節(jié)點(diǎn)的指針int min;struct pro *p,*q,*flag

14、;p=head;q=p->next;min=q->service;flag=p; /flag記錄返回值while(count>0)if(q->service<min)min=q->service;flag=p;count-;p=q;q=q->next;return flag;void run(struct pro *head) /按短進(jìn)程優(yōu)先算法調(diào)度，并輸岀其運(yùn)行情況int time=0,count,i;struct pro *s,*t;while(head->next!=NULL) count=getCount(head,time); 查看就

15、緒隊(duì)列中的進(jìn)程數(shù)目if(count=0) /如果當(dāng)前就緒隊(duì)列中沒(méi)有進(jìn)程，時(shí)間自增time+;else if(count=1) /如果就緒隊(duì)列中只有一個(gè)進(jìn)程，則必定是第一個(gè)節(jié)點(diǎn)t=head;s=t->next;printf("processname %dn",s->num);printf("arrivetime:%dn",s->arriveTime);printf("serivetime:%dnn",s->service);printf("star time: %dn",time);time+

16、=s->service;printf("end time:%dn",time);printf("turnaroundtime:%dn",time-s->arriveTime);i=time-s->arriveTime;*");del(t);else /如果就緒隊(duì)列中的進(jìn)程數(shù)2,則在head后的count個(gè)節(jié)點(diǎn)中的短進(jìn)程優(yōu)先調(diào) 度t=SPF(head,count);s=t->next;printf("processname %dn",s->num);printf("arrivetime

17、:%dn",s->arriveTime);printf("serivetime:%dnn",s->service);printf("star time%dn",time);time+=s->service;printf("end time:%dn",time);printf("turnaroundtime:%dn",time-s->arriveTime);i=time-s->arriveTime;prin tf("*n ");del(t);/*Fcfs算法

18、 *void FCFS(int x) void input(); / 輸入數(shù)據(jù)void ordination(); /對(duì)數(shù)據(jù)按到達(dá)時(shí)間進(jìn)行排序void fcfs(); /先來(lái)先服務(wù)計(jì)算void output();/ 輸出結(jié)果printf("/* * *FCFS* */n");input(x);ordination(x);fcfs(x);output(x);void input(int x)printf("please input arrive time of the %d processes:",x);for (n=0;n<x;n+)scanf(&

19、quot;%d",&rtn);printf("please input serivce time of the %d processes:",x);for (n=0;n<x;n+)scanf("%d", &stn);void ordination(int x)int temp;for (n=0;n<x;n+)for (m=0;m<x-n-1;m+)if (rtm+1<rtm)temp=rtm+1;rtm+1=rtm;rtm=temp;temp=stm+1;stm+1=stm;stm=temp;void f

20、cfs(int x) ctO=rtO+stO;for (n=1;n<x;n+)if (ctn-1>=rtn) /考慮當(dāng)前一個(gè)進(jìn)程完成而后一個(gè)進(jìn)程還沒(méi)有到達(dá)的情況ctn=ctn-1+stn;elsectn=rtn+stn;for (n=0;n<x;n+)cytn=ctn-rtn;void output(int x)for (n=0;n<x;n+)printf("name:%dnarrivetime:%dnserive:%dnend time:%dnturnaround time:%dn",n+1,rtn,stn,ctn,cytn);void main(

21、)int swich;/選擇使用算法struct pro *head;int c=1;/選擇是否繼續(xù)for (;c=1;)printf("please input the number ofthe processes:");scanf("%d"，& x);printf("please choose method(RR:0SPF:1 FCFS:2):");scanf("%d", &swich);六、在虛擬機(jī)上的具體操作if(swich=0)RR(x);elseif(swich=1)head=creat

22、List(); printf("SPF:n"); run(head);elseif(swich=2)FCFS(x);elseprintf("input error,please input again:n");printf("continue:1 ， quit:0npleaseinput:");scanf("%d", &c);printf(" *File Edit View Ternninal Helpfeifcigubuntucd:-/os2$ qcc -o os2 os2.cos2.c:： I

23、n function *mainr:os2.<：265: warifg: return type of gin' is not 'intFIH IB七、實(shí)驗(yàn)結(jié)果RR:please input the number erf the processes：3please thoose method IRR;0 5PF；1 FCFS;2 please input please input4please input5please input3thethethethetime piece(t);3 strivetimeofprocess1:seriveserivetimetimeof

24、process2:3;process name:1 called number:1 end time：3 left timeil process name：2called number:1end time:6left time：2process rame：3called number:1end time:9left time:0草車尊 卓車呻卓斗草 車耳單車斗卓斗 草車尊單率斗卓斗 草車沖卓 草"* 卓耳牛prote-s-s rame： 1 tailed number；2 end time:16 left tine:9process rame；2 called number:2 en

25、d time:12 left time:04 »«»*«*»««« i£ *««*«-«»： all the process have been done tQntinue；l&frquit;6SPF:continue: lwquit: 6input：1input the number of the processes：3 choose method(RR:G SPF:1 FCFS:2:1 inputpleaseplease pleaseproce

26、ssname(number);processarrivetimeservicetimeprocessname(number):proc皂55arrivetimeservi匚已timeprocessnameinumber):processarrivetimeservicetimeplae5einputplease2please input plaese input2please input 0please input1plaese input3please input4please input1SPF:process arrive time:0derive time：7 itar time WOend time:7turnaround time:?事車拿掌字羋當(dāng)搴卷車字掌事羋當(dāng)字學(xué)字字掌字學(xué)當(dāng)字學(xué)卓字拿字字字 process nameMni3arrive tinie :4i&nve time： Itiine7 end tiine:8 turnaround time:4