簡述多級反饋隊列調度演算法

⑴ 多級隊列調度演算法和多級反饋隊列的調度演算法 優缺點

#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個時間段，完成