优先级调度算法
优先级调度算法
算法介绍
优先调度算法的类型（用于作业调度）
1）非抢占式优先权调度算法
系统一旦把处理机分配给优先权最高的进程后，便一直执行下去，至完成。
2）抢占式优先权调度算法
只要系统中出现一个新的就绪进程，就进行优先权比较 。若出现优先权更高的进程，则立即停止当前执行，并将处理机分配给新到的优先权最高的进程。优先权类型
1）静态优先权
静态优先权在创建进程时确定，且在进程的整个运行期间保持不变。
https://img-blog.csdn.net/20180424234537546?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk2Mjk1NQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/702）动态优先权
https://img-blog.csdn.net/2018042423463796?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk2Mjk1NQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70算法实现抢占式动态优先权： https://img-blog.csdn.net/20180424234727904?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk2Mjk1NQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
PS：本人认为非抢占式静态优先权没有实际价值。
[*]
#include <stdio.h>
[*]
#include <stdlib.h>
[*]
#include <string.h>
[*]
typedef struct node
[*]
{
[*]
char name[10]; /*进程标识符*/
[*]
int prio; /*进程优先数*/
[*]
int round; /*进程时间轮转时间片*/
[*]
int cputime; /*进程占用CPU时间*/
[*]
int needtime; /*进程到完成还要的时间*/
[*]
int count; /*计数器*/
[*]
char state; /*进程的状态*/
[*]
struct node *next; /*链指针*/
[*]
}PCB;
[*]
PCB *finish,*ready,*tail,*run; /*队列指针*/
[*]
int N; /*进程数*/
[*]
/*将就绪队列中的第一个进程投入运行*/
[*]
firstin()
[*]
{
[*]
run=ready; /*就绪队列头指针赋值给运行头指针*/
[*]
run->state='R'; /*进程状态变为运行态*/
[*]
ready=ready->next; /*就绪对列头指针后移到下一进程*/
[*]
}
[*]
/*标题输出函数*/
[*]
void prt1(char a)
[*]
{
[*]
if(toupper(a)=='P') /*优先数法*/
[*]
printf(" 进程号 cpu时间 所需时间 优先数 状态\n");
[*]
else
[*]
printf(" 进程号 cpu时间 所需时间 记数 时间片 状态\n");
[*]
}
[*]
/*进程PCB输出*/
[*]
void prt2(char a,PCB *q)
[*]
{
[*]
if(toupper(a)=='P') /*优先数法的输出*/
[*]
printf(" %-10s%-10d%-10d%-10d %c\n",q->name,
[*]
q->cputime,q->needtime,q->prio,q->state);
[*]
else/*轮转法的输出*/
[*]
printf(" %-10s%-10d%-10d%-10d%-10d %-c\n",q->name,
[*]
q->cputime,q->needtime,q->count,q->round,q->state);
[*]
}
[*]
/*输出函数*/
[*]
void prt(char algo)
[*]
{
[*]
PCB *p;
[*]
prt1(algo); /*输出标题*/
[*]
if(run!=NULL) /*如果运行指针不空*/
[*]
prt2(algo,run); /*输出当前正在运行的PCB*/
[*]
p=ready; /*输出就绪队列PCB*/
[*]
while(p!=NULL)
[*]
{
[*]
prt2(algo,p);
[*]
p=p->next;
[*]
}
[*]
p=finish; /*输出完成队列的PCB*/
[*]
while(p!=NULL)
[*]
{
[*]
prt2(algo,p);
[*]
p=p->next;
[*]
}
[*]
getchar(); /*压任意键继续*/
[*]
}
[*]
/*优先数的插入算法*/
[*]
insert1(PCB *q)
[*]
{
[*]
PCB *p1,*s,*r;
[*]
int b;
[*]
s=q; /*待插入的PCB指针*/
[*]
p1=ready; /*就绪队列头指针*/
[*]
r=p1; /*r做p1的前驱指针*/
[*]
b=1;
[*]
while((p1!=NULL)&&b) /*根据优先数确定插入位置*/
[*]
if(p1->prio>=s->prio)
[*]
{
[*]
r=p1;
[*]
p1=p1->next;
[*]
}
[*]
else
[*]
b=0;
[*]
if(r!=p1) /*如果条件成立说明插入在r与p1之间*/
[*]
{
[*]
r->next=s;
[*]
s->next=p1;
[*]
}
[*]
else
[*]
{
[*]
s->next=p1; /*否则插入在就绪队列的头*/
[*]
ready=s;
[*]
}
[*]
}
[*]
/*优先数创建初始PCB信息*/
[*]
void create(char alg)
[*]
{
[*]
PCB *p;
[*]
int i,time;
[*]
char na[10];
[*]
ready=NULL; /*就绪队列头指针*/
[*]
finish=NULL; /*完成队列头指针*/
[*]
run=NULL; /*运行队列指针*/
[*]
printf("输入进程号和运行时间：\n"); /*输入进程标识和所需时间创建PCB*/
[*]
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) /*就绪队列不空调用插入函数插入*/
[*]
insert1(p);
[*]
else
[*]
{
[*]
p->next=ready; /*创建就绪队列的第一个PCB*/
[*]
ready=p;
[*]
}
[*]
}
[*]
printf(" 优先数算法输出信息:\n");
[*]
printf("************************************************\n");
[*]
prt(alg); /*输出进程PCB信息*/
[*]
run=ready; /*将就绪队列的第一个进程投入运行*/
[*]
ready=ready->next;
[*]
run->state='R';
[*]
}
[*]
/*优先数调度算法*/
[*]
priority(char alg)
[*]
{
[*]
while(run!=NULL) /*当运行队列不空时，有进程正在运行*/
[*]
{
[*]
run->cputime=run->cputime+1;
[*]
run->needtime=run->needtime-1;
[*]
run->prio=run->prio-3; /*每运行一次优先数降低3个单位*/
[*]
PCB *p;
[*]
p=ready;
[*]
while(p!=NULL)
[*]
{
[*]
p->prio=p->prio+1; /*每等待一次优先数升高1个单位*/
[*]
p=p->next;
[*]
}
[*]
if(run->needtime==0) /*如所需时间为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';
[*]
insert1(run);
[*]
firstin(); /*将就绪队列的第一个进程投入运行*/
[*]
}
[*]
prt(alg); /*输出进程PCB信息*/
[*]
}
[*]
}
[*]
/*主函数*/
[*]
main()
[*]
{
[*]
char algo; /*算法标记*/
[*]
printf("输入P确定算法：优先数算法\n");
[*]
scanf("%c",&algo); /*输入字符确定算法*/
[*]
printf("输入进程数：\n");
[*]
scanf("%d",&N); /*输入进程数*/
[*]
if(algo=='P'||algo=='p')
[*]
{
[*]
create(algo); /*优先数法*/
[*]
priority(algo);
[*]
}
[*]
}
输出结果：
https://img-blog.csdn.net/20180424234901971?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk2Mjk1NQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70https://img-blog.csdn.net/20180424234916810?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk2Mjk1NQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
原文：https://blog.csdn.net/weixin_40962955/article/details/80072769
页:
[1]