单核与多核的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（Shortest Remaining Time First）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 多级队列调度算法（multilevel queue-scheduling algorithm）将Ready队列分成多个独立的队列，对Ready队列和每个独立的队列采用不同的调度算法进行执行。常用的方式是，Ready队列采用优先级调度算法，不同队列根据实际情况采用合适的调度算法即可。

优点：综合了多种调度算法，避免了starvation现象，最大限度地提高了调度效率，也提高了CPU利用率。3.2 多级反馈队列调度算法

UNIX OS采用的调度算法。其详细过程如下： 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调度算法去实现。

第二篇：操作系统实验二——cpu调度与内存分页

一、试验目的

理解操作系统内存管理的原理及分页内存管理方案

二、试验要求

1、实现分页内存管理方案，假定页和帧的大小均为4KB，物理内存为128MB

2、输入为进程ID，所需内存大小等，输出为页表。

3、请按要求撰写实验报告，并和源程序一起打包上传

4、实验平台不限，linux和windows均可

5、与第一次实验的程序整合成一个程序

三、试验环境

Windows XP Visual C++ 6.0

四、试验内容

为了与上一个实验结合，并且考虑到可能需要兼容以后的实验，所以本次实验不但重写了PCB，而且按照自己对操作系统的理解构造出了一虚拟的I/O设备和两套调度程序（作业调度程序和CPU调度程序）

一、首先从与内存分配相关的作业调度函数说起，程序中为Jobs_scheduler。Job_scheduler的作用如下图所示;

Job_scheduler从大容量存储设备上的缓冲池中载入新生成的进程到内存，同时生成新的PCB到就绪队列中。这里涉及到了两个数据结构class Program，class PCB。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 #include using namespace std;

/***************

随机数，后面随机生成进程用的 *************/ void rand_seed(){ int seed = static_cast(time(0));srand(seed);}

int rand_int(int a, int b){ return a + rand()%(b1)

{

pc[1]++;

}

else

{

pc[0]++;

pc[1] = 0;

}

pcb.state = READY;} else if(pc[1] < PAGE-1){

pc[1]++;} else

pcb.state = TERMINATED;}

bool io_equipment = OFF;/* I/O设备(DMA)*/ DWORD WINAPI IOEquipment(LPVOID lpParamter){ io_equipment = ON;list

::iterator pw = 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++;

else

pw = WaitingQueue.begin();} io_equipment = OFF;return FINISH;}

HANDLE ioEquipment;/**

模拟CPU执行

只实现了部分功能，并没有完全按照原理模拟

**/ int Run(PCB& pcb){ pcb.state = RUN;list

::iterator p = pcb.PageTable.begin();int addr[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

;

return INTERRUPT;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];

return NORMAL;}

HANDLE hMutex = CreateMutex(NULL, FALSE, “screen”);

/* 长期调度程序,将缓冲池中的进程加载到内存上 */ DWORD WINAPI Jobs_scheduler(LPVOID lpParamter){ list

::iterator p = 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);

}

else if(p!= BufferList.end())

p++;

else

p = BufferList.begin();

//ReleaseMutex(hMutex);

} }

/* 利用RR算法的短期调度程序 */ DWORD WINAPI CPU_scheduler(LPVOID lpParamter){ list

::iterator p = ReadyQueue.begin();int run_time = 0;int total_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 << “ ” << “run time ” << p->run_time << endl;

if(Run(*p)== NORMAL)

/* do nothing */;

else

{

p = ReadyQueue.erase(p);

break;

}

/* 操作系统负责计时 */

}

run_time = 0;

if(p->state == TERMINATED)

{

Release(*p);

p = ReadyQueue.erase(p);

}

else

{

p++;

}

ReleaseMutex(hMutex);} }

int main(){ int num = 1;Program p1(num++, “O123456089”);Program p2(num++, “0”);Program p3(num++, “01”);Program p4(num++, “01”);Program p5(num++, “01234”);BufferList.push_back(p1);BufferList.push_back(p2);BufferList.push_back(p3);BufferList.push_back(p4);BufferList.push_back(p5);

HANDLE hThread1 = CreateThread(NULL, 0, Jobs_scheduler, NULL, 0, NULL);HANDLE hThread2 = CreateThread(NULL, 0, CPU_scheduler, NULL, 0, NULL);while(true)

{

if(num < 7)

BufferList.push_back(Program(num++, “156789”));}

return 0;}

第三篇：电梯优先调度算法

电梯优先调度算法

电梯调度算法(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].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(“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;}

第四篇：常用进程调度算法的分析与评价

常用进程调度算法的分析与评价

（一）2009-10-31 22:48

进程调度是按照某种调度算法从就绪状态的进程中选择一个进程到处理机上运行。进程调度的两种方式 ：

(1)非抢占调度方式

在这种调度方式中，OS一旦把处理机分配给某个就绪状态的进程后，就让该进程一直执行下去，直至该进程完成或由于该进程等待某事件发生而被阻塞时，才把处理机分配给其他进程。

(2)抢占调度方式

在这种调度方式中，进程调度程序可根据某种原则停止正在执行的进程，将已分配给当前进程的处理机收回，重新分配给另一个处于就绪状态的进程。

抢占进程调度的原则：

（1）时间片原则：各进程按系统分配给的一个时间片运行，当该时间片用完或由于该进程等待某事件发生而被阻塞时，系统就停止该进程的执行而重新进行调度。

（2）优先级原则：每个进程均赋于一个调度优先级，通常一些重要和紧急的进程赋于较高的优先级。当一个新的紧迫进程到达时，或者一个优先级高的进程从阻塞状态变成就绪状态的时，如果该进程的优先级比当前进程的优先级高，OS就停止当前进程的执行，将处理机分配给该优先级高的进程，使之执行。

（3）短进程优先原则：当新到达的作业对应的进程比正在执行的作业对应进程的运行时间明显短时，系统剥夺当前进程的执行，而将处理机分配给新的短进程，使之优先执行。进程调度算法评价依据

进程调度性能的衡量方法可以分为定性和定量两种，在定性衡量方面，首先是调度的安全性。比如，一次进程调度是否可能引起数据结构的破坏等。这要求对调度时机的选择和保存CPU现场十分小心。另外，系统开销也是衡量进程调度的一个重要指标，由于调度程序的执行涉及到多个进程的上下文切换，如果调度策略过于繁琐和复杂，将会耗去较大的系统开销。这在用户进程调度系统调用较多的情况下，将会造成响应时间大幅度增加。

进程调度的定量评价包括CPU的利用率评价、进程在就绪队列中的等待时间与执行时间之比等。实际上，由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，从而对进程调度进行解析是很困难的，一般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。

常用进程调度算法的分析与评价

（二）2009-11-01 20:22

四种常用进程调度算法的分析与评价

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 算法分析与评价

① 静态优先级调度算法实现较为简单，但不能反映系统以及进程在运行过程中发生的各种变化。而动态优先级法可以满足这个方面的需要。

② 动态优先级调度算法的性能一般介于时间片轮转算法和先来先服务算法之间。

常用进程调度算法的分析与评价

（三）2009-11-01 20:23

3.3时间片轮转调度算法

3.3.1 算法思想

该算法思想是使每个进程在就绪队列中的等待时间与享受服务的时间成比例。即将CPU的处理时间分成固定大小的时间片，如果在执行的一个进程把它分给它的时间片用完了，但任务还没有完成，则它也只能停止下来，释放它所占的CPU资源，然后排在相应的就绪队列的后面去。

3.3.2 算法实现原理图

该算法实现原理图如图2所示

说明：Ready表示就绪队列，Pi表示新进入队列的进程，Finish表示进程运行完毕退出。Not Finish表示分配给某进程的时间片已用完但任务还没有完成，从而插入到Ready队列尾部。

3.3.3 算法分析与评价

① 时间片的长度选择比较困难

时间片的长度选择比较困难是因为时间片长度的选择直接关系到系统开销和进程的响应时间。如果时间片长度过短→导致调度程序剥夺处理器的次数增加→进程的上下文切换的次数增加→系统的开销也加重；如果时间片长度过长，长到能使就绪队列中所需要执行时间最长的进程执行完

毕→轮转法就变成了FCFS算法→FCFS短处不足就显示出来了。

又因为CPU的整个执行时间＝各进程执行时间之和＋系统开销（各进程切换所花费的CPU时间之和，假定存储开销忽略不计）。即。因此，时间片的长短通常需要由以下因素确定：↙系统的响应时间。

↙就绪队列中的进程数。

↙进程的切换时间。

↙ 计算机的处理能力，计算机的速度越高，时间片就可越短。

② 时间片长度选择的动态性

以上仅仅作了静态分析，通常情况下，就绪队列里地进程个数是不断变化的。因此，每一次的调度都需要计算新一轮的时间片长度，不能用固定的时间片长度来进行所有进程的轮转执行。③ 该算法的扩充——多级反馈轮转法

在上面的算法中，未对就绪队列中的进程加以条件分析（即进入就绪队列的因素），由于进入就绪队列的原因不一样，要求占用处理机的紧急程度也不一样。主要因素有：↙分给该进程的时间片用完，但进程还未完成。

↙ 分给其时间片未用完，而发生了I/O等请求后由阻塞态转变成就绪态。

↙新的进程进入。

因此，根据紧急程度的不一样，建立多个就绪队列，同时赋予不同的的优先级，优先权高的就绪队列优先执行，同一就绪队列中，优先级相同，按照先来先服务进行调度，运行一个给定的时间片，如果没有执行完成则转入到相应的就绪队列中去（运行一次，优先级降低一个等级，等待一个时间片，则优先级升高一个等级）。其实现原理图如图3所示。

3.4 短进程优先调度算法

3.4.1 算法思想

该算法的基本思想是从就绪队列（内存）中选择一个估计运行时间最短的进程，将处理机分配给它。

3.4.2 算法分析与评价

① 该算法能有效降低作业的平均等待时间，提高系统吞吐量。

② 对长进程不利，甚至导致长期得不到处理。

③ 该算法完全未考虑进程的紧迫程度。

④ 进程的长短通常由某种策略估计提供，不能做到真正的短进程优先。

4结语

综述所述，本文从算法思想、算法的实现原理、算法的优缺点等几个方面对先来先服务算法、时间片轮转算法、最高优先权优先调度算法、短进程优先调度算法等四种进程调度算法进行详细地论述。（转自《计算机与信息技术》）

第五篇：操作系统课程设计-磁盘调度算法

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 #include #include void menu(){ cout<<“*********************菜单*********************”<

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(iqueue[i]){ i++;} if(i>n-1)return n-1;//当前磁道号大于磁盘请求序列中的所有磁道 if(i==0)return-1;//当前磁道号小于磁盘请求序列中的所有磁道 else return i-1;//返回小于当前磁道号中最大的一个 } /*=================使用冒泡算法从小到大排序==============*/ int *bubble(int queue[],int m){ int i,j;int temp;for(i=0;i queue[j]){ temp=queue[i];queue[i]=queue[j];queue[j]=temp;} } cout<<“排序后的磁盘序列为：”;for(i=0;i

/* ====================以下是FCFS算法==================*/ void FCFS(int queue[],int n,int diskrode,int headstarts)//queue是请求调度序列，n为其个数，diskroad为磁盘磁道数，headstarts为正在调度的磁道 { cout<<“************以下为FCFS调度算法***********”<queue[0])count +=headstarts-queue[0];else count+=queue[0]-headstarts;cout<<“调度序列为: ”;cout<queue[i+1])count +=queue[i]-queue[i+1];else count +=queue[i+1]-queue[i];} cout<

/*=====================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调度算法***********”<=0;i--)cout<=headstarts)//若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务 { cout<<“磁盘扫描序列为： ”;cout<queue[0] && headstarts =0)&&(r

-headstarts)){ cout<=0;j--){ cout<

/*======================以下是SCAN算法====================*/ void SCAN(int queue[], int n, int diskrode, int headstarts){ int direction, i, fixi;cout<<“***********以下是SCAN调度算法*************”<>direction;double count=0;*bubble(queue,n);fixi = fix(queue,n,headstarts);cout<=0;i--){ cout<=0;i--)//从大到小 { cout<-1;i--){ cout<-1;i--)//从大到小 { cout<

/*======================以下是CSCAN算法====================*/ void CSCAN(int queue[],int n,int diskrode,int headstarts){ int direction,i,fixi;cout<<“***********以下是CSCAN调度算法*************”<>direction;int count=0;//count表示磁道移动的长度 *bubble(queue,n);fixi=fix(queue,n,headstarts);cout<<“调度序列为: ”<-1;--i){ cout<-1;--i){ cout<-1;i--){ cout<fixi;i--){ cout<

void main(){ int n, i, diskrode, headstarts;//n表示调度磁盘请求序列queue的长度，diskrode表示磁盘磁道的个数，headstarts表示目前正在调度的磁道； cout<<“请输入磁盘的总磁道数:”<> diskrode;cout<<“请输入磁盘调度请求序列个数:”<>n;int *queue;queue =(int*)malloc(n*sizeof(int));//给quneue数组分配空间...int *queue_copy;queue_copy =(int*)malloc(n*sizeof(int));cout<<“请依次输入该序列的值:”<>queue[i];for(i=0;i>headstarts;int menux;menu();cout<<“请按菜单选择，输入相应的数字: ”;cin>>menux;while(menux!=0){ if(menux ==1)FCFS(queue,n,diskrode,headstarts);

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<<“程序结束,谢谢使用！”<>menux;cout<