1、上機報告姓名學(xué)號專業(yè)班級計科普1002 課程名稱 網(wǎng)絡(luò)操作系統(tǒng)指導(dǎo)教師機房名稱 （I515）上機日期2012 年12 月 20 日上機項目名稱 上機步驟及內(nèi)容： 1實驗?zāi)康?1) 加深對可變分區(qū)的存儲管理的理解；(2) 提高用C語言編制大型系統(tǒng)程序的能力，特別是掌握C語言編程的難點：指針和指針作為函數(shù)參數(shù)；(3) 掌握用指針實現(xiàn)鏈表和在鏈表上的基本操作。2 實驗要求首先向系統(tǒng)申請內(nèi)存空間，初始化空閑表，輸出命令菜單（分配內(nèi)存，釋放內(nèi)存，退出程序）；按用戶的選擇，分別進行內(nèi)存分配、內(nèi)存釋放或退出程序的操作；若未選擇退出程序，則操作完成后輸出新的空閑表并回到命令菜單。3 實驗內(nèi)容3.1 數(shù)據(jù)結(jié)構(gòu)結(jié)

2、點：class Nodepublic:char* addr;/空閑內(nèi)存起始地址unsigned int size;/空閑內(nèi)存大小Node* next;/下一個空閑內(nèi)存節(jié)點Node* prior;/上一個空閑內(nèi)存節(jié)點Node();/構(gòu)造函數(shù)void Display(int i);/顯示這個節(jié)點（減去初始地址i，以顯示相對地址）;列表：class ListNode* first;/鏈表中的第一個節(jié)點Node* now;/下一個要搜索的空閑內(nèi)存節(jié)點public:List();void Insert(Node* n,char* a,unsigned int s);/在節(jié)點i之后插入一個起始地址為a，大

3、小為s的節(jié)點void ChangeFirst(char* a,unsigned int s);/在first前面插入起始地址為a，大小為s的節(jié)點void Delete(Node* n);/刪除節(jié)點iNode* FindSize(unsigned int i);/從節(jié)點now開始找到下一個大小大于i的節(jié)點Node* FindAddr(char* a);/查找內(nèi)存單元a所在的已分配內(nèi)存塊之前的節(jié)點bool InNodes(char* a);/判斷內(nèi)存地址a是否在某個節(jié)點所指向的空閑塊中char* lmalloc(unsigned int s);/從節(jié)點n指向的起始地址開始分配i個內(nèi)存單元void

4、lfree(char* a,unsigned int s);/釋放起始地址為a，大小為s的內(nèi)存塊void Traverse(int i);/顯示整個線性表，i是初始地址;3.2 框圖開始向系統(tǒng)申請內(nèi)存空間初始化空閑表，創(chuàng)建一個List類的對象，建立頭指針和起始查找指針。顯示菜單xm讓用戶輸入要分配的內(nèi)存大小(s)f輸入數(shù)據(jù)是否越界yn讓用戶輸入要釋放的內(nèi)存的起始地址(a)輸入地址越界或未被分配？yyn讓用戶輸入要釋放的內(nèi)存大小(s)退出輸入數(shù)據(jù)是否越界調(diào)用List:lmalloc(unsigned int s)n調(diào)用List:lfree(char* a,unsigned int s)顯示空閑內(nèi)

5、存表圖一 總體框架圖char* lmalloc(unsigned int s)遍歷空閑內(nèi)存表，看是否有size=s的節(jié)點y把該節(jié)點的起始地址加上s，大小減去s。n顯示已經(jīng)沒有可分配的內(nèi)存了，然后退出。該節(jié)點大小是否為0返回找到的節(jié)點原來的起始地址刪除該節(jié)點yn圖二 內(nèi)存分配框圖void lfree(char* a,unsigned int s)空閑內(nèi)存表是否為空新建節(jié)點，其起始地址為a，大小為s。將頭指針和起始查找指針指向它。然后退出yn找到a之前的空閑塊節(jié)點na在頭節(jié)點的起始地址之前？yna+s在頭節(jié)點起始地址之前？若(a+s)=first-addr則令first-addr=a， first

6、-size加s，否則創(chuàng)建一個起始地址為a，大小為s的節(jié)點，將頭指針和起始查找指針指向它。yn是尾節(jié)點？若n-addr+n-size=a則n-size加s，否則創(chuàng)建一個起始地址為a，大小為s的節(jié)點作為尾節(jié)點。a+s在n-next的起始地址之前？報錯并退出ynyn要釋放的內(nèi)存塊與前后都相連？要釋放的內(nèi)存塊與后面相連？要釋放的內(nèi)存塊與前面相連？yn-size加上(n-next-size+s)，刪除n-nextyynnn令n-next-addr=a; n-next-size加上s;在n之后創(chuàng)建一個起始地址為a，大小為s的節(jié)點。n-size加上s圖三 循環(huán)首次適應(yīng)法4 實驗任務(wù)l 閱讀并調(diào)試循環(huán)首次適應(yīng)

7、算法；循環(huán)首次適應(yīng)算法(Next Fit)是首次適應(yīng)算法的變種。在分配內(nèi)存空間時，不再每次從表頭（鏈?zhǔn)祝╅_始查找，而是從上次找到空閑區(qū)的下一個空閑開始查找，直到找到第一個能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑區(qū)分布得較均勻。l 編寫首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法其中的一個。首次適應(yīng)算法代碼：Node* List:FindSizeFirst(unsigned int s)if(first=NULL)return NULL;/如果空閑表為空，則返回空else if(now-next=now)/如果空閑表只有一個節(jié)點，且這個節(jié)點的

8、大小不小于s，則返回這個節(jié)點，否則返回空if(now-size=s)return now;else return NULL;else/否則遍歷整個表，尋找第一個合適的節(jié)點Node* e=first;Node* aa=first;doif(aa-size=s)break;else aa=aa-next;while(aa!=e-prior);if(aa-size=s)return aa;else return NULL;圖 四 效果圖圖 五 效果圖結(jié)果分析與體會： 本次實驗主要是讓大家了解上面的幾個算法，循環(huán)首次適應(yīng)算法、首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法。了解它們各自的算法，以及知道他們的流程圖，知道他們之間的區(qū)別，這樣我們才能夠真正的理解這次實驗的主要內(nèi)容。最佳適應(yīng)算法（Best Fit）從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區(qū)分配。該算法保留大的空閑區(qū)，但造成許多小的空閑區(qū)。最壞適應(yīng)分配算法要掃描整個空閑分區(qū)或鏈表，總是挑選一個最大的空閑分區(qū)分割給作業(yè)使用。該算法要求將所有的空閑分區(qū)按其容量從大到小的順序形成一空閑分區(qū)鏈，查找時只要看第一個