1、<p><b>　　操作系統(tǒng)課程設(shè)計</b></p><p>　　--進程調(diào)度子系統(tǒng)模擬實現(xiàn)</p><p><b>　　設(shè)計內(nèi)容及意義</b></p><p><b>　　課程設(shè)計內(nèi)容</b></p><p>　　使用java語言或C++語言編程實現(xiàn)模擬操作系統(tǒng)進程

2、調(diào)度子系統(tǒng)的基本功能；實現(xiàn)先來先服務(wù)、時間片輪轉(zhuǎn)、多級反饋輪轉(zhuǎn)法對進程進行的調(diào)度過程；掌握各個調(diào)度算法的特點。</p><p><b>　　該課程設(shè)計意義</b></p><p><b>　　理解進程調(diào)度的概念</b></p><p>　　深入了解進程控制塊的功能、進程的創(chuàng)建、刪除以及進程各個狀態(tài)間的轉(zhuǎn)換過程</p&

3、gt;<p>　　從實用的角度對《數(shù)據(jù)結(jié)構(gòu)》課程內(nèi)容進行更深入理解和更熟練的應用</p><p>　　進一步練習對Java及C++語言的熟練使用</p><p><b>　　設(shè)計方案</b></p><p><b>　　硬件環(huán)境</b></p><p><b>　　PC一臺&

4、lt;/b></p><p><b>　　開發(fā)語言及工具</b></p><p>　　操作系統(tǒng)：MS windows XP</p><p>　　C++版：Visual Studio 2008 + MFC</p><p>　　Java版：Eclipse 3.4 + Java Swing</p><

5、p><b>　　設(shè)計思路</b></p><p>　　系統(tǒng)設(shè)備表用于存取調(diào)度過程中進程可申請的資源</p><p>　　進程控制塊主要負責具體進程信息的保存</p><p>　　等待隊列、就緒隊列、完成隊列用于保存執(zhí)行過程的狀態(tài)信息</p><p>　　進程調(diào)度進程（類、線程）在就緒隊列與等待隊列之間進行調(diào)度<

6、;/p><p>　　主界面顯示調(diào)度過程的三個隊列的狀態(tài)信息</p><p>　　用戶創(chuàng)建進程放入就緒隊列等待調(diào)度</p><p><b>　　功能模塊設(shè)計</b></p><p><b>　　進程狀態(tài)轉(zhuǎn)換</b></p><p><b>　　PCB信息</b>

7、;</p><p>　　主要負責保存各進程基本信息</p><p>　　提供外部狀態(tài)設(shè)置和讀取接口</p><p><b>　　系統(tǒng)設(shè)備類</b></p><p><b>　　系統(tǒng)設(shè)備的基本信息</b></p><p>　　設(shè)備狀態(tài)設(shè)置、讀取接口</p><

8、;p><b>　　調(diào)度類</b></p><p>　　向就緒隊列添加新創(chuàng)建進程</p><p>　　從就緒隊列取相應進程執(zhí)行</p><p>　　將執(zhí)行阻塞進程放入等待隊列</p><p>　　檢測系統(tǒng)設(shè)備表，分配、釋放設(shè)備、喚醒等待進程</p><p>　　執(zhí)行完成程序放入完成隊列（僅為保

9、存狀態(tài)，非系統(tǒng)部分）</p><p>　　提供獲取執(zhí)行狀態(tài)的外部接口，即各個隊列數(shù)據(jù)的獲取</p><p><b>　　視圖類</b></p><p>　　提供用戶操作接口（調(diào)度策略選擇、進程創(chuàng)建）</p><p><b>　　顯示各隊列狀態(tài)信息</b></p><p>　　

10、創(chuàng)建進程調(diào)度類線程，調(diào)用調(diào)度類的接口</p><p><b>　　程序總控流程圖</b></p><p>　　用戶接口、調(diào)度算法、進程狀態(tài)轉(zhuǎn)換關(guān)系示意</p><p>　　調(diào)度算法基本工作流程示意</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)設(shè)計</b></p><p>　　PCB（

11、進程基本信息）</p><p><b>　　類結(jié)構(gòu)</b></p><p><b>　　說明</b></p><p><b>　　pid進程ID</b></p><p><b>　　pName進程名</b></p><p>　　us

12、erName進程用戶</p><p>　　priority進程優(yōu)先級</p><p>　　subtime進程提交時間</p><p>　　totalTime進程需要執(zhí)行的總時間</p><p>　　runtime進程已經(jīng)運行時間</p><p>　　dcReqlst當前進程所需要的設(shè)備請求表</p>&l

13、t;p>　　Dispatcher（進程調(diào)度進程）</p><p><b>　　類結(jié)構(gòu)</b></p><p><b>　　說明</b></p><p>　　sysTime系統(tǒng)時間</p><p>　　isContention當前調(diào)度是否為搶占方式</p><p>　　p

14、relst就緒隊列</p><p>　　waitlst等待隊列</p><p>　　finishlst完成隊列</p><p>　　executing正在執(zhí)行的進程</p><p>　　sysDclst系統(tǒng)設(shè)備表</p><p>　　Device（系統(tǒng)設(shè)備）</p><p><b>　

15、　類結(jié)構(gòu)</b></p><p><b>　　說明</b></p><p><b>　　dcid設(shè)備標識</b></p><p>　　dcType設(shè)備類型</p><p>　　dcTime該設(shè)備一次I/O服務(wù)需要時間</p><p>　　dcPid使用該設(shè)備的進程

16、</p><p>　　dcDisc設(shè)備描述</p><p>　　dcLefTime設(shè)備剩余服務(wù)時間</p><p><b>　　程序代碼結(jié)構(gòu)</b></p><p><b>　　類層次關(guān)系</b></p><p><b>　　詳細說明</b></p

17、><p>　　Dispatcher定義進程調(diào)度進程的基本信息和接口</p><p>　　FIFODispatcher、PLevelDispatcher、RRDispatcher、MRDispatcher分別實現(xiàn)相應的調(diào)度算法</p><p>　　Device為系統(tǒng)設(shè)備</p><p>　　DeviceReq為進程設(shè)備請求，包括請求設(shè)備ID和時間&

18、lt;/p><p><b>　　代碼實現(xiàn)分析</b></p><p>　　算法分析（各算法過程見下流程圖）</p><p><b>　　設(shè)備的分配釋放</b></p><p><b>　　先來先服務(wù)</b></p><p><b>　　優(yōu)先級調(diào)度&

19、lt;/b></p><p><b>　　時間片輪轉(zhuǎn)</b></p><p><b>　　多級反饋輪轉(zhuǎn)</b></p><p>　　具體實現(xiàn)（代碼部分有詳細注釋）</p><p><b>　　進程的插入</b></p><p><b>　

20、　@Override</b></p><p>　　public void addPreProc(Process proc) {</p><p>　　//按優(yōu)先級加到就緒隊列</p><p>　　this.prelst.add(proc); </p><p><b>　　int loc;</b></p&g

21、t;<p>　　for(loc=prelst.size()-2; loc>=0; loc--){</p><p>　　//比proc大的元素后移一個位置</p><p>　　Process temp = prelst.get(loc);</p><p>　　if(proc.Priority<temp.Priority){</p>

22、<p>　　prelst.set( loc+1, temp);</p><p><b>　　}</b></p><p>　　else{//將proc放入空閑位置</p><p>　　prelst.set( loc+1, proc);</p><p><b>　　break;</b>

23、</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(loc<0){</p><p>　　prelst.set(0, proc);</p><p><b>　　}</b></p>

24、<p><b>　　}</b></p><p><b>　　取出進程</b></p><p><b>　　@Override</b></p><p>　　public Process delPreProc() {</p><p>　　//取優(yōu)先級最高者，即為第一個&l

25、t;/p><p>　　if(prelst.size()<=0){</p><p>　　return null;</p><p><b>　　}</b></p><p>　　return this.prelst.remove(0);//返回最小一個</p><p><b>　　}&l

26、t;/b></p><p><b>　　先進先出算法的調(diào)度</b></p><p><b>　　@Override</b></p><p>　　public void run(int time) {</p><p>　　int proctimeslice = 1;//假設(shè)處理器指令周期為1個

27、時鐘周期</p><p>　　while(time>0){//處理機運行time時間</p><p>　　if(this.executing==null){//沒有進程占用處理機則空轉(zhuǎn)</p><p>　　this.executing = this.delPreProc();</p><p><b>　　}</b

28、></p><p>　　else{//執(zhí)行當前進程</p><p>　　Process proc = this.executing;</p><p>　　//下一次執(zhí)行需要的設(shè)備</p><p>　　DcRequest req = proc.getNextReq();</p><p>　　if(req!

29、=null && req.getReqtime()<=proc.runtime){</p><p>　　//進程需要請求設(shè)備，而且執(zhí)行到請求時間</p><p>　　this.addWaitProc(proc);</p><p>　　this.executing = this.delPreProc();</p><p>

30、;　　}else{//無資源請求</p><p>　　proc.run(proctimeslice);</p><p>　　if(proc.isFinished()){</p><p>　　//當前進程是已完成進程，放入完成隊列,取下一進程</p><p>　　proc.setFinishTime(</p><p>

31、　　Dispatcher.getBeginTime()</p><p>　　+ Dispatcher.getRunTime());</p><p>　　//設(shè)置當前執(zhí)行結(jié)束時間</p><p>　　this.addFinishProc(proc);</p><p>　　this.executing = this.delPreProc();&

32、lt;/p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　super.processWaitlst(proctimeslice);</p><p>　　++Dispatch

33、er.runTime;</p><p><b>　　--time;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　優(yōu)先級搶占算法的調(diào)度</p><p><b>　　@Override

34、</b></p><p>　　public void run(int time, boolean isContention) {</p><p>　　if(!isContention){//非搶占方式</p><p>　　this.run(time);</p><p><b>　　return;</b>&

35、lt;/p><p><b>　　}</b></p><p>　　int proctimeslice = 1;//假設(shè)處理器時鐘周期</p><p>　　while(time>0){//處理機運行time時間</p><p>　　if(this.executing==null){//沒有進程占用處理機則空轉(zhuǎn)&l

36、t;/p><p>　　this.executing = this.delPreProc();</p><p><b>　　}</b></p><p>　　else{//執(zhí)行當前進程</p><p>　　Process proc = this.executing;</p><p>　　//下一

37、次執(zhí)行需要的設(shè)備</p><p>　　DcRequest req = proc.getNextReq();</p><p>　　if(req!=null && req.getReqtime()<=proc.runtime){</p><p>　　//進程需要請求設(shè)備，而且執(zhí)行到請求時間</p><p>　　//放入等待

38、隊列,取下一進程</p><p>　　this.addWaitProc(proc);</p><p>　　this.executing = this.delPreProc();</p><p>　　}else{//無資源請求</p><p>　　proc.run(proctimeslice);</p><p>　　i

39、f(proc.isFinished()){</p><p>　　//當前進程是已完成進程，放入完成隊列,取下一進程</p><p>　　proc.setFinishTime(//設(shè)置當前執(zhí)行結(jié)束時間</p><p>　　Dispatcher.getBeginTime()+</p><p>　　Dispatcher.getRunTime());

40、</p><p>　　this.addFinishProc(proc);</p><p>　　this.executing = this.delPreProc();</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(!

41、this.prelst.isEmpty()){//搶占</p><p>　　Process preproc = this.prelst.get(0);</p><p>　　if(this.executing.Priority></p><p>　　preproc.Priority){ //按優(yōu)先級搶占</p><p>　　this.

42、addPreProc(this.executing);</p><p>　　this.executing = this.delPreProc();</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p

43、><p>　　super.processWaitlst(proctimeslice);</p><p>　　++Dispatcher.runTime;</p><p><b>　　--time;</b></p><p><b>　　}</b></p><p><b>　

44、　}</b></p><p><b>　　時間片輪轉(zhuǎn)</b></p><p><b>　　@Override</b></p><p>　　public void run(int time) {</p><p>　　int proctimeslice = 1;//假設(shè)處理器時鐘周期<

45、;/p><p>　　while(time>0){//處理機運行time時間</p><p>　　if(this.executing==null){//沒有進程占用處理機則空轉(zhuǎn)</p><p>　　this.executing = this.delPreProc();</p><p><b>　　}</b><

46、/p><p>　　else{//執(zhí)行當前進程</p><p>　　Process proc = this.executing;</p><p>　　//下一次執(zhí)行需要的設(shè)備</p><p>　　DcRequest req = proc.getNextReq();</p><p>　　if(req!=null &

47、& req.getReqtime()<=proc.runtime){</p><p>　　//進程需要請求設(shè)備，而且執(zhí)行到請求時間</p><p>　　//放入等待隊列,取下一進程</p><p>　　this.addWaitProc(proc);</p><p>　　this.executing = this.delPreP

48、roc();</p><p>　　}else{//無資源請求</p><p>　　proc.run(proctimeslice);</p><p>　　if(proc.isFinished()){</p><p>　　//當前進程是已完成進程，放入完成隊列,取下一進程</p><p>　　proc.setFinish

49、Time(//設(shè)置當前執(zhí)行結(jié)束時間</p><p>　　Dispatcher.getBeginTime()+ </p><p>　　Dispatcher.getRunTime());</p><p>　　this.addFinishProc(proc);</p><p>　　this.executing = this.delPreProc(

50、);</p><p><b>　　}else{</b></p><p>　　//如果當前時間片沒有執(zhí)行完，則從就緒隊列頭移到隊列尾部</p><p>　　this.addPreProc(this.executing);</p><p>　　//當前執(zhí)行進程放入就緒隊列</p><p>　　thi

51、s.executing = this.delPreProc();</p><p>　　//從就緒隊列取下一個進程占用cpu</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p&

52、gt;　　super.processWaitlst(proctimeslice);</p><p>　　++Dispatcher.runTime;</p><p><b>　　--time;</b></p><p><b>　　}</b></p><p><b>　　}</b>

53、</p><p>　　多級反饋輪轉(zhuǎn)搶占方式</p><p><b>　　@Override</b></p><p>　　public void run(int time, boolean isContention) {</p><p>　　int proctimeslice = 1;//假設(shè)處理器時鐘周期</p&

54、gt;<p>　　while(true){ </p><p><b>　　--time;</b></p><p>　　if(this.executing==null){//沒有進程占用處理機則空轉(zhuǎn)</p><p>　　this.executing = this.delPreProc();</p><p>

55、　　if(this.executing!=null){ //每調(diào)度一次重新計算時間片</p><p>　　time = this.executing.getPriority()*3+1;</p><p><b>　　}</b></p><p><b>　　break;</b></p><p>&l

56、t;b>　　}</b></p><p>　　else{//執(zhí)行當前進程</p><p>　　Process proc = this.executing;</p><p>　　//下一次執(zhí)行需要的設(shè)備</p><p>　　DcRequest req = proc.getNextReq();if(req!=n

57、ull && </p><p>　　req.getReqtime()<=proc.runtime){</p><p>　　//進程需要請求設(shè)備，而且執(zhí)行到請求時間</p><p>　　//TODO 放入等待隊列,取下一進程</p><p>　　this.addWaitProc(proc);</p>&l

58、t;p>　　this.executing = this.delPreProc();</p><p>　　break;//時間片未完，設(shè)備請求，重新調(diào)度</p><p>　　}else{//無資源請求</p><p>　　proc.run(proctimeslice);</p><p>　　if(proc.isFinished())

59、{</p><p>　　//當前進程是已完成進程，放入完成隊列,取下一進程</p><p>　　proc.setFinishTime(//設(shè)置當前執(zhí)行結(jié)束時間</p><p>　　Dispatcher.getBeginTime()+</p><p>　　Dispatcher.getRunTime());</p><p&g

60、t;　　this.addFinishProc(proc);</p><p>　　this.executing = this.delPreProc();</p><p>　　break;//時間片沒用完，程序執(zhí)行完，下一次調(diào)度</p><p><b>　　}else{</b></p><p>　　if(time<=

61、0){//時間片用完</p><p>　　//當前執(zhí)行進程放入就緒隊列</p><p>　　this.addPreProc(proc); </p><p>　　//從就緒隊列取下一個進程占用cpu</p><p>　　this.executing = this.delPreProc();break;</p&

62、gt;<p>　　//時間片用完，程序未執(zhí)行完，下一次調(diào)度</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(!this.prelst.isEmpty()){//搶

63、占</p><p>　　Process preproc = this.prelst.get(0);</p><p>　　if(this.executing.Priority></p><p>　　(preproc.Priority+1)){</p><p>　　//取出時優(yōu)先級已經(jīng)降一級</p><p>　　t

64、his.executing.setPriority(</p><p>　　//恢復優(yōu)先級，放入當前進程被取出隊列尾部</p><p>　　this.executing.Priority+1); </p><p>　　this.addPreProc(this.executing);</p><p>　　this.executing = this

65、.delPreProc();</p><p>　　break;//搶占，下一次調(diào)度</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　super.process

66、Waitlst(proctimeslice);</p><p>　　++Dispatcher.runTime;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　測試結(jié)果</b></p><p>

67、<b>　　先來先服務(wù)</b></p><p><b>　　申請資源及阻塞</b></p><p><b>　　中間狀態(tài)</b></p><p><b>　　執(zhí)行結(jié)果</b></p><p><b>　　優(yōu)先級</b></p&g

68、t;<p>　　按優(yōu)先順序放入就緒隊列</p><p>　　優(yōu)先級搶占及執(zhí)行結(jié)果</p><p><b>　　時間片輪轉(zhuǎn)</b></p><p><b>　　測試數(shù)據(jù)</b></p><p><b>　　中間過程</b></p><p>&

69、lt;b>　　測試結(jié)果</b></p><p><b>　　多級反饋輪轉(zhuǎn)</b></p><p><b>　　測試數(shù)據(jù)</b></p><p><b>　　搶占測試</b></p><p><b>　　執(zhí)行狀態(tài)</b></p>

70、<p><b>　　執(zhí)行結(jié)果</b></p><p><b>　　設(shè)計過程難點</b></p><p><b>　　遇到的問題</b></p><p><b>　　調(diào)度時機決策</b></p><p><b>　　迭代器的破壞<

71、;/b></p><p><b>　　多級反饋隊列兼容</b></p><p><b>　　設(shè)備分配、釋放</b></p><p>　　外部統(tǒng)一接口，類型兼容、上轉(zhuǎn)型對象</p><p><b>　　進程的搶占</b></p><p><b&

72、gt;　　解決方法</b></p><p>　　設(shè)置進程相應狀態(tài)（空轉(zhuǎn)、結(jié)束、阻塞、時間片用完、搶斷）</p><p>　　修改循環(huán)嵌套層次，或標記迭代位置、跳出該層循環(huán)重構(gòu)迭代器</p><p>　　采用單一就緒隊列，各進程轉(zhuǎn)入就緒隊列進行插入排序，插入相應位置</p><p>　　掃描設(shè)備請求表，判斷系統(tǒng)設(shè)備表中申請的設(shè)備是否

73、空閑；掃描系統(tǒng)設(shè)備表，判斷設(shè)備是否運轉(zhuǎn)完畢，修改設(shè)備狀態(tài)及進程狀態(tài)</p><p>　　為提供外部統(tǒng)一調(diào)用接口，采用類的繼承及上轉(zhuǎn)型對象，用同一調(diào)用實現(xiàn)不同算法；為實現(xiàn)類型兼容，采用抽象類及虛函數(shù)</p><p>　　沒執(zhí)行一次，判斷就緒隊列首端元素是否有更高優(yōu)先級，就緒隊列插入元素直接進行插入排序，平均復雜度為O(n),實際上只需要常數(shù)級的比較和移動</p><p&g

74、t;<b>　　總結(jié)</b></p><p><b>　　系統(tǒng)實現(xiàn)情況</b></p><p>　　該系統(tǒng)實現(xiàn)了C++及Java兩個版本</p><p>　　Java版本實現(xiàn)了上述各調(diào)度算法，設(shè)備的自動分配及釋放，有良好的用戶操作接口、有很好的容錯提示能力</p><p>　　C++版本實現(xiàn)了上述調(diào)

75、度算法、提供用戶選擇設(shè)備接口、MFC實現(xiàn)良好的操作界面</p><p>　　采用純面向?qū)ο蟮乃枷耄辛己玫姆庋b性，接口統(tǒng)一</p><p>　　用到了抽象類及虛函數(shù)、類型兼容、函數(shù)重載及運算符重載</p><p>　　采用了泛化的變成思想，解決了迭代器的完整性問題</p><p>　　邏輯與控制顯示分離，算法與界面分離并使用不同的現(xiàn)成執(zhí)行&l

76、t;/p><p><b>　　系統(tǒng)特點</b></p><p>　　根據(jù)要求實現(xiàn)了各類調(diào)度算法，并實現(xiàn)了搶占和非搶占工作方式</p><p>　　用戶可在創(chuàng)建進程時發(fā)出多個設(shè)備請求</p><p>　　程序自動檢測設(shè)備請求，阻塞進程并在適當時機喚醒</p><p>　　在插入隊列是對進程排序預處理、減

77、少執(zhí)行過程中的比較次數(shù)</p><p><b>　　收獲</b></p><p>　　掌握了進程調(diào)度的完整過程</p><p>　　進一步復習了C++語言，加強了面向?qū)ο蟮乃枷?，掌握了如何實現(xiàn)邏輯、控制、顯示的分離</p><p>　　復習了多線程的編程思想</p><p>　　掌握了抽象類及虛函

78、數(shù)的應用，學習了上轉(zhuǎn)型對象的應用</p><p>　　進一步學習泛化編程思想，掌握了如何保證迭代器的完整性</p><p>　　進一步實踐如何在面向?qū)ο蠊こ讨蟹止ず献?，采用邏輯分離的思想使得各個模塊并行實現(xiàn)以及各模塊的單元測試</p><p><b>　　參考文獻</b></p><p>　　著作：[1] 張堯?qū)W,史美林