高优先权调度算法例题

① 动态高优先权优先调度算法

动态高优先权优先调度算法：

动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值，那么，对于优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降，则可防止一个长作业长期地垄断处理机。

算法代码模拟实现：

#include<stdio.h>
#include<stdlib.h>
#defineN6

//待插入就绪队列的进程数据
intid[N]={0,1,
2,3,4,
5};
intpriority[N]={9,38,17,
2,7,18};
intcpuTime[N]={0,
0,0,0,
0,0};
intallTime[N]={3,
2,3,6,
1,3};

//********************************
//
//模拟进程/PCB数据结构
//
//********************************

//
枚举进程的状态：就绪、执行、阻塞、完成
enumSTATE{Ready,Run,Block,Finish
};

//建立PCB结构体
structPCB{
intid;//标志数
intpriority;//优先数
intcpuTime;//
已占CPU时间
intallTime;//
还需占CPU时间
intblockTime;//已被阻塞的时间
STATEstate;//
进程状态
PCB*pre;//
PCB的前指针
PCB*nxt;//
PCB的后指针
};

//********************************
//
//模拟进程队列
//
//********************************

//进程入列
voidqueQush(PCB*process,PCB
*queHead)
{
process->pre=NULL;
process->nxt=
queHead->nxt;
if(queHead->nxt!=NULL){
//非第一个入列
queHead->nxt->pre=
process;
}
queHead->nxt=process;
}

//进程出列
voidquePop(PCB*process,PCB
*queHead)
{
if(process->pre!=NULL){
//不是头节点
process->pre->nxt=
process->nxt;
}
else{
queHead->nxt=
process->nxt;
}
if(process->nxt!=NULL){
//不是尾节点
process->nxt->pre=
process->pre;
}
//
清空进程指针
process->pre=process->nxt=
NULL;
}

//查看队列里进程的信息
voidqueWalk(PCB*queHead)
{
PCB*pro=queHead->nxt;
if(pro==NULL){
printf("(无进程)
");
return;
}
while(pro!=NULL)
{
printf("id:%d,
pri:%d,alltime:%d
",
pro->id,
pro->priority,
pro->allTime);
pro=
pro->nxt;
}
}

//********************************
//
//模拟就绪队列
//
//********************************

intreadyQueNum;//就绪队列的进程数量
PCBreadyQueHead;//
就绪队列的头部
PCB*readyMaxProcess;//就绪队列中优先级最高的进程

//进程插入到就绪队列
voidreadyQueQush(PCB
*process)
{
readyQueNum++;
process->state=Ready;
queQush(process,&readyQueHead);
}

//优先级最高的进程出列
PCB*readyQuePop()
{
readyQueNum--;
quePop(readyMaxProcess,
&readyQueHead);
returnreadyMaxProcess;
}

//每个时间片，更新就绪队列里进程的信息
voidreadyQueUpdate()
{
intmaxPriority=-1;
PCB*pro=readyQueHead.nxt;
if(pro==NULL){
//就绪队列没有进程
readyMaxProcess=
NULL;
return;
}
while(pro!=NULL)
{
pro->priority
++;
if(pro->priority>maxPriority)
{
maxPriority=
pro->priority;
readyMaxProcess=pro;
}
pro=
pro->nxt;
}
}

//返回就绪队列最高优先级的值
intreadyMaxPriority()
{
returnreadyMaxProcess->priority;
}

//查看就绪队列里进程的信息
voidreadyQueWalk()
{
printf("就绪队列里的进程信息为：
");
queWalk(&readyQueHead);
}

//********************************
//
//模拟阻塞队列
//
//********************************

#defineEndBlockTime3
//进程最长被阻塞时间

intblockQueNum;//阻塞队列的进程数量
PCBblockQueHead;//
阻塞队列的头部
PCB*blockMaxProcess;//阻塞队列中优先级最高的进程

//进程插入到阻塞队列
voidblockQueQush(PCB
*process)
{
blockQueNum++;
process->blockTime=0;
process->state=Block;
queQush(process,&blockQueHead);
}

//优先级最高的进程出列
PCB*blockQuePop()
{
blockQueNum--;
quePop(blockMaxProcess,
&blockQueHead);
returnblockMaxProcess;
}

//每个时间片，更新阻塞队列里进程的信息
voidblockQueUpdate()
{
intmaxPriority=-1;
PCB*pro=blockQueHead.nxt;
while(pro!=NULL)
{
pro->blockTime
++;
if(pro->blockTime>=EndBlockTime)
{
PCB*process=pro;
pro=pro->nxt;
//阻塞时间到，调入就绪队列
blockQueNum--;
quePop(process,
&blockQueHead);
readyQueQush(process);
}else
if(pro->priority>maxPriority)
{
//更新阻塞队列里优先级最高的进程指针
maxPriority=
pro->priority;
blockMaxProcess=pro;
pro=pro->nxt;
}
}
}

//查看阻塞队列里进程的信息
voidblockQueWalk()
{
printf("阻塞队列里的进程信息为：
");
queWalk(&blockQueHead);
}

//********************************
//
//模拟动态优先权的进程调度
//
//********************************

//初始化数据
voidinitData()
{
//
初始化就绪队列和阻塞队列
readyQueNum=blockQueNum=0;
readyMaxProcess=blockMaxProcess=NULL;
readyQueHead.pre=readyQueHead.nxt=NULL;
blockQueHead.pre=blockQueHead.nxt=NULL;

//
初始化进程进入就绪队列
inti,maxPriority=-1;
for(i=0;i<N;i
++)
{
//分配一个PCB的内存空间
PCB*pro=(PCB
*)malloc(sizeof(PCB));
//给当前的PCB赋值
pro->id
=id[i];
pro->priority
=priority[i];
pro->cpuTime
=cpuTime[i];
pro->allTime
=allTime[i];
pro->blockTime
=0;
if(pro->allTime>0){
//插入到就绪队列中
readyQueQush(pro);
//更新就绪队列优先级最高的进程指针
if(pro->priority>
maxPriority){
maxPriority=pro->priority;
readyMaxProcess=pro;
}
}
}
}

//模拟cpu执行1个时间片的操作
voidcpuWord(PCB
*cpuProcess)
{
cpuProcess->priority-=3;
if(cpuProcess->priority<0)
{
cpuProcess->priority=0;
}
cpuProcess->cpuTime++;
cpuProcess->allTime--;
//
显示正执行进程的信息：
printf("CPU正执行的进程信息为：
");
printf("id:M,pri:M,
alltime:M
",
cpuProcess->id,
cpuProcess->priority,
cpuProcess->allTime);
}

intmain()
{
inttimeSlice=0;//
模拟时间片
intcpuBusy=0;
//模拟cpu状态
PCB*cpuProcess=NULL;//当前在cpu执行的进程
//
初始化数据
initData();
//
模拟进程调度
while(1)
{
if(readyQueNum==0
&&blockQueNum==0
&&cpuBusy==0){
//就绪队列、阻塞队列和cpu无进程，退出
break;
}
//printf("
%d%d",
readyQueNum,blockQueNum);
if(cpuBusy==0)
{
//cpu空闲，选择一个进程进入cpu
if(readyQueNum>0)
{
//
选择绪队列优先级最高的进程
cpuProcess
=readyQuePop();
}else{
//
就绪队列没有进程，改为选择阻塞队列优先级最高的进程
cpuProcess
=blockQuePop();
}
cpuProcess->cpuTime=
0;
cpuProcess->state=
Run;
cpuBusy=1;
}
timeSlice++;
printf("
第%d个时间片后：
",
timeSlice);
//
模拟cpu执行1个时间片的操作
cpuWord(cpuProcess);
if(cpuProcess->allTime==0){
cpuProcess->state=
Finish;
//释放已完成进程的PCB
free(cpuProcess);
cpuBusy=0;
}
//
更新就绪队列和阻塞队列里的进程信息
blockQueUpdate();
readyQueUpdate();
//
查看就绪队列和阻塞队列的进程信息
readyQueWalk();
blockQueWalk();
if(cpuBusy==1
&&readyQueNum>0
&&
cpuProcess->priority
<readyMaxPriority()){
//需抢占cpu，当前执行的进程调入阻塞队列
blockQueQush(cpuProcess);
cpuProcess=readyQuePop();
}
}
printf("
模拟进程调度算法结束
");
return0;
}

② 最高优先权优先调度和先进先出的区别

最高优先权优先调度（Highest Priority First，HPF）是一种调度算法，其核心思想是把所有排队等待被执行的任务按照优先级进行排序，并把优先级最高的任务放到队列的前面，依次进行调度。
先进先出（First In First Out，FIFO）是另一种调度算法，它的核心思想是把所有排队等待被执行的任务按照入队的时间顺序排序，先进入队列的任务优先被调度。
两种调度算法都用于提高系统的资源利用率，但是它们的实现方式和优先级判定标准不同。最高优先权优先调度算法强调优先级的重要性，会把优先级最高的任务作为优先执行的对象，而先进先出算法则主要关注时间的顺序，按照先进先出的顺序依次执行任务。

③ 第三章 进程调度的几种方式

进程调度概念：操作系统必须为多个，吗进程可能有竞争的请求分配计算机资源。对处理器而言，可分配的资源是在处理器上的执行时间，分配途径是调度。调度功能必须设计成可以满足多个目标，包括公平、任何进程都不会饿死、有效地使用处理器时间和低开销。此外，调度功能可能需要为某些进程的启动或结束考虑不同的优先级和实时最后期限。

这些年以来，调度已经成为深入研究的焦点，并且已经实现了许多不同的算法。如今，调度研究的重点是开发多处理系统，特别是用于多线程的。

下面简介几种调度算法。

一、先来先服务和短作业(进程)优先调度算法

1．先来先服务调度算法

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

2．短作业(进程)优先调度算法

短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

二、高优先权优先调度算法

1．优先权调度算法的类型

为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。

1) 非抢占式优先权算法

在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。

2) 抢占式优先权调度算法

在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i 时，就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i 进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

2．高响应比优先调度算法

在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：

由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：

由上式可以看出：

(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。

(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。

(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。因此，该算法实现了一种较好的折衷。当然，在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。

三、基于时间片的轮转调度算法

1．时间片轮转法

1) 基本原理

在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。

2．多级反馈队列调度算法

前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下所述。

(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。

(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。

(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。