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

1、計(jì)算機(jī)專業(yè)操作系統(tǒng)課程設(shè)計(jì)（操作系統(tǒng)課程設(shè)計(jì)）連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存 管理模擬實(shí)現(xiàn) 目錄操作系統(tǒng)課程設(shè)計(jì). 1 引言.3 課程設(shè)計(jì)目的和內(nèi)容 . 3 需求分析.3 概要設(shè)計(jì).3開發(fā)環(huán)境. 4系統(tǒng)分析設(shè)計(jì). 4有關(guān)了解內(nèi)存管理的相關(guān)理論. 4內(nèi)存管理概念.4 內(nèi)存管理的必要性.4 內(nèi)存的物理組織.4 什么是虛擬內(nèi)存.5 連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式. 5單一連續(xù)分配（單個(gè)分區(qū)). 5 固定分區(qū)存儲(chǔ)管理.5可變分區(qū)存儲(chǔ)管理（動(dòng)態(tài)分區(qū)）. 5 可重定位分區(qū)存儲(chǔ)管理.5問題描述和分析.6程序流程圖.6數(shù)據(jù)結(jié)構(gòu)體分析.8主要程序代碼分析.9分析并實(shí)現(xiàn)四種內(nèi)存分配算法 . 11最先適應(yīng)算.11 下次適應(yīng)分

2、配算法.13 最優(yōu)適應(yīng)算法.16 最壞適應(yīng)算法. .18回收內(nèi)存算法.20調(diào)試與操作說明.22初始界面.22模擬內(nèi)存分配.23已分配分區(qū)說明表面.24空閑區(qū)說明表界面.24回收內(nèi)存界面.25重新申請(qǐng)內(nèi)存界面.26.總結(jié)與體會(huì). 28參考文獻(xiàn). 28引言操作系統(tǒng)是最重要的系統(tǒng)軟件，同時(shí)也是最活躍的學(xué)科之一。我們通過操作系統(tǒng)可以理解計(jì)算機(jī)系統(tǒng)的資源如何組織，操作系統(tǒng)如何有效地管理這些系統(tǒng)資源，用戶如何通過操作系統(tǒng)與計(jì)算機(jī)系統(tǒng)打交道。存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，近年來，存儲(chǔ)器容量雖然一直在不斷擴(kuò)大，但仍不能滿足現(xiàn)代軟件發(fā)展的需要，因此，存儲(chǔ)器仍然是一種寶貴而又緊俏的資源。如何對(duì)它加以有效的管理

3、，不僅直接影響到存儲(chǔ)器的利用率，而且還對(duì)系統(tǒng)性能有重大影響。而動(dòng)態(tài)分區(qū)分配屬于連續(xù)分配的一種方式，它至今仍在內(nèi)存分配方式中占有一席之地。課程設(shè)計(jì)目的和內(nèi)容： 理解內(nèi)存管理的相關(guān)理論，掌握連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理的理論；通過對(duì)實(shí)際問題的編程實(shí)現(xiàn)，獲得實(shí)際應(yīng)用和編程能力。 編寫程序?qū)崿F(xiàn)連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式，該程序管理一塊虛擬內(nèi)存，實(shí)現(xiàn)內(nèi)存分配和回收功能。 分析并實(shí)現(xiàn)四種內(nèi)存分配算法，即最先適應(yīng)算法，下次最先適應(yīng)算法，最優(yōu)適應(yīng)算法，最壞適應(yīng)算法。內(nèi)存分配算法和回收算法的實(shí)現(xiàn)。需求分析動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配時(shí)，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)

4、分配算法和分區(qū)的分配和回收操作這樣三個(gè)問題。常用的數(shù)據(jù)結(jié)構(gòu)有動(dòng)態(tài)分區(qū)表和動(dòng)態(tài)分區(qū)鏈。在對(duì)數(shù)據(jù)結(jié)構(gòu)有一定掌握程度的情況下設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)來描述存儲(chǔ)空間，實(shí)現(xiàn)分區(qū)存儲(chǔ)管理的內(nèi)存分配功能，應(yīng)該選擇最合適的適應(yīng)算法（首次適應(yīng)算法，最佳適應(yīng)算法，最后適應(yīng)算法，最壞適應(yīng)算法），在動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式中主要實(shí)現(xiàn)內(nèi)存分配和內(nèi)存回收算法，在這些存儲(chǔ)管理中間必然會(huì)有碎片的產(chǎn)生，當(dāng)碎片產(chǎn)生時(shí)，進(jìn)行碎片的拼接等相關(guān)的內(nèi)容概要設(shè)計(jì)本程序采用機(jī)構(gòu)化模塊化的設(shè)計(jì)方法，共分為四大模塊。最先適應(yīng)算法實(shí)現(xiàn) 從空閑分區(qū)表的第一個(gè)表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時(shí)間。為適應(yīng)這種算法，空

5、閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進(jìn)行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。下次適應(yīng)分配算法實(shí)現(xiàn)該算法是最先適應(yīng)算法的變種。在分配內(nèi)存空間時(shí)，不再每次從表頭（鏈?zhǔn)祝╅_始查找，而是從上次找到空閑區(qū)的下一個(gè)空閑開始查找，直到找到第一個(gè)能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑區(qū)分布得較均勻。最優(yōu)適應(yīng)算法實(shí)現(xiàn)它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進(jìn)行排序，自表頭開始查找到

6、第一個(gè)滿足要求的自由分區(qū)分配。最壞算法實(shí)現(xiàn)最壞適應(yīng)分配算法要掃描整個(gè)空閑分區(qū)或鏈表，總是挑選一個(gè)最大的空閑分區(qū)分割給作業(yè)使用。該算法要求將所有的空閑分區(qū)按其容量從大到小的順序形成一空閑分區(qū)鏈，查找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。開發(fā)環(huán)境： win7 下 VC+6.0系統(tǒng)分析設(shè)計(jì)： 相關(guān)算法原理，算法流程圖，涉及的數(shù)據(jù)結(jié)構(gòu)內(nèi)容都相應(yīng)包含在各章節(jié)中有關(guān)了解內(nèi)存管理的相關(guān)理論 內(nèi)存管理概念： 內(nèi)存管理，是指軟件運(yùn)行時(shí)對(duì)計(jì)算機(jī)內(nèi)存資源的分配和使用的技術(shù)。其最主要的目的是如何高效，快速的分配，并且在適當(dāng)?shù)臅r(shí)候釋放和回收內(nèi)存資源。內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運(yùn)行的過程中建立分區(qū).當(dāng)作業(yè)裝入主存時(shí)，

7、根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個(gè)分區(qū)給該作業(yè)；否則令該作業(yè)等待.分區(qū)長(zhǎng)度不固定分區(qū)個(gè)數(shù)不固定。這種存儲(chǔ)管理的方法克服了固定分區(qū)嚴(yán)重浪費(fèi)主存的問題，提高了主存資源的利用率。內(nèi)存管理的必要性： 內(nèi)存管理對(duì)于編寫出高效率的 Windows 程序是非常重要的，這是因?yàn)閃indows 是多任務(wù)系統(tǒng)，它的內(nèi)存管理和單任務(wù)的 DOS 相比有很大的差異。DOS是單任務(wù)操作系統(tǒng)，應(yīng)用程序分配到內(nèi)存后，如果它不主動(dòng)釋放，系統(tǒng)是不會(huì)對(duì)它作任何改變的；但 Windows 卻不然，它在同一時(shí)刻可能有多個(gè)應(yīng)用程序共享內(nèi)存，有時(shí)為了使某個(gè)任務(wù)更好地執(zhí)行，Windows 系統(tǒng)可能會(huì)對(duì)其它

8、任務(wù)分配的內(nèi)存進(jìn)行移動(dòng)，甚至刪除。因此，我們?cè)?Windows 應(yīng)用程序中使用內(nèi)存時(shí)，要遵循Windows 內(nèi)存管理的一些約定，以盡量提高 Windows 內(nèi)存的利用率。 1.3 內(nèi)存的物理組織：物理地址： 把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)存儲(chǔ)單元占 8 位，稱作字節(jié)（byte）。每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為物理地址（內(nèi)存地址、絕對(duì)地址、實(shí)地址）。二、物理地址空間： 物理地址的集合稱為物理地址空間（主存地址空間），它是一個(gè)一維空間。 什么是虛擬內(nèi)存： 虛擬內(nèi)存是內(nèi)存管理技術(shù)的一個(gè)極其實(shí)用的創(chuàng)新。它是一段程序（由操作系統(tǒng)調(diào)度），持續(xù)監(jiān)控著所有物理內(nèi)存中的代碼段、數(shù)據(jù)段，并保證他們?cè)谶\(yùn)

9、行中的效率以及可靠性，對(duì)于每個(gè)用戶層（user-level）的進(jìn)程分配一段虛擬內(nèi)存空間。當(dāng)進(jìn)程建立時(shí)，不需要在物理內(nèi)存件之間搬移數(shù)據(jù)，數(shù)據(jù)儲(chǔ)存于磁盤內(nèi)的虛擬內(nèi)存空間，也不需要為該進(jìn)程去配置主內(nèi)存空間，只有當(dāng)該進(jìn)程被被調(diào)用的時(shí)候才會(huì)被加載到主內(nèi)存。連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式的實(shí)現(xiàn)在早期的操作系統(tǒng)中，主存分配廣泛采用連續(xù)分配方式。 連續(xù)分配方式，是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間，該連續(xù)內(nèi)存空間指的的是物理內(nèi)存。下面介紹連續(xù)分配的四種方式。 單一連續(xù)分配（單個(gè)分區(qū)） 最簡(jiǎn)單的存儲(chǔ)管理方式，用于多道程序設(shè)計(jì)技術(shù)之前。 內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)由操作系統(tǒng)使用。用戶區(qū)作為一個(gè)連續(xù)的分區(qū)分配給一

10、個(gè)作業(yè)。 分區(qū)存儲(chǔ)管理是滿足多道程序設(shè)計(jì)的最簡(jiǎn)單的一種存儲(chǔ)管理方法，它允許多 4個(gè)用戶程序同時(shí)存在系統(tǒng)內(nèi)存中，即共享內(nèi)存空間。 按分區(qū)劃分方式可分為固定分區(qū)和可變分區(qū)。 固定分區(qū)存儲(chǔ)管理 把內(nèi)存的用戶區(qū)預(yù)先劃分成多個(gè)分區(qū)，每個(gè)分區(qū)大小可以相同，也可以不同。（分區(qū)的劃分由計(jì)算機(jī)的操作員或者由操作系統(tǒng)給出，并給出主存分配表） 分區(qū)個(gè)數(shù)固定，分區(qū)的大小固定。 一個(gè)分區(qū)中可裝入一個(gè)作業(yè)，作業(yè)執(zhí)行過程中不會(huì)改變存放區(qū)域。 早期的 IBM 的 OS/MFT（具有固定任務(wù)數(shù)的多道程序系統(tǒng)）采用了這種固定分區(qū)的方法?？勺兎謪^(qū)存儲(chǔ)管理（動(dòng)態(tài)分區(qū)） 內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運(yùn)行的過程中建立分區(qū).當(dāng)作業(yè)裝入

11、主存時(shí)，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個(gè)分區(qū)給該作業(yè)；否則令該作業(yè)等待。 分區(qū)長(zhǎng)度不固定分區(qū)個(gè)數(shù)不固定。 這種存儲(chǔ)管理的方法克服了固定分區(qū)嚴(yán)重浪費(fèi)主存的問題，提高了主存資源的利用率。 操作系統(tǒng)采用可變分區(qū)存儲(chǔ)管理?？芍囟ㄎ环謪^(qū)存儲(chǔ)管理 解決碎片問題的一種簡(jiǎn)單方法是采用可重定位分區(qū)分配.。 其中心思想是，把不同程序，且在內(nèi)存中地址不連續(xù)的想法讓他們連續(xù)。例：內(nèi)存中現(xiàn)有 3 個(gè)空閑區(qū)，現(xiàn)有一作業(yè)到達(dá)，要求獲得 30k 內(nèi)存空間，沒有分區(qū)滿足容量要求，若想把作業(yè)裝入，可將內(nèi)存中所有作業(yè)進(jìn)行移動(dòng)，這樣把原來分散的空閑區(qū)匯集成一個(gè)大的空閑區(qū)。 將內(nèi)存中的作業(yè)進(jìn)行移動(dòng)

12、使它們連接在一起把原來分散的多個(gè)小分區(qū)拼接成一個(gè)大的空閑區(qū).這個(gè)過程稱為”緊湊”或”移動(dòng)”。 需解決的問題:每次”緊湊”后程序或數(shù)據(jù)裝入的物理地址變化采用動(dòng)態(tài)重定位。 問題描述和分析系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈表中找到所需大小的分區(qū)，如果空閑分區(qū)大小大于請(qǐng)求分區(qū)大小，則從該分區(qū)中按改請(qǐng)求的大小劃分出一塊內(nèi)存空間大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑鏈表中。然后，將分配區(qū)的首址返回給調(diào)用者。當(dāng)進(jìn)程運(yùn)行完畢師范內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)以下四種情況之一：該空閑區(qū)的上下兩相鄰分區(qū)都是空閑區(qū)：將三個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)。新空閑區(qū)的起始

13、地址為上空閑區(qū)的起始地址，大小為三個(gè)空閑區(qū)之和。空閑區(qū)合并后，取消可用表或自由鏈中下空閑區(qū)的表目項(xiàng)或鏈指針，修改上空閑區(qū)的對(duì)應(yīng)項(xiàng)。 該空閑區(qū)的上相鄰區(qū)是空閑區(qū)：將釋放區(qū)與上空閑區(qū)合并為一個(gè)空閑區(qū)，其起始地址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改上空閑區(qū)對(duì)應(yīng)的可用表的表目項(xiàng)或自由鏈指針。 該空閑區(qū)的下相鄰區(qū)是空閑區(qū)：將釋放區(qū)與下空閑區(qū)合并，并將釋放區(qū)的起始地址作為合并區(qū)的起始地址。合并區(qū)的長(zhǎng)度為釋放區(qū)與下空閑區(qū)之和。同理，合并后修改可用表或自由鏈中相應(yīng)的表目項(xiàng)或鏈指針。兩相鄰區(qū)都不是空閑區(qū)：釋放區(qū)作為一個(gè)新空閑可用區(qū)插入可用表或自由鏈。程序流程圖內(nèi)存分配流程圖，如圖內(nèi)存回

14、收流程圖，如圖數(shù)據(jù)結(jié)構(gòu)體分析進(jìn)程屬性結(jié)構(gòu)體typedef struct readyque char name10; int size;readyque,*readyqueue;空閑鏈表結(jié)構(gòu)體typedef struct idlyspace int from; int size; idlyspace * next;idlyspace,*idly;已分配鏈表結(jié)構(gòu)體typedef struct busyspace int from; readyque r; busyspace * next;busyspace,*busy主要程序代碼分析主函數(shù)/代碼請(qǐng)?zhí)砑舆m當(dāng)?shù)淖⑨尅nt main() Is=(id

15、ly)malloc(sizeof(idlyspace); Is->from=0; Is->size=256; Is->next=NULL; Is2=Is; Bs=(busy)malloc(sizeof(busyspace); Bs->next=NULL; int t,t1; printf("n.歡迎來到動(dòng)態(tài)分區(qū)存儲(chǔ)管理系統(tǒng).nn"); printf(".請(qǐng)選擇要執(zhí)行的算法:.n"); printf(". 1.最先適應(yīng)算法 .n"); printf(". 2.下次適應(yīng)算法 .n"); prin

16、tf(".3.最優(yōu)適應(yīng)算法 .n"); printf(". 4.最壞適應(yīng)算法 .n"); printf(".n"); printf("請(qǐng)輸入您的選擇:"); scanf("%d",&t); int i; while(i!=5) printf(".n"); printf(".操作菜單如下：（請(qǐng)選擇）.n"); printf(".1.輸入進(jìn)程分配空間 .n"); printf(". 2.進(jìn)程撤銷回收空間 .n")

17、; printf(". 3.輸出所有空閑分區(qū) .n"); printf(".4.輸出所有已分配分區(qū).n"); printf(". 5.退 出 .n"); printf(".n"); scanf("%d",&i); switch(i) case 1: switch(t) case 1: t1=FF(); break; case 2: t1=NF(); break; case 3: t1=BF(); break; case 4: t1=WF(); break; default: printf

18、("選擇算法錯(cuò)誤n"); return 1; if(t1) printf("分配空間成功n"); else printf("分配空間失敗n"); break; case 2: t1=recover(); if(t1) printf("回收成功n"); else printf("回收失敗n"); break; case 3: Isprint(); break; case 4: Bsprint(); break; return 0;第三章 ：分析并實(shí)現(xiàn)四種內(nèi)存分配算法最先適應(yīng)算法 空閑區(qū)按地址從小到

19、大的次序排列。 分配：當(dāng)進(jìn)程申請(qǐng)大小為 SIZE 的內(nèi)存時(shí)，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到容量滿足要求（SIZE）的空閑區(qū)為止。從該空閑區(qū)中劃出大小為 SIZE的分區(qū)分配給進(jìn)程，余下的部分仍作為一個(gè)空閑區(qū)，但要修改其首址和大小。 優(yōu)點(diǎn)：這種算法是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址 6部分的大空閑區(qū)，有利于大作業(yè)的裝入。  缺點(diǎn):主存低地址和高地址分區(qū)利用不均衡。在低地址部分集中了許多非常小的空閑區(qū)碎片降低了主存的利用率。最先適應(yīng)算法int FF() int t=0; readyque D; printf“"請(qǐng)輸入進(jìn)程名:”"); scanf“

20、"%”",D.name); printf“"輸入進(jìn)程申請(qǐng)空間大小:”"); scanf“"%”",&D.size); idly l=Is; int mt=256; busy b=Bs; idly min=NULL; while(l)/尋找空閑表中大小滿足申請(qǐng)進(jìn)程所需大小并且起址最小的空閑結(jié)點(diǎn) if(D.size<=l->size) if(l->from<mt) mt=l->from; min=l; t=1; l=l->next; if(mt!=256)/如果找到則為進(jìn)程分配空間 busy j

21、; j=(busy)malloc(sizeof(busyspace); j->from=min->from; for(int i=0;i<10;i+) j->i=D.namei; j->r.size=D.size; while(b->next) if(b->next->from<j->from) b=b->next; else break; j->next=b->next; b->next=j; min->from=min->from+D.size; min->size=min-&

22、gt;size-D.size; return t;下次適應(yīng)分配算法 最先適應(yīng)算法的變種。 總是從空閑區(qū)上次掃描結(jié)束處順序查找空閑區(qū)表（鏈），直到找到第一個(gè)滿足容量要求的空閑區(qū)為止，分割一部分給作業(yè)，剩余部分仍作為空閑區(qū)。下次適應(yīng)分配算法int NF() int t=0; readyque D; printf“"請(qǐng)輸入進(jìn)程名:”"); scanf“"%”",D.name); printf“"輸入進(jìn)程申請(qǐng)空間大小:”"); scanf“"%”",&D.size); int mt=256; idly l=Is2;

23、 idly min=NULL; busy b=Bs; while(l) /尋找空閑表中大小滿足申請(qǐng)進(jìn)程所需大小并且起址最小的空閑結(jié)點(diǎn) if(D.size<=l->size) if(l->from<mt) mt=l->from; min=l; t=1; l=l->next; if(mt!=256)/如果找到則為進(jìn)程分配空間 busy j; j=(busy)malloc(sizeof(busyspace); j->from=min->from; for(int i=0;i<10;i+) j->i=D.namei; j->

24、r.size=D.size; while(b->next) if(b->next->from<j->from) b=b->next; else break; /將申請(qǐng)空間進(jìn)程插入到已分配鏈表中 j->next=b->next; b->next=j; /修改相應(yīng)空閑節(jié)點(diǎn)的起址和大小 min->from=min->from+D.size; min->size=min->size-D.size; Is2=min->next;/ls2指向修改結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) t=1; return t; l=Is;/l指向空閑表的頭

25、while(l!=Is2)/循環(huán)查找 if(D.size<=l->size) if(l->from<mt) mt=l->from; min=l; t=1; l=l->next; if(mt!=256) busy j; j=(busy)malloc(sizeof(busyspace); j->from=min->from; for(int i=0;i<10;i+) j->i=D.namei; j->r.size=D.size; while(b->next) if(b->next->from<j-

26、>from) b=b->next; else break; j->next=b->next; b->next=j; min->from=min->from+D.size; min->size=min->size-D.size; Is2=min->next; t=1; return t; return t; 最優(yōu)適應(yīng)算法空閑區(qū)按容量遞增的次序排列。 分配：當(dāng)進(jìn)程申請(qǐng)存儲(chǔ)空間，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到第一個(gè)滿足容量要求的空閑區(qū)為止。 采用最優(yōu)適應(yīng)算法選中的空閑區(qū)是滿足容量要求的最小空閑區(qū)。 優(yōu)點(diǎn)：選中的空閑區(qū)是滿足容

27、量要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。 缺點(diǎn)：空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來越多，從而造成存儲(chǔ)空間的浪費(fèi)。最優(yōu)適應(yīng)算法int BF()int t=0; readyque D; printf“"請(qǐng)輸入進(jìn)程名:”"); scanf“"%”",D.name); printf“"輸入進(jìn)程申請(qǐng)空間大小:”"); scanf“"%”",&D.size); idly l=Is; idly min=NUL

28、L; int mt=256; busy b=Bs; while(l)/在空閑鏈中尋找第一個(gè)大于所輸入的進(jìn)程大小的空閑塊 if(D.size<=l->size) if(l->size<mt) mt=l->size; min=l; t=1; l=l->next; if(mt!=256)/找到第一個(gè)滿足要求的空閑塊 busy j; j=(busy)malloc(sizeof(busyspace);/申請(qǐng)分配用于存放進(jìn)程的內(nèi)存空間 j->from=min->from;/將第一個(gè)滿足要求的空閑塊（min）的首地址賦給j for(int i=0;i<1

29、0;i+) j->i=D.namei; j->r.size=D.size; while(b->next)/按從小到大的順序查找新進(jìn)程在已分配區(qū)中的位置 if(b->next->from<j->from) b=b->next; else break; j->next=b->next; b->next=j;/將所輸入的進(jìn)程插入進(jìn)程鏈 min->from=min->from+D.size;/改變?cè)摽臻e塊的起始地址 min->size=min->size-D.size;/改變?cè)摽臻e塊的剩余大小 ret

30、urn t;最壞適應(yīng)算法 為了克服最佳適應(yīng)算法把空閑區(qū)切割得太小的缺點(diǎn)，人們提出了一種最壞適應(yīng)算法，即每次分配時(shí)，總是將最大的空閑區(qū)切去一部分分配給請(qǐng)求者，剩余的部分仍是一個(gè)較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。 要求空閑區(qū)按容量遞減的順序排列。 分配：進(jìn)程申請(qǐng)存儲(chǔ)區(qū)時(shí)，檢查空閑區(qū)表（鏈）的第一個(gè)空閑區(qū)的大小是否滿足要求，若不滿足則令進(jìn)程等待；若滿足則從該空閑區(qū)中分配一部分存儲(chǔ)區(qū)給用戶，剩下的部分仍作為空閑區(qū)。最壞適應(yīng)算法int WF() int t=0; readyque D; printf“"請(qǐng)輸入進(jìn)程名:”"); scanf“"%”",D.na

31、me); printf“"輸入進(jìn)程申請(qǐng)空間大小:”"); scanf“"%”",&D.size);/輸入進(jìn)程申請(qǐng)的空間大小 idly l=Is;/l指向空閑鏈表ls頭 idly min=NULL; int mt=0; busy b=Bs;/b指向已分配鏈表Bs頭 /找到空閑分區(qū)中大小滿足進(jìn)程的請(qǐng)求且尺寸最大的結(jié)點(diǎn) while(l) if(D.size<=l->size)/判斷進(jìn)程所申請(qǐng)的大小是否小于空閑區(qū)的各結(jié)點(diǎn)大小 if(l->size>mt) mt=l->size; min=l;/min指向空閑區(qū)中尺寸最大的結(jié)點(diǎn)

32、 t=1; l=l->next;/l指向空閑鏈表下一個(gè)結(jié)點(diǎn) if(mt!=0)/判斷是否找到了空閑區(qū)的滿足結(jié)點(diǎn) busy j; j=(busy)malloc(sizeof(busyspace); j->from=min->from; for(int i=0;i<10;i+) j->i=D.namei; j->r.size=D.size; while(b->next)/尋找插入到已分配鏈表中的位置 if(b->next->from<j->from) b=b->next; else break; /把此進(jìn)程結(jié)點(diǎn)j插

33、入到已分配鏈表中 j->next=b->next; b->next=j; /修改空閑鏈表的相應(yīng)結(jié)點(diǎn)的參數(shù) min->from=min->from+D.size; min->size=min->size-D.size; return t;可變分區(qū)的回收當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí)，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)去，否則把釋放區(qū)作為一個(gè)空閑區(qū)插入到空閑表的適當(dāng)位置。釋放區(qū)與空閑區(qū)相鄰的四種情況。（1） 釋放區(qū)與前空閑區(qū)相鄰：把釋放區(qū)與前空閑區(qū)合并到一個(gè)空閑區(qū)。其首址仍為前空閑區(qū)首址，大小為釋放區(qū)大小與空閑區(qū)大小之和

34、。（2） 釋放區(qū)與后空閑區(qū)相鄰：則把釋放區(qū)合并到后空閑區(qū)，其首地址為釋放區(qū)首地址，大小為二者之和。（3） 釋放區(qū)與前后兩空閑區(qū)相鄰：這三個(gè)區(qū)合為一個(gè)空閑區(qū)，首地址為前空閑區(qū)首址，大小為這三個(gè)空閑區(qū)之和，并取消后空閑區(qū)表目。（4） 釋放區(qū)不與任何空閑區(qū)相鄰：將釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址插入到空閑區(qū)表的適當(dāng)位置?；厥諆?nèi)存算法int recover() readyque D; printf“"請(qǐng)輸入想要回收的進(jìn)程名”"); scanf“"%”",D.name); busy b=Bs; idly l=Is; while(b->next) /查找輸

35、入的進(jìn)程名是否在已分配鏈表中 bool yo=1; for(int i=0;i<10;i+) if(b->next->i=D.namei) yo=yo*1; else yo=0; /如果在已分配鏈表中則釋放該結(jié)點(diǎn)所占空間 if(yo) int t=b->next->from; int ts=b->next->r.size; while(l) if(l->from>t+ts)/所回收進(jìn)程與空閑結(jié)點(diǎn)上下都不鄰接 idly tl; tl=(idly)malloc(sizeof(idlyspace); tl->from=t; tl->size=ts; tl->next=l; Is=tl; break; if(l->from=t+ts)/所回收進(jìn)程與空閑結(jié)點(diǎn)下鄰接 l->from=t; l->size=l->size+ts; busy tb=b->next; b->next=b->next->next; free(tb); return 1; if(l->from+l->size<t)/所回收進(jìn)程與空閑結(jié)點(diǎn)上下都不鄰接 idly tl; tl=(idly)malloc(sizeof(idlyspace); t