第一篇：短作業(yè)優(yōu)先調(diào)度算法
《操作系統(tǒng)》課程實(shí)驗(yàn)報(bào)告
姓名：陳凱
學(xué)號(hào)：541413430202
地點(diǎn)：四教樓301
指導(dǎo)老師：張旭
專業(yè)班級(jí)：嵌入式軟件14-02
實(shí)驗(yàn)名稱：短作業(yè)優(yōu)先調(diào)度算法
一、實(shí)驗(yàn)?zāi)康模?/p>
測試數(shù)據(jù)可以隨即輸入或從文件中讀入。必須要考慮到作業(yè)的到達(dá)時(shí)間
最終能夠計(jì)算每一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間。
二、實(shí)驗(yàn)內(nèi)容：
模擬實(shí)現(xiàn)短作業(yè)調(diào)度算法，具體如下：
設(shè)置作業(yè)體：作業(yè)名，作業(yè)的到達(dá)時(shí)間，服務(wù)時(shí)間，作業(yè)間的鏈接指針 進(jìn)程初始化：由用戶輸入作業(yè)名、作業(yè)的到達(dá)時(shí)間和服務(wù)時(shí)間進(jìn)行初始化。顯示函數(shù)：
1、顯示當(dāng)前調(diào)度的是哪個(gè)作業(yè)，后備隊(duì)列中有哪些作業(yè)
2、最終顯示每個(gè)作業(yè)的作業(yè)名、到達(dá)時(shí)間、服務(wù)時(shí)間、完成時(shí)間和周轉(zhuǎn)時(shí)間
排序函數(shù)：對就已到達(dá)的作業(yè)按照服務(wù)時(shí)間進(jìn)行排序。注意考慮到達(dá)時(shí)間 調(diào)度函數(shù)：每次從已到達(dá)的作業(yè)隊(duì)列隊(duì)首調(diào)度優(yōu)一個(gè)作業(yè)執(zhí)行。刪除函數(shù)：作業(yè)結(jié)束后撤銷。
三、實(shí)驗(yàn)代碼
#include
char name[10];//進(jìn)程名
floatarrivetime;//到達(dá)時(shí)間
floatservicetime;//服務(wù)時(shí)間
floatstarttime;
//開始時(shí)間
floatfinishtime;//完成時(shí)間 floatzztime;//周轉(zhuǎn)時(shí)間 floatdqzztime;
//帶權(quán)周轉(zhuǎn)時(shí)間 };
sjf b[100];
//定義短作業(yè)優(yōu)先算法進(jìn)程的最大數(shù)量 voidSinput(sjf *p,int N)
//輸入函數(shù) { int i;
printf(“輸入進(jìn)程的名稱、到達(dá)時(shí)間、服務(wù)時(shí)間:n”);for(i=0;i<=N-1;i++){
printf(“輸入第%d進(jìn)程的名稱、到達(dá)時(shí)間、服務(wù)時(shí)間:”,i+1);scanf(“%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} }
//輸出函數(shù) voidSPrint(sjf *p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,int N){ int k;
printf(“n執(zhí)行順序:n”);printf(“%s”,p[0].name);
for(k=1;k { printf(“-%s”,p[k].name);} printf(“n進(jìn)程名tarrivetservicetstarttfinishtzztdqzzn”); for(k=0;k<=N-1;k++) { printf(“%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftnn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); } } voidSsort(sjf *p,int N) //按短作業(yè)優(yōu)先算法排序 { for(int i=1;i<=N-1;i++)for(int j=1;j<=i;j++) if(p[i].servicetime sjf temp;temp=p[i]; p[i]=p[j]; p[j]=temp;} } //運(yùn)行結(jié)果 voidSdeal(sjf *p, float arrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&dqzztime,int N){ int k; for(k=0;k<=N-1;k++) { if(k==0){ p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime; } else { p[k].starttime=p[k-1].finishtime;//開始時(shí)間=前一個(gè)進(jìn)程的完成時(shí)間 p[k].finishtime=p[k-1].finishtime+p[k].servicetime; //結(jié)束時(shí)間=前一個(gè)進(jìn)程的完成時(shí)間+現(xiàn)在進(jìn)程的服務(wù)時(shí)間 } } for(k=0;k<=N-1;k++){ p[k].zztime=p[k].finishtime-p[k].arrivetime; //周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間 p[k].dqzztime=p[k].zztime/p[k].servicetime; //帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間 } } void SJF(sjf *p,int N){ float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; Ssort(p,N); Sdeal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); SPrint(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);} void main()//主函數(shù) { int M;printf(“------------短作業(yè)優(yōu)先調(diào)度算法-----------n”);printf(“輸入作業(yè)數(shù):”);scanf(“%d”,&M); Sinput(b,M);SJF(b,M);} 四、實(shí)驗(yàn)結(jié)果 五、實(shí)驗(yàn)總結(jié) 通過本次實(shí)驗(yàn)讓我學(xué)到了很多關(guān)于作業(yè)與作業(yè)調(diào)度的知識(shí)，今后我會(huì)好好努力學(xué)習(xí)。 實(shí) 驗(yàn) 報(bào) 告 學(xué)生姓名： 學(xué) 號(hào)： 指導(dǎo)教師： 一、實(shí)驗(yàn)室名稱： 二、實(shí)驗(yàn)項(xiàng)目名稱：進(jìn)程調(diào)度算法的設(shè)計(jì) 三、實(shí)驗(yàn)原理： 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法：短作業(yè)調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或者若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將他們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先調(diào)度算法則是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或者發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)再重新調(diào)度。 時(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ù)此信號(hào)來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的隊(duì)尾；然后，再把處理機(jī)分配給就緒隊(duì)列中的新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程在一個(gè)給定的時(shí)間內(nèi)均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。 四、實(shí)驗(yàn)?zāi)康模?/p> 通過對進(jìn)程調(diào)度算法的設(shè)計(jì)，深入理解進(jìn)程調(diào)度的原理 五、實(shí)驗(yàn)內(nèi)容： 1．編寫程序?qū)崿F(xiàn)SJ（P）F算法 2．編寫程序?qū)崿F(xiàn)RR算法 六、實(shí)驗(yàn)器材（設(shè)備、元器件）： 裝有VC++6.0的PC機(jī)一臺(tái) 七、實(shí)驗(yàn)步驟： 1．打開VC，設(shè)計(jì)編寫程序的源代碼 2．編譯運(yùn)行程序的源代碼 3．分析檢驗(yàn)程序的結(jié)果是否正確 4．總結(jié)實(shí)驗(yàn)結(jié)果及結(jié)論 短進(jìn)程優(yōu)先調(diào)度源代碼： #include “stdio.h” struct sjf{ char name[10];float arrivetime;float servicetime;float starttime;float finishtime;float zztime;float dqzztime;};sjf a[100];void input(sjf *p,int N){ int i;printf(“intput the process's name & arrivetime & servicetime:nfor exmple: a 0 100n”);for(i=0;i<=N-1;i++){ printf(“input the %dth process's information:n”,i+1);scanf(“%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} } void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N){int k; printf(“run order:”); printf(“%s”,p[0].name);for(k=1;k printf(“nthe process's information:n”); printf(“nnametarrivetservicetstarttfinishtzztdqzzn”); for(k=0;k<=N-1;k++){ printf(“%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);} } //排序 void sort(sjf *p,int N){ for(int i=0;i<=N-1;i++) for(int j=0;j<=i;j++) if(p[i].arrivetime { sjf temp; temp=p[i]; p[i]=p[j]; p[j]=temp; } } //運(yùn)行階段 void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N){ int k; for(k=0;k<=N-1;k++) { if(k==0) { p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime;} else { p[k].starttime=p[k-1].finishtime; p[k].finishtime=p[k-1].finishtime+p[k].servicetime;} } for(k=0;k<=N-1;k++) { p[k].zztime=p[k].finishtime-p[k].arrivetime; p[k].dqzztime=p[k].zztime/p[k].servicetime; } } void sjff(sjf *p,int N){float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;//對結(jié)構(gòu)進(jìn)行初始化 sort(p,N); for(int m=0;m {if(m==0) p[m].finishtime=p[m].arrivetime+p[m].servicetime; else p[m].finishtime=p[m-1].finishtime+p[m].servicetime; int i=0; for(int n=m+1;n<=N-1;n++) {if(p[n].arrivetime<=p[m].finishtime)//判斷內(nèi)存中每次完成之后有多少到達(dá)的進(jìn)程 i++; } float min=p[m+1].servicetime; int next=m+1;//m+1=n for(int k=m+1;k { if(p[k+1].servicetime {min=p[k+1].servicetime; next=k+1;} } sjf temp; temp=p[m+1]; p[m+1]=p[next]; p[next]=temp; } deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);} void main(){ int N; printf(“------短作業(yè)優(yōu)先調(diào)度算法------n”); printf(“input the process's number:n”); scanf(“%d”,&N); input(a,N); sjf *b=a; sjf *c=a; sjff(b,N);} 時(shí)間片輪轉(zhuǎn)法源代碼： #include //物理頁數(shù) #define printf(“|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|n”)typedef struct PCB { int ID;int ReachTime;int TotalTime;}PCB;//進(jìn)程號(hào)，到達(dá)時(shí)間和服務(wù)時(shí)間 typedef struct NOTE //備份 { Myprintf int ID;int TotalTime;}NOTE; PCB A[M];//5個(gè)進(jìn)程 PCB a[M];NOTE temp;int queue[50];//記錄調(diào)度的進(jìn)程 int K=0;//調(diào)度進(jìn)程數(shù)組的標(biāo)識(shí) void INIT()//初始化 { int i;for(i=0;i A[i].ID=-1;} } int GetNum()//計(jì)算進(jìn)程數(shù) { int i,j=0;for(i=0;i if(A[i].ID!=-1) { j++; } } return j;} int GetReach(int time)//找出到達(dá)進(jìn)程號(hào) { int i;for(i=0;i if(a[i].ReachTime<=time) { a[i].ReachTime=100; return i; } } return-1;} int GetInsert()//找出插入位置 { int i;for(i=0;i if(A[i].ID==-1) return i;} return-1;} void Forward(int num)//前移 { int i;for(i=0;i A[i].ID=A[i+1].ID; A[i].TotalTime=A[i+1].TotalTime;} A[num-1].ID=-1;} void Process()//執(zhí)行進(jìn)程 { queue[K]=A[0].ID;K++;A[0].TotalTime--;temp.ID=A[0].ID;temp.TotalTime=A[0].TotalTime;} void main(){ int i;int time;int t=0;int reach;int insert;int num;printf(“RR算法nn”);INIT();for(i=0;i printf(“請輸入進(jìn)程ID：”); scanf(“%d”,&a[i].ID); printf(“請輸入到達(dá)時(shí)間：”); scanf(“%d”,&a[i].ReachTime); printf(“請輸入服務(wù)時(shí)間：”); scanf(“%d”,&a[i].TotalTime); } for(i=0;i { insert=GetInsert(); A[insert].ID=a[reach].ID; A[insert].TotalTime=a[reach].TotalTime; num=GetNum(); if(num==1) continue;//進(jìn)程數(shù)為1 else { //進(jìn)程數(shù)不為1 Process(); Forward(num); if(temp.TotalTime!=0) { A[num-1].ID=temp.ID; A[num-1].TotalTime=temp.TotalTime; } } } else//沒有進(jìn)程到達(dá) { num=GetNum(); if(num==1) {//進(jìn)程數(shù)為1 Process(); if(temp.TotalTime==0) { A[0].ID=-1; } } else if(num==0) } continue;//進(jìn)程數(shù)為0 else { Process(); Forward(num); if(temp.TotalTime!=0) { A[num-1].ID=temp.ID; A[num-1].TotalTime=temp.TotalTime; } } } } printf(“n”);printf(“調(diào)度順序?yàn)椋簄”);Myprintf;for(i=0;i<50;i++){ if(queue[i]!=-1) printf(“|%2d ”,queue[i]);} printf(“|n”);Myprintf;printf(“n”); 八、實(shí)驗(yàn)數(shù)據(jù)及結(jié)果分析： 短作業(yè)優(yōu)先調(diào)度算法的實(shí)驗(yàn)結(jié)果： 時(shí)間片輪轉(zhuǎn)調(diào)度算法結(jié)果： 九、實(shí)驗(yàn)結(jié)論： 本次實(shí)驗(yàn)成功的完成了短作業(yè)優(yōu)先調(diào)度算法和輪轉(zhuǎn)時(shí)間片調(diào)度算法的模擬，通過本次實(shí)驗(yàn)我們了解到短作業(yè)優(yōu)先調(diào)度算法不利于長作業(yè)的處理，因?yàn)殚L作業(yè)將長期得不到處理，而輪轉(zhuǎn)時(shí)間片調(diào)度算法則解決了這一問題。短長作業(yè)均能在每一個(gè)周期內(nèi)分得一個(gè)時(shí)間片處理自己的任務(wù)。 十、總結(jié)及心得體會(huì)： 通過本次實(shí)驗(yàn)對短作業(yè)優(yōu)先調(diào)度算法和時(shí)間片輪轉(zhuǎn)調(diào)度算法有了更深入的理解，同時(shí)，對程序算法能力有了進(jìn)一步的提高，同時(shí)對模塊化編程有了更深入得理解，代碼的模塊化會(huì)使程序的代碼復(fù)用率提高，提高編程的效率。 十一、對本實(shí)驗(yàn)過程及方法、手段的改進(jìn)建議： 本次實(shí)驗(yàn)的時(shí)間片輪轉(zhuǎn)調(diào)度算法由于教材版本不一樣有兩種結(jié)果，本次實(shí)驗(yàn)本人采取的新教材的版本，新版本的難度較老教材要大很多，實(shí)驗(yàn)時(shí)候可以根據(jù)具體情況選擇一個(gè)適合自己的來做。 報(bào)告評分： 指導(dǎo)教師簽字： 電梯優(yōu)先調(diào)度算法 電梯調(diào)度算法(ms InterView) 移臂調(diào)度算法包括以下四種： 1）先來先服務(wù)算法：根據(jù)訪問者提出訪問請求的先后次序來決定執(zhí)行次序。 2）最短尋找時(shí)間優(yōu)先調(diào)度算法：從等待的訪問者中挑選尋找時(shí)間最短的那個(gè)請求執(zhí)行，而不管訪問者的先后次序。 3）電梯調(diào)度掃描算法：從移動(dòng)臂當(dāng)前位置沿移動(dòng)方向選擇最近的那個(gè)柱面的訪問者來執(zhí)行，若該方向上無請求訪問時(shí)，就改變移動(dòng)方向再選擇。 4）單向掃描調(diào)度算法：從0柱面開始往里單向掃描，掃到哪個(gè)執(zhí)行哪個(gè)。 */ // t1.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。 // #include “stdafx.h” #include“math.h” #include“stdlib.h” #include“string.h” struct Head { int nPosition;bool bVisited;}; void Visit(struct Head *pHead){ printf(“visite cy:%dn”,pHead->nPosition);pHead->bVisited=true;} int ReadInputKeyboard(struct Head *pHead,int *pCurrentPosition,int nMaxNumber){ int i; printf(“please input Current position:”);scanf(“%d”,pCurrentPosition); printf(“please input will visit position:”);for(i=0;i scanf(“%d”,&pHead[i].nPosition);pHead[i].bVisited=false;if(pHead[i].nPosition<0)break;} return i;} int ReadInputFile(struct Head *pHead,int *pCurrentPosition,int nMaxNumber){ int i; char szFileName[256],*q,*p,szTemp[20];printf(“please input filename:”);scanf(“%s”,szFileName); FILE *pFile=fopen(szFileName,“r”);if(pFile==NULL){ printf(“open file %s error”,szFileName);return-1;} for(i=0;!feof(pFile)&&i p=szFileName;fgets(p,256,pFile); while(q=strchr(p,',')){ memset(szTemp,0,sizeof(szTemp)*sizeof(char));strncpy(szTemp,p,q-p);p=q+1;if(i==0) *pCurrentPosition=atoi(szTemp);else { pHead[i-1].nPosition=atoi(szTemp);pHead[i-1].bVisited=false;} i++;} memset(szTemp,0,sizeof(szTemp)*sizeof(char));pHead[i-1].nPosition=atoi(p);pHead[i-1].bVisited=false;//i++; } fclose(pFile);return i;} int FifoVisit(int nCurrentPosition,struct Head *pHead,int nNumber){ //先來先服務(wù) int nHaveVisited=0;int nMoveDistance=0;int i;while(nHaveVisited for(i=0;i if(pHead[i].bVisited)continue; Visit(&pHead[i]);nHaveVisited++; nMoveDistance+=abs(nCurrentPosition-pHead[i].nPosition);nCurrentPosition=pHead[i].nPosition;} } printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int SsfoVisit(int nCurrentPosition,struct Head *pHead,int nNumber){ // 最短尋找時(shí)間優(yōu)先 int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i; while(nHaveVisited nMinDistance=0xffff;nMinIndex=0;//找最小值 for(i=0;i if(pHead[i].bVisited)continue; if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){ nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } //訪問 Visit(&pHead[nMinIndex]);nHaveVisited++; nMoveDistance+=nMinDistance; nCurrentPosition=pHead[nMinIndex].nPosition;} printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int DtVisit(int nCurrentPosition,bool bOut,struct Head *pHead,int nNumber){ //電梯調(diào)度算法 int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i; while(nHaveVisited nMinDistance=0xffff;nMinIndex=0;//找最小值 for(i=0;i if(pHead[i].bVisited)continue; if(bOut&&pHead[i].nPosition if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){ nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } } if(nMinDistance==0xffff){ bOut=!bOut;continue;} //訪問 Visit(&pHead[nMinIndex]);nHaveVisited++; nMoveDistance+=nMinDistance; nCurrentPosition=pHead[nMinIndex].nPosition;} printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int DxVisit(int nCurrentPosition,struct Head *pHead,int nNumber){ //單向調(diào)度算法 int nHaveVisited=0;int nMoveDistance=0;int nMinDistance=0;int nMinIndex=0;int i;while(nHaveVisited nMinDistance=0xffff;nMinIndex=0;//找最小值 for(i=0;i if(pHead[i].bVisited)continue; if(pHead[i].nPosition>nCurrentPosition){ if(nMinDistance>abs(pHead[i].nPosition-nCurrentPosition)){ nMinDistance=abs(pHead[i].nPosition-nCurrentPosition);nMinIndex=i;} } } if(nMinDistance==0xffff){ nMoveDistance+=199-nCurrentPosition;nCurrentPosition=0;continue;} //訪問 Visit(&pHead[nMinIndex]);nHaveVisited++; nMoveDistance+=nMinDistance; nCurrentPosition=pHead[nMinIndex].nPosition;} printf(“the sum of move distance:%dn”,nMoveDistance);return nMoveDistance;} int main(int argc, char* argv[]){ //p114 struct Head mylist[20];//={98,false,183,false,37,false,122,false,14,false,124,false,65,false,67,false}; //int nCurrentPosition=53; //int nRealNumber=8; int nCurrentPosition=0; int nRealNumber=ReadInputFile(mylist,&nCurrentPosition,20);// FifoVisit(nCurrentPosition,mylist,nRealNumber); // SsfoVisit(nCurrentPosition,mylist,nRealNumber); //DtVisit(nCurrentPosition,false,mylist,nRealNumber); DxVisit(nCurrentPosition,mylist,nRealNumber); return 0;} 1.實(shí)驗(yàn)題目: 磁盤調(diào)度算法。 建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)； 在屏幕上顯示磁盤請求的服務(wù)狀況； 將一批磁盤請求的情況存磁盤文件，以后可以讀出并重放； 計(jì)算磁頭移動(dòng)的總距離及平均移動(dòng)距離； 支持算法：FIFO、SSTF、SCAN、CSCAN; 2.設(shè)計(jì)目的: 調(diào)度磁盤I/O請求服務(wù)，采用好的方式能提高訪問時(shí)間和帶寬。本實(shí)驗(yàn)通過編程對磁盤調(diào)度算法的實(shí)現(xiàn)，加深對算法的理解，同時(shí)通過用C++語言編寫程序?qū)崿F(xiàn)這些算法，并在windos平臺(tái)上實(shí)現(xiàn)，更好的掌握操作系統(tǒng)的原理以及實(shí)現(xiàn)方法，提高綜合運(yùn)用專業(yè)課知識(shí)的能力。 3.任務(wù)及要求 3.1 設(shè)計(jì)任務(wù) 編程實(shí)現(xiàn)下述磁盤調(diào)度算法，并求出每種算法的平均尋道長度： 1、先來先服務(wù)算法（FCFS） 2、最短尋道時(shí)間算法（SSTF） 3、掃描算法（SCAN） 4、循環(huán)掃描算法（CSCAN） 3.2 設(shè)計(jì)要求 對用戶指定的磁盤調(diào)度請求序列，基于以上四種算法，實(shí)現(xiàn)各自的調(diào)度順序并輸出，同時(shí)計(jì)算出各種算法下的平均尋道長度。 4.算法及數(shù)據(jù)結(jié)構(gòu) 4.1算法的總體思想 queue[n] 為請求調(diào)度序列，diskrode為磁盤磁道數(shù)，headstarts為正在調(diào)度的磁道 ①先來先服務(wù)算法（FCFS）按queue[n]數(shù)組的順序進(jìn)行磁盤調(diào)度，將前一個(gè)調(diào)度磁道與下一個(gè)調(diào)度磁道的差值累加起來，得到總的尋道長度，再除以n得到平均尋道長度。 ②最短尋道時(shí)間優(yōu)先算法（SSTF）將queue[n]進(jìn)行由小到大的排序，首先定位當(dāng)前調(diào)度磁headstarts在queue[n]的位置，通過循環(huán)語句找出離起始磁頭最短的位置。 ③掃描算法（SCAN） 將queue[n]進(jìn)行由小到大的排序，首先定位當(dāng)前調(diào)度磁headstarts在queue[n]的位置，然后在此位置按給定的方向遍歷queue[n]，當(dāng)?shù)蓝它c(diǎn)（queue[0]或queue[n-1]）時(shí)，再在定位處反向遍歷到另一端。當(dāng)調(diào)度磁道不在queue端點(diǎn)時(shí)，總的尋道長度為為前一個(gè)磁道與后一個(gè)磁 道差值的累加，當(dāng)?shù)竭_(dá)端點(diǎn)且queue[n]未全調(diào)度時(shí)，總尋道長度加上端點(diǎn)值再加上下一個(gè)調(diào)度磁道的值，再按前面的算法進(jìn)行，直到磁道全部都調(diào)度完畢，得到總的尋道長度，除以n得到平均尋道長度。 ④循環(huán)掃描算法（CSCAN）將queue[n]進(jìn)行由小到大的排序，首先定位當(dāng)前調(diào)度磁headstarts在queue[n]的位置，然后在此位置按給定的方向遍歷queue[n]，當(dāng)?shù)蓝它c(diǎn)（queue[0]或queue[n-1]）時(shí)，反向到另一端點(diǎn)再以此方向進(jìn)行遍歷，直到queue[n]中所有都調(diào)度完。當(dāng)調(diào)度磁道不在queue端點(diǎn)時(shí)，總的尋道長度為為前一個(gè)磁道與后一個(gè)磁道差值的累加，當(dāng)?shù)竭_(dá)端點(diǎn)且queue[n]未全調(diào)度時(shí)，總尋道長度加上端點(diǎn)值再加上磁盤磁道總長度，再加上下一個(gè)調(diào)度磁道的值，再按前面的算法進(jìn)行，直到磁道全部都調(diào)度完畢，得到總的尋道長度，除以n得到平均尋道長度。 5、源代碼： #include 1、先來先服務(wù)算法（FCFS)**********”< cout<<“****** 2、最短尋道時(shí)間優(yōu)先算法(SSTF)**********”< cout<<“****** 3、掃描算法(SCAN)**********”< cout<<“****** 4、循環(huán)掃描算法(CSCAN)**********”< cout<<“****** 5、退出 **********”< /*======================初始化序列=======================*/ void init(int queue[],int queue_copy[],int n){ int i;for(i=0;i //對當(dāng)前正在執(zhí)行的磁道號(hào)進(jìn)行定位，返回磁道號(hào)小于當(dāng)前磁道中最大的一個(gè) int fix(int queue[], int n, int headstarts){ int i =0;while(i /* ====================以下是FCFS算法==================*/ void FCFS(int queue[],int n,int diskrode,int headstarts)//queue是請求調(diào)度序列，n為其個(gè)數(shù)，diskroad為磁盤磁道數(shù)，headstarts為正在調(diào)度的磁道 { cout<<“************以下為FCFS調(diào)度算法***********”< /*=====================SSTF算法====================*/ void SSTF(int queue[], int n, int diskrode, int headstarts){ int k=1;int l,r;int i,j,count=0;queue =bubble(queue,n);cout<<“************以下為SSTF調(diào)度算法***********”< -headstarts)){ cout< /*======================以下是SCAN算法====================*/ void SCAN(int queue[], int n, int diskrode, int headstarts){ int direction, i, fixi;cout<<“***********以下是SCAN調(diào)度算法*************”< /*======================以下是CSCAN算法====================*/ void CSCAN(int queue[],int n,int diskrode,int headstarts){ int direction,i,fixi;cout<<“***********以下是CSCAN調(diào)度算法*************”< void main(){ int n, i, diskrode, headstarts;//n表示調(diào)度磁盤請求序列queue的長度，diskrode表示磁盤磁道的個(gè)數(shù)，headstarts表示目前正在調(diào)度的磁道； cout<<“請輸入磁盤的總磁道數(shù):”< if(menux ==2)SSTF(queue,n,diskrode,headstarts); if(menux ==3)SCAN(queue,n,diskrode,headstarts);if(menux ==4)CSCAN(queue,n,diskrode,headstarts);if(menux ==5)cout<<“程序結(jié)束,謝謝使用！”< 1.傳統(tǒng)電梯調(diào)度算法 1.1先來先服務(wù)算法(FCFS) 先來先服務(wù)(FCFS-First Come First Serve)算法，是一種隨即服務(wù)算法，它不僅僅沒有對尋找樓層進(jìn)行優(yōu)化，也沒有實(shí)時(shí)性的特征，它是一種最簡單的電梯調(diào)度算法。它根據(jù)乘客請求乘坐電梯的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡單，且每個(gè)乘客的請求都能依次地得到處理，不會(huì)出現(xiàn)某一乘客的請求長期得不到滿足的情況[12]。這種方法在載荷較輕松的環(huán)境下，性能尚可接受，但是在載荷較大的情況下，這種算法的性能就會(huì)嚴(yán)重下降，甚至惡化。人們之所以研究這種在載荷較大的情況下幾乎不可用的算法，有兩個(gè)原因： (1)任何調(diào)度算法在請求隊(duì)列長度為1時(shí)，請求速率極低或相鄰請求的間隔為無窮大時(shí)使用先來先服務(wù)算法既對調(diào)度效率不會(huì)產(chǎn)生影響，而且實(shí)現(xiàn)這種算法極其簡單。 (2)先來先服務(wù)算法可以作為衡量其他算法的標(biāo)準(zhǔn)。 1.2最短尋找樓層時(shí)間優(yōu)先算法(SSTF) 最短尋找樓層時(shí)間優(yōu)先(SSTF-Shortest Seek Time First)[14]算法，它注重電梯尋找樓層的優(yōu)化。最短尋找樓層時(shí)間優(yōu)先算法選擇下一個(gè)服務(wù)對象的原則是最短尋找樓層的時(shí)間。這樣請求隊(duì)列中距當(dāng)前能夠最先到達(dá)的樓層的請求信號(hào)就是下一個(gè)服務(wù)對象。在重載荷的情況下，最短尋找樓層時(shí)間優(yōu)先算法的平均響應(yīng)時(shí)間較短，但響應(yīng)時(shí)間的方差較大，原因是隊(duì)列中的某些請求可能長時(shí)間得不到響應(yīng)，出現(xiàn)所謂的“餓死”現(xiàn)象。 1.3掃描算法(SCAN) 掃描算法(SCAN)是一種按照樓層順序依次服務(wù)請求，它讓電梯在最底層和最頂層之間連續(xù)往返運(yùn)行，在運(yùn)行過程中響應(yīng)處在于電梯運(yùn)行方向相同的各樓層上的請求。它進(jìn)行尋找樓層的優(yōu)化，效率比較高，但它是一個(gè)非實(shí)時(shí)算法。掃描算法較好地解決了電梯移動(dòng)的問題，在這個(gè)算法中，每個(gè)電梯響應(yīng)乘客請求使乘客獲得服務(wù)的次序是由其發(fā)出請求的乘客的位置與當(dāng)前電梯位置之間的距離來決定的，所有的與電梯運(yùn)行方向相同的乘客的請求在一次電向上運(yùn)行或向下運(yùn)行的過程中完成，免去了電梯頻繁的來回移動(dòng)[2]。掃描算法的平均響應(yīng)時(shí)間比最短尋找樓層時(shí)間優(yōu)先算法長，但是響應(yīng)時(shí)間方差比最短尋找樓層時(shí)間優(yōu)先算法小，從統(tǒng)計(jì)學(xué)角度來講，掃描算法要比最短尋找樓層時(shí)間優(yōu)先算法穩(wěn)定。 1.4 LOOK 算法 LOOK算法[18]是掃描算法的一種改進(jìn)。對LOOK算法而言，電梯同樣在最底層和最頂層之間運(yùn)行。但當(dāng)LOOK算法發(fā)現(xiàn)電梯所移動(dòng)的方向上不再有請求時(shí)立即改變運(yùn)行方向，而掃描算法則需要移動(dòng)到最底層或者最頂層時(shí)才改變運(yùn)行方向。 1.5 SAFT 算法 SATF(Shortest Access Time First)[15,19]算法與SSTF算法的思想類似，唯一的區(qū)別就是SATF算法將SSTF算法中的尋找樓層時(shí)間改成了訪問時(shí)間。這是因?yàn)殡娞菁夹g(shù)發(fā)展到今天，尋找樓層的時(shí)間已經(jīng)有了很大地改進(jìn)，但是電梯的運(yùn)行當(dāng)中等待乘客上梯時(shí)間卻不是人為可以控制。SATF算法考慮到了電梯運(yùn)行過程中乘客上梯時(shí)間的影響。實(shí)時(shí)電梯調(diào)度算法 2.1最早截止期優(yōu)先調(diào)度算法 最早截止期優(yōu)先(EDF-Earliest Deadline First)[16]調(diào)度算法是最簡單的實(shí)時(shí)電梯調(diào)度算法，它的缺點(diǎn)就是造成電梯任意地尋找樓層，導(dǎo)致極低的電梯吞吐率。它與FCFS調(diào)度算法類似，EDF算法是電梯實(shí)時(shí)調(diào)度算法中最簡單的調(diào)度算法。它響應(yīng)請求隊(duì)列中時(shí)限最早的請求，是其它實(shí)時(shí)電梯調(diào)度算法性能衡量的基準(zhǔn)和特例。 2.2 SCAN-EDF 算法 SCAN-EDF[16]算法是SCAN算法和EDF算法相結(jié)合的產(chǎn)物。SCAN-EDF算法先按照EDF算法選擇請求列隊(duì)中哪一個(gè)是下一個(gè)服務(wù)對象，而對于具有相同時(shí)限的請求，則按照SCAN算法服務(wù)每一個(gè)請求。它的效率取決于有相同deadline 的數(shù)目，因而效率是有限的。 2.3 PI 算法 PI(Priority Inversion)[16]算法將請求隊(duì)列中的請求分成兩個(gè)優(yōu)先級(jí)，它首先保證高優(yōu)先級(jí)隊(duì)列中的請求得到及時(shí)響應(yīng)，再搞優(yōu)先級(jí)隊(duì)列為空的情況下在相應(yīng)地優(yōu)先級(jí)隊(duì)列中的請求。 2.4 FD-SCAN 算法 FD-SCAN(Feasible Deadline SCAN)[17]算法首先從請求隊(duì)列中找出時(shí)限最早、從當(dāng)前位置開始移動(dòng)又可以買足其時(shí)限要求的請求，作為下一次SCAN的方向。并在電梯所在樓層向該請求信號(hào)運(yùn)行的過程中響應(yīng)處在與電梯運(yùn)行方向相同且電梯可以經(jīng)過的請求信號(hào)。這種算法忽略了用SCAN算法相應(yīng)其它請求的開銷，因此并不能確保服務(wù)對象時(shí)限最終得到滿足。電梯調(diào)度的高水平研究 以上兩個(gè)小結(jié)介紹了幾種在目前本人的能力上能進(jìn)行研究的、簡單的電梯調(diào)度算法。但是并不是說目前電梯調(diào)度只發(fā)展到這個(gè)層次。目前電梯的控制技術(shù)已經(jīng)進(jìn)入了電梯群控的時(shí)代。 隨著微機(jī)在電梯系統(tǒng)中的應(yīng)用和人工智能技術(shù)的發(fā)展，智能群控技術(shù)得以迅速發(fā)展起來。由此，電梯的群控方面陸續(xù)發(fā)展出了一批新方法，包括：基于專家系統(tǒng)的電梯群控方法、基于模糊邏輯的電梯群控方法、基于遺產(chǎn)算法的電梯群控方法、基于勝景網(wǎng)絡(luò)的電梯群控方法和基于模糊神經(jīng)網(wǎng)絡(luò)的電梯群控方法。4 電梯問題的需求分析 4.1 電梯的初始狀態(tài) 本人設(shè)置的電梯的初始狀態(tài)，是對住宅樓的電梯的設(shè)置。 (1)建筑共有21層，其中含有地下一層（地下一層為停車場及貨物運(yùn)送場所）。 (2)建筑內(nèi)部設(shè)有兩部電梯，編號(hào)分別為A梯、B梯。 (3)電梯內(nèi)部有23個(gè)按鈕，其中包括開門按鈕、關(guān)門按鈕和樓層按鈕，編號(hào)為-1，1，2，3，4……20。 (4)電梯外部含有兩個(gè)按鈕，即向上運(yùn)行按鈕和向下運(yùn)行按鈕。建筑頂層與地下一層例外，建筑頂層只設(shè)置有向下運(yùn)行按鈕，地下一層只設(shè)置有向上運(yùn)行按鈕。 (5)電梯開關(guān)門完成時(shí)間設(shè)定為1秒。電梯到達(dá)每層后上下人的時(shí)間設(shè)定為8秒。電梯從靜止開始運(yùn)行到下一層的時(shí)間設(shè)置為2秒，而運(yùn)行中通過一層的時(shí)間為1秒。 (6)在凌晨2：00——4：30之間，如若沒有請求信號(hào)，A梯自動(dòng)停在14層，B梯自動(dòng)停在6層。 (7)當(dāng)電梯下到-1層后，如果沒有請求信號(hào)，電梯自動(dòng)回到1層 4.2 電梯按鈕功能 電梯內(nèi)部的樓層按鈕：電梯內(nèi)部對應(yīng)每一個(gè)樓層的按鈕成為樓層按鈕，即本章第一結(jié)提到的編號(hào)為-1，1，2，3，4……20的按鈕。當(dāng)乘客進(jìn)入電梯后按下樓層按鈕，此按鈕顯示灰色，代表不可以用。這樣就表示乘客將要去往此層，電梯將開往相應(yīng)層。當(dāng)電梯到達(dá)該層后，按鈕恢復(fù)可以使用狀態(tài)。 電梯內(nèi)部開門按鈕：當(dāng)電梯達(dá)到乘客想要去往的某樓層后，乘客需要準(zhǔn)備離開電梯，當(dāng)電梯停穩(wěn)后，乘客可以按下開門按鈕，電梯門將打開，讓用戶離開。如若電梯到了乘客曾經(jīng)按下的樓層，但是無乘客按開門按鈕，電梯將自動(dòng)在停穩(wěn)后1秒后自動(dòng)開門。 電梯內(nèi)部關(guān)門按鈕：當(dāng)所有想要乘坐電梯的乘客都進(jìn)入電梯以后，準(zhǔn)備讓電梯開始運(yùn)行的時(shí)候，乘客需要按下關(guān)門按鈕，讓電梯門關(guān)閉，使電梯進(jìn)入運(yùn)行狀態(tài)。設(shè)置電梯的自動(dòng)關(guān)門時(shí)間為8秒。 電梯外部向上按鈕：此按鈕表示上樓請求，當(dāng)按下此按鈕時(shí)，如果電梯到達(dá)按下此按鈕的樓層，且電梯運(yùn)行方向是向上的，那么電梯響將停下，并在電梯停穩(wěn)之后自動(dòng)開門，此請求被響應(yīng)后，取消此請求信號(hào)。電梯外部向下按鈕：此按鈕表示下樓請求，當(dāng)按下此按鈕時(shí)，如果電梯到達(dá)按下此按鈕的樓層，且電梯運(yùn)行方向是向下的，那么電梯響將停下，并在電梯停穩(wěn)之后自動(dòng)開門，此請求被響應(yīng)后，取消此請求信號(hào)。第二篇：短作業(yè)優(yōu)先調(diào)度和時(shí)間片輪轉(zhuǎn)調(diào)度算法
第三篇：電梯優(yōu)先調(diào)度算法
第四篇：操作系統(tǒng)課程設(shè)計(jì)-磁盤調(diào)度算法
第五篇：電梯調(diào)度算法總結(jié)
點(diǎn)擊咨詢 