可搶占調(diào)度算法(在V下編譯通過(guò))

1、可搶占調(diào)度算法(在VC下編譯通過(guò))#include #include #include #include #include #include const int FINISH=0;/完成狀態(tài)const int RUNNING=1;/運(yùn)行狀態(tài)const int READY=2;/就緒狀態(tài)const int PCBNUM=3;/進(jìn)程個(gè)數(shù)typedef struct long pid;char pname10;int pstate;int pneedtime;int ptime;int priority;pcbs;/pcb結(jié)構(gòu)class pcbnode;/隊(duì)列結(jié)點(diǎn)class pcbnodepubli

2、c:pcbs *pcb;pcbnode *link;pcbnode();pcbnode();int run();/運(yùn)行操作int runend();/運(yùn)行結(jié)束？int insertnode(pcbnode *p,pcbnode *q);/在q后插入結(jié)點(diǎn)pint deletenode(pcbnode *p,pcbnode *q);/刪除p結(jié)點(diǎn)，q為p的前驅(qū)int addnode(pcbnode *p);/增加結(jié)點(diǎn);pcbnode:pcbnode()pcb=0;link=0;pcbnode:pcbnode()if(link)delete link;if(pcb)pcb-pstate=FINISH;

3、int pcbnode:run()pcb-pstate=RUNNING;+(pcb-ptime);pcb-priority-;/優(yōu)先級(jí)降低return 0;int pcbnode:runend()return (pcb-pneedtimeptime);int pcbnode:addnode(pcbnode *p)pcbnode *q;q=this;p-pcb-pstate=READY;while(q-link)q=q-link;q-link=p;return 0;int pcbnode:insertnode(pcbnode *p,pcbnode *q)p-link=q-link;q-link=

4、p;return 0;int pcbnode:deletenode(pcbnode *p,pcbnode *q)q-link=p-link;p-link=0;return 0;int randInt( int seed)/隨機(jī)函數(shù)：產(chǎn)生不大于seed的正整數(shù)int r;r=rand();while(rseed|rpid=order;strcpy(pcb-pname, proc);_itoa(order,buf,10);strcat(pcb-pname,buf);pcb-pneedtime=randInt(5);/進(jìn)程需要時(shí)間pcb-ptime=0;pcb-priority=randInt(10

5、);/優(yōu)先度void pprint(pcbs *pcb, int count)/打印進(jìn)程狀態(tài)ofstream ofs(result.txt, ios:out|ios:app);coutidtnametstattneedtruntimetpriendl;ofsidtnametstattneedtruntimetpriendl;for(int i=0;icount;i+)coutpcbi.pidt pcbi.pnamet;ofs pcbi.pidt pcbi.pnamet;switch(pcbi.pstate) case RUNNING:coutRU;ofsRU;break;case READY:

6、coutRE;ofsRE;break;case FINISH:coutFI;ofsFI;break;couttpcbi.pneedtime;ofstpcbi.pneedtime;couttpcbi.ptime;ofstpcbi.ptime;couttpcbi.priority;ofstpcbi.priority;coutendl;ofsendl;void priority(pcbs *pcb, int pcbsnum)/可搶占的優(yōu)先調(diào)度/* 從就緒隊(duì)列中取出最優(yōu)先的進(jìn)程送到運(yùn)行隊(duì)列* 每運(yùn)行一次，正在運(yùn)行的進(jìn)程優(yōu)先數(shù)減1，等待的進(jìn)程優(yōu)先數(shù)加1* 如果就緒隊(duì)列中的最大優(yōu)先數(shù)進(jìn)程的優(yōu)先數(shù)大于正在運(yùn)

7、行的優(yōu)先數(shù)，* 則運(yùn)行的進(jìn)程讓出cpu,排到就緒隊(duì)列的尾部，將最大優(yōu)先數(shù)的進(jìn)程送進(jìn)* 運(yùn)行隊(duì)列。*/pcbnode running,ready,blocked;pcbnode *p,*f,*front;pcbnode *q;/*將進(jìn)程表中的進(jìn)程加到就緒隊(duì)列中*/for(int i=0;ipcb=pcb+i;ready.addnode(p);while(ready.link|running.link)/判斷將運(yùn)行隊(duì)列中的進(jìn)程是否結(jié)束if(running.link)if(running.link-runend() /運(yùn)行結(jié)束?p=running.link;p-pcb-priority=0;runn

8、ing.link=0;delete p;/尋找最大的一個(gè)優(yōu)先級(jí)p=ready.link;q=p;f=&ready;front=f;if(p)int maxpri=p-pcb-priority;while(p)if(p-pcb-prioritymaxpri)maxpri=p-pcb-priority;front=f;q=p;f=p;p=p-link;/如果最大優(yōu)先級(jí)大于正在運(yùn)行的優(yōu)先級(jí)則強(qiáng)占cpu/p=running.link;if(q)if(p)if(p-pcb-prioritypcb-priority)ready.addnode(p);running.deletenode(p, &runni

9、ng);p-pcb-pstate=READY;running.addnode(q);ready.deletenode(q,front);q-pcb-pstate=RUNNING;elserunning.addnode(q);ready.deletenode(q,front);q-pcb-pstate=RUNNING;/* * 運(yùn)行進(jìn)程 */p=running.link;q=&running;if(p)int r;r=p-run();/運(yùn)行進(jìn)程 /動(dòng)態(tài)計(jì)算就緒隊(duì)列優(yōu)先級(jí)p=ready.link;while(p)(p-pcb-priority)+;p=p-link;/print proc stat

10、epprint(pcb,pcbsnum);void main(int argc, char* argv)pcbs *pcblist;/進(jìn)程表remove(result.txt);pcblist=new pcbsPCBNUM;/為進(jìn)程表分配空間for(int i=0; iPCBNUM; i+)newpcb(pcblist+i),i);/產(chǎn)生進(jìn)程pprint(pcblist,PCBNUM);/打印進(jìn)程priority(pcblist,PCBNUM);/可強(qiáng)占優(yōu)先法delete pcblist;/釋放進(jìn)程空間用C語(yǔ)言編寫(xiě)如下：實(shí)驗(yàn)(一)一， 實(shí)驗(yàn)內(nèi)容： 三，實(shí)驗(yàn)內(nèi)容（任選一個(gè)）1、按優(yōu)先權(quán)調(diào)度算法實(shí)

11、現(xiàn)處理機(jī)調(diào)度的程序； PCB內(nèi)容：要求進(jìn)程名/PID；要求運(yùn)行時(shí)間（單位時(shí)間）；優(yōu)先權(quán)；l例如：5狀態(tài)：登記進(jìn)程當(dāng)前狀態(tài)（就緒、執(zhí)行、阻塞）PCB指針；指向本進(jìn)程隊(duì)列中下個(gè)進(jìn)程的PCB1、可隨時(shí)輸入若干進(jìn)程，并按優(yōu)先權(quán)排序；2、從就緒隊(duì)首選進(jìn)程運(yùn)行：優(yōu)先權(quán)-1，要求運(yùn)行時(shí)間-1，要求運(yùn)行時(shí)間=0時(shí)，撤銷(xiāo)該進(jìn)程3、重新排序，進(jìn)行下輪調(diào)度；4、每次調(diào)度后，顯示各進(jìn)程狀態(tài)。七，源程序清單：#include #include #include #include #define NULL 0#define FINISH 1#define RUNNING 2#define READY 3struct pc

12、bsint pid;int pstate;int pneedtime;int ptime;int priority;struct pcbs *link;pcbs;struct pcbs *running,*ready;struct pcbs *pcblist;int PCBNUM;FILE *fp;void run(struct pcbs *p)p-pstate=RUNNING;p-ptime=p-ptime+1;if(PCBNUM!=1)p-priority=p-priority-1;int runend(struct pcbs *p)if(p-ptime=p-pneedtime)p-pst

13、ate=FINISH;p-priority=NULL;return 1;elsereturn NULL;struct pcbs *deletenode(struct pcbs *p,struct pcbs *q)struct pcbs *f,*g;f=p;g=q;if(p=q)f=f-link;if(p-link) p-link=NULL;return f;else while(f-link!=g) f=f-link; f-link=g-link; if(g-link) g-link=NULL; return p;struct pcbs *addnode(struct pcbs *q,stru

14、ct pcbs *p)struct pcbs *g,*f,*d;f=q;d=p;if(f=NULL)f=d;d-pstate=READY;return f;elseg=q;while(q-link) q=q-link;d-pstate=READY;q-link=d;return g;int randInt(int seed)int r;r=rand();while(rseed|rpid); fprintf(fp,%dt,f-pid); switch(f-pstate) case RUNNING: printf(RUt); fprintf(fp,%st,RU); break; case READ

15、Y: printf(REt); fprintf(fp,%st,RE); break; case FINISH: fprintf(fp,%st,FI); printf(FIt); break; default: printf( t); fprintf(fp,%st, ); printf(%dt,f-pneedtime); fprintf(fp,%dt,f-pneedtime); printf(%dt,f-ptime); fprintf(fp,%dt,f-ptime); printf(%dn,f-priority); fprintf(fp,%dn,f-priority); printf(n); f

16、=f-link; i+;if(i=PCBNUM|i=1)fprintf(fp,%sn,=);void priority()struct pcbs *addnode();void pprint();void run();struct pcbs *deletenode();int runend();int i=0;int maxpri;struct pcbs *p,*q;struct pcbs *f;if(PCBNUM=1) running=pcblist; while(!runend(running) run(running); pprint(running); pprint(pcblist);

17、else while(ipriority=0; ready=addnode(ready,f); f-pstate=FINISH; running=deletenode(running,f); i+; q=ready; p=ready; maxpri=p-priority; while(p) if(p-priority)maxpri) maxpri=p-priority; f=p; q=p; p=p-link; p=running; if(p&q&(p-priority)priority) p-pstate=READY; q-pstate=RUNNING; ready=addnode(ready

18、,p); running=deletenode(running,p); running=addnode(running,q); ready=deletenode(ready,q); else if(!runend(q)&running=NULL) q-pstate=RUNNING; running=addnode(running,q); ready=deletenode(ready,q); p=ready; while(p) if(p-pstate!=FINISH)&(p-pstate!=RUNNING)(p-priority)+; p=p-link; if(running|ready) if

19、(ready) pprint(ready); if(running)run(running);pprint(running);p=ready; main( )int i,j=0;struct pcbs *p=NULL,*q=NULL;void priority();void pprint();struct pcbs *addnode();int randInt();if(fp=fopen(result1.txt,a)=NULL)printf(cannot open file!n);exit(1);printf(nenter pcbnum(ensure pcbnum0):);scanf(%d,&

20、PCBNUM);while(PCBNUM0) /*可隨時(shí)加入進(jìn)程*/for(i=0;ilink=NULL; p-pid=i+j; p-pneedtime=randInt(10); p-ptime=0; p-priority=randInt(10); if (q=NULL) pcblist=q=p; p=NULL; else q-link=p;q=q-link;p=NULL;running=NULL;pprint(pcblist);q=pcblist;while(q) ready=addnode(ready,q); /*將進(jìn)程加入后備隊(duì)列*/ q=deletenode(q,q);pprint(r

21、eady);priority();for(i=0;ilink; free(p); j=j+PCBNUM;printf(nenter pcbnum:);scanf(%d,&PCBNUM);fclose(fp); 實(shí)驗(yàn)（二） 一， 實(shí)驗(yàn)內(nèi)容：實(shí)現(xiàn)主存儲(chǔ)器的分配和回收。二， 實(shí)驗(yàn)題目：在可變分區(qū)管理方式下，用最先適應(yīng)算法實(shí)現(xiàn)主存空間的分配和回收。注：提示及要求： 1、自行假設(shè)主存空間大小，預(yù)設(shè)操作系統(tǒng)所占大小并構(gòu)造未分分區(qū)表； 表目?jī)?nèi)容：起址、長(zhǎng)度、狀態(tài)（未分/空表目）2、結(jié)合實(shí)驗(yàn)一，PCB增加為： PID，要求運(yùn)行時(shí)間，優(yōu)先權(quán)，狀態(tài)，所需主存大小，主存起始位置，PCB指針3、采用最先適應(yīng)算法分配主

22、存空間；4、進(jìn)程完成后，回收主存，并與相鄰空閑分區(qū)合并。三， 實(shí)驗(yàn)原理：目前的內(nèi)存分區(qū)管理辦法分為兩種類(lèi)型：連續(xù)分配方式和離散分配方式，其中連續(xù)分配方式又存在兩種形式：靜態(tài)分區(qū)分配和動(dòng)態(tài)分區(qū)分配。這次實(shí)驗(yàn)采用的是連續(xù)分配算法中的動(dòng)態(tài)分區(qū)分配算法中的最佳適應(yīng)算法：其原理如下：每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿足要求，又是最小的空閑分區(qū)分配給作業(yè)，實(shí)現(xiàn)對(duì)分配空間的合理利用。三、 程序清單：#include #include #include #include #define NULL 0#define FINISH 1#define RUNNING 2#define READY 3#define N

23、UM 50struct pcbsint pid;int pstate;int pneedtime;int ptime;int priority;int needsize;int startaddress;struct pcbs *link;pcbs;struct pcbs *running,*ready;struct pcbs *pcblist;int PCBNUM;FILE *fp;struct wordint flag;int size;int address;struct word *next,*llink;struct pcbs *space;word;void run(struct

24、pcbs *p) /*運(yùn)行進(jìn)程*/p-pstate=RUNNING;p-ptime=p-ptime+1;if(PCBNUM!=1)p-priority=p-priority-1;int runend(struct pcbs *p) /*判斷進(jìn)程是否運(yùn)行完畢*/if(p-ptime=p-pneedtime)p-pstate=FINISH;p-priority=NULL;return 1;elsereturn NULL;struct pcbs *deletenode(struct pcbs *p,struct pcbs *q) /*刪除節(jié)點(diǎn)*/struct pcbs *f,*g;f=p;g=q;i

25、f(p=q) /*要?jiǎng)h除節(jié)點(diǎn)是頭節(jié)點(diǎn)*/f=f-link;if(p-link) p-link=NULL;return f;else /*要?jiǎng)h除節(jié)點(diǎn)不是頭節(jié)點(diǎn)*/ while(f-link!=g) f=f-link; f-link=g-link; if(g-link) g-link=NULL; return p;struct pcbs *addnode(struct pcbs *q,struct pcbs *p) /*增加節(jié)點(diǎn)*/struct pcbs *g,*f,*d;f=q;d=p;if(f=NULL) /*把節(jié)點(diǎn)增加到隊(duì)列的隊(duì)首*/f=d;d-pstate=READY;return f;e

26、lseg=q;while(q-link) q=q-link;d-pstate=READY;q-link=d;return g;int randInt(int seed) /*產(chǎn)生不大于seed的隨機(jī)數(shù)*/int r;r=rand();while(rseed|rpid); fprintf(fp,%dt,f-pid); switch(f-pstate) case RUNNING: printf(RUt); fprintf(fp,%st,RU); break; case READY: printf(REt); fprintf(fp,%st,RE); break; case FINISH: fprin

27、tf(fp,%st,FI); printf(FIt); break; default: printf( t); fprintf(fp,%st, ); printf(%dt,f-pneedtime); fprintf(fp,%dt,f-pneedtime); printf(%dt,f-ptime); fprintf(fp,%dt,f-ptime); printf(%dt,f-priority); fprintf(fp,%dt,f-priority); printf(%dtt,f-needsize); fprintf(fp,%dtt,f-needsize); printf(%dn,f-starta

28、ddress); fprintf(fp,%dn,f-startaddress); fprintf(fp,n); printf(n); f=f-link; i+;if(i=PCBNUM|(i=1&p!=ready)fprintf(fp,%sn,-);printf(-);void priority() /*可搶占優(yōu)先調(diào)度算法*/struct pcbs *addnode();void pprint();void run();struct pcbs *deletenode();int runend();int i=0;int maxpri;struct pcbs *p,*q;struct pcbs *

29、f;if(PCBNUM=1) running=pcblist; while(!runend(running) run(running); pprint(running); pprint(pcblist);else while(ipriority=0; ready=addnode(ready,f); f-pstate=FINISH; running=deletenode(running,f); i+; q=ready; p=ready; maxpri=p-priority; while(p) /*動(dòng)態(tài)尋找最大的一個(gè)優(yōu)先級(jí)*/ if(p-priority)maxpri&p-pstate!=FINI

30、SH) maxpri=p-priority; f=p; q=p; p=p-link; p=running; if(p&q&(p-priority)priority) /*如果最大優(yōu)先級(jí)大于正在運(yùn)行的優(yōu)先級(jí)則強(qiáng)占cpu*/ p-pstate=READY; q-pstate=RUNNING; ready=addnode(ready,p); running=deletenode(running,p); running=addnode(running,q); ready=deletenode(ready,q); else if(!runend(q)&running=NULL) q-pstate=RUN

31、NING; running=addnode(running,q); ready=deletenode(ready,q); p=ready; while(p) if(p-pstate!=FINISH)&(p-pstate!=RUNNING)(p-priority)+; p=p-link; if(running|ready) if(ready) pprint(ready); if(running)run(running); /*運(yùn)行進(jìn)程*/pprint(running);p=ready; main( )int i,j,sum=0,k=0;struct pcbs *p=NULL,*q=NULL;st

32、ruct word *pav=NULL,*s=NULL,*f=NULL;void priority();void pprint();struct pcbs *addnode();int randInt();if(fp=fopen(result.txt,w)=NULL)printf(cannot open file!n);exit(1);printf(nenter pcbnum(ensure pcbnum0):);scanf(%d,&PCBNUM);fprintf(fp,nthe pcb number is:%dnn,PCBNUM);for(i=0;ispace=(struct pcbs *)malloc(NUM); /*請(qǐng)求內(nèi)存*/ if(pav-spa