反饋

處理機調度

在多道程序設計系統中，內存中有多道程序運行，他們相互爭奪處理機這一重要的資源。處理機調度就是從就緒隊列中，按照一定的算法選擇一個進程並將處理機分配給它運行，以實現進程併發地執行。

中文名: 處理機調度
釋義: 照算法選擇進程並將處理機分配
目的: 實現進程併發地執行

功能: 記住進程的狀態等
性能準則: 不同的調度算法
因素: CPU利用率等

處理機調度功能

一般情況下，當佔用處理機的進程因為某種請求得不到滿足而不得不放棄CPU進入等待狀態時，或者當時間片到，系統不得不將CPU分配給就緒隊列中另一進程的時候，都要引起處理機調度。除此之外，進程正常結束、中斷處理等也可能引起處理機的調度。因此，處理機調度是操作系統核心的重要組成部分，它的主要功能如下：

（1）記住進程的狀態，如進程名稱、指令計數器、程序狀態寄存器以及所有通用寄存器等現場信息，將這些信息記錄在相應的進程控制塊中。

（2）根據一定的算法，決定哪個進程能獲得處理機，以及佔用多長時間。

（3）收回處理機，即正在執行的進程因為時間片用完或因為某種原因不能再執行的時候，保存該進程的現場，並收回處理機。

處理機調度的功能中，很重要的一項就是根據一定算法，從就緒隊列中選出一個進程佔用CPU運行。可見，算法是處理機調度的關鍵。

處理機調度性能準則

處理機調度，有許多不問的調度算法，不同的調度算法具有不同的特性。因此，在介紹算法之前，先介紹衡量一個算法的基本準則。

衡量和比較調度算法性能優劣主要有一下幾個因素：

（1）CPU利用率。CPU是計算機系統中最重要的資源，所以應儘可能使CPU保持忙，使這一資源利用率最高。

（2）吞吐量。CPU運行時表示系統正處於工作狀態，工作量的大小是以每單位時間所完成的作業數目來描述的，這就叫吞吐量。

（3）週轉時間。指從作業提交到作業完成所經過的時間，包括作業等待，在就緒隊列中排隊，在處理機上運行以及進行輸入/輸出操作所花時間的總和。

（4）等待時間。處理機調度算法實際上並不影響作業執行或輸入/輸出操作的時間，隻影響作業在就緒隊列中等待所花的時間。因此，衡量一個調度算法優劣常常簡單的考察等待時間。

（5）響應時間。指從作業提交到系統作出響應所經過的時間。在交互式系統中，作業的週轉時間並不一定是最好的衡量準則，因此，常常使用另一種度量準則，即響應時間。從用户觀點看，響應時間應該快一點好，但這常常要犧牲系統資源利用率為代價。

處理機調度調度算法

處理機調度先來先服務調度算法（FCFS）

先來先服務(FCFS)調度算法是一種最簡單的調度算法，該算法既可用於作業調度，也可用於進程調度。當在作業調度中採用該算法時，每次調度都是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然後放入就緒隊列。在進程調度中採用FCFS算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞後才放棄處理機。

處理機調度短作業優先調度算法

短作業(進程)優先調度算法SJ(P)F，是指對短作業或短進程優先調度的算法。它們可以分別用於作業調度和進程調度。短作業優先(SJF)的調度算法是從後備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先(SPF)調度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執行並一直執行到完成，或發生某事件而被阻塞放棄處理機時再重新調度。

處理機調度優先權調度算法

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

（1）非搶佔式優先權算法

在這種方式下，系統一旦把處理機分配給就緒隊列中優先權最高的進程後，該進程便一直執行下去，直至完成；或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分配給另一優先權最高的進程。這種調度算法主要用於批處理系統中；也可用於某些對實時性要求不嚴的實時系統中。

（2）搶佔式優先權調度算法

在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個其優先權更高的進程，進程調度程序就立即停止當前進程(原優先權最高的進程)的執行，重新將處理機分配給新到的優先權最高的進程。因此，在採用這種調度算法時，是每當系統中出現一個新的就緒進程i 時，就將其優先權Pi與正在執行的進程j 的優先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續執行；但如果是Pi>Pj，則立即停止Pj的執行，做進程切換，使i 進程投入執行。顯然，這種搶佔式的優先權調度算法能更好地滿足緊迫作業的要求，故而常用於要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。

處理機調度基於時間片的輪轉調度算法

在早期的時間片輪轉法中，系統將所有的就緒進程按先來先服務的原則排成一個隊列，每次調度時，把CPU 分配給隊首進程，並令其執行一個時間片。時間片的大小從幾ms 到幾百ms。當執行的時間片用完時，由一個計時器發出時鐘中斷請求，調度程序便據此信號來停止該進程的執行，並將它送往就緒隊列的末尾；然後，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒隊列中的所有進程在一給定的時間內均能獲得一時間片的處理機執行時間。換言之，系統能在給定的時間內響應所有用户的請求。^[1]

處理機調度算法的實現

^[2] 程序設計思路：

自定義結構體PCB表（進程名name，進程優先數priority，進程執行時間time）以及進程就緒隊列Queue_Process（data[MAXSIZE]數組存放PCB，front，rear隊首隊尾指針），通過每次對進程就緒隊列進行進程優先數從大到小排序來確定進程執行的選擇，並且是採用動態優先數調度算法（每次優先數減1，執行時間減1），每次輸出進程執行情況時只需要將隊首PCB調出執行，其他進程都處於動態就緒狀態，等進程執行結束後重新對進程就緒隊列排序。

^[2] 程序中，採用結構體、隊列等數據結構，其中對隊列每次排序是採用冒泡排序算法實現。

#include<iostream>
#include<string>

usingnamespacestd;

#defineMAXSIZE10

structPCB
{
intname;//進程名
intpriority;//進程優先數
inttime;//進程執行時間
};

structQueue_Process
{
PCBdata[MAXSIZE];//PCB隊列
intfront;//隊首
intrear;//隊尾
};

voidInitQueue(Queue_Process*Q)
{
Q->front=Q->rear=0;
}

boolIsQueueEmpty(Queue_ProcessQ)//隊空判斷函數
{
return(Q.front==Q.rear)?true:false;
}

boolIsQueueFull(Queue_ProcessQ)//隊滿判斷函數
{
return(Q.front==(Q.rear+1)%MAXSIZE)?true:false;
}

voidEnQueue(Queue_Process*Q,PCBx)//入隊函數
{
if(IsQueueFull(*Q))//判斷隊列是否為滿
{
cout<<"隊滿，入隊操作失敗！"<<endl;
exit(0);
}
//隊列非滿，將PCB入隊，將其中信息填入
Q->data[Q->rear].name=x.name;
Q->data[Q->rear].priority=x.priority;
Q->data[Q->rear].time=x.time;
Q->rear=(Q->rear+1)%MAXSIZE;//隊列隊尾指針後移
}

voidDeleQueue(Queue_Process*Q)
{
if(IsQueueEmpty(*Q))//判斷隊列是否為空
{
cout<<"隊空，出隊操作失敗！"<<endl;
exit(0);
}
Q->front=(Q->front+1)%MAXSIZE;//將隊列首指針後移
}

voidSortPCB(PCB*pcb,intn)//PCB優先數大小從大到小排列函數
{
PCBtemp;
boolexchange=true;//交換標誌
for(inti=n-1;i>0&&exchange;i--)//冒泡排序算法排序
{
exchange=false;
for(intj=0;j<i;j++)
{
if(pcb[j].priority<pcb[j+1].priority)//交換PCB中的數據
{

temp.name=pcb[j].name;
temp.priority=pcb[j].priority;
temp.time=pcb[j].time;
pcb[j].name=pcb[j+1].name;
pcb[j].priority=pcb[j+1].priority;
pcb[j].time=pcb[j+1].time;
pcb[j+1].name=
temp.name;
pcb[j+1].priority=temp.priority;
pcb[j+1].time=temp.time;
exchange=true;
}
}
}
}

voidInput(PCB*pcb,intn)//進程信息輸入函數
{
cout<<"請輸入每個進程的優先數和執行時間："<<endl;
intp,t;
for(inti=0;i<n;i++)//輸入每個進程的優先數和執行時間
{
cin>>p>>t;
pcb[i].name=i;
pcb[i].priority=p;
pcb[i].time=t;
}
}

voidDisplay(Queue_Process*queue)//輸出每個時刻的進程運行情況函數
{
cout<<"進程名\t"<<"優先數\t"<<"執行時間\t"<<"進程狀態"<<endl;
do
{
if(queue->data[queue->front].time>1)
{
cout<<""<<queue->data[queue->front].name<<"\t"<<""<<queue->data[queue->front].priority<<"\t\t"<<""<<queue->data[queue->front].time<<"\t\t"<<"執行中..."<<endl;
queue->data[queue->front].priority-=1;
queue->data[queue->front].time-=1;
for(inti=1;i<queue->rear-queue->front;i++)
cout<<""<<queue->data[queue->front+i].name<<"\t"<<""<<queue->data[queue->front+i].priority<<"\t\t"<<""<<queue->data[queue->front+i].time<<"\t\t"<<"等待中..."<<endl;
cout<<endl<<endl;
}
else
{
cout<<""<<queue->data[queue->front].name<<"\t"<<""<<queue->data[queue->front].priority<<"\t\t"<<""<<queue->data[queue->front].time<<"\t\t"<<"執行中..."<<endl;
for(inti=1;i<queue->rear-queue->front;i++)
cout<<""<<queue->data[queue->front+i].name<<"\t"<<""<<queue->data[queue->front+i].priority<<"\t\t"<<""<<queue->data[queue->front+i].time<<"\t\t"<<"等待中..."<<endl;
cout<<"進程"<<queue->data[queue->front].name<<"執行完畢！"<<endl<<endl<<endl;
DeleQueue(queue);
}
SortPCB(queue->data,queue->rear-queue->front);//對隊列中的優先數進程重新排序
}while(!IsQueueEmpty(*queue));
}

voidmain()
{
PCBprocess[MAXSIZE-1];//進程數組
Queue_Processqueue;//進程隊列
intnum;//要輸入的進程數
cout<<"請輸入進程同步數num："<<endl;
cin>>num;

InitQueue(&queue);//初始化隊列
Input(process,num);
for(inti=0;i<num;i++)//通過循環使每個進程入隊
{
EnQueue(&queue,process[i]);
}
SortPCB(queue.data,queue.rear-queue.front);//對進程按優先數從大到小排列

cout<<endl<<"\t\t進程執行情況："<<endl;
Display(&queue);//進程運行函數
}

參考資料

1. 湯小丹梁紅兵哲鳳屏湯子瀛．《計算機操作系統》（第三版）：西安電子科技大學出版社，2007
2. 處理機調度算法的實現．百度文庫[引用日期2013-12-25]

處理機調度的概述圖（1張）

詞條統計

瀏覽次數：次
編輯次數：14次歷史版本
最近更新：玄冬有玖（2022-11-11）

1 功能
2 性能準則
3 調度算法: 3.1 先來先服務調度算法（FCFS）; 3.2 短作業優先調度算法; 3.3 優先權調度算法; 3.4 基於時間片的輪轉調度算法
4 算法的實現