在多道程式設計系統中，記憶體中有多道程式運行，他們相互爭奪處理機這一重要的資源。處理機調度就是從就緒佇列中，按照一定的算法選擇一個進程並將處理機分配給它運行，以實現進程並發地執行。
基本介紹
- 中文名：處理機調度
- 釋義：照算法選擇進程並將處理機分配
- 目的：實現進程並發地執行
- 功能：記住進程的狀態等
- 性能準則：不同的調度算法
- 因素：CPU利用率等
功能,性能準則,調度算法,先來先服務調度算法（FCFS）,短作業優先調度算法,優先權調度算法,基於時間片的輪轉調度算法,算法的實現,
功能
一般情況下，當占用處理機的進程因為某種請求得不到滿足而不得不放棄CPU進入等待狀態時，或者當時間片到，系統不得不將CPU分配給就緒佇列中另一進程的時候，都要引起處理機調度。除此之外，進程正常結束、中斷處理等也可能引起處理機的調度。因此，處理機調度是作業系統核心的重要組成部分，它的主要功能如下：
（2）根據一定的算法，決定哪個進程能獲得處理機，以及占用多長時間。
（3）收回處理機，即正在執行的進程因為時間片用完或因為某種原因不能再執行的時候，保存該進程的現場，並收回處理機。
處理機調度的功能中，很重要的一項就是根據一定算法，從就緒佇列中選出一個進程占用CPU運行。可見，算法是處理機調度的關鍵。
性能準則
處理機調度，有許多不問的調度算法，不同的調度算法具有不同的特性。因此，在介紹算法之前，先介紹衡量一個算法的基本準則。
衡量和比較調度算法性能優劣主要有一下幾個因素：
（1）CPU利用率。CPU是計算機系統中最重要的資源，所以應儘可能使CPU保持忙，使這一資源利用率最高。
（5）回響時間。指從作業提交到系統作出回響所經過的時間。在互動式系統中，作業的周轉時間並不一定是最好的衡量準則，因此，常常使用另一種度量準則，即回響時間。從用戶觀點看，回響時間應該快一點好，但這常常要犧牲系統資源利用率為代價。
調度算法
先來先服務調度算法（FCFS）
先來先服務(FCFS)調度算法是一種最簡單的調度算法，該算法既可用於作業調度，也可用於進程調度。當在作業調度中採用該算法時，每次調度都是從後備作業佇列中選擇一個或多個最先進入該佇列的作業，將它們調入記憶體，為它們分配資源、創建進程，然後放入就緒佇列。在進程調度中採用FCFS算法時，則每次調度是從就緒佇列中選擇一個最先進入該佇列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞後才放棄處理機。
短作業優先調度算法
優先權調度算法
為了照顧緊迫型作業，使之在進入系統後便獲得優先處理，引入了最高優先權優先(FPF)調度算法。此算法常被用於批處理系統中，作為作業調度算法，也作為多種作業系統中的進程調度算法，還可用於實時系統中。當把該算法用於作業調度時，系統將從後備佇列中選擇若干個優先權最高的作業裝入記憶體。當用於進程調度時，該算法是把處理機分配給就緒佇列中優先權最高的進程，這時，又可進一步把該算法分成如下兩種。
（1）非搶占式優先權算法
在這種方式下，系統一旦把處理機分配給就緒佇列中優先權最高的進程後，該進程便一直執行下去，直至完成；或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分配給另一優先權最高的進程。這種調度算法主要用於批處理系統中；也可用於某些對實時性要求不嚴的實時系統中。
（2） 搶占式優先權調度算法
在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個其優先權更高的進程，進程調度程式就立即停止當前進程(原優先權最高的進程)的執行，重新將處理機分配給新到的優先權最高的進程。因此，在採用這種調度算法時，是每當系統中出現一個新的就緒進程i 時，就將其優先權Pi與正在執行的進程j 的優先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續執行；但如果是Pi>Pj，則立即停止Pj的執行，做進程切換，使i 進程投入執行。顯然，這種搶占式的優先權調度算法能更好地滿足緊迫作業的要求，故而常用於要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。
基於時間片的輪轉調度算法
在早期的時間片輪轉法中，系統將所有的就緒進程按先來先服務的原則排成一個佇列，每次調度時，把CPU 分配給隊首進程，並令其執行一個時間片。時間片的大小從幾ms 到幾百ms。當執行的時間片用完時，由一個計時器發出時鐘中斷請求，調度程式便據此信號來停止該進程的執行，並將它送往就緒佇列的末尾；然後，再把處理機分配給就緒佇列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒佇列中的所有進程在一給定的時間內均能獲得一時間片的處理機執行時間。換言之，系統能在給定的時間內回響所有用戶的請求。
算法的實現
程式設計思路：
自定義結構體PCB表（進程名name，進程優先數priority，進程執行時間time）以及進程就緒佇列Queue_Process（data[MAXSIZE]數組存放PCB，front，rear隊首隊尾指針），通過每次對進程就緒佇列進行進程優先數從大到小排序來確定進程執行的選擇，並且是採用動態優先數調度算法（每次優先數減1，執行時間減1），每次輸出進程執行情況時只需要將隊首PCB調出執行，其他進程都處於動態就緒狀態，等進程執行結束後重新對進程就緒佇列排序。
程式中，採用結構體、佇列等數據結構，其中對佇列每次排序是採用冒泡排序算法實現。
#include<iostream>#include<string>usingnamespacestd;#defineMAXSIZE10structPCB{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);//進程運行函式}