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

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

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

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

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

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

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

7、序#include "string.h"#define n 10/假定系統(tǒng)中可容納的作業(yè)數量為n typedef struct jcb char name4;/作業(yè)名 int length;/作業(yè)長度，所需主存大小 int printer;/作業(yè)執(zhí)行所需打印機的數量 int tape;/作業(yè)執(zhí)行所需磁帶機的數量 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)內現有作業(yè)數量 shedule( ) /作業(yè)調度函數 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è)p的響應比 k=xk;/記錄響應比 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è)調度函數結束main( ) char name4; int size,tcount,pcount,wtime,rtime; int p; /系統(tǒng)數據初始化 memory=65536; tape=4; printer=2; head=-1; printf("輸入作業(yè)相關數據(以作業(yè)大小為負數停止輸入)：n"); /輸入數據，建立作業(yè)隊列 printf("輸入作業(yè)名、作業(yè)大小、磁帶機數、打印

11、機數、等待時間、估計執(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è)相關內容 strcpy(,name); jobtablep.length=size; jobtablep.printer=pcount; jobtablep.tape=tcount; jobtablep.runtime=rtime; jobtablep.waittime=wtime; /掛入作業(yè)隊列隊首 jobtablep.next=head; head=p; / 輸入一個作業(yè)數據 printf