连续分配方式
连续分配方式
复习定位
在分页出现之前——程序必须被装在一块连续的内存区域中。连续分配面临的核心矛盾：给程序分配一大块连续的空闲空间——但分配/回收过程中内存被切成很多小碎片——导致大程序进不来。这一矛盾直接驱动了分页存储管理的发明。
单一连续分配
最简单的内存管理方式——内存被分为两个区域:系统区(存放操作系统,通常在低地址)和用户区(一个用户程序)。任何时刻的用户在内存里只有一个用户程序在运行——用户程序独占整个用户区。MS-DOS和早期单用户单任务系统使用此模式。优点：管理极其简单——无需保护用户区之间的隔离。缺点：不能执行多道程序、CPU在用户程序等待I/O时闲置——CPU利用率很低。
固定分区
将用户区预先划分为若干个固定大小的分区——每个分区可以容纳一道程序。分区的数量决定了多道程序度。每个分区有长度——也可设置不同大小的小分区用于小作业、大分区用于大作业减少浪费。
固定分区的缺点——分区大小是预先确定的——如果一个分区大小为8MB——而一道程序只需要3MB——该分区内的5MB就完全未被使用(内部碎片)。反之——如果一道程序需要9MB——现有的分区最大才8MB——无法运行该程序——尽管总空闲内存可能超过9MB。
动态分区
不预先划分分区——程序需要多少内存就分配多少。系统维护一个空闲分区表和已分配分区表——当一个新进程需要内存时在空闲分区中找一块满足大小的可用区域切割分配。当进程退出时——它所持有的分区归还为空闲——如果前后有空闲块则合并。
动态分配算法比较：
首次适应(First Fit)——从空闲分区链表的表头开始扫描——找到第一个大小足够的分区。分配速度很快——因为很快找到第一个可用块。但低址部分留下大量无法分配给大程序的小碎片(外碎片)。首次适应的总体性能被认为是最好的——实现简单且在高地址保留了较大的空闲块。
循环首次适应(Next Fit)——从上一次分配结束的位置继续往下扫描——而不是每次都从链表头开始——避免低址区碎片集中。但碎片分布到整个地址空间——当分配大块时可能很难找到连续的较大块。
最佳适应(Best Fit)——选择满足需求但尺寸最小的空闲块——"最小可用"——直觉上可以减少碎片尺寸。但实际上——每次分配后留下的残留碎片都极小——随着时间的推移这些小碎片越来越小完全无法再利用——长期性能比首次适应更差。因此最佳适应是名字好听但实际表现最差的算法之一。
最坏适应(Worst Fit)——选最大的空闲块分配——使余下的空闲块仍然较大——更容易满足后续较大的分配。但很快最大的块也被切割了——碎片随着进展均匀地缩小到不可用。
碎片问题与紧凑
内部碎片：固定分区中分配给某作业的空间没有用完的部分——这部分完全浪费。
外部碎片：动态分区中——经过反复的分配和释放——空闲空间的总体大小足够满足某个新请求——但空间是分散的小片——没有一块连续的大块可以容纳该程序。例如总空闲内存共20MB但分别分布在如0-8KB、100-108KB等微小空间单元中而无法分配一个8MB的程序——这种现象就是外部碎片。
紧凑(Compaction)：通过移动已分配分区的位置——将分散的小空闲块合并为一大块连续空闲。需要动态重定位支持(MMU硬件)——而且紧凑过程中所有进程都必须暂停——对实时交互系统开销较大。
复习检查
固定分区的内部碎片和动态分区的外部碎片在成因上有什么不同——一个分区内没被用到被称为内部碎片——因为给程序的内存块比实际需求大——而外部碎片发生在区外的空闲区域过于分散而不是在一个分区的边界内。
首次适应算法将小碎片集中在低地址——为什么这对其后的"为大程序寻找空闲区"造成困难？
紧凑技术为什么不能在分页存储管理中被用来处理外碎片——分页的离散分配理念不是自然就不再有紧凑的需求了吗？
动态分区中释放分区时——如果前后分区都是空闲——需要将三个连续的空闲空间合并成一个大的——链表结构允许通过向前和向后的指针查找相邻的空闲区域——描述合并前后的指针变化逻辑。
首次适应好还是循环首次适应好？在碎片分布上的长时间系统表现是不是循环更好？