连续分配：为用户进程分配的必须是一个连续的内存空间
单一连续分配
在单一连续分配中，内存被分为系统区和用户区
系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据
内存中只能有一道用户程序，用户程序独占整个用户区空间
优点：实现简单，无外部碎片，可以采用覆盖技术扩充内存，不一定需要采取内存保护
缺点：只适用于单用户、单任务的操作系统，有内部碎片，存储器利用率极低
固定分区分配
将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业
- 分区大小相等：缺乏灵活性，适用于一台计算机控制多个相同对象的场合
- 分区大小不等：增加灵活性，可以满足不同大小的进程需求
操作系统建立一个分区说明表来实现各个分区的分配和回收。每个表项对应一个分区，包括对应分区的大小、起始地址、状态（是否已分配）
当用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为已分配
优点：实现简单、无外部碎片
缺点：当用户程序太大时，可能所有的分区都不能满足要求，此时不得不采用覆盖技术来解决，但这会使得性能降低；会产生内部碎片，内存利用率低
动态分区分配
又称为可变内存分配。不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的
系统应该用什么数据结构记录内存的使用情况
- 空闲分区表：每个空闲分区对应一个表项，表项中包含分区号、起始地址、分区大小、状态等信息
- 空闲分区链：每个分区的起始部分和末尾部分分别设置一个前向指针和后向指针，起始部分还可记录分区大小等信息
当有很多空闲分区都能满足需求时，应该选择哪个分区进行分配
涉及到四种动态分区分配算法，文章后面会展开
如何进行分区的分配和回收，假设是空闲分区表
分配：更新表项（大小、起始地址）或者删除表项
回收：回收区有相邻空闲分区，表项合并
内部碎片和外部碎片
动态分区分配没有内部碎片，但是有外部碎片
内部碎片：分配给某进程的内存区域中，有些部分没用上
外部碎片：内存中某些空闲分区由于太小而难以利用
可以用紧凑技术解决外部碎片：挪位挪出较大的空闲分区
换入换出技术、中级调度（内存调度）
动态分区分配应该采用动态重定位方式
动态分区分配算法
在动态分区分配方式中，如果有多个空闲分区满足要求，应该选择哪个
-
首次适应算法
算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区
实现：空闲分区以地址递增的次序排列，每次分配内存时顺序查找空闲分区链（空闲分区表），找到大小能够满足要求的第一个空闲分区 -
最佳适应算法
算法思想：为了保证大进程到来时能有连续的大片空间，尽可能多的留下大片的空闲区，优先使用更小的空闲区
实现：空闲分区按照容量递增次序排列，每次分配内存时顺序查找空闲分区链（空闲分区表），找到大小能够满足要求的第一个空闲分区
缺点：每次都选最小的分区进行分配，会留下越来越多的很小的难以利用的碎片（外部碎片） -
最坏适应算法
算法思想：为了减少外部碎片的产生，每次分配时优先使用最大的连续空闲块，这样分配后剩余的空闲区不会太小，更方便利用
实现：空闲分区按照容量递减排列，每次分配时按顺序查找空闲分区链（空闲分区表），找到第一个大小能满足要求的空闲区
缺点：每次都选择最大的分区，如果之后有大进程到来，可能没有足够大的空闲区可供分配 -
邻近适应算法
算法思想：首次适应算法每次都从头开始查找，可能导致低地址部分出现很多小的空闲分区，每次分配查找时，都要经过这些分区，增加了查找的开销。因此邻近适应算法选择从上次查找结束的位置开始检索
实现：空闲分区以地址递增的顺序排列（可以排成一个循环链表），每次分配内存时，从上次查找结束的位置开始查找空闲分区链（空闲分区表），找到大小能够满足要求的第一个空闲分区
首次适应算法每次都从头查找，如果低地址有满足需求的分区时，更有可能用到低地址的小分区，更有可能把高地址的大分区留下来
邻近适应算法更可能会导致高地址的大分区被使用，导致无大分区可用
最佳和最坏分配后需要更新空闲区排列，开销大
网友评论