操作系統(tǒng)_進(jìn)程調(diào)度算法

1、計(jì)算機(jī)程序設(shè)計(jì)實(shí)踐報(bào)告課程設(shè)計(jì)報(bào)告書(shū)2012 / 2013 學(xué)年 第 1 學(xué)期課程名稱： 操作系統(tǒng)課程設(shè)計(jì) 專業(yè)班級(jí)：_計(jì)算機(jī)科學(xué)與技術(shù)1401班學(xué) 號(hào)：_130405220_姓 名：_柴艷_指導(dǎo)教師：_李威_課程設(shè)計(jì)指導(dǎo)教師評(píng)語(yǔ) 成 績(jī)：_ 指導(dǎo)教師簽字：_15進(jìn)程調(diào)度算法模擬11 題目的主要研究?jī)?nèi)容及預(yù)期達(dá)到的目標(biāo)1.1.1目的通過(guò)優(yōu)先權(quán)法和輪轉(zhuǎn)算法的模擬加深對(duì)進(jìn)程概念和進(jìn)程調(diào)度過(guò)程的理解，掌握進(jìn)程狀態(tài)之間的切換，同時(shí)掌握進(jìn)程調(diào)度算法的實(shí)現(xiàn)方法和技巧。1.1.2目標(biāo)1用C+語(yǔ)言來(lái)實(shí)現(xiàn)對(duì)n個(gè)進(jìn)程采用優(yōu)先權(quán)優(yōu)先算法以及輪轉(zhuǎn)算法的進(jìn)程調(diào)度。2每個(gè)用來(lái)標(biāo)識(shí)進(jìn)程的進(jìn)程控制塊PCB用結(jié)構(gòu)來(lái)描述，包括以

2、下字段：（1）進(jìn)程標(biāo)識(shí)ID，其中0為閑逛進(jìn)程，用戶進(jìn)程的標(biāo)識(shí)數(shù)為1，2，3。（2）進(jìn)程優(yōu)先級(jí)Priority，閑逛進(jìn)程（idle）的優(yōu)先級(jí)為0，用戶進(jìn)程的優(yōu)先級(jí)大于0，且隨機(jī)產(chǎn)生，標(biāo)識(shí)數(shù)越大，優(yōu)先級(jí)越高。（3）進(jìn)程占用的CPU時(shí)間CPUtime，進(jìn)程每運(yùn)行一次，累計(jì)值等于4。（4）進(jìn)程總共需要運(yùn)行時(shí)間Alltime，利用隨機(jī)函數(shù)產(chǎn)生。（5）進(jìn)程狀態(tài)，0就緒態(tài)；1運(yùn)行態(tài)；2阻塞態(tài)。（6）隊(duì)列指針next，用來(lái)將多個(gè)進(jìn)程控制塊PCB鏈接為隊(duì)列。1.1.3優(yōu)先數(shù)改變的原則（1）進(jìn)程在就緒隊(duì)列中每呆一個(gè)時(shí)間片，優(yōu)先數(shù)增加1。（2）進(jìn)程每運(yùn)行一個(gè)時(shí)間片，優(yōu)先數(shù)減3。1.1.4在調(diào)度前，系統(tǒng)中擁有的進(jìn)程數(shù)

3、PCB_number由鍵盤輸入，經(jīng)初始化后，所有的進(jìn)程控制塊PCB鏈接成就緒隊(duì)列。1.1.5為了清楚地觀察諸進(jìn)程的調(diào)度過(guò)程，程序應(yīng)將每個(gè)時(shí)間片內(nèi)的進(jìn)程的情況顯示出來(lái)。12 題目研究的工作基礎(chǔ)或?qū)嶒?yàn)條件windowsXP系統(tǒng)、VC+6.0 13 設(shè)計(jì)思想n 進(jìn)程調(diào)度的思想（1）當(dāng)系統(tǒng)空閑（就緒隊(duì)列為空）時(shí)，系統(tǒng)運(yùn)行閑逛進(jìn)程，否則運(yùn)行其他進(jìn)程，發(fā)生變遷1（就緒運(yùn)行）。（2）在運(yùn)行進(jìn)程（包括閑逛進(jìn)程）的過(guò)程中，可能發(fā)生變遷2（運(yùn)行阻塞），即將運(yùn)行進(jìn)程插入到阻塞隊(duì)列（閑逛進(jìn)程不能被阻塞），可能有其他新的進(jìn)程創(chuàng)建PCB，還可能喚醒阻塞隊(duì)列中的某些進(jìn)程PCB，發(fā)生變遷3（阻塞就緒），即從阻塞隊(duì)列中移出并插

4、入就緒隊(duì)列中。n （3）時(shí)間片運(yùn)行結(jié)束后，若進(jìn)程累計(jì)占用CPU時(shí)間大于等于進(jìn)程需要運(yùn)行的時(shí)間，則進(jìn)程執(zhí)行結(jié)束，釋放其PCB。若進(jìn)程累計(jì)占用CPU時(shí)間小于進(jìn)程需要運(yùn)行時(shí)間，發(fā)生變動(dòng)態(tài)優(yōu)先權(quán)的遷4（運(yùn)行就緒），即將當(dāng)前運(yùn)行的進(jìn)程插入就緒隊(duì)列中。14 流程圖1 進(jìn)程調(diào)度算法模擬流程創(chuàng)建n個(gè)PCB并加入ready_queue中輸入開(kāi)始進(jìn)程個(gè)數(shù)n各進(jìn)程按優(yōu)先級(jí)從高到低排列Yready_queue為空?NRunning<=逐個(gè)將ready_pc中PCBRunning<=idle阻塞running?NYYrunning=idle?N將running從 ready_queue中刪除,再將runni

5、ng 加入block_queuebN是否創(chuàng)建新PCB?Y創(chuàng)建新進(jìn)程并加入到ready_queue中對(duì)ready_queue中的進(jìn)程PCB進(jìn)行優(yōu)先級(jí)排序隨機(jī)對(duì)block_queue中的進(jìn)程PCB詢問(wèn)是否要喚醒？Y處理完了嗎？NN是否要喚醒？YNY將其從 block_queue隊(duì)列中刪除,再將其加入ready_queue隊(duì)列中并進(jìn)行優(yōu)先級(jí)排序（圖1.4.1）2輪轉(zhuǎn)法進(jìn)程調(diào)度算法模擬流程輸入開(kāi)始進(jìn)程個(gè)數(shù)n創(chuàng)建n個(gè)PCB并加入ready_queue中Yready_queue為空?NRunning<=逐個(gè)將ready_pc中PCBRunning<=idle阻塞running?NYYrunni

6、ng=idle?N將running從 ready_queue中刪除,再將running 加入block_queuebN是否創(chuàng)建新PCB?Y創(chuàng)建新進(jìn)程并加入到ready_queue中隨機(jī)對(duì)block_queue中的進(jìn)程PCB詢問(wèn)是否要喚醒？Y處理完了嗎？NN是否要喚醒？Y將其從 block_queue隊(duì)列中刪除,再將其加入ready_queue隊(duì)列中 （圖1.4.2）15 主要程序代碼#define NULL 0#include <stdio.h>#include <stdlib.h>#include<iostream>using namespace std;

7、/*進(jìn)程PCB結(jié)構(gòu)*/struct Pcbint ID;/進(jìn)程標(biāo)識(shí)ID，其中0為閑逛進(jìn)程，用戶進(jìn)程的標(biāo)識(shí)數(shù)為1，2，3int priority;/進(jìn)程優(yōu)先級(jí)Priority，閑逛進(jìn)程（idle）的優(yōu)先級(jí)為0，用戶進(jìn)程的優(yōu)先級(jí)大于0，且隨機(jī)產(chǎn)生，標(biāo)識(shí)數(shù)越大，優(yōu)先級(jí)越高。int CPUtime;/進(jìn)程占用的CPU時(shí)間CPUtime，進(jìn)程每運(yùn)行一次，累計(jì)值等于4int ALLtime;/進(jìn)程總共需要運(yùn)行時(shí)間Alltimeint State;/進(jìn)程狀態(tài)，0就緒態(tài)；1運(yùn)行態(tài)；2阻塞態(tài)。struct Pcb *next;/隊(duì)列指針next，用來(lái)將多個(gè)進(jìn)程控制塊PCB鏈接為隊(duì)列;typedef struct

8、 Pcb PCB;void init(); /*產(chǎn)生idle進(jìn)程，輸入用戶進(jìn)程數(shù)目，調(diào)用insert()*/void print(PCB *pcb); /*輸出進(jìn)程屬性信息*/void print_init(PCB *pcb); /*輸出所有PCB的初始值*/void insert_queue(PCB *queue,PCB *item); /*動(dòng)態(tài)優(yōu)先權(quán)調(diào)試算法將item插入到隊(duì)列中,使得插入后，隊(duì)列中按照優(yōu)先級(jí)從高到低有序*/void insert_queue1(PCB *queue,PCB *item); /*輪轉(zhuǎn)法將item插入到隊(duì)列末尾*/void pushback_queue(PCB

9、 *queue,PCB *item); /*將item插入到隊(duì)列的尾部*/void insert(); /*動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度算法生成進(jìn)程屬性信息，插入進(jìn)程就緒隊(duì)列*/void insert1(); /*輪轉(zhuǎn)法的進(jìn)程調(diào)度算法生成進(jìn)程屬性信息，插入進(jìn)程就緒隊(duì)列*/void run(PCB *pcb); /*運(yùn)行進(jìn)程，隨機(jī)阻塞進(jìn)程、產(chǎn)生新進(jìn)程，插入就緒隊(duì)列，喚醒阻塞進(jìn)程*/void run1(PCB *pcb); /*輪轉(zhuǎn)法試運(yùn)行參數(shù)PCB所指的進(jìn)程*/void block(PCB *pcb); /*調(diào)用destroy()，將進(jìn)程插入阻塞隊(duì)列*/void wakeup(); /*動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程

10、調(diào)度算法喚醒進(jìn)程，插入就緒隊(duì)列*/void wakeup1(); /*輪轉(zhuǎn)法的進(jìn)程調(diào)度算法喚醒進(jìn)程，插入就緒隊(duì)列*/void proc_priority(); /*優(yōu)先權(quán)調(diào)度算法模擬*/void proc_loop(); /*輪轉(zhuǎn)法調(diào)度算法模擬*/void update(PCB *pcb); /*更新進(jìn)程信息*/PCB *ready_queue,*block_queue,*idleprocess; /*就緒隊(duì)列，阻塞隊(duì)列及閑逛進(jìn)程指針變量*/void main()int i=0;while(1)cout<<("n Please select a number (1,2,0

11、) ");cout<<("n 1- priority ");cout<<("n 2- loop");cout<<("n 0- exitn");cin>>i;if(i=1)cout<<("nThis is an example for priority processing:n");init();:proc_priority();else if (i=2)cout<<("nThis is an example for roun

12、d robin processing:n");init();proc_loop();else if(i=0)exit(1);/*輸出所有PCB的初始值，此函數(shù)用于測(cè)試程序*/void print_init(PCB *pcb)PCB *temp=pcb->next;cout<<("n ID priority CPUtime ALLtime Staten");while(temp!=NULL)cout<<"n"<<" "<<temp->ID<<"

13、"<<temp->priority<<" "<<temp->CPUtime<<" "<<temp->ALLtime;if (temp->State=0)cout<<(" ready");else if (temp->State=1)cout<<(" running");elsecout<<(" blocked");temp=temp->next;/*輸出進(jìn)

14、程屬性信息*/void print(PCB *pcb)PCB *temp;temp=pcb;if (pcb->ID=0) cout<<("ntThe idle process is running!");elsecout<<"n"<<" "<<temp->ID<<" "<<temp->priority<<" "<<temp->CPUtime<<" &quo

15、t;<<temp->ALLtime;if (temp->State=0)cout<<(" ready");else if (temp->State=1)cout<<(" running");elsecout<<(" blocked");void insert_queue(PCB *queue,PCB *item)/動(dòng)態(tài)優(yōu)先權(quán)調(diào)試算法將item插入到隊(duì)列中,使得插入后，隊(duì)列中按照優(yōu)先級(jí)從高到低有序PCB *p,*q;q=queue;p=q->next;while(p

16、!=0 &&p->priority>=item->priority )q=p;p=p->next;if(p=0)/在隊(duì)尾插入item->next=0;q->next=item;else/在q之后、p之前插入item->next=p;q->next=item;void insert_queue1(PCB *queue,PCB *item)/輪轉(zhuǎn)法將item插入到隊(duì)列末尾PCB *p,*q;q=queue;p=q->next;item->next=0;q->next=item;void pushback_queue(

17、PCB *queue,PCB *item)/將item插入到隊(duì)列的尾部PCB *p,*q;q=queue;p=q->next;while(p!=0 )q=p;p=p->next;item->next=q->next;q->next=item;void sort_queue(PCB *&queue)/對(duì)queue中的結(jié)點(diǎn)進(jìn)行排序，按照優(yōu)先級(jí)從大到小PCB *temp=new PCB;temp->next=0;while(queue->next)PCB *p;p=queue->next;queue->next=p->next;:i

18、nsert_queue(temp,p);queue->next=temp->next;delete temp;/*動(dòng)態(tài)優(yōu)先權(quán)的進(jìn)程調(diào)度生成進(jìn)程屬性信息，插入進(jìn)程就緒隊(duì)列,顯示進(jìn)程信息*/void insert()PCB *newp=0;static long id=0;newp=new PCB;id+;newp->ID=id;newp->State=0;newp->CPUtime=0;newp->priority=rand()%3+1;newp->ALLtime=rand()%3+1;newp->next=NULL;:pushback_queue

19、(ready_queue,newp);/將新生成進(jìn)程插入到就緒隊(duì)列尾部print(newp);cout<<("t建立： Creating -> readyn");/*輪轉(zhuǎn)法的進(jìn)程調(diào)度生成進(jìn)程屬性信息，插入進(jìn)程就緒隊(duì)列,顯示進(jìn)程信息*/void insert1()PCB *newp=0;static long id=0;newp=new PCB;id+;newp->ID=id;newp->State=0;newp->CPUtime=0;newp->ALLtime=rand()%3+1;newp->next=NULL;:pushb

20、ack_queue(ready_queue,newp);/將新生成進(jìn)程插入到就緒隊(duì)列尾部print(newp);cout<<("t建立： Creating -> readyn");/*生成n個(gè)進(jìn)程屬性信息，插入進(jìn)程就緒隊(duì)列,顯示進(jìn)程信息*/void insert(int n)for(int i=1;i<=n;i+)insert(); /*動(dòng)態(tài)優(yōu)先權(quán)調(diào)度產(chǎn)生idle進(jìn)程，輸入用戶進(jìn)程數(shù)目，調(diào)用insert()*/void init()/為每個(gè)隊(duì)列設(shè)立頭結(jié)點(diǎn)，便于插入刪除操作block_queue=new PCB;block_queue->next

21、=0;ready_queue=new PCB;ready_queue->next=0;int i,pcb_number=-1;idleprocess=NULL; /*設(shè)置閑逛進(jìn)程PCB各字段值*/idleprocess=(PCB *)malloc(sizeof(PCB);idleprocess->ID=0;idleprocess->State=0;idleprocess->CPUtime=0;idleprocess->priority=0;idleprocess->ALLtime=1;idleprocess->next=NULL;/閑逛進(jìn)程放入就緒隊(duì)列

22、idleprocess->next=ready_queue->next;ready_queue->next=idleprocess; /也可假定初始時(shí)系統(tǒng)中只有一個(gè)idle進(jìn)程/輸入初始時(shí)進(jìn)程的個(gè)數(shù)/while (pcb_number<0)/cout<<("Input the number of the PCB to be started:");/cin>>pcb_number;/cout<<("n ID priority CPUtime ALLtime State");/for (i=0;i&

23、lt;pcb_number;i+)/insert();cout<<"就緒隊(duì)列初始化成功"<<endl;:print_init(ready_queue);cout<<endl;/*調(diào)用destroy()，將進(jìn)程插入阻塞隊(duì)列*/void block(PCB *pcb)/將pcb插入到阻塞隊(duì)列pcb->State=2; /*將PCB所指進(jìn)程的狀態(tài)設(shè)置為阻塞*/pcb->CPUtime-=2; /*設(shè)進(jìn)程執(zhí)行半個(gè)時(shí)間片單位后被阻塞*/*pcb->next=NULL;*/print(pcb);cout<<("

24、 變遷2：running -> blockedn");/將pcb插入到阻塞隊(duì)列/按照什么方式插入呢，需要參考喚醒條件/因?yàn)槭请S機(jī)喚醒一個(gè)進(jìn)程，所以我們就簡(jiǎn)單地把它放置在阻塞隊(duì)列的頭部pcb->next=block_queue->next;block_queue->next=pcb;void update(PCB *pcb)/就緒隊(duì)列中進(jìn)程的優(yōu)先級(jí)均增加1PCB *temp=ready_queue->next;while(temp && temp->next )/就緒隊(duì)列的最后一個(gè)是閑逛進(jìn)程temp->priority+;tem

25、p=temp->next;/*動(dòng)態(tài)優(yōu)先權(quán)調(diào)度試運(yùn)行參數(shù)PCB所指的進(jìn)程*/void run(PCB *pcb) /如果pcb是閑逛進(jìn)程，則不做處理，再次放入就緒隊(duì)列ready_queueif(pcb->ID=0):insert_queue(ready_queue,pcb);print(pcb);cout<<" 變遷1：ready -> runningn"else/如果不是閑逛進(jìn)程，則進(jìn)行如下處理pcb->State=1;/*設(shè)置該進(jìn)程的狀態(tài)為"運(yùn)行"*/pcb->CPUtime+=4;/*累計(jì)該進(jìn)程占用CPU的時(shí)

26、間*/pcb->priority=pcb->priority-3; /*每運(yùn)行一個(gè)時(shí)間片，其優(yōu)先數(shù)減3*/if(pcb->priority<1)pcb->priority=1;print(pcb);printf(" 變遷1：ready -> runningn");if (rand()%3=1 ) /*PCB不是閑逛進(jìn)程，滿足條件則阻塞此進(jìn)程*/if(pcb->CPUtime-2<pcb->ALLtime) block(pcb);else/已經(jīng)執(zhí)行完畢，應(yīng)該銷毀進(jìn)程cout<<endl;cout<<

27、"t the process no "<<pcb->ID<<" is completed! 銷毀：running->Destroy"<<endl;delete pcb;else/否則看改進(jìn)程是否執(zhí)行完畢，如果執(zhí)行完，則釋放，否則再次放入就緒隊(duì)列if(pcb->CPUtime>=pcb->ALLtime)/釋放cout<<endl;cout<<"t the process no "<<pcb->ID<<" i

28、s completed! 銷毀：running->Destroy"<<endl;delete pcb;else/再次放入就緒隊(duì)列,按照優(yōu)先級(jí)有序:insert_queue(ready_queue,pcb);update(ready_queue);/*更新就緒隊(duì)列進(jìn)程優(yōu)先數(shù)*/if (rand()%5=1)insert(3); /*創(chuàng)建3個(gè)新進(jìn)程*/:sort_queue(ready_queue);if (rand()%7=1)wakeup(); /*喚醒一個(gè)進(jìn)程*/ /*返回當(dāng)前進(jìn)程是否被阻塞，1（已阻塞），0（未阻塞）*/*輪轉(zhuǎn)法試運(yùn)行參數(shù)PCB所指的進(jìn)程*/vo

29、id run1(PCB *pcb) /如果pcb是閑逛進(jìn)程，則不做處理，再次放入就緒隊(duì)列ready_queueif(pcb->ID=0):insert_queue1(ready_queue,pcb);print(pcb);cout<<" 變遷1：ready -> runningn"else/如果不是閑逛進(jìn)程，則進(jìn)行如下處理pcb->State=1;/*設(shè)置該進(jìn)程的狀態(tài)為"運(yùn)行"*/pcb->CPUtime+=4;/*累計(jì)該進(jìn)程占用CPU的時(shí)間*/if(pcb->priority<1)pcb->prio

30、rity=1;/print(pcb);/ printf(" 變遷1：ready -> runningn");if (rand()%3=1 ) /*PCB不是閑逛進(jìn)程，滿足條件則阻塞此進(jìn)程*/if(pcb->CPUtime-2<pcb->ALLtime) block(pcb);else/已經(jīng)執(zhí)行完畢，應(yīng)該銷毀進(jìn)程cout<<endl;cout<<"t the process no "<<pcb->ID<<" is completed! 銷毀：running->De

31、stroy"<<endl;delete pcb;else/否則看改進(jìn)程是否執(zhí)行完畢，如果執(zhí)行完，則釋放，否則再次放入就緒隊(duì)列if(pcb->CPUtime>=pcb->ALLtime)/釋放cout<<endl;cout<<"t the process no "<<pcb->ID<<" is completed! 銷毀：running->Destroy"<<endl;delete pcb;else/再次放入就緒隊(duì)列:insert_queue1(

32、ready_queue,pcb);if (rand()%5=1)insert(3); /*創(chuàng)建3個(gè)新進(jìn)程*/:sort_queue(ready_queue);if (rand()%7=1)wakeup1(); /*喚醒一個(gè)進(jìn)程*/ /*返回當(dāng)前進(jìn)程是否被阻塞，1（已阻塞），0（未阻塞）*/*喚醒，即從阻塞隊(duì)列中選擇一個(gè)PCB，且插入就緒隊(duì)列中*/void wakeup()/隨機(jī)喚醒一個(gè)阻塞進(jìn)程/這里采取的方法是遍歷阻塞隊(duì)列，每訪問(wèn)一個(gè)，就產(chǎn)生一個(gè)隨機(jī)數(shù)/如果該隨機(jī)數(shù)對(duì)20求余恰好是1，則當(dāng)前結(jié)點(diǎn)被喚醒，就要納入就緒隊(duì)列if(block_queue->next=0)/此時(shí)沒(méi)有被阻塞的進(jìn)程，

33、無(wú)所謂喚醒return;PCB *q,*p;/下面遍歷阻塞隊(duì)列，q永遠(yuǎn)指向p的前驅(qū)while(true)q=block_queue;p=q->next;while(p && rand()%20!=1)q=p;p=p->next;if(p!=0)/p就是要喚醒的進(jìn)程q->next=p->next;break;p->State=0;cout<<endl;:print(p);cout<<" 變遷3：blocked->ready"<<endl;:insert_queue(ready_queue,

34、p);void wakeup1()/隨機(jī)喚醒一個(gè)阻塞進(jìn)程/這里采取的方法是遍歷阻塞隊(duì)列，每訪問(wèn)一個(gè)，就產(chǎn)生一個(gè)隨機(jī)數(shù)/如果該隨機(jī)數(shù)對(duì)20求余恰好是1，則當(dāng)前結(jié)點(diǎn)被喚醒，就要納入就緒隊(duì)列if(block_queue->next=0)/此時(shí)沒(méi)有被阻塞的進(jìn)程，無(wú)所謂喚醒return;PCB *q,*p;/下面遍歷阻塞隊(duì)列，q永遠(yuǎn)指向p的前驅(qū)while(true)q=block_queue;p=q->next;while(p && rand()%20!=1)q=p;p=p->next;if(p!=0)/p就是要喚醒的進(jìn)程q->next=p->next;br

35、eak;p->State=0;cout<<endl;:print(p);cout<<" 變遷3：blocked->ready"<<endl;:insert_queue1(ready_queue,p);/*優(yōu)先權(quán)優(yōu)先調(diào)度算法*/void proc_priority():sort_queue(ready_queue);/對(duì)queue中的結(jié)點(diǎn)進(jìn)行排序，按照優(yōu)先級(jí)從大到小PCB *temp=0,*running=0; /*running的PCB指針*/int times;for(times=0;times<10;times+)/找到優(yōu)先級(jí)最高的進(jìn)程，并且從隊(duì)列中刪除cout<<"本次調(diào)度前："<<endl;:print_init(ready_queue);running=ready_queue->next; /*running指向就緒隊(duì)列隊(duì)首PCB*/ready_queue->next=r