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

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

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

已閱讀1頁，還剩35頁未讀，繼續(xù)免費(fèi)閱讀

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

文檔簡介

1、　　《操作系統(tǒng)》課程設(shè)計　　論文題目：連續(xù)動態(tài)分區(qū)內(nèi)存管理模擬實現(xiàn) 　　所在班級： 　　學(xué)生學(xué)號： 　　學(xué)生姓名：

2、 　　任課教師： 　　完成日期： 2012年12月1日 　　《操作系統(tǒng)》課程設(shè)計1　　課程設(shè)計目的和內(nèi)容：3　　開

3、發(fā)環(huán)境：3　　系統(tǒng)分析設(shè)計：3　　第一章：有關(guān)了解內(nèi)存管理的相關(guān)理論3　　1.1 內(nèi)存管理概念：3　　1.2 內(nèi)存管理的必要性：3　　1.3 內(nèi)存的物理組

4、織：4　　1.4 什么是虛擬內(nèi)存：4　　第二章：連續(xù)動態(tài)分區(qū)內(nèi)存管理方式的實現(xiàn)4　　2.1 單一連續(xù)分配（單個分區(qū)）4　　2.2 固定分區(qū)存儲管理5　　2.3 可變分區(qū)存儲管理（動態(tài)分區(qū)）5

5、;　　2.4 可重定位分區(qū)存儲管理5　　2.5 覆蓋技術(shù)與對換技術(shù)6　　第三章：分析并實現(xiàn)四種內(nèi)存分配算法6　　3.1 最先適應(yīng)算法6　　3.2 下次適應(yīng)分配算法9　　3.3 最優(yōu)適應(yīng)算

6、法11　　3.4 最壞適應(yīng)算法13　　第四章：實現(xiàn)對分配內(nèi)存后進(jìn)行回收的算法16　　4.1 可變分區(qū)的回收16　　4.2 對可變分區(qū)回收的流程圖17　　4.3 利用可變分區(qū)的首次適應(yīng)算法，模擬內(nèi)存的分配與回收算法

7、。18　　第五章有關(guān)動態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)、存儲管理分析及實現(xiàn)虛擬內(nèi)存的算法25　　5.1 實現(xiàn)動態(tài)分區(qū)需要的數(shù)據(jù)結(jié)構(gòu)25　　5.2 可變分區(qū)存儲管理分析：26　　5.3 使用三種方法FIFO、OPI、LRU實現(xiàn)虛擬內(nèi)存頁面置換算法26

8、　　心得體會及小結(jié)：35　　參考文獻(xiàn)：36　　課程設(shè)計目的和內(nèi)容：　　理解內(nèi)存管理的相關(guān)理論，掌握連續(xù)動態(tài)分區(qū)內(nèi)存管理的理論；通過對實際問題的編程實現(xiàn)，獲得實際應(yīng)用和編程能力。　　編寫程序?qū)崿F(xiàn)連續(xù)動態(tài)分區(qū)內(nèi)存

9、管理方式，該程序管理一塊虛擬內(nèi)存，實現(xiàn)內(nèi)存分配和回收功能。　　分析并實現(xiàn)四種內(nèi)存分配算法，即首次適應(yīng)算法，循環(huán)首次適應(yīng)算法，最佳適應(yīng)算法，最壞適應(yīng)算法。內(nèi)存分配算法和回收算法的實現(xiàn)。　　開發(fā)環(huán)境：　　win7下VC++6.0<b

10、>　　系統(tǒng)分析設(shè)計：　　相關(guān)算法原理，算法流程圖，涉及的數(shù)據(jù)結(jié)構(gòu)內(nèi)容都相應(yīng)包含在各章節(jié)中 　　第一章：有關(guān)了解內(nèi)存管理的相關(guān)理論　　1.1 內(nèi)存管理概念：　　內(nèi)存管理，是指軟件運(yùn)行時對計算機(jī)內(nèi)存資源的分配和使用的技術(shù)。其最主要的目的是如何高效

11、，快速的分配，并且在適當(dāng)?shù)臅r候釋放和回收內(nèi)存資源。內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運(yùn)行的過程中建立分區(qū).當(dāng)作業(yè)裝入主存時，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區(qū)給該作業(yè)；否則令該作業(yè)等待.分區(qū)長度不固定,分區(qū)個數(shù)不固定。這種存儲管理的方法克服了固定分區(qū)嚴(yán)重浪費(fèi)主存的問題，提高了主存資源的利用率。　　1.2 內(nèi)存管理的必要性：<p

12、>　　內(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系統(tǒng)可能會對其它任務(wù)分配的內(nèi)存進(jìn)行移動，甚至刪除。因此，我們在Windows應(yīng)用程序中使

13、用內(nèi)存時，要遵循Windows內(nèi)存管理的一些約定，以盡量提高Windows內(nèi)存的利用率。　　1.3 內(nèi)存的物理組織：　　一、物理地址：　　把內(nèi)存分成若干個大小相等的存儲單元，每個存儲單元占8位，稱作字節(jié)（byte）。每個單元給一個編號，這個編號稱為物理地址（內(nèi)存地址、絕對地

14、址、實地址）。　　二、物理地址空間：　　物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維空間。　　1.4 什么是虛擬內(nèi)存：　　虛擬內(nèi)存是內(nèi)存管理技術(shù)的一個極其實用的創(chuàng)新。它是一段程序（由操作系統(tǒng)調(diào)度），持續(xù)監(jiān)控著所有物理

15、內(nèi)存中的代碼段、數(shù)據(jù)段，并保證他們在運(yùn)行中的效率以及可靠性，對于每個用戶層（user-level）的進(jìn)程分配一段虛擬內(nèi)存空間。當(dāng)進(jìn)程建立時，不需要在物理內(nèi)存件之間搬移數(shù)據(jù)，數(shù)據(jù)儲存于磁盤內(nèi)的虛擬內(nèi)存空間，也不需要為該進(jìn)程去配置主內(nèi)存空間，只有當(dāng)該進(jìn)程被被調(diào)用的時候才會被加載到主內(nèi)存。　　：連續(xù)動態(tài)分區(qū)內(nèi)存管理方式的實現(xiàn)　　在早期的操作系統(tǒng)中，主存分配廣泛

16、采用連續(xù)分配方式。　　連續(xù)分配方式，是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間，該連續(xù)內(nèi)存空間指的的是物理內(nèi)存。下面介紹連續(xù)分配的四種方式。　　2.1 單一連續(xù)分配（單個分區(qū)）　　最簡單的存儲管理方式，用于多道程序設(shè)計技術(shù)之前。　　內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)由操作系統(tǒng)

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

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

19、　　2.3 可變分區(qū)存儲管理（動態(tài)分區(qū)）　　內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運(yùn)行的過程中建立分區(qū).當(dāng)作業(yè)裝入主存時，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區(qū)給該作業(yè)；否則令該作業(yè)等待。　　分區(qū)長度不固定,分區(qū)個數(shù)不固定。　　這種存儲管理的方法克服了固定分區(qū)嚴(yán)

20、重浪費(fèi)主存的問題，提高了主存資源的利用率。　?。桑拢筒僮飨到y(tǒng)ＯＳ／ＭＶＴ采用可變分區(qū)存儲管理。　　2.4 可重定位分區(qū)存儲管理　　解決碎片問題的一種簡單方法是采用可重定位分區(qū)分配.。　　其中心思想是，把不同程序，且在內(nèi)存中地址不連續(xù)的想法讓他們連續(xù)。例：內(nèi)存中現(xiàn)有3個空

21、閑區(qū)，現(xiàn)有一作業(yè)到達(dá)，要求獲得30k內(nèi)存空間，沒有分區(qū)滿足容量要求，若想把作業(yè)裝入，可將內(nèi)存中所有作業(yè)進(jìn)行移動，這樣把原來分散的空閑區(qū)匯集成一個大的空閑區(qū)。　　將內(nèi)存中的作業(yè)進(jìn)行移動,使它們連接在一起,把原來分散的多個小分區(qū)拼接成一個大的空閑區(qū).這個過程稱為”緊湊”或”移動”。　　需解決的問題:每次”緊湊”后,程序或數(shù)據(jù)裝入的物理地址變化,采用動態(tài)重定位

22、。　　2.5 覆蓋技術(shù)與對換技術(shù)　　一、為什么引入？　　在多道環(huán)境下擴(kuò)充內(nèi)存的方法，用以解決在較小的存儲空間中運(yùn)行較大程序時遇到的矛盾。　　覆蓋技術(shù)主要用在早期的操作系統(tǒng)中。　　對換技術(shù)被廣

23、泛用于小型分時系統(tǒng)中，交換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn)。　　二、覆蓋技術(shù)　　把程序劃分為若干個功能上相對獨(dú)立的程序段，按照其自身的邏輯結(jié)構(gòu)將那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域　　程序段先保存在磁盤上，當(dāng)有關(guān)程序段的前一部分執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的

24、程序段（內(nèi)存“擴(kuò)大”了）　　覆蓋：一個作業(yè)的若干程序段，或幾個作業(yè)的某些部分共享某一個存儲空間　　一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，程序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后由由操作系統(tǒng)完成自動覆蓋。　　對換技術(shù)　　為平衡系統(tǒng)負(fù)載，通過選

25、擇一個進(jìn)程，把其暫時移出到磁盤，騰出空間給其他進(jìn)程使用，同時把磁盤中的某個進(jìn)程再換進(jìn)主存，讓其投入運(yùn)行，這種互換稱對換。　　多用于分時系統(tǒng)中　?。悍治霾崿F(xiàn)四種內(nèi)存分配算法　　3.1 最先適應(yīng)算法　　空閑區(qū)按地址從小到大的次序排列。

26、 　　分配：當(dāng)進(jìn)程申請大小為SIZE的內(nèi)存時，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到容量滿足要求（≥SIZE）的空閑區(qū)為止。從該空閑區(qū)中劃出大小為SIZE的分區(qū)分配給進(jìn)程，余下的部分仍作為一個空閑區(qū)，但要修改其首址和大小。　　優(yōu)點：這種算法是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址部分的大空閑區(qū)，有利于大作業(yè)的裝入。<

27、;p>　　缺點:主存低地址和高地址分區(qū)利用不均衡。在低地址部分,集中了許多非常小的空閑區(qū)(碎片),降低了主存的利用率。　　最先適應(yīng)算法代碼實現(xiàn)：　　#include<stdio.h>　　void main()　　{ int m,n,i,j,j0,k,k

28、0,A[30][3],B[30];　　printf("請輸入空閑分區(qū)塊數(shù):");　　scanf("%d",&m);　　printf("\n\t分區(qū)號\t\t大小\t\t起始地址\n");　　for(i=0

29、;i<m;i++)　　for(j=0;j<3;j++)　　scanf("%d",&A[i][j]);　　/* 按地址從小到大排列(直接選擇排序) */　　for(i=0;i<m-1;i++)<p

30、>　　{ k0=i;　　for(k=i+1;k<m;k++)　　if(A[k][2]<A[k0][2])k0=k;　　if(k0!=i)　　{ for(j=0;j<

31、3;j++)　　{ int t;　　t=A[k0][j];　　A[k0][j]=A[i][j];　　A[i][j]=t;　　}

32、　}　　}　　printf("\n----首次適應(yīng)算法按地址從小到大排列后空閑區(qū)----\n");　　printf("\t分區(qū)號\t\t大小\t\t起始地址\n");

33、for(i=0;i<m;i++)　　for(j=0;j<3;j++)　　{ printf("\t%d\t",A[i][j]);　　if(j==2)printf("\n");　　}

34、　　printf("\n請輸入要分配的作業(yè)數(shù):");　　scanf("%d",&n);　　printf("請輸入作業(yè)大小:\n");　　for(j0=0;j0<n;j0++)

35、　　scanf("%d",&B[j0]);　　/* 空閑表首址和大小變換 */　　i=j0=0;　　do　　{ while(A[i][1]<

36、;B[j0]&&i<m)　　i++;　　if(i==m)printf("\n內(nèi)存不足,%dK大小的作業(yè)需要等待內(nèi)存資源!\n",B[j0]);　　if(i<m)<

37、;p>　　{ A[i][1]=A[i][1]-B[j0];　　A[i][2]=A[i][2]+B[j0];　　}　　j0++;i=0;　　}while(j0<n);</p

38、>　　printf("\n----首次適應(yīng)算法分區(qū)分配后的空閑區(qū)----\n");　　printf("\t分區(qū)號\t\t大小\t\t起始地址\n");　　for(i=0;i<m;i++)　　for(j=0;j<3;j++)</p

39、>　　{ if(A[i][1]) printf("\t%d\t",A[i][j]);　　if(j==2) printf("\n");　　}　　}

40、　　運(yùn)行結(jié)果如下：　　3.2 下次適應(yīng)分配算法　　最先適應(yīng)算法的變種。　　總是從空閑區(qū)上次掃描結(jié)束處順序查找空閑區(qū)表（鏈），直到找到第一個滿足容量要求的空閑區(qū)為止，分割一部分給作業(yè)，剩余部分仍作為空閑區(qū)。　　下

41、次適應(yīng)分配算法代碼實現(xiàn)：　　void NF_Assign(unsigned size)/*循環(huán)首次適應(yīng)算法的分配*/　　{　　LN *p,*t,*s;　　p=find;&l

42、t;p>　　if (fsize <= 0)　　{　　printf("系統(tǒng)已無可用空間\n");　　return;　　}<

43、/p>　　else if (size > fsize)　　{　　printf("系統(tǒng)空間不足！分配不成功\n");　　return;<b

44、>　　}　　else if (size <= 0)　　{　　printf("大小不正確！\n");　　}

45、;　　do　　{　　if(size > p->size)　　{　　p=p->next;　　if(p

46、==find)　　{　　printf("沒有足夠大的空閑區(qū)分配！分配不成功\n"); break;　　}　　}&

47、lt;p>　　else　　{　　p->size -= size;　　p->m_addr += size;　　fsize -= size;

48、　　find=p->next;　　if(p->size==0)　　{　　t = getpch(LN);　　t=p->next;　　t->front=p->fron

49、t;　　(t->front)->next=t;　　n--;　　if (p == L) {L=t;}　　free(p);　　f

50、ind = t;　　}　　printf("\n分配成功！\n");　　break;　　}<

51、;p>　　} while (1);　　}// end of NF_Assign　　運(yùn)行結(jié)果如下：　　3.3 最優(yōu)適應(yīng)算法　　空閑區(qū)按容量遞增的次序排列。　　分配：當(dāng)進(jìn)程申請存儲空間，系

52、統(tǒng)順序查找空閑區(qū)表（鏈），直到找到第一個滿足容量要求的空閑區(qū)為止。　　采用最優(yōu)適應(yīng)算法選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)。　　優(yōu)點：選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。　　缺點：空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用

53、。隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲空間的浪費(fèi)。　　最優(yōu)適應(yīng)算法代碼實現(xiàn)：　　#include<stdio.h>　　void main()　　{ int m,n,i,j,j0,k,k0,A[30][3],B[30];

54、;　　printf("請輸入空閑分區(qū)塊數(shù):");　　scanf("%d",&m);　　printf("\t分區(qū)號\t\t大小\t\t起始地址\n");　　for(i=0;i<m;i++)<

55、p>　　for(j=0;j<3;j++)　　scanf("%d",&A[i][j]);　　/* 按空閑區(qū)的容量大小從小到大排列(直接選擇排序) */　　for(i=0;i<m-1;i++)　　{ k0=

56、i;　　for(k=i+1;k<m;k++)　　if(A[k][1]<A[k0][1])k0=k;　　if(k0!=i)　　{ for(j=0;j<3;j++)<p

57、>　　{ int t;　　t=A[k0][j];　　A[k0][j]=A[i][j];　　A[i][j]=t;　　}　　}

58、　　}　　printf("\n----最佳適應(yīng)算法按空閑區(qū)的容量從小到大排列后空閑區(qū)----\n");　　printf("\t分區(qū)號\t\t大小\t\t起始地址\n");　　for(i=0;i<m;i++)&

59、lt;/p>　　for(j=0;j<3;j++)　　{ printf("\t%d\t",A[i][j]);　　if(j==2)printf("\n");　　}

60、;　　printf("\n請輸入要分配的作業(yè)數(shù):");　　scanf("%d",&n);　　printf("請輸入作業(yè)大小:\n");　　for(j0=0;j0<n;j0++)　　scanf(&qu

61、ot;%d",&B[j0]);　　i=j0=0;　　do　　{ while(A[i][1]<B[j0]&&i<m)　　i++;&

62、lt;/b>　　if(i==m)printf("\n內(nèi)存不足,%dK大小的作業(yè)需要等待內(nèi)存資源!\n",B[j0]);　　if(i<m)　　{ A[i][1]=A[i][1]-B[j0];　　A[

63、i][2]=A[i][2]+B[j0];　　}　　j0++;　　for(i=0;i<m-1;i++)　　{ k0=i;<

64、;p>　　for(k=i+1;k<m;k++)　　if(A[k][1]<A[k0][1])k0=k;　　if(k0!=i)　　{ for(j=0;j<3;j++)　　{ int t;

65、　　t=A[k0][j];　　A[k0][j]=A[i][j];　　A[i][j]=t;　　}　　}　　}<

66、/b>　　i=0;　　}while(j0<n);　　printf("\n----最佳適應(yīng)算法分區(qū)分配后的空閑區(qū)----\n");　　printf("\t分區(qū)號\t\t大小\t\t起始地址\n

67、");　　for(i=0;i<m;i++)　　for(j=0;j<3;j++)　　{ if(A[i][1]) printf("\t%d\t",A[i][j]);　　if(j==2) printf("\n&quo

68、t;);　　}　　}　　運(yùn)行結(jié)果如下：　　3.4 最壞適應(yīng)算法　　為了克服最佳適應(yīng)算法把空閑區(qū)切割得太小的缺點，人

69、們提出了一種最壞適應(yīng)算法，即每次分配時，總是將最大的空閑區(qū)切去一部分分配給請求者，剩余的部分仍是一個較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。　　要求空閑區(qū)按容量遞減的順序排列。　　分配：進(jìn)程申請存儲區(qū)時，檢查空閑區(qū)表（鏈）的第一個空閑區(qū)的大小是否滿足要求，若不滿足則令進(jìn)程等待；若滿足則從該空閑區(qū)中分配一部分存儲區(qū)給用戶，剩下的部分仍作為空閑區(qū)。<

70、/p>　　最壞適應(yīng)算法代碼實現(xiàn)：　　#include<stdio.h>　　void main()　　{ int m,n,i,j,j0,k,k0,A[30][3],B[30];　　printf("請輸入空閑分區(qū)塊數(shù):&q

71、uot;);　　scanf("%d",&m);　　printf("\t分區(qū)號\t\t大小\t\t起始地址\n");　　for(i=0;i<m;i++)　　for(j=0;j<3;j++)&

72、lt;p>　　scanf("%d",&A[i][j]);　　/* 按空閑區(qū)的容量大小從小到大排列(直接選擇排序) */　　for(i=0;i<m-1;i++)　　{ k0=i;　　for(

73、k=i+1;k<m;k++)　　if(A[k][1]<A[k0][1])k0=k;　　if(k0!=i)　　{ for(j=0;j<3;j++)　　{ int t;

74、t=A[k0][j];　　A[k0][j]=A[i][j];　　A[i][j]=t;　　}　　}　　}</p

75、>　　printf("\n----最佳適應(yīng)算法按空閑區(qū)的容量從小到大排列后空閑區(qū)----\n");　　printf("\t分區(qū)號\t\t大小\t\t起始地址\n");　　for(i=0;i<m;i++)　　for(j=0;j<3;j+

76、+)　　{ printf("\t%d\t",A[i][j]);　　if(j==2)printf("\n");　　}　　printf("\n請輸入要分配的作業(yè)數(shù):");&l

77、t;/p>　　scanf("%d",&n);　　printf("請輸入作業(yè)大小:\n");　　for(j0=0;j0<n;j0++)　　scanf("%d",&B[j0]);<

78、;p>　　i=j0=0;　　do　　{ while(A[i][1]<B[j0]&&i<m)　　i++;　　if(i==m

79、)printf("\n內(nèi)存不足,%dK大小的作業(yè)需要等待內(nèi)存資源!\n",B[j0]);　　if(i<m)　　{ A[i][1]=A[i][1]-B[j0];　　A[i][2]=A[i][2]+B[j0];<p&g

80、t;　　}　　j0++;　　for(i=0;i<m-1;i++)　　{ k0=i;　　for(k=i+1;k<m;k++)

81、　　if(A[k][1]<A[k0][1])k0=k;　　if(k0!=i)　　{ for(j=0;j<3;j++)　　{ int t;　　t=A[k0][j];<

82、;p>　　A[k0][j]=A[i][j];　　A[i][j]=t;　　}　　}　　}　　i

83、=0;　　}while(j0<n);　　printf("\n----最佳適應(yīng)算法分區(qū)分配后的空閑區(qū)----\n");　　printf("\t分區(qū)號\t\t大小\t\t起始地址\n");　　for(i=0;

84、i<m;i++)　　for(j=0;j<3;j++)　　{ if(A[i][1]) printf("\t%d\t",A[i][j]);　　if(j==2) printf("\n");　　}&l

85、t;/b>　　}　　運(yùn)行結(jié)果如下：　　第四章：實現(xiàn)對分配內(nèi)存后進(jìn)行回收的算法　　4.1 可變分區(qū)的回收　　當(dāng)某個進(jìn)程釋放某存儲區(qū)時，系統(tǒng)首先檢查釋

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

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

88、變分區(qū)回收的流程圖　　當(dāng)對內(nèi)存進(jìn)行了為作業(yè)分配了存儲大小時，使用完后要將它回收，其回收的流程圖如下：　　4.3 利用可變分區(qū)的首次適應(yīng)算法，模擬內(nèi)存的分配與回收算法。　　一、基本思想：可變分區(qū)分配是根據(jù)進(jìn)程的實際需求，動態(tài)地為之分配內(nèi)存空間。首次適應(yīng)算法要求空閑空間鏈以地址遞增的次序鏈接。進(jìn)行內(nèi)存分配時，從鏈

89、表頭部開始依次檢索，找到第一個不小于請求空間大小的空閑空間進(jìn)行分配。分配時需考慮碎片問題，若分配會導(dǎo)致碎片產(chǎn)生則將整塊分區(qū)分配。　　二、主要數(shù)據(jù)結(jié)構(gòu)：　　struct FreeArea{ 鏈結(jié)點包含的數(shù)據(jù)：分區(qū)號、大小、起址、標(biāo)記

90、　　int ID;　　int size;　　long address;　　int sign;　　};<p&g

91、t;　　struct Node { 雙鏈表結(jié)點結(jié)構(gòu)體：數(shù)據(jù)區(qū)、前向指針、后繼指針　　FreeArea data;　　struct Node *prior; 　　struct Node *next; 　　}*DLinkList;&l

92、t;p>　　三、源程序代碼：　　#include<iostream>　　using namespace std;　　#define Free 0 //空閑狀態(tài)　　#define Busy 1 //已用狀態(tài)</p

93、>　　#define PBusy 2 //碎片已用狀態(tài)　　#define FINISH 1 //完成　　#define FINISH2 1 //完成　　#define ERROR 0 //出錯　　#define memory 512

94、 //最大內(nèi)存空間為(單位：KB）　　#define min 10 //碎片最小值(單位：KB)　　typedef struct FreeArea//空閑鏈數(shù)據(jù)　　{　　int ID;</p

95、>　　int size;　　long address;　　int sign;　　};　　typedef struct Node /

96、/空閑連結(jié)構(gòu)　　{ 　　FreeArea data;　　struct Node *prior; 　　struct Node *next; 　　}*DLinkList;

97、　　DLinkList head; //頭結(jié)點　　DLinkList tail; //尾結(jié)點　　int Create()//初始化　　{　　head=(DLinkList)malloc(sizeof(Node)

98、);//分配內(nèi)存　　tail=(DLinkList)malloc(sizeof(Node));　　head->prior=NULL;　　head->next=tail;　　tail->prior=head;　　t

99、ail->next=NULL;　　tail->data.address=0;　　tail->data.size=memory;　　tail->data.ID=0;　　tail->data.sign=Free;<p

100、>　　return FINISH;　　}　　int FirstFit(int ID,int request)//首次適應(yīng)算法　　{　　DLinkList temp=(DLinkList)ma

101、lloc(sizeof(Node));//新建作業(yè)的結(jié)點　　temp->data.ID=ID;　　temp->data.size=request;　　temp->data.sign=Busy;　　Node *p=head;//插入指針P </p&g

102、t;　　while(p)　　{　　if(p->data.sign==Free && p->data.size==request)//剩余大小恰好滿足{　　p->data.sign=B

103、usy;　　p->data.ID=ID;　　return FINISH;　　break;　　}　　else if(p->data.sign==

104、Free && p->data.size>request && (p->data.size-request>min))//滿足需求且有剩余且不產(chǎn)生碎片　　{　　temp->prior=p->prior;　　t

105、emp->next=p;　　temp->data.address=p->data.address;　　p->prior->next=temp;　　p->prior=temp;　　p->data.address=temp->d

106、ata.address+temp->data.size;　　p->data　　.size=p->data.size-request;　　return FINISH;　　break;

107、;　　}　　else if(p->data.sign==Free && p->data.size>request && p->data.size-request<=min)//產(chǎn)生碎片時　　{&l

108、t;/b>　　p->data.sign=PBusy;　　p->data.ID=ID;　　return FINISH;　　break;　　}

109、;　　p=p->next;//若前面的分區(qū)都已分配，P指針后移　　}　　return ERROR;　　}　　int Allocate()//主存分配

110、　　{　　int ID,request;　　cout<<"請輸入作業(yè)所在分區(qū)號：";　　cin>>ID;　　c

111、out<<"請輸入分配的主存(單位:KB)：";　　cin>>request;　　if(request<0 ||request==0)　　{　　cout<<"分配

112、的主存必須是正整數(shù)！"<<endl;　　return ERROR;　　}　　if(FirstFit(ID,request)==FINISH)　　cout<<"分配成功！"<&

113、lt;endl;　　else　　cout<<"內(nèi)存不足，分配失敗！"<<endl;　　}　　int Recycle(int ID)//回收</p&

114、gt;　　{　　Node *p=head;　　while(p)　　{　　if(p->data.ID==ID)

115、　　{　　p->data.sign=Free;　　//p->data.ID=Free;　　if((p->prior->data.sign==Free)&&(p->next->data.sign==Free

116、))//與前后的空閑塊相連　　{　　p->prior->data.size=p->prior->data.size+p->data.size+p->next->data.size;　　p->prior->next=p-&g

117、t;next->next;　　if(p->next->next==NULL)//若p->next是最后一個結(jié)點　　{p->prior->data.ID=Free;p->next=NULL;}　　else{p->next->next->prior=p-&g

118、t;prior;}　　break; 　　}　　if(p->prior->data.sign==Free)//與前面的空閑塊相連　　{</p&

119、gt;　　p->prior->data.size+=p->data.size;　　p->prior->next=p->next;　　p->next->prior=p->prior;　　break;&l

120、t;/p>　　}　　if(p->next->data.sign==Free)//與后面的空閑塊相連　　{　　p->data.size+=p->next->data.size;<

121、;/p>　　if(p->next->next==NULL)//若p->next是最后一個結(jié)點　　p->next=NULL;　　else{　　p->next->next->prior=p;

122、　　p->next=p->next->next;}　　break;　　}　　break;　　}

123、　　p=p->next;　　}　　cout<<"分區(qū)："<<ID<<"回收成功"<<endl;　　return FINI

124、SH;　　}　　void show()//顯示　　{　　cout<<" 主存分配情況 \n";<

125、;p>　　Node *p=head->next;　　while(p)　　{　　cout<<"分區(qū)號：";　　if(p->data.ID==Free

126、)　　cout<<"Free"<<endl;　　else　　cout<<p->data.ID<<endl;　　cout<<"起始地址：&q

127、uot;<<p->data.address;　　cout<<" 分區(qū)大?。?quot;<<p->data.size<<" KB";　　cout<<" 狀態(tài)：";　　if(p-

128、>data.sign==Free)　　cout<<"空閑"<<endl;　　else if(p->data.sign==PBusy)　　cout<<"碎片已分配"<<endl;<p&

129、gt;　　else　　cout<<"已分配"<<endl;　　p=p->next;　　}　　cout<<endl;

130、　　}　　void main()　　{　　Create();　　int choice;<

131、b>　　int i;　　for(i=0;;i++)　　{ 　　cout<<"請輸入操作：";　　cout<<"1.分配內(nèi)存 2.回收內(nèi)存

132、 3.顯示主存 0.退出";　　cout<<endl;　　cin>>choice;　　if(choice==1)// 分配內(nèi)存　　Allocate();　　else if(choice

133、==2)// 內(nèi)存回收　　{ int ID;　　cout<<"請輸入要釋放的分區(qū)號：";　　cin>>ID;　　Recycle(ID);<

134、;b>　　}　　else if(choice==3)//顯示主存　　show();　　else if(choice==0)//退出　　break;

135、　　else //非法輸入　　{　　cout<<"輸入有誤！"<<endl;　　continue;　　}</b

136、>　　}　　}　　運(yùn)行結(jié)果如下：　　第五章有關(guān)動態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)、存儲管理分析及實現(xiàn)虛擬內(nèi)存的算法　　5.

137、1 實現(xiàn)動態(tài)分區(qū)需要的數(shù)據(jù)結(jié)構(gòu)　　在動態(tài)分區(qū)存儲管理中，要有相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來登記空閑區(qū)信息，它包括空閑區(qū)的大小和位置。　　不同系統(tǒng)根據(jù)設(shè)計要求采用不同的結(jié)構(gòu)。常用的有表結(jié)構(gòu)和鏈結(jié)構(gòu)。　　系統(tǒng)還要設(shè)置了等待分區(qū)隊列，當(dāng)系統(tǒng)中無空閑區(qū)或無滿足要求的空閑區(qū)時，則把申請者送入等待隊列中，等待別的進(jìn)程釋放內(nèi)存之后再喚醒隊

138、列中的進(jìn)程。　　5.2 可變分區(qū)存儲管理分析：　　優(yōu)點:　　1.有助于多道程序設(shè)計　　2.不需過多硬件,僅需界地址寄存器用于存儲保護(hù)　　3.所采用的算法都比較簡單,易于實現(xiàn)

139、;　　缺點:　　1.碎片問題　　由于空閑區(qū)的大小與申請內(nèi)存的大小相等的情況是很少的，絕大多數(shù)情況是從一個空閑區(qū)中切去一塊，剩下的部分作為一個空閑區(qū)仍留在空閑區(qū)表中，隨著時間的推移，空閑區(qū)的發(fā)展趨勢是越來越小，直至不能滿足任何用戶要求。

140、　　這種不能被任何用戶使用的極小的空閑區(qū)稱為碎片。碎片的出現(xiàn)造成了存儲空間的浪費(fèi)。　　2.分區(qū)大小受主存容量限制,無法擴(kuò)充主存容量　　5.3 使用三種方法FIFO、OPI、LRU實現(xiàn)虛擬內(nèi)存頁面置換算法　　代碼實現(xiàn)如下：<p&

141、gt;　　//--------------- YeMianZhiHuan.cpp -----------------　　#include "iostream.h"　　const int DataMax=100;　　const int BlockNum = 10;<

142、p>　　int DataShow[BlockNum][DataMax]; // 用于存儲要顯示的數(shù)組　　bool DataShowEnable[BlockNum][DataMax]; // 用于存儲數(shù)組中的數(shù)據(jù)是否需要顯示　　//int Data[DataMax]={4,3,2,1,4,3,5,4,3,2,1,5,6,2,3,7,1,2,6,1};

143、 // 測試數(shù)據(jù)　　//int N = 20; // 輸入頁面?zhèn)€數(shù)　　int Data[DataMax]; // 保存數(shù)據(jù)　　int Block[BlockNum]; // 物理塊　　int count[BlockNum]; // 計數(shù)器<p

眾賞文庫> 全部分類> 畢業(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)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(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)

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載