操作系統(tǒng)實(shí)驗(yàn)報(bào)告進(jìn)程調(diào)度算法

HUNANUNIVERSITY進(jìn)程調(diào)度算法題目進(jìn)程調(diào)度算法學(xué)生姓名學(xué)生學(xué)號(hào)專業(yè)班級(jí)完成日期 2013.12.06一、實(shí)驗(yàn)題目實(shí)現(xiàn)短進(jìn)程優(yōu)先調(diào)度算法（SPF）實(shí)現(xiàn)時(shí)間片輪轉(zhuǎn)調(diào)度算法（RR）二、實(shí)驗(yàn)?zāi)康耐ㄟ^對(duì)進(jìn)程調(diào)度算法的設(shè)計(jì)，深入理解進(jìn)程調(diào)度的原理。進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(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í)驗(yàn)內(nèi)容1.先來先服務(wù)（FCFS）調(diào)度算法原理：每次調(diào)度是從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入就緒隊(duì)列的進(jìn)程，把處理器分配給該進(jìn)程，使之得到執(zhí)行。該進(jìn)程一旦占有了處理器，它就一直運(yùn)行下去，直到該進(jìn)程完成或因發(fā)生事件而阻塞，才退出處理器。將用戶作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊(duì)列，并按照先來先服務(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)程，CPU繁忙型作業(yè)，不利于短進(jìn)程，排隊(duì)時(shí)間相對(duì)過長(zhǎng)。2.時(shí)間片輪轉(zhuǎn)調(diào)度算法RR原理：時(shí)間片輪轉(zhuǎn)法主要用于進(jìn)程調(diào)度。采用此算法的系統(tǒng)，其程序就緒隊(duì)列往往按進(jìn)程到達(dá)的時(shí)間來排序。進(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ì)列末尾參加下一輪調(diào)度，CPU分配給就緒隊(duì)列的首進(jìn)程。固定時(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ì)尾?？勺儠r(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=N×(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.算法類型:4.模擬程序可由兩部分組成，先來先服務(wù)(FCFS)調(diào)度算法，時(shí)間片輪轉(zhuǎn)。流程圖如下圖所示:四打印的源程序及附上的注釋#include<iostream>usingnamespacestd;#defineP_NUM3//cpu4種狀態(tài)就緒運(yùn)行等待完成enumstate{ ready, waiting, block, finish};//PCB進(jìn)程控制塊包括名稱、優(yōu)先級(jí)、占用CPU時(shí)間、需要時(shí)間structpcb{ charname[4]; intpriority; intcputime; intneedtime; intcount; intround; stateprocess; pcb*next;//構(gòu)建優(yōu)先級(jí)隊(duì)列};//建立一個(gè)優(yōu)先權(quán)的隊(duì)列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;}//輸出當(dāng)前隊(duì)列各個(gè)進(jìn)程各種狀態(tài)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; }}//檢查隊(duì)列中進(jìn)程是否完成intprocess_finish(pcb*q){ intbl=1; while(bl&&q){ bl=bl&&q->needtime==0; if(q->next!=NULL) q=q->next; } returnbl;}//找到優(yōu)先權(quán)最大的進(jìn)程執(zhí)行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++; }}//優(yōu)先權(quán)調(diào)度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調(diào)度算法："<<endl; cout<<"1優(yōu)先權(quán)"<<endl; cout<<"2轉(zhuǎn)輪法"<<endl; cout<<"3退出"<<endl;}//輪轉(zhuǎn)法調(diào)度初始化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單位時(shí)間為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;}//輪轉(zhuǎn)法找到下一個(gè)可以CPU執(zhí)行的程序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;}//整理隊(duì)列里的進(jìn)程狀態(tài)voidset_state(pcb*p){ while(p){ if(p->needtime<=0){ p->process=finish; } if(p->process==waiting){ p->process=ready; } p=p->next; }}//每個(gè)CPU時(shí)間后輸出每個(gè)進(jìn)程狀態(tài)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; }}//轉(zhuǎn)輪調(diào)度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);