编写C语言程序，模拟实现首次/最佳/最坏适应算法的内存块分配和回收，要求每次分配和回收后显示出空闲分区和已分配分区的情况。假设初始状态下，可用的内存空间为640KB。（江西师范大学软件学院 操作系统）_编写c程序,采用最优适应算法的内存块分配与回收,要求每次分配与回收后显示出空闲

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

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

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

可变分区分配策略:

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

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

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

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

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

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

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

#include <stdio.h>
 
#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 < MEMORY_SIZE / BLOCK_SIZE; i++) {
        if (memory[i].is_free && memory[i].size >= 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 < MEMORY_SIZE / BLOCK_SIZE; i++) {
        if (memory[i].is_free && memory[i].size >= 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）