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

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

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

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

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

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

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

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

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

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

10、調(diào)度算法喚醒進程，插入就緒隊列*/void wakeup1(); /*輪轉(zhuǎn)法的進程調(diào)度算法喚醒進程，插入就緒隊列*/void proc_priority(); /*優(yōu)先權(quán)調(diào)度算法模擬*/void proc_loop(); /*輪轉(zhuǎn)法調(diào)度算法模擬*/void update(PCB *pcb); /*更新進程信息*/PCB *ready_queue,*block_queue,*idleprocess; /*就緒隊列，阻塞隊列及閑逛進程指針變量*/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ù)用于測試程序*/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;/*輸出進

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)/動態(tài)優(yōu)先權(quán)調(diào)試算法將item插入到隊列中,使得插入后，隊列中按照優(yōu)先級從高到低有序PCB *p,*q;q=queue;p=q->next;while(p

16、!=0 &&p->priority>=item->priority )q=p;p=p->next;if(p=0)/在隊尾插入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插入到隊列末尾PCB *p,*q;q=queue;p=q->next;item->next=0;q->next=item;void pushback_queue(

17、PCB *queue,PCB *item)/將item插入到隊列的尾部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)/對queue中的結(jié)點進行排序，按照優(yōu)先級從大到小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;/*動態(tài)優(yōu)先權(quán)的進程調(diào)度生成進程屬性信息，插入進程就緒隊列,顯示進程信息*/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);/將新生成進程插入到就緒隊列尾部print(newp);cout<<("t建立： Creating -> readyn");/*輪轉(zhuǎn)法的進程調(diào)度生成進程屬性信息，插入進程就緒隊列,顯示進程信息*/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);/將新生成進程插入到就緒隊列尾部print(newp);cout<<("t建立： Creating -> readyn");/*生成n個進程屬性信息，插入進程就緒隊列,顯示進程信息*/void insert(int n)for(int i=1;i<=n;i+)insert(); /*動態(tài)優(yōu)先權(quán)調(diào)度產(chǎn)生idle進程，輸入用戶進程數(shù)目，調(diào)用insert()*/void init()/為每個隊列設(shè)立頭結(jié)點，便于插入刪除操作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è)置閑逛進程PCB各字段值*/idleprocess=(PCB *)malloc(sizeof(PCB);idleprocess->ID=0;idleprocess->State=0;idleprocess->CPUtime=0;idleprocess->priority=0;idleprocess->ALLtime=1;idleprocess->next=NULL;/閑逛進程放入就緒隊列

22、idleprocess->next=ready_queue->next;ready_queue->next=idleprocess; /也可假定初始時系統(tǒng)中只有一個idle進程/輸入初始時進程的個數(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<<"就緒隊列初始化成功"<<endl;:print_init(ready_queue);cout<<endl;/*調(diào)用destroy()，將進程插入阻塞隊列*/void block(PCB *pcb)/將pcb插入到阻塞隊列pcb->State=2; /*將PCB所指進程的狀態(tài)設(shè)置為阻塞*/pcb->CPUtime-=2; /*設(shè)進程執(zhí)行半個時間片單位后被阻塞*/*pcb->next=NULL;*/print(pcb);cout<<("

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

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

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

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

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

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

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

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

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

33、無所謂喚醒return;PCB *q,*p;/下面遍歷阻塞隊列，q永遠指向p的前驅(qū)while(true)q=block_queue;p=q->next;while(p && rand()%20!=1)q=p;p=p->next;if(p!=0)/p就是要喚醒的進程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()/隨機喚醒一個阻塞進程/這里采取的方法是遍歷阻塞隊列，每訪問一個，就產(chǎn)生一個隨機數(shù)/如果該隨機數(shù)對20求余恰好是1，則當前結(jié)點被喚醒，就要納入就緒隊列if(block_queue->next=0)/此時沒有被阻塞的進程，無所謂喚醒return;PCB *q,*p;/下面遍歷阻塞隊列，q永遠指向p的前驅(qū)while(true)q=block_queue;p=q->next;while(p && rand()%20!=1)q=p;p=p->next;if(p!=0)/p就是要喚醒的進程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);/對queue中的結(jié)點進行排序，按照優(yōu)先級從大到小PCB *temp=0,*running=0; /*running的PCB指針*/int times;for(times=0;times<10;times+)/找到優(yōu)先級最高的進程，并且從隊列中刪除cout<<"本次調(diào)度前："<<endl;:print_init(ready_queue);running=ready_queue->next; /*running指向就緒隊列隊首PCB*/ready_queue->next=r