分区存储管理中常用的分配策略有哪些及优缺点比较

第四种是最坏适应算法（Worst Fit），它将空闲分区按内存大小递减的顺序排序链接。分配时从头开始查找，将第一个满足进程需要的空闲分区分配给它，实际上就是分配最大的空闲分区。这种策略基于不留下碎片空闲区出发，分配后的剩余部分仍能再分配。

第三种是最佳适应算法（Best Fit），它将空闲分区按内存大小递增的顺序排序链接。当需要分配内存时，从头开始查找，将第一个满足进程需要的空闲分区分配给它。这里的“第一个”是指在按大小排序后的链表中，符合大小要求的最小分区，旨在减少剩余碎片的大小。

关于空闲区利用，最佳适应算法被认为最佳，因为它倾向于留下较小的碎片。最先适应算法的另一个优点是尽可能利用低地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的进程或作业。而最坏适应算法则是基于不留下碎片空闲区出发，选择最大空闲区满足用户需求。

比较最佳适应算法和最坏适应算法，它们的相同点在于都按分区容量大小进行排序，且每次都是从头开始查询，将第一个满足进程需求的空闲分区分配给请求进程。不同点在于链接顺序：最佳适应算法按容量从小到大顺序链接，而最坏适应算法按容量从大到小顺序链接，因此最坏适应算法总是分配最大的空闲分区。

再比较首次/循环首次适应算法与最佳/最坏适应算法。首次/循环首次适应算法是按照地址递增的次序进行排列并链接到一起的。而最佳/最坏适应算法则是按照容量大小递增或递减的次序排列并链接到一起的，这种根本的排序依据不同导致了它们性能表现的差异。

解决动态分区产生的外部碎片问题，常用的内存分配策略有四种。首先是首次适应算法（First Fit），它将空闲分区以地址递增的次序排序并链接。当需要分配内存时，从头开始按顺序查找，将第一个能满足进程所需大小的空闲分区分配给它。

动态分区分配方式在用户程序装入内存时，根据进程所需大小动态建立分区，使得分区大小刚好符合进程需要，从而在初期取得了较好的分配效果。但随着内存进程的需要和时间的推移，内存中会产生许多外部碎片。为了解决这个问题，通常采用紧凑技术将多个细小碎片合并成一个较大的外部碎片。

其次是循环首次适应算法（Next Fit），它将空闲区域按地址递增次序排序连接。首次查找时从头开始，将第一个满足大小的空间分配给进程；非首次查找时，则从上次查找结束的位置开始继续查找，注意这与首次适应算法的区别在于查找起始点的不同。

分区存储管理主要分为连续分配和非连续分配两大类，其中连续分配方式包括单一连续、固定分区和动态分区。单一连续分配将内存分为系统区和用户区，内存中永远只有一道程序，适用于单用户单任务操作系统，其优点是实现简单且无外部碎片，但缺点是存在内部碎片且存储器利用率低，不适合现代多道程序环境。

在查找速度、释放速度和空闲区利用这三个方面，各算法表现各异。从搜索速度上看，最先适应算法拥有最佳性能，因为它是顺序查找且通常能较快找到合适的分区。回收过程中，最先适应算法也是最佳，因为它能保持空闲分区链的顺序不变或调整开销较小。

固定分区分配方式无论分区大小是否相等，都便于内存分配和管理。其优点在于管理相对简单，但缺点也很明显：当程序较大时，如果无法放入任何一个固定分区，该程序就无法运行。此外，主存利用率较低，会出现内部碎片，不过好在这种方式不会产生外部碎片。