单核与多核的CPU调度算法

PAGEPAGE1单核与多核的CPU调度算法第一篇：单核与多核的CPU调度算法1.多核CPU调度算法1.1全局队列调度算法操作系统维护一个全局的任务等待队列，每个进程在执行阶段可以使用全部的处理器资源。当系统中有一个CPU核心空闲时，操作系统就从全局任务等待队列中选取Ready进程开始在此核心上执行。优点：CPU核心利用率较高，能保证全局资源的充分利用。缺点：多处理器同时查找工作时，可能会降低处理器效率。且同一进程可能在不同内核上执行，造成的进程迁移开销较大。1.2局部队列调度算法操作系统为每个CPU内核维护一个局部的任务等待队列，将所有进程分配到与处理器对应的进程队列中。当系统中有一个CPU内核空闲时，便从该核心的任务等待队列中选取恰当的任务执行。优点：充分利用局部缓存，降低了进程迁移的开销。任务基本上无需在多个CPU核心间切换，有利于提高CPU核心局部Cache命中率。目前多数多核CPU操作系统采用的是基于全局队列的任务调度算法。缺点：可能造成某些处理器超负荷，而某些处理器空闲，即资源分配不均衡不充分，引起全局资源的不充分利用。2.简单单核CPU调度算法2.1先到先服务调度算法：FCFS（first-come,first-served）当一个进程进入到Ready队列，其PCB就被链接到队列的尾部。当CPU空闲时，CPU被分配给位于队列头的进程（即当前Ready队列中已等待时间最长的进程）。接着，该运行进程从队列中被删除。缺点：对于一个进程队列，其总的周转时间太长，且当进程的I/O较为密集时，效率将会变得相当低，CPU利用率也会变得很低。优点：实现方式简单，适用于长程调度和处理器密集的进程调度。常与优先级策略结合提供一种更有效率的调度方法。2.2最短作业优先调度算法：SJF（shortest-job-first）SJF是一种非抢占式的调度算法，其实现原则是取Ready队列中处理时间最短的进程加载入CPU，进入CPU执行的进程执行完后才释放CPU，然后加载第二个进程进入CPU执行。缺点：忽视了作业等待时间，会出现starvation现象，且作业执行时间无法提前知道，也很难预估。优点：算法实现简单，能有效地降低作业的平均等待时间，提高系统吞吐量，是理论上的最优调度算法。2.3最短剩余时间优先调度算法：SRTF（ShortestRemainingTimeFirst）SRTF调度算法是抢占式的SJF调度算法，调度程序总是首先选择预期剩余时间最短的进程加载进入CPU执行。缺点：总是选择预期剩余时间最短的进程，会造成starvation现象。有处理时间预估，效率不足够高。优点：不偏向长进程，没有额外的中断，因此开销较低。且对于一个进程队列，总的周转时间较短，执行效率较高，对短进程的响应较快。2.4优先级调度算法每个进程都有一个自己的优先级，Ready队列采用优先级队列实现，CPU每次取Ready队列队首的进程。通常情况，当两个进程的优先级相同时，我们在相同优先级的进程之间采用FCFS调度算法。优先级可以通过内部或外部方式来定义。缺点：会出现starvation现象（也称无穷阻塞），且不适用于分时系统或交互式事务处理环境。优点：主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中。可以采用老化技术，每个进程执行以后其优先级降低，以此来克服starvation的缺点。2.5轮转法调度算法轮转法（RR）调度算法是专门为分时系统设计的，是一种基于时钟的抢占策略。定义一个小时间单元，称为时间量或时间片。时间片通常为10ms到100ms。将Ready队列作为循环队列处理。CPU调度程序循环就需队列，为每个进程分配不超过一个时间片间隔的CPU。如果上下文切换时间约为时间片的10%，那么约10%的CPU时间会浪费在上下文切换上。缺点：时间片长度设计较难，当时间片长度过大时，会退化成FCFS调度算法。调度I/O密集型进程时效率较低。由于轮询调度在调度过程中不考虑瞬时信道条件，因此它将导致较低的整体系统性能。优点：对不同的分组业务流队列进行同样的无差别的循环调度服务，对于等长业务流队列是公平的，不存在starvation现象。2.6最高响应比优先调度算法首先需要理解一个概念，叫作响应比。响应比的计算表达式为其中R为响应比，w为等待处理器的时间，s为预计服务的时间。当进程被立即调用时，R等于归一化周转时间。调度算法的过程是，当进程完成执行或被阻塞时，选择R值最大的Ready进程加载进入CPU执行。缺点：需要预估服务时间s，效率不太高。优点：能克服starvation现象。3.复杂单核CPU调度算法3.1多级队列调度算法（multilevelqueue-schedulingalgorithm）将Ready队列分成多个独立的队列，对Ready队列和每个独立的队列采用不同的调度算法进行执行。常用的方式是，Ready队列采用优先级调度算法，不同队列根据实际情况采用合适的调度算法即可。优点：综合了多种调度算法，避免了starvation现象，最大限度地提高了调度效率，也提高了CPU利用率。3.2多级反馈队列调度算法UNIXOS采用的调度算法。其详细过程如下：1.进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。2.首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。3.对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。4.在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。优点：既能使高优先级的作业得到响应又能使短作业(进程)迅速完成。4.多核CPU调度算法与单核CPU调度算法对比从上面的不同CPU调度算法，我们不难发现，单核CPU调度算法是多核CPU调度算法的基础，多核CPU调度算法是单核CPU调度算法的延伸和综合使用。我以大篇幅介绍了单核CPU的调度算法，而以少量的篇幅介绍了多核CPU调度算法，其目的也在于说明此结论。多核CPU调度算法中，无论是全局队列调度算法还是局部队列调度算法，其实现原理均可采用单核CPU调度算法中的某一个或一些综合起来实现。例如局部队列调度算法，每一个局部队列就相当于一个单核CPU调度队列，可以采用合适的单核CPU调度算法去实现。第二篇：电梯优先调度算法电梯优先调度算法电梯调度算法(msInterView)移臂调度算法包括以下四种：1）先来先服务算法：根据访问者提出访问请求的先后次序来决定执行次序。2）最短寻找时间优先调度算法：从等待的访问者中挑选寻找时间最短的那个请求执行，而不管访问者的先后次序。3）电梯调度扫描算法：从移动臂当前位置沿移动方向选择最近的那个柱面的访问者来执行，若该方向上无请求访问时，就改变移动方向再选择。4）单向扫描调度算法：从0柱面开始往里单向扫描，扫到哪个执行哪个。*///t1.cpp:定义控制台应用程序的入口点。//#include“stdafx.h”#include“math.h”#include“stdlib.h”#include“string.h”structHead{intnPosition;boolbVisited;};voidVisit(structHead*pHead){printf(“visitecy:%dn”,pHead->nPosition);pHead->bVisited=true;}intReadInputKeyboard(structHead*pHead,int*pCurrentPosition,intnMaxNumber){inti;printf(“pleaseinputCurrentposition:”);scanf(“%d”,pCurrentPosition);printf(“pleaseinputwillvisitposition:”);for(i=0;iscanf(“%d”,&pHead[i].nPosition);pHead[i].bVisited=false;if(pHead[i].nPosition<0)break;}returni;}intReadInputFile(structHead*pHead,int*pCurrentPosition,intnMaxNumber){inti;charszFileName[256],*q,*p,szTemp[20XXprintf(“pleaseinputfilename:”);scanf(“%s”,szFileName);FILE*pFile=fopen(szFileName,“r”);if(pFile==NULL){printf(“openfile%serror”,szFileName);return-1;}for(i=0;!feof(pFile)&&ip=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);returni;}intFifoVisit(intnCurrentPosition,structHead*pHead,intnNumber){//先来先服务intnHaveVisited=0;intnMoveDistance=0;inti;while(nHaveVisitedfor(i=0;iif(pHead[i].bVisited)continue;Visit(&pHead[i]);nHaveVisited++;nMoveDistance+=abs(nCurrentPosition-pHead[i].nPosition);nCurrentPosition=pHead[i].nPosition;}}printf(“thesumofmovedistance:%dn”,nMoveDistance);returnnMoveDistance;}intSsfoVisit(intnCurrentPosition,structHead*pHead,intnNumber){//最短寻找时间优先intnHaveVisited=0;intnMoveDistance=0;intnMinDistance=0;intnMinIndex=0;inti;while(nHaveVisitednMinDistance=0xffff;nMinIndex=0;//找最小值for(i=0;iif(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(“thesumofmovedistance:%dn”,nMoveDistance);returnnMoveDistance;}intDtVisit(intnCurrentPosition,boolbOut,structHead*pHead,intnNumber){//电梯调度算法intnHaveVisited=0;intnMoveDistance=0;intnMinDistance=0;intnMinIndex=0;inti;while(nHaveVisitednMinDistance=0xffff;nMinIndex=0;//找最小值for(i=0;iif(pHead[i].bVisited)continue;if(bOut&&pHead[i].nPositionnCurrentPosition){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(“thesumofmovedistance:%dn”,nMoveDistance);returnnMoveDistance;}intDxVisit(intnCurrentPosition,structHead*pHead,intnNumber){//单向调度算法intnHaveVisited=0;intnMoveDistance=0;intnMinDistance=0;intnMinIndex=0;inti;while(nHaveVisitednMinDistance=0xffff;nMinIndex=0;//找最小值for(i=0;iif(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(“thesumofmovedistance:%dn”,nMoveDistance);returnnMoveDistance;}intmain(intargc,char*argv[]){//p114structHeadmylist[20XX//={98,false,183,false,37,false,122,false,14,false,124,false,65,false,67,false};//intnCurrentPosition=53;//intnRealNumber=8;intnCurrentPosition=0;intnRealNumber=ReadInputFile(mylist,&nCurrentPosition,20XX//FifoVisit(nCurrentPosition,mylist,nRealNumber);//SsfoVisit(nCurrentPosition,mylist,nRealNumber);//DtVisit(nCurrentPosition,false,mylist,nRealNumber);DxVisit(nCurrentPosition,mylist,nRealNumber);return0;}第三篇：操作系统实验二——cpu调度与内存分页一、试验目的理解操作系统内存管理的原理及分页内存管理方案二、试验要求1、实现分页内存管理方案，假定页和帧的大小均为4KB，物理内存为128MB2、输入为进程ID，所需内存大小等，输出为页表。3、请按要求撰写实验报告，并和源程序一起打包上传4、实验平台不限，linux和windows均可5、与第一次实验的程序整合成一个程序三、试验环境WindowsXPVisualC++6.0四、试验内容为了与上一个实验结合，并且考虑到可能需要兼容以后的实验，所以本次实验不但重写了PCB，而且按照自己对操作系统的理解构造出了一虚拟的I/O设备和两套调度程序（作业调度程序和CPU调度程序）一、首先从与内存分配相关的作业调度函数说起，程序中为Jobs_scheduler。Job_scheduler的作用如下图所示;Job_scheduler从大容量存储设备上的缓冲池中载入新生成的进程到内存，同时生成新的PCB到就绪队列中。这里涉及到了两个数据结构classProgram，classPCB。Program：PCB：PCB中的state包含五个状态NEW、READY、RUN、WAITING、TERMINATED，加入到ReadyQueue中等待运行的PCB均为READY状态的，运行中会被置为RUN，WAITNG状态为等待I/O设备的进程，如果进程状态为TERMINATED，将会被移出作业队列。Job_scheduler函数在将program装入内存前，会查看帧表内空闲的帧的数目是否大于等于program所需的页数目，如果成立才装入，并且为PCB构造页表。构造时，先按照帧表通过顺序查找找到可用的帧，然后就将页的内容加载上去。二、接下来是CPU调度程序，也成为短期调度程序。CPU_scheduler所做的工作如下图所示，其操作的队列是就绪队列RedayQueue本程序采用的调度算法为分时调度，时间片大小TimeSlice取为1（当然这个随时都可用改动），里面执行程序的函数Run是模拟CPU功能的，它会返回一个值，Normal表示执行正常，若是返回了INTERRUPT中断；ERROR出错就会中断此次运行，并且将所指PCB从ReadyQueue中移除。这里的Run函数其实模拟了CPU的取指令和翻译指令的功能，本程序只有一个有实际作用的指令，'O'，如果内存中的内容为'0'（十进制ASCⅡ码值），则代表需要利用I/O设备输出该地址内容。如上图所示，PCB会加入到WaitingQueue中等待I/O，并判断此时I/O设备是否开启，如果未开启则开启设备。Run函数也因此返回一个interrupt值。运行结果在编号为1的进程中的第一个内存单位设置了一条I/O指令，可以看出其发生中断后等待I/O完成才重新回到ReadyQueue中并执行完毕。以上结果是在内存足够大的情况，下面再看一组内存不能同时满足需求的情况此次内存设为11帧，编号为1的进程需要10帧，编号为2的进程需要1帧，我们看到，2号进程顺利载入并执行了，但其他进程都要等到1号进程执行完释放内存后才能载入内存，符合预期情况。五、心得体会为了很好的仿真，本次试验尽可能地模拟了硬件的工作，如输入输出设备和模拟CPU的run函数，基本上把教材77页调度问题的队列图所示功能模拟出来了，也大体实现了从用户程序到系统进程再到硬件的执行过程。对于本次实验的核心内容——内存管理，实现了从磁盘到内存额装载过程，实现了页表的创建，实现了内存的释放。缺陷是没有考虑到换入换出等动态的情况，也就是说在此做了一个假设：每个进程相互独立且对于每个单独的进程来说，内存空间是足够大的。第二点缺陷是，没有按照题目要求分配那么多的内存空间，因为那么大输入输出不好控制。在本程序中，输入输出与要求有出入，并没有输入进程需要的时间，而是以进程的具体内容代替，在这里又有一个假设：假设进程在CPU中每执行一步需要一个单位的时间，这样进程的大小也就等价于进程需要的时间了（排除有I/O请求的情况），个人认为这样假设比人工限定执行时间更加贴近现实情况。程序的输入非即时的，而是通过事先设定好的5个进程加上运行后随机生成的若干进程，也是为了模拟实际情况考虑。因为全手工输入需要输入进程的到达时间，也就是需要根据到达时间来为缓冲池中进程排序的问题，但实际情况下到达时间是多余的，先创建的先加入队列即可，所以采用了随机生成的方式。为了此次实验，复习了调度和内存管理两章的大部分内容，对操作系统对进程调度和内存分配管理有了更深入的认识，但只是从概念上，没有看到真正操作系统的代码或者算法实例，所以可能很多地方的代码与实际情况出入很大。代码：#include#include#include#include#include#include#include#includeusingnamespacestd;/***************随机数，后面随机生成进程用的*************/voidrand_seed(){intseed=static_cast(time(0));srand(seed);}intrand_int(inta,intb){returna+rand()%(b1){pc[1]++;}else{pc[0]++;pc[1]=0;}pcb.state=READY;}elseif(pc[1]<1){pc[1]++;}elsepcb.state=TERMINATED;}boolio_equipment=OFF;/*I/O设备(DMA)*/DWORDWINAPIIOEquipment(LPVOIDlpParamter){io_equipment=ON;list::iteratorpw=WaitingQueue.begin();while(pw!=WaitingQueue.end()){/*为了体现I/O设备速度较慢，所以在此用了Sleep函数*/Sleep(1000);cout<<“P”<<pw->number<<“I/O:”<<(char)Memory[AddOfIO]<<endl;if(pw->state==WAITING)pw->state=READY;ReadyQueue.push_back(*pw);pw=WaitingQueue.erase(pw);if(pw!=WaitingQueue.end())pw++;elsepw=WaitingQueue.begin();}io_equipment=OFF;returnFINISH;}HANDLEioEquipment;/**模拟CPU执行只实现了部分功能，并没有完全按照原理模拟**/intRun(PCB&pcb){pcb.state=RUN;list::iteratorp=pcb.PageTable.begin();intaddr[2];addr[1]=pcb.pc[1];addr[0]=pcb.findframe(pcb.pc[0]);switch(Memory[addr[0]*FRAME+addr[1]]){case'O'://如果指令触发了输出设备pcb.state=WAITING;pcr[0]=pcb.pc[0];pcr[1]=pcb.pc[1];IncPc(pcb,pcr);pcb.pc[0]=pcr[0];pcb.pc[1]=pcr[1];AddOfIO=addr[0]*FRAME+addr[1];WaitingQueue.push_back(pcb);/*如果I/O设备未开启，则打开，否则什么都不做*/if(io_equipment==OFF)ioEquipment=CreateThread(NULL,0,IOEquipment,NULL,0,NULL);else;returnINTERRUPT;default:break;}/*在没有跳转的情况下，运行之后，pc自加*/pcr[0]=pcb.pc[0];pcr[1]=pcb.pc[1];IncPc(pcb,pcr);pcb.pc[0]=pcr[0];pcb.pc[1]=pcr[1];returnNORMAL;}HANDLEhMutex=CreateMutex(NULL,FALSE,“screen”);/*长期调度程序,将缓冲池中的进程加载到内存上*/DWORDWINAPIJobs_scheduler(LPVOIDlpParamter){list::iteratorp=BufferList.begin();while(true){//WaitForSingleObject(hMutex,INFINITE);if(p!=BufferList.end()&&p->page_numbers<=FraTable.free_frame){ReadyQueue.push_back(PCB(*p));p=BufferList.erase(p);}elseif(p!=BufferList.end())p++;elsep=BufferList.begin();//ReleaseMutex(hMutex);}}/*利用RR算法的短期调度程序*/DWORDWINAPICPU_scheduler(LPVOIDlpParamter){list::iteratorp=ReadyQueue.begin();intrun_time=0;inttotal_time=1;while(true){WaitForSingleObject(hMutex,INFINITE);if(p==ReadyQueue.end())p=ReadyQueue.begin();while(run_time<TimeSlice&&p->state==READY){p->run_time++;run_time++;//cout<<total_time++<<endl;cout<<“p”<<p->number<<“”<<“runtime”<<p->run_time<<endl;if(Run(*p)==NORMAL)/*donothing*/;else{p=ReadyQueue.erase(p);break;}/*操作系统负责计时*/}run_time=0;if(p->state==TERMINATED){Release(*p);p=ReadyQueue.erase(p);}else{p++;}ReleaseMutex(hMutex);}}intmain(){intnum=1;Programp1(num++,“O123456089”);Programp2(num++,“0”);Programp3(num++,“01”);Programp4(num++,“01”);Programp5(num++,“01234”);BufferList.push_back(p1);BufferList.push_back(p2);BufferList.push_back(p3);BufferList.push_back(p4);BufferList.push_back(p5);HANDLEhThread1=CreateThread(NULL,0,Jobs_scheduler,NULL,0,NULL);HANDLEhThread2=CreateThread(NULL,0,CPU_scheduler,NULL,0,NULL);while(true){if(num<7)BufferList.push_back(Program(num++,“156789”));}return0;}第四篇：常用进程调度算法的分析与评价常用进程调度算法的分析与评价（一）20XX-10-3122:48进程调度是按照某种调度算法从就绪状态的进程中选择一个进程到处理机上运行。进程调度的两种方式：(1)非抢占调度方式在这种调度方式中，OS一旦把处理机分配给某个就绪状态的进程后，就让该进程一直执行下去，直至该进程完成或由于该进程等待某事件发生而被阻塞时，才把处理机分配给其他进程。(2)抢占调度方式在这种调度方式中，进程调度程序可根据某种原则停止正在执行的进程，将已分配给当前进程的处理机收回，重新分配给另一个处于就绪状态的进程。抢占进程调度的原则：（1）时间片原则：各进程按系统分配给的一个时间片运行，当该时间片用完或由于该进程等待某事件发生而被阻塞时，系统就停止该进程的执行而重新进行调度。（2）优先级原则：每个进程均赋于一个调度优先级，通常一些重要和紧急的进程赋于较高的优先级。当一个新的紧迫进程到达时，或者一个优先级高的进程从阻塞状态变成就绪状态的时，如果该进程的优先级比当前进程的优先级高，OS就停止当前进程的执行，将处理机分配给该优先级高的进程，使之执行。（3）短进程优先原则：当新到达的作业对应的进程比正在执行的作业对应进程的运行时间明显短时，系统剥夺当前进程的执行，而将处理机分配给新的短进程，使之优先执行。进程调度算法评价依据进程调度性能的衡量方法可以分为定性和定量两种，在定性衡量方面，首先是调度的安全性。比如，一次进程调度是否可能引起数据结构的破坏等。这要求对调度时机的选择和保存CPU现场十分小心。另外，系统开销也是衡量进程调度的一个重要指标，由于调度程序的执行涉及到多个进程的上下文切换，如果调度策略过于繁琐和复杂，将会耗去较大的系统开销。这在用户进程调度系统调用较多的情况下，将会造成响应时间大幅度增加。进程调度的定量评价包括CPU的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。实际上，由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，从而对进程调度进行解析是很困难的，一般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。常用进程调度算法的分析与评价（二）20XX-11-0120XX2四种常用进程调度算法的分析与评价3.1先来先服务算法3.1.1算法思想该算法思想是按照进入就绪队列的先后次序来分配处理机。FCFS采用非剥夺调度方式，即一旦某个进程占有处理机，就一直运行下去，直到该进程完成其工作或因等待某一事件而不能继续执行时才释放处理机。3.1.2算法实现原理图该算法实现原理图如图1所示。说明：Ready表示就绪队列，Pi表示新进入队列的进程，Finish表示进程运行完毕退出。3.1.3算法分析与评价①该算法原理简单，易于实现。②各进程平等竞争。③由于各进程执行的时间不一样，从而导致相对不公平现象的产生。④该算法有利于长进程，不利于短进程。⑤该算法很少用来作为主调度策略，常常用作辅助调度算法使用3.2最高优先权优先调度算法3.2.1算法思想该算法的基本思想是进程优先权高者优先调度，是一种最常用的进程调度算法。该算法的关键是如何确定优先数。通常确定优先数的方法有两种，即静态法和动态法。静态优先权是在创建进程时确定的，其运行特征是优先数确定之后在整个进行运行期间不再改变。确定静态优先权的依据有进程的类型、进程所使用的资源、进程的估计运行时间等因素。进程所申请的资源越多，估计的运行时间越长，进程的优先权越低。进程类型不同，优先权也不同，如系统进程的优先权高于用户进程的优先权。动态优先权是指在创建进程时，其运行特征是根据系统资源的使用情况和进程的当前特点确定一个优先权，在进程运行过程中再根据情况的变化调整优先权。动态优先权一般根据进程占有CPU时间的长短、进程等待CPU时间的长短等因素确定。占有处理机的时间越长，则优先权越低；等待时间越长，则优先权越高。3.3.2算法分析与评价①静态优先级调度算法实现较为简单，但不能反映系统以及进程在运行过程中发生的各种变化。而动态优先级法可以满足这个方面的需要。②动态优先级调度算法的性能一般介于时间片轮转算法和先来先服务算法之间。常用进程调度算法的分析与评价（三）20XX-11-0120XX33.3时间片轮转调度算法3.3.1算法思想该算法思想是使每个进程在就绪队列中的等待时间与享受服务的时间成比例。即将CPU的处理时间分成固定大小的时间片，如果在执行的一个进程把它分给它的时间片用完了，但任务还没有完成，则它也只能停止下来，释放它所占的CPU资源，然后排在相应的就绪队列的后面去。3.3.2算法实现原理图该算法实现原理图如图2所示说明：Ready表示就绪队列，Pi表示新进入队列的进程，Finish表示进程运行完毕退出。NotFinish表示分配给某进程的时间片已用完但任务还没有完成，从而插入到Ready队列尾部。3.3.3算法分析与评价①时间片的长度选择比较困难时间片的长度选择比较困难是因为时间片长度的选择直接关系到系统开销和进程的响应时间。如果时间片长度过短→导致调度程序剥夺处理器的次数增加→进程的上下文切换的次数增加→系统的开销也加重；如果时间片长度过长，长到能使就绪队列中所需要执行时间最长的进程执行完毕→轮转法就变成了FCFS算法→FCFS短处不足就显示出来了。又因为CPU的整个执行时间＝各进程执行时间之和＋系统开销（各进程切换所花费的CPU时间之和，假定存储开销忽略不计）。即。因此，时间片的长短通常需要由以下因素确定：↙系统的响应时间。↙就绪队列中的进程数。↙进程的切换时间。↙计算机的处理能力，计算机的速度越高，时间片就可越短。②时间片长度选择的动态性以上仅仅作了静态分析，通常情况下，就绪队列里地进程个数是不断变化的。因此，每一次的调度都需要计算新一轮的时间片长度，不能用固定的时间片长度来进行所有进程的轮转执行。③该算法的扩充——多级反馈轮转法在上面的算法中，未对就绪队列中的进程加以条件分析（即进入就绪队列的因素），由于进入就绪队列的原因不一样，要求占用处理机的紧急程度也不一样。主要因素有：↙分给该进程的时间片用完，但进程还未完成。↙分给其时间片未用完，而发生了I/O等请求后由阻塞态转变成就绪态。↙新的进程进入。因此，根据紧急程度的不一样，建立多个就绪队列，同时赋予不同的的优先级，优先权高的就绪队列优先执行，同一就绪队列中，优先级相同，按照先来先服务进行调度，运行一个给定的时间片，如果没有执行完成则转入到相应的就绪队列中去（运行一次，优先级降低一个等级，等待一个时间片，则优先级升高一个等级）。其实现原理图如图3所示。3.4短进程优先调度算法3.4.1算法思想该算法的基本思想是从就绪队列（内存）中选择一个估计运行时间最短的进程，将处理机分配给它。3.4.2算法分析与评价①该算法能有效降低作业的平均等待时间，提高系统吞吐量。②对长进程不利，甚至导致长期得不到处理。③该算法完全未考虑进程的紧迫程度。④进程的长短通常由某种策略估计提供，不能做到真正的短进程优先。4结语综述所述，本文从算法思想、算法的实现原理、算法的优缺点等几个方面对先来先服务算法、时间片轮转算法、最高优先权优先调度算法、短进程优先调度算法等四种进程调度算法进行详细地论述。（转自《计算机与信息技术》）第五篇：电梯调度算法总结1.传统电梯调度算法1.1先来先服务算法(FCFS)先来先服务(FCFS-FirstComeFirstServe)算法，是一种随即服务算法，它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，它是一种最简单的电梯调度算法。它根据乘客请求乘坐电梯的先后次序进行调度。此算法的优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求长期得不到满足的情况[12]。这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，这种算法的性能就会严重下降，甚至恶化。人们之所以研究这种在载荷较大的情况下几乎不可用的算法，有两个原因：(1)任何调度算法在请求队列长度为1时，请求速率极低或相邻请求的间隔为无穷大时使用先来先服务算法既对调度效率不会产生影响，而且实现这种算法极其简单。(2)先来先服务算法可以作为衡量其他算法的标准。1.2最短寻找楼层时间优先算法(SSTF)最短寻找楼层时间优先(SSTF-ShortestSeekTimeFirst)[14]算法，它注重电梯寻找楼层的优化。最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“饿死”现象。1.3扫描算法(SCAN)扫描算法(SCAN)是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。它进行寻找楼层的优化，效率比较高，但它是一个非实时算法。扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的，所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成，免去了电梯频繁的来回移动[2]。扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻找楼层时间优先算法小，从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法稳定。1.4LOOK算法LOOK算法[18]是扫描算法的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。但当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。1.5SAFT算法SATF(ShortestAccessTimeFirst)[15,19]算法与SSTF算法的思想类似，唯一的区别就是SATF算法将SSTF算法中的寻找楼层时间改成了访问时间。这是因为电梯技术发展到今天，寻找楼层的时间已经有了很大地改进，但是电梯的运行当中等待乘客上梯时间却不是人为可以控制。SATF算