内存管理.doc

实验四 内存管理一、实验目的：利用图形包代码，编写程序，实现内存的分配算法（最佳适配和邻近适配）。即学习内存管理动态分区的思想，通过阅读和分析实验程序，熟悉几种常用的算法，首次适配算法(FirstFit)、最佳适配算法(BestFit)和邻近适配算法(NextFit)，且能对每种算法的特点进行比较。二、实验原理：首次适配算法(FirstFit)：从内存的首地址出发，选择第一个能满足进程大小内存空闲块。最佳适配算法(BestFit)：从内存的首地址出发，选择内存空闲块中最适合进程大小的块。邻近适配算法(NextFit)：从上一次分配的地址开始查找第一个能满足进程大小的内存空闲块。对于每一个进程，用作业控制块来表示，其数据结构如下：typedef struct JCBInfochar* JobName;/作业名int JobIndex;/作业序号int JobLength;/作业大小int* JobPageTable;/页表首地址JCBInfo * nextPointer;/指向下一个JCBInfoJCBInfo * prePointer;/指向上一个JCBInfo;对于每一个内存块，其数据结构如下：/*内存块结构，可以表示主存空间占用情况（链表形式）*/typedef struct MemoryBlock long StartAddr;/内存块起始地址(单位 KB)long BlockLength;/内存块长度(单位 KB)int JobIndex;/属于哪个作业。nBelongToJob=0 表示“空闲”MemoryBlock * nextPointer;/指向下一个MemoryBlockMemoryBlock * prePointer;/指向上一个MemoryBlock;JCBInfo和 MemoryBlock定义在CMemAllocate类中，其中包含内存块和作业的初始化，增加一个作业，删除某个作业，首次适配算法，最佳适配算法，邻近适配算法以及算法的检测等方法，CMemAllocate类的定义如下：class CMemAllocate /*内存块结构，可以表示主存空间占用情况（链表形式）*/typedef struct MemoryBlock /*作业控制块信息结构*/typedef struct JCBInfopublic:CMemAllocate();virtual CMemAllocate();private:MemoryBlock * m_MemList;/主存空间占用列表(用链表表示)JCBInfo * m_JobsHead, * m_JobsEnd;/作业控制块(用链表表示)public:void DrawMemory( CDC* pDC);/把当前的内存状态的图形画出来void InitMemoryBlock();/把对象进行初始化内存空间。初始状态为一个1M(1024KB)的空间void InitJobs();/初始化作业void AllocateMem_FirstAdapt(JCBInfo& job);/(首次适应算法)把一个作业分配到内存中 void AllocateMem_BestAdapt(JCBInfo& job);void AllocateMem_NextAdapt(JCBInfo& job);void AddAJobInEnd(char * JobName,int JobIndex,int JobLength,int* JobPageTable=NULL);添加一个作业 void DeleteJob(int JobIndex); /删除某个作业void FirstAdaptTest(); /首次适配算法测试void BestAdaptTest(); /最佳适配算法测试void NextAdaptTest(); /邻近适配算法测试;三、实验内容：(1).参考首次适配算法的源程 ，在所提供的程序基础之上实现最佳适配和邻近适配算法。(2).增加测试案例，验证程序的正确性(3).删除掉一个分配的进程(4).重新分配一个进程，假设进程6大小为100(5).利用VC+6.0实现程序设计和调试操作。(6).通过阅读和分析实验程序，熟悉内存分配算法四、实验步骤：(1)首次适配算法void AllocateMem_FirstAdapt(JCBInfo& job)思路及分析首次适配算法是指从内存的首地址开始寻找，找到第一个能满足作业大小的空闲块。内存块用双向链表来表示，每次查找从指向链表首部的指针m_MemList开始遍历，一旦找到内存块为空闲(p-JobIndex = 0)且满足作业大小(job.JobLength BlockLength)，则停止查找，并将该作业添加进主存块中。添加过程即为双向链表的插入操作。(2)最佳适配算法void AllocateMem_BestAdapt(JCBInfo& job)思路及分析最佳适配算法是指从内存的首地址出发，选择内存空闲块中最适合进程大小的块。查找的关键因素在于寻找内存空闲块中最时候作业大小的块，其实现过程也并不困难，可用MinBlockLength来表示满足作业大小的最小空闲块的长度，其初始值为1024，以后每次找到比MinBlockLength小的内存空闲块，则将该长度赋值给MinBlockLength。遍历整个链表，则找到满足作业大小的最小空闲块的长度，然后将该作业添加进主存中。(3)邻近适配算法void AllocateMem_NextAdapt(JCBInfo& job)思路及分析邻近适配算法是指从上一次分配的地址开始查找第一个能满足进程大小的内存空闲块，该算法与首次适配算法很相近，即从上一次分配的地址开始进行首次适配查找。为此，可以用一个指针（latestMemBlock）来表示最近分配的内存块，用变量JobIndex来表示最近分配的作业号，二者定义在结构体Flag中：/*标记最近分配的主存块和作业号*/typedef struct FlagMemoryBlock *latestMemBlock; /最近分配的MemoryBlockint JobIndex; /最近分配的作业号;在类CMemAllocate中定义一个private类型成员变量flag（Flag *flag），用来标记上一次分配的主存块和作业号。故邻近适配算法的实现过程即为：每次从flag指向的内存块开始执行首次适配算法，其中flag初始值为m_MemList。每次分配完一个作业后更新flag的内容。(4)删除作业void DeleteJob(int JobIndex) 的思路及分析由于是动态分配，因此删除某个作业的时候要考虑其上、下一块的内存分配情况。首先考虑最简单的情形：（假设现在要删除作业2）如图A所示，假设作业2驻留在内存中，其上一块和下一块均已分配作业，若要删除作业2，则只需将相应的内存块的作业号设置为0(表示空闲)即可。其他情形：若作业2的上一块（或下一块）为空，如图B、C所示，则应考虑将其与上一块（或下一块）进行合并。对于上、下一块均为空闲的情形，除了要将三块合并以外，flag的内容有可能也要发生改变。考虑如下情况：作业2为最近一次分配的作业，此时flag -JobIndex = 2，flag -latestMemBlock = p;作业2删除后，flag -latestMemBlock应指向合并后的那一个“大块”，否则在执行邻近适配算法的时候则会出错。五、运行结果及分析：(1)设有五个作业，其大小分别为：180K，360K，180K，60K，8K。内存大小为1024K，执行各种算法后内存的分配情况（深色表示已分配，浅色表示未分配）： 首次适配算法 最佳适配算法 邻近适配算法(2)删掉作业3，并重新分配作业6（大小为100K），执行各种算法后内存分配的情况： 首次适配算法 最佳适配算法 邻近适配算法(3)最佳适配算法和邻近适配算法的正确性检验，假设删除作业1,2,5,6，重新分配作业7（90K），执行各种算法后内存分配的情况： 首次适配算法 最佳适配算法 邻近适配算法(4)对上述运行结果的分析：对于内存开始为空闲的情况下，不论执行哪种算法其分配情况都是相同的，因为作业是按序进入主存的，而主存大小也足够大。当删掉作业3，添加作业6时，内存中第三块为空闲区（180K），由于内存中只有两个空闲区，大小分别为180K和228K，因此执行首次适配算法和最佳适配算法效果相同，都是将作业6分配在内存的第三块，而对于邻近适配算法则是将作业6分配在第二个空闲区，因上一次分配的位置为作业5驻留在内存的位置。进一步考虑前面讨论的情形B(或C)和D，删除作业1，2,5,6，同时再添加作业7（40K），此时作业7被分配在内存的第一个空闲区，而邻近适配算法和最佳适配算法效果相同，都是将作业7分配在内存的第二个空闲区，其原因也是显然的。最佳适配算法的思想是分配最合适的满足作业大小的空闲块，但其最大的缺陷是导致内存中“小碎片”越来越多，这大大降低了主存的利用率，若采用压缩技术，其开销也很大。邻近适配算法执行效率最快，但主作业都驻留在内存的尾部，即使前面有空闲块，但却不能被分配。首次适配算法执行效率介于邻近适配和最佳算法之间，但却避免了上述两种算法的不足。虽然也会产生“碎片”，但这些碎片可以容纳下一些不大的作业，因此主存的利用率是最高的。通过对几种算法的比较分析可知，首次适配、最佳适配以及邻近适配算法都有一定的适应性，在某些场合下，它们的效果是相同的，但在其他场合下却有所差异。因此，在考虑实际问题中，我们应综合考虑各种因素，选择最合适的算法。五、几个算法的源程序：/实现了最佳适配算法void CMemAllocate:AllocateMem_BestAdapt(CMemAllocate:JCBInfo& job) long MinBlockLength = 1024;MemoryBlock * q; for (MemoryBlock * p = m_MemList; p != 0; p= p-nextPointer)if (job.JobLength BlockLength & p-JobIndex = 0) /如果作业需要空间小于内存块空间，分配if(p -BlockLength BlockLength; /找到满足作业的最小空闲块q = p; if(q != 0) MemoryBlock * tmpMemBlock = new MemoryBlock;tmpMemBlock -BlockLength = job.JobLength;tmpMemBlock -JobIndex = job.JobIndex;tmpMemBlock -StartAddr = q-StartAddr;tmpMemBlock -nextPointer = q;tmpMemBlock -prePointer = q -prePointer;q-StartAddr = q-StartAddr + job.JobLength;q-BlockLength = q-BlockLength -job.JobLength;if (q-prePointer = 0 )m_MemList = tmpMemBlock;elseq -prePointer-nextPointer = tmpMemBlock;q -prePointer = tmpMemBlock;/实现了邻近适配算法void CMemAllocate:AllocateMem_NextAdapt(CMemAllocate:JCBInfo& job) for ( MemoryBlock * p = flag -latestMemBlock; p != 0; p=p-nextPointer) /从最近一次分配的位置开始进行首次适配算法if (job.JobLength BlockLength & p-JobIndex = 0)/如果作业需要空间小于内存块空间，分配MemoryBlock * tmpMemBlock = new MemoryBlock;tmpMemBlock -BlockLength = job.JobLength;tmpMemBlock -JobIndex = job.JobIndex;tmpMemBlock -StartAddr = p-StartAddr;tmpMemBlock -nextPointer = p;tmpMemBlock -prePointer = p -prePointer;p-StartAddr = p-StartAddr + job.JobLength;p-BlockLength = p-BlockLength -job.JobLength;if (p-prePointer = 0 )m_MemList = tmpMemBlock;elsep-prePointer-nextPointer = tmpMemBlock;p -prePointer = tmpMemBlock; flag -latestMemBlock = tmpMemBlock;flag -JobIndex = job.JobIndex; /记录最近一次分配的作业号break;elsecontinue;/删除某一个作业void CMemAllocate:DeleteJob(int JobIndex) for(MemoryBlock *p = m_MemList;p -JobIndex != JobIndex;p = p -nextPointer); /找到要删除的作业 MemoryBlock *pre = p -prePointer; MemoryBlock *next = p-nextPointer; if(pre !=0 & next !=0 & pre -JobIndex = 0 & next -JobIndex = 0) /如果要删除的作业上一块以及下一块均空闲，则合并这三块 pre -BlockLength += p -BlockLength + next -BlockLength; pre -nextPointer = next -nextPointer; if(flag -JobIndex = JobIndex) /如果要删除的作业恰好为最近一