第一篇：短作业优先调度算法
《操作系统》课程实验报告
姓名：陈凯
学号：541413430202
地点：四教楼301
指导老师：张旭
专业班级：嵌入式软件14-02
实验名称：短作业优先调度算法
一、实验目的：
测试数据可以随即输入或从文件中读入。必须要考虑到作业的到达时间
最终能够计算每一个作业的周转时间。
二、实验内容：
模拟实现短作业调度算法，具体如下：
设置作业体：作业名，作业的到达时间，服务时间，作业间的链接指针 进程初始化：由用户输入作业名、作业的到达时间和服务时间进行初始化。显示函数：
1、显示当前调度的是哪个作业，后备队列中有哪些作业
2、最终显示每个作业的作业名、到达时间、服务时间、完成时间和周转时间
排序函数：对就已到达的作业按照服务时间进行排序。注意考虑到达时间 调度函数：每次从已到达的作业队列队首调度优一个作业执行。删除函数：作业结束后撤销。
三、实验代码
#include
char name[10];//进程名
floatarrivetime;//到达时间
floatservicetime;//服务时间
floatstarttime;
//开始时间
floatfinishtime;//完成时间 floatzztime;//周转时间 floatdqzztime;
//带权周转时间 };
sjf b[100];
//定义短作业优先算法进程的最大数量 voidSinput(sjf *p,int N)
//输入函数 { int i;
printf(“输入进程的名称、到达时间、服务时间:n”);for(i=0;i<=N-1;i++){
printf(“输入第%d进程的名称、到达时间、服务时间:”,i+1);scanf(“%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} }
//输出函数 voidSPrint(sjf *p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,int N){ int k;
printf(“n执行顺序:n”);printf(“%s”,p[0].name);
for(k=1;k { printf(“-%s”,p[k].name);} printf(“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) //按短作业优先算法排序 { 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;} } //运行结果 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;//开始时间=前一个进程的完成时间 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 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()//主函数 { int M;printf(“------------短作业优先调度算法-----------n”);printf(“输入作业数:”);scanf(“%d”,&M); Sinput(b,M);SJF(b,M);} 四、实验结果 五、实验总结 通过本次实验让我学到了很多关于作业与作业调度的知识，今后我会好好努力学习。 实 验 报 告 学生姓名： 学 号： 指导教师： 一、实验室名称： 二、实验项目名称：进程调度算法的设计 三、实验原理： 短作业（进程）优先调度算法：短作业调度算法是从后备队列中选择一个或者若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或者发生某事件而被阻塞放弃处理机时再重新调度。 时间片轮转法：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的队尾；然后，再把处理机分配给就绪队列中的新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一个给定的时间内均能获得一时间片的处理机执行时间。 四、实验目的： 通过对进程调度算法的设计，深入理解进程调度的原理 五、实验内容： 1．编写程序实现SJ（P）F算法 2．编写程序实现RR算法 六、实验器材（设备、元器件）： 装有VC++6.0的PC机一台 七、实验步骤： 1．打开VC，设计编写程序的源代码 2．编译运行程序的源代码 3．分析检验程序的结果是否正确 4．总结实验结果及结论 短进程优先调度源代码： #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; } } //运行阶段 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;//对结构进行初始化 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)//判断内存中每次完成之后有多少到达的进程 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(“------短作业优先调度算法------n”); printf(“input the process's number:n”); scanf(“%d”,&N); input(a,N); sjf *b=a; sjf *c=a; sjff(b,N);} 时间片轮转法源代码： #include //物理页数 #define printf(“|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|n”)typedef struct PCB { int ID;int ReachTime;int TotalTime;}PCB;//进程号，到达时间和服务时间 typedef struct NOTE //备份 { Myprintf int ID;int TotalTime;}NOTE; PCB A[M];//5个进程 PCB a[M];NOTE temp;int queue[50];//记录调度的进程 int K=0;//调度进程数组的标识 void INIT()//初始化 { int i;for(i=0;i A[i].ID=-1;} } int GetNum()//计算进程数 { int i,j=0;for(i=0;i if(A[i].ID!=-1) { j++; } } return j;} int GetReach(int time)//找出到达进程号 { 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()//执行进程 { 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(“请输入进程ID：”); scanf(“%d”,&a[i].ID); printf(“请输入到达时间：”); scanf(“%d”,&a[i].ReachTime); printf(“请输入服务时间：”); 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;//进程数为1 else { //进程数不为1 Process(); Forward(num); if(temp.TotalTime!=0) { A[num-1].ID=temp.ID; A[num-1].TotalTime=temp.TotalTime; } } } else//没有进程到达 { num=GetNum(); if(num==1) {//进程数为1 Process(); if(temp.TotalTime==0) { A[0].ID=-1; } } else if(num==0) } continue;//进程数为0 else { Process(); Forward(num); if(temp.TotalTime!=0) { A[num-1].ID=temp.ID; A[num-1].TotalTime=temp.TotalTime; } } } } printf(“n”);printf(“调度顺序为：n”);Myprintf;for(i=0;i<50;i++){ if(queue[i]!=-1) printf(“|%2d ”,queue[i]);} printf(“|n”);Myprintf;printf(“n”); 八、实验数据及结果分析： 短作业优先调度算法的实验结果： 时间片轮转调度算法结果： 九、实验结论： 本次实验成功的完成了短作业优先调度算法和轮转时间片调度算法的模拟，通过本次实验我们了解到短作业优先调度算法不利于长作业的处理，因为长作业将长期得不到处理，而轮转时间片调度算法则解决了这一问题。短长作业均能在每一个周期内分得一个时间片处理自己的任务。 十、总结及心得体会： 通过本次实验对短作业优先调度算法和时间片轮转调度算法有了更深入的理解，同时，对程序算法能力有了进一步的提高，同时对模块化编程有了更深入得理解，代码的模块化会使程序的代码复用率提高，提高编程的效率。 十一、对本实验过程及方法、手段的改进建议： 本次实验的时间片轮转调度算法由于教材版本不一样有两种结果，本次实验本人采取的新教材的版本，新版本的难度较老教材要大很多，实验时候可以根据具体情况选择一个适合自己的来做。 报告评分： 指导教师签字： 电梯优先调度算法 电梯调度算法(ms InterView) 移臂调度算法包括以下四种： 1）先来先服务算法：根据访问者提出访问请求的先后次序来决定执行次序。 2）最短寻找时间优先调度算法：从等待的访问者中挑选寻找时间最短的那个请求执行，而不管访问者的先后次序。 3）电梯调度扫描算法：从移动臂当前位置沿移动方向选择最近的那个柱面的访问者来执行，若该方向上无请求访问时，就改变移动方向再选择。 4）单向扫描调度算法：从0柱面开始往里单向扫描，扫到哪个执行哪个。 */ // t1.cpp : 定义控制台应用程序的入口点。 // #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){ //先来先服务 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){ // 最短寻找时间优先 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){ //电梯调度算法 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){ //单向调度算法 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.实验题目: 磁盘调度算法。 建立相应的数据结构； 在屏幕上显示磁盘请求的服务状况； 将一批磁盘请求的情况存磁盘文件，以后可以读出并重放； 计算磁头移动的总距离及平均移动距离； 支持算法：FIFO、SSTF、SCAN、CSCAN; 2.设计目的: 调度磁盘I/O请求服务，采用好的方式能提高访问时间和带宽。本实验通过编程对磁盘调度算法的实现，加深对算法的理解，同时通过用C++语言编写程序实现这些算法，并在windos平台上实现，更好的掌握操作系统的原理以及实现方法，提高综合运用专业课知识的能力。 3.任务及要求 3.1 设计任务 编程实现下述磁盘调度算法，并求出每种算法的平均寻道长度： 1、先来先服务算法（FCFS） 2、最短寻道时间算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN） 3.2 设计要求 对用户指定的磁盘调度请求序列，基于以上四种算法，实现各自的调度顺序并输出，同时计算出各种算法下的平均寻道长度。 4.算法及数据结构 4.1算法的总体思想 queue[n] 为请求调度序列，diskrode为磁盘磁道数，headstarts为正在调度的磁道 ①先来先服务算法（FCFS）按queue[n]数组的顺序进行磁盘调度，将前一个调度磁道与下一个调度磁道的差值累加起来，得到总的寻道长度，再除以n得到平均寻道长度。 ②最短寻道时间优先算法（SSTF）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，通过循环语句找出离起始磁头最短的位置。 ③扫描算法（SCAN） 将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，再在定位处反向遍历到另一端。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁 道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。 ④循环扫描算法（CSCAN）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，反向到另一端点再以此方向进行遍历，直到queue[n]中所有都调度完。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上磁盘磁道总长度，再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。 5、源代码： #include 1、先来先服务算法（FCFS)**********”< cout<<“****** 2、最短寻道时间优先算法(SSTF)**********”< cout<<“****** 3、扫描算法(SCAN)**********”< cout<<“****** 4、循环扫描算法(CSCAN)**********”< cout<<“****** 5、退出 **********”< /*======================初始化序列=======================*/ void init(int queue[],int queue_copy[],int n){ int i;for(i=0;i //对当前正在执行的磁道号进行定位，返回磁道号小于当前磁道中最大的一个 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是请求调度序列，n为其个数，diskroad为磁盘磁道数，headstarts为正在调度的磁道 { cout<<“************以下为FCFS调度算法***********”< /*=====================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调度算法***********”< -headstarts)){ cout< /*======================以下是SCAN算法====================*/ void SCAN(int queue[], int n, int diskrode, int headstarts){ int direction, i, fixi;cout<<“***********以下是SCAN调度算法*************”< /*======================以下是CSCAN算法====================*/ void CSCAN(int queue[],int n,int diskrode,int headstarts){ int direction,i,fixi;cout<<“***********以下是CSCAN调度算法*************”< void main(){ int n, i, diskrode, headstarts;//n表示调度磁盘请求序列queue的长度，diskrode表示磁盘磁道的个数，headstarts表示目前正在调度的磁道； cout<<“请输入磁盘的总磁道数:”< 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<<“程序结束,谢谢使用！”< 1.传统电梯调度算法 1.1先来先服务算法(FCFS) 先来先服务(FCFS-First Come First Serve)算法，是一种随即服务算法，它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，它是一种最简单的电梯调度算法。它根据乘客请求乘坐电梯的先后次序进行调度。此算法的优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求长期得不到满足的情况[12]。这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，这种算法的性能就会严重下降，甚至恶化。人们之所以研究这种在载荷较大的情况下几乎不可用的算法，有两个原因： (1)任何调度算法在请求队列长度为1时，请求速率极低或相邻请求的间隔为无穷大时使用先来先服务算法既对调度效率不会产生影响，而且实现这种算法极其简单。 (2)先来先服务算法可以作为衡量其他算法的标准。 1.2最短寻找楼层时间优先算法(SSTF) 最短寻找楼层时间优先(SSTF-Shortest Seek Time First)[14]算法，它注重电梯寻找楼层的优化。最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“饿死”现象。 1.3扫描算法(SCAN) 扫描算法(SCAN)是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。它进行寻找楼层的优化，效率比较高，但它是一个非实时算法。扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的，所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成，免去了电梯频繁的来回移动[2]。扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻找楼层时间优先算法小，从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法稳定。 1.4 LOOK 算法 LOOK算法[18]是扫描算法的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。但当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。 1.5 SAFT 算法 SATF(Shortest Access Time First)[15,19]算法与SSTF算法的思想类似，唯一的区别就是SATF算法将SSTF算法中的寻找楼层时间改成了访问时间。这是因为电梯技术发展到今天，寻找楼层的时间已经有了很大地改进，但是电梯的运行当中等待乘客上梯时间却不是人为可以控制。SATF算法考虑到了电梯运行过程中乘客上梯时间的影响。实时电梯调度算法 2.1最早截止期优先调度算法 最早截止期优先(EDF-Earliest Deadline First)[16]调度算法是最简单的实时电梯调度算法，它的缺点就是造成电梯任意地寻找楼层，导致极低的电梯吞吐率。它与FCFS调度算法类似，EDF算法是电梯实时调度算法中最简单的调度算法。它响应请求队列中时限最早的请求，是其它实时电梯调度算法性能衡量的基准和特例。 2.2 SCAN-EDF 算法 SCAN-EDF[16]算法是SCAN算法和EDF算法相结合的产物。SCAN-EDF算法先按照EDF算法选择请求列队中哪一个是下一个服务对象，而对于具有相同时限的请求，则按照SCAN算法服务每一个请求。它的效率取决于有相同deadline 的数目，因而效率是有限的。 2.3 PI 算法 PI(Priority Inversion)[16]算法将请求队列中的请求分成两个优先级，它首先保证高优先级队列中的请求得到及时响应，再搞优先级队列为空的情况下在相应地优先级队列中的请求。 2.4 FD-SCAN 算法 FD-SCAN(Feasible Deadline SCAN)[17]算法首先从请求队列中找出时限最早、从当前位置开始移动又可以买足其时限要求的请求，作为下一次SCAN的方向。并在电梯所在楼层向该请求信号运行的过程中响应处在与电梯运行方向相同且电梯可以经过的请求信号。这种算法忽略了用SCAN算法相应其它请求的开销，因此并不能确保服务对象时限最终得到满足。电梯调度的高水平研究 以上两个小结介绍了几种在目前本人的能力上能进行研究的、简单的电梯调度算法。但是并不是说目前电梯调度只发展到这个层次。目前电梯的控制技术已经进入了电梯群控的时代。 随着微机在电梯系统中的应用和人工智能技术的发展，智能群控技术得以迅速发展起来。由此，电梯的群控方面陆续发展出了一批新方法，包括：基于专家系统的电梯群控方法、基于模糊逻辑的电梯群控方法、基于遗产算法的电梯群控方法、基于胜景网络的电梯群控方法和基于模糊神经网络的电梯群控方法。4 电梯问题的需求分析 4.1 电梯的初始状态 本人设置的电梯的初始状态，是对住宅楼的电梯的设置。 (1)建筑共有21层，其中含有地下一层（地下一层为停车场及货物运送场所）。 (2)建筑内部设有两部电梯，编号分别为A梯、B梯。 (3)电梯内部有23个按钮，其中包括开门按钮、关门按钮和楼层按钮，编号为-1，1，2，3，4……20。 (4)电梯外部含有两个按钮，即向上运行按钮和向下运行按钮。建筑顶层与地下一层例外，建筑顶层只设置有向下运行按钮，地下一层只设置有向上运行按钮。 (5)电梯开关门完成时间设定为1秒。电梯到达每层后上下人的时间设定为8秒。电梯从静止开始运行到下一层的时间设置为2秒，而运行中通过一层的时间为1秒。 (6)在凌晨2：00——4：30之间，如若没有请求信号，A梯自动停在14层，B梯自动停在6层。 (7)当电梯下到-1层后，如果没有请求信号，电梯自动回到1层 4.2 电梯按钮功能 电梯内部的楼层按钮：电梯内部对应每一个楼层的按钮成为楼层按钮，即本章第一结提到的编号为-1，1，2，3，4……20的按钮。当乘客进入电梯后按下楼层按钮，此按钮显示灰色，代表不可以用。这样就表示乘客将要去往此层，电梯将开往相应层。当电梯到达该层后，按钮恢复可以使用状态。 电梯内部开门按钮：当电梯达到乘客想要去往的某楼层后，乘客需要准备离开电梯，当电梯停稳后，乘客可以按下开门按钮，电梯门将打开，让用户离开。如若电梯到了乘客曾经按下的楼层，但是无乘客按开门按钮，电梯将自动在停稳后1秒后自动开门。 电梯内部关门按钮：当所有想要乘坐电梯的乘客都进入电梯以后，准备让电梯开始运行的时候，乘客需要按下关门按钮，让电梯门关闭，使电梯进入运行状态。设置电梯的自动关门时间为8秒。 电梯外部向上按钮：此按钮表示上楼请求，当按下此按钮时，如果电梯到达按下此按钮的楼层，且电梯运行方向是向上的，那么电梯响将停下，并在电梯停稳之后自动开门，此请求被响应后，取消此请求信号。电梯外部向下按钮：此按钮表示下楼请求，当按下此按钮时，如果电梯到达按下此按钮的楼层，且电梯运行方向是向下的，那么电梯响将停下，并在电梯停稳之后自动开门，此请求被响应后，取消此请求信号。第二篇：短作业优先调度和时间片轮转调度算法
第三篇：电梯优先调度算法
第四篇：操作系统课程设计-磁盘调度算法
第五篇：电梯调度算法总结
点击咨询 