简述多级反馈队列调度算法

⑴ 多级队列调度算法和多级反馈队列的调度算法 优缺点

#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
int time[3];
struct program { /* 定义进程控制块PCB */
char name[10];
char state;
int queue;//进程队列
int priority; // 数字越小优先级越高
int needtime;//需运行时间
int runtime; //已经运行时间
struct program *link;
}*ready=NULL;
typedef struct program PROGRAM;
PROGRAM *run=NULL,*head1=NULL,*head2=NULL,*head3=NULL,*end1=NULL,*end2=NULL,*end3=NULL;
/*PROCESS *high_priority(PROCESS *P) //选择优先级最高的进程
{
PROCESS *q,*p; //问题，入口形参中
q=p;

while(p->next!=NULL)
{
if(q->priority>p->priority)
q=p;
p=p->next;
}
return q;
}*/

void sort(PROGRAM *p)
{switch(p->queue)
{case 1:
{if(head1==NULL) {head1=p;end1=p;}
else
{end1->link=p;end1=p;p->link=NULL;}
p->state='w';
break;
}
case 2:
{if(head2==NULL)
{head2=p;end2=p;p->state='w';}
else
{end2->link=p;end2=p;p->link=NULL;}
p->state='w';
break;
}
case 3:
{if(head3==NULL)
{head3=p;end3=p;}
else
{end3->link=p;end3=p;p->link=NULL;}
p->state='w';
break;
}
}
}
void input() /* 建立进程控制块函数*/
{ PROGRAM *p;
int i,num;
/*clrscr(); 清屏*/
system("cls");
printf("\n 多级反馈队列调度算法 \n");
printf("\n 请输入进程个数:\n");
scanf("%d",&num);

//printf("\n qname \t state \t queue \t needtime \t runtime \n");
printf("\n 输入第一个进程名:");
ready=getpch(PROGRAM);
scanf("%s",ready->name);
printf("\n 输入第一个进程优先级:");
scanf("%d",&ready->priority);
printf("\n 输入第一个进程运行时间:");

scanf("%d",&ready->needtime);
printf("\n");
ready->runtime=0;ready->state='r';
ready->queue=1;
ready->link=NULL;

for(i=0;i<num-1;i++)
{ printf("\n 进程号No.%d:\n",i+2);
p=getpch(PROGRAM);
printf("\n 输入进程名:");
scanf("%s",p->name);
printf("\n 输入进程优先级:");
scanf("%d",&ready->priority);
p->queue=1;
//printf("\n 输入进程队伍数1~3:");
//scanf("%d",&p->queue);
printf("\n 输入进程运行时间:");
scanf("%d",&p->needtime);
printf("\n");
p->runtime=0;p->state='w';
p->link=NULL;
sort(p);
}
}
void disp(PROGRAM * pr) /*建立进程显示函数,用于显示当前进程*/
{
printf("\n qname\t priority\t state\t queue\t needtime\t runtime \n");
printf("|%s\t",pr->name);
printf("|%c\t",pr->priority);
printf("|%c\t",pr->state);
printf("|%d\t",pr->queue);
printf("|%d\t",pr->needtime);
printf("|%d\t",pr->runtime);
printf("\n");
}
void check()//进程查看函数
{PROGRAM *pr;
printf("\n****当前正在运行的进程%s",run->name);
disp(run);
printf("\n****当前正准备好的进程%s",ready->name);
if(ready!=NULL)
{disp(ready);
printf("\n****当前就绪的队列状态为:\n");}
pr=head1;
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
pr=head2;
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
pr=head3;
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
}
//三个队伍的进程的执行函数
void runpro()
{
run=ready;
if(head1!=NULL)
{ready=head1;head1=head1->link;ready->state='r';}
else
{
if(head2!=NULL)
{ready=head2;head2=head2->link;ready->state='r';}
else
{if(head3!=NULL)
{ready=head3;head3=head3->link;ready->state='r';}
else
ready=NULL;}
}
if(run!=NULL)
{check();//显示运行及等待队列的状况
run->runtime=run->runtime+time[run->queue-1];
if(run->runtime>run->needtime)
run->runtime=run->needtime;
if(run->queue<3)
run->queue+=1;
//disp(run);
if(run->runtime<run->needtime)
sort(run);
}
}
void main() /*主函数*/
{
int h=0;
char ch;
input();
time[0]=1;
time[1]=2;
time[2]=3;

while(ready!=NULL)
{
ch=getchar();
h++;//标志执行的步骤
printf("\n The execute number:%d \n",h);

runpro();
if(run->runtime==run->needtime)
{printf("\n进程%s已经完成\n",run->name);/*run=NULL;*/}
printf("\n 按任一键继续......");
ch=getchar();
}
printf("整个进程运行完毕");
}

⑵ 试说明多级反馈队列调度算法的基本思想，为什么它是目前公认较好的一种进程调度算法

3．试说明多级反馈队列调度算法的基本思想，为什么它是目前公认的较好的一种进程调度算法（与FCFS，SJF，优先级调度相比）。
答： FCFS、SJF和优先级调度算法仅对某一类作业有利，相比之下，它能全面满足不同类型作业的需求，较好实现公平性与资源利用率之间的平衡。对交互型作业，由于通常较短，这些作业在第一队列规定的时间片内完成，可使用户感到满意；对短批作业，开始时在第一队列中执行一个时间片就可完成，便可与交互型作业一样获得快速晌应，否则通常也仅需在第二、第三队列中各执行一个时间片即可完成，其周转时间仍较短；对长批作业，它们依次在第一至第n个队列中轮番执行，不必担心长时间得不到处理。

来自：中科院计算所（软件所）2001年硕士入学操作系统试题参考答案
http://www.xuece.com/html/caozuoxitong/200904/14-41.html

⑶ 多级反馈队列调度算法的优点

调度开销低。

相反多级反馈队列调度算法允许进程在队列之间迁移。这种想法是根据不同 CPU 执行的特点来区分进程。如果进程使用过多的 CPU 时间，那么会被移到更低的优先级队列。这种方案将 I/O 密集型和交互进程放在更高优先级队列上，此外在较低优先级队列中等待过长的进程会被移到更高优先级队列。这种形式的老化可阻止饥饿的发生。

(3)简述多级反馈队列调度算法扩展阅读：

注意事项：

调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如Q1，Q2，Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理只有Q1,Q2都为空时才会去调度Q3。

对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了时间片为N的时间后，若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。

⑷ 为什么说多级反馈队列调度算法能较好的满足各方面用户需要

多级反馈队列调度算法是一种性能较好的作业低级调度策略，能够满足各类用户的需要。对于分时交互型短作业，系统通常可在第一队列（高优先级队列）规定的时间片内让其完成工作，使终端型用户都感到满意；对短的批处理作业，通常，只需在第一或第一、第二队列（中优先级队列）中各执行一个时间片就能完成工作，周转时间仍然很短；对长的批处理作业，它将依次在第一、第二、……，各个队列中获得时间片并运行，决不会出现得不到处理的情况。此系统模拟了多级反馈队列调度算法及其实现

⑸ 作业调度算法的多级反馈队列列算法

多级反馈队列算法(Round Robin with Multiple Feedback)是轮转算法和优先级算法的综合和发展。 设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。
新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。 为提高系统吞吐量和缩短平均周转时间而照顾短进程。
为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。
不必估计进程的执行时间，动态调节 I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。
计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。
I/O次数不多，而主要是CPU处理的进程。在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。
为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。

⑹ 多级反馈队列调度算法

1.'quantum length' defines the length of time slice for queue2.(You'd better read the 'README-mlfq' before you try your best to finish this assignment of OS. In fact, the file has illustrated nearly anything.)
2.It's necessary to handle the starvation, which refers to the condition that excessive interactive jobs consume all the CPU time and long-running jobs will never receive CPU time. So 'boost' is introced, which means all the jobs are moved to the topmost queue after some specific periods.
Reference:http://pages.cs.wisc.e/~remzi/OSTEP/cpu-sched-mlfq.pdf
The PDF file showed above would be a good tutorial for you to understand MLFQ(multi-level feedback queue) better.

⑺ 怎么用C语言实现多级反馈队列调度算法

调度算法的实施过程如下所述：（1）应设置多个就绪队列，并为各个队列赋予不同的优先级。（2）当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS的原则排队等待调度。当轮到该进程执行时，如他能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列……，如此下去，当一个长作业进程从第一队列依次降到第N队列后，在第N队列中便采取时间片轮转的方式运行

⑻ 请教多级反馈队列调度算法计算题

² I/O型进程 ：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。

² 计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。

² I/O次数不多，而主要是CPU处理的进程。在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。

² 为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。

⑼ 多级反馈队列调度算法的介绍

多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。（对比一下FCFS与高优先响应比调度算法的缺陷）。

⑽ 请教多级反馈队列调度算法

0时刻A到达，进入I队列，执行2个时间段后，转向队列II，再执行了3个时间段后，B进程到达（A还剩下2个时间段）.
5时刻B进入I队列，执行了2个时间段后（B还剩下2个时间段），进入II队列，此时进程C到达，此时队列 I 中有进程C，队列II中有两个进程A,B（A为队首）。
7时刻C进入I队列，执行2个时间段后，进入队列II，此时II队列中有进程A,B,C（A为队首）
9时刻，取出II队列中的A执行，执行了1个时间段后，A在队列II中的时间片完成，于是进入队列III。（队列II中还剩下B,C进程，其中B为队首）
10时刻，取出B，执行2个时间段后，B进程完成，D进程到达，D进程进入队列I。
12时刻，D进程到达，进入队列I。
此时三个队列中还有的进程为
队列I，D（还剩9个时间段）
队列II，C（还剩9个时间段）
队列III，A（还剩1个时间段）
14时刻，D执行完一个时间段，进入队列II。此时三个队列的情况：
队列II（C（还剩9个时间段），D（还剩7个时间段））(c为队首）
队列III A（还剩一个时间段）
18时刻，C执行了4个时间段，进入队列III。
队列II D（还剩7个时间段）
队列III A（还剩一个时间段） C（还剩5个时间段）
21时刻，D执行了3个时间段，进入队列III。
队列III中的两个进程 A（还剩1个时间段） C（还剩5个时间段）
D （还剩3个时间段）（A为队首）
22时刻，A执行了1个时间段，完成。
27时刻，C执行了5个时间段，完成。
30时刻，D执行了3个时间段，完成