动态分区分配四种算法例题

在操作系统中，内存管理是一个核心功能，动态分区分配是实现内存管理的一种方法。首次适应算法是一种常用的动态分区分配策略，它按照分区在内存中的物理地址顺序进行分配。具体来说，当有一个新的进程需要内存时，系统会搜索整个内存空间，从头开始找到第一个足够大的空闲分区来满足进程的需求。如果该分区的大小正好等于进程需求，就将整个分区分配给该进程；如果分区比进程需求大，则会将分区分割，将需求大小的部分分配给进程，剩余的部分继续作为空闲分区留在内存中。 参考资源链接：[四川大学操作系统历年真题详解与解析](https://wenku.csdn.net/doc/7c9u2f2oc6?spm=1055.2569.3001.10343) 首次适应算法的优点在于它的简单易实现，且由于它从内存的低地址开始查找，通常能够更好地利用内存中的低地址空间。但是，它也可能导致内存中留下较多的碎片，因为小的空闲分区可能会分散在内存的各个地方。这可能会导致当有新的大进程到来时，无法找到足够大的连续空闲分区来分配，即使总的空闲内存足够多。 例如，假设内存的初始状态是一个大小为100KB的连续空闲分区，如果按顺序分配内存请求如下：首先分配了20KB，接着分配了30KB，这时内存中会留下一个50KB的空闲分区；如果接下来的请求是分配一个35KB的分区，首次适应算法会在这个50KB的空闲分区前分配，尽管内存中总共还有80KB的空间，但因为没有一个连续的35KB空闲分区，所以请求失败。 了解首次适应算法的工作原理对于理解内存管理的动态分区策略至关重要。如果想要进一步深入学习计算机操作系统中的内存管理技术，建议查阅《四川大学操作系统历年真题详解与解析》。这本书不仅详细解析了首次适应算法和其他相关知识点，还包含了大量实际问题和例题，可以帮助考生在理论学习和实践应用方面达到更好的水平。 参考资源链接：[四川大学操作系统历年真题详解与解析](https://wenku.csdn.net/doc/7c9u2f2oc6?spm=1055.2569.3001.10343)

### 首次适应算法示例 首次适应算法从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业。这种方法旨在减少查找时间，并且为了适应此算法，空闲分区表（空闲区链）中的空闲分区间需按照地址由低到高排序[^2]。 假设有一个初始状态下有如下几个连续的空闲分区： | 地址范围 | 大小 | | -- | ---- | | 0-100 | 101 | | 200-500 | 301 | | 600-800 | 201 | 如果现在需要分配一个大小为 `150` 的新进程，则会找到第一个可以容纳它的区域即 `[200, 500]` 这一区间来放置这个新的进程。 ```python def first_fit(partitions, size_needed): for i in range(len(partitions)): start_addr, end_addr = partitions[i] partition_size = end_addr - start_addr + 1 if partition_size >= size_needed: new_end_addr = start_addr + size_needed - 1 # 更新剩余的空间 remaining_space = (new_end_addr + 1, end_addr) if new_end_addr < end_addr else None return { "allocated": (start_addr, new_end_addr), "remaining": remaining_space, "index": i } raise Exception("No suitable space found.") ``` ### 最佳适应算法示例 最佳适应算法是从全部空闲区中找出能满足作业请求的、且大小最小的那个空闲分区来进行分配，这样可以使产生的碎片尽可能的小[^1]。 继续沿用上面的例子，当尝试分配同样大小为 `150` 的新进程时，最佳适应会选择 `[600, 800]` 中的一个子集作为目标位置，因为这是能刚好适合所需尺寸的最小可用空间。 ```python import sys def best_fit(partitions, size_needed): min_diff = sys.maxsize chosen_index = -1 for i in range(len(partitions)): start_addr, end_addr = partitions[i] current_partition_size = end_addr - start_addr + 1 diff = abs(current_partition_size - size_needed) if current_partition_size >= size_needed and diff < min_diff: min_diff = diff chosen_index = i if chosen_index != -1: start_addr, end_addr = partitions[chosen_index] allocated_start = start_addr allocated_end = start_addr + size_needed - 1 # 计算并返回未使用的部分 unused_part = (allocated_end + 1, end_addr) if allocated_end < end_addr else None return {"allocated": (allocated_start, allocated_end), "unused": unused_part} raise Exception("Insufficient memory to allocate the process.") ``` ### 最坏适应算法示例 最坏适应算法则是选择最大的那个空闲区块进行划分，以此方式试图保持较小规模的自由块不被分割得过碎。对于相同的需求——分配 `150` 单位的新进程，最坏适应将会挑选 `[200, 500]` 来完成此次操作，因为它拥有足够的空间并且是当前列表里最大的一块空白区域[^3]。 ```python def worst_fit(partitions, size_needed): max_size = -sys.maxsize chosen_index = -1 for i in range(len(partitions)): start_addr, end_addr = partitions[i] current_partition_size = end_addr - start_addr + 1 if current_partition_size > max_size and current_partition_size >= size_needed: max_size = current_partition_size chosen_index = i if chosen_index != -1: start_addr, end_addr = partitions[chosen_index] allocated_start = start_addr allocated_end = start_addr + size_needed - 1 # 返回剩下的那部分 leftover = (allocated_end + 1, end_addr) if allocated_end < end_addr else None return {"allocated": (allocated_start, allocated_end), "leftover": leftover} raise Exception("Not enough contiguous free blocks available.") ```