操作系統(tǒng)課程設計報告-多道批處理調度的模擬

1、課 程 設 計 課程名稱 操作系統(tǒng) _ 題目名稱 多道批處理調度的模擬學生學院 計算機學院 專業(yè)班級 2007 級計科（5）班 2010年 07月 03日廣東工業(yè)大學課程設計任務書一、課程設計的內容本課程設計要求模擬實現(xiàn)一個的多道批處理系統(tǒng)的兩級調度。通過具體的作業(yè)調度、進程調度、內存分配等功能的實現(xiàn)，加深對多道批處理系統(tǒng)的兩級調度模型和實現(xiàn)過程的理解。 二、課程設計的要求與數(shù)據(jù)1 要求作業(yè)從進入系統(tǒng)到最后完成，要經歷兩級調度：作業(yè)調度和進程調度。作業(yè)調度是高級調度，它的主要功能是根據(jù)一定的算法，從輸入井中選中若干個作業(yè)，分配必要的資源，如主存、外設等，為它們建立初始狀態(tài)為就緒的作業(yè)進程。進程

2、調度是低級調度，它的主要功能是根據(jù)一定的算法將cpu分派給就緒隊列中的一個進程。2 假定某系統(tǒng)可供用戶使用的主存空間共100kb，并有4臺磁帶機。主存分配采用可變分區(qū)分配方式且主存中信息不允許移動，對磁帶機采用靜態(tài)分配策略，作業(yè)調度分別采用先來先服務算法和最小作業(yè)優(yōu)先算法，進程調度采用先來先服務和最短進程優(yōu)先算法。（能增加實現(xiàn)更多的調度算法則可以獲得加分）。3 假定“預輸入”程序已經把一批作業(yè)的信息存放在輸入井了，并為它們建立了相應作業(yè)表。測試數(shù)據(jù)如下：作業(yè) 到達時間 估計運行時間 內存需要 磁帶機需要job1 10：00 25分鐘 15k 2臺job2 10：20 30分鐘 60k 1臺jo

3、b3 10：30 10分鐘 50k 3臺job4 10：35 20分鐘 10k 2臺job5 10：40 15分鐘 30k 2臺4 分別在不同算法控制下運行設計的程序，依次顯示被選中作業(yè)、內存空閑區(qū)和磁帶機的情況。比較不同算法作業(yè)的選中次序及作業(yè)平均周轉時間。5 選用程序設計語言：c、c等。三、課程設計應完成的工作1充分理解設計的任務，完成設計的基本要求。然后根據(jù)自己的基礎和能力選擇不同難度的算法和實現(xiàn)方式，以取得更高的分數(shù)。 2. 獨立完成系統(tǒng)的分析、設計、編碼、測試工作。3完成設計報告的撰寫。4以光盤（以班為單位刻錄）方式提交已調試通過的完整的相關源程序和能夠運行的執(zhí)行文件；提交“課程設計

4、報告”的書面和電子兩種版本。四、課程設計進程安排序號設計各階段內容地點起止日期1查閱資料、分析題目、概要設計分散周一2詳細設計、編碼分散周二3調試實驗室周三4撰寫設計報告分散周四5運行、驗收實驗室周五五、應收集的資料及主要參考文獻1 計算機操作系統(tǒng)， 湯小丹等 ，西安電子科技大學出版社2 操作系統(tǒng)實驗指導書，傅秀芬，廣東工業(yè)大學（自編）3 計算機操作系統(tǒng)教程 ( 第二版 )， 張堯學、 史美林，清華大學出版社4 現(xiàn)代操作系統(tǒng)，a.s.tanenbaum 著，陳向群等譯機械工業(yè)出版社發(fā)出任務書日期：2010年6月27日 指導教師簽名：林穗計劃完成日期： 2010年7月3日 基層教學單位責任人簽章

5、：傅秀芬一 設計背景本次課程設計的目的是模擬實現(xiàn)一個多道批處理系統(tǒng)的兩級調度。在這之前，我們的操作系統(tǒng)課程已經做過了四次實驗，分別是進程調度，作業(yè)調度，主存空間的分配和回收，文件系統(tǒng)。而此次多道批處理系統(tǒng)的兩級調度將在采用前三次實驗（即進程調度，作業(yè)調度，主存空間的分配和回收）成果的基礎上，對他們進行整合，完成一個完整的模擬多道批處理系統(tǒng)兩級調度的系統(tǒng)程序。本課程設計將按要求規(guī)定的步驟進行：設計背景（查詢資料和分析題目），概要設計，詳細設計，編碼，調試和測試，總結和撰寫報告。二 概要設計1.要求作業(yè)從進入系統(tǒng)到最后完成，要經歷兩級調度：作業(yè)調度和進程調度。作業(yè)調度是高級調度，它的主要功能是根據(jù)

6、一定的算法，從輸入井中選中若干個作業(yè)，分配必要的資源，如主存、外設等，為它們建立初始狀態(tài)為就緒的作業(yè)進程。進程調度是低級調度，它的主要功能是根據(jù)一定的算法將cpu分派給就緒隊列中的一個進程。2假定“預輸入”程序已經把一批作業(yè)的信息存放在輸入井了，并為它們建立了相應作業(yè)表。測試數(shù)據(jù)如下：作業(yè) 到達時間 估計運行時間 內存需要 磁帶機需要job1 10：00 25分鐘 15k 2臺job2 10：20 30分鐘 60k 1臺job3 10：30 10分鐘 50k 3臺job4 10：35 20分鐘 10k 2臺job5 10：40 15分鐘 30k 2臺3使用visual c+設計如下各功能界面。

7、放在輸入井的作業(yè)列表：內存分配的情況：已經進入內存并存在的作業(yè)：已經完成的作業(yè)列表：程序設置區(qū)：包括開始時間，磁帶機和內存初始值，調度算法的選擇作業(yè)添加區(qū)，可以輸入作業(yè)及它的各個參數(shù)。程序運行狀態(tài)區(qū)。如開始，暫停，繼續(xù)和重置等個人信息的顯示：三 詳細設計。1 相關數(shù)據(jù)結構的設計。typedef struct job/建立作業(yè)信息結構char jname10; /作業(yè)名int hour; /到達時刻時鐘數(shù)int minute; /到達時刻分鐘數(shù)int run; /運行時間int memory; /要求主存空間int sign; /所要磁帶機數(shù)int fhour; /完成時刻時鐘數(shù)int fmin

8、ute; /完成時刻分鐘數(shù)int enterhour;/進入內存時時刻時鐘數(shù)int enterminute;/進入內存時刻分鐘數(shù)bool done;/記錄是否作業(yè)已完成，完成true，否則falsejob,job;typedef struct jcb/作業(yè)信息結構intnu/記錄作業(yè)位于主存分區(qū)表的分區(qū)號char name10;/作業(yè)名int rtime;/運行時間int memory;/申請主存空間jcb,jcb;typedef struct spart/分區(qū)表信息結構int num;/分區(qū)序號int sadd;/分區(qū)始址int space;/分區(qū)大小char situ10;/分區(qū)狀態(tài)spa

9、rt,spart;typedef struct pcb /* 定義進程控制塊pcb */ char name10; / 進程名 int ntime; / 所需要的運行時間 int stime; /剩余時間pcb,pcb;typedef struct qbnode pcb base; struct qbnode *next;qbnode,*qcb;typedef struct int tip; / 就緒隊列時間片 int num; / 就緒隊列成員數(shù) qcb front; / 隊頭指針 qcb rear; / 隊尾指針 queuejob jwork5=/定義五個作業(yè)joba,10, 0,25,1

10、5,2,0,0,0,0,false,jobb,10,20,30,60,1,0,0,0,0,false,jobc,10,30,10,50,3,0,0,0,0,false,jobd,10,35,20,10,2,0,0,0,0,false,jobe,10,40,15,30,2,0,0,0,0,false;int disk=4;/磁帶機數(shù)5int memory=100;/系統(tǒng)可用主存100kbint hour=9;/系統(tǒng)時間int minute=55;/9:55vector jexe;/主存作業(yè)隊列vector jwait; /后備作業(yè)隊列vector jdone;/完成作業(yè)隊列vector jdis

11、k;/輸入井作業(yè)隊列vectorqjcb;/作業(yè)隊列vectorqproce;/位于主存的作業(yè)隊列vectorqpart;/分區(qū)表狀態(tài)隊列vectorqfree;/空閑分區(qū)表項vectorpronum;/完成作業(yè)的主存分區(qū)號vector:iterator pnext;/記錄空閑分區(qū)表分配主存后下一個空閑位置intsystime = 0;/系統(tǒng)時間，初始化為0intsysmemory = 100;/主存空間100kbintpnadr = -1;/記錄pnext所要指向的分區(qū)始址，-1表示無空閑分區(qū)float progressflag = 0;/進度條標志位status initqueue(que

12、ue &q)/* 構造空隊列q */ q.front=(qcb)malloc(sizeof(qbnode); q.rear=q.front; if(!q.front)return -2;q.num=0;q.tip=0; q.front-next=null; return 1;status enqueue(queue &q,pcb &e)/* 插入元素e為q的新的隊尾元素 */ qcb p; p=(qcb)malloc(sizeof(qbnode); if(!p)return -2; p-base=e; p-next=null; q.rear-next=p;q.rear=p; return 1;

13、status dequeue(queue &q,pcb &e)/* 若隊列非空，則刪除q的隊頭元素，用e返回其值 */ qcb p; if(q.front=q.rear)return 0;/* 空隊列 */ p=q.front-next; e=p-base; q.front-next=p-next; if(q.rear=p)q.rear=q.front; p-next=null; free(p); return 1;status emptyqueue(queue &q)/判斷q是否為空隊列，是返回1,否返回0if(q.front-next=null)return 1;elsereturn 0;

14、queue al;/進程隊列2主存空間分配和回收的設計：循環(huán)首次適應法。使用鏈指針把所有的空閑分區(qū)鏈成一條鏈，為了實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的起始部分設置狀態(tài)位、分區(qū)的大小和鏈接各個分區(qū)的前向指針，由狀態(tài)位指示該分區(qū)是否分配出去了；同時，在分區(qū)尾部還設置有一后向指針，用來鏈接后面一個分區(qū)；分區(qū)的中間部分是用來存放作業(yè)的空閑內存空間，當該分區(qū)分配出去后，狀態(tài)位改變。設計一個內存空閑分鏈，內存空閑分區(qū)通過空閑分區(qū)鏈來管理，在進行內存分配時系統(tǒng)統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。設計一個空閑分區(qū)說明鏈，設計一個某時刻主存空間占用情況表，作為主存當前使用基礎。初始化空閑區(qū)和已分配區(qū)說明表的值。設計

15、作業(yè)申請隊列以及作業(yè)完成后的釋放順序，實現(xiàn)主存的分配和回收。當一個作業(yè)執(zhí)行完成撤離時，作業(yè)所占的分區(qū)應該歸還給系統(tǒng)。歸還的分區(qū)如果與其它空閑區(qū)相鄰，則應合成一個較大的空閑區(qū)，登記在空閑區(qū)說明表中。此時，相鄰空閑區(qū)的合并問題，要求考慮四種情況：1）、釋放區(qū)下鄰空閑區(qū)（低地址鄰接）2）、釋放區(qū)上鄰空閑區(qū)（高地址鄰接）3）、釋放區(qū)上下都與空閑區(qū)鄰接4）、釋放區(qū)上下都與空閑區(qū)不鄰接3作業(yè)調度算法：先來先服務和短作業(yè)優(yōu)先。（1）先來先服務算法：是按照作業(yè)進入輸入井的先后次序來挑選作業(yè)，先進入輸入井的作業(yè)優(yōu)先被挑選，當系統(tǒng)中現(xiàn)有的尚未分配的資源不能滿足先進入輸入井的作業(yè)時，那么順序挑選后面的作業(yè)。（2）短

16、作業(yè)優(yōu)先算法：總是按作業(yè)要求運行的時間來選擇作業(yè)，每次挑選要求運行時間短且資源要求能滿足的作業(yè)先進入主存執(zhí)行。（3）程序流程圖（僅以先來先服務調度算法說明過程）4進程調度算法：短進程優(yōu)先和先來先服務。（1）先來先服務算法：是按照作業(yè)進入內存的先后次序來創(chuàng)建進程，先進入內存的作業(yè)優(yōu)先被挑選，只要cpu一空閑，立即分配給隊首的進程，讓它擁有處理機資源，運行。（2）短進程優(yōu)先算法：總是按進程要求運行的時間來選擇進程，每次挑選要求運行時間最短進程先分配cpu執(zhí)行。（3）程序流程圖（僅以先來先服務調度算法說明過程）四編碼。相應算法的實現(xiàn)（其中的重點部分）：void pclock(int &hour,in

17、t &minute)/時鐘函數(shù)+minute;if(minute59)minute=0;+hour;if(hour23)hour=0;void calt(job &job,int hour,int minute) /計算完成時刻job.fminute=minute;job.fhour=hour;void pfcfsinput(queue &al1,vector &q)/* 建立先來先服務進程隊列模塊函數(shù) */if(al1.num != q.size()/此時有新作業(yè)進入內存，則為它建立進程pcb p;while(al1.num q.size()strcpy(,qal1.num.jn

18、ame);p.ntime = qal1.num.run;enqueue(al1,p);al1.num +;void psjfinput(queue &al1,vector &q) /建立短進程優(yōu)先進程隊列模塊if(al1.num != q.size()pcb p;qcb ip1,ip2;int id = al1.num;while(al1.num next;/指向隊列的首元素while(ip2 != null)if(p.ntime base.ntime)/新進程比正在運行的進程還要短break;ip1 = ip2;ip2 = ip1-next;pi-base = p;/插入進程pi-next

19、= ip2;ip1-next = pi;al1.num +;while(al1.rear-next != null)/派完序注意要更新隊尾指針al1.rear = al1.rear-next;vector:iterator ip;for(ip = q.begin();ip != q.end();+ip)if(ip-jname = qid.jname)break;vector jev(ip,q.end();/記錄將要被刪除作業(yè)q.erase(ip,q.end();/把這部分刪除，以便從新排序for(id = 0;id jev.size();+id)/插入排序ip = q.begin();whil

20、e(ip != q.end()if(jevid.run run)break;else+ip;q.insert(ip,jevid);void prun(queue &al1)/進程隊列運行模塊pclock(hour,minute); if(emptyqueue(al1) = 0)/進程隊列非空，則執(zhí)行al1.front-next-base.ntime -;/進程隊列首元素正在執(zhí)行if(al1.front-next-base.ntime next-base.ntime = 0;int sub = jexe0.run - al1.front-next-base.ntime; progressflag

21、 = (float)(sub)/(float)(jexe0.run);if(al1.front-next-base.ntime = 0)/進程已完成要撤銷該進程pcb e;jexe0.done = true;dequeue(al1,e);al1.num -;vector:iterator itor = qproce.begin();while(itor != qproce.end()if(strcmp(itor-name,) = 0)itor-rtime = 0; break;else+itor;void insert(vector &q)/插入作業(yè)處理模塊vector:itera

22、tor itor = pnext;sysmemory -= q0.memory;/分配主存空間if(q0.memory = itor-space)/空閑分區(qū)大小恰好等于作業(yè)大小strcpy(qpartitor-num.situ,q0.name);/將作業(yè)裝入內存相應分區(qū)中jcb job = q0;q.erase(q.begin();/刪除已裝進主存的作業(yè)隊列的作業(yè)job.num = pnext-num;/新作業(yè)的分區(qū)號int sub = qpart.size() - 1;if(pnext-num = sub)/新作業(yè)恰好位于末尾分區(qū)qproce.push_back(job);/新作業(yè)插入主存作

23、業(yè)隊列末尾elsevector:iterator jp;int id;id = pnext-num + 1;jp = qproce.begin();while(jp-num != id) /找到要插入新作業(yè)的位置+jp;qproce.insert(jp,job);+itor;if(itor = qfree.end()/指向原空閑分區(qū)表的最后一個元素qfree.erase(pnext);/刪除已分配的空閑分區(qū)項pnext = qfree.begin();/pnext指向qfree首元素elsevector:iterator reg ;/記錄要刪除項的下一項reg = qfree.erase(pn

24、ext);/刪除已分配的空閑分區(qū)項pnext = reg;/令pnext指向下一個空閑分區(qū)else/空閑分區(qū)大小大于作業(yè)申請空間大小spart part;/分割后位于分區(qū)表的空閑分區(qū)part.num = pnext-num + 1;part.sadd = pnext-sadd + q0.memory;part.space = pnext-space - q0.memory;strcpy(part.situ,pnext-situ);jcb job = q0;job.num = pnext-num;int sub = qpart.size() - 1;if(pnext-num = sub)/新作業(yè)

25、裝入原分區(qū)的最后的空閑分區(qū)qproce.push_back(job);elsevector:iterator jp;int id;jp = qproce.begin();id = pnext-num + 1;while(jp-num != id)/記錄作業(yè)分區(qū)號需要改變的首位置+jp;vector:iterator ip;ip = jp;while(ip != qproce.end()/改變新作業(yè)之后作業(yè)的分區(qū)序號+(ip-num);+ip;qproce.insert(jp,job);/插入新作業(yè)vector:iterator spt;vector:iterator reg;spt = qpa

26、rt.begin();while(spt-sadd !=qpartpnext-num.sadd)/記錄分區(qū)表插入qpart所需要的位置+spt;qpartpnext-num.space = q0.memory;strcpy(qpartpnext-num.situ,q0.name);/把作業(yè)裝進主存相應分區(qū)下+spt;reg = spt;while(reg != qpart.end()/更改其下的分區(qū)號+(reg-num);+reg;qpart.insert(spt,part);/插入part，分區(qū)表相應項序號已更改(*pnext) = part;/分割后的空閑分區(qū)項+itor;while(it

27、or != qfree.end()/更改其下的空閑分區(qū)號+(itor-num);+itor;q.erase(q.begin();/刪除已裝進主存的作業(yè)隊列的作業(yè)if(pnext != qfree.end()/空閑分區(qū)表非空pnadr = pnext-sadd;/賦pnext所指空閑分區(qū)的分區(qū)始址elsepnadr = -1;int disproce(vector &q)/主存分配處理模塊if(qfree.empty()/無空閑空間分配q.erase(q.begin();/直接刪除首元素return 0;elseif(q0.memory space)/空閑分區(qū)足夠裝入作業(yè)insert(q);re

28、turn 1;else/搜索其它空閑分區(qū)if(qfree.size() 1)vector:iterator itor;itor = pnext;+itor;while(itor != pnext)if(itor = qfree.end()itor = qfree.begin();if(q0.memory space)/z找到合適的分區(qū)break/跳出while循環(huán)，停止搜索+itor;if(q0.memory space)pnext = itor;insert(q);return 1;q.erase(q.begin();/直接刪除首元素return 0;void jsjfpro(vector

29、&m) /短作業(yè)優(yōu)先作業(yè)調度vector:iterator itor;vector:iterator reg;itor = jdisk.begin();while(itor != jdisk.end()/輸入井作業(yè)if(itor-hour minute = minute) /當有作業(yè)在特定時刻申請進入主存jwait.push_back(*itor);/將作業(yè)插入就緒隊列reg = jdisk.erase(itor);itor = reg;else+itor;if(!jwait.empty()/后備隊列非空，按短作業(yè)排序vector jev(jwait);jwait.clear();vector

30、:iterator ip;for(vector:size_type id = 0;id jev.size();+id)ip = jwait.begin();while(ip != jwait.end()if(jevid.run run )break;else+ip;jwait.insert(ip,jevid);m.clear();int i = 0;jcb m;ip = jwait.begin();while(ip != jwait.end()m.memory = ip-memory;m.rtime = ip-run;strcpy(,ip-jname);m.push_back(m)

31、;+i;+ip;/就緒隊列作業(yè)，存放已到達而因資源不足而阻塞的作業(yè)itor=jwait.begin();while(itor!=jwait.end()if(disk=itor-sign) /當主存空間磁帶機足夠用時if(disproce(m) = 1)job job=*itor; /復制作業(yè)信息job.enterhour = hour;/進入主存時鐘數(shù)job.enterminute = minute;/進入主存分鐘數(shù)memory-=itor-memory; /分配主存空間disk-=itor-sign;/分配磁帶機reg=jwait.erase(itor); /刪除就緒隊列將要插入主存的作業(yè)j

32、exe.push_back(job); /將job插入主存隊列尾itor=reg;/指向被刪除作業(yè)的下一個位置else+ itor;/往主存隊列添加作業(yè)直至主存空間不足或者就緒作業(yè)隊列為空else+itor;m.erase(m.begin();void jfcfspro(vector &m)/先來先服務作業(yè)調度vector:iterator itor;vector:iterator reg;itor = jdisk.begin();while(itor != jdisk.end()/輸入井作業(yè)if(itor-hour minute = minute) /當有作業(yè)在特定時刻申請進入主存jwait

33、.push_back(*itor);/將作業(yè)插入就緒隊列reg = jdisk.erase(itor);itor = reg;else+itor;if(!jwait.empty()m.clear();int i = 0;jcb m;vector:iterator ip;ip = jwait.begin();while(ip != jwait.end()m.memory = ip-memory;m.rtime = ip-run; strcpy(,ip-jname);m.push_back(m);+i;+ip; /就緒隊列作業(yè)，存放已到達而因資源不足而阻塞的作業(yè)itor=jwait.b

34、egin();while(itor!=jwait.end()if(disk = itor-sign) /當主存空間磁帶機足夠用時if(disproce(m) = 1)job job= *itor; /復制作業(yè)信息job.enterhour = hour;/進入主存時鐘數(shù)job.enterminute = minute;/進入主存分鐘數(shù)memory-=itor-memory; /分配主存空間disk-=itor-sign;/分配磁帶機reg=jwait.erase(itor); /刪除就緒隊列將要插入主存的作業(yè)jexe.push_back(job); /將job插入主存隊列尾itor=reg;/

35、指向被刪除作業(yè)的下一個位置else+ itor;/往主存隊列添加作業(yè)直至主存空間不足或者就緒作業(yè)隊列為空else+itor;m.erase(m.begin();void jfinjob()/完成作業(yè)處理模塊if(!jexe.empty()/主存作業(yè)非空if(jexe0.done = true) /如果作業(yè)已完成 job work=*jexe.begin();/作業(yè)完成，要將其插入到完成作業(yè)隊列calt(work,hour,minute);memory+=jexe.begin()-memory; /釋放占用的主存空間disk+=jexe.begin()-sign;/釋放磁帶機jexe.erase

36、(jexe.begin(); /刪除主存模塊的首作業(yè)jdone.push_back(work);/添加到完成隊列void recproce()/作業(yè)釋放處理模塊for(vector:size_type i = 0;i pronum.size();+i)sysmemory += qpartpronumi.space;/釋放主存strcpy(qpartpronumi.situ,空閑內存);/釋放已完成的作業(yè)pronum.clear();vector:iterator del;vector:iterator it;del = qpart.begin();+del;/主存隊列首分區(qū)分配已給系統(tǒng)whil

37、e(del != qpart.end()/更新分區(qū)表qpartif(strcmp(del-situ,空閑內存) = 0)/指定分區(qū)為空閑分區(qū)it = del;+it;if(it != qpart.end()if(strcmp(it-situ,空閑內存) = 0)/del的下一分區(qū)也空閑/合并del和it指向的分區(qū)int adr1,adr2;adr1 = del-sadd;adr2 = it-sadd;it-num = del-num;it-sadd = del-sadd;it-space += del-space;it = qpart.erase(del);/合并分區(qū)，刪除無用分區(qū)if(pna

38、dr != -1)if(pnadr = adr1)|(pnadr = adr2) /pnext記錄的內容恰好指向原分區(qū)表的del和it位置pnadr = it-sadd;/記錄pnext所要指向it所指位置的始址，以便更新qfree表elsepnadr = it-sadd;elseif(pnadr = -1)/原空閑分區(qū)表為空pnadr = del-sadd;/令pnext指向分區(qū)表的第一個空閑分區(qū)位置，便于更新qfreedel = it;else/指向的分區(qū)為作業(yè)分區(qū)，則跳過+del;void memfreeproce()/主存釋放處理模塊vectorpreg;/記錄主存作業(yè)隊列中未完成的作業(yè)隊列for(vector:size_type i = 0;i qproce.size();+i)if(qprocei.rtime = 0)/說明作業(yè)已完成pronum.push_back(qprocei.num);/記錄要釋放的主存分區(qū)號elsepreg.push_back(qprocei);qproce.clear();qproce = preg;if(!pronum.empty()/有作業(yè)要釋放recproc