調度演算法

1. 操作系統中的HRRF是什麼調度演算法

操作系統的常見調度演算法有哪些啊?
ABCDE五進程達間別0 1 2 3 4服務間4 3 5 2 4要求按高響應比優先調度算求平均帶權周轉間

2. 編寫代碼實現作業的三種調度演算法

#include<windows.h>
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
const int maxnum=100;
int N; /*進程數*/
double start[maxnum],endtime[maxnum],arrive[maxnum],runtime[maxnum],zhou[maxnum];
double averagezhou; // 平均周轉時間
double average_zhou; //平均帶權周轉時間
char name; //進程名
double dqzhou[maxnum]; //帶權周轉時間
typedef struct node
{
char name[10]; //進程名
int round; //進程時間輪轉時間片
int cputime; //進程佔用CPU時間
int needtime; //進程到完成還要的時間
char state; //進程的狀態
struct node *next; //鏈指針
}PCB;
PCB *finish,*ready,*tail,*run; /*隊列指針*/

void firstin() /*將就緒隊列中的第一個進程投入運行*/
{
run=ready; /*就緒隊列頭指針賦值給運行頭指針*/
run->state='R'; /*進程狀態變為運行態*/
ready=ready->next; /*就緒對列頭指針後移到下一進程*/
}
void print1(PCB *q) /*進程PCB輸出*/
{
printf("進程名 已運行時間 還需要時間 時間片 狀態\n");
printf(" %-10s%-15d%-10d%-10d %-c\n",q->name,q->cputime,q->needtime,q->round,q->state);
}
void print() /*輸出函數*/
{
PCB *p;
if(run!=NULL) /*如果運行指針不空*/
print1(run); /*輸出當前正在運行的PCB*/
p=ready; /*輸出就緒隊列PCB*/
while(p!=NULL)
{
print1(p);
p=p->next;
}
p=finish; /*輸出完成隊列的PCB*/
while(p!=NULL)
{
print1(p);
p=p->next;
}
}
void insert(PCB *p2) //輪轉法插入函數
{
tail->next=p2; //將新的PCB插入在當前就緒隊列的尾
tail=p2;
p2->next=NULL;
}
void create() /*創建進程PCB*/
{
PCB *p;
int i,time;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf("請輸入進程名稱和所需要CPU的時間:\n");
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;
if(i==1)
p->state='R';
else
p->state='W';
p->round=1; /*時間片*/
if(ready!=NULL)
insert(p);
else
{
p->next=ready;
ready=p;
tail=p;
}
}
printf("------------------------------------------------------------------\n");
print(); /*輸出進程PCB信息*/
run=ready; /*將就緒隊列的第一個進程投入運行*/
ready=ready->next;
run->state='R';
}
void RR() //時間片輪轉調度
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
if(run->needtime==0) /*運行完將其變為完成態，插入完成隊列*/
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
firstin(); /*就緒對列不空，將第一個進程投入運行*/
}
else
if(ready!=NULL) /*如就緒隊列不空*/
{
run->state='W'; /*將進程插入到就緒隊列中等待輪轉*/
insert(run);
firstin(); /*將就緒對列的第一個進程投入運行*/
}
printf("------------------------------------------------------------------\n");
print(); /*輸出進程信息*/
}
}

void FCFS(double *arrive,double *runtime,double n) //先來先服務調度演算法
{
start[0]=arrive[0]; //開始執行時間=到達時間
endtime[0]=start[0]+runtime[0]; //完成時間=開始時間+服務時間
zhou[0]=endtime[0]-arrive[0]; //周轉時間=完成時間-到達時間
dqzhou[0]=zhou[0]/runtime[0];
for(int i=0;i<n;i++)
{
if(endtime[i-1]>arrive[i]||endtime[i-1]==arrive[i])
endtime[i]=endtime[i-1]+runtime[i];
else
endtime[i]=arrive[i]+runtime[i];
zhou[i]=endtime[i]-arrive[i];
dqzhou[i]=zhou[i]/runtime[i];
averagezhou+=zhou[i];
average_zhou+=dqzhou[i];
}
averagezhou=averagezhou/n;
average_zhou=average_zhou/n;
cout<<"完成時間為:"<<endl;
for(int j=0;j<n;j++)
cout<<endtime[j]<<" "<<endl;
cout<<"周轉時間為:"<<endl;
for(int k=0;k<n;k++)
cout<<zhou[k]<<" "<<endl;
cout<<"帶權周轉時間為:"<<endl;
for(int m=0;m<n;m++)
cout<<dqzhou[m]<<" "<<endl;
cout<<"平均周轉時間為:"<<endl;
cout<<averagezhou<<" "<<endl;
cout<<"平均帶權周轉時間為:"<<endl;
cout<<average_zhou<<" "<<endl;
}

void SJF(double *arrive,double *runtime,double n) //短作業優先調度演算法
{
int end[maxnum]; //用於標記進程是否已經執行，應經執行end[i]=1,否則為0;
for(int k=0;k<n;k++)
end[k]=0;
int temp,now=0,next=1,p=1; //now表示剛執行完的進程號，next表示下一個要執行的進程號
start[0]=arrive[0]; //開始執行時間=到達時間
endtime[0]=start[0]+runtime[0]; //完成時間=開始時間+服務時間
zhou[0]=endtime[0]-arrive[0]; //周轉時間=完成時間-到達時間
dqzhou[0]=zhou[0]/runtime[0]; //帶權周轉時間=周轉時間/服務時間
averagezhou=zhou[0];
average_zhou=dqzhou[0];
end[now]=1; //執行完的進程設置為1；
for(int i=1;i<n;i++)
{
int j;
for(j=1;j<n;)
{
if(arrive[j]<endtime[now]||arrive[j]==endtime[now])
j++;
else
break;
}
temp=j;
int min=p;
for(j=1;j<=temp;j++)
{
if(runtime[min]>runtime[j] && end[j]==0)
min=j;
}
next=min;
endtime[next]=endtime[now]+runtime[next];
zhou[next]=endtime[next]-arrive[next];
dqzhou[next]=zhou[next]/runtime[next];
averagezhou+=zhou[next];
average_zhou+=dqzhou[next];
end[next]=1;
now=next;
next=p;
while(end[p]!=0)
p++;
}
averagezhou=averagezhou/n;
average_zhou=average_zhou/n;
cout<<"完成時間為:"<<endl;
for(int j=0;j<n;j++)
cout<<endtime[j]<<" "<<endl;
cout<<"周轉時間為:"<<endl;
for(k=0;k<n;k++)
cout<<zhou[k]<<" "<<endl;
cout<<"帶權周轉時間為:"<<endl;
for(int m=0;m<n;m++)
cout<<dqzhou[m]<<" "<<endl;
cout<<"平均周轉時間為:"<<endl;
cout<<averagezhou<<" "<<endl;
cout<<"平均帶權周轉時間為:"<<endl;
cout<<average_zhou<<" "<<endl;
}

int EDF() //最早截止時間的調度演算法
{
int arrive_A,arrive_B; //標記進程A,進程B的到達時間
int zhouqi_A,zhouqi_B,serve_A,serve_B; //進程的周期時間和服務時間
int i,j,a=0,b=0,ka=0,kb=0; //ka,kb為開關,i,j,a,b為進程下標
int num_a=0,num_b=0; //服務累計時間
printf("輸入進程A的周期時間,服務時間: ");
scanf("%d%d",&zhouqi_A,&serve_A);
printf("輸入進程B的周期時間,服務時間: ");
scanf("%d%d",&zhouqi_B,&serve_B);
for(int T=0;T<=100;T++)
{
if(num_a==serve_A) //進程A完成
{
num_a=serve_A+1;
printf("當T=%d時",T);
printf("進程A%d結束\n",a);
if(num_b<serve_B)
{
printf(" 調用進程B%d\n",b);
kb=1;
}
ka=0;
}
if(num_b==serve_B)
{
num_b=serve_B+1;
printf("當T=%d時",T);
printf("進程B%d結束\n",b);
if(num_a<serve_A)
{
printf(" 調用進程A%d\n",a);
ka=1;
}
kb=0;
}
if(T%zhouqi_A==0 && T%zhouqi_B==0)
{
arrive_A=arrive_B=T;
j=++a;
i=++b;
printf("當T=%d時,進程A%d和進程B%d同時產生，此時，",T,j,i);
if(zhouqi_A<=zhouqi_B)
{
printf("調用進程A%d，阻塞進程B%d\n",j,i);
ka=1;
kb=0;
}
else
{
printf("調用進程B%d，阻塞進程A%d\n",i,j);
ka=0;
kb=1;
}
num_a=num_b=0;
}
if(T%zhouqi_A==0&&T%zhouqi_B!=0)
{
arrive_A=T;
printf("當T=%d時",T);
printf("進程A%d產生 ",++a); //不可能與進程A競爭處理器
num_a=0;
if(num_b<serve_B) //進程B沒有完成
if(arrive_B+zhouqi_B>arrive_A+zhouqi_A) //若進程B最早截止時間大於進程A的,則執行進程A
{
printf("進程A%d執行。\n",a);
ka=1;
kb=0;
}
else //若進程B最早截止時間小於等於進程A的
printf("進程B%d繼續執行。\n",b);
else //進程B完成
{
printf("進程A%d執行。\n",a);
ka=1;
}
}
if(T%zhouqi_A!=0 && T%zhouqi_B==0)
{
arrive_B=T;
printf("當T=%d時",T);
printf("進程B%d產生，",++b); //不可能與進程B競爭處理器
num_b=0;
if(num_a<serve_A) //進程A沒有完成
if(arrive_B+zhouqi_B>=arrive_A+zhouqi_A) //進程A的最早截止時間不小於B
printf("進程A%d繼續執行。\n",a);
else
{
printf("進程B%d執行。\n",b);
kb=1;
ka=0;
}

else //進程A完成
{
printf("進程B%d執行。\n",b);
kb=1;
}
}
if(ka)
num_a++;
if(kb)
num_b++;
}
return 1;
}

int main()
{
system("color 0b"); //設置顏色
cout<<"最早截止時間的調度演算法如下: "<<endl<<endl;
EDF();
int n;
cout<<endl;
cout<<"請輸入進程的數目: ";
cin>>n;
cout<<"請按進程到達時間從小到大依次輸入n個進程的到達時間: "<<endl;
for(int i=0;i<n;i++)
cin>>arrive[i];
cout<<"請按上面進程的順序依次輸入n個進程的服務時間: "<<endl;
for(int j=0;j<n;j++)
cin>>runtime[j];
cout<<"先來先服務調度演算法如下: "<<endl;
FCFS(arrive,runtime,n);
cout<<endl<<endl;
cout<<"短作業優先調度演算法如下: "<<endl;
SJF(arrive,runtime,n);
cout<<endl<<endl;
printf("輪轉調度演算法如下:\n\n");
printf("輸入創建進程的數目:\n");
scanf("%d",&N);
create();
RR();
return 0；
}

3. 進程調度演算法是什麼

調度演算法是指：根據系統的資源分配策略所規定的資源分配演算法。
一、先來先服務和短作業（進程）優先調度演算法

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隊列的隊尾。

4. 什麼rm調度演算法

一個任務的響應時間(response time)是指一個任務請求, 這個任務實際完成的時間跨度. 在靜態調度中, 任務的臨界時刻(critical instant)這個概念被首先提出來. 它被定義為一個特定的時刻, 如果在這個時刻有這個任務的請求, 那麼這個任務就會需要最大的響應時間. 由此得出 定理1: 一個任務的臨界時間就是比這個任務優先順序高的所有任務同時發出請求的時刻. 定理1的價值在於它找到了一個證明一個調度演算法能否調度任一任務集充分必要條件, 那就是所有任務同時請求執行的時的情況下每個任務仍能滿足各自的期限, 那麼這個任務集就可以被這個調度演算法調度. 有了這個推論, 我們就可以證明RM調度的最優性了. 定理2: 如果一個任務集能夠被靜態調度, 那麼RMS演算法就能夠調度這個任務集. 從這個意義上說, RMS是最優的靜態調度演算法. 這個定理的證明方法就是有名的交換法. 證明思路如下: 假設一個任務集S採用其他靜態優先順序演算法可以調度,那麼總有這樣兩個優先順序相鄰的任務i和j, 有Ti>Tj,而Pi≤Pj.把Ti和Tj的優先順序Pi和Pj互換,明顯可以看出這時S仍然可以調度, 因為在所有任務同時請求的情況下, 交換這兩個任務不會影響其它任務的完成時間, 同時這兩個任務都可以在各自期限內完成. 按照這樣的方法,其他任何靜態優先順序調度最終都可以轉換成RM調度. RMS已被證明是靜態最優調度演算法, 開銷小, 靈活性好, 是實時調度的基礎性理論。即使系統瞬時過載, 也完全可預測哪些任務丟失時限。缺點是處理機利用率較低, 最壞的情況下，當n→∞時, 不超過ln2 (≈ 70%)。另外, RMS是充分但非必要條件。而在一般情況下，對於隨機的任務集大約只有88%. 70%或者88%的處理器利用率對於許多實時應用來說是一個嚴重的限制，動態調度演算法如最早截止期最先（earliest deadline first，EDF）或者最少空閑時間最先（least laxity first，LLF）已經被證明是最優的，並且能夠實現100% 的處理器利用率. 具有資源同步約束的RMS調度 當實時任務間共享資源時, 可能出現低優先順序任務不可預測地阻塞高優先順序任務執行的情況, 叫優先順序倒置。這時RMS 演算法不能保證任務集的調度, 必須使用有關協議控制優先順序的倒置時間。常用的協議有優先順序頂級協議和堆資源協議, 使用這些協議可使優先順序的倒置時間最多為一個資源臨界段的執行時間, 並且不會發生死鎖。 基於RMS 的非周期任務的調度 實時系統中的非周期任務可採用延遲伺服器演算法或隨機伺服器演算法進行調度。它們的最大特點是可在周期任務的實時調度環境下處理隨機請求。兩者的基本思想是將非周期任務轉化成周期任務, 再利用RMS演算法進行調度。前者用一個或幾個專用的周期任務執行所有非周期任務, 這種周期任務叫非周期任務伺服器。根據周期大小,伺服器有固定優先順序, 伺服器的執行時間被稱為預算, 它在每個伺服器周期Ts 的起點補充。只要伺服器有充足的預算, 就可在其周期內為非周期任務服務。該演算法實現簡單, 但可調度性分析較難, 有時會出現抖動, 可能發生一個非周期任務在相鄰兩個伺服器周期中連續執行2倍預算的現象, 與RMS理論不符, 需要適當修改RMS演算法。隨機伺服器演算法與延遲伺服器演算法相似, 但預算不是在每個周期起點補充, 而是在預算消耗Ts時間之後再補充。該演算法與RMS分析演算法一致, 但實現復雜。 EDF最早截止時間優先演算法（EDF）也稱為截止時間驅動調度演算法（DDS），是一種動態調度演算法。EDF指在調度時，任務的優先順序更具任務的截止時間動態分配。截止時間越短，優先順序越高。EDF有如下定理： 定理2：如果一個任務集按EDF演算法調度，當且僅當U<=1。 EDF的特點(1) 任務模型: 與RMS 調度相同。 (2) 優先順序分配方法: 動態分配, 距要求時限所剩時間越短優先順序越高。 理論上，EDF和LLF演算法都是單處理器下的最優調度演算法。但是由於EDF和LLF在每個調度時刻都要計算任務的deadline或者空閑時間，並根據計算結果改變任務優先順序，因此開銷大、不易實現，其應用受到一定限制。多處理器實時調度

5. 什麼是調度演算法

調度演算法

通常將作業或進程歸入各種就緒或阻塞隊列。有的演算法適用於作業調度，有的演算法適用於進程調度，有的兩者都適應。

1．先來先服務(FCFS, First Come First Serve)

先來先服務（FCFS, First Come First Serve）是最簡單的調度演算法，按先後順序進行調度。

1. FCFS演算法

按照作業提交或進程變為就緒狀態的先後次序，分派CPU；

當前作業或進程佔用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）。

在作業或進程喚醒後（如I/O完成），並不立即恢復執行，通常等到當前作業或進程出讓CPU。最簡單的演算法。

2. FCFS的特點

比較有利於長作業，而不利於短作業。

有利於CPU繁忙的作業，而不利於I/O繁忙的作業。

2. 輪轉法(Round Robin)

輪轉法(Round Robin)是讓每個進程在就緒隊列中的等待時間與享受服務的時間成正比例。

1. 輪轉法

Ø 將系統中所有的就緒進程按照FCFS原則，排成一個隊列。

Ø 每次調度時將CPU分派給隊首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。

Ø 在一個時間片結束時，發生時鍾中斷。

Ø 調度程序據此暫停當前進程的執行，將其送到就緒隊列的末尾，並通過上下文切換執行當前的隊首進程。

Ø 進程可以未使用完一個時間片，就出讓CPU（如阻塞）。

Ø

2. 時間片長度的確定

Ø 時間片長度變化的影響

² 過長－>退化為FCFS演算法，進程在一個時間片內都執行完，響應時間長。

² 過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數增加，響應時間長。

Ø 對響應時間的要求：T(響應時間)=N(進程數目)*q(時間片)

Ø 就緒進程的數目：數目越多，時間片越小

Ø 系統的處理能力：應當使用戶輸入通常在一個時間片內能處理完，否則使響應時間，平均周轉時間和平均帶權周轉時間延長。

3. 多級反饋隊列演算法(Round Robin with Multiple Feedback)

多級反饋隊列演算法時間片輪轉演算法和優先順序演算法的綜合和發展。

優點：

² 為提高系統吞吐量和縮短平均周轉時間而照顧短進程。

² 為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程。

² 不必估計進程的執行時間，動態調節。

1. 多級反饋隊列演算法

² 設置多個就緒隊列，分別賦予不同的優先順序，如逐級降低，隊列1的優先順序最高。每個隊列執行時間片的長度也不同，規定優先順序越低則時間片越長，如逐級加倍。

² 新進程進入內存後，先投入隊列1的末尾，按FCFS演算法調度；若按隊列1一個時間片未能執行完，則降低投入到隊列2的末尾，同樣按FCFS演算法調度；如此下去，降低到最後的隊列，則按「時間片輪轉」演算法調度直到完成。

² 僅當較高優先順序的隊列為空，才調度較低優先順序的隊列中的進程執行。如果進程執行時有新進程進入較高優先順序的隊列，則搶先執行新進程，並把被搶先的進程投入原隊列的末尾。

²

2. 幾點說明

² I/O型進程：讓其進入最高優先順序隊列，以及時響應I/O交互。通常執行一個小時間片，要求可處理完一次I/O請求的數據，然後轉入到阻塞隊列。

² 計算型進程：每次都執行完時間片，進入更低級隊列。最終採用最大時間片來執行，減少調度次數。

² I/O次數不多，而主要是CPU處理的進程。在I/O完成後，放回優先I/O請求時離開的隊列，以免每次都回到最高優先順序隊列後再逐次下降。

² 為適應一個進程在不同時間段的運行特點，I/O完成時，提高優先順序；時間片用完時，降低優先順序。

6. 調度演算法的調度演算法

在操作系統中調度是指一種資源分配，因而調度演算法是指：根據系統的資源分配策略所規定的資源分配演算法。對於不同的的系統和系統目標，通常採用不同的調度演算法，例如，在批處理系統中，為了照顧為數眾多的段作業，應採用短作業優先的調度演算法；又如在分時系統中，為了保證系統具有合理的響應時間，應當採用輪轉法進行調度。目前存在的多種調度演算法中，有的演算法適用於作業調度，有的演算法適用於進程調度；但也有些調度演算法既可以用於作業調度，也可以用於進程調度。
通常將作業或進程歸入各種就緒或阻塞隊列。
調度演算法要求：高資源利用率、高吞吐量、用戶滿意等原則。
進程調度所採用的演算法是與整個系統的設計目標相一致的：
1.批處理系統：增加系統吞吐量和提高系統資源的利用率;
2.分時系統：保證每個分時用戶能容忍的響應時間。
3.實時系統：保證對隨機發生的外部事件做出實時響應。

7. 幾種進程調度演算法分析

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

8. 虛擬存儲器採用的頁面調度演算法是「先進先出」（FIFO）演算法嗎

虛擬存儲器採用的頁面調度演算法是「先進先出」（FIFO）演算法嗎。常見的替換演算法有4種。

①隨機演算法：用軟體或硬體隨機數產生器確定替換的頁面。

②先進先出：先調入主存的頁面先替換。

③近期最少使用演算法（LRU，Least Recently Used）：替換最長時間不用的頁面。

④最優演算法：替換最長時間以後才使用的頁面。這是理想化的演算法，只能作為衡量其他各種演算法優劣的標准。

虛擬存儲器的效率是系統性能評價的重要內容，它與主存容量、頁面大小、命中率，程序局部性和替換演算法等因素有關。

(8)調度演算法擴展閱讀

虛擬存儲器地址變換基本上有3種形虛擬存儲器工作過程式：全聯想變換、直接變換和組聯想變換。任何邏輯空間頁面能夠變換到物理空間任何頁面位置的方式稱為全聯想變換。每個邏輯空間頁面只能變換到物理空間一個特定頁面的方式稱為直接變換。

組聯想變換是指各組之間是直接變換，而組內各頁間則是全聯想變換。替換規則用來確定替換主存中哪一部分，以便騰空部分主存，存放來自輔存要調入的那部分內容。

在段式虛擬存儲系統中，虛擬地址由段號和段內地址組成，虛擬地址到實存地址的變換通過段表來實現。每個程序設置一個段表，段表的每一個表項對應一個段，每個表項至少包括三個欄位：有效位(指明該段是否已經調入主存)、段起址(該段在實存中的首地址)和段長(記錄該段的實際長度)。

9. 關於《操作系統》中的磁碟調度演算法

（1）先來先服務調度演算法
由於該演算法就是按照磁軌請求序列的先後次序依次訪問磁軌的，因此磁軌的訪問序列（服務順序）就是：
110、180、32、115、15、120、60、70。
當前磁頭在50號磁軌。故磁頭移動道數為：
（110-50）+（180-110）+（180-32）+（115-32）+（115-15）+（120-15）+（120-60）+（70-60）=60+70+148+83+100+105+60+10=636
（2）單向掃描調度演算法
該演算法是沿磁頭移動方向訪問距離當前磁軌最近的磁軌，當到達一個頂端時立刻返回到另一個頂端繼續掃描。本題磁頭移動方向是磁軌增加的方向，當前磁頭在50號磁軌。因此磁軌的訪問序列（服務順序）就是：60、70、110、115、120、180、15、32。而磁頭移動道數與前面（1）問差不多，也是兩兩相減，然後求和。在此略