實驗1批處理作業(yè)調(diào)度

1、批處理系統(tǒng)的作業(yè)調(diào)度1實驗?zāi)康募由顚ψ鳂I(yè)概念的理解；深入了解批處理系統(tǒng)如何組織作業(yè)、管理作業(yè)和調(diào)度作業(yè)；2實驗預(yù)備知識作業(yè)的概念；作業(yè)的創(chuàng)建；作業(yè)的調(diào)度。3實驗內(nèi)容編寫程序完成批處理系統(tǒng)中的作業(yè)調(diào)度，要求采用響應(yīng)比高者優(yōu)先的作業(yè)調(diào)度算法。實驗具體包括：首先確定作業(yè)控制塊的內(nèi)容，作業(yè)控制塊的組成方式；然后完成作業(yè)調(diào)度；最后編寫主函數(shù)對所作工作進程測試。4提示與講解操作系統(tǒng)根據(jù)允許并行工作的道數(shù)和一定的算法從系統(tǒng)中選取若干作業(yè)把它們裝入主存儲器，使它們有機會獲得處理器運行，這項工作被稱為“作業(yè)調(diào)度”。實現(xiàn)這部分功能的程序就是“作業(yè)調(diào)度程序”。作業(yè)調(diào)度的實現(xiàn)主要有兩個問題，一個是如何將系統(tǒng)中的作業(yè)組

2、織起來；另一個是如何進行作業(yè)調(diào)度。為了將系統(tǒng)中的作業(yè)組織起來，需要為每個進入系統(tǒng)的作業(yè)建立檔案以記錄和作業(yè)相關(guān)的信息，例如作業(yè)名、作業(yè)所需資源、作業(yè)執(zhí)行時間、作業(yè)進入系統(tǒng)的時間、作業(yè)信息在存儲器中的位置、指向下一個作業(yè)控制塊的指針等信息。這個記錄作業(yè)相關(guān)信息的數(shù)據(jù)塊稱為作業(yè)控制塊（JCB），并將系統(tǒng)中等待作業(yè)調(diào)度的作業(yè)控制塊組織成一個隊列，這個隊列稱為后備隊列。一個作業(yè)全部信息進入系統(tǒng)后，就為其建立作業(yè)控制塊，并掛入后備隊列。當(dāng)進行作業(yè)調(diào)度時，從后備隊列中查找選擇作業(yè)。由于實驗中沒有實際作業(yè)，作業(yè)控制塊中的信息內(nèi)容只使用了實驗中需要的數(shù)據(jù)。作業(yè)控制塊中首先應(yīng)該包括作業(yè)名；其次是作業(yè)所需資源，根

3、據(jù)需要，實驗中只包括需要主存的大小（采用可移動的動態(tài)分區(qū)方式管理主存，作業(yè)大小就是需要主存的大?。?、需要打印機的數(shù)量和需要磁帶機的數(shù)量；采用響應(yīng)比作業(yè)調(diào)度算法，為了計算響應(yīng)比，還需要有作業(yè)的估計執(zhí)行時間、作業(yè)在系統(tǒng)中的等待時間；另外，指向下一個作業(yè)控制塊的指針必不可少。實驗中，作業(yè)控制塊及隊列的數(shù)據(jù)結(jié)構(gòu)定義如下。typedef struct jcbchar name4; /作業(yè)名 int length; /作業(yè)長度，所需主存大小 int printer; /作業(yè)執(zhí)行所需打印機的數(shù)量 int tape; /作業(yè)執(zhí)行所需磁帶機的數(shù)量 int runtime; /作業(yè)估計執(zhí)行時間 int waitt

4、ime;/作業(yè)在系統(tǒng)中的等待時間 int next;/指向下一個作業(yè)控制塊的指針JCB /作業(yè)控制塊類型定義存放作業(yè)控制塊的區(qū)域：#define n 10/假定系統(tǒng)中可容納的作業(yè)數(shù)量為nJCB jobtable10;/作業(yè)表int jobcount;/系統(tǒng)內(nèi)現(xiàn)有作業(yè)數(shù)量將作業(yè)控制塊組織成一個隊列，實驗中采用靜態(tài)鏈表的方式模擬作業(yè)的后備隊列，如圖2.1所示。作業(yè)隊列頭指針定義： int *head;圖2.1 采用響應(yīng)比高者優(yōu)先算法的作業(yè)調(diào)度程序的流程圖確定作業(yè)組織方式之后，就要開始考慮如何進行作業(yè)調(diào)度。盡管不同的計算機系統(tǒng)可以采用不同的調(diào)度原則和調(diào)度算法，但是都必須遵循一個必要條件，即系統(tǒng)現(xiàn)有的

5、尚未分配的資源可以滿足被選作業(yè)的資源要求。就是說，所有的作業(yè)調(diào)度都是按照一定的算法，從滿足必要條件的作業(yè)中選擇一部分作業(yè)裝入主存儲器。實驗中，主存采用可移動的動態(tài)分區(qū)管理方法，即只要主存空閑區(qū)總和比作業(yè)大就可以滿足作業(yè)對主存的需求；對打印機和磁帶機這兩種獨占型設(shè)備采用靜態(tài)分配法，即作業(yè)執(zhí)行前必須獲得所需資源，并且執(zhí)行完才歸還。常用的作業(yè)調(diào)度算法有先來先服務(wù)算法、計算時間短的作業(yè)優(yōu)先算法、響應(yīng)比高者優(yōu)先算法、優(yōu)先數(shù)調(diào)度算法和均衡調(diào)度算法。實驗中采用響應(yīng)比高者優(yōu)先算法，響應(yīng)比的定義為：響應(yīng)比=作業(yè)的等待時間/作業(yè)估計執(zhí)行時間采用響應(yīng)比高者優(yōu)先調(diào)度算法，進行調(diào)度時必須計算出系統(tǒng)中的所有滿足必要條件作

6、業(yè)的響應(yīng)比；從中選擇響應(yīng)比最高的一個作業(yè)裝入主存儲器、分配資源，由于是實驗，所以就用將作業(yè)的作業(yè)控制塊出隊，并輸出作業(yè)的作業(yè)名代替裝入主存儲器，同時修改系統(tǒng)的資源數(shù)量；用同樣方法選擇第二個、第三個直到不再有滿足必要條件的作業(yè)。采用響應(yīng)比高者優(yōu)先算法的作業(yè)調(diào)度程序流程圖如圖2.1所示。模擬程序中，首先要假設(shè)系統(tǒng)的資源情況，假設(shè)系統(tǒng)資源只有主存（memory）64MB(以KB為單位分配)、磁帶機（tape）4臺和打印機（printer）2臺；然后，手工輸入某個時刻系統(tǒng)中的各個作業(yè)情況；最后進行作業(yè)調(diào)度，并將結(jié)果輸出。5課外題將上述實驗中的作業(yè)調(diào)度算法改為短作業(yè)優(yōu)先調(diào)度算法重新完成上述工作。6參考程

7、序#include "string.h"#define n 10/假定系統(tǒng)中可容納的作業(yè)數(shù)量為n typedef struct jcb char name4;/作業(yè)名 int length;/作業(yè)長度，所需主存大小 int printer;/作業(yè)執(zhí)行所需打印機的數(shù)量 int tape;/作業(yè)執(zhí)行所需磁帶機的數(shù)量 int runtime;/作業(yè)估計執(zhí)行時間 int waittime;/作業(yè)在系統(tǒng)中的等待時間 int next;/指向下一個作業(yè)控制塊的指針 JCB;/作業(yè)控制塊類型定義 int head; /作業(yè)隊列頭指針定義 int tape,printer; long me

8、mory; JCB jobtablen;/作業(yè)表 int jobcount=0;/系統(tǒng)內(nèi)現(xiàn)有作業(yè)數(shù)量 shedule( ) /作業(yè)調(diào)度函數(shù) float xk,k; int p,q,s,t; do p=head; q=s=-1; k=0; while(p!=-1) if(jobtablep.length<=memory&&jobtablep.tape<=tape&&jobtablep.printer<=printer) /系統(tǒng)可用資源是否滿足作業(yè)需求 xk=(float)(jobtablep.waittime)/jobtablep.runtime

9、; if(q=0|xk>k)/滿足條件的第一個作業(yè)或者作業(yè)q的響應(yīng)比小于作業(yè)p的響應(yīng)比 k=xk;/記錄響應(yīng)比 q=p; t=s; /if /if s=p; p=jobtablep.next;/指針p后移 /while if(q!=-1) if(t=-1)/是作業(yè)隊列的第一個 head=jobtablehead.next; else jobtablet.next=jobtableq.next; /為作業(yè)q分配資源：分配主存空間；分配磁帶機;分配打印機 memory=memory-jobtableq.length; tape=tape-jobtableq.tape; printer=pri

10、nter-jobtableq.printer; printf("選中作業(yè)的作業(yè)名：%sn",); while(q!=-1); /作業(yè)調(diào)度函數(shù)結(jié)束main( ) char name4; int size,tcount,pcount,wtime,rtime; int p; /系統(tǒng)數(shù)據(jù)初始化 memory=65536; tape=4; printer=2; head=-1; printf("輸入作業(yè)相關(guān)數(shù)據(jù)(以作業(yè)大小為負(fù)數(shù)停止輸入)：n"); /輸入數(shù)據(jù)，建立作業(yè)隊列 printf("輸入作業(yè)名、作業(yè)大小、磁帶機數(shù)、打印

11、機數(shù)、等待時間、估計執(zhí)行時間n"); scanf("%s%d%d %d %d %d",name,&size,&tcount,&pcount,&wtime,&rtime); while(size!=-1) /創(chuàng)建JCB if(jobcount<n)p=jobcount; else printf("無法再創(chuàng)建作業(yè)n"); break; jobcount+; /填寫該作業(yè)相關(guān)內(nèi)容 strcpy(,name); jobtablep.length=size; jobtablep.printer=pcount; jobtablep.tape=tcount; jobtablep.runtime=rtime; jobtablep.waittime=wtime; /掛入作業(yè)隊列隊首 jobtablep.next=head; head=p; / 輸入一個作業(yè)數(shù)據(jù) printf