HUNANUNIVERSITY進程調度算法題目進程調度算法學生姓名學生學號專業班級完成日期 2013.12.06一、實驗題目實現短進程優先調度算法（SPF）實現時間片輪轉調度算法（RR）二、實驗目的通過對進程調度算法的設計，深入理解進程調度的原理。進程是程序在一個數據集合上運行的過程，它是系統進行資源分配和調度的一個獨立單位。進程調度分配處理機，是控制協調進程對CPU的競爭，即按一定的調度算法從就緒隊列中選中一個進程，把CPU的使用權交給被選中的進程。三、實驗內容1.先來先服務（FCFS）調度算法原理：每次調度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執行。該進程一旦占有了處理器，它就一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。將用戶作業和就緒進程按提交順序或變為就緒狀態的先后排成隊列，并按照先來先服務的方式進行調度處理，是一種最普遍和最簡單的方法。它優先考慮在系統中等待時間最長的作業，而不管要求運行時間的長短。按照就緒進程進入就緒隊列的先后次序進行調度，簡單易實現，利于長進程，CPU繁忙型作業，不利于短進程，排隊時間相對過長。2.時間片輪轉調度算法RR原理：時間片輪轉法主要用于進程調度。采用此算法的系統，其程序就緒隊列往往按進程到達的時間來排序。進程調度按一定時間片(q)輪番運行各個進程.進程按到達時間在就緒隊列中排隊，調度程序每次把CPU分配給就緒隊列首進程使用一個時間片，運行完一個時間片釋放CPU，排到就緒隊列末尾參加下一輪調度，CPU分配給就緒隊列的首進程。固定時間片輪轉法：1所有就緒進程按FCFS規則排隊。2處理機總是分配給就緒隊列的隊首進程。3如果運行的進程用完時間片，則系統就把該進程送回就緒隊列的隊尾，重新排隊。4因等待某事件而阻塞的進程送到阻塞隊列。5系統把被喚醒的進程送到就緒隊列的隊尾。可變時間片輪轉法：1進程狀態的轉換方法同固定時間片輪轉法。2響應時間固定，時間片的長短依據進程數量的多少由T=N×(q+t)給出的關系調整。3根據進程優先級的高低進一步調整時間片，優先級越高的進程，分配的時間片越長。3.算法類型:4.模擬程序可由兩部分組成，先來先服務(FCFS)調度算法，時間片輪轉。流程圖如下圖所示:四打印的源程序及附上的注釋#include<iostream>usingnamespacestd;#defineP_NUM3//cpu4種狀態就緒運行等待完成enumstate{ ready, waiting, block, finish};//PCB進程控制塊包括名稱、優先級、占用CPU時間、需要時間structpcb{ charname[4]; intpriority; intcputime; intneedtime; intcount; intround; stateprocess; pcb*next;//構建優先級隊列};//建立一個優先權的隊列pcb*get_process(){ pcb*q=NULL;; pcb*t=NULL;; pcb*p=NULL; inti=0; cout<<"inputnameandtime"<<endl; while(i<P_NUM){ q=(structpcb*)malloc(sizeof(pcb)); cin>>q->name; cin>>q->needtime; q->cputime=0; q->priority=P_NUM-i; q->process=ready; q->next=NULL; if(i==0){ p=q; t=q; } else{ t->next=q; t=q; } i++; }//while returnp;}//輸出當前隊列各個進程各種狀態voiddisplay(pcb*p){ cout<<"name"<<""<<"cputime"<<""<<"needtime"<<""<<"priority"<<""<<"state"<<endl; while(p){ cout<<p->name; cout<<""; cout<<p->cputime; cout<<""; cout<<p->needtime; cout<<""; cout<<p->priority; cout<<""; switch(p->process){ caseready:cout<<"ready"<<endl;break; casewaiting:cout<<"waiting"<<endl;break; caseblock:cout<<"block"<<endl;break; casefinish:cout<<"finish"<<endl;break; } p=p->next; }}//檢查隊列中進程是否完成intprocess_finish(pcb*q){ intbl=1; while(bl&&q){ bl=bl&&q->needtime==0; if(q->next!=NULL) q=q->next; } returnbl;}//找到優先權最大的進程執行voidcpuexe(pcb*q){ pcb*t=q; inttp=0; while(q){ if(q->process!=finish){ q->process=ready; if(q->needtime==0){ q->process=finish; } } if(tp<q->priority&&q->process!=finish){ tp=q->priority; t=q; } q=q->next; } if(t->needtime!=0){ t->needtime--; t->process=waiting; t->cputime++; }}//優先權調度voidpriority_cal(){ pcb*p=NULL; p=get_process(); intcpu=0; while(!process_finish(p)){ cpu++; cout<<"cputime:"<<cpu<<endl; cpuexe(p); display(p); } printf("Allprocesseshavefinished,pressanykeytoexit");}//初始化界面voiddisplay_menu(){ cout<<"選擇CPU調度算法："<<endl; cout<<"1優先權"<<endl; cout<<"2轉輪法"<<endl; cout<<"3退出"<<endl;}//輪轉法調度初始化pcb*get_process_round(){ pcb*q=NULL; pcb*t=NULL; pcb*p=NULL; inti=0; cout<<"inputnameandtime："<<endl; while(i<P_NUM){ q=(structpcb*)malloc(sizeof(pcb)); cin>>q->name; cin>>q->needtime; q->cputime=0; q->round=0; q->count=0; q->process=ready; q->next=NULL; if(i==0){ p=q; t=q; } else{ t->next=q; t=q; } i++; }//while returnp;}//cpu單位時間為1voidcpu_round(pcb*q){ q->cputime+=1; q->needtime-=1; if(q->needtime<=0){ q->needtime=0; q->process=finish; return; } q->count++; q->round++; q->process=waiting;}//輪轉法找到下一個可以CPU執行的程序pcb*get_next(pcb*k,pcb*head){ pcb*t; t=k; t=t->next; while(t&&t->process==finish){ t=t->next; } if(t==NULL){ t=head; while(t->next!=NULL&&t->process==finish){ if(t->next==k) t=t->next; if(t->next!=NULL) t=t->next; } } returnt;}//整理隊列里的進程狀態voidset_state(pcb*p){ while(p){ if(p->needtime<=0){ p->process=finish; } if(p->process==waiting){ p->process=ready; } p=p->next; }}//每個CPU時間后輸出每個進程狀態voiddisplay_round(pcb*p){ cout<<"NAME"<<""<<"CPUTIME"<<""<<"NEEDTIME"<<""<<"COUNT"<<""<<"ROUND"<<""<<"STATE"<<endl; while(p){ cout<<p->name; cout<<""; cout<<p->cputime; cout<<""; cout<<p->needtime; cout<<""; cout<<p->count; cout<<""; cout<<p->round; cout<<""; switch(p->process){ caseready:cout<<"ready"<<endl;break; casewaiting:cout<<"waiting"<<endl;break; casefinish:cout<<"finish"<<endl;break; } p=p->next; }}//轉輪調度voidround_cal(){ pcb*p=NULL; pcb*r=NULL; p=get_process_round(); intcpu=0; r=p; while(!process_finish(p)){ cpu+=1; cpu_round(r); r=get_next(r,p);