优先调度算法

‘壹’ 短作业优先调度算法和优先级为基础的非抢占式调度算法

短进程优先算法是一种非剥夺式算法，总是选取预计作业时间最短的作业优先运行；最短剩余时间优先算法是非剥夺式的，但可以改造成剥夺式的调度算法，称抢占式最短作业优先算法。

‘贰’ 优先级调度算法是什么

优先级算法是指在进程创建时先确定一个初始优先数，以后在进程运行中随着进程特性的改变不断修改优先数，这样，由于开始优先数很低而得不到CPU的进程，就能因为等待时间的增长而优先数变为最高而得到CPU运行。

‘叁’ 高响应比优先调度算法的原理

高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。
该算法中的响应比是指作业等待时间与运行比值，响应比公式定义如下：
响应比 =（等待时间+要求服务时间）/ 要求服务时间,即RR=（w+s）/s=1+w/s，因此响应比一定是大于1的。
如实例：
某系统有3个作业，系统确定它们在全部到达后，再开始采用响应比高者优先的调度算法，则它们的调度顺序是什么？各自的周转时间是什么？
作业号 提交时间 运行时间
1 8.8 1.5
2 9.0 0.4
3 9.5 1.0
(1)如果都到达再算的话,等待时间=最后一个的提交时间-该作业到达的时刻
1: 9.5-8.8=0.7
2: 9.5-9=0.5
3: 0
所以响应比为（等待时间+要求服务时间）要求服务时间=等待时间/要求服务时间+1
1: 0.7/1.5+1=1.47
2: 0.5/0.4+1=2.25
3: 1
所以2先运行,2从9.5开始运行到9.9结束;
再以9.9时刻算响应比:
1: (9.9-8.8)/1.5+1=1.73
3: (9.9-9.5)/1+1=1.4
所以2执行完后1开始执行,从9.9执行到11.4结束
最后一个是3:从11.4开始执行到12.4结束
(2)如果不是都到达后才运行，那么在8.8时只有作业1到达，所以先运行作业1
8.8+1.5（运行时间）=10.3
到10.3的时候作业1完成，此时作业2和3都已到达所以计算其响应比
（等待时间+要求服务时间）要求服务时间=等待时间/要求服务时间+1
作业2：（10.3-9.0）/0.4+1=4.325
作业3：（10.3-9.5）/1.0+1=1.8
所以先运行作业2
10.3+0.4=10.7
到10.7运行作业3
10.7+1.0=11.7
到11.7结束

‘肆’ 高响应比优先调度算法

- - 你是西农的吧

‘伍’ 动态高优先权优先调度算法

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

动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率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;
}

‘陆’ 什么是高响应比优先调度算法，它采用何种调度方式

高响应比优先调度算法就是把CPU分配给就绪队列中响应比最高的进程。响应比=等待时间/要求服务时间+1。采用非抢占式调度方式。030

‘柒’ 为什么说响应比高者优先调度算法是对先来先服务以及短作业优先这两种调度算法的折中

先来先服务的作业调度算法，重点考虑的是作业在后备作业队列里的等待时间，因此对短作业不利；短作业优先的作业调度算法，重点考虑的是这样所需要的CPU时间（当然，这个时间是用户自己估计的），因此对长作业不利；“响应比高者优先”的作业调度算法，试图综合这两方面的因素，以便能更好的满足各种用户的需要。
所谓一个作业的响应比，是指该作业已经等待的时间与所需运行时间的比，即：
响应比=（已等待时间）/（所需CPU时间）
该比值的分母是不变的，但是随着时间的推移，一个作业的“已等待时间”会不断地发生变化。显然，短作业比较容易获得较高的响应比，这是因为它们的分母比较小，只需稍加等待，整个比值就会上升。另一方面，长作业的分母虽然很大，但随着等待时间的增加，比值也会逐渐上升，从而获得较高的响应比。根据这种分析，“可见响应比高者优先”的作业调度算法，既照顾到了短作业的利益，也照顾到长作业的利益，是一种折中的作业调度算法。

‘捌’ 设计一个按优先数调度算法实现处理器调度的程序。 高手帮忙!!

#include <stdio.h>
#include <stdlib.h> //提供atoi()函数
#include <conio.c> //提供clrscr()函数
#define M 10 //字符串大小常量
#define N 3 //进程数常量
#define SLOT 2
typedef struct node{
char name[M];
int prio; //优先级
int round; //时间片长度
int cputime; //已经使用的cpu时间
int needtime;//需要多少cpu时间
int count; //计数器
char state; //进程的当前状态
struct node *next; //指向下一个进程
}PCB;

PCB *finish,*ready,*tail,*run;

void ShowHead(char *s1,char *s2);
int Menu_Select();
void Creat(int select);
void InsertPriority(PCB *q);
void InsertSlot(PCB *q);
void PrintOneProcess(int select,PCB *q);
void PrintAllProcess(int select);
void FirstIn();
void FIFODo(int select);
void PriorityDo(int select);
void SlotDo(int select);
void Quit();
main()
{
while(1)
{
clrscr();
switch(Menu_Select())
{
case 1:
Creat(1);
FIFODo(1);
printf("\n\n\t\t按回车键返回菜单...");
getchar();
getchar();
break;
case 2:
Creat(2);
PriorityDo(2);
printf("\n\n\t\t按回车键返回菜单...");
getchar();
getchar();
break;
case 3:
Creat(3);
SlotDo(3);
printf("\n\n\t\t按回车键返回菜单...");
getchar();
getchar();
break;
case 0:
Quit();
break;
}
}
}

/*打印每个界面的开头显示*/
void ShowHead(char *s1,char *s2)
{
printf("\t ==================%s========================\n\n",s1);
printf("\t\t\t\t%s\n\n",s2);
printf("\t ========================================================\n\n");
}

/*主菜单*/
int Menu_Select()
{
int choose;
char s[2];
clrscr();
printf("====================进程调度算法模拟程序=====================\n\n");
printf("\t\t 1.先进先出调度策略\n");
printf("\t\t 2.优先数调度策略\n");
printf("\t\t 3.时间片轮转调度策略\n");
printf("\t\t 0.退出系统\n\n");
printf("=============================================================\n\n");
do
{
printf("\n请输入你的选择(0-3):");
scanf("%s",s);
choose=atoi(s);
}while(choose<0 || choose>3);
return choose;
}

/*创建调度算法的链表*/
void Creat(int select)
{
PCB *p,*q; //q为就绪队列的最后一个结点
int i,time,rounds;
char na[M];
ready=NULL;
finish=NULL;
run=NULL;
if(select==1) //先进先出调度创建
{
printf("\nEnter name and time of process:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->state='W';
p->next=NULL;
if(ready!=NULL) //就绪队列不为空
{
q->next=p;
q=p;
}
else //就绪队列为空
{
p->next=ready;
ready=p;
q=ready;
}
}
clrscr();
ShowHead("先进先出调度策略","FIFO dispatching algorithm ");
printf("\t\t name cputime needtime state\n");
PrintAllProcess(select); //打印出初始状态的信息
}
else if(select==2) //优先数调度创建
{
printf("\nEnter name and time of process:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->state='W';
p->prio=50-time;
if(ready!=NULL) //就绪队列不为空的时候
InsertPriority(p);
else //就绪队列为空
{
p->next=ready;
ready=p;
}
}//end of for()
clrscr();
ShowHead("优先级调度策略","Priority dispatching algorithm ");
printf("\t\t name cputime needtime prio state\n");
PrintAllProcess(select); //打印出初始状态的信息
}//end of else if()
else if(select==3) //时间片轮转调度创建
{
printf("\nEnter name and the time of process:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->count=0; //计数器
p->round=SLOT;
p->state='W';
if(ready!=NULL)
InsertSlot(p);
else
{
p->next=ready;
ready=p;
}
}
clrscr();
ShowHead("时间片轮转调度策略","Time slot dispatching algorithm ");
printf("\n\t\t name cputime needtime count slot state\n");
PrintAllProcess(select); //打印出初始状态的信息
}
run=ready; //从就绪队列取一个进程，使其运行，同时就绪队列的头指针后移
run->state='R';
ready=ready->next;
}

/*优先调度：把进程插入到合适的位置，就绪队列按优先级由高到低的顺序排列*/
void InsertPriority(PCB *q)
{
PCB *pre,*p;
int flag=1;
pre=NULL;
p=ready;
while(p!=NULL && flag)
{
if(p->prio>q->prio)
{
pre=p;
p=p->next;
}
else
flag=0;
}
if(pre==NULL)
{
q->next=ready;
ready=q;
}
else
{
pre->next=q;
q->next=p;
}
}

/*时间片轮转：把结点插入到就绪队列的末尾*/
void InsertSlot(PCB *q)
{
PCB *pre,*p;
pre=NULL;
p=ready;
while(p!=NULL)
{
pre=p;
p=p->next;
}
pre->next=q;
q->next=NULL; /*由于插入到队列的末尾，所以必须要使其的下一个结点为空值*/
}

/*打印一个信息*/
void PrintOneProcess(int select,PCB *q)
{
if(select==1)
printf("\t\t %-10s%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->state);
else if(select==2)
printf("\t\t %-10s%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);
else if(select==3)
printf("\t\t %-10s%-10d%-10d%-10d%-10d%c\n",q->name,q->cputime,q->needtime,q->count,q->round,q->state);
}

/*将所有的进程打印出来，按运行，就绪，完成顺序打印*/
void PrintAllProcess(int select)
{
PCB *p;
if(run!=NULL)
PrintOneProcess(select,run);
p=ready;
while(p!=NULL)
{
PrintOneProcess(select,p);
p=p->next;
}
p=finish;
while(p!=NULL)
{
PrintOneProcess(select,p);
p=p->next;
}
}

/*把就绪队列的第一个进程调入运行*/
void FirstIn()
{
run=ready;
ready=ready->next;
run->state='R';
}

/*先进先出调度策略*/
void FIFODo(int select)
{
while(run!=NULL)
{

run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
if(run->needtime==0) //进程执行结束
{
printf("\n\t\t name cputime needtime state\n");
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
FirstIn();
PrintAllProcess(1);
}
}
}

/*优先级算法*/
void PriorityDo(int select)
{
while(run!=NULL)
{
printf("\n\t\t name cputime needtime prio state\n");
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->prio=run->prio-3;
if(run->needtime==0)
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
FirstIn();
}
else if((ready!=NULL) && (run->prio < ready->prio))
{
run->state='W';
InsertPriority(run);
FirstIn();
}
PrintAllProcess(select);
}
}

/*时间片轮转算法*/
void SlotDo(int select)
{
while(run!=NULL)
{
printf("\n\t\t name cputime needtime count slot state\n");
run->count=run->count+1;
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
if(run->needtime==0) /*运行完成时*/
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
FirstIn(); //就绪队列不为空，将就绪队列的第一个进程投入运行
}
else if(run->count==run->round) /*时间片已经到了，还未运行完成*/
{
run->count=0; //时间片
if(ready!=NULL)
{
run->state='W';
InsertSlot(run);
FirstIn();
}
}
PrintAllProcess(select); //打印本次的所有记录
}
}

void Quit()
{
char ch;
clrscr();
gotoxy(10,5);
printf("==========================================================\n\n");
printf(" Thank you for you using\n\n");
gotoxy(10,9);
printf("==========================================================\n\n");
gotoxy(13,15);

getchar();
printf("\n\t\tDo you really want to quit(y/Y or n/N):");
scanf("%c",&ch);
if(ch=='y' || ch=='Y')
{
printf("\n\t\t按任意键退出系统...");
getchar();
exit(0);
}

}

‘玖’ 先来先服务调度算法。 优先级调度算法。 短作业优先调度算法 轮转调度算法 响应比高优先调度算法

你试一下

#include<stdio.h>
//using namespace std;
#define MAX 10
struct task_struct
{
char name[10]; /*进程名称*/
int number; /*进程编号*/
float come_time; /*到达时间*/
float run_begin_time; /*开始运行时间*/
float run_time; /*运行时间*/
float run_end_time; /*运行结束时间*/
int priority; /*优先级*/
int order; /*运行次序*/
int run_flag; /*调度标志*/
}tasks[MAX];
int counter; /*实际进程个数*/
int fcfs(); /*先来先服务*/
int ps(); /*优先级调度*/
int sjf(); /*短作业优先*/
int hrrn(); /*响应比高优先*/
int pinput(); /*进程参数输入*/
int poutput(); /*调度结果输出*/

void main()
{ int option;
pinput();
printf("请选择调度算法（0~4）:\n");
printf("1.先来先服务\n");
printf("2.优先级调度\n");
printf(" 3.短作业优先\n");
printf(" 4.响应比高优先\n");
printf(" 0.退出\n");
scanf("%d",&option);
switch (option)
{case 0:
printf("运行结束。\n");
break;
case 1:
printf("对进程按先来先服务调度。\n\n");
fcfs();
poutput();
break;
case 2:
printf("对进程按优先级调度。\n\n");
ps();
poutput();
break;
case 3:
printf("对进程按短作业优先调度。\n\n");
sjf();
poutput();
break;
case 4:
printf("对进程按响应比高优先调度。\n\n");
hrrn();
poutput();
break;
}
}
int fcfs() /*先来先服务*/
{
float time_temp=0;
inti;
intnumber_schel;
time_temp=tasks[0].come_time;
for(i=0;i<counter;i++)
{
tasks[i].run_begin_time=time_temp;
tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time;
tasks[i].run_flag=1;
time_temp=tasks[i].run_end_time;
number_schel=i;
tasks[number_schel].order=i+1;
}
return 0;
}

int ps() /*优先级调度*/
{
float temp_time=0;
inti=0,j;
intnumber_schel,temp_counter;
intmax_priority;
max_priority=tasks[i].priority;
j=1;
while((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].priority>tasks[i].priority)
{
max_priority=tasks[j].priority;
i=j;
}
j++;
} /*查找第一个被调度的进程*/
/*对第一个被调度的进程求相应的参数*/
number_schel=i;
tasks[number_schel].run_begin_time=tasks[number_schel].come_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
tasks[number_schel].order=1;
temp_counter=1;
while (temp_counter<counter)
{
max_priority=0;
for(j=0;j<counter;j++)
{if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if (tasks[j].priority>max_priority)
{
max_priority=tasks[j].priority;
number_schel=j;
}
} /*查找下一个被调度的进程*/
/*对找到的下一个被调度的进程求相应的参数*/
tasks[number_schel].run_begin_time=temp_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
temp_counter++;
tasks[number_schel].order=temp_counter;

}return 0;
}

int sjf() /*短作业优先*/
{
float temp_time=0;
inti=0,j;
intnumber_schel,temp_counter;
float run_time;
run_time=tasks[i].run_time;
j=1;
while((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].run_time<tasks[i].run_time)
{
run_time=tasks[j].run_time;
i=j;
}
j++;
} /*查找第一个被调度的进程*/
/*对第一个被调度的进程求相应的参数*/
number_schel=i;
tasks[number_schel].run_begin_time=tasks[number_schel].come_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
tasks[number_schel].order=1;
temp_counter=1;
while (temp_counter<counter)
{
for(j=0;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{run_time=tasks[j].run_time;number_schel=j;break;}
}

for(j=0;j<counter;j++)
{if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if(tasks[j].run_time<run_time)
{run_time=tasks[j].run_time;
number_schel=j;
}
}
/*查找下一个被调度的进程*/
/*对找到的下一个被调度的进程求相应的参数*/
tasks[number_schel].run_begin_time=temp_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
temp_counter++;
tasks[number_schel].order=temp_counter;
}return 0;
}

int hrrn() /*响应比高优先*/
{ int j,number_schel,temp_counter;
float temp_time,respond_rate,max_respond_rate;
/*第一个进程被调度*/
tasks[0].run_begin_time=tasks[0].come_time;
tasks[0].run_end_time=tasks[0].run_begin_time+tasks[0].run_time;
temp_time=tasks[0].run_end_time;
tasks[0].run_flag=1;
tasks[0].order=1;
temp_counter=1;
/*调度其他进程*/
while(temp_counter<counter)
{
max_respond_rate=0;
for(j=1;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{respond_rate=(temp_time-tasks[j].come_time)/tasks[j].run_time;
if (respond_rate>max_respond_rate)
{
max_respond_rate=respond_rate;
number_schel=j;
}
}
} /*找响应比高的进程*/
tasks[number_schel].run_begin_time=temp_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
temp_time=tasks[number_schel].run_end_time;
tasks[number_schel].run_flag=1;
temp_counter+=1;
tasks[number_schel].order=temp_counter;
}
return 0;
}
int pinput() /*进程参数输入*/
{ int i;
printf("please input the processcounter:\n");
scanf("%d",&counter);

for(i=0;i<counter;i++)
{printf("******************************************\n");
printf("please input the process of %d th :\n",i+1);
printf("please input the name:\n");
scanf("%s",tasks[i].name);
printf("please input the number:\n");
scanf("%d",&tasks[i].number);
printf("please input the come_time:\n");
scanf("%f",&tasks[i].come_time);
printf("please input the run_time:\n");
scanf("%f",&tasks[i].run_time);
printf("please input the priority:\n");
scanf("%d",&tasks[i].priority);
tasks[i].run_begin_time=0;
tasks[i].run_end_time=0;
tasks[i].order=0;
tasks[i].run_flag=0;
}
return 0;
}
int poutput() /*调度结果输出*/
{
int i;
float turn_round_time=0,f1,w=0;
printf("name number come_time run_timerun_begin_time run_end_time priority order turn_round_time\n");
for(i=0;i<counter;i++)
{
f1=tasks[i].run_end_time-tasks[i].come_time;
turn_round_time+=f1;
w+=(f1/tasks[i].run_time);
printf(" %s, %d, %5.3f, %5.3f, %5.3f, %5.3f, %d, %d,%5.3f\n",tasks[i].name,tasks[i].number,tasks[i].come_time,tasks[i].run_time,tasks[i].run_begin_time,tasks[i].run_end_time,tasks[i].priority,tasks[i].order,f1);
}
printf("average_turn_round_timer=%5.2f\n",turn_round_time/counter);
printf("weight_average_turn_round_timer=%5.2f\n",w/counter);
return 0;
}

‘拾’ 什么是最早截止时间优先调度算法

最早截止时间优先（Earliest Dealine First， EDF）是实时系统中常用的一种调度算法，系统中有多个任务时，由调度算法决定哪个任务当前占用处理器，那么EDF算法就是按照任务的截止时间（deadline）来确定任务的执行顺序，最早截止的任务先执行。
设现在所有的进程都是就绪状态,调度器会计算EDF,按进程的完成时间排序,也就是执行时间短的排在前面,调度器会按EDF的排序依次执行； 当有新的进程时,调度器会重新计算EDF,按进程的完成时间重新排序,如果新的进程排序比当前执行的进程排序高,那么会先执行新的进程