动态分区分配以及动态重定位分配四种方式.ppt

第四章内存管理、4.3连续分配方式、连续分配方式是指对用户程序分配连续的内存空间。 分为四种方式：单连续分配、固定分区分配、动态分区分配和动态重新定位分配。 单个连续分配是最简单的存储管理方法，但仅适用于单用户单任务操作系统。 通过这种存储管理方式，将内存分为系统区域和用户区域，系统区域仅提供给操作系统，通常位于内存低地址部分的用户区域是指除系统区域以外的所有内存区域，并提供给用户。 固定分区分配和固定分区分配是运行多个程序的最简单的存储管理方法。 这可以将内存用户区域划分为多个固定大小的区域，并且只需要将作业加载到每个分区中，就可以将用户区域划分为多个分区，并且同时允许多个作业。 如果存在空分区，则可以从外部备份作业队列中选择适当大小的作业并将其加载到分区中，如果作业完成，则可以确保另一个作业已从备份作业队列转入分区。 分割分区的方法可以用两种方法来将存储器用户空间分割为若干固定大小的分区： (1)即使所有存储器分区的大小相同，分区的大小也是相同的。 其缺点是缺乏灵活性，即程序过小会浪费内存空间程序过大，导致加载程序的分区不足，无法运行程序。 (2)区域大小不同。 存储器部分可以划分为多个小分区、适量的中等分区和少量的大分区，以克服分区大小相等而不灵活的缺点。 因此，可以根据程序的大小来分配适当的分区。 内存分配通常按大小对分区进行排队，以便于内存分配，并创建分区使用表。 每个表中的条目都包含每个分区的起始地址、大小和状态(是否已分配)。 如图4-5(a )所示。 载入使用者程式后，记忆体配置程式会搜寻表格，找到符合要求的未配置分割区，并将其配置给程式，如果找不到足够大小的分割区，使表格项目的状态为已配置，则为该使用者专业人员存储空间分配如图4-5(b )所示。 此外，图4-5固定分区使用表、动态分区分配以及动态分配期间根据过程的实际需要动态分配空间。 实现可变分区分配存在三个问题：用于分配分区的数据结构、分区分配算法以及分区分配和收集工作。 此外，为了在分区分配期间实现数据结构分区分配，必须在系统中安排适当的数据结构来描述空分区和所分配的分区的情况，以及为分配提供依据。 一般的数据结构包括： (1)空分区表。 在系统中设置记录每个可用分区状况的可用分区表。 每个空分区占用一个表条目，其中包含数据项，如分区编号、分区的起始地址和分区大小。(2)空分区链。 为了实现空分区的分配和链接，请在每个分区的开头设置用于控制分区分配的信息，以及用于链接每个分区的前向指针。区域的末尾设置有后向指针，前向链接指针和后向链接指针而且，图4-6空闲链结构、区域分配算法1 )首次适配(first fit )算法要求空闲区域链以地址升序进行链接。 在分配内存时，从链的开头开始按顺序搜索，直到找到满足请求的可用分区，然后根据作业的大小从该分区中剪切内存空间并将其分配给请求者，使剩馀的可用分区保留在可用链中如果从链标题到链标题找不到满足请求的分区，则此次内存分配将失败并返回。 该算法倾向于优先利用存储器中的低地址部分的空闲分区，并且确保高地址部分的空闲区域较大。这为后来到达的大工作创造了大的存储空间分配条件。 其缺点是，由于低地址部分不断分割，残留有很多难以利用的小的空闲分区，因此每次的检索从低地址部分开始，检索空闲分区时的开销一定会增加。 另外，561832，0，56，74，106，2 )环初始自适应算法(nextfit )该算法从初始自适应算法演进而来。 为进程分配内存空间时，不是每次从链标题中进行搜索，而是从上次发现的空分区的下一个空分区中进行搜索，找到满足请求的空分区，从其中剪切与请求大小相同的内存空间，分配给作业。 要实现此算法，必须设置指示下一个开始引用的空分区的开始引用指针，并采用循环引用方法。 也就是说，如果最后一个(链端)可用分区的大小尚未满足要求，则必须返回到第一个可用分区并比较该大小是否满足要求。 找到后，必须调整起始参照指针。 此算法可以更均匀地分配内存中的可用分区，从而降低搜索可用分区的开销，但缺少可用分区。3 )自适应算法(bestfit )是指每次向作业分配内存时，都能够满足要求，始终向作业分配最小的空闲分区，避免“最大材料使用”。 为了加速搜索，该算法要求所有空分区按容量从小到大的顺序形成空分区链。 这样，满足首次发现要求的空闲区域必然是最佳的。 从孤立角度来看，最优自适应算法似乎是最优的，但宏观上并非总是如此。 由于每次分配被剪切的剩馀部分总是最小的，所以在存储器中残留了很多难以利用的小的空闲空间。 4 )最差自适应算法(worstfit )最差自适应分配算法扫描空分区表或整个链接表，始终选择最大空闲空间供工作。 其优点是剩馀的可用区域不应过小，碎片发生的概率最小，有利于中、小作业，同时最优自适应分配算法的搜索效率高。 该算法要求所有可用分区按容量从大到小的顺序形成可用分区链，并检查第一个分区是否满足工作要求。 但是，该算法的缺点也很明显，内存没有大的空闲分区。 最坏自适应算法也称为连续搜索法，以及上述的初始自适应算法、循环初始自适应算法和最佳自适应算法。5 )快速自适应算法(quickfit )此算法也称为分类搜索方法，该方法通过以空分区的容量大小对空分区进行分类，并为每个类具有相同容量的所有空分区单独创建空分区链路表。 在系统中存在多个可用分区链接表的同时，在内存中设置管理索引表，表中的每个条目与可用分区类型相对应，并记录该类型的可用分区链接表头的指针。 可用分区的分类可以按照该过程中通常使用的空间大小进行分类，并且对于其它大小的分区(例如，2KB、4KB、8KB )，例如7KB的可用区域可以放入8KB的链路表中或者放入特定的可用区域链路表中。 该算法的优点在于具有高检索效率，并且根据该过程的长度，只需找到能够存储它的最小空闲链路表并拆除第一个块进行分配。 另外，在该算法中，在分配空分区时，不会分割任何分区，因此可以保留大的分区，满足大容量的需求，也不会发生内存碎片。 此算法的缺点是当分区返回到主存储器中时，该算法复杂且系统开销较大。 另外，由于该算法在分配空分区时以程序为单位，一个分区仅属于一个程序，因此分配给程序的一个分区多少有些浪费。 空闲分区的划分越细，浪费的越严重，总体上浪费的存储空间越多，通常是在空间中交换时间的方式。此外，分区分配操作1 )为了分配存储器系统，需要使用某种分配算法从空分区链(表)中找到所需大小的分区。 如果所请求的分区的大小为u.size，则表中的空闲分区的大小可以表示为m.size。 如果m.size-u.size-size (其中size是预定义的未断开的剩馀分区的大小)，则可以将整个分区分配给请求者(即，超过size的剩馀部分)，而无需断开连接。 按照该分区请求的大小分配内存空间，其馀部分仍保留在空分区链(表)中。 然后，返回分配给调用方的区域的起始地址。 图4-7中的存储器分配流程；2 )当完成回收存储器的过程并释放存储器时，系统基于回收区的起始地址从空闲区链(表)中找到相应的插入点，其中，可能发生以下四种情况之一： (1)回收区在插入点之前的此时，您必须将回收站与插入点之前的分区合并。 您只需调整上一个分区F1的大小，而不是为回收站分区指定新的表条目。 (2)回收区域与插入点的下一个空白区域F2相邻，参照图4-8(b )。 此时，虽然可以将2个分区合并形成新的空分区，但是将回收区的起始地址作为新的空分区的起始地址，大小为两者的和。 在图4-8的存储器回收时，(3)回收区同时与插入点前、后两个区域相邻，参照图4-8(c )。 合并三个分区，然后使用F1条目和F1起始地址取消F2条目，使其大小为三个和。 (4)回收区与F1和F2都不相邻。 此时，回收区必须分别创建新的表单条目，填写回收区的起始地址和大小，并根据起始地址插入自由链中的相应位置。 合作伙伴系统、固定分区和动态分区方案都存在缺点。 固定分区方案限制了活动进程的数量，如果进程的大小与可用分区的大小不匹配，则内存空间利用率较低。 动态分区方式的算法很复杂，在回收空分区时需要分区整合等，系统开销很大。 合作伙伴系统方式是上述两种存储方式的权衡。 合作伙伴系统规定为大小是2的k次方，k是整数，l-8 k-m而不考虑所分配的分区或空闲分区。 其中，21是所分配的最小分区的大小，2m是所分配的最大分区的大小，并且通常2m是整个可分配存储器的大小。 应当注意的是，当前的操作系统通常采用基于下面描述的寻呼和分段机制的虚拟存储器机制，该机制比合作伙伴算法更合理、更高效，但是在多处理器系统中在上述分类搜索算法和合作伙伴系统算法中，哈希算法根据分区的大小来对空分区进行分类，并为每个类别具有相同大小的空分区单独设置空分区链接表。 如果要为进程分配空间，则必须在管理索引表中查找与所需空间大小对应的表条目，然后从中检索相应的可用分区链接表头指针，以通过检索检索可用分区。 当空分区的分类数目较小时，适当的空分区链接表的数目较大，从而选择适当的空分区表的开销增加并且时间性能会降低。 此外，散列算法通过利用散列的快速搜索优势以及空分区在可用空间表中的分布规则来建立散列函数，以空分区的大小为关键字创建散列表，该表中的每个表项目表示对应的空分区在进行空分区的分配时，根据需要的空分区的大小用散列函数进行计算，从而得到散列表中的位置，从中得到相应的空分区链接表，实现最佳的分配策略。 此外，可重定位的分区分配和动态重定位的引入必须以连续分配方式将系统或用户程序加载到连续的存储空间中。 如果系统具有多个较小的分区，则无法将程序加载到内存中，因为这些分区不相邻，即使这些总容量大于要加载的程序。例如，在图4-9(a )中，示出了存在于存储器中的所有四个彼此不相邻的小区，它们的容量分别为10KB、30KB、14KB和26KB，其总容量为80KB。 然而，由于当工作到达时需要40KB的内存容量并在其上必须分配连续空间，因此工作不能进行。 这种不可利用的小区称为“零头”或“碎片”。 此外，图4-9的紧凑示意图采用如下方法：在要加载作业时，移动存储器内的所有作业，使它们全部相邻，由此将原来的分散的多个小区域连接成一个大区域，并在此时将作业放入该区域。 通过这样移动在存储器内工作的场所，将原来的多个分散的小区块连接到一个大区块的方法称为“连接”或“紧凑”，参照图4-9(b )。 一些紧凑的用户程序在存储器内的位置发生变化，因此，如果不变更(变换)程序和数据的地址，则无法执行程序。 因此，每当变得“紧凑”时，就必须重新配置移动的程序和数据。 应当注意，以动态重新定位的实现方式，在作业被加载到存储器中之后的所有地址仍然是相对地址，并将相对地址转换为物理地址的操作推迟到程序指令实际执行。 为了防止地址转换影响指令的执行速度，需要硬件地址转换机构的支持，需要在系统中增设定位寄存器，存储程序(数据)的存储器内的起始地址。 在执行程序时，实际访问的存储器地址通过相对地址加上定位寄存器的地址来形成。 地址转换过程称为动态位置，因为它会在程序运行时自动访问指令和数据。 如果系统将存储器设置为“紧凑”，一些程序从存储器的一个位置移动到另一个位置，则无需改变程序，只需用该程序的存储器的新起始地址替换原始起始地址即可。 此外，在图4-10中的动态重新定位视图、动态重新定位分区分配算法、动态重新定位分区分配算法和动态分区分配算法基本上相同，因为这样的分配算法仅仅增加了紧凑的功能，通常，用户可以使用动态分区分配算法此外，图4-11动态分区分配算法的流程图、交换和交换的引入是在多个程序环境下执行的，其中由于存储器中的一些进程没有发生事件，因此被块执行，但是占用了存储器区域，并且， 存储器内的所有进程都可能被阻塞，停止CPU并等待，而许多工作可能等待在外部存储器上，因为没有存储器，所以无法进行存储器的运行。 显然，这对于系统资源是一项严重的浪费，会降低系统吞吐量。 为了解决这个问题，在系统中增设了更换(也称为更换)的设施。 “交换”是指将暂时无法在内存中运行的进程或暂时不使用的程序或数据调用到外部内存中，确保足够的内存空间，将已经具有运行条件的进程或进程所需的程序或数据读入内存。 交换是提高内存使用率的有效措施。 如果交换是整个过程的单元，则称为“整体交换”或“过程交换”。 此交换广泛应用于时分系统，其目的是解决内存紧张问题，进一步提高内存利用率。 此外，如果交换以“页”或“段”为单位进行，则分别称为“页交换”或“段交换”，统称为“部分交换”。 为了实现过程交换，系统必须实现交换空间管理、过程交换、过程交换三个功能。 另外，交换空间的管理在具有交换功能的OS中，通常将外部存储器分割为文件区域和交换区域。 前者用于存储文件，后者用于存储来自内存的进程。由于普通文件比较长地存在于外部，因此文件区域管理的主要目标是提高文件存储区域的利用率，从而对文件区域采用离散的分配方式。 但由于流程在交换区滞留时间短，交换操作频繁，交换空间管理的主要目标是提高流程交换和交换的速度。 因此，采用连续分配方式，很少考虑外部存储器的碎片化。 此外，为了能够管理交换区域的空闲磁盘块，在系统中配置适当的数据结构，记录外部存储器的使用状况。 其形式与存储器在动态分区分配方式中使用的数据结构相