操作系統(tǒng)課程設(shè)計報告

1、課程設(shè)計說明書嵌入式操作系統(tǒng)課程設(shè)計題目: 內(nèi)存管理算法模擬 院 系： 計算機科學(xué)與工程學(xué)院 專業(yè)班級： 學(xué) 號： 學(xué)生姓名： 指導(dǎo)教師： 2014年 11月 25日 安徽理工大學(xué)課程設(shè)計（論文）任務(wù)書 計算機 院系 軟件 教研室學(xué) 號學(xué)生姓名專業(yè)（班級）物聯(lián)網(wǎng)工程設(shè)計題目內(nèi)存管理算法模擬設(shè)計技術(shù)參數(shù)了解內(nèi)存分配方式掌握動態(tài)分區(qū)分配的一些算法首次適應(yīng)算法(FIRST FIT)循環(huán)首次適應(yīng)算法(NEXT FIT)最佳適應(yīng)算法(BEST FIT)快速適應(yīng)算法(QUICK FIT)用高級語言模擬內(nèi)存管理算法程序設(shè)計要求(1) 對內(nèi)存管理算法用高級語言進行模擬。(2)對程序的一些部分要有較詳細的分析說

2、明。(3)源代碼格式要規(guī)范。(4)設(shè)計合適的測試用例對程序進行測試。(5)總結(jié)要深刻，能說明問題。(6)按期提交完整的程序代碼、可執(zhí)行程序和課程設(shè)計報告。工作量課程設(shè)計任務(wù)要求不少于10頁的報告，要賦有模塊圖或流程圖。工作計劃第一周：查找相關(guān)資料，并繪制草圖。第二周：確定選用VC為編程語言。第三周：寫需求分析報告。第四周：著手進行編程，實現(xiàn)算法，并調(diào)試程序。第五周：測試程序并優(yōu)化功能，最終完成設(shè)計報告。參考資料湯小丹 梁紅兵 哲鳳屏 湯子瀛 計算機操作系統(tǒng)（第三版）西安電子科技大學(xué)出版社，20072楊克昌 王岳斌 計算機導(dǎo)論（第二版）M中國水電出版社，20053徐孝凱 C+語言基礎(chǔ)教程（第二版

3、）M 清華大學(xué)出版社，20074何欽銘 顏暉 C語言程序設(shè)計 M 浙江大學(xué)出版社，2004指導(dǎo)教師簽字教研室主任簽字 年 月 日 課程設(shè)計（論文）成績評定表指導(dǎo)教師評語：成績： 指導(dǎo)教師： 年 月 日摘要內(nèi)存管理，是指軟件運行時對計算機內(nèi)存資源的分配和使用的技術(shù)。其最主要的目的是如何高效，快速的分配，并且在適當?shù)臅r候釋放和回收內(nèi)存資源。內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運行的過程中建立分區(qū).當作業(yè)裝入主存時，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區(qū)給該作業(yè)；否則令該作業(yè)等待.分區(qū)長度不固定分區(qū)個數(shù)不固定。這種存儲管理的方法克服了固定分區(qū)嚴重浪費主存的問題，提高了

4、主存資源的利用率。動態(tài)分區(qū)分配是根據(jù)進程的實際需要，動態(tài)的為之分配內(nèi)存空間。在實現(xiàn)可變分區(qū)時，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法與回收操作等問題。為了實現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)包括空閑分區(qū)表和空閑分區(qū)鏈。內(nèi)存管理對于編寫出高效率的 Windows 程序是非常重要的，這是因為Windows 是多任務(wù)系統(tǒng)，它的內(nèi)存管理和單任務(wù)的 DOS 相比有很大的差異。DOS是單任務(wù)操作系統(tǒng)，應(yīng)用程序分配到內(nèi)存后，如果它不主動釋放，系統(tǒng)是不會對它作任何改變的；但 Windows 卻不然，它在同一時刻可能有多個應(yīng)用程序共享內(nèi)存，有時為了使某個任務(wù)更好地執(zhí)行，Windows 系

5、統(tǒng)可能會對其它任務(wù)分配的內(nèi)存進行移動，甚至刪除。因此，我們在 Windows 應(yīng)用程序中使用內(nèi)存時，要遵循Windows 內(nèi)存管理的一些約定，以盡量提高 Windows 內(nèi)存的利用率。 關(guān)鍵詞：內(nèi)存管理，內(nèi)存資源分配，動態(tài)分區(qū)分配，多任務(wù)系統(tǒng) 目錄1系統(tǒng)分析11.1問題描述11.2算法描述11.3設(shè)計目的22 系統(tǒng)設(shè)計32.1設(shè)計要求32.2設(shè)計原理32.3設(shè)計流程圖43系統(tǒng)實現(xiàn)73.1數(shù)據(jù)結(jié)構(gòu)73.2函數(shù)聲明與定義73.3運行結(jié)果84總結(jié)12參考文獻13121系統(tǒng)分析1.1問題描述系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈表中找到所需大小的分區(qū)，如果空閑分區(qū)大小大于請求分區(qū)大小，則從該分區(qū)中按改請

6、求的大小劃分出一塊內(nèi)存空間大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑鏈表中。然后，將分配區(qū)的首址返回給調(diào)用者。當進程運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)中找到相應(yīng)的插入點，此時可能出現(xiàn)以下四種情況之一：該空閑區(qū)的上下兩相鄰分區(qū)都是空閑區(qū)：將三個空閑區(qū)合并為一個空閑區(qū)。新空閑區(qū)的起始地址為上空閑區(qū)的起始地址，大小為三個空閑區(qū)之和?？臻e區(qū)合并后，取消可用表或自由鏈中下空閑區(qū)的表目項或鏈指針，修改上空閑區(qū)的對應(yīng)項。 該空閑區(qū)的上相鄰區(qū)是空閑區(qū)：將釋放區(qū)與上空閑區(qū)合并為一個空閑區(qū)，其起始地址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改上空閑區(qū)對應(yīng)的可用表的表目

7、項或自由鏈指針。 該空閑區(qū)的下相鄰區(qū)是空閑區(qū)：將釋放區(qū)與下空閑區(qū)合并，并將釋放區(qū)的起始地址作為合并區(qū)的起始地址。合并區(qū)的長度為釋放區(qū)與下空閑區(qū)之和。同理，合并后修改可用表或自由鏈中相應(yīng)的表目項或鏈指針。兩相鄰區(qū)都不是空閑區(qū)：釋放區(qū)作為一個新空閑可用區(qū)插入可用表或自由鏈。1.2算法描述動態(tài)分區(qū)分配是根據(jù)進程的實際需要，動態(tài)的為之分配內(nèi)存空間。在實現(xiàn)可變分區(qū)時，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法與回收操作等問題。為了實現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)包括空閑分區(qū)表和空閑分區(qū)鏈。為把一個新作業(yè)裝入內(nèi)存，必須按照一定的分配方法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給作

8、業(yè)。常用的分配算法有五種，首次適應(yīng)算法(FIRST FIT)、循環(huán)首次適應(yīng)算法(NEXT FIT)、最佳適應(yīng)算法(BEST FIT)、快速適應(yīng)算法(QUICK FIT)和最壞適應(yīng)算法(WORST FIT)。 本程序采用的是最佳適應(yīng)算法，我們以空閑分區(qū)鏈為例來說明采用最佳適應(yīng)算法的分配情況?？臻e區(qū)按容量遞增的次序排列。 分配：當進程申請存儲空間，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到第一個滿足容量要求的空閑區(qū)為止。 采用最優(yōu)適應(yīng)算法選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)。 優(yōu)點：選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。 缺點：空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其

9、一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲空間的浪費。1.3設(shè)計目的設(shè)計目的比較明確，主要有以下幾個：1.了解動態(tài)分區(qū)分配；2.了解分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)；3.掌握分區(qū)分配算法；4.掌握分區(qū)分配算法實現(xiàn)過程；5.會用高級語音模擬內(nèi)存分配。2 系統(tǒng)設(shè)計2.1設(shè)計要求1.對內(nèi)存管理算法用高級語言進行模擬。2.對程序的一些部分要有較詳細的分析說明。3.源代碼格式要規(guī)范。4.設(shè)計合適的測試用例對程序進行測試。5.總結(jié)要深刻，能說明問題。6.對程序中個功能模塊進行說明。7.按期提交完整的程序代碼、可執(zhí)行程序和課程設(shè)計報告。2.2設(shè)計原

10、理1. 最佳適應(yīng)算法思路：動態(tài)分區(qū)管理方式將內(nèi)存除操作系統(tǒng)占用區(qū)域外的空間看成一個大的空閑區(qū)。當作業(yè)要求裝入內(nèi)存時，根據(jù)作業(yè)需要內(nèi)存空間的大小 查詢內(nèi)存中的各個空閑區(qū)，當從內(nèi)存空間中找到一個大于或等于該作業(yè)大小的內(nèi)存空閑區(qū)時，選擇其中一個空閑區(qū)，按作業(yè)需求量劃出一個分區(qū)裝人該作業(yè)，作業(yè)執(zhí)行完后，其所占的內(nèi)存分區(qū)被收回，成為一個空閑區(qū)。如果該空閑區(qū)的相鄰分區(qū)也是空閑區(qū)，則需要將相鄰空閑區(qū)合并成一個空閑區(qū)。2.算法設(shè)計:采用最優(yōu)適應(yīng)算法，每次為作業(yè)分配內(nèi)存時，總是把既能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)。 但最優(yōu)適應(yīng)算法容易出現(xiàn)找到的一個分區(qū)可能只比作業(yè)所需求的長度略大一點的情行，這時，空閑區(qū)

11、分割后剩下的空閑區(qū)就很小以致很難再使用，降低了內(nèi)存的使用率。為解決此問題，設(shè)定一個限值minsize，如果空閑區(qū)的大小減去作業(yè)需求長度得到的值小于等于minsize，不再將空閑區(qū)分成己分分區(qū)和空閑區(qū)兩部分，而是將整個空閑區(qū)都分配給作業(yè)。3.內(nèi)存分配與回收所使用的結(jié)構(gòu)體： 為便于對內(nèi)存的分配和回收，建立兩張表記錄內(nèi)存的使用情況。一張為記錄作業(yè)占用分區(qū)的“內(nèi)存分配表”，內(nèi)容包括分區(qū)起始地址、長度、作業(yè)名/標志（為0時作為標志位表示空欄目）；一張為記錄空閑區(qū)的“空閑分區(qū)表”，內(nèi)容包括分區(qū)起始地址、長度、標志（0表空欄目，1表未分配）。兩張表都采用順序表形式。4.關(guān)于分配留下的內(nèi)存小碎片問題：當要裝入

12、一個作業(yè)時，從“空閑分區(qū)表”中查找標志為“1”（未分配）且滿足作業(yè)所需內(nèi)存大小的最小空閑區(qū)，若空閑區(qū)的大小與作業(yè)所需大小的差值小于或等于minsize，把該分區(qū)全部分配給作業(yè)，并把該空閑區(qū)的標志改為“0”（空欄目）。同時，在已分配區(qū)表中找到一個標志為“0”的欄目登記新裝人作業(yè)所占用分區(qū)的起始地址，長度和作業(yè)名。若空閑區(qū)的大小與作業(yè)所需大小的差值大于minsize。則把空閑區(qū)分成兩部分，一部分用來裝入作業(yè)，另外一部分仍為空閑區(qū)。這時只要修改原空閑區(qū)的長度，且把新裝人的作業(yè)登記到已分配區(qū)表中。5.內(nèi)存的回收：在動態(tài)分區(qū)方式下回收內(nèi)存空間時，先檢查是否有與歸還區(qū)相鄰的空閑區(qū)（上鄰空閑區(qū)，下鄰空閑區(qū)）

13、。若有，則將它們合件成一個空閑區(qū)。程序?qū)崿F(xiàn)時，首先將要釋放的作業(yè)在“內(nèi)存分配表”中的記錄項的標志改為“0”（空欄目），然后檢查“空閑區(qū)表”中標志為1（未分配）的欄目，查找是否有相鄰的空閑區(qū)，若有，將之合并，并修改空閑區(qū)的起始地址和長度。2.3設(shè)計流程圖根據(jù)程序結(jié)構(gòu)分析本程序內(nèi)存分配流程圖如圖2-1所示：圖2-1內(nèi)存分配流程圖內(nèi)存回收流程圖如圖2-2所示：圖2-1內(nèi)存回收流程圖3系統(tǒng)實現(xiàn)3.1數(shù)據(jù)結(jié)構(gòu)（1）已分配表的定義：structfloat address; /已分分區(qū)起始地址 float length; /已分分區(qū)長度，單位為字節(jié) int flag; /已分配區(qū)表登記欄標志，"0

14、"表示空欄目，實驗中只支持一個字符的作業(yè)名used_tablen; /已分配區(qū)表（2）空閑分區(qū)表的定義：structfloat address;/空閑區(qū)起始地址 float length;/空閑區(qū)長度，單位為字節(jié) int flag; /空閑區(qū)表登記欄標志，用"0"表示空欄目，用"1"表示未分配free_tablem; /空閑區(qū)表 3.2函數(shù)聲明與定義/全局變量float minsize=5;int count1=0;int count2=0;#define M 10/假定系統(tǒng)允許的空閑區(qū)表最大為m#define N 10 /假定系統(tǒng)允許的最大作

15、業(yè)數(shù)量為n/函數(shù)聲明void initialize(void);int distribute(int, float);int recycle(int);void show();3.3運行結(jié)果運行結(jié)果如下所示：如圖3-1所示為程序的主界面圖3-1程序主界面如圖3-2所示為模擬內(nèi)存的分配圖3-2模擬內(nèi)存的分配如圖3-3所示為內(nèi)存分配狀況圖3-3內(nèi)存分配狀況如圖3-4為創(chuàng)建第二個進程圖3-4創(chuàng)建第二個進程如圖3-5所示為模擬內(nèi)存的回收圖3-5模擬內(nèi)存的回收如圖3-6,3-7為回收后內(nèi)存的狀況先回收作業(yè)1：圖3-6回收作業(yè)1再回收作業(yè)2：圖3-7回收作業(yè)24總結(jié)本次課程設(shè)計我做的是內(nèi)存管理算法模擬，我

16、們這次課程設(shè)計用到了五種方法實現(xiàn)內(nèi)存管理，分別是首次適應(yīng)算法(FIRST FIT)、循環(huán)首次適應(yīng)算法(NEXT FIT)、最佳適應(yīng)算法(BEST FIT)、快速適應(yīng)算法(QUICK FIT)和最壞適應(yīng)算法(WORST FIT)。每個人負責(zé)用一種算法的實現(xiàn)。我采用的分區(qū)分配算法是最佳適應(yīng)算法，通過這門課程的學(xué)習(xí)讓我充分了解了內(nèi)存管理的機制實現(xiàn)，從而更深一步的的對計算機有了很多了解，這對于以后我們的研究和學(xué)習(xí)計算機系統(tǒng)起到了很重要的作用。通過本次操作系統(tǒng)課程設(shè)計，自己的編程能力有所提高，對操作系統(tǒng)內(nèi)存分配，存儲空間的回收都有全新的認識。在這次操作系統(tǒng)課程設(shè)計中，我使用了c+編寫系統(tǒng)軟件，對操作系統(tǒng)

17、中可變分區(qū)存儲管理有了深刻的理解，但是過程中遇到了很多困難，一邊做一邊學(xué)，對c+有了比較多的理解。實驗中遇到很多問題，但是通過與組員的反復(fù)討論和溝通，上網(wǎng)查找了一些資料，終于使問題得到了解決。這次課程設(shè)計也讓我意識到團隊合作的重要性，自己一個人的力量畢竟有限，要和組員反復(fù)溝通才能獲得解決問題的多方面途徑。通過這次課程設(shè)計，我們操作系統(tǒng)這門學(xué)科有了更深的認識。讓我這學(xué)期所學(xué)的課程得到鞏固和良好的吸收，我們組對系統(tǒng)設(shè)計的理解得到進一步提高，完善了一些把握不準確的知識點。對之前學(xué)過的操作系統(tǒng)課程知識得到了復(fù)習(xí)與鞏固。認識到了對編程的不熟悉，對實踐的不足，以后要繼續(xù)努力。 參考文獻1徐孝凱.C+語言基礎(chǔ)教程（第二版）.北京:清華大學(xué)出版社,20072徐孝凱.數(shù)據(jù)結(jié)構(gòu)應(yīng)用教程（第二版）.北京:清華大學(xué)出版社,20073何欽銘 顏暉 .C語言程