進(jìn)程先來先服務(wù)調(diào)度算法的動(dòng)態(tài)演示研究

申鴻燁，于維海

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

進(jìn)程先來先服務(wù)調(diào)度算法的動(dòng)態(tài)演示研究

申鴻燁，于維海

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

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

調(diào)度算法；先來先服務(wù)

0 引言

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

1 先來先服務(wù)算法

2 算法實(shí)現(xiàn)

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

衡量作業(yè)性能的標(biāo)準(zhǔn)方面，可以使用CPU利用

為演示需要，設(shè)有3個(gè)作業(yè)隊(duì)列，編號(hào)分別是1、2、3，每個(gè)進(jìn)程到達(dá)時(shí)間相差一個(gè)時(shí)間單位，如圖1所示。

圖1 先來先服務(wù)調(diào)度算法

各進(jìn)程初始數(shù)據(jù)如下表1所示。

作業(yè)控制塊JCB結(jié)構(gòu)體包括：作業(yè)名稱、作業(yè)到達(dá)時(shí)間、作業(yè)運(yùn)行時(shí)間、作業(yè)開始運(yùn)行的時(shí)間、作業(yè)完成的時(shí)間、作業(yè)的周轉(zhuǎn)時(shí)間等，結(jié)構(gòu)體如下：

JCB{

char jobName[10];//名稱

intarriveTime;//到達(dá)時(shí)間

int runTime;//運(yùn)行時(shí)長

intstartTime;//開始時(shí)間

intendTime;//完成時(shí)間

intzzTime;//周轉(zhuǎn)時(shí)間

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

};

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

void init(struct JCB*jcb){

......

jcb[0].arriveTime=0;//本例假設(shè)每個(gè)進(jìn)程相差一個(gè)時(shí)間單位

jcb[1].arriveTime=1;

jcb[2].arriveTime=2;

......

}

先來先服務(wù)意味著先到的進(jìn)程優(yōu)先運(yùn)行，因此需要對(duì)其排序，使用sort函數(shù)將各個(gè)進(jìn)程按照到達(dá)進(jìn)程鏈的時(shí)間先后，按照升序排列，準(zhǔn)備下一步運(yùn)算。

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 各進(jìn)程初始數(shù)據(jù)

jcb[idx]=t;

}

}

//先來先服務(wù)調(diào)度算法

void runIt(struct JCB*jcb){

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

sort(jcb);

intcurrentTime=0;

//進(jìn)程調(diào)度currentTime每次加1，直到進(jìn)程全部被調(diào)度完成為止

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);//打印當(dāng)前進(jìn)程狀態(tài)

}

currentTime++;//模擬時(shí)鐘不停運(yùn)行，直到進(jìn)程全部被調(diào)度完成為止

}

}

}

3 運(yùn)行

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

printIt(struct JCB*jcb){

printf("當(dāng)前時(shí)間：%d ",currentTime);

printf("作業(yè)號(hào)到達(dá)時(shí)間需要運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間狀態(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);

}

}

通過計(jì)算，本例的先來先服務(wù)算法的性能如表2所示。

4 結(jié)語

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

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

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

[3]張堯?qū)W．計(jì)算機(jī)操作系統(tǒng)教程[M]．北京：清華大學(xué)出版社，2013.10.

[4]Andrew S.Tanenbaum．操作系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[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-），男，河北內(nèi)丘人，碩士，研究生，研究方向?yàn)檫h(yuǎn)程教育、云計(jì)算、大數(shù)據(jù)

2017-05-22

2017-07-28

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

1007-1423（2017）22-0003-03

10.3969/j.issn.1007-1423.2017.22.001

于維海（1976-），男，遼寧沈陽人，碩士，講師，研究方向?yàn)閿?shù)據(jù)挖掘

Scheduling Algorithm;FirstCome FirstServed