操作系統(tǒng)課程設(shè)計(jì)LRU算法的實(shí)現(xiàn)

1、上孝甩SHANGHAI DIANJI UNIVERSITY操作系統(tǒng)原理課程設(shè)計(jì)報(bào)告姓名：黃崧岳班級(jí)：BX1010學(xué)號(hào)：5扌旨導(dǎo)老師：蘇慶岡I二一二年十二月十四日一、操作系統(tǒng)原理課程設(shè)計(jì)的目的與要求 11目的12要求1二、簡(jiǎn)述課程設(shè)計(jì)內(nèi)容、主要功能和實(shí)現(xiàn)環(huán)境 11課程設(shè)計(jì)內(nèi)容12主要功能13實(shí)現(xiàn)環(huán)境2三、任務(wù)的分析、設(shè)計(jì)、實(shí)現(xiàn)和討論 21任務(wù)的分析22任務(wù)的設(shè)計(jì)與實(shí)現(xiàn) 34思考題的解答和討論 10四、操作系統(tǒng)課程設(shè)計(jì)小結(jié) 14五、參考文獻(xiàn)14附錄14操作系統(tǒng)原理課程設(shè)計(jì)的目的與要求1目的近年來(lái)，由于大規(guī)模集成電路（LSI）和超大規(guī)模集成電路（VLSI ）技術(shù)的發(fā)展，使存 儲(chǔ)器的容量不斷擴(kuò)大，價(jià)格

2、大幅度下降。但從使用角度看，存儲(chǔ)器的容量和成本總受到一定 的限制。所以，提高存儲(chǔ)器的效率始終是操作系統(tǒng)研究的重要課題之一。虛擬存儲(chǔ)技術(shù)是用來(lái)擴(kuò)大內(nèi)存容量的一種重要方法。學(xué)生應(yīng)獨(dú)立地用高級(jí)語(yǔ)言編寫(xiě)幾個(gè)常用的存儲(chǔ)分配算法， 并設(shè)計(jì)一個(gè)存儲(chǔ)管理的模擬程序，對(duì)各種算法進(jìn)行分析比較，評(píng)測(cè)其性能優(yōu)劣，從而加深對(duì)這些算法的了解。2要求任務(wù)四采用最近最少使用頁(yè)淘汰算法 （LRU）實(shí)現(xiàn)。為了比較真實(shí)地模擬存儲(chǔ)管理，可預(yù) 先生成一個(gè)大致符合實(shí)際情況的指令地址流。然后模擬這樣一種指令序列的執(zhí)行來(lái)計(jì)算和分析各種算法的訪問(wèn)命中率。二、簡(jiǎn)述課程設(shè)計(jì)內(nèi)容、主要功能和實(shí)現(xiàn)環(huán)境1課程設(shè)計(jì)內(nèi)容最近最少使用頁(yè)淘汰算法（LRU），這

3、是一種經(jīng)常使用的方法。有各種不同的實(shí)施方案， 這里采用的是不斷調(diào)整頁(yè)表鏈的方法，即總是淘汰頁(yè)表鏈鏈?zhǔn)椎捻?yè)，而把新訪問(wèn)的頁(yè)插入鏈尾。如果當(dāng)前調(diào)用頁(yè)已在頁(yè)表內(nèi)，則把它再次調(diào)整到鏈尾。這樣就能保證最近使用的頁(yè)，總 是處于靠近鏈尾部分，而不常使用的頁(yè)就移到鏈?zhǔn)祝饌€(gè)被淘汰，在頁(yè)表較大時(shí)，調(diào)整頁(yè)表鏈的代價(jià)也是不小的。2主要功能（1）菜單函數(shù)int menu_select（）:用于顯示主菜單，可在其中選擇1.自定義進(jìn)程數(shù)和塊數(shù)；2顯示顯示用戶自定義的進(jìn)程數(shù)和塊數(shù)；3.進(jìn)行LRU算法4.退出程序。（2）最近最久未使用算法函數(shù) void LRU（）:此函數(shù)是將隨機(jī)產(chǎn)生的頁(yè)面進(jìn)行最近未使用 便置換的函數(shù)，也是本

4、程序的主要部分。（3）自定義進(jìn)程數(shù)和塊數(shù)函數(shù) void Zidingyi（）:此函數(shù)是主菜單中的第一個(gè)選項(xiàng)，即用戶可以自定義所需的進(jìn)程數(shù)和塊數(shù)。（4）顯示用戶自定義的進(jìn)程數(shù)和塊數(shù)函數(shù)void ShowCustomer（）:此函數(shù)是用于顯示用戶自定義的進(jìn)程數(shù)和塊數(shù)的情況。（5）修改塊數(shù)函數(shù)void Xiugaikuaishu（）:此函數(shù)是在進(jìn)行 LRU算法后，可以在原來(lái)的進(jìn)程數(shù)的基礎(chǔ)上，修改塊數(shù)并重新生成一組LRU算法的過(guò)程。（6）顯示每次換頁(yè)后的結(jié)果函數(shù)void ShowResult（）:此函數(shù)是顯示在LRU算法的執(zhí)行過(guò)程中每次換頁(yè)的情況。（7）顯示一定不用換頁(yè)的函數(shù) void ShowNot

5、（）:此函數(shù)是顯示最近使用過(guò)的頁(yè)面，即不用換頁(yè)的結(jié)果。3實(shí)現(xiàn)環(huán)境本次課程設(shè)計(jì)結(jié)合算法的特點(diǎn)，采用Windows操作系統(tǒng)平臺(tái)。開(kāi)發(fā)工具為MicrosoftVisual C+6.0。三、任務(wù)的分析、設(shè)計(jì)、實(shí)現(xiàn)和討論1任務(wù)的分析本示例是采用頁(yè)式分配存儲(chǔ)管理方案，并通過(guò)分析計(jì)算不同頁(yè)面淘汰算法情況下的訪問(wèn)命中率來(lái)比較各種算法的優(yōu)劣。 另外也考慮到改變頁(yè)面大小和實(shí)際存儲(chǔ)器容量對(duì)計(jì)算結(jié)果的 影響，從而可為算則好的算法、合適的頁(yè)面尺寸和實(shí)存容量提供依據(jù)。本程序是按下述原則生成指令序列的：（1）50%的指令是順序執(zhí)行的。（2）25%的指令均勻散布在前地址部分。（3）25%的指令均勻散布在后地址部分。示例中選用

6、最佳淘汰算法（OPT）和最近最少使用頁(yè)面淘汰算法（LRU ）計(jì)算頁(yè)面命中 率。公式為命中率=1 -頁(yè)面失效次數(shù) 頁(yè)地址流長(zhǎng)度3#假定虛存容量為32K，頁(yè)面尺寸從1K至8K，實(shí)存容量從4頁(yè)至32頁(yè)。#2任務(wù)的設(shè)計(jì)與實(shí)現(xiàn)2.1 ma in()函數(shù)流程圖:42.2主菜單流程圖:inm;11printfl入 你0renrrnlji),2.3 LRU函數(shù)流程圖:62.4 Zidingyi()函數(shù)流程圖:inti;i-0piiges:100;岸 whim);2.5 ShowCustomer(函數(shù)流程圖:o("cm；i-0printtVtd *bpagesi汁十72.6 ShowNot()函數(shù)流程

7、圖:82.7 ShowResult()函數(shù)流程圖:9#pr'Tlttr1 %d",Fu7hui；i+pTinttrn"：#3操作過(guò)程和結(jié)果分析按1進(jìn)入自定義進(jìn)程數(shù)和塊數(shù)請(qǐng)求頁(yè)式存儲(chǔ)管理中LRU譚法的實(shí)現(xiàn)12 3 4利義 矍 程自法 進(jìn)UMTT 義用RUEX 定一憑 自顯#輸入你的選擇#按2顯示進(jìn)程數(shù)，塊數(shù)和隨機(jī)分配頁(yè)號(hào)10覽 JOCKXHHBEXX JOCKKJOC” KUH WBHHHHOCJtK ICX)0000( JOC)1 W lOOCK 100(童 Wit JCK見(jiàn)不:進(jìn)程斂為：20頁(yè)號(hào)分別為： 4167 34 B 6924 ?B 5862 B4 

8、3;45 Bl 27 G1 VI 95422736町用物理塊數(shù)為，1曲任意鍵 可返回 主菜.單按3實(shí)現(xiàn)LRU算法，輸出命中率11#LRU算法結(jié)果顯示;9-454259-420 52 80:414141078781 188:27換為：為為：一 書(shū)備詈一 總罷一 s頁(yè)面頁(yè)一 頁(yè)置4叩缺一#按1修改塊數(shù)，按2遞回主菜單Wes1, No2#按1修改物理塊數(shù)，重新實(shí)現(xiàn) LRU算法并輸出命中率27&191958178顯示:34417ZT別為27町用物理塊數(shù)為:按任意鍵可返回王菜單UW算袪結(jié)果顯黃:454S4561616161424241412.b81813i12EZ2l2l0B 0 0 17fhj

9、 為為；為為.24總忌率 95換頁(yè)面頁(yè) 置畳命缺-按1修改塊數(shù)按2返回主菜單Wes1, No2 2_請(qǐng)求頁(yè)式存儲(chǔ)管理中LRU算法的實(shí)現(xiàn)按4退出程序12 3 4數(shù) 塊和義 墊疋 程自法 進(jìn)fin 義用RUEK 定不L 自顯12#輸入你的選擇= 4 謝謝使用算迭？Bye ByeA-APress any keu to continueFIFO算法該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，既選擇內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需要把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按照先后測(cè)序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，使他總是指向最老的頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁(yè)面經(jīng)常被

10、訪問(wèn)，比如，含有全局變量、常用函數(shù)、例程等的頁(yè)面，F(xiàn)IFO算法并不能保證這些頁(yè)面不被淘汰。這里，我們用下面的例子，采用FIFO算法進(jìn)行頁(yè)面置換。當(dāng)進(jìn)程第一次訪問(wèn)頁(yè)面 2時(shí)，將把第七頁(yè)換出，因?yàn)樗亲钕缺徽{(diào)入內(nèi)存的；在第一次范文頁(yè)面3時(shí)，又將把第零頁(yè)換出，因?yàn)樗诂F(xiàn)有的2，0，1三個(gè)頁(yè)面中是最老的頁(yè)。由下圖可以看出，利用 FIFO算法時(shí)進(jìn)行了十二次頁(yè)面置換，比最佳置換算法正好多一倍。結(jié)果分析一一兩種算法的比較：先進(jìn)先出（FIFO）算法較易實(shí)現(xiàn)，比較適用于具有線性順序特性的程序，而對(duì)其他特性的程序 則效率不高。缺頁(yè)中斷率為最佳算法的23倍；增加可用主存塊的數(shù)量會(huì)導(dǎo)致更多的缺頁(yè)，此算法還可能出現(xiàn)抖動(dòng)

11、現(xiàn)象異常。最近最久未被使用（LRU）算法的實(shí)現(xiàn)需要硬件支持，基于程序的局部性原理，所以適用用大 多數(shù)程序，此算實(shí)現(xiàn)必須維護(hù)一個(gè)特殊的隊(duì)列一一頁(yè)面淘汰隊(duì)列。關(guān)鍵是確定頁(yè)面最后訪問(wèn)以來(lái) 所經(jīng)歷的時(shí)間。4思考題的解答和討論（1 ）設(shè)計(jì)一個(gè)界地址存儲(chǔ)管理的模擬系統(tǒng)，模擬界地址方式下存儲(chǔ)區(qū)的分配和回收過(guò)程。提示：必須設(shè)置一個(gè)內(nèi)存分配表， 按照分配表中有關(guān)信息實(shí)施存儲(chǔ)區(qū)的分配，并不斷根據(jù)存儲(chǔ)區(qū)的分配和回收修改該表。算法有首次匹配法，循環(huán)首次匹配法和最佳匹配法等?？捎酶鞣N方法的比較來(lái)充實(shí)實(shí)習(xí)內(nèi)容。可使用碎片收集和復(fù)蓋等技術(shù)。答：開(kāi)始（1 ）數(shù)據(jù)結(jié)構(gòu)及說(shuō)明本程序?yàn)榭勺兎謪^(qū)管理方式主存分配回收模擬程序，采用首次

12、適應(yīng)策略。主要數(shù)據(jù)結(jié)構(gòu)：空閑區(qū)鏈表FBC，分配區(qū)鏈表ABC :表中記錄塊的起始地址和大小，塊按照始地址大小從小到大排列。（2）功能實(shí)現(xiàn) 分配時(shí)，根據(jù)用戶提供的作業(yè)大小，從第一個(gè)空閑塊開(kāi)始查找，將找到的第一個(gè)足夠大的空閑塊塊分配給該作業(yè)，返回給用戶該塊始地址。如果該塊剩余部分小于特定閾值（本程序?yàn)?k）,將該塊整體分配給此作業(yè)，將該塊直接加入分配區(qū)鏈表，若剩余塊大于或等于閾值，將分配塊加入分配區(qū)鏈表，剩余部分作為新的空閑塊另：程序開(kāi)始時(shí)已將0到20k分配給操作系統(tǒng)。 回收時(shí)，根據(jù)用戶提供的作業(yè)的始地址，在分配區(qū)表查找，若找到該塊，將其加入空閑區(qū)鏈表，提示用戶釋放成功。 若新形成的空閑塊與其前后的

13、空閑塊相連，合并空閑塊形成更大的空閑塊。 顯示，用戶可隨時(shí)選擇查看內(nèi)存分配狀態(tài)圖以及空閑區(qū)表與分配區(qū)表，在分配或回收成功時(shí)，程序自動(dòng)顯示內(nèi)存分配狀態(tài)圖、空閑區(qū)表與分配區(qū)表。編制一個(gè)程(2)自行設(shè)計(jì)或選用一種較為完善的內(nèi)存管理方法，并加以實(shí)現(xiàn)。 提示：設(shè)計(jì)一個(gè)段頁(yè)式管理的模擬程序或通過(guò)一個(gè)實(shí)際系統(tǒng)的消化和分析, 序來(lái)模擬該系統(tǒng)。答：分配總空間大小為128,若輸入的進(jìn)程大于該數(shù)，則顯示“占用空間過(guò)大，分配失敗”若分配的進(jìn)程大小為 0,則顯示“進(jìn)程空間大小錯(cuò)誤”1603070b閑區(qū)情況： 無(wú)空閑區(qū)了.長(zhǎng).g *C: Docu*ent s and Sett ingsAdB.in.ist rat orB

14、y DocuAent sDebugCppl. exe Sb-內(nèi)名名名Jt:a=纏粗 長(zhǎng)鼎始 己己-己- - 0 tSI - -Ir:! -!r 況:7分； 第存:a:b 區(qū)地問(wèn)名名 空起進(jìn)進(jìn)進(jìn)：30（：40：58睛按鍵選搖：1犧輸入進(jìn)翟名和占用空I可大小:CC58:址址址 乩也也也 壇始始 己己己己 酉_已一已_已 分a b C 存:a:b:c選擇1分配內(nèi)存，輸入內(nèi)存名和占用空間大小即可分配內(nèi)存，顯示的項(xiàng)目有進(jìn)程名、起始地址和長(zhǎng)度，已分配的內(nèi)存分配情況會(huì)顯示出來(lái)，如上圖?？臻g分配滿則顯示“無(wú)空閑區(qū)” *C: Docu>ent s and Sett ingsAdB.inist rat or

15、By DocuAent sDebugCppl. exe*CC58空閑區(qū)情況: 氏空閑區(qū)了.內(nèi)名名名進(jìn)進(jìn)進(jìn)進(jìn)：0aa起.：30 f ：40bb起始地址：30起始地址:西長(zhǎng)度汚&cc熒黯爲(wèi)和程名: 迸翟內(nèi)存回收完畢.ccg=5a=纏粗 彼鼎始 卡 己己-己一 - 酉走 況:0分；擇 舟存:a:b選 區(qū)地內(nèi)名名 鍵 i K 按 空起逬進(jìn)逬 請(qǐng)選擇2回收內(nèi)存，輸入已分配的內(nèi)存名稱即可回收該內(nèi)存，并顯示剩余的已分配內(nèi)存17四、操作系統(tǒng)課程設(shè)計(jì)小結(jié)頁(yè)面置換算法理解比較容易，這次根據(jù)學(xué)號(hào)要求實(shí)現(xiàn)的是 LRU算法的實(shí)現(xiàn)。分配到我的是兩道思考題，其實(shí)這兩道思考題的算法是差不多的，所以第一 題我沒(méi)有去編寫(xiě)

16、只是寫(xiě)出了大概的思路和算法框圖。其實(shí)這兩種算法的程序編寫(xiě) 比較容易，雖然不全是自己編寫(xiě)的，一部分是參考的網(wǎng)上的例題，但是通過(guò)對(duì)每 一語(yǔ)句的理解，自己弄懂了整個(gè)程序的執(zhí)行原理。 但是，在編寫(xiě)過(guò)程中自己還是 遇到了一些問(wèn)題。最大的一個(gè)問(wèn)題就是兩個(gè)算法的正確實(shí)現(xiàn)，在程序的編寫(xiě)時(shí)，兩個(gè)程序是分 開(kāi)進(jìn)行編寫(xiě)的，分別執(zhí)行起來(lái)沒(méi)有什么問(wèn)題，但是把兩個(gè)程序融合在一起后，卻 出現(xiàn)了問(wèn)題，即在執(zhí)行完成一個(gè)算法后再執(zhí)行另外一個(gè)算法時(shí)， 開(kāi)始的數(shù)據(jù)是緊 接著上次算法結(jié)果的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)的。 這個(gè)問(wèn)題困擾了我好長(zhǎng)時(shí)間，直到現(xiàn)在還 沒(méi)有很好的解決掉，程序只能分別執(zhí)行一次，如果再進(jìn)行執(zhí)行的話，就會(huì)出現(xiàn)問(wèn) 題。自己的編程技術(shù)不

17、好，程序編的也很繁瑣，但是基本的要求已經(jīng)實(shí)現(xiàn)了，希 望這次的實(shí)驗(yàn)是自己動(dòng)手的一個(gè)開(kāi)始，自己應(yīng)該更加努力，再接再厲。五、參考文獻(xiàn)【1】 計(jì)算機(jī)操作系統(tǒng) 【2】 計(jì)算機(jī)操作系統(tǒng) 【3】 操作系統(tǒng)教程孫雅如等編著西安電子科技大學(xué)2003（第2版）吳企淵 等編著清華大學(xué)出版社 2003 徐甲同編著西安電子科技大學(xué)出版社.2001附錄LRU算法實(shí)現(xiàn)#i nclude <stdio.h>#i nclude <stdlib.h>#in elude <time.h>#defi ne Maxsize 300 void Xiugaikuaishu(); void In itio

18、 n();void Zidi ngyi(); void ShowCustomer();void ShowResult();void ShowNot();void LRU();int menu _select();int pageNum = 0;/ 頁(yè)面數(shù)int pagesMaxsize; 存儲(chǔ)頁(yè)號(hào)int FuzhuMaxsize; 輔助數(shù)組int TimeMaxsize;記錄頁(yè)在內(nèi)存中的時(shí)間int block;/記錄物理塊數(shù)int Fz;輔助變量int mai n()for(;) /*循環(huán)無(wú)限次*/switch(me nu _select()case 1: Zidi ngyi();break;

19、case 2: ShowCustomer();break;case 3: LRU();break;case 4:printf(”謝謝使用LRU算法!n");printf(” Bye ByeA-An");exit(0);/*如菜單返回值為13則程序結(jié)束*/return 0; int menu _select()int n;printf(”i1n");prin tf("|請(qǐng)求頁(yè)式存儲(chǔ)管理中 LRU算法的實(shí)現(xiàn)| n ”);prin tf("| n ”);prin tf("|1.自定義進(jìn)程數(shù)和塊數(shù)| n");prin tf(&quo

20、t;|2.顯示用戶自定義| n");prin tf("|3.LRU算法| n");19prin tf("|4.EXIT1 n ”);prin tf("|1 n ”);prin tf("|1 n ”);printf(”|1n");doprintf("nttt 輸入你的選擇(14):");scan f("%d", &n);while(n< 1|n>4); /*如果選擇項(xiàng)不在13之間則重輸*/ |如果一個(gè)以上為真,真，二者都為假時(shí)，結(jié)果為假return(n); /*返回選

21、擇項(xiàng)，主函數(shù)根據(jù)該數(shù)調(diào)用相應(yīng)的函數(shù)*/則結(jié)果為void Zidi ngyi()II自定義進(jìn)程數(shù)和塊數(shù)int i;system("cls");printf(” *n");printf(”頁(yè)式儲(chǔ)存管理一LRU算法printf(” *n");printf(” 自定義進(jìn)程數(shù)和塊數(shù) n");prin tf("n");printf("請(qǐng)輸入進(jìn)程數(shù)：”)；scan f("%d",&pageNum);for(i = 0 ; i < pageNum ; i+)pagesi = rand()%100;

22、 II初始化頁(yè)號(hào)，初始值在0-100之內(nèi) getchar();printf("請(qǐng)輸入塊數(shù)：”)；scan f("%d",&block );getchar();自定義進(jìn)程數(shù)和塊數(shù)n");void LRU()II最近最久未使用算法 int i,j;int WithOutPages = 0;II 記錄缺頁(yè)數(shù)printf(" *printf(”LRU 算法結(jié)果顯示：n");prin tf("n");ShowNot();for(i = Fz ; i < pageNum; i+)21int key = 0;for

23、(j = 0 ; j < block ; j+)判斷該頁(yè)是否在物理塊中 if(Fuzhuj = pagesi)key = 1;Timej = i;更新時(shí)間break; if(key = 0)/若該頁(yè)不在內(nèi)存中WithOutPages+;int min = Time0;int flag = 0;for(j = 1 ; j < block ; j+)if(min > Timej)min = Timej;/找到最久的頁(yè)面 flag = j;Timeflag = i;/ 記錄時(shí)間Fuzhuflag = pagesi;ShowResult();printf("置換次數(shù)為：d

24、n”,WithOutPages);printf("頁(yè)面總數(shù)為：%d n”,pageNum);double re = (double)WithOutPages)/(double)pageNum); printf("置換率為：%.2lfn",re);printf("命中率為：.2lfn",1-re);printf("缺頁(yè)次數(shù)為：%d n”,WithOutPages+block);printf("頁(yè)面總數(shù)為：%d n”,pageNum);re = (double)(WithOutPages+block)/(double)pageN

25、um); printf("缺頁(yè)率為：%.2lfn",re);22printf("*printf(”按1修改塊數(shù)，按2返回主菜單n");#prin tf("n");printf(”Yes-1，No-2 n");in t la;sea nf("%d",&la);if(la=1)Xiugaikuaishu();elseprintf(” *n “);printf("system("cls");void ShowResult()顯示每次換頁(yè)后的結(jié)果int i;for(i = 0

26、 ; i < block ; i+)printf(" %d",Fuzhui);prin tf("n"); void Xiugaikuaishu()system("cls");printf(" *printf(”請(qǐng)輸入需要修改塊的數(shù)目 ：n ”);prin tf("");int a;scan f("%d", &a);block = a;ShowCustomer();顯示自定義頁(yè)面信息LRU();void ShowCustomer()顯示用戶自定義的進(jìn)程數(shù)和塊數(shù) system

27、("cls");int i;printf(" *printf("顯示:n");printf("進(jìn)程數(shù)為：%dn",pageNum); printf("頁(yè)號(hào)分別為：”)；for(i = 0 ; i < pageNum ; i+)prin tf("%d”,pagesi);prin tf("n");printf("可用物理塊數(shù)為：%dn",block);printf(" *printf(” 按任意鍵可返回主菜單 n");getchar();voi

28、d ShowNot()顯示一定不用換頁(yè)的部分 Fz = block;int i,j,k=O,key = 0;for(i = 0 ; i < Fz ; i+)int flag = 0;for(j = 0 ; j <= i-1 ; j+)if(Fuzhuj = pagesi) Timej = i;flag = 1;Fz = Fz+1; key+; if(flag = 0) Timek = i;Fuzhuk = pagesi;k+;for(j = 0 ; j <= i-key ; j+)prin tf("%d",Fuzhuj); prin tf("n&

29、quot;);思考題2:內(nèi)存管理小程序#in clude <iostream.h>#in clude <stdio.h>#in elude <stri ng.h> struct programchar n ame30;long start;long len gth;struct program *n ext;struct spacelong start;long len gth;struct space *n ext;void creat();void allot();void back();void callback(program *r);void so

30、rt(space *L);void sort(program *S);void display(space *L);void display(program *S);space *L; program *S;void creat()L=new space;space *p=new space; p->start=0;p->le ngth=128;p-> next=NULL;L_>n ext=p;S=new program;S-> next=NULL;void allot()program *q;q=new program;cout<<"請(qǐng)輸入

31、進(jìn)程名和占用空間大小:"<<endl;cin»q_>n ame»q->le ngth;if(q->le ngth<=0)cout<<"進(jìn)程空間大小錯(cuò)誤."<<endl;delete q;return;space *p,*r;P=L;r=p;while(p-> next!=NULL&&p-> next->le ngth<q->le ngth)r=p;p=p->n ext;if(p-> next=NULL)cout<<&

32、quot;占用空間過(guò)大，分配失敗"<<endl;delete q;return;elseq->start=p->n ext->start;q->n ext=S->n ext;S_>n ext=q;p-> next->le ngth-=q->le ngth;if(p->n ext->le ngth!=O)p_>n ext->start+=q->le ngth;elseif(p-> next-next!=NULL)p->n ext=p->n ext- >n ext;el

33、ser->n ext=NULL;delete p->n ext;display(L);display(S);void back()char n ame30;cout<<"輸入要回收的進(jìn)程名："cin»n ame;program *p;p=S;while(p-> next!=NULL)if(strcmp(p->n ext- >n ame, n ame)=0)callback(p);return;p=p->n ext;if(p-> next=NULL)cout<<"此進(jìn)程不存在，內(nèi)存回收失敗&

34、quot;<<endl;void callback(program *t)program *r;r=t- >n ext;space *p,*q;long n;n=r->le ngth;if(L-> next=NULL)space *w=new space;w->start=0;w->le ngth=n;w-> next=NULL;L->n ext=w;t->n ext=r- >n ext;delete r;cout<<"此進(jìn)程內(nèi)存回收完畢."<<endl;27display(L);di

35、splay(S);return;p=L->n ext;while(p!=NULL&&p->start<r->start)q=p;p=p->n ext;上下均空if(q->start+q->le ngth=r->start )&&( r->start+ n=p->start) /q_>n ext=p->n ext;q->le ngth=q_>le ngth+p_>le ngth+n;t->n ext=r- >n ext;delete r;else if(r->

36、;start+ n=p->start) / 下鄰空p->start-=n;p->le ngth+=n;t->n ext=r- >n ext;delete r;else if(q->start+q->le ngth=r->start)q->le ngth+=n;t->n ext=r- >n ext;delete r;elsespace *sp=new space;sp->start=r->start;sp->le ngth=n;sp->n ext=L->n ext;L->n ext=sp;t-&

37、gt;n ext=r- >n ext;delete r;cout<<"此進(jìn)程內(nèi)存回收完畢."<<endl;display(L);display(S);void display(space *L)sort(L);space *p=L->n ext;cout<<e ndl<<"空閑區(qū)情況："<<e ndl;if(p=NULL) cout<<"無(wú)空閑區(qū)了 ."<<endl; return;while(p!=NULL)cout<<"起始地址:"<<p->start<<"長(zhǎng)度:"<<p->length<<endl;p=p->n ext;void display(program *S)sort(S);program *p=S->n ext;cout<<e ndl<