實(shí)現(xiàn)FCFS和SJF調(diào)度算法

1、操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)一：作業(yè)調(diào)度學(xué)院：軟件學(xué)院專業(yè)：軟件工程 班級(jí)：軟件工程12-01 姓名：* 學(xué)號(hào)：541213460157實(shí)驗(yàn)一：作業(yè)調(diào)度實(shí)現(xiàn)FCFS和SJF調(diào)度算法【實(shí)驗(yàn)題目】：編寫程序，實(shí)現(xiàn)FCFS和SJF算法，模擬作業(yè)調(diào)度過(guò)程，加深對(duì)作業(yè)調(diào)度的理解?！緦?shí)驗(yàn)內(nèi)容】實(shí)現(xiàn)FCFS和SJF調(diào)度算法。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)（JCB，后備作業(yè)隊(duì)列） 算法實(shí)現(xiàn)與模擬（排序、調(diào)度） 輸出調(diào)度結(jié)果，展示調(diào)度過(guò)程并解釋【實(shí)驗(yàn)要求】1. 設(shè)計(jì)作業(yè)控制塊(JCB)的數(shù)據(jù)結(jié)構(gòu) 應(yīng)包含實(shí)驗(yàn)必須的數(shù)據(jù)項(xiàng)，如作業(yè)ID、需要的服務(wù)時(shí)間、進(jìn)入系統(tǒng)時(shí)間、完成時(shí)間，以及實(shí)驗(yàn)者認(rèn)為有必要的其他數(shù)據(jù)項(xiàng)。2. 實(shí)現(xiàn)排序算法（將作業(yè)排隊(duì)

2、） 策略1：按“進(jìn)入系統(tǒng)時(shí)間”對(duì)作業(yè)隊(duì)列排序(FCFS) 策略2：按“需要的服務(wù)時(shí)間”對(duì)作業(yè)隊(duì)列排序（SJF）3. 實(shí)現(xiàn)調(diào)度過(guò)程模擬（1）每個(gè)作業(yè)用一個(gè)JCB表示，如果模擬FCFS，按策略1將作業(yè)排隊(duì)，如果模擬SJF，按策略2將作業(yè)排隊(duì)（2）選擇隊(duì)首的作業(yè)，將其從后備隊(duì)列移出。（3）（作業(yè)運(yùn)行過(guò)程，在本實(shí)驗(yàn)中，無(wú)需實(shí)現(xiàn)，可認(rèn)為后備隊(duì)列上的作業(yè)一但被調(diào)度程序選出，就順利運(yùn)行完畢，可以進(jìn)入第4步）（4）計(jì)算選中作業(yè)的周轉(zhuǎn)時(shí)間（5） 進(jìn)行下一次調(diào)度（去往第2步）4.實(shí)現(xiàn)結(jié)果輸出 輸出作業(yè)狀態(tài)表，展示調(diào)度過(guò)程 初始作業(yè)狀態(tài)（未調(diào)度時(shí)） 每次調(diào)度后的作業(yè)狀態(tài)5.撰寫實(shí)驗(yàn)報(bào)告 包含實(shí)驗(yàn)要求中14項(xiàng)內(nèi)容，要

3、求有設(shè)計(jì)圖（結(jié)構(gòu)圖/流程圖）和源代碼。 注明使用的編程語(yǔ)言和環(huán)境。注意事項(xiàng) 實(shí)驗(yàn)中注重實(shí)現(xiàn)算法本質(zhì)（先來(lái)先服務(wù)，短作業(yè)優(yōu)先）。 兩個(gè)算法可以使用一套程序，差別只在隊(duì)列的排序方式。 這兩個(gè)算法也可適用于進(jìn)程調(diào)度。關(guān)于作業(yè)調(diào)度和進(jìn)程調(diào)度的區(qū)別，只要求概念上理解清楚，不要求實(shí)現(xiàn)。設(shè)計(jì)作業(yè)控制塊(JCB)的數(shù)據(jù)結(jié)構(gòu) 每個(gè)作業(yè)由一個(gè)作業(yè)控制塊JCB表示，JCB可以包含如下信息：作業(yè)名、提交時(shí)間、所需的運(yùn)行時(shí)間、所需的資源、作業(yè)狀態(tài)、鏈指針等等。具體結(jié)構(gòu)如下：  typedef struct jcbchar name10; /*

4、0;作業(yè)名 */       char state;  /* 作業(yè)狀態(tài) */      int ts; /* 提交時(shí)間 */      float super; /* 優(yōu)先權(quán) */ int tb; /* 開(kāi)始運(yùn)行時(shí)間 */

5、0;     int tc;  /* 完成時(shí)間 */      float ti;  /* 周轉(zhuǎn)時(shí)間 */    float wi;  /* 帶權(quán)周轉(zhuǎn)時(shí)間 */     int ntime;  /* 作業(yè)所需運(yùn)行時(shí)間 *

6、/      char resource10;  /* 所需資源 */        struct jcb *next;  /* 結(jié)構(gòu)體指針 */          JCB; JCB *p,*tail=NULL,*head=NULL;

7、60; 作業(yè)的狀態(tài)可以是等待W(Wait)、運(yùn)行R(Run)和完成F(Finish)三種狀態(tài)之一。每個(gè)作業(yè)的最初狀態(tài)總是等待W。，組成一個(gè)后備隊(duì)列等待，總是首先調(diào)度等待隊(duì)列中隊(duì)首的作業(yè)。  本實(shí)驗(yàn)采用鏈表的形式存放各后備隊(duì)列當(dāng)中的作業(yè)控制塊，各個(gè)等待的作業(yè)按照提交時(shí)刻的先后次序排隊(duì)。當(dāng)一個(gè)作業(yè)進(jìn)入系統(tǒng)時(shí)，就為其動(dòng)態(tài)建立一作業(yè)控制塊（JCB），掛入后備隊(duì)列尾部。當(dāng)作業(yè)調(diào)度時(shí)，從后備隊(duì)列中按某種調(diào)度算法選擇一作業(yè)，讓其進(jìn)入主存以便占用CPU執(zhí)行。 每個(gè)作業(yè)完成后要打印該作業(yè)的開(kāi)始運(yùn)行時(shí)刻、完成時(shí)刻、周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，這一組作業(yè)完成后要計(jì)算并打印這組作業(yè)的平均周轉(zhuǎn)

8、時(shí)間、帶權(quán)平均周轉(zhuǎn)時(shí)間。設(shè)計(jì)圖編程語(yǔ)言：c+編程環(huán)境：Visual C+ 6.0程序代碼：FCFS：#include <iostream> using namespace std; class Fcfs private: int num10; /作業(yè)編號(hào) double arriveTime10; /到達(dá)時(shí)間 double startTime10; /開(kāi)始時(shí)間，進(jìn)內(nèi)存時(shí)間 double workTime10; /工作時(shí)間 double finishTime10; /完成時(shí)間 double cirTime10; /存放每一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間 /double freeTime10; /上一

9、個(gè)作業(yè)已結(jié)束，但下一個(gè)作業(yè)還未到，存放這一段空閑時(shí)間 public: Fcfs(int n) /n為作業(yè)數(shù)目 cout<<"默認(rèn)第一個(gè)作業(yè)的到達(dá)時(shí)間為0。"<<endl; for(int i=0;i<n;i+) numi=i+1; /給作業(yè)編號(hào) cout<<"第"<<numi<<"個(gè)作業(yè)："<<endl; cout<<"請(qǐng)輸入該作業(yè)的到達(dá)時(shí)間：" cin>>arriveTimei; if(i=0) arriveTi

10、mei=0; /默認(rèn)第一個(gè)作業(yè)的到達(dá)時(shí)間為0 cout<<"請(qǐng)輸入該作業(yè)的執(zhí)行時(shí)間：" cin>>workTimei; if(i=0) startTimei=0; finishTimei=workTimei; /freeTimei=0; else if(arriveTimei<=finishTimei-1) /如果后一個(gè)作業(yè)已到，而前一個(gè)作業(yè)未結(jié)束 startTimei=finishTimei-1; /則后一個(gè)作業(yè)的開(kāi)始時(shí)間為上一個(gè)作業(yè)的結(jié)束時(shí)間finishTimei=startTimei+workTimei; /freeTimei=0; /前

11、一個(gè)一結(jié)束就開(kāi)始工作，沒(méi)有空閑時(shí)間 else if(arriveTimei>finishTimei-1) /freeTimei=arriveTimei-finishTimei-1;/計(jì)算空閑時(shí)間，前一個(gè)作業(yè)已完成，但后一個(gè)作業(yè)還沒(méi)到，中間空閑時(shí)間 startTimei=arriveTimei; /由于來(lái)的時(shí)候前一個(gè)作業(yè)已完成，則該作業(yè)的開(kāi)始時(shí)間即為它的到達(dá)時(shí)間 finishTimei=startTimei+workTimei; cirTimei=finishTimei-arriveTimei; /計(jì)算平均周轉(zhuǎn)時(shí)間 double getAverageCir(int n) /n為作業(yè)數(shù) do

12、uble averageCir,sumCir=0; for(int i=0;i<n;i+) sumCir+=cirTimei; averageCir=sumCir/n; return averageCir; /打印輸出 void print(int n) /n為作業(yè)數(shù) cout<<"numt"<<"arrivet"<<"startt"<<"workt"<<"finisht"<<"cirt"<&

13、lt;endl; for(int i=0;i<n;i+) cout<<numi<<"t"<<arriveTimei<<"t"<<startTimei<<"t"<<workTimei<<"t"<<finishTimei<<"t"<<cirTimei<<"t"<<endl; cout<<endl; cout&

14、lt;<"平均周轉(zhuǎn)時(shí)間："<<getAverageCir(n)<<endl; ; int main() int n; /n為作業(yè)數(shù)目 cout<<"請(qǐng)輸入作業(yè)數(shù)目：" cin>>n; Fcfs f=Fcfs(n); f.print(n); return 0; SJF:#include<iostream>using namespace std;class SJF private: int num10; /作業(yè)編號(hào) double arriveTime10; /到達(dá)時(shí)間 double start

15、Time10; /開(kāi)始時(shí)間，進(jìn)內(nèi)存時(shí)間 double workTime10; /工作時(shí)間 double finishTime10; /完成時(shí)間 double cirTime10; /存放每一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間 public:SJF(int n) /n為作業(yè)數(shù)目 int i; cout<<"默認(rèn)第一個(gè)作業(yè)的到達(dá)時(shí)間為0。"<<endl;for(i=0;i<n;i+) numi=i+1; /給作業(yè)編號(hào) cout<<"第"<<numi<<"個(gè)作業(yè)："<<endl;

16、cout<<"請(qǐng)輸入該作業(yè)的到達(dá)時(shí)間："cin>>arriveTimei;if(i=0)arriveTimei=0; /默認(rèn)第一個(gè)作業(yè)的到達(dá)時(shí)間為0cout<<"請(qǐng)輸入該作業(yè)的執(zhí)行時(shí)間："cin>>workTimei;if(i=0) startTimei=0; finishTimei=workTimei; cirTimei=finishTimei-arriveTimei; else /排序 for(int j=1;j<i;j+) /i=當(dāng)前作業(yè)數(shù)目-1，這里不能用numi表示當(dāng)前作業(yè)數(shù) 起泡排序法fo

17、r (int k=1;k<=i-j;k+)if(workTimek>workTimek+1)double temp;temp=numk; numk=numk+1; numk+1=temp;temp=arriveTimek; arriveTimek=arriveTimek+1; arriveTimek+1=temp; temp=workTimek; workTimek=workTimek+1; workTimek+1=temp;for(i=1;i<n;i+) /排序后計(jì)算各作業(yè)的開(kāi)始、結(jié)束、周轉(zhuǎn)時(shí)間startTimei=finishTimei-1; finishTimei=st

18、artTimei+workTimei; cirTimei=finishTimei-arriveTimei;/計(jì)算平均周轉(zhuǎn)時(shí)間double getAverageCir(int n) /n為作業(yè)數(shù) double averageCir,sumCir=0; for(int i=0;i<n;i+) sumCir+=cirTimei; averageCir=sumCir/n; return averageCir; /打印輸出void print(int n) /n為作業(yè)數(shù)cout<<"numt"<<"arrivet"<<&q

19、uot;startt"<<"workt"<<"finisht"<<"cirt"<<endl; for(int i=0;i<n;i+)cout<<numi<<"t"<<arriveTimei<<"t"<<startTimei<<"t"<<workTimei<<"t"<<finishTimei<<"t"<<cirTimei<<"t"<<endl;cout<<endl; cout<<"平均周轉(zhuǎn)時(shí)