申鴻燁，于維海

（沈陽廣播電視大學信息工程學院，沈陽110003)

進程先來先服務調度算法的動態(tài)演示研究

申鴻燁，于維海

（沈陽廣播電視大學信息工程學院，沈陽110003)

進程的先來先服務算法在操作系統(tǒng)中具有重要地位，給出相關代碼的動態(tài)演示，通過該演示，學生可以更加清晰地了解先來先服務算法的基本思想和工作流程，了解該算法與其他算法的聯系與區(qū)別。

調度算法；先來先服務

0 引言

在日常生活中，經常要發(fā)生調度問題。例如，建筑工地中如何安排各工種的施工順序等。在操作系統(tǒng)中，同樣離不開調度，調度不僅涉及到進程調度，而且還包括作業(yè)調度。計算機中，CPU是計算機最主要的資源，只有通過調度才能把CPU分配給合適的進程。大型的計算機操作系統(tǒng)里，往往有上百個終端和主機相連接，有眾多用戶同時在線訪問一臺服務器，這些進程不可能一股腦地并發(fā)執(zhí)行，而是按照一定的邏輯順序先后執(zhí)行，那么怎樣從中挑選出合適的進程讓它參與運行呢？率、吞吐量、周轉時間、平均帶權周轉時間、就緒等待時間響應時間等。其中，先來先服務算法就是一種最簡單的調度算法，它的思路就是排隊買票的方法，每次調度從后備隊列中挑選出最前面的一個，把它調入內存，分配相應的資源創(chuàng)建進程，然后把進程放入到就緒隊列，然后把CPU分配給該進程讓它參與運行，一直運行下去直到完成或者由于某種原因阻塞，放棄CPU才結束。這樣當某個進程進入到就緒隊列中時，它的PCB（Process Control Block進程控制塊）將其鏈接到就緒隊列的末尾，每次調度算法都從隊首獲取該進程，分配CPU，使其運行。

1 先來先服務算法

2 算法實現

以作業(yè)調度算法為例，它的工作是，把合適的作業(yè)，調入到內存中。設計一個調度算法包括多個指標：例如進程調度的設計目標，對于批處理系統(tǒng)而言，應該盡量提高各種資源的利用率和增加系統(tǒng)的平均吞吐量；如果是實時系統(tǒng)，為了提高系統(tǒng)對外部的響應，要考慮對時間的及時可靠處理的效率；還要考慮均衡性，盡量使系統(tǒng)中各類資源能夠同時得到利用，提高資源的利用率，可以設置作業(yè)的優(yōu)先級，優(yōu)先考慮優(yōu)先級高的作業(yè)。

衡量作業(yè)性能的標準方面，可以使用CPU利用

為演示需要，設有3個作業(yè)隊列，編號分別是1、2、3，每個進程到達時間相差一個時間單位，如圖1所示。

圖1 先來先服務調度算法

各進程初始數據如下表1所示。

作業(yè)控制塊JCB結構體包括：作業(yè)名稱、作業(yè)到達時間、作業(yè)運行時間、作業(yè)開始運行的時間、作業(yè)完成的時間、作業(yè)的周轉時間等，結構體如下：

JCB{

char jobName[10];//名稱

intarriveTime;//到達時間

int runTime;//運行時長

intstartTime;//開始時間

intendTime;//完成時間

intzzTime;//周轉時間

charstatus[10];//狀態(tài)

};

init函數用于創(chuàng)建JCB，代碼如下：

void init(struct JCB*jcb){

......

jcb[0].arriveTime=0;//本例假設每個進程相差一個時間單位

jcb[1].arriveTime=1;

jcb[2].arriveTime=2;

......

}

先來先服務意味著先到的進程優(yōu)先運行，因此需要對其排序，使用sort函數將各個進程按照到達進程鏈的時間先后，按照升序排列，準備下一步運算。

void sort(struct JCB*jcb){

for(int i=0;i<3;i++){

intmin=jcb[i].arriveTime;

int idx=i;

for(int j=i+1;j<3;j++){

if(jcb[j].arriveTime

min=jcb[j].arriveTime;

idx=j;

}

}

struct JCB t=jcb[i];

jcb[i]=jcb[minIndex];

表1 各進程初始數據

jcb[idx]=t;

}

}

//先來先服務調度算法

void runIt(struct JCB*jcb){

init(jcb);//創(chuàng)建JCB

sort(jcb);

intcurrentTime=0;

//進程調度currentTime每次加1，直到進程全部被調度完成為止

for(i=0;i<3;i++){

jcb[i].startTime=currentTime;

jcb[i].endTime=jcb[i].startTime+jcb[i].runTime;

jcb[i].zzTime=jcb[i].endTime-jcb[i].arriveTime;

strcpy(jcb[i].status,RUN);

while(true){

if(currentTime==jcb[i].endTime){

strcpy(jcb[i].status,FINISH);

break;

}else{

printIt(jcb);//打印當前進程狀態(tài)

}

currentTime++;//模擬時鐘不停運行，直到進程全部被調度完成為止

}

}

}

3 運行

上述各函數分別進行了初始化等工作，下面執(zhí)行printIt函數，逐個時間片將三個進程的工作狀態(tài)列舉打印出來，展示動態(tài)過程。

printIt(struct JCB*jcb){

printf("當前時間：%d ",currentTime);

printf("作業(yè)號到達時間需要運行時間開始時間完成時間周轉時間狀態(tài) ");

for(inti=0;i<3;i++){

printf("%s%d%d%d%d%d%s ",jcb[i].job?Name,jcb[i].arriveTime,jcb[i].runTime,jcb[i].startTime,jcb[i]. endTime,jcb[i].zzTime,jcb[i].status);

}

}

通過計算，本例的先來先服務算法的性能如表2所示。

4 結語

本文給出了操作系統(tǒng)課程中先來先服務算法的程序實現，給出了相關代碼的動態(tài)演示，通過該演示，學生可以更加清晰地了解先來先服務算法的基本思想和工作流程，了解該算法與時間片輪轉法、優(yōu)先級法、短作業(yè)優(yōu)先法、最短剩余時間優(yōu)先法、多級隊列法、多級反饋隊列法之間的聯系與區(qū)別，為后續(xù)課程的學習打下了良好鋪墊。

[1]孟慶昌．操作系統(tǒng)[M]．北京：中央廣播電視大學出版社，2008.

[2](美)斯托林斯著．操作系統(tǒng)：精髓與設計原理[M]．北京：機械工業(yè)出版社，2010.9.

[3]張堯學．計算機操作系統(tǒng)教程[M]．北京：清華大學出版社，2013.10.

[4]Andrew S.Tanenbaum．操作系統(tǒng)設計與實現[M]．北京：電子工業(yè)出版社，2015.6.

Research on the Dynam ic Demonstration FirstCome First Service Process Scheduling Algorithm

SHENHong-ye，YUWei-hai
（Schoolof Information Engineering,Shenyang Radio and TVUniversity,Shenyang 110003）

First come first serve algorithm plays an important role in the operating system,gives the dynamic demonstration of the relevant code, through the demonstration,students canmore clearly understand the basic idea and working processof first come firstservice,don'tunder?stand connectionsand the algorithm with otheralgorithm.

申鴻燁（1973-），男，河北內丘人，碩士，研究生，研究方向為遠程教育、云計算、大數據

2017-05-22

2017-07-28

2016年度遼寧省教育科學“十三五”規(guī)劃課題（No.JG16EB182）

1007-1423（2017）22-0003-03

10.3969/j.issn.1007-1423.2017.22.001

于維海（1976-），男，遼寧沈陽人，碩士，講師，研究方向為數據挖掘

Scheduling Algorithm;FirstCome FirstServed