動態優先權調度演算法

1. unix系統v的進程調度是採用怎樣的調度演算法完成的

答案為D。 多級反饋隊列輪轉法 調度演算法（作業調度、進程調度） 1、先來先服務調度演算法（FCFS） 按進入後備（或就緒）隊列的先後選擇目標作業（或進程）。 有利於長作業（進程），不利於短作業（進程）。 2、最短作業優先調度演算法SJ（P）F 從後備（或就緒）隊列中選擇估計運行時間最短的作業（或進程） tn+1=a tn+(1-a) tn tn為實際值， tn為預測值 SJF有效地降低作業的平均等待時間，提高了系統的吞吐量。 對長作業（或進程）不利，可能死等，且未考慮作業的緊迫程度。 3、時間片輪轉調度演算法（進程調度） 系統將所有的就緒進程按先來先服務原則，排成一個隊列，每次調度時把CPU分配給隊首進程，令其執行一個時間片。 就緒隊列中所有進程，在一個給定的時間內，均能獲得一個時間片的處理機執行時間。T=nq 4、優先權調度演算法 適用於作業調度和進程調度。 非搶占式、搶占式優先權調度演算法 優先權類型：靜態優先權、動態優先權 5、高響應比優先調度演算法（作業調度） 響應比RP= 響應時間/要求服務時間=（等待時間+要求服務時間）/要求服務時間 = 1+等待時間/要求服務時間 同時到達的作業（等待時間相同），要求服務時間越短（短作業），響應比越高，有利於短作業。 要求服務時間相同的作業，等待時間越長，響應比越高，相當於先來先服務。 長作業在等待足夠長時間後，響應比上升，也可被調度，避免長作業的死等。 每次調度需計算響應比，增加系統的開銷。 6、多級隊列調度 根據作業的性質或類型的不同，將就緒進程隊列分成若干個子隊列，各個作業固定分屬於一個隊列。每個隊列採用各自的調度演算法。 7、多級反饋隊列調度演算法 UNIX系統中的進程調度演算法。 處理方法： 設置多個就緒隊列，每個隊列賦予不同的優先權(S1>S2……>Sn )，且各隊列中進程執行的時間片的大小各不相同(q，2q……nq)。 新進程進入內存，首先放在S1的末尾，按FCFS排隊調度，執行q時間片，若未完成，該進程轉入S2，依次類推。 僅當Si空閑，才會調度Si+1中進程。 能較好地滿足各種類型用戶的需要。

2. 哪種調度演算法會導致飢餓

一、處理機調度相關基本概念
1、調度方式和調度演算法的若干准則
1)面向用戶的准則：周轉時間短（CPU執行用時Ts、周轉時間T=Ts+Tw、帶權周轉時間W= T/Ts）、響應時間快、均衡性、截止時間的保證、優先權准則
2)面向系統的准則：系統吞吐量高、處理機利用率好、各類資源的平衡利用
3)批處理系統為照顧為數眾多的短作業，應採用短作業優先的調度演算法；分時系統為保證系統具有合理的響應時間，應採用輪轉法進行調度
二、常用調度演算法
1、先來先服務調度演算法FCFS
（1）按照作業提交，或進程變為就緒狀態的先後次序分派CPU；
（2）新作業只有當當前作業或進程執行完或阻塞才獲得CPU運行
（3）被喚醒的作業或進程不立即恢復執行，通常等到當前作業或進程出讓CPU。（所以，默認即是非搶占方式）
（4）有利於CPU繁忙型的作業，而不利於I/O繁忙的作業（進程）。

2、短作業（進程）優先調度演算法SJF（非搶占）/SPF（搶占）
（1）平均周轉時間、平均帶權周轉時間都有明顯改善。SJF/SPF調度演算法能有效的降低作業的平均等待時間，提高系統吞吐量。
（2）未考慮作業的緊迫程度，因而不能保證緊迫性作業（進程）的及時處理、對長作業的不利、作業（進程）的長短含主觀因素，不一定能真正做到短作業優先。

3、高優先權優先調度演算法HPF
（1）兩種方式：非搶占式優先權演算法、搶占式優先權演算法（關鍵點：新作業產生時）
（2）類型:靜態優先權：創建進程時確定，整個運行期間保持不變。動態優先權：創建進程時賦予的優先權可隨進程的推進或隨其等待時間的增加而改變。
（3）高響應比優先調度演算法HRRN
HRRN為每個作業引入動態優先權，使作業的優先順序隨著等待時間的增加而以速率a提高：優先權 =（等待時間+要求服務時間)/要求服務時間= 響應時間 / 要求服務時間。
什麼時候計算各進程的響應比優先權？（作業完成時、新作業產生時（搶占、非搶占）、時間片完成時、進程阻塞時）

3. 動態優先順序調度演算法

給你兩個例子，第一個：http://dev.csdn.net/article/53/53415.shtm

第二個：

#include "stdio.h"
#include <STDLIB.H>
#include <CONIO.H>
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
struct pcb { /* 定義進程式控制制塊PCB */
char name[10];
char state;
int super;
int ntime;
int rtime;
struct pcb* link;
}*ready=NULL,*p;
typedef struct pcb PCB;
sort() /* 建立對進程進行優先順序排列函數*/
{
PCB *first, *second;
int insert=0;
if((ready==NULL)||((p->super)>(ready->super))) /*優先順序最大者,插入隊首*/
{
p->link=ready;
ready=p;
}
else /* 進程比較優先順序,插入適當的位置中*/
{
first=ready;
second=first->link;
while(second!=NULL)
{
if((p->super)>(second->super)) /*若插入進程比當前進程優先數大,*/
{ /*插入到當前進程前面*/
p->link=second;
first->link=p;
second=NULL;
insert=1;
}
else /* 插入進程優先數最低,則插入到隊尾*/
{
first=first->link;
second=second->link;
}
}
if(insert==0) first->link=p;
}
}

input() /* 建立進程式控制制塊函數*/
{
int i,num;
//clrscr(); /*清屏*/
printf("\n 請輸入進程號?");
scanf("%d",&num);
for(i=0;i<NUM;I++) scanf(?%s?,p- 輸入進程名:?); printf(?\n p="getpch(PCB);" 進程號No.%d:\n?,i); {>name);
printf("\n 輸入進程優先數:");
scanf("%d",&p->super);
printf("\n 輸入進程運行時間:");
scanf("%d",&p->ntime);
printf("\n");
p->rtime=0;p->state='w';
p->link=NULL;
sort(); /* 調用sort函數*/
}
}
int space()
{
int l=0; PCB* pr=ready;
while(pr!=NULL)
{
l++;
pr=pr->link;
}
return(l);
}

disp(PCB * pr) /*建立進程顯示函數,用於顯示當前進程*/
{
printf("\n qname \t state \t super \t ndtime \t runtime \n");
printf("|%s\t",pr->name);
printf("|%c\t",pr->state);
printf("|%d\t",pr->super);
printf("|%d\t",pr->ntime);
printf("|%d\t",pr->rtime);
printf("\n");
}

check() /* 建立進程查看函數 */
{
PCB* pr;
printf("\n **** 當前正在運行的進程是:%s",p->name); /*顯示當前運行進程*/
disp(p);
pr=ready;
printf("\n ****當前就緒隊列狀態為:\n"); /*顯示就緒隊列狀態*/
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
}

destroy() /*建立進程撤消函數(進程運行結束,撤消進程)*/
{
printf("\n 進程 [%s] 已完成.\n",p->name);
free(p);
}
running() /* 建立進程就緒函數(進程運行時間到,置就緒狀態*/
{
(p->rtime)++;
if(p->rtime==p->ntime)
destroy(); /* 調用destroy函數*/
else
{
(p->super)--;
p->state='w';
sort(); /*調用sort函數*/
}
}

main() /*主函數*/
{
int len, h=0;
char ch;
input();
len=space();
while((len!=0)&&(ready!=NULL))
{
ch=getchar();
h++;
printf("\n The execute number:%d \n",h);
p=ready;
ready=p->link;
p->link=NULL;
p->state='R';
check();
running();
printf("\n 按任一鍵繼續......");
ch=getchar();
}
printf("\n\n 進程已經完成.\n");
ch=getchar();
}

4. 響應比計算公式是什麼

響應比=作業周轉時間/作業執行時間。

按照作業／進程進入系統的先後次序進行調度，先進入系統者先調度；即啟動等待時間最長的作業／進程。是一種最簡單的調度演算法，即可用於作業調度，也可用於進程調度。先來先服務（先進先出）優缺點。

比較有利於長作業（進程），而不利於短作業（進程）。有利於CPU繁忙型作業（進程） ，而不利於I/O繁忙型作業（進程）。用於批處理系統，不適於分時系統。

響應比計算公式介紹：

短作業優先調度演算法＋動態優先權機制。既考慮作業的執行時間也考慮作業的等待時間，綜合了先來先服務和最短作業優先兩種演算法的特點。

原理是高響應比優先調度演算法既考慮作業的執行時間也考慮作業的等待時間，綜合了先來先服務和最短作業優先兩種演算法的特點。

該演算法中的響應比是指作業等待時間與運行比值，響應比公式定義是響應比＝（等待時間＋要求服務時間）／要求服務時間，即RR=（w+s）／s=1+w/s，因此響應比一定是大於1的。

5. 常見的調度演算法總結

一、FCFS——先來先服務和短作業（進程）優先調度演算法

1. 先來先服務調度演算法。

先來先服務（FCFS）調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度， 也可用於進程調度。FCFS演算法比較有利於長作業（進程），而不利於短作業（進程）。由此可知，本演算法適合於CPU繁忙型作業， 而不利於I/O繁忙型的作業（進程）。

2. 短作業（進程）優先調度演算法。

短作業（進程）優先調度演算法（SJ/PF）是指對短作業或短進程優先調度的演算法，該演算法既可用於作業調度， 也可用於進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。

二、FPF高優先權優先調度演算法

1. 優先權調度演算法的類型。

為了照顧緊迫性作業，使之進入系統後便獲得優先處理，引入了最高優先權優先（FPF）調度演算法。 此演算法常被用在批處理系統中，作為作業調度演算法，也作為多種操作系統中的進程調度，還可以用於實時系統中。當其用於作業調度， 將後備隊列中若干個優先權最高的作業裝入內存。當其用於進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時， 又可以進一步把該演算法分成以下兩種：

1)非搶占式優先權演算法

2)搶占式優先權調度演算法（高性能計算機操作系統）

2. 優先權類型 。

對於最高優先權優先調度演算法，其核心在於：它是使用靜態優先權還是動態優先權， 以及如何確定進程的優先權。

3.動態優先權

高響應比優先調度演算法為了彌補短作業優先演算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。 該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間

三、基於時間片的輪轉調度演算法

1.時間片輪轉法。

時間片輪轉法一般用於進程調度，每次調度，把CPU分配隊首進程，並令其執行一個時間片。 當執行的時間片用完時，由一個記時器發出一個時鍾中斷請求，該進程被停止，並被送往就緒隊列末尾；依次循環。

2. 多級反饋隊列調度演算法

多級反饋隊列調度演算法多級反饋隊列調度演算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度演算法。 其實施過程如下：

1) 設置多個就緒隊列，並為各個隊列賦予不同的優先順序。在優先權越高的隊列中， 為每個進程所規定的執行時間片就越小。

2) 當一個新進程進入內存後，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。 如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度…… 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最後隊列）後，便按第n隊列時間片輪轉運行。

3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；

僅當第1到第（ i-1 ）隊列空時， 才會調度第i隊列中的進程運行，並執行相應的時間片輪轉。

4) 如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列， 則此新隊列搶占正在運行的處理機，並把正在運行的進程放在第i隊列的隊尾。

6. 優先順序調度演算法如何用JAVA實現

在多線程時,可以手動去設置每個線程的優先順序setPriority(int newPriority)
更改線程的優先順序。

7. 進程調度方案設計 實現一個基本動態優先順序的調度演算法

前兩天做操作系統作業的時候學習了一下幾種進程調度演算法，在思考和討論後，有了一些自己的想法，現在就寫出來，跟大家討論下。，或者說只有有限的CPU資源，當系統中有多個進程處於就緒狀態，要競爭CPU資源時，操作系統就要負責完成如何分配資源的任務。在操作系統中，由調度程序來完成這一選擇分配的工作，調度程序所使用的演算法即是調度演算法。調度演算法需要考慮的指標主要有盡量保證CPU資源分配的公平性；按照一定策略強制執行演算法調度；平衡整個計算機系統，盡量保持各個部分都處於忙碌狀態。而根據系統各自不同的特點和要求，調度演算法又有一些側重點和目標不同，因此，演算法按照系統差異主要分為三大類：批處理系統中的調度演算法，代表調度演算法有：先來先服務、最短作業優先、最短剩餘時間優先。互動式系統中的調度演算法，代表調度演算法有：輪轉調度、優先順序調度、多級隊列、最短進程優先、保證調度、彩票調度、公平分享調度。實時系統中的調度演算法，代表調度演算法有：速率單調調度、最早最終時限優先調度。下面就上述提到的調度演算法中挑出幾個進行重點分析：保證調度保證調度是指利用演算法向用戶做出明確的性能保證，然後盡力按照此保證實現CPU的資源分配。利用這種演算法，就是定一個進程佔用CPU的時間的標准，然後按照這個標准去比較實際佔用CPU的時間，調度進程每次使離此標准最遠的進程得到資源，不斷滿足離所保證的標准最遠的進程，從而平衡資源分配滿足這個標準的要求。保證調度演算法的優點是：能很好的保證進程公平的CPU份額，當系統的特點是：進程的優先順序沒有太大懸殊，所制定的保證標准差異不大，各個進程對CPU的要求較為接近時，比如說系統要求n個進程中的每個進程都只佔用1/n的CPU資源，利用保證調度可以很容易的實現穩定的CPU分配要求。但缺點是，這種情況太過理想，當系統的各個進程對CPU要求的緊急程度不同，所制定的保證較為復雜的時候，這個演算法實現起來比較困難。彩票調度彩票調度這種演算法的大意是指向進程提供各種系統資源如CPU資源的彩票，當系統需要做出調度決策時，隨機抽出一張彩票，由此彩票的擁有者獲得資源。在彩票調度系統中，如果有一個新的進程出現並得到一些彩票，那麼在下一次的抽獎中，該進程會有同它持有彩票數量成正比例的機會贏得獎勵。進程持有的彩票數量越多，則被抽中的可能性就越大。調度程序可以通過控制進程的彩票持有數量來進行調度。彩票調度有很多優點：首先，它很靈活，系統增加分給某個進程的彩票數量，就會大大增加它佔用資源的可能性，可以說，彩票調度的反應是迅速的，而快速響應需求正是互動式系統的一個重要要求。其次，彩票調度演算法中，進程可以交換彩票，這個特點可以更好的保證系統的平衡性，使其各個部分都盡可能的處於忙碌狀態。而且利用彩票調度還可以解決許多別的演算法很難解決的問題，例如可以根據特定的需要大致成比例的劃分CPU的使用。速率單調調度速率單調調度演算法是一種可適用於可搶占的周期性進程的經典靜態實時調度演算法。當實時系統中的進程滿足：每個周期性進程必須在其周期內完成，且進程之間沒有相互依賴的關系，每個進程在一次突發中需要相同的CPU時間量，非周期的進程都沒有最終時限四個條件時，並且為了建模方便，我們假設進程搶占即刻發生沒有系統開銷，可以考慮利用速率單調演算法。速率單調調度演算法是將進程的速率（按照進程周期所算出的每秒響應的次數）賦為優先順序，則保證了優先順序與進程速率成線性關系，這即是我們所說的速率單調。調度程序每次運行優先順序最高的，只要優先順序較高的程序需要運行，則立即搶占優先順序低的進程，而優先順序較低的進程必須等所有優先順序高於它的進程結束後才能運行。速率單調調度演算法可以保證系統中最關鍵的任務總是得到調度，但是缺點是其作為一種靜態演算法，靈活性不夠好，當進程數變多，系統調度變得復雜時，可能不能較好的保證進程在周期內運行。最早最終時限優先調度最早最終時限優先調度演算法是一個動態演算法，不要求進程是周期性的，只要一個進程需要CPU時間，它就宣布它的到來時間和最終時限。調度程序維持一個可運行的進程列表，按最終時限排序，每次調度一個最終時限最早的進程得到CPU 。當新進程就緒時，系統檢查其最終時限是否在當前運行的進程結束之前，如果是，則搶占當前進程。由於是動態演算法，最早最終優先調度的優點就是靈活，當進程數不超過負載時，資源分配更優，但也同樣由於它的動態屬性，進程的優先順序都是在不斷變化中的，所以也沒有哪個進程是一定可以保證滿足調度的，當進程數超過負載時，資源分配合理度會急速下降，所以不太穩定。

8. 採用動態優先權的調度演算法，若所有的進程都具有相同優先權初值，則此時的調度演算法其實和哪種演算法一樣

FCFS，先來先服務。

9. 優先權調度演算法可分為_______和______兩種方式。

優先權調度演算法可分為
非搶占式優先權演算法和搶占式優先權調度演算法兩種方式。
1.非搶占式優先權演算法
在這種方式下,系統一旦把處理機分配給就緒隊列中優先權最高的進程後,該進程便一直執行下去,直至完成;
或因發生某事件使該進程放棄處理機時,系統方可再將處理機重新分配給另一優先權最高的進程.這種調度演算法主要用於批處理系統中;也可用於某些對實時性要求不嚴的實時系統中.
2.搶占式優先權調度演算法
系統同樣把處理機分配給優先權最高的進程,使之執行.但在其執行期間,只要又出現了另一個其優先權更高的進程,進程調度程序就立即停止當前進程(原優先權最高的進程)的執行,重新將處理機分配給新到的優先權最高的進程.
這種搶占式的優先權調度演算法,能更好地滿足緊迫作業的要求,常用於要求比較嚴格的實時系統中,
以及對性能要求較高的批處理和分時系統中.
參考：http://louzi8888.blog.163.com/blog/static/22283442010315112010946/