蘭州理工大學(xué)—操作系統(tǒng)課設(shè)—作業(yè)調(diào)度模擬程序說明書

1、目 錄前 言2摘 要3正 文41.設(shè)計(jì)思想42.算法用到的主要數(shù)據(jù)結(jié)構(gòu)（采用類c語(yǔ)言定義）53.相關(guān)的各模塊的偽碼算法54.調(diào)試分析85.測(cè)試結(jié)果146.源程序（帶注釋）15總 結(jié)24參考文獻(xiàn)25致 謝26前 言每個(gè)用戶請(qǐng)求計(jì)算機(jī)計(jì)算的一個(gè)計(jì)算任務(wù)叫做一個(gè)作業(yè)。一個(gè)作業(yè)從輸入初始數(shù)據(jù)到得到計(jì)算結(jié)果，要經(jīng)過若干個(gè)步驟的相繼執(zhí)行。例如：編輯、編譯、運(yùn)行等，其中每一個(gè)步驟稱作一個(gè)作業(yè)步。用戶向系統(tǒng)提出作業(yè)加工步驟的方式稱作業(yè)控制方式，作業(yè)控制方式有兩種：終端控制方式（又稱直接控制方式或聯(lián)機(jī)控制方式）和批處理控制方式（又稱自動(dòng)控制方式或脫機(jī)控制方式）。在批處理控制方式下，用戶采用系統(tǒng)提供的作業(yè)控制語(yǔ)言

2、（JCL）寫好作業(yè)說明書，說明作業(yè)加工的步驟。操作員把一批作業(yè)組織成輸入流，通過“預(yù)輸入”手段使每個(gè)作業(yè)的信息（包括作業(yè)說明書、源程序、初始數(shù)據(jù)等）暫存在輔助存儲(chǔ)器的“輸入井”中。批處理多道程序操作系統(tǒng)的作業(yè)管理有兩個(gè)任務(wù)：作業(yè)調(diào)度和作業(yè)控制。采用多道程序設(shè)計(jì)方法的操作系統(tǒng)，在系統(tǒng)中要經(jīng)常用保留多個(gè)運(yùn)行的作業(yè)，以提高系統(tǒng)效率。作業(yè)調(diào)度從系統(tǒng)已接納的作業(yè)分配所需的系統(tǒng)資源。對(duì)被選中運(yùn)行的作業(yè)按照它們各自的作業(yè)說明書中規(guī)定的步驟進(jìn)行控制。摘 要對(duì)于成批進(jìn)入系統(tǒng)的作業(yè)來說，根據(jù)作業(yè)控制塊信息，按照一定的策略選取若干個(gè)作業(yè)使它們可以去獲得處理器運(yùn)行，這項(xiàng)工作稱為作業(yè)調(diào)度。而對(duì)于每個(gè)用戶來說，總希望自己

3、的作業(yè)的周轉(zhuǎn)時(shí)間盡可能小，最理想的情況是進(jìn)入系統(tǒng)后能立即運(yùn)行，即希望作業(yè)的周轉(zhuǎn)時(shí)間等于執(zhí)行時(shí)間。對(duì)于系統(tǒng)來說，則希望進(jìn)入系統(tǒng)的作業(yè)的平均周轉(zhuǎn)時(shí)間盡可能的小，是的CPU的利用率盡量高。于是，每個(gè)計(jì)算機(jī)系統(tǒng)都必須選擇適當(dāng)?shù)淖鳂I(yè)調(diào)度算法，既考慮用戶的要求又要有利于系統(tǒng)效率的提高。當(dāng)選中一個(gè)作業(yè)后，首先要建立此作業(yè)的用戶進(jìn)程，同時(shí)為其分配系統(tǒng)資源，接著就可以投入運(yùn)行。當(dāng)一個(gè)作業(yè)執(zhí)行結(jié)束進(jìn)入完成狀態(tài)時(shí)，負(fù)責(zé)收回資源，撤銷其作業(yè)控制塊。本課設(shè)則模擬了作業(yè)調(diào)度的實(shí)現(xiàn)，通過FCFS、SJF、HRF幾種算法的實(shí)現(xiàn)，說明了作業(yè)調(diào)度在操作系統(tǒng)中的作用。關(guān)鍵字：作業(yè)；調(diào)度；FCFS；SJF；HRF正 文1. 設(shè)計(jì)思想

4、作業(yè)調(diào)度是操作系統(tǒng)非常重要的內(nèi)容，選擇合適的算法可以提高計(jì)算機(jī)的運(yùn)行效率。根據(jù)操作系統(tǒng)的學(xué)習(xí)，我們采用FCFS、SJF、HRF算法各自處理相同的作業(yè)，對(duì)比各自的平均周轉(zhuǎn)時(shí)間和平均代權(quán)周轉(zhuǎn)時(shí)間。建立作業(yè)的控制塊信息，利用多道程序設(shè)計(jì)，采用不同的策略運(yùn)行，觀察各算法的優(yōu)略性。 1.1各模塊及程序流程圖輸入作業(yè)J0J1J2J3選擇算法FCFSSJFHRF執(zhí)行執(zhí)行執(zhí)行打印結(jié)果2. 算法用到的主要數(shù)據(jù)結(jié)構(gòu)（采用類c語(yǔ)言定義）2.1運(yùn)行時(shí)間等控制塊struct worktime float Tb; /作業(yè)運(yùn)行時(shí)刻 float Tc; /作業(yè)完成時(shí)刻 float Ti; /周轉(zhuǎn)時(shí)間 float Wi; /帶

5、權(quán)周轉(zhuǎn)時(shí)間;2.2作業(yè)控制塊信息struct jcb /*定義作業(yè)控制塊JCB */ char name10; /作業(yè)名 float subtime; /作業(yè)提交時(shí)間 float runtime; /作業(yè)所需的運(yùn)行時(shí)間/ char resource; /所需資源 float Rp; /后備作業(yè)響應(yīng)比 char state; /作業(yè)狀態(tài) struct worktime wt; struct jcb* link; /鏈指針*jcb_ready=NULL,*j;3. 相關(guān)的各模塊的偽碼算法3.1 FCFS算法的偽碼算法typedef struct jcb JCB;float T=0;void sor

6、t() /* 建立對(duì)作業(yè)進(jìn)行提交時(shí)間排列函數(shù)*/ JCB *first, *second; int insert=0; if(jcb_ready=NULL)|(j-subtime)subtime) /*作業(yè)提交時(shí)間最短的,插入隊(duì)首*/ j-link=jcb_ready; jcb_ready=j; T=j-subtime; j-Rp=1; else /* 作業(yè)比較提交時(shí)間,插入適當(dāng)?shù)奈恢弥?/ first=jcb_ready; second=first-link; while(second!=NULL) if(j-subtime)subtime) /*若插入作業(yè)比當(dāng)前作業(yè)提交時(shí)間短,*/ /*插

7、入到當(dāng)前作業(yè)前面*/ j-link=second; first-link=j; second=NULL; insert=1; else /* 插入作業(yè)優(yōu)先數(shù)最低,則插入到隊(duì)尾*/ first=first-link; second=second-link; if (insert=0) first-link=j; 3.2 SJF偽碼算法void SJFget()/* 獲取隊(duì)列中的最短作業(yè) */ JCB *front,*mintime,*rear; int ipmove=0; mintime=jcb_ready; rear=mintime-link; while(rear!=NULL) if (re

8、ar!=NULL)&(T=rear-subtime)&(mintime-runtime)(rear-runtime) front=mintime; mintime=rear; rear=rear-link; ipmove=1; else rear=rear-link; if (ipmove=1) front-link=mintime-link; mintime-link=jcb_ready; jcb_ready=mintime;3.3 HRF算法的偽碼算法void HRNget()/* 獲取隊(duì)列中的最高響應(yīng)作業(yè) */ JCB *front,*mintime,*rear; int ipmove=

9、0; mintime=jcb_ready; rear=mintime-link; while(rear!=NULL) if (rear!=NULL)&(T=rear-subtime)&(mintime-Rp)Rp) front=mintime; mintime=rear; rear=rear-link; ipmove=1; else rear=rear-link; if (ipmove=1) front-link=mintime-link; mintime-link=jcb_ready; jcb_ready=mintime;4. 調(diào)試分析1、FCFS1.1根據(jù)提示并輸入作業(yè)數(shù)。1.2輸入第一號(hào)

10、作業(yè)的作業(yè)名。1.3輸入第二號(hào)作業(yè)的作業(yè)名。1.4輸入第三號(hào)作業(yè)的作業(yè)名。1.5輸入第四號(hào)作業(yè)的作業(yè)名。1.6選擇作業(yè)調(diào)度算法。1.7選擇FCFS算法，并執(zhí)行完第一個(gè)作業(yè)。1.8執(zhí)行完第二個(gè)作業(yè)。1.9執(zhí)行完第三個(gè)作業(yè)。1.10執(zhí)行完第四個(gè)作業(yè)。1.11顯示所有作業(yè)執(zhí)行完之后的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。FCFS算法作業(yè)調(diào)度測(cè)試完成，根據(jù)以上方法測(cè)試SJF和HRF算法的作業(yè)調(diào)度。5. 測(cè)試結(jié)果一、FCFS二、SJF三、HRFHRF算法下的作業(yè)調(diào)度結(jié)果如下。6. 源程序（帶注釋）#include stdio.h #include #include #define getpch(type) (

11、type*)malloc(sizeof(type) /#define NULL 0struct worktime float Tb; /作業(yè)運(yùn)行時(shí)刻 float Tc; /作業(yè)完成時(shí)刻 float Ti; /周轉(zhuǎn)時(shí)間 float Wi; /帶權(quán)周轉(zhuǎn)時(shí)間;struct jcb /*定義作業(yè)控制塊JCB */ char name10; /作業(yè)名 float subtime; /作業(yè)提交時(shí)間 float runtime; /作業(yè)所需的運(yùn)行時(shí)間/ char resource; /所需資源 float Rp; /后備作業(yè)響應(yīng)比 char state; /作業(yè)狀態(tài) struct worktime wt;

12、struct jcb* link; /鏈指針*jcb_ready=NULL,*j;typedef struct jcb JCB;float T=0;void sort() /* 建立對(duì)作業(yè)進(jìn)行提交時(shí)間排列函數(shù)*/ JCB *first, *second; int insert=0; if(jcb_ready=NULL)|(j-subtime)subtime) /*作業(yè)提交時(shí)間最短的,插入隊(duì)首*/ j-link=jcb_ready; jcb_ready=j; T=j-subtime; j-Rp=1; else /* 作業(yè)比較提交時(shí)間,插入適當(dāng)?shù)奈恢弥?/ first=jcb_ready; sec

13、ond=first-link; while(second!=NULL) if(j-subtime)subtime) /*若插入作業(yè)比當(dāng)前作業(yè)提交時(shí)間短,*/ /*插入到當(dāng)前作業(yè)前面*/ j-link=second; first-link=j; second=NULL; insert=1; else /* 插入作業(yè)優(yōu)先數(shù)最低,則插入到隊(duì)尾*/ first=first-link; second=second-link; if (insert=0) first-link=j; void SJFget()/* 獲取隊(duì)列中的最短作業(yè) */ JCB *front,*mintime,*rear; int i

14、pmove=0; mintime=jcb_ready; rear=mintime-link; while(rear!=NULL) if (rear!=NULL)&(T=rear-subtime)&(mintime-runtime)(rear-runtime) front=mintime; mintime=rear; rear=rear-link; ipmove=1; else rear=rear-link; if (ipmove=1) front-link=mintime-link; mintime-link=jcb_ready; jcb_ready=mintime;void HRNget()

15、/* 獲取隊(duì)列中的最高響應(yīng)作業(yè) */ JCB *front,*mintime,*rear; int ipmove=0; mintime=jcb_ready; rear=mintime-link; while(rear!=NULL) if (rear!=NULL)&(T=rear-subtime)&(mintime-Rp)Rp) front=mintime; mintime=rear; rear=rear-link; ipmove=1; else rear=rear-link; if (ipmove=1) front-link=mintime-link; mintime-link=jcb_rea

16、dy; jcb_ready=mintime;void input() /* 建立作業(yè)控制塊函數(shù)*/ int i,num; printf(n 請(qǐng)輸入作業(yè)數(shù):); scanf(%d,&num); for(i=0;iname); printf(n 輸入作業(yè)提交時(shí)刻:); scanf(%f,&j-subtime); printf(n 輸入作業(yè)運(yùn)行時(shí)間:); scanf(%f,&j-runtime); printf(n); j-state=w; j-link=NULL; sort(); /* 調(diào)用sort函數(shù)*/ int space() int l=0; JCB* jr=jcb_ready; while

17、(jr!=NULL) l+; jr=jr-link; return(l); void disp(JCB* jr,int select) /*建立作業(yè)顯示函數(shù),用于顯示當(dāng)前作業(yè)*/ if (select=3) printf(n 作業(yè) 服務(wù)時(shí)間 響應(yīng)比 運(yùn)行時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 n); else printf(n 作業(yè) 服務(wù)時(shí)間 運(yùn)行時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 n); printf( |%st,jr-name); printf( |%.2ft ,jr-runtime); if (select=3) printf( |%.2f ,jr-Rp); if (j=jr) pr

18、intf( |%.2ft,jr-wt.Tb); printf( |%.2f ,jr-wt.Tc); printf( |%.2f t,jr-wt.Ti); printf( |%.2f,jr-wt.Wi); printf(n); void destroy() /*建立作業(yè)撤消函數(shù)(作業(yè)運(yùn)行結(jié)束,撤消作業(yè))*/ printf(n 作業(yè) %s 已完成.n,j-name); free(j); void check(int select) /* 建立作業(yè)查看函數(shù) */ JCB* jr; printf(n * 當(dāng)前正在運(yùn)行的作業(yè)是:%s,j-name); /*顯示當(dāng)前運(yùn)行作業(yè)*/ disp(j,select

19、); jr=jcb_ready; printf(n *當(dāng)前就緒隊(duì)列狀態(tài)為:n); /*顯示就緒隊(duì)列狀態(tài)*/ while(jr!=NULL) jr-Rp=(T-jr-subtime)/jr-runtime; disp(jr,select); jr=jr-link; destroy();void running(JCB* jr) /* 建立作業(yè)就緒函數(shù)(作業(yè)運(yùn)行時(shí)間到,置就緒狀態(tài)*/ if (T=jr-subtime) jr-wt.Tb=T; else jr-wt.Tb=jr-subtime; jr-wt.Tc=jr-wt.Tb+jr-runtime; jr-wt.Ti=jr-wt.Tc-jr-s

20、ubtime; jr-wt.Wi=jr-wt.Ti/jr-runtime; T=jr-wt.Tc;void main() /*主函數(shù)*/ int select=0,len,h=0; float sumTi=0,sumWi=0; input(); len=space(); printf(nt1.FCFS 2.SJF 3.HRNnn請(qǐng)選擇作業(yè)調(diào)度算法:?); scanf(%d,&select); while(len!=0)&(jcb_ready!=NULL) h+; printf(n 執(zhí)行第%d個(gè)作業(yè) n,h); j=jcb_ready; jcb_ready=j-link; j-link=NULL

21、; j-state=R; running(j); sumTi+=j-wt.Ti; sumWi+=j-wt.Wi; check(select); if (select=2&hlen-1) SJFget(); if (select=3&hlen-1) HRNget(); printf(n 按任一鍵繼續(xù).n); getchar(); getchar(); printf(nn 作業(yè)已經(jīng)完成.n); printf(t 此組作業(yè)的平均周轉(zhuǎn)時(shí)間：%.2fn,sumTi/h); printf(t 此組作業(yè)的帶權(quán)平均周轉(zhuǎn)時(shí)間：%.2fn,sumWi/h); getchar();總 結(jié)本次課設(shè)主要通過程序模擬實(shí)現(xiàn)批處理多道程序操作系統(tǒng)的作業(yè)調(diào)度。在課設(shè)中遇到的主要問題有：1、由于對(duì)設(shè)計(jì)要求理解的偏差，程序在執(zhí)行過程中，用戶每選擇一個(gè)作業(yè)，就要選擇一次算法，這樣是與實(shí)際情況不符的。通過分析程序，將程序改正過來，即先選擇算法，再進(jìn)行作業(yè)的調(diào)度。2、調(diào)試問題。由于程序比較長(zhǎng)，出現(xiàn)錯(cuò)誤調(diào)試起來很不方便，但通過單步調(diào)試和分析都一一改正過來。在課設(shè)過程中，我對(duì)操作系統(tǒng)有了更進(jìn)一步的認(rèn)識(shí)，尤