【操作系统】分区分配算法 （首次适应算法、最佳适应算法、最坏适应算法）（C语言实现）

为了实现动态分区分配，通常将系统中的空闲分区链接成一个链。所谓顺序查找是指依次搜索空闲分区链上的空闲分区，去寻找一个大小能满足要求的分区。 ——–计算机操作系统（第四版）

可变分区也称动态分区，在指作业装入内存时，从可用的内存中划出一块连续的区域分配给他，且分区大小正好等于改作业的大小。

可变分区分配策略:

1.首次适应算法：地址递增，从链首开始

2.最佳适应算法：性能最差，容量递减，浪费最小

3.最坏适应算法：分区大小递减，整合碎片，提高利用率

首次适应算法的话可以不断的去遍历寻找空间是否为空余的。

最佳适应算法的话是要找到最佳适配的空余区域，但是也会导致空闲区被利用之后可能会有一下片内存没被利用，而这小的碎片也很难再次被利用。

最坏适应算法的话是要找到最大空间来分配内存，这样剩余的空间也会最大，这样的话可以更有效的去减少出现小碎片的情况。

分配内存的时候，总是会想到C语言有个malloc函数可以分配内存。所以我写这份作业的时候抱有这是理解malloc函数的成分在里面的。一开始本来是用vector来存放空闲链表，后来觉得要符合底层的话，还是得用纯的c语言来写更好一点。

#include #define MEMORY_SIZE 640 // 内存大小（单位：KB）#define BLOCK_SIZE 1 // 内存块大小（单位：KB）// 内存块结构体typedef struct {int size; // 大小（单位：KB）int is_free; // 是否空闲} block_t;// 内存块数组block_t memory[MEMORY_SIZE / BLOCK_SIZE];// 初始化内存块数组void init_memory() {int i;for (i = 0; i < MEMORY_SIZE / BLOCK_SIZE; i++) {memory[i].size = BLOCK_SIZE;memory[i].is_free = 1;}}// 显示内存分配情况void print_memory() {int i, free_blocks = 0, allocated_blocks = 0, free_size = 0, allocated_size = 0;printf("\n------------------------------\n");printf("Memory Allocation\n");printf("------------------------------\n");for (i = 0; i < MEMORY_SIZE / BLOCK_SIZE; i++) {printf("%d ", i);if (memory[i].is_free) {printf("Free ");free_blocks++;free_size += memory[i].size;}else {printf("Allocated ");allocated_blocks++;allocated_size += memory[i].size;}printf("%dKB\n", memory[i].size);}printf("------------------------------\n");printf("Total Blocks: %d\n", free_blocks + allocated_blocks);printf("Free Blocks: %d\n", free_blocks);printf("Allocated Blocks: %d\n", allocated_blocks);printf("Total Size: %dKB\n", free_size + allocated_size);printf("Free Size: %dKB\n", free_size);printf("Allocated Size: %dKB\n", allocated_size);printf("------------------------------\n\n");}// 首次适应算法分配内存int first_fit_allocation(int size) {int i, j;int blocks_needed = (size + BLOCK_SIZE - 1) / BLOCK_SIZE; // 需要的块数for (i = 0; i < MEMORY_SIZE / BLOCK_SIZE; i++) {if (memory[i].is_free) { // 如果当前块为空闲块int free_blocks = 0;for (j = i; j < MEMORY_SIZE / BLOCK_SIZE && memory[j].is_free; j++) {free_blocks++;if (free_blocks == blocks_needed) { // 如果找到了足够的空闲块for (j = i; j < i +blocks_needed; j++) {memory[j].is_free = 0;}return i; // 返回分配的起始块的索引}}}}return -1; // 分配失败}// 最佳适应算法分配内存int best_fit_allocation(int size) {int i, j;int blocks_needed = (size + BLOCK_SIZE - 1) / BLOCK_SIZE; // 需要的块数int best_index = -1, best_size = MEMORY_SIZE / BLOCK_SIZE + 1; // 初始化为无效值for (i = 0; i = blocks_needed) { // 如果当前块为空闲块并且大小足够if (memory[i].size < best_size) { // 如果当前块更小best_index = i;best_size = memory[i].size;}}}if (best_index == -1) { // 分配失败return -1;}else {for (j = best_index; j < best_index + blocks_needed; j++) {memory[j].is_free = 0;}return best_index; // 返回分配的起始块的索引}}// 最坏适应算法分配内存int worst_fit_allocation(int size) {int i, j;int blocks_needed = (size + BLOCK_SIZE - 1) / BLOCK_SIZE; // 需要的块数int worst_index = -1, worst_size = -1; // 初始化为无效值for (i = 0; i = blocks_needed) { // 如果当前块为空闲块并且大小足够if (memory[i].size > worst_size) { // 如果当前块更大worst_index = i;worst_size = memory[i].size;}}}if (worst_index == -1) { // 分配失败return -1;}else {for (j = worst_index; j < worst_index + blocks_needed; j++) {memory[j].is_free = 0;}return worst_index; // 返回分配的起始块的索引}}// 回收内存void deallocation(int start_index) {int i;for (i = start_index; i < MEMORY_SIZE / BLOCK_SIZE && !memory[i].is_free; i++) {memory[i].is_free = 1;}}int main() {int choice, size, start_index;init_memory();do {print_memory();printf("1. First Fit Allocation\n");printf("2. Best Fit Allocation\n");printf("3. Worst Fit Allocation\n");printf("4. Deallocation\n");printf("0. Exit\n");printf("Enter your choice: ");scanf_s("%d", &choice);switch (choice) {case 1:printf("Enter the size to be allocated (in KB): ");scanf_s("%d", &size);start_index = first_fit_allocation(size);if (start_index == -1) {printf("Memory allocation failed.\n");} else {printf("Memory allocated from block %d to %d.\n", start_index, start_index + (size + BLOCK_SIZE - 1) / BLOCK_SIZE - 1);}break;case 2:printf("Enter the size to be allocated (in KB): ");scanf_s("%d", &size);start_index = best_fit_allocation(size);if (start_index == -1) {printf("Memory allocation failed.\n");}else {printf("Memory allocated from block %d to %d.\n", start_index, start_index + (size + BLOCK_SIZE - 1) / BLOCK_SIZE - 1);}break;case 3:printf("Enter the size to be allocated (in KB): ");scanf_s("%d", &size);start_index = worst_fit_allocation(size);if (start_index == -1) {printf("Memory allocation failed.\n");}else {printf("Memory allocated from block %d to %d.\n", start_index, start_index + (size + BLOCK_SIZE - 1) / BLOCK_SIZE - 1);}break;case 4:printf("Enter the starting block index to be deallocated: ");scanf_s("%d", &start_index);deallocation(start_index);printf("Memory deallocated from block %d.\n", start_index);break;case 0:printf("退出...\n");break;default:printf("没有这个选项\n");}} while (choice != 0);return 0;}

因为是用vs写的代码，所以用的是scanf_s。如果换别的编译器的话得改一下。

（大家看完点个赞再走，这个对我真的很重要QwQ）