一、先來先服務調度算法

（1）算法內容：先來先服務調度算法是一種最簡單的調度算法，可以應用于高級調度也可以運用于低級調度。高級調度時，FCFS調度算法按照作業(yè)進入后備作業(yè)隊列的先后順序選擇作業(yè)進入內存，即先進入后備作業(yè)隊列的作業(yè)被優(yōu)先選擇進入內存，然后為選中的作業(yè)創(chuàng)建進程并分配該作業(yè)所需資源。低級調度時，FCFS調度算法每次從內存的進程/線程就緒隊列中選擇一個最先進入的進程/線程，然后由進程/線程調度程序將CPU分配給它并使其運行。

（2）算法要求：每個進程由一個進程控制快（PCB）表示。進程控制塊可以包含如下信息：進程名，到達時間，運行時間，開始時間，完成時間，等待時間，周轉時間，代權周轉時間等。先進入就緒隊列的進程，先分配處理機運行。一旦一個進程占有了處理機，它就一直運行下去，直到該進程完成工作或者因為等待某事件發(fā)生而不能繼續(xù)運行時才釋放處理機。

（3）設計思想：該算法按照進程到達時間先后順序執(zhí)行，先到達的先執(zhí)行。

（4）算法分析：先定義一個PCB結構體；

定義input()輸入函數，輸入進程號、到達時間、運行時間；

定義output()輸出函數，輸出每個進程塊的各種時間；

定義rank()排序函數，將進程按照到達時間進行排序；

定義FCFS()先來先服務算法函數，計算各種時間；

定義main()主函數，實現先來先服務功能；

（5）核心代碼：

#include<stdio.h>
    double atime;            //平均周轉時間 
	double awtime;    //平均帶權周轉時間
struct PCB     //聲明結構體類型PCB 
{
	char name[20];          //進程號 
	int arrivaltime;       //到達時間 
	int runtime;           //運行時間 
	int starttime;         //開始時間 
	int finishtime;        //完成時間 
	int waitingtime;       //等待時間 
	int cycletime;        //周轉時間 
	double wctime;        //帶權周轉時間 
};
struct PCB pcb[100];
/*輸入函數*/ 
int input(int n)   
{
	printf("請依次輸入進程號、到達時間、運行時間：\n");
	for(int i=0;i<n;i++)
	{
		scanf("%s\t%d\t%d",pcb[i].name,&pcb[i].arrivaltime,&pcb[i].runtime);
	}
 } 
 /*輸出函數*/ 
int output(int n)  
{
	printf("\n======================================================================================================================\n");
	printf("進程號 \t到達時間\t運行時間\t開始時間\t完成時間\t等待時間\t周轉時間\t帶權周轉時間\n");
	printf("----------------------------------------------------------------------------------------------------------------------\n");
	for(int i=0;i<n;i++)
	{
	printf("%3s\t  %d\t\t   %d\t\t   %d\t\t   %d\t\t   %d\t\t   %d\t\t   %.2lf\n",pcb[i].name,pcb[i].arrivaltime,pcb[i].runtime,pcb[i].starttime,pcb[i].finishtime,pcb[i].waitingtime,pcb[i].cycletime,pcb[i].wctime);
	}
	printf("----------------------------------------------------------------------------------------------------------------------\n");
	printf("\t平均周轉時間    \t\t%.2lf\t\n",atime);
	printf("----------------------------------------------------------------------------------------------------------------------\n");
	printf("\t平均帶權周轉時間\t\t%.2lf\t\n",awtime);
	printf("======================================================================================================================\n"); 
}
/*按到達時間進行排序*/ 
int rank(int n)
{
	struct PCB t;
	for(int j=0;j<n-1;j++)  //冒泡法排序
	for(int i=0;i<n-1-j;i++)
    {
    	if(pcb[i].arrivaltime>pcb[i+1].arrivaltime)
		{
			t=pcb[i];
			pcb[i]=pcb[i+1];
			pcb[i+1]=t;
		} 
	}
}
/*先來先服務算法*/
int FCFS(int n)
{
/*完成時間*/
	if(pcb[0].arrivaltime!=0) //第一個進程到達時間不為0時，其完成時間=開始時間+運行時間
	{
		pcb[0].finishtime=pcb[0].starttime+pcb[0].runtime;
	}
	else
		pcb[0].finishtime=pcb[0].runtime; //第一個進程到達時間為0時，其完成時間=運行時間
		for(int i=1;i<n;i++)
		{
			if(pcb[i-1].finishtime>=pcb[i].arrivaltime) //如果前一個進程的完成時間大于等于當前進程的到達時間
			{
				pcb[i].finishtime=pcb[i-1].finishtime+pcb[i].runtime; //當前進程的完成時間=前一個進程的完成時間+該進程的運行時間
			 } 
			else
			{
				pcb[i].finishtime=pcb[i].arrivaltime+pcb[i].runtime; //否則為當前進程的到達時間+運行時間
			}
		 }
 /*開始時間*/ 
	pcb[0].starttime=pcb[0].arrivaltime; //第一個進程的開始時間即到達時間
	for(int i=1;i<n;i++)
	{
		pcb[i].starttime=pcb[i-1].finishtime; //從第二個進程開始，開始時間=前一個進程的完成時間
	}
/*等待時間 周轉時間 帶權周轉時間*/
 	for(int i=0;i<n;i++) 
 	{
 		pcb[i].waitingtime=pcb[i].starttime-pcb[i].arrivaltime; //等待時間=開始時間-到達時間
pcb[i].cycletime=pcb[i].finishtime-pcb[i].arrivaltime; //周轉時間=完成時間-到達時間
pcb[i].wctime=pcb[i].cycletime/(pcb[i].runtime*1.0); //帶權周轉時間=周轉時間/運行時間
	 }
/*平均周轉時間 平均帶權周轉時間*/
int sum1=0;
double sum2=0;
for(int i=0;i<n;i++)
		{
			sum1+=pcb[i].cycletime;    //求所有進程周轉時間的和
sum2+=pcb[i].wctime;      //求有所進程周轉時間的和
		}
		atime=sum1/(n*1.0);   //平均周轉時間=所有進程周轉時間的和/進程數
awtime=sum2/n;       //平均帶權周轉時間=所有進程周轉時間的和/進程數 
	}
	/*主函數*/ 
int main()
{
	printf("先來先服務FCFS算法模擬\n請輸入進程個數：\n");
    int n;
    scanf("%d",&n);  //輸入進程數 n
input(n);       //輸入函數
rank(n);        //排序函數，按到達時間給各進程排序 （升序）
    FCFS(n);         //先來先服務算法函數，計算各種時間
    output(n);       //輸出函數
    return 0;
}

（6）測試數據或截圖：

?（6）運行結果分析：根據先來先服務算法，首先按到達時間大小將其排序，根據進程的輸入信息，第一個進程a到達時間為0，其完成時間=運行時間=1，其余進程的完成時間=前一個進程的完成時間+該進程的運行時間，（如，b的完成時間=1+100=101，c的完成時間=101+1=102，d的完成時間=102+100=201）；第一個進程a的開始時間=到達時間=0，其余進程的開始時間=前一個進程的完成時間，（如，b的開始時間=a的完成時間=1，c的開始時間=b的完成時間=101，d的開始時間=c的完成時間=102）；每個進程的等待時間=開始時間-到達時間（如，a的等待時間=0-0=0，b的等待時間=1-1=0，c的等待時間=101-2=99，d的等待時間=102-3=99）；周轉時間=完成時間-到達時間（如，a的周轉時間=1-0=1，b的周轉時間=101-1=100，c的周轉時間=102-2=100，d的周轉時間=202-3=199）；帶權周轉時間=周轉時間/運行時間（如，a的帶權周轉時間=1/1=1，b的帶權周轉時間=100/100=1，c的帶權周轉時間=100/1=100，d的帶權周轉時間=199/100=1.99）；平均周轉時間=所有進程周轉時間的和/進程數(1+100+100+199)/4=100；平均帶權周轉時間=所有進程帶權周轉時間的和/進程數（1+1+100+1.99）/4=26。

二、時間片輪轉調度算法

（1）算法內容：時間片輪轉調度算法主要用于低級調度，調度方式實際上是一種基于時鐘的搶占式調度算法。在采用時間片輪轉調度算法的系統(tǒng)中，進程/線程就緒隊列按到達時間的先后次序進行排隊，按照先來先服務原則，將需要執(zhí)行的所有進程按照到達時間大小排成一個升序的序列，每次都給一個進程同樣大小的時間片，在這個時間片內如果進程執(zhí)行結束了，那么把進程從進程隊列中刪去，如果進程沒有結束，那么把該進程停止然后改成等待狀態(tài)，放到進程隊列的尾部，直到所有的進程都已執(zhí)行完畢。

（2）算法要求：每個進程由一個進程控制塊（PCB）表示。進程控制塊可以包含如下信息：進程名，到達時間，運行時間，完成時間，周轉時間，帶權周轉時間，完成進程標志，剩余服務時間等。進程的運行時間以時間片為單位進行計算。

（3）設計思想：每次調度時，總是選擇就緒隊列的隊首進程，讓其在CPU上運行一個系統(tǒng)預先設置好的時間片。一個時間片內沒有完成運行的進程，返回到緒隊列末尾重新排隊，等待下一次調度。時間片輪轉調度屬于搶占式調度，適用于分時系統(tǒng)。

（4）算法分析：先定義一個RR結構體；

input()輸入函數；

rank()函數對進程到達時間排序；

rr_pcb()函數執(zhí)行輪轉調度算法；

output()輸出函數；

main()主函數。

（5）核心代碼：

#include<stdio.h>
   double atime;            //平均周轉時間 
   double awtime;    //平均帶權周轉時間
 struct RR
 {
 	char name[20];         //進程號 
 	int arrivaltime;       //到達時間 
	int runtime;           //運行時間
	int starttime;         //開始時間 
	int finishtime;        //完成時間
	int cycletime;      //周轉時間 
	double wctime;      //帶權周轉時間
	int sign;          //完成進程標志 
	int st1;    //剩余服務時間 
  };
  struct RR rr[100];
  /*輸入函數*/ 
int input(int n)
{
	printf("請依次輸入進程號、到達時間、運行時間：\n");
	for(int i=0;i<n;i++)
	{
		rr[i].sign=0; 
		scanf("%s\t%d\t%d",rr[i].name,&rr[i].arrivaltime,&rr[i].runtime);
		rr[i].st1=rr[i].runtime;
	} 
}
/*采用冒泡法，按進程的到達時間對進程進行排序*/
int rank(int n)
{
	int i,j;
	struct RR temp; 
	for(j=0;j<n-1;j++)
	for(i=0;i<n-1-j;i++)
	{
		if(rr[i].arrivaltime>rr[i+1].arrivaltime)
		{
			temp=rr[i];
			rr[i]=rr[i+1];
			rr[i+1]=temp;
		}
	}
}
/*執(zhí)行時間片輪轉調度算法*/ 
int rr_pcb(int n)  
{
	printf("請輸入時間片：\n");
	int t;
	scanf("%d",&t);  //輸入時間片
	int time=rr[0].arrivaltime;     //給當前時間time賦初值
	int flag=1;          //標志就緒隊列中有進程
	int sum=0;          //記錄完成的進程數
	printf("\n====================================================================================================================\n");
	printf("進程號 \t到達時間\t運行時間\t開始時間\t完成時間\t周轉時間\t帶權周轉時間\n");
	printf("--------------------------------------------------------------------------------------------------------------------\n");
	while(sum<n) //當完成的進程數小于進程總數
	{
	flag=0;    //標記就緒隊列沒有進程
	for(int i=0;i<n;i++) //時間片輪轉法執(zhí)行各進程 
	{
		if(rr[i].sign==1)//已完成進程 
		continue;
		else//未完成的進程
		{
			if(rr[i].st1<=t && time>=rr[i].arrivaltime)//還需運行的時間小于等于一個時間片 
			{
	 	      flag=1;  //把進程加入到就緒隊列中
	       	  time+=rr[i].st1;
	 	      rr[i].sign=1; //此進程完成
	          rr[i].finishtime=time;  //完成時間 
              rr[i].cycletime=rr[i].finishtime-rr[i].arrivaltime;  //計算周轉時間=完成時間-到達時間 
			  rr[i].wctime=rr[i].cycletime/(rr[i].runtime*1.0);   //計算帶權周轉時間=周轉時間/服務 
			  printf("%3s\t  %d\t\t   %d\t\t   %d\t\t   %d\t\t   %d\t\t   %.2lf\n",rr[i].name,
	rr[i].arrivaltime,rr[i].runtime,time-rr[i].st1,time,rr[i].cycletime,rr[i].wctime);
			}		 	    
			else if(rr[i].st1>t&&time>=rr[i].arrivaltime)    //還需服務時間至少大于一個時間片 
			{
	 		  flag=1;  //把進程加入到就緒隊列中
	 		  time+=t;
			  rr[i].st1-=t;
              rr[i].cycletime=rr[i].finishtime-rr[i].arrivaltime; //計算周轉時間=完成時間-到達時間 
			  rr[i].wctime=rr[i].cycletime/(rr[i].runtime*1.0);  //計算帶權周轉時間=周轉時間/服務
			  printf("%3s\t  %d\t\t   %d\t\t   %d\t\t   %d\t\t   %d\t\t   %.2lf\n",rr[i].name,
	rr[i].arrivaltime,rr[i].runtime,time-t,time,rr[i].cycletime,rr[i].wctime);
			} 
	    	if(rr[i].sign==1)
 		       sum++;     //一個進程執(zhí)行完就+1
		} 
	 } 
	} 
	/*平均周轉時間  平均帶權周轉時間*/ 
	int sum1=0;
	double sum2=0;
	for(int i=0;i<n;i++)
	{
		
		sum1+=rr[i].cycletime;  //求所有進程周轉時間的和 
		sum2+=rr[i].wctime;  //求所有進程帶權周轉時間的和 
	}
	atime=sum1/(n*1.0);  //平均周轉時間=有進程周轉時間的和/進程數 
	awtime=sum2/n;   //平均帶權周轉時間=所有進程帶權周轉時間的和/進程數 
 } 
 /*輸出函數*/
 int output(int n)
 {
    printf("--------------------------------------------------------------------------------------------------------------------\n");
	printf("\t平均周轉時間    \t\t%.2lf\t\n",atime);
	printf("--------------------------------------------------------------------------------------------------------------------\n");
	printf("\t平均帶權周轉時間\t\t%.2lf\t\n",awtime);
	printf("====================================================================================================================\n"); 
}
/*主函數*/
int main()
{
	printf("時間片輪轉調度算法\n請輸入總進程數：\n");
	int n;
	scanf("%d",&n);   //輸入總進程數 
	input(n);   //輸入函數 
	rank(n);    //排序函數 
	rr_pcb(n);   //計算各時間 
	output(n);   //輸出函數 
	return 0;
 }

（6）測試數據或截圖：（時間片為1的見圖1，時間片為5的見圖2）

圖1 時間片=1時運行結果截圖

圖2?時間片=5時運行結果截圖

（7）運行結果分析：執(zhí)行時間圖像如下，

圖4-24 執(zhí)行時間圖像

時間片=1時，a、b、c、d四個進程的運行時間都大于規(guī)定的時間片，一個時間片內沒有完成運行，則都需要返回就緒隊列的隊尾，等待下一次調度繼續(xù)執(zhí)行。CPU被分配給當前就緒隊列的第一個進程。

時間片=5時，第一個進程的運行時間等于20>5，一個時間片內沒有完成運行，則進程a返回到就緒隊列末尾重新排隊，等待下一次調度；第二個進程的運行時間等于10>5，用完了規(guī)定的時間片，則進程b返回到緒隊列末尾，等待再次被調度執(zhí)行；第二個進程的運行時間等于15>5，則進程c返回到就緒隊列的隊尾，等到下一次輪轉到自己時再投入運行；第四個進程的運行時間為5，剛好在一個時間片內完成運行，則進程d放棄CPU的使用權。此時，進程調度程序又將CPU分配給當前就緒隊列的第一個進程，即進程a。

三、優(yōu)先級調度算法

（1）算法內容：優(yōu)先級調度算法既可以應用于高級調度（作業(yè)調度）也可以應用于低級調度（進程調度），還可用于實時系統(tǒng)。高級調度時，優(yōu)先數調度算法每次從后備作業(yè)隊列中選擇優(yōu)先級最高的作業(yè)調入內存，為其分配相應的資源并創(chuàng)建進程放入到進程就緒隊列中。低級調度時，優(yōu)先級調度算法每次從進程就緒隊列中選擇優(yōu)先級最高的進程為其分配CPU而投入運行。如果有多個優(yōu)先級最高的作業(yè)/進程，則可結合先來先服務或短作業(yè)/短進程優(yōu)先調度策略。

（2）算法要求：每個進程由一個進程控制塊（PCB）表示。進程控制塊可以包含如下信息：進程名，運行時間，優(yōu)先數，進程狀態(tài)等。進程的優(yōu)先數及需要運行時間可以事先人為指定（也可由隨機數產生）。每個進程的狀態(tài)可以是就緒W（Wait）,運行R（Run）或者完成F（Finish）3個狀態(tài)之一。

（3）設計思想：采用搶占式優(yōu)先級調度算法，具有最高級優(yōu)先級的就緒進程/線程首先得到CPU運行，并在運行過程中允許被具有更高優(yōu)先級的就緒進程/線程搶占CPU。如果有多個優(yōu)先級最高的進程，則結合先來先服務調度策略。每次運行之前，為每個進程任意確定它的“優(yōu)先數”和“要求運行時間”。處理器總是選隊首進程運行。采用動態(tài)改變優(yōu)先數的辦法，進程每運行1次，優(yōu)先數減1，要求運行時間減1。進程運行一次后，若要求運行時間不等于0，則將它加入隊列，否則，將狀態(tài)改為“結束”，退出隊列。若就緒隊列為空，結束，否則重復上述步驟。

（4）算法分析：定義進程控制塊；

input()函數;

output()函數；

max_priority()函數找出就緒態(tài)中優(yōu)先級最高的進程；

psa_pcb()函數為優(yōu)先級調度算法；

main()主函數；

（5）核心代碼：

#include<stdio.h>
/*結構體*/
struct PSA
{
char name[10];      //進程名
int runtime;       //運行時間
int priority;      //優(yōu)先數
char state;        //狀態(tài)，三狀態(tài)：W-就緒；R-運行；F-結束
};
struct PSA psa[10];   //定義進程控制塊數組

/*輸入函數*/
int input(int n)
{ 
printf("請輸入PCB的進程名，運行時間，優(yōu)先數:\n");
for(int i=0;i<n;i++)    //i為進程編號
{
scanf("%s\t%d\t%d",&psa[i].name,&psa[i].runtime,&psa[i].priority);
psa[i].state=‘W’;    //初始狀態(tài)都設為就緒
getchar();
}
}
/*輸出函數*/
int output(int n)
{ 
printf("\n==============================\n");
printf("進程號 運行時間 優(yōu)先數 狀態(tài)\n");
printf("------------------------------\n");
for(int i=0;i<n;i++)
printf("%s %7d%9d\t%s\n",psa[i].name,psa[i].runtime,psa[i].priority,&psa[i].state);
printf("==============================\n");
}
/*進程在就緒狀態(tài)時找出最大優(yōu)先數進程（返回值為最大優(yōu)先數編號）*/
int max_priority(int n)
{
int max=-1;    //max為最大優(yōu)先數
int m;     //m為最大優(yōu)先數進程的編號
for(int i=0;i<n;i++)
{      //進程在就緒狀態(tài)時找出最大優(yōu)先數
if(psa[i].state==‘R’)    //進程在運行狀態(tài)
return -1;
else if((max<psa[i].priority)&&(psa[i].state==‘W’)) //進程在就緒狀態(tài)
{
max=psa[i].priority;
m=i;     //把最大優(yōu)先數對應的編號賦給m
}
}
//確保最大優(yōu)先數進程還沒結束運行
if(psa[m].state==‘F’) //最大優(yōu)先數進程已結束運行
return -1;
else //最大優(yōu)先數進程還沒結束運行
return m; //返回值為最大優(yōu)先數編號
}
/*優(yōu)先數調度算法*/
int psa_pcb(int n)
{
int max_time=-1,m=0;
int sum=0;    //sum為程序總運行次數
for(int i=0;i<n;i++)
sum+=psa[i].runtime;
printf("\n初始時各進程信息如下:\n");
output(n);
getchar();
for(int j=0;j<sum;j++)
{
//當程序正在運行時
while(max_priority(n)!=-1)    //max_priority ()為找出最大優(yōu)先數進程函數，返回最大值對應的編號m
{
if(psa[max_priority(n)].priority!=0)
psa[max_priority(n)].state=‘R’;    //由就緒轉為運行態(tài)
else
{ //當優(yōu)先級降為0，進程還沒運行完時
for(int i=0;i<n;i++)
if(max_time<psa[i].runtime)
{
max_time=psa[i].runtime;
m=i;    //返回對應的編號
}
max_time=-1;
psa[m].state=‘R’;    //狀態(tài)轉為運行態(tài)
}
}
    //判斷程序狀態(tài)(對優(yōu)先數和運行時間操作) 
    for(int i=0;i<n;i++)
    {
        if(psa[i].state==‘R’)   //當進程處于運行狀態(tài)時 
        {
            if(psa[i].priority>0)     //優(yōu)先數>0
               psa[i].priority--;  //每運行一次優(yōu)先數-1
            psa[i].runtime--;   //每運行一次運行時間-1
        }
        if(psa[i].runtime==0)  //運行時間完
			psa[i].state=‘F’;   //進程狀態(tài)轉為完成狀態(tài)
        else     //運行時間沒完
			psa[i].state=‘W’;   //進程狀態(tài)轉為就緒狀態(tài)
    } 
    output(n);
    getchar();
}    
}
/*主函數*/
int main()
{
	printf("優(yōu)先數調度算法：\n輸入總進程數：\n");
	int n;
	scanf("%d",&n);   //輸入總進程數n
    input(n);    //輸入函數
    psa_pcb(n);   //優(yōu)先數調度算法
    return 0;
}

?
（6）測試數據或截圖：

??

?

（7）運行結果分析：初始時，a、b、c、d、e五個進程的狀態(tài)都是就緒態(tài)（W），其中c的優(yōu)先級最大，則c首先得到CPU運行，其運行時間為2，在運行狀態(tài)時運行時間減1，優(yōu)先數減1；進程a的運行時間為0，此時a的狀態(tài)由就緒態(tài)變?yōu)橥瓿蓱B(tài)；之后c、e的優(yōu)先數都是最大的，但根據先來先服務調度策略，c先處于運行態(tài)，優(yōu)先數減1，運行時間減1為0，所以c變成完成態(tài)；此時只有b、d、e三個進程處于就緒態(tài)，其中e的優(yōu)先數最大，則e獲得CPU投入運行，其運行時間減1，優(yōu)先數減1；然后b和e的優(yōu)先數都一樣大，根據先來先服務調度策略，則b搶占CPU處于運行態(tài)，運行時間減1為0，則b變成完成態(tài)；此時只剩下d和e兩個進程，e的優(yōu)先數較大，則e搶占CPU處于運行態(tài)，優(yōu)先數和運行時間減1；e優(yōu)先數減1后與d的一樣大，但根據先來先服務原則，d先獲得CPU，處于運行態(tài)，優(yōu)先數和運行時間減1；此刻，e的優(yōu)先數比d大，故e得到CPU運行，運行時間和優(yōu)先數減1；d和e的優(yōu)先數又是一樣大，但d先運行，運行時間和優(yōu)先數減1，則e優(yōu)先數大于d，e獲得CPU，運行時間減1為0，e處于完成態(tài)；最后只剩d獲得CPU運行，運行時間減1為0，變成完成態(tài)。總之，優(yōu)先級高的進程先獲得CPU處于運行態(tài)，運行一次后，運行時間與優(yōu)先數減1,當運行時間不為0時加入就緒隊列，運行時等于0時狀態(tài)改為結束（F）。如果有多個優(yōu)先級一樣高的進程，則根據先來先服務原則處理。文章來源地址http://www.zghlxwxcb.cn/news/detail-420761.html

到了這里，關于操作系統(tǒng)進程調度算法——先來先服務、時間片輪轉、優(yōu)先級調度算法的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！