操作系統(tǒng)課程設(shè)計--連續(xù)動態(tài)分區(qū)內(nèi)存管理模擬實現(xiàn)

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：29 大?。?37.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩28頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　?。ú僮飨到y(tǒng)課程設(shè)計）　　連續(xù)動態(tài)分區(qū)內(nèi)存　　管理模擬實現(xiàn)　　學(xué)生姓名： 　　學(xué)生學(xué)號： <

2、p>　　班級： 　　二〇一三年十二月　　目錄　　《操作系統(tǒng)》課程設(shè)計....................................................... 1<

3、;/p>　　引言......................................................................3　　課程設(shè)計目的和內(nèi)容 ...................................................... 3　　需求分析...........

4、..............................................................3　　概要設(shè)計...................................................................3　　開發(fā)環(huán)境...................................

5、..................................... 4　　系統(tǒng)分析設(shè)計..................................................................... 4　　有關(guān)了解內(nèi)存管理的相關(guān)理論.............................................

6、..... 4　　內(nèi)存管理概念........................................................................4　　內(nèi)存管理的必要性..............................................................4 <

7、p>　　內(nèi)存的物理組織.............................................................4 　　什么是虛擬內(nèi)存.................................................................5 　　連續(xù)動態(tài)分區(qū)內(nèi)存管理方式...........

8、........................................ 5　　單一連續(xù)分配（單個分區(qū))................................................... 5　　固定分區(qū)存儲管理...........................................................

9、....5　　可變分區(qū)存儲管理（動態(tài)分區(qū)）.............................................. 5 　　可重定位分區(qū)存儲管理........................................................5　　問題描述和分析.........

10、...........................................................6　　程序流程圖........................................................................6　　數(shù)據(jù)結(jié)構(gòu)體分析.............................

11、.....................................8　　主要程序代碼分析...............................................................9　　分析并實現(xiàn)四種內(nèi)存分配算法 .................................................

12、11　　最先適應(yīng)算.....................................................................11 　　下次適應(yīng)分配算法..........................................................13 　　最優(yōu)適

13、應(yīng)算法...............................................................16 　　最壞適應(yīng)算法......................................................... ......18　　回收內(nèi)存算法...........................

14、.....................................20　　調(diào)試與操作說明.................................................................22　　初始界面.........................................................

15、..............22　　模擬內(nèi)存分配...............................................................23　　已分配分區(qū)說明表面............................................................24<

16、p>　　空閑區(qū)說明表界面.............................................................24　　回收內(nèi)存界面.....................................................................25　　重新申請內(nèi)存界面...........

17、...............................................26.　　總結(jié)與體會...................................................................... 28　　參考文獻..........................................

18、............................... 28　　引言　　操作系統(tǒng)是最重要的系統(tǒng)軟件，同時也是最活躍的學(xué)科之一。我們通過操作系統(tǒng)可以理解計算機系統(tǒng)的資源如何組織，操作系統(tǒng)如何有效地管理這些系統(tǒng)資源，用戶如何通過操作系統(tǒng)與計算機系統(tǒng)打交道。　　存儲器是計算

19、機系統(tǒng)的重要組成部分，近年來，存儲器容量雖然一直在不斷擴大，但仍不能滿足現(xiàn)代軟件發(fā)展的需要，因此，存儲器仍然是一種寶貴而又緊俏的資源。如何對它加以有效的管理，不僅直接影響到存儲器的利用率，而且還對系統(tǒng)性能有重大影響。而動態(tài)分區(qū)分配屬于連續(xù)分配的一種方式，它至今仍在內(nèi)存分配方式中占有一席之地。　　課程設(shè)計目的和內(nèi)容：　　理解內(nèi)存管理的相關(guān)理論，掌握連續(xù)動態(tài)

20、分區(qū)內(nèi)存管理的理論；通過對實際問題的編程實現(xiàn)，獲得實際應(yīng)用和編程能力。 　　編寫程序?qū)崿F(xiàn)連續(xù)動態(tài)分區(qū)內(nèi)存管理方式，該程序管理一塊虛擬內(nèi)存，實現(xiàn)內(nèi)存分配和回收功能。分析并實現(xiàn)四種內(nèi)存分配算法，即最先適應(yīng)算法，下次最先適應(yīng)算法，最優(yōu)適應(yīng)算法，最壞適應(yīng)算法。內(nèi)存分配算法和回收算法的實現(xiàn)。　　需求分析

21、　　動態(tài)分區(qū)分配是根據(jù)進程的實際需要，動態(tài)地為之分配內(nèi)存空間。在實現(xiàn)動態(tài)分區(qū)分配時，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配和回收操作這樣三個問題。常用的數(shù)據(jù)結(jié)構(gòu)有動態(tài)分區(qū)表和動態(tài)分區(qū)鏈。在對數(shù)據(jù)結(jié)構(gòu)有一定掌握程度的情況下設(shè)計合理的數(shù)據(jù)結(jié)構(gòu)來描述存儲空間，實現(xiàn)分區(qū)存儲管理的內(nèi)存分配功能，應(yīng)該選擇最合適的適應(yīng)算法（首次適應(yīng)算法，最佳適應(yīng)算法，最后適應(yīng)算法，最壞適應(yīng)算法），在動態(tài)分區(qū)存儲管理方式中主要實

22、現(xiàn)內(nèi)存分配和內(nèi)存回收算法，在這些存儲管理中間必然會有碎片的產(chǎn)生，當(dāng)碎片產(chǎn)生時，進行碎片的拼接等相關(guān)的內(nèi)容　　概要設(shè)計　　本程序采用機構(gòu)化模塊化的設(shè)計方法，共分為四大模塊。　?、抛钕冗m應(yīng)算法實現(xiàn) 　　從空閑分區(qū)表的第一個表目起查找該表，

23、把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。　?、葡麓芜m應(yīng)分配算法實現(xiàn)　　該算法是最先適應(yīng)算法的變種。在分配內(nèi)存空間時，不再每次從表頭（鏈?zhǔn)祝╅_始查找，而是從上次找到空

24、閑區(qū)的下一個空閑開始查找，直到找到第一個能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑區(qū)分布得較均勻。　?、亲顑?yōu)適應(yīng)算法實現(xiàn)　　它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從

25、小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區(qū)分配。　?、茸顗乃惴▽崿F(xiàn)　　最壞適應(yīng)分配算法要掃描整個空閑分區(qū)或鏈表，總是挑選一個最大的空閑分區(qū)分割給作業(yè)使用。該算法要求將所有的空閑分區(qū)按其容量從大到小的順序形成一空閑分區(qū)鏈，查找時只要看第一個分區(qū)能否滿足作業(yè)要求。&

26、lt;b>　　開發(fā)環(huán)境：　　win7 下 VC++6.0　　系統(tǒng)分析設(shè)計： 　　相關(guān)算法原理，算法流程圖，涉及的數(shù)據(jù)結(jié)構(gòu)內(nèi)容都相應(yīng)包含在各章節(jié)中　　有關(guān)了解內(nèi)存管理的相關(guān)理論 <

27、p>　　內(nèi)存管理概念： 　　內(nèi)存管理，是指軟件運行時對計算機內(nèi)存資源的分配和使用的技術(shù)。其最主要的目的是如何高效，快速的分配，并且在適當(dāng)?shù)臅r候釋放和回收內(nèi)存資源。內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運行的過程中建立分區(qū).當(dāng)作業(yè)裝入主存時，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區(qū)給該作業(yè)；否則令該作業(yè)等待.分區(qū)長度不固定分區(qū)

28、個數(shù)不固定。這種存儲管理的方法克服了固定分區(qū)嚴(yán)重浪費主存的問題，提高了主存資源的利用率。　　內(nèi)存管理的必要性：　　內(nèi)存管理對于編寫出高效率的 Windows 程序是非常重要的，這是因為Windows 是多任務(wù)系統(tǒng)，它的內(nèi)存管理和單任務(wù)的 DOS 相比有很大的差異。DOS是單任務(wù)操作系統(tǒng)，應(yīng)用程序分配到內(nèi)存后，如果它不

29、主動釋放，系統(tǒng)是不會對它作任何改變的；但 Windows 卻不然，它在同一時刻可能有多個應(yīng)用程序共享內(nèi)存，有時為了使某個任務(wù)更好地執(zhí)行，Windows 系統(tǒng)可能會對其它任務(wù)分配的內(nèi)存進行移動，甚至刪除。因此，我們在 Windows 應(yīng)用程序中使用內(nèi)存時，要遵循Windows 內(nèi)存管理的一些約定，以盡量提高 Windows 內(nèi)存的利用率。 　　1.3 內(nèi)存的物理組織：<

30、;p>　　物理地址： 　　把內(nèi)存分成若干個大小相等的存儲單元，每個存儲單元占 8 位，稱作字節(jié)（byte）。每個單元給一個編號，這個編號稱為物理地址（內(nèi)存地址、絕對地址、實地址）。二、物理地址空間：物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維空間。　　什么是虛擬內(nèi)存：<

31、/b>　　虛擬內(nèi)存是內(nèi)存管理技術(shù)的一個極其實用的創(chuàng)新。它是一段程序（由操作系統(tǒng)調(diào)度），持續(xù)監(jiān)控著所有物理內(nèi)存中的代碼段、數(shù)據(jù)段，并保證他們在運行中的效率以及可靠性，對于每個用戶層（user-level）的進程分配一段虛擬內(nèi)存空間。當(dāng)進程建立時，不需要在物理內(nèi)存件之間搬移數(shù)據(jù)，數(shù)據(jù)儲存于磁盤內(nèi)的虛擬內(nèi)存空間，也不需要為該進程去配置主內(nèi)存空間，只有當(dāng)該進程被被調(diào)用的時候才會被加載到主內(nèi)存。&l

32、t;/p>　　連續(xù)動態(tài)分區(qū)內(nèi)存管理方式的實現(xiàn)　　在早期的操作系統(tǒng)中，主存分配廣泛采用連續(xù)分配方式。連續(xù)分配方式，是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間，該連續(xù)內(nèi)存空間指的的是物理內(nèi)存。下面介紹連續(xù)分配的四種方式。　　單一連續(xù)分配（單個分區(qū)）　　最簡單的存儲管理方式，用于多道程序設(shè)計

33、技術(shù)之前。內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)由操作系統(tǒng)使用。用戶區(qū)作為一個連續(xù)的分區(qū)分配給一個作業(yè)。分區(qū)存儲管理是滿足多道程序設(shè)計的最簡單的一種存儲管理方法，它允許多 4個用戶程序同時存在系統(tǒng)內(nèi)存中，即共享內(nèi)存空間。按分區(qū)劃分方式可分為固定分區(qū)和可變分區(qū)。　　固定分區(qū)存儲管理 　　把內(nèi)存的用戶區(qū)預(yù)先劃分成多個分區(qū)，

34、每個分區(qū)大小可以相同，也可以不同。（分區(qū)的劃分由計算機的操作員或者由操作系統(tǒng)給出，并給出主存分配表）分區(qū)個數(shù)固定，分區(qū)的大小固定。一個分區(qū)中可裝入一個作業(yè)，作業(yè)執(zhí)行過程中不會改變存放區(qū)域。早期的 IBM 的 OS/MFT（具有固定任務(wù)數(shù)的多道程序系統(tǒng)）采用了這種固定分區(qū)的方法。　　可變分區(qū)存儲管理（動態(tài)分區(qū)）　　內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運行

35、的過程中建立分區(qū).當(dāng)作業(yè)裝入主存時，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區(qū)給該作業(yè)；否則令該作業(yè)等待。分區(qū)長度不固定分區(qū)個數(shù)不固定。這種存儲管理的方法克服了固定分區(qū)嚴(yán)重浪費主存的問題，提高了主存資源的利用率。ＩＢＭ操作系統(tǒng)ＯＳ／ＭＶＴ采用可變分區(qū)存儲管理。　　可重定位分區(qū)存儲管理 　　解決碎片問題的一種簡單方法是

36、采用可重定位分區(qū)分配.。其中心思想是，把不同程序，且在內(nèi)存中地址不連續(xù)的想法讓他們連續(xù)。　　例：內(nèi)存中現(xiàn)有 3 個空閑區(qū)，現(xiàn)有一作業(yè)到達，要求獲得 30k 內(nèi)存空間，沒有分區(qū)滿足容量要求，若想把作業(yè)裝入，可將內(nèi)存中所有作業(yè)進行移動，這樣把原來分散的空閑區(qū)匯集成一個大的空閑區(qū)。將內(nèi)存中的作業(yè)進行移動使它們連接在一起把原來分散的多個小分區(qū)拼接成一個大的空閑區(qū).這個過程稱為”緊湊”或”移動”。需

37、解決的問題:每次”緊湊”后程序或數(shù)據(jù)裝入的物理地址變化采用動態(tài)重定位。　　問題描述和分析　　系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈表中找到所需大小的分區(qū)，如果空閑分區(qū)大小大于請求分區(qū)大小，則從該分區(qū)中按改請求的大小劃分出一塊內(nèi)存空間大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑鏈表中。然后，將分配區(qū)的首址返回給調(diào)

38、用者。　　當(dāng)進程運行完畢師范內(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)項。

39、　?、圃摽臻e區(qū)的上相鄰區(qū)是空閑區(qū)：將釋放區(qū)與上空閑區(qū)合并為一個空閑區(qū)，其起始地址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改上空閑區(qū)對應(yīng)的可用表的表目項或自由鏈指針。 　?、窃摽臻e區(qū)的下相鄰區(qū)是空閑區(qū)：將釋放區(qū)與下空閑區(qū)合并，并將釋放區(qū)的起始地址作為合并區(qū)的起始地址。合并區(qū)的長度為釋放區(qū)與下空閑區(qū)之和。同理，合并后修改可用表或自由鏈中相應(yīng)的表目項或鏈指針。&

40、lt;/p>　?、葍上噜弲^(qū)都不是空閑區(qū)：釋放區(qū)作為一個新空閑可用區(qū)插入可用表或自由鏈。　　程序流程圖　　內(nèi)存分配流程圖，如圖　　內(nèi)存回收流程圖，如圖　　數(shù)據(jù)結(jié)構(gòu)體分析&

41、lt;/p>　　⑴進程屬性結(jié)構(gòu)體　　typedef struct readyque　　{　　char name[10];　　int size;<

42、/b>　　}readyque,*readyqueue;　?、瓶臻e鏈表結(jié)構(gòu)體　　typedef struct idlyspace　　{

43、;　　int from;　　int size;　　idlyspace * next;　　}idlyspace,*idly;　?、且逊峙滏湵斫Y(jié)構(gòu)體<

44、p>　　typedef struct busyspace　　{　　int from;　　readyque r;　　busyspace * next;

45、　　}busyspace,*busy　　主要程序代碼分析　?、胖骱瘮?shù)//代碼請?zhí)砑舆m當(dāng)?shù)淖⑨尅?lt;/p>　　int main()　　{　　Is=(idly)mall

46、oc(sizeof(idlyspace));　　Is->from=0;　　Is->size=256;　　Is->next=NULL;　　Is2=Is;　　Bs=(busy)m

47、alloc(sizeof(busyspace));　　Bs->next=NULL;　　int t,t1;　　printf("\n.......................歡迎來到動態(tài)分區(qū)存儲管理系統(tǒng)..................\n\n")

48、;　　printf("...........................請選擇要執(zhí)行的算法:...........................\n");　　printf("......................... 1.最先適應(yīng)算法 ...............................\n&quo

49、t;);　　printf("......................... 2.下次適應(yīng)算法 ............................\n");　　printf("..........................3.最優(yōu)適應(yīng)算法 ...............................\n&q

50、uot;);　　printf("......................... 4.最壞適應(yīng)算法 ................................\n");　　printf(".................................................................

51、.......\n");　　printf("請輸入您的選擇:");　　scanf("%d",&t);　　int i;　　while(i!=5)<p

52、>　　{　　printf("........................................................................\n");　　printf(".........................操作菜單如下：（請選擇）...

53、....................n");　　printf("..........................1.輸入進程分配空間 ...........................n");　　printf("......................... 2.進程撤銷回收空間 .........

54、..................\n");　　printf("......................... 3.輸出所有空閑分區(qū) ..........................\n");　　printf("..........................4.輸出所有已分配分區(qū).........

55、.................\n");　　printf(".......................... 5.退出 ..........................\n");　　printf(".........................................

56、...............................\n");　　scanf("%d",&i);　　switch(i)　　{　　c

57、ase 1:　　switch(t)　　{　　case 1:　　t1=FF();

58、　　break;　　case 2:　　t1=NF();　　break;　　case

59、 3:　　t1=BF();　　break;　　case 4:　　t1=WF();

60、　　break;　　default:　　printf("選擇算法錯誤\n");　　return 1;

61、;　　}　　if(t1)　　printf("分配空間成功\n");　　else　　printf("分配空間失敗\n");</p&g

62、t;　　break;　　case 2:　　t1=recover();　　if(t1)　　printf("回收成功\n"

63、;);　　else　　printf("回收失敗\n");　　break;　　case 3:　　I

64、sprint();　　break;　　case 4:　　Bsprint();　　break;　　}

65、　　}　　return 0;　　}　　第三章：分析并實現(xiàn)四種內(nèi)存分配算法

66、最先適應(yīng)算法　　空閑區(qū)按地址從小到大的次序排列。　　分配：當(dāng)進程申請大小為 SIZE 的內(nèi)存時，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到容量滿足要求（≥SIZE）的空閑區(qū)為止。從該空閑區(qū)中劃出大小為 SIZE的分區(qū)分配給進程，余下的部分仍作為一個空閑區(qū)，但要修改其首址和大小。 　　優(yōu)點：這種算法是

67、盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址 6部分的大空閑區(qū)，有利于大作業(yè)的裝入。　　缺點:主存低地址和高地址分區(qū)利用不均衡。在低地址部分集中了許多非常小的空閑區(qū)碎片降低了主存的利用率。　　最先適應(yīng)算法　　int FF()<

68、/p>　　{　　int t=0;　　readyque D;　　printf“"請輸入進程名:\”");　　scanf“"%”",

69、D.name);　　printf“"輸入進程申請空間大小:\”");　　scanf“"%”",&D.size);　　idly l=Is;　　int mt=256;　　busy b=B

70、s;　　idly min=NULL;　　while(l)　　//尋找空閑表中大小滿足申請進程所需大小并且起址最小的空閑結(jié)點　　{　　if(D.size<=l->size)&l

71、t;/p>　　{　　if(l->from<mt)　　{ mt=l->from; min=l; t=1;　　}　　}

72、;　　l=l->next;　　}　　if(mt!=256)//如果找到則為進程分配空間　　{　　busy j;<

73、;/b>　　j=(busy)malloc(sizeof(busyspace));　　j->from=min->from;　　for(int i=0;i<10;i++)　　{<p&g

74、t;　　j->r.name[i]=D.name[i];　　}　　j->r.size=D.size;　　while(b->next)　　{ if(b->next->from<j->from)&l

75、t;/p>　　b=b->next; else　　break;　　}　　j->next=b->next;　　b->next=j;

76、;　　min->from=min->from+D.size;　　min->size=min->size-D.size;　　}　　return t;&l

77、t;b>　　}　　下次適應(yīng)分配算法 　　最先適應(yīng)算法的變種。　　總是從空閑區(qū)上次掃描結(jié)束處順序查找空閑區(qū)表（鏈），直到找到第一個滿足容量要求的空閑區(qū)為止，分割一部分給作業(yè)，剩余部分仍作為空閑區(qū)。<b&g

78、t;　　下次適應(yīng)分配算法　　int NF()　　{　　int t=0;　　readyque D;

79、　　printf“"請輸入進程名:\”");　　scanf“"%”",D.name);　　printf“"輸入進程申請空間大小:\”");　　scanf“"%”",&D.size);

80、　int mt=256;　　idly l=Is2;　　idly min=NULL;　　busy b=Bs;　　while(l)　　//尋找空閑表中大小滿足申請進程所需大小并且起址最小的空閑結(jié)點

81、　　{　　if(D.size<=l->size)　　{　　if(l->from<mt)　　{ mt=l->from; min

82、=l; t=1;　　}　　}　　l=l->next;　　}　　if(mt!=256)//如果

83、找到則為進程分配空間　　{　　busy j;　　j=(busy)malloc(sizeof(busyspace));　　j->from=min->from;&l

84、t;p>　　for(int i=0;i<10;i++)　　{　　j->r.name[i]=D.name[i];　　}　　j->r.size=D.size;

85、;　　while(b->next)　　{ if(b->next->from<j->from)　　b=b->next; else　　break;　　}</

86、b>　　//將申請空間進程插入到已分配鏈表中　　j->next=b->next;　　b->next=j;　　//修改相應(yīng)空閑節(jié)點的起址和大小　　min->from=min->from+D.siz

87、e;　　min->size=min->size-D.size;　　Is2=min->next;//ls2指向修改結(jié)點的下一個結(jié)點　　t=1;　　return t;

88、;　　}　　l=Is;//l指向空閑表的頭　　while(l!=Is2)//循環(huán)查找　　{　　if(D.size<=l->s

89、ize)　　{　　if(l->from<mt)　　{ mt=l->from; min=l; t=1;　　}　　}<

90、;/b>　　l=l->next;　　}　　if(mt!=256)　　{　　busy j;</p&g

91、t;　　j=(busy)malloc(sizeof(busyspace));　　j->from=min->from;　　for(int i=0;i<10;i++)　　{　　j->r.nam

92、e[i]=D.name[i];　　}　　j->r.size=D.size;　　while(b->next)　　{ if(b->next->from<j->from)<p

93、>　　b=b->next; else　　break;　　}　　j->next=b->next;　　b->next=j;　　m

94、in->from=min->from+D.size;　　min->size=min->size-D.size;　　Is2=min->next;　　t=1;　　return t;</

95、b>　　}　　return t;　　}　　最優(yōu)適應(yīng)算法　　空閑區(qū)按容量遞

96、增的次序排列。　　分配：當(dāng)進程申請存儲空間，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到第一個滿足容量要求的空閑區(qū)為止。采用最優(yōu)適應(yīng)算法選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)。 　　優(yōu)點：選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。 　　缺點：空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二

97、，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲空間的浪費。　　最優(yōu)適應(yīng)算法　　int BF()　　{

98、;　　int t=0;　　readyque D;　　printf“"請輸入進程名:\”");　　scanf“"%”",D.name);　　printf“"輸入進程申請空間大小:\”&q

99、uot;);　　scanf“"%”",&D.size);　　idly l=Is;　　idly min=NULL;　　int mt=256;　　busy b=Bs;

100、;　　while(l)　　//在空閑鏈中尋找第一個大于所輸入的進程大小的空閑塊　　{　　if(D.size<=l->size)　　{</p&

101、gt;　　if(l->size<mt)　　{ 　　mt=l->size; min=l; t=1;　　}　　}</

102、p>　　l=l->next;　　}　　if(mt!=256)//找到第一個滿足要求的空閑塊　　{　　busy j;</b

103、>　　j=(busy)malloc(sizeof(busyspace));//申請分配用于存放進程的內(nèi)存空間　　j->from=min->from;　　//將第一個滿足要求的空閑塊（min）的首地址賦給j　　for(int i=0;i&l

104、t;10;i++)　　{　　j->r.name[i]=D.name[i];　　}　　j->r.size=D.size;　　while(b-&g

105、t;next)　　//按從小到大的順序查找新進程在已分配區(qū)中的位置　　{ if(b->next->from<j->from)　　b=b->next; else　　break;

106、;　　}　　j->next=b->next;　　b->next=j;//將所輸入的進程插入進程鏈　　min->from=min->from+D.size;//改變該空閑塊的起始地址

107、;　　min->size=min->size-D.size;//改變該空閑塊的剩余大小　　}　　return t;　　}<p&

108、gt;　　最壞適應(yīng)算法 　　為了克服最佳適應(yīng)算法把空閑區(qū)切割得太小的缺點，人們提出了一種最壞適應(yīng)算法，即每次分配時，總是將最大的空閑區(qū)切去一部分分配給請求者，剩余的部分仍是一個較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。 　　要求空閑區(qū)按容量遞減的順序排列。 　　分配：進程申請

109、存儲區(qū)時，檢查空閑區(qū)表（鏈）的第一個空閑區(qū)的大小是否滿足要求，若不滿足則令進程等待；若滿足則從該空閑區(qū)中分配一部分存儲區(qū)給用戶，剩下的部分仍作為空閑區(qū)。　　最壞適應(yīng)算法　　int WF()　　{<

110、;/p>　　int t=0;　　readyque D;　　printf“"請輸入進程名:\”");　　scanf“"%”",D.name);　　printf“&quo

111、t;輸入進程申請空間大小:\”");　　scanf“"%”",&D.size);//輸入進程申請的空間大小　　idly l=Is;//l指向空閑鏈表ls頭　　idly min=NULL;　　int mt

112、=0;　　busy b=Bs;//b指向已分配鏈表Bs頭　　//找到空閑分區(qū)中大小滿足進程的請求且尺寸最大的結(jié)點　　while(l)　　{

113、　　if(D.size<=l->size)　　//判斷進程所申請的大小是否小于空閑區(qū)的各結(jié)點大小　　{　　if(l->size>mt)　　{</

114、p>　　mt=l->size;　　min=l;//min指向空閑區(qū)中尺寸最大的結(jié)點 　　t=1;　　}　　}</p&g

115、t;　　l=l->next;//l指向空閑鏈表下一個結(jié)點　　}　　if(mt!=0)//判斷是否找到了空閑區(qū)的滿足結(jié)點　　{<

116、b>　　busy j;　　j=(busy)malloc(sizeof(busyspace));　　j->from=min->from;　　for(int i=0;i<10;i++)　　{&l

117、t;/p>　　j->r.name[i]=D.name[i];　　}　　j->r.size=D.size;　　while(b->next)//尋找插入到已分配鏈表中的位置

118、{ if(b->next->from<j->from)　　b=b->next; else　　break;　　}　　//把此進程結(jié)點j插入到已分配鏈表中</p&g

119、t;　　j->next=b->next;　　b->next=j;　　//修改空閑鏈表的相應(yīng)結(jié)點的參數(shù)　　min->from=min->from+D.size;　　min->size=min->size-D.s

120、ize;　　}　　return t;　　}　　可變分區(qū)的回收　　當(dāng)某個進程釋放

121、某存儲區(qū)時，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)去，否則把釋放區(qū)作為一個空閑區(qū)插入到空閑表的適當(dāng)位置。　　釋放區(qū)與空閑區(qū)相鄰的四種情況。　　釋放區(qū)與前空閑區(qū)相鄰：把釋放區(qū)與前空閑區(qū)合并到一個空閑區(qū)。其首址仍為前空閑區(qū)首址，大小為釋放區(qū)大小與空閑區(qū)大小之和。　　釋放區(qū)與后空閑

122、區(qū)相鄰：則把釋放區(qū)合并到后空閑區(qū)，其首地址為釋放區(qū)首地址，大小為二者之和。　　釋放區(qū)與前后兩空閑區(qū)相鄰：這三個區(qū)合為一個空閑區(qū)，首地址為前空閑區(qū)首址，大小為這三個空閑區(qū)之和，并取消后空閑區(qū)表目。　　釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個空閑區(qū)，將其大小和首址插入到空閑區(qū)表的適當(dāng)位置。　　回收

123、內(nèi)存算法　　int recover()　　{　　readyque D;　　printf“"請輸入想要回收的進程名\”");　　scanf“"%

124、”",D.name);　　busy b=Bs;　　idly l=Is;　　while(b->next) //查找輸入的進程名是否在已分配鏈表中　　{　　bool

125、yo=1;　　for(int i=0;i<10;i++)　　{　　if(b->next->r.name[i]==D.name[i]) yo=yo*1;　　else yo=0;

126、　　}　　//如果在已分配鏈表中則釋放該結(jié)點所占空間　　if(yo)　　{　　int t=b->next->from;&l

127、t;p>　　int ts=b->next->r.size;　　while(l)　　{ if(l->from>t+ts)//所回收進程與空閑結(jié)點上下都不鄰接 　　{ <

128、p>　　idly tl;　　tl=(idly)malloc(sizeof(idlyspace));　　tl->from=t;　　tl->size=ts;　　tl->next=l; <

129、;p>　　Is=tl;　　break; 　　}　　if(l->from==t+ts)//所回收進程與空閑結(jié)點下鄰接 {　　l->

130、from=t;　　l->size=l->size+ts;　　busy tb=b->next;　　b->next=b->next->next;　　free(tb);<p&

131、gt;　　return 1;　　} 　　if(l->from+l->size<t)//所回收進程與空閑結(jié)點上下都不鄰接 {　　idly tl;<

132、;p>　　tl=(idly)malloc(sizeof(idlyspace));　　tl->from=t;　　tl->size=ts;　　tl->next=l->next;　　l->next=tl;<p&g

133、t;　　break; 　　} 　　else if(l->from+l->size==t)//所回收進程與空閑結(jié)點上鄰接 {　　l->size=l->size+ts;

134、　　if(l->from+l->size==l->next->from)//所回收進程與空閑結(jié)點上下都鄰接　　{　　l->size=l->size+l->next->size;　　idly tm=l->next;<

135、;/p>　　l->next=l->next->next;　　freI);　　}　　br　　l=l->nex

136、t;　　}　　//從已分配鏈表中釋放所回收進程　　busy tb=b->next;　　b->next=b->next->next;　　free(tb)

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

操作系統(tǒng)課程設(shè)計--連續(xù)動態(tài)分區(qū)內(nèi)存管理模擬實現(xiàn)

文檔簡介

溫馨提示

最新文檔

評論

操作系統(tǒng)課程設(shè)計--連續(xù)動態(tài)分區(qū)內(nèi)存管理模擬實現(xiàn)

文檔簡介

溫馨提示

最新文檔

評論

免費下載