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

1、操作系統(tǒng) 操作系統(tǒng) 項(xiàng)目文檔報(bào)告進(jìn)程調(diào)度算法專 業(yè)： 班 級： 指導(dǎo)教師： 姓 名： 學(xué) 號： 一、核心算法思想1.先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法是一種最簡單的調(diào)度算法，該算法既可以用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將他們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。在進(jìn)程調(diào)度中采用FCFS算法時(shí)，則每次調(diào)度是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。FCFS算法比較有利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程

2、）。2. 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法SJ（P）F，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先（SJF）的調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程（SPF）調(diào)度算法則是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)再重新調(diào)度。SJ(P)F調(diào)度算法能有效地降低作業(yè)（進(jìn)程）的平均等待時(shí)間，提高系統(tǒng)吞吐量。該算法對長作業(yè)不利，完全未考慮作業(yè)的緊迫程度。3.高響應(yīng)比優(yōu)先調(diào)度算法在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比

3、較好的算法，其主要不足之處是長作業(yè)的運(yùn)行得不到保證。如果我們能為每個(gè)作業(yè)引人動態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級隨著等待時(shí)間的增加而以速率a提高，則長作業(yè)在等待一定的時(shí)間后，必然有機(jī)會分配到處理機(jī)。該優(yōu)先權(quán)的變化規(guī)律可描述為:優(yōu)先權(quán)=（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間即 優(yōu)先權(quán)=響應(yīng)時(shí)間/要求服務(wù)時(shí)間如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間越短，其優(yōu)先權(quán)越高，因而該算法有利于短作業(yè)。當(dāng)要球服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間越長，優(yōu)先權(quán)越高，因而它實(shí)現(xiàn)的是先來先服務(wù)對于長作業(yè)，作業(yè)的優(yōu)先級可以隨著等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級便可以升到很高，從而也可獲得

4、處理機(jī)。4. 時(shí)間片輪轉(zhuǎn)算法在時(shí)間片輪轉(zhuǎn)算法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)數(shù)器發(fā)出時(shí)鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程在一給定的時(shí)間內(nèi)均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。換言之，系統(tǒng)能在給定的時(shí)間內(nèi)響應(yīng)所有用戶的請求。二、核心算法流程圖1.先來先服務(wù)算法流程圖開始 創(chuàng)建進(jìn)程PCB按到達(dá)時(shí)間排序調(diào)用action，執(zhí)行進(jìn)程輸出結(jié)果結(jié)束2. 短

5、進(jìn)程優(yōu)先算法 開始獲取進(jìn)程信息按進(jìn)程越要時(shí)間排序調(diào)用action，執(zhí)行進(jìn)程輸出結(jié)果結(jié)束3.時(shí)間片輪轉(zhuǎn)算法開始 獲得進(jìn)程信息 調(diào)用時(shí)間片輪轉(zhuǎn)算法在每個(gè)時(shí)間片執(zhí)行程序大于0計(jì)算各進(jìn)程剩余時(shí)間等于0進(jìn)程結(jié)束4.髙響應(yīng)比優(yōu)先算法開始首先進(jìn)行第一個(gè)進(jìn)程計(jì)算剩余進(jìn)程的響應(yīng)比按優(yōu)先級排序運(yùn)行優(yōu)先級最高的進(jìn)程結(jié)束四、源代碼下面給出的是用C實(shí)現(xiàn)程序的源代碼：#include<stdio.h>#include <stdlib.h>#include <time.h>typedef struct pcb int name; int needtime; int arrivetime;

6、 int pri; int state; int cputime;plist;void action(plist * nowpro);void action(plist * nowpro) delay(1000); printf("now is process %d ",nowpro->name); nowpro->needtime-; if(nowpro->needtime=0) printf(" the process %d is endn",nowpro->name); /* nowpro->state=1; */ p

7、rintf("-n"); else printf("process %d needtime is %dn",nowpro->name,nowpro->needtime); printf("-n"); void creatpro(int n,plist * process ) int j; for(j=0;j<n;j+) = j; processj.needtime=rand()%10+1; processj.arrivetime=rand()%10; processj.pri=rand()%

8、4; processj.state=0; processj.cputime=0; void show( int n,plist * process) int j; for (j=0 ;j<n;j+) printf("name of process%dt",); printf("needtime %dt",processj.needtime); printf("arrivetime %dt",processj.arrivetime); printf("pri %dn",processj

9、.pri); printf("state %dt",processj.state); printf("cputime %dn",processj.cputime); void main() void creatpro(int n,plist * process ); void show( int n,plist * process); void fcfs(int n,plist * process); void sjf(int n,plist * process); void rr(int n,plist * pro1); void hrrn(int n

10、,plist * pro1); int n; /*the number of process*/ int k; plist process10; printf("please input the number of process from 0 to 10n"); scanf("%d",&n); creatpro(n,process); show(n,process); printf("please choose the what you want to usen"); printf("1 FCFSt 2 SJFt

11、3 HRRNt 4 RRn"); scanf("%d",&k); switch(k) case 1: fcfs(n,process); break; case 2: sjf(n,process); break; case 3: hrrn(n,process); break; case 4: rr(n,process); break; default : break; getch();void fcfs(int n,plist * pro1) void show( int n,plist * process); int i,j,k; int m=0; int

12、 time; plist temp; plist pro210; for(i=0;i<n;i+) k=0; while(pro1k.state=1) k+; temp=pro1k; for(j=k+1;j<n;j+) if(temp.arrivetime>pro1j.arrivetime&&pro1j.state!=1) temp=pro1j; k=j; pro2m+=temp; pro1k.state=1; show(n,pro2); for(i=0;i<n;i+) while(pro2i.needtime>0) action(&pro2

13、i); void sjf(int n,plist * pro1) void show( int n,plist * process); int i,j,k; int m=0; plist temp; plist pro210; for(i=0;i<n;i+) k=0; while(pro1k.state=1) k+; temp=pro1k; for(j=k+1;j<n;j+) if(temp.needtime>pro1j.needtime&&pro1j.state!=1) temp=pro1j; k=j; pro2m+=temp; pro1k.state=1;

14、 show(n,pro2); for(i=0;i<n;i+) while(pro2i.needtime>0) action(&pro2i); void rr(int n,plist * pro1) void show( int n,plist * process); int i,j,k; int m=0; int time; plist temp; plist pro210; for(i=0;i<n;i+) k=0; while(pro1k.state=1) k+; temp=pro1k; for(j=k+1;j<n;j+) if(temp.arrivetime

15、>pro1j.arrivetime&&pro1j.state!=1) temp=pro1j; k=j; pro2m+=temp; pro1k.state=1; show(n,pro2); time=pro20.needtime; for(i=0;i<n;i+) if(time<pro2i.needtime) time=pro2i.needtime; while(time>0) for(i=0;i<n;i+) if(pro2i.needtime>0) action(&pro2i); time-; void hrrn(int n,plis

16、t * pro1) int cal(int a ,plist * pro2); int i,k,j,m; int curtime=0; plist temp; for(i=0;i<n;i+) k=0; while(pro1k.state=1) k+; temp=pro1k; m=cal(curtime,&temp); for(j=0;j<n;j+) if(pro1j.state!=1) pro1j.pri=cal(curtime,&pro1j); if(m>pro1j.pri) temp=pro1j; m=pro1j.pri; k=j; while(pro1k.needtime>0) action(&pro1k); curtime+; pro1k.state=1; int cal(int a ,plist * pro2) int pr; if(a-pro2->arrivetime)<=0) pr=1; else pr=(a-pro2->arrivetime+pro2->needtime)/pro2->needtime