操作系統(tǒng)課程設(shè)計(jì)-- 網(wǎng)絡(luò)教學(xué)系統(tǒng)

1、<p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　課程名稱 操作系統(tǒng)課程設(shè)計(jì) </p><p>　　設(shè)計(jì)題目 網(wǎng)絡(luò)教學(xué)系統(tǒng) </p><p>　　專業(yè)班級(jí) </p><p>　　姓 名

2、</p><p>　　學(xué) 號(hào) </p><p>　　指導(dǎo)教師 </p><p>　　起止時(shí)間 2013年1月6日 </p><p><b>　　成 績(jī) 評(píng) 定</b></p><p><b>　

3、　一、進(jìn)程調(diào)度</b></p><p>　　1、設(shè)計(jì)目的：    </p><p>　　進(jìn)程管理是操作系統(tǒng)中的重要功能，用來(lái)創(chuàng)建進(jìn)程、撤消進(jìn)程、實(shí)現(xiàn)進(jìn)程狀態(tài)轉(zhuǎn)換，它提供了在可運(yùn)行的進(jìn)程之間復(fù)用CPU的方法。在進(jìn)程管理中，進(jìn)程調(diào)度是核心，因?yàn)樵诓捎枚嗟莱绦蛟O(shè)計(jì)的系統(tǒng)中，往往有若干個(gè)進(jìn)程同時(shí)處于就緒狀態(tài)，當(dāng)就緒進(jìn)程個(gè)數(shù)大于處理器數(shù)目時(shí)，就必須

4、依照某種策略決定哪些進(jìn)程優(yōu)先占用處理器。本實(shí)驗(yàn)?zāi)M在單處理器情況下的進(jìn)程調(diào)度，目的是加深對(duì)進(jìn)程調(diào)度工作的理解，掌握不同調(diào)度算法的優(yōu)缺點(diǎn)。</p><p><b>　　2、設(shè)計(jì)題目</b></p><p>　　設(shè)計(jì)一個(gè)按多級(jí)隊(duì)列調(diào)度算法實(shí)現(xiàn)處理器調(diào)度的程序。</p><p><b>　　設(shè)計(jì)思想</b></p>

5、<p>　　設(shè)置多個(gè)就緒隊(duì)列，分別賦予不同的優(yōu)先級(jí)，如逐級(jí)降低，隊(duì)列1的優(yōu)先級(jí)最高。每個(gè)隊(duì)列執(zhí)行時(shí)間片的長(zhǎng)度也不同，規(guī)定優(yōu)先級(jí)越低則時(shí)間片越長(zhǎng)，如逐級(jí)加倍?！　⌒逻M(jìn)程進(jìn)入內(nèi)存后，先投入隊(duì)列1的末尾，按FCFS算法調(diào)度；若按隊(duì)列1一個(gè)時(shí)間片未能執(zhí)行完，則降低投入到隊(duì)列2的末尾，同樣按FCFS算法調(diào)度；如此下去，降低到最后的隊(duì)列，則按“時(shí)間片輪轉(zhuǎn)”算法調(diào)度直到完成?！　H當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程

6、執(zhí)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶先執(zhí)行新進(jìn)程，并把被搶先的進(jìn)程投入原隊(duì)列的末尾。</p><p><b>　　源代碼 </b></p><p>　　#include "stdio.h"</p><p>　　#include "conio.h"</p><p>

7、　　#include "stdlib.h"</p><p>　　#include "malloc.h"</p><p>　　#include "time.h"</p><p>　　#include "windows.h"</p><p>　　#define nul

8、l 0</p><p>　　#define N 4</p><p>　　int MN=18;</p><p>　　struct cpu { //就緒隊(duì)列</p><p>　　int time; //時(shí)間片數(shù)量</p><p>　　struct pss *head;</p><p>　　st

9、ruct pss *tail;</p><p><b>　　};</b></p><p>　　struct pss { //進(jìn)程</p><p>　　char name[5];</p><p>　　int pro_time; //執(zhí)行時(shí)間</p><p>　　int l_time; // 剩余

10、時(shí)間</p><p>　　struct pss *next;</p><p><b>　　};</b></p><p>　　void gotoxy(int x, int y) </p><p><b>　　{ </b></p><p><b>　　COORD c;

11、</b></p><p>　　c.X = x - 1; </p><p>　　c.Y = y - 1; </p><p>　　SetConsoleCursorPosition (GetStdHandle(STD_OUTPUT_HANDLE), c); </p><p><b>　　} </b></p&g

12、t;<p>　　void initial(struct cpu cpu_quene[]) //初始化就緒隊(duì)列，時(shí)間片分別為2 4 8 16</p><p><b>　　{</b></p><p>　　int i,t=2;</p><p>　　for(i=0;i<4;i++)</p><p>　　{ c

13、pu_quene[i].time=t;</p><p>　　cpu_quene[i].head=null;</p><p>　　cpu_quene[i].tail=null;</p><p><b>　　t=2*t;</b></p><p><b>　　}</b></p><p&

14、gt;<b>　　return;</b></p><p><b>　　}</b></p><p>　　void creatpcb(struct cpu cpu_quene[]) //創(chuàng)建進(jìn)程</p><p><b>　　{</b></p><p>　　struct pss *

15、 p,*q;</p><p>　　p=(struct pss *)malloc(sizeof(struct pss));</p><p>　　gotoxy(25,6);</p><p>　　printf(" 請(qǐng)輸入進(jìn)程名稱 ：");</p><p>　　scanf("%s",p->

16、name);</p><p>　　gotoxy(25,8);</p><p>　　printf("請(qǐng)輸入處理進(jìn)程需要的時(shí)間：");</p><p>　　scanf("%d",&p->pro_time);</p><p>　　p->l_time=p->pro_time; //剩余

17、時(shí)間初始化，初始值為需要時(shí)間的值</p><p>　　p->next=null;</p><p>　　if(cpu_quene[0].head==null)</p><p>　　{cpu_quene[0].head=p;</p><p>　　cpu_quene[0].tail=p;}</p><p><b&

18、gt;　　else</b></p><p>　　{q=cpu_quene[0].tail;</p><p>　　cpu_quene[0].tail=p;</p><p>　　q->next=p;}</p><p><b>　　}</b></p><p>　　void osdela

19、y(int n)</p><p>　　{int a,i,m;</p><p><b>　　m=500*n;</b></p><p>　　a=clock();</p><p>　　for(i=0;;i++){</p><p>　　if(clock()-a==m)</p><p&g

20、t;<b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void print(struct cpu cpu_quene[])</p><p>　　{ struct pss *p;</p>

21、;<p>　　gotoxy(23,5);</p><p>　　p=cpu_quene[0].head;</p><p>　　printf(" ");</p><p>　　gotoxy(23,5);</p><p>　　

22、while(p!=null)</p><p>　　{printf("[%s %d] ",p->name,p->l_time);</p><p>　　p=p->next;}</p><p>　　gotoxy(23,7);</p><p>　　p=cpu_quene[1].head;</p>

23、;<p>　　printf(" ");</p><p>　　gotoxy(23,7);</p><p>　　while(p!=null)</p><p>　　{printf("[%s %d] ",p->na

24、me,p->l_time);</p><p>　　p=p->next;}</p><p>　　gotoxy(23,9);</p><p>　　p=cpu_quene[2].head;</p><p>　　printf(" &q

25、uot;);</p><p>　　gotoxy(23,9);</p><p>　　while(p!=null)</p><p>　　{printf("[%s %d] ",p->name,p->l_time);</p><p>　　p=p->next;}</p><p>　　

26、gotoxy(23,11);</p><p>　　p=cpu_quene[3].head;</p><p>　　printf(" ");</p><p>　　gotoxy(23,11);</p><p>　　while(p!=n

27、ull)</p><p>　　{printf("[%s %d] ",p->name,p->l_time);</p><p>　　p=p->next;}</p><p><b>　　}</b></p><p>　　void nprint(struct pss *p)</p

28、><p>　　{gotoxy(27,15);</p><p>　　printf("[%s %d] ",p->name,p->l_time);</p><p><b>　　}</b></p><p>　　void process(struct cpu cpu_quene[N]) //

29、進(jìn)程執(zhí)行函數(shù)</p><p><b>　　{</b></p><p>　　struct pss *p,*q,*p1;</p><p>　　int i=0,j,a,b;</p><p>　　int flag1=1;</p><p>　　while(i<4&&cpu_quene[

30、i].head==null){</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p><b>　　if(i==4)</b></p><p>　　printf("\n無(wú)需要處理的進(jìn)程！");</p>

31、<p><b>　　else </b></p><p><b>　　{if(i==3)</b></p><p><b>　　a=1;</b></p><p><b>　　else </b></p><p><b>　　a=2;<

32、/b></p><p>　　for(;flag1==1;)</p><p>　　{switch(a)</p><p>　　{case 1:{if(cpu_quene[i].head!=null)</p><p>　　{p=cpu_quene[i].head;</p><p>　　gotoxy(27,15);<

33、;/p><p>　　printf(" ");</p><p>　　nprint(p);</p><p>　　while(p!=null)</p><p><b>　　{</b></p><

34、p>　　while(p->l_time!=0)</p><p>　　{osdelay(1);</p><p>　　p->l_time=p->l_time-1; //剩余時(shí)間-1？</p><p><b>　　}</b></p><p>　　gotoxy(27,15);</p><

35、;p>　　printf("進(jìn)程%s處理完畢，離開(kāi)隊(duì)列!",p->name);</p><p>　　cpu_quene[i].head=p->next;</p><p>　　print(cpu_quene);</p><p>　　gotoxy(MN,18);</p><p>　　printf("[

36、%s %d]",p->name,p->pro_time); //輸出執(zhí)行結(jié)果</p><p><b>　　MN=MN+9;</b></p><p>　　free(p); //釋放內(nèi)存</p><p>　　p=cpu_quene[i].head;</p><p><b>　　}</

37、b></p><p>　　gotoxy(10,2);</p><p>　　printf(" ");</p><p>　　gotoxy(10,2);</p><p>

38、;　　printf("所有進(jìn)程處理完畢!");</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　{gotoxy(10,2);</p><p>　　printf("

39、 ");</p><p>　　gotoxy(10,2);</p><p>　　printf("所有進(jìn)程處理完畢!");}</p><p><b>　　flag1=0;</b></p><p&

40、gt;<b>　　break;</b></p><p><b>　　}</b></p><p>　　case 2:{p=cpu_quene[i].head;</p><p>　　for(;cpu_quene[i].head!=null;)</p><p>　　{ cpu_quene[i].head=

41、p->next;</p><p>　　p->next=null;</p><p>　　gotoxy(27,15);</p><p>　　printf(" ");</p><p>　　nprint(p);</p

42、><p>　　b=cpu_quene[i].time;</p><p>　　while(p->l_time!=0&&b!=0)</p><p>　　{osdelay(1);</p><p>　　p->l_time=p->l_time-1;</p><p>　　b--; //時(shí)間片減1&l

43、t;/p><p><b>　　}</b></p><p>　　if(p->l_time==0) //剩余時(shí)間為零</p><p>　　{gotoxy(27,15);</p><p>　　printf("進(jìn)程%s處理完畢，離開(kāi)隊(duì)列!",p->name);</p><p>

44、　　gotoxy(MN,18);</p><p>　　printf("[%s %d]",p->name,p->pro_time); //輸出完成進(jìn)程</p><p><b>　　MN=MN+9;</b></p><p><b>　　free(p);</b></p><p

45、><b>　　}</b></p><p><b>　　else{</b></p><p><b>　　j=i+1;</b></p><p>　　if(cpu_quene[j].head!=null) //p=cpu_quene[i].head</p><p>　　{q=

46、cpu_quene[j].tail;</p><p>　　cpu_quene[j].tail=p;</p><p>　　q->next=p;}</p><p><b>　　else</b></p><p>　　{cpu_quene[j].head=p;</p><p>　　cpu_quene

47、[j].tail=p;</p><p>　　p->next=null;}</p><p><b>　　}</b></p><p>　　print(cpu_quene);</p><p>　　p=cpu_quene[i].head;</p><p><b>　　}</b>

48、</p><p>　　cpu_quene[i].tail=null;</p><p><b>　　i++;</b></p><p><b>　　if(i==3)</b></p><p><b>　　a=1;</b></p><p><b>　　

49、else</b></p><p><b>　　a=2;</b></p><p><b>　　break;}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><

50、;b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p>　　{ int i, j,flag=1,t=2;</p><p><b>　　char a;</b></p><p>　　struct

51、pss *p1;</p><p>　　struct cpu cpu_quene[4];</p><p>　　initial(cpu_quene); //創(chuàng)建就緒隊(duì)列</p><p>　　for(;flag==1;){</p><p>　　gotoxy(20,4);</p><p>　　printf("┏━━

52、━━━━━━━━━━━━━━━━┓");</p><p>　　for(j=5;j<10;j++)</p><p>　　{gotoxy(20,j);</p><p>　　printf("┃ ┃");}</p><p>　　gotoxy(20

53、,10);</p><p>　　printf("┗━━━━━━━━━━━━━━━━━━┛");</p><p>　　creatpcb(cpu_quene); //創(chuàng)建進(jìn)程</p><p>　　gotoxy(25,12);</p><p>　　printf("繼續(xù)輸入進(jìn)程？（Y/N）");</p&g

54、t;<p>　　scanf("%s",&a);</p><p>　　if(a=='n'||a=='N')</p><p><b>　　{flag=0;}</b></p><p>　　system("cls"); //消除上一次回車(chē)的內(nèi)容</p&

55、gt;<p><b>　　}</b></p><p>　　gotoxy(10,2);</p><p>　　printf("待處理進(jìn)程： ");</p><p>　　p1=cpu_quene[0].head;</p><p>　　while(p1!=null){</p>&l

56、t;p>　　printf("[%s %d] ",p1->name,p1->pro_time);</p><p>　　p1=p1->next;</p><p><b>　　}</b></p><p>　　for(j=4;j<13;j++)</p><p>　　{got

57、oxy(8,j);</p><p>　　printf("┃ ┃");}</p><p>　　gotoxy(8,4);</p><p>　　printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━

58、━━━━┓");</p><p>　　gotoxy(10,5);</p><p>　　printf("一級(jí)隊(duì)列 2：");</p><p>　　gotoxy(10,7);</p><p>　　printf("二級(jí)隊(duì)列 4：");</p><p>　　gotoxy(1

59、0,9);</p><p>　　printf("三級(jí)隊(duì)列 8：");</p><p>　　gotoxy(10,11);</p><p>　　printf("四級(jí)隊(duì)列 16："); </p><p>　　gotoxy(8,13);</p><p>　　printf("┗

60、━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛");</p><p>　　print(cpu_quene);</p><p>　　gotoxy(10,15);</p><p>　　printf("正在處理的進(jìn)程："); </p><p>　　process(cpu_quene);</p

61、><p>　　gotoxy(10,20);</p><p>　　printf("\n*******************************************************************************");</p><p><b>　　}</b></p><p>

62、<b>　　運(yùn)行結(jié)果：</b></p><p>　　重點(diǎn)和難點(diǎn)及其解決方法 </p><p>　　多級(jí)反饋隊(duì)列算法的實(shí)現(xiàn)。剛開(kāi)始對(duì)多級(jí)反饋隊(duì)列算法不太了解，是FCFS 、RR、HPF三者結(jié)合而形成的一種進(jìn)程調(diào)度算法。</p><p><b>　　二、死鎖 </b>

63、</p><p>　　1、設(shè)計(jì)目的：        </p><p>　　死鎖是進(jìn)程并發(fā)執(zhí)行過(guò)程中可能出現(xiàn)的現(xiàn)象，哲學(xué)家就餐問(wèn)題是描述死鎖的經(jīng)典例子。為了防止死鎖，可以采用資源預(yù)分配法或者資源按序分配法。資源預(yù)分配法是指進(jìn)程在運(yùn)行前一次性地向系統(tǒng)申請(qǐng)它所需要的全部資源，如果系統(tǒng)當(dāng)前不能夠滿足進(jìn)程的全部資源請(qǐng)求，

64、則不分配資源, 此進(jìn)程暫不投入運(yùn)行，如果系統(tǒng)當(dāng)前能夠滿足進(jìn)程的全部資源請(qǐng)求, 則一次性地將所申請(qǐng)的資源全部分配給申請(qǐng)進(jìn)程。資源按序分配法是指事先將所有資源類全排序, 即賦予每一個(gè)資源類一個(gè)唯一的整數(shù)，規(guī)定進(jìn)程必需按照資源編號(hào)由小到大的次序申請(qǐng)資源。</p><p><b>　　2、設(shè)計(jì)題目： </b></p><p>　　模擬有五個(gè)哲學(xué)家的哲學(xué)家進(jìn)餐問(wèn)題。&

65、lt;/p><p><b>　　3、設(shè)計(jì)思路</b></p><p>　　在什么情況下5 個(gè)哲學(xué)家全部吃不上飯。</p><p>　　(1) 假如所有的哲學(xué)家都同時(shí)拿起左側(cè)筷子，看到右側(cè)筷子不可用，又都放下左側(cè)筷子，</p><p>　　等一會(huì)兒，又同時(shí)拿起左側(cè)筷子，如此這般，永遠(yuǎn)重復(fù)。對(duì)于這種情況，即所有的程序都在<

66、/p><p>　　無(wú)限期地運(yùn)行，但是都無(wú)法取得任何進(jìn)展，即出現(xiàn)饑餓，所有哲學(xué)家都吃不上飯。</p><p>　　(2) 算法：規(guī)定在拿到左側(cè)的筷子后，先檢查右面的筷子是否可用。如果不可用，則先放下左側(cè)筷子，等一段時(shí)間再重復(fù)整個(gè)過(guò)程。當(dāng)出現(xiàn)以下情形，在某一個(gè)瞬間，所有的哲學(xué)家都同時(shí)啟動(dòng)這個(gè)算法，拿起左側(cè)的筷子，而看到右側(cè)筷子不可用，又都放下左側(cè)筷子，等一會(huì)兒，又同時(shí)拿起左側(cè)筷子……如此這樣永遠(yuǎn)重

67、復(fù)下去。對(duì)于這種情況，所有的程序都在運(yùn)行，但卻無(wú)法取得進(jìn)展，即出現(xiàn)饑餓，所有的哲學(xué)家都吃不上飯。</p><p>　　一種沒(méi)有人餓死算法.。</p><p>　　僅當(dāng)哲學(xué)家的左右兩支筷子都可用時(shí),才允許他拿起筷子進(jìn)餐。</p><p>　　利用型信號(hào)量機(jī)制實(shí)現(xiàn)：在一個(gè)原語(yǔ)中，將一段代碼同時(shí)需要的多個(gè)臨界資源，要么全部分配給它，要么一個(gè)都不分配，因此不會(huì)出現(xiàn)死鎖的情形

68、。當(dāng)某些資源不夠時(shí)阻塞調(diào)用進(jìn)程;由于等待隊(duì)列的存在，使得對(duì)資源的請(qǐng)求滿足要求，因此不會(huì)出現(xiàn)饑餓的情形。</p><p>　　#include <stdlib.h></p><p>　　#include <iostream.h></p><p>　　#include <time.h></p><p>　　en

69、um PhState{Thinking=0,Waiting,Eating};//枚舉型、哲學(xué)家狀態(tài)</p><p>　　int stick[5];//筷子狀態(tài)，1表示使用，0表示空閑</p><p>　　PhState phstate[5];//哲學(xué)家狀態(tài)</p><p>　　int timerforPh[5];// 定時(shí)器，確定狀態(tài)變化的時(shí)刻</p>

70、<p>　　const int SPAN = 91;//定義思考和進(jìn)食的最長(zhǎng)時(shí)間</p><p>　　void hungry(int i) //模擬當(dāng)i饑餓時(shí)，采用的策略。</p><p><b>　　{</b></p><p>　　int left = (i)%5;</p><p>　　int right

71、= (i+1)%5;</p><p>　　if(stick[left]==0 && stick[right]==0) //筷子左右空閑</p><p><b>　　{</b></p><p>　　stick[left]=stick[right]=1; //使用筷子</p><p>　　phstate[i]

72、=Eating; </p><p>　　timerforPh[i]=rand()%SPAN+1;//設(shè)置吃飯時(shí)間</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p&g

73、t;　　phstate[i]=Waiting; //等待</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void wakeup(int i)//從等待中喚醒</p><p><b>　　{</b></p>&l

74、t;p>　　hungry( i); //喚醒后的操作同思考時(shí)饑餓的操作相同</p><p><b>　　}</b></p><p>　　void ate(int i) //模擬吃完后的動(dòng)作</p><p><b>　　{</b></p><p>　　stick[(i)%5]=0;

75、 //吃完后放下筷子</p><p>　　stick[(i+1)%5]=0; //喚醒左右哲學(xué)家的順序可以改成隨機(jī)的，這里僅僅是固定順序</p><p>　　if(phstate[(5+i-1)%5]==Waiting)</p><p>　　wakeup((5+i-1)%5);</p><p>　　if(phstate[(i+1)%

76、5]==Waiting)</p><p>　　wakeup((i+1)%5);</p><p>　　phstate[i]=Thinking; //喚醒后思考</p><p>　　timerforPh[i]=rand()%SPAN+1;//設(shè)置思考時(shí)間、隨機(jī)</p><p><b>　　}</b></p>

77、<p>　　void print_state(int cur_time) //輸出當(dāng)前狀態(tài),參數(shù)為當(dāng)前時(shí)間</p><p><b>　　{</b></p><p>　　char state_ch[]={'0','!','X'};</p><p>　　cout.width(4);<

78、/p><p>　　cout<<cur_time<<"ms : ";</p><p>　　for(int i=0; i<5; i++)</p><p><b>　　{</b></p><p>　　cout.width(2);</p><p>　　cout

79、<<state_ch[phstate[i]]<<' ';</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　void simulator() //模擬器

80、</p><p><b>　　{</b></p><p>　　srand(time(NULL)); //初始化</p><p>　　for(int i=0; i<5;i++)</p><p><b>　　{</b></p><p>　　stick[i]=0;</

81、p><p>　　timerforPh[i]=rand()%SPAN+1; //設(shè)置思考時(shí)間</p><p>　　phstate[i]=Thinking;</p><p><b>　　}</b></p><p><b>　　//模擬開(kāi)始</b></p><p>　　long tim

82、e = 0;//時(shí)鐘</p><p>　　int eating_event_cnt=0;//進(jìn)食成功事件次數(shù)</p><p>　　while(eating_event_cnt<10)</p><p><b>　　{</b></p><p><b>　　time++;</b></p>

83、<p>　　for(int i=0;i<5;i++) //檢查哪個(gè)哲學(xué)家的狀態(tài)需要改變</p><p><b>　　{</b></p><p>　　switch(phstate[i])</p><p><b>　　{</b></p><p>　　case Waiting:<

84、;/p><p>　　++timerforPh[i];//記錄等待時(shí)間</p><p><b>　　break;</b></p><p>　　case Thinking:</p><p>　　if(--timerforPh[i]<0)</p><p><b>　　{</b>&

85、lt;/p><p>　　hungry(i);</p><p>　　print_state(time);</p><p><b>　　}</b></p><p><b>　　break;</b></p><p><b>　　default:</b></p

86、><p>　　if(--timerforPh[i]<0)</p><p><b>　　{</b></p><p><b>　　ate(i);</b></p><p>　　print_state(time);</p><p>　　eating_event_cnt++;<

87、/p><p><b>　　}</b></p><p><b>　　break;</b></p><p><b>　　};</b></p><p><b>　　}</b></p><p><b>　　}</b><

88、;/p><p><b>　　}</b></p><p>　　int main(int argc, char* argv[])</p><p><b>　　{</b></p><p>　　simulator();</p><p><b>　　return 0;</b

89、></p><p><b>　　}</b></p><p><b>　　運(yùn)行結(jié)果：</b></p><p>　　23ms : 0 0 X 0 0</p><p>　　34ms : 0 ! X 0 0</p><p>　　34ms : 0 ! X

90、 0 X</p><p>　　37ms : 0 ! X 0 0</p><p>　　48ms : 0 ! X ! 0</p><p>　　57ms : 0 X 0 X 0</p><p>　　72ms : 0 X 0 0 0</p><p>　　88ms : ! X 0

91、 0 0</p><p>　　123ms : ! X ! 0 0</p><p>　　127ms : ! X ! 0 X</p><p>　　143ms : ! X ! ! X</p><p>　　146ms : ! 0 X ! X</p><p>　　163ms : !

92、 ! X ! X</p><p>　　182ms : X ! X ! 0</p><p>　　216ms : 0 ! X ! 0</p><p>　　236ms : 0 X 0 X 0</p><p>　　246ms : ! X 0 X 0</p><p>　　252ms

93、: ! X ! X 0</p><p>　　258ms : ! X ! X !</p><p>　　269ms : X 0 ! X !</p><p>　　273ms : 0 0 ! X !</p><p>　　297ms : 0 0 X 0 X</p><p>　　重

94、點(diǎn)和難點(diǎn)及其解決方法</p><p>　　解決哲學(xué)家饑餓的算法。哲學(xué)家餓了就要嘗試去得到叉子，哲學(xué)家得到相鄰的左右兩把叉子才可以進(jìn)餐，吃完了就要釋放兩把叉子。</p><p>　　三 、動(dòng)態(tài)異長(zhǎng)分區(qū)的存儲(chǔ)分配與回收算法 </p><p>　　1、設(shè)計(jì)目的：     </p><p>

95、　　存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)中的關(guān)鍵資源，存儲(chǔ)管理一直是操作系統(tǒng)的最主要功能之一。存儲(chǔ)管理既包括內(nèi)存資源管理，也包括用 于實(shí)現(xiàn)分級(jí)存儲(chǔ)體系的外存資源的管理。通常，內(nèi)存與外存可采用相同或相似的管理技術(shù)，如內(nèi)存采用段式存儲(chǔ)管理，則外存也采用段式存儲(chǔ)管理。 通過(guò)本設(shè)計(jì) 理解存儲(chǔ)管理的功能，掌握動(dòng)態(tài)異長(zhǎng)分區(qū)的存儲(chǔ)分配與回收算法。</p><p><b>　　2、設(shè)計(jì)題目： </b></p&

96、gt;<p>　　模擬動(dòng)態(tài)異長(zhǎng)分區(qū)的分配算法、回收算法和碎片整理算法。</p><p><b>　　3、設(shè)計(jì)思路</b></p><p>　　設(shè)計(jì)目標(biāo)用C語(yǔ)言或C++語(yǔ)言分別實(shí)現(xiàn)采用首次適應(yīng)算法和最佳適應(yīng)算法的動(dòng)態(tài)分區(qū)分配過(guò)程alloc()和回收過(guò)程free()。其中，空閑分區(qū)通過(guò)空閑分區(qū)鏈表來(lái)管理，在進(jìn)行內(nèi)存分配時(shí)，系統(tǒng)優(yōu)先使用空閑區(qū)低端空間。分別用首

97、次適應(yīng)算法和最佳適應(yīng)算法進(jìn)行內(nèi)存塊的分配和回收，同時(shí)顯示內(nèi)存塊分配和回收后空閑內(nèi)存分區(qū)鏈的情況。</p><p>　　首次適應(yīng)算法（First-fit）：當(dāng)要分配內(nèi)存空間時(shí)，就查表，在各空閑區(qū)中查找滿足大小要求的可用塊。只要找到第一個(gè)足以滿足要球的空閑塊就停止查找，并把它分配出去；如果該空閑空間與所需空間大小一樣，則從空閑表中取消該項(xiàng)；如果還有剩余，則余下的部分仍留在空閑表中，但應(yīng)修改分區(qū)大小和分區(qū)始址。<

98、/p><p>　　最佳適應(yīng)算法（Best-fit）：當(dāng)要分配內(nèi)存空間時(shí)，就查找空閑表中滿足要求的空閑塊，并使得剩余塊是最小的。然后把它分配出去，若大小恰好合適，則直按分配；若有剩余塊，則仍保留該余下的空閑分區(qū)，并修改分區(qū)大小的起始地址。</p><p>　　內(nèi)存回收：將釋放作業(yè)所在內(nèi)存塊的狀態(tài)改為空閑狀態(tài)，刪除其作業(yè)名，設(shè)置為空。并判斷該空閑塊是否與其他空閑塊相連，若釋放的內(nèi)存空間與空閑塊相連

99、時(shí)，則合并為同一個(gè)空閑塊，同時(shí)修改分區(qū)大小及起始地址。</p><p><b>　　源代碼 </b></p><p>　　#include<iostream.h></p><p>　　#include<stdlib.h></p><p>　　#define Free 0 //空閑狀態(tài)</p

100、><p>　　#define Busy 1 //已用狀態(tài)</p><p>　　#define OK 1 //完成</p><p>　　#define ERROR 0 //出錯(cuò)</p><p>　　#define MAX_length 640 //最大內(nèi)存空間為640KB</p><p>　　typedef int S

101、tatus;</p><p>　　typedef struct freearea//定義一個(gè)空閑區(qū)說(shuō)明表結(jié)構(gòu)</p><p><b>　　{</b></p><p>　　int ID; //分區(qū)號(hào)</p><p>　　long size; //分區(qū)大小</p><p>　　long add

102、ress; //分區(qū)地址</p><p>　　int state; //狀態(tài)</p><p>　　}ElemType;</p><p>　　typedef struct DuLNode // 線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)</p><p><b>　　{</b></p><p>　　ElemType

103、 data; </p><p>　　struct DuLNode *prior; //前趨指針</p><p>　　struct DuLNode *next; //后繼指針</p><p>　　}DuLNode,*DuLinkList;</p><p>　　DuLinkList block_first; //頭結(jié)點(diǎn)</p>&

104、lt;p>　　DuLinkList block_last; //尾結(jié)點(diǎn)</p><p>　　Status alloc(int);//內(nèi)存分配</p><p>　　Status free(int); //內(nèi)存回收</p><p>　　Status First_fit(int,int);//首次適應(yīng)算法</p><p>　　Status

105、Best_fit(int,int); //最佳適應(yīng)算法</p><p>　　void show();//查看分配</p><p>　　Status Initblock();//開(kāi)創(chuàng)空間表</p><p>　　Status Initblock()//開(kāi)創(chuàng)帶頭結(jié)點(diǎn)的內(nèi)存空間鏈表</p><p><b>　　{</b><

106、/p><p>　　block_first=(DuLinkList)malloc(sizeof(DuLNode));</p><p>　　block_last=(DuLinkList)malloc(sizeof(DuLNode));</p><p>　　block_first->prior=NULL;</p><p>　　block_firs

107、t->next=block_last;</p><p>　　block_last->prior=block_first;</p><p>　　block_last->next=NULL;</p><p>　　block_last->data.address=0;</p><p>　　block_last->dat

108、a.size=MAX_length;</p><p>　　block_last->data.ID=0;</p><p>　　block_last->data.state=Free;</p><p>　　return OK;</p><p><b>　　}</b></p><p>　　/

109、/分 配 主 存 </p><p>　　Status alloc(int ch)</p><p><b>　　{</b></p><p>　　int ID,request;</p><p>　　cout<<"請(qǐng)輸入作業(yè)(分區(qū)號(hào))："; </p><p><b&

110、gt;　　cin>>ID;</b></p><p>　　cout<<"請(qǐng)輸入需要分配的主存大小(單位:KB)："; </p><p>　　cin>>request;</p><p>　　if(request<0 ||request==0) </p><p><b&

111、gt;　　{</b></p><p>　　cout<<"分配大小不合適，請(qǐng)重試！"<<endl;</p><p>　　return ERROR;</p><p><b>　　}</b></p><p>　　if(ch==2) //選擇最佳適應(yīng)算法</p>

112、<p><b>　　{</b></p><p>　　if(Best_fit(ID,request)==OK) cout<<"分配成功！"<<endl;</p><p>　　else cout<<"內(nèi)存不足，分配失??！"<<endl;</p><p&

113、gt;　　return OK;</p><p><b>　　}</b></p><p>　　else //默認(rèn)首次適應(yīng)算法</p><p><b>　　{</b></p><p>　　if(First_fit(ID,request)==OK) cout<<"分配成功！"

114、;<<endl;</p><p>　　else cout<<"內(nèi)存不足，分配失敗！"<<endl;</p><p>　　return OK;</p><p><b>　　}</b></p><p><b>　　}</b></p>

115、<p>　　// 首次適應(yīng)算法 </p><p>　　Status First_fit(int ID,int request)//傳入作業(yè)名及申請(qǐng)量</p><p><b>　　{</b></p><p>　　//為申請(qǐng)作業(yè)開(kāi)辟新空間且初始化</p><p>　　DuLinkList temp=(DuLinkL

116、ist)malloc(sizeof(DuLNode)); </p><p>　　temp->data.ID=ID; </p><p>　　temp->data.size=request;</p><p>　　temp->data.state=Busy;</p><p>　　DuLNode *p=block_first->

117、;next;</p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　if(p->data.state==Free && p->data.size==request)</p><p>　　{//有大小恰好合適的空閑

118、塊</p><p>　　p->data.state=Busy;</p><p>　　p->data.ID=ID;</p><p>　　return OK;</p><p><b>　　break;</b></p><p><b>　　}</b></p>

119、<p>　　if(p->data.state==Free && p->data.size>request)</p><p>　　{//有空閑塊能滿足需求且有剩余"</p><p>　　temp->prior=p->prior;</p><p>　　temp->next=p; <

120、;/p><p>　　temp->data.address=p->data.address;</p><p>　　p->prior->next=temp; </p><p>　　p->prior=temp;</p><p>　　p->data.address=temp->data.address+temp-

121、>data.size;</p><p>　　p->data.size-=request;</p><p>　　return OK;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　p=p->nex

122、t;</p><p><b>　　}</b></p><p>　　return ERROR;</p><p><b>　　}</b></p><p>　　//最佳適應(yīng)算法 </p><p>　　Status Best_fit(int ID,int request)</

123、p><p><b>　　{</b></p><p>　　int ch; //記錄最小剩余空間</p><p>　　DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); </p><p>　　temp->data.ID=ID; </p><p>

124、　　temp->data.size=request;</p><p>　　temp->data.state=Busy;</p><p>　　DuLNode *p=block_first->next;</p><p>　　DuLNode *q=NULL; //記錄最佳插入位置</p><p>　　while(p) //初始化最

125、小空間和最佳位置</p><p><b>　　{</b></p><p>　　if(p->data.state==Free &&</p><p>　　(p->data.size>request || p->data.size==request) )</p><p><b>

126、;　　{</b></p><p><b>　　q=p;</b></p><p>　　ch=p->data.size-request;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p&g

127、t;　　p=p->next;</p><p><b>　　}</b></p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　if(p->data.state==Free && p->d

128、ata.size==request)</p><p>　　{//空閑塊大小恰好合適</p><p>　　p->data.ID=ID;</p><p>　　p->data.state=Busy;</p><p>　　return OK;</p><p><b>　　break;</b>&

129、lt;/p><p><b>　　}</b></p><p>　　if(p->data.state==Free && p->data.size>request)</p><p>　　{//空閑塊大于分配需求</p><p>　　if(p->data.size-request<ch)

130、//剩余空間比初值還小</p><p><b>　　{</b></p><p>　　ch=p->data.size-request;//更新剩余最小值</p><p>　　q=p;//更新最佳位置指向</p><p><b>　　}</b></p><p><b&

131、gt;　　}</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　if(q==NULL) return ERROR;//沒(méi)有找到空閑塊</p><p><b>　　else</b></p><p>　

132、　{//找到了最佳位置并實(shí)現(xiàn)分配</p><p>　　temp->prior=q->prior;</p><p>　　temp->next=q;</p><p>　　temp->data.address=q->data.address;</p><p>　　q->prior->next=temp;&l

133、t;/p><p>　　q->prior=temp;</p><p>　　q->data.address+=request;</p><p>　　q->data.size=ch;</p><p>　　return OK;</p><p><b>　　}</b></p>&

134、lt;p><b>　　}</b></p><p>　　// 主 存 回 收 </p><p>　　Status free(int ID)</p><p><b>　　{</b></p><p>　　DuLNode *p=block_first;</p><p>&l

135、t;b>　　while(p)</b></p><p><b>　　{</b></p><p>　　if(p->data.ID==ID)</p><p><b>　　{</b></p><p>　　p->data.state=Free;</p><p&

136、gt;　　p->data.ID=Free;</p><p>　　if(p->prior->data.state==Free)//與前面的空閑塊相連</p><p><b>　　{</b></p><p>　　p->prior->data.size+=p->data.size;</p><p

137、>　　p->prior->next=p->next;</p><p>　　p->next->prior=p->prior;</p><p><b>　　}</b></p><p>　　if(p->next->data.state==Free)//與后面的空閑塊相連</p>&l

138、t;p><b>　　{</b></p><p>　　p->data.size+=p->next->data.size;</p><p>　　p->next->next->prior=p;</p><p>　　p->next=p->next->next; <

139、;/p><p><b>　　}</b></p><p><b>　　break; </b></p><p><b>　　}</b></p><p>　　p=p->next;</p><p><b>　　}</b></p&g

140、t;<p>　　return OK;</p><p><b>　　}</b></p><p>　　// 顯示主存分配情況 </p><p>　　void show()</p><p><b>　　{</b></p><p>　　cout<<"

141、;+++++++++++++++++++++++++++++++++++++++\n";</p><p>　　cout<<"+++ 主 存 分 配 情 況 +++\n";</p><p>　　cout<<"+++++++++++++++++++++++++++++++++++++++\n"

142、;</p><p>　　DuLNode *p=block_first->next;</p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　cout<<"分 區(qū) 號(hào)：";</p><p