Question

进程调度算法

Answer 1

调度算法是指：根据系统的资源分配策略所规定的资源分配算法。
一、先来先服务和短作业（进程）优先调度算法

1. 先来先服务调度算法。先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度， 也可用于进程调度。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。由此可知，本算法适合于CPU繁忙型作业， 而不利于I/O繁忙型的作业（进程）。
2. 短作业（进程）优先调度算法。短作业（进程）优先调度算法（SJ/PF）是指对短作业或短进程优先调度的算法，该算法既可用于作业调度， 也可用于进程调度。但其对长作业不利；不能保证紧迫性作业（进程）被及时处理；作业的长短只是被估算出来的。

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

1. 优先权调度算法的类型。为了照顾紧迫性作业，使之进入系统后便获得优先处理，引入了最高优先权优先（FPF）调度算法。 此算法常被用在批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度，还可以用于实时系统中。当其用于作业调度， 将后备队列中若干个优先权最高的作业装入内存。当其用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，此时， 又可以进一步把该算法分成以下两种：
1)非抢占式优先权算法
2)抢占式优先权调度算法（高性能计算机操作系统）
2. 优先权类型 。对于最高优先权优先调度算法，其核心在于：它是使用静态优先权还是动态优先权， 以及如何确定进程的优先权。
3. 高响应比优先调度算法
为了弥补短作业优先算法的不足，我们引入动态优先权，使作业的优先等级随着等待时间的增加而以速率a提高。 该优先权变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间；即 =（响应时间）/要求服务时间

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

1. 时间片轮转法。时间片轮转法一般用于进程调度，每次调度，把CPU分配队首进程，并令其执行一个时间片。 当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环。 2. 多级反馈队列调度算法 多级反馈队列调度算法多级反馈队列调度算法，不必事先知道各种进程所需要执行的时间，它是目前被公认的一种较好的进程调度算法。 其实施过程如下：
1) 设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权越高的队列中， 为每个进程所规定的执行时间片就越小。
2) 当一个新进程进入内存后，首先放入第一队列的末尾，按FCFS原则排队等候调度。 如果他能在一个时间片中完成，便可撤离；如果未完成，就转入第二队列的末尾，在同样等待调度…… 如此下去，当一个长作业（进程）从第一队列依次将到第n队列（最后队列）后，便按第n队列时间片轮转运行。
3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1到第（i-1）队列空时， 才会调度第i队列中的进程运行，并执行相应的时间片轮转。
4) 如果处理机正在处理第i队列中某进程，又有新进程进入优先权较高的队列， 则此新队列抢占正在运行的处理机，并把正在运行的进程放在第i队列的队尾。

Answer 2

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

typedef struct PCB /*进程信息*/
{
char processname;
int arrivetime;
int servicetime;
int finishtime;
int priority;
int state;
struct PCB *next;
}PCB, *PCB_pointer;

PCB_pointer initial(int e) //初始化进程链表
{
int i;
PCB_pointer p,q,l;

q = (PCB_pointer)malloc(sizeof(PCB)); //链表头结点
q->next=NULL;

l=q;
printf("请输入各进程信息：进程名 到达时间 服务时间 优先级\n");
for(i=0;i<e;i++)
{
printf("\n第%d个进程信息：",i+1);
p = (PCB_pointer)malloc(sizeof(PCB));
scanf("%s%d%d%d",&(p->processname),&(p->arrivetime),&(p->servicetime),&(p->priority));

p->finishtime = 0;
p->state =0; //状态0表示就绪,状态1表示运行,状态2表示完成
p->next = l->next;
l->next = p;
l=l->next;
}
return q;
}

PCB_pointer sort1(PCB_pointer p) //按优先级排序
{
PCB_pointer q1,q2;
char c;
int e;
q1 = q2 = p->next;
while(q1!=NULL)
{
while(q2!=NULL)
{
if(q1->priority < q2->priority)
{
c = q1->processname;
q1->processname = q2->processname;
q2->processname = c;

e = q1->arrivetime;
q1->arrivetime = q2->arrivetime;
q2->arrivetime = e;

e = q1->servicetime;
q1->servicetime = q2->servicetime;
q2->servicetime = e;

e = q1->priority;
q1->priority = q2->priority;
q2->priority = e;
}
q2 = q2->next;
}
q1 = q1->next;
q2 = q1;
}
return p;
}

PCB_pointer sort3(PCB_pointer p) //按短作业排序
{
PCB_pointer q1,q2;
char c;
int e;
q1 = q2 = p->next;
while(q1!=NULL)
{
while(q2!=NULL)
{
if(q1->servicetime > q2->servicetime)
{
c = q1->processname;
q1->processname = q2->processname;
q2->processname = c;

e = q1->arrivetime;
q1->arrivetime = q2->arrivetime;
q2->arrivetime = e;

e = q1->servicetime;
q1->servicetime = q2->servicetime;
q2->servicetime = e;

e = q1->priority;
q1->priority = q2->priority;
q2->priority = e;
}
q2 = q2->next;
}
q1 = q1->next;
q2 = q1;
}
return p;
}

void operate1(PCB_pointer p)
{
PCB_pointer l,h,q;
l=p->next;
int s=0,i=1;
while(l!=NULL)
{
if(l->state == 0)
{
l->state = 1;
l->finishtime=s+l->servicetime;
s=l->finishtime;
h=l->next;
if(h==NULL)
{
printf("\n%c是第%d个运行的进程",l->processname,i);
printf("\n到达时间为: %d, 完成时间为: %d",l->arrivetime,l->finishtime);
q=p->next;
printf("\n在它运行时,已完成的进程有: ");
while(q!=NULL)
{
if(q->state==2)
printf(" %c ",q->processname);
q=q->next;
}

printf("\n此时无进程处于就绪状态\n");
break;
}
else
{
printf("\n%c是第%d个运行的进程",l->processname,i);
printf("\n到达时间为: %d, 完成时间为: %d",l->arrivetime,l->finishtime);
i++;
q=p->next;
if(i==2)
printf("\n在它运行之前无进程运行");
else
{
printf("\n在它运行时,已完成的进程有: ");
while(q!=NULL)
{
if(q->state==2)
printf(" %c ",q->processname);
q=q->next;
}
}

printf("\n此时处于就绪状态进程有: ");
q=p->next;
while(q!=NULL)
{
if(q->state==0)
printf(" %c ",q->processname);
q=q->next;
}

printf("\n");
}
l->state=2;
}

l=l->next;
}

}

void operate2(PCB_pointer p,int e)
{
PCB_pointer l,q;
int i=0;
char c;

l=q=p->next;

while(l->next!=NULL) //找到链表的最后一个结点
{
l=l->next;
}
l->next=p->next; //末尾一个结点和首结点连接起来形成一个单向循环链表
l=l->next;
c=l->processname;
while(l)
{
if(l->state==0)
{
if(l->servicetime>2)
{
l->servicetime-=2;
do
{
if(q->state==0)
q->finishtime+=2;
q=q->next;
}while(q->processname!=c);
}
else if(l->servicetime!=0)
{
do
{
if(q->state==0)
q->finishtime+=l->servicetime;
q=q->next;
}while(q->processname!=c);

l->servicetime=0;
l->state=1;
i++;
printf("\n%c是第%d个完成的",l->processname,i);
printf("\n开始时间为: %d, 完成时间为: %d",l->arrivetime,l->finishtime);
if(i==1)
printf("\n在它之前无进程运行");
else
{
printf("\n当它运行时,已完成的进程有: ");
do
{
if(q->state==2)
printf(" %c ",q->processname);
q=q->next;
}while(q->processname!=c);
}
if(i==e)
printf("\n此时无进程处于阻塞状态");
else
{
printf("\n此时处于阻塞状态的进程有: ");
do
{
if(q->state==0)
printf(" %c ",q->processname);
q=q->next;
}while(q->processname!=c);
}
printf("\n");
l->state=2;
if(i==e)
break;
}
}
l=l->next;
}
}

int menu()
{
int i;
printf("\n***********************************************\n");
printf("* CHOICE MENU *\n");
printf("*---------------------------------------------*\n");
printf("* 调度方式： *\n");
printf("* *\n");
printf("* 1. 优先级 2.时间片轮转 3.短作业优先 *\n");
printf("* *\n");
printf("***********************************************\n");
printf("请选择：");
scanf("%d",&i);
switch(i)
{
case 1: printf("*****您选择了按优先级调度*****\n\n");break;
case 2: printf("*****您选择了按时间片轮转调度*****\n\n");break;
case 3: printf("*****您选择了按短作业优先调度*****\n\n");break;
default: printf("错误的选择!");
}
return i;
}

void main()
{
int i,e;
PCB_pointer p;
printf("请输入进程数：");
scanf("%d",&e);
p=initial(e);
i=menu();
switch(i)
{
case 1: p=sort1(p);operate1(p);break;
case 2: operate2(p,e);break;
case 3: p=sort3(p);operate1(p);break;
default: ;
}
}

Answer 3

网页链接里面有 进程调度算法 详细代码，可以输出结果并且绘制折线图