c语言 最佳适应算法 640kb

C语言最佳适应算法是一种动态存储分配策略，用于管理内存的分配和释放。它的目标是在给定分区大小和内存需求的情况下，找到合适的空闲分区进行分配，以最大限度地减少内存的碎片化。

这个算法的基本思想是遍历内存中的分区，找到第一个大小能够满足需求的空闲分区。但不仅仅是找到满足需求的分区，而是找到大小最接近需求的分区，即最佳适应。

具体实现中，算法会维护一个已分配列表和一个空闲分区列表。当内存需要被分配时，算法会遍历空闲分区列表，找到一个最接近需求大小的空闲分区进行分配。如果找不到大小合适的分区，就需要进行内存的碎片整理或者申请更多的内存。

相比于首次适应和循环首次适应算法，最佳适应算法选择分区的能力更加灵活，可以减少分配给某一特定大小的分区，从而减少内存的碎片化。但是这个算法也有一定的缺点，因为需要遍历分区列表，所以在分配内存时可能会比较耗时。

总而言之，C语言最佳适应算法是一种根据需求大小选择最接近的空闲分区的动态内存分配策略，旨在减少内存碎片化，并提高内存的利用率。

相关问题

动态分区最佳适应算法c语言,使用最佳适应算法对内存实现模拟动态分区管理...

以下是使用最佳适应算法对内存实现模拟动态分区管理的 C 语言代码：

#include<stdio.h>

#define MAX_SIZE 100

int free_blocks[MAX_SIZE];

int main()
{
    int i, n, choice;
    int mem_size, block_size, block_num, frag_size;
    int best_fit(int);
    void allocate(int, int);
    void deallocate(int, int);
    void display();

    printf("Enter the total memory size: ");
    scanf("%d", &mem_size);

    printf("Enter the number of blocks: ");
    scanf("%d", &n);

    for(i=0; i<n; i++){
        printf("Enter the size of block %d: ", i+1);
        scanf("%d", &free_blocks[i]);
    }

    while(1){
        printf("\n1. Allocate Memory\n2. Deallocate Memory\n3. Display\n4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch(choice){
            case 1: // Allocate Memory
                printf("Enter the size of memory block to be allocated: ");
                scanf("%d", &block_size);
                block_num = best_fit(block_size);
                if(block_num == -1){
                    printf("Memory allocation failed! No suitable block found.\n");
                }
                else{
                    allocate(block_num, block_size);
                    printf("Memory allocated successfully.\n");
                }
                break;

            case 2: // Deallocate Memory
                printf("Enter the block number to be deallocated: ");
                scanf("%d", &block_num);
                if(block_num < 1 || block_num > n){
                    printf("Invalid block number!\n");
                }
                else{
                    deallocate(block_num-1, free_blocks[block_num-1]);
                    printf("Memory deallocated successfully.\n");
                }
                break;

            case 3: // Display
                display();
                break;

            case 4: // Exit
                return 0;

            default:
                printf("Invalid choice!\n");
        }
    }

    return 0;
}

int best_fit(int block_size){
    int i, best_block = -1, best_frag = MAX_SIZE;

    for(i=0; i<n; i++){
        if(free_blocks[i] >= block_size && free_blocks[i]-block_size < best_frag){
            best_block = i;
            best_frag = free_blocks[i]-block_size;
        }
    }

    return best_block;
}

void allocate(int block_num, int block_size){
    free_blocks[block_num] -= block_size;
}

void deallocate(int block_num, int block_size){
    free_blocks[block_num] += block_size;
}

void display(){
    int i;

    printf("\nMemory Status:\n");

    for(i=0; i<n; i++){
        printf("Block %d: %d KB\n", i+1, free_blocks[i]);
    }
}

在这个代码中，`free_blocks` 数组用于存储每个空闲块的大小，`n` 是空闲块的数量。`best_fit` 函数使用最佳适应算法来查找最适合分配请求的内存块，并返回该块的编号。`allocate` 函数用于将给定大小的内存块分配给指定的内存块编号。`deallocate` 函数用于释放给定内存块编号中的内存块。`display` 函数用于显示当前内存块的状态。

在程序开始时，用户输入总内存大小和空闲块的数量以及每个空闲块的大小。然后，用户可以使用菜单选择内存分配和释放操作，或者显示当前内存块的状态，或者退出程序。

C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloca（）和回收过程free（）。其中空闲分区通过空闲分区链来管理；在进行内存分配时，系统优先是有空闲分区低端的空间,假设初始状态下的可用的内存空间为640KB，自行设计作业的请求序列,分别采用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况的代码

首次适应算法的代码实现：

#include <stdio.h>

// 定义内存块结构体
typedef struct mem_block {
    int start_addr;  // 起始地址
    int size;        // 大小
    struct mem_block *next;  // 下一个空闲内存块
} MemBlock;

MemBlock *free_head;  // 空闲分区链表头指针

// 初始化空闲分区链表
void init_free_list() {
    free_head = (MemBlock *)malloc(sizeof(MemBlock));
    free_head->start_addr = 0;
    free_head->size = 640;
    free_head->next = NULL;
}

// 显示空闲分区链表状态
void display_free_list() {
    MemBlock *p = free_head;
    printf("空闲内存分区链表：\n");
    while (p != NULL) {
        printf("起始地址：%d，大小：%d\n", p->start_addr, p->size);
        p = p->next;
    }
}

// 首次适应算法的内存分配函数
int first_fit_alloc(int size) {
    MemBlock *p = free_head;
    MemBlock *pre = NULL;

    // 遍历空闲分区链表，找到第一个符合要求的分区
    while (p != NULL) {
        if (p->size >= size) {
            break;
        }
        pre = p;
        p = p->next;
    }

    // 没有找到符合要求的内存块
    if (p == NULL) {
        printf("没有足够的内存空间！\n");
        return -1;
    }

    // 找到了符合要求的内存块，进行分配
    int start_addr = p->start_addr;
    int remaining_size = p->size - size;

    // 如果分配后剩余空间不足以存放一个 MemBlock 结构体，则直接将这个分区作为已分配分区
    if (remaining_size < sizeof(MemBlock)) {
        if (pre == NULL) {
            free_head = p->next;
        } else {
            pre->next = p->next;
        }
    } else {
        // 否则，将这个分区分裂成两个
        p->size = size;
        p->start_addr = start_addr;
        start_addr += size;
        p = (MemBlock *)start_addr;
        p->size = remaining_size - sizeof(MemBlock);
        p->start_addr = start_addr;
        p->next = NULL;
        if (pre == NULL) {
            free_head = p;
        } else {
            pre->next = p;
        }
    }

    printf("分配成功！起始地址：%d，大小：%d\n", start_addr, size);
    return start_addr;
}

// 内存回收函数
void my_free(int start_addr) {
    MemBlock *p = (MemBlock *)start_addr;
    MemBlock *pre = NULL;

    // 遍历空闲分区链表，找到要回收的内存块应该插入的位置
    while (p > free_head && p < free_head->next) {
        pre = free_head;
        free_head = free_head->next;
    }

    // 将要回收的内存块插入到空闲分区链表中
    if (pre == NULL) {
        p->next = free_head;
        free_head = p;
    } else {
        p->next = pre->next;
        pre->next = p;
    }

    // 尝试合并相邻的空闲分区
    MemBlock *curr = free_head;
    while (curr != NULL && curr->next != NULL) {
        if (curr->start_addr + curr->size == curr->next->start_addr) {
            curr->size += curr->next->size + sizeof(MemBlock);
            curr->next = curr->next->next;
        } else {
            curr = curr->next;
        }
    }

    printf("回收成功！\n");
}

int main() {
    init_free_list();
    display_free_list();

    // 采用首次适应算法进行内存分配和回收
    printf("\n采用首次适应算法进行内存分配和回收：\n");
    first_fit_alloc(80);
    display_free_list();
    first_fit_alloc(120);
    display_free_list();
    first_fit_alloc(200);
    display_free_list();
    my_free(80);
    display_free_list();
    first_fit_alloc(100);
    display_free_list();
    first_fit_alloc(250);
    display_free_list();
    my_free(200);
    display_free_list();

    return 0;
}

最佳适应算法的代码实现：

#include <stdio.h>

// 定义内存块结构体
typedef struct mem_block {
    int start_addr;  // 起始地址
    int size;        // 大小
    struct mem_block *next;  // 下一个空闲内存块
} MemBlock;

MemBlock *free_head;  // 空闲分区链表头指针

// 初始化空闲分区链表
void init_free_list() {
    free_head = (MemBlock *)malloc(sizeof(MemBlock));
    free_head->start_addr = 0;
    free_head->size = 640;
    free_head->next = NULL;
}

// 显示空闲分区链表状态
void display_free_list() {
    MemBlock *p = free_head;
    printf("空闲内存分区链表：\n");
    while (p != NULL) {
        printf("起始地址：%d，大小：%d\n", p->start_addr, p->size);
        p = p->next;
    }
}

// 最佳适应算法的内存分配函数
int best_fit_alloc(int size) {
    MemBlock *p = free_head;
    MemBlock *pre = NULL;
    MemBlock *best_p = NULL;
    MemBlock *best_pre = NULL;
    int best_size = 640;

    // 遍历空闲分区链表，找到最小的符合要求的分区
    while (p != NULL) {
        if (p->size >= size && p->size < best_size) {
            best_p = p;
            best_pre = pre;
            best_size = p->size;
        }
        pre = p;
        p = p->next;
    }

    // 没有找到符合要求的内存块
    if (best_p == NULL) {
        printf("没有足够的内存空间！\n");
        return -1;
    }

    // 找到了符合要求的内存块，进行分配
    int start_addr = best_p->start_addr;
    int remaining_size = best_p->size - size;

    // 如果分配后剩余空间不足以存放一个 MemBlock 结构体，则直接将这个分区作为已分配分区
    if (remaining_size < sizeof(MemBlock)) {
        if (best_pre == NULL) {
            free_head = best_p->next;
        } else {
            best_pre->next = best_p->next;
        }
    } else {
        // 否则，将这个分区分裂成两个
        best_p->size = size;
        best_p->start_addr = start_addr;
        start_addr += size;
        best_p = (MemBlock *)start_addr;
        best_p->size = remaining_size - sizeof(MemBlock);
        best_p->start_addr = start_addr;
        best_p->next = NULL;
        if (best_pre == NULL) {
            free_head = best_p;
        } else {
            best_pre->next = best_p;
        }
    }

    printf("分配成功！起始地址：%d，大小：%d\n", start_addr, size);
    return start_addr;
}

// 内存回收函数
void my_free(int start_addr) {
    MemBlock *p = (MemBlock *)start_addr;
    MemBlock *pre = NULL;

    // 遍历空闲分区链表，找到要回收的内存块应该插入的位置
    while (p > free_head && p < free_head->next) {
        pre = free_head;
        free_head = free_head->next;
    }

    // 将要回收的内存块插入到空闲分区链表中
    if (pre == NULL) {
        p->next = free_head;
        free_head = p;
    } else {
        p->next = pre->next;
        pre->next = p;
    }

    // 尝试合并相邻的空闲分区
    MemBlock *curr = free_head;
    while (curr != NULL && curr->next != NULL) {
        if (curr->start_addr + curr->size == curr->next->start_addr) {
            curr->size += curr->next->size + sizeof(MemBlock);
            curr->next = curr->next->next;
        } else {
            curr = curr->next;
        }
    }

    printf("回收成功！\n");
}

int main() {
    init_free_list();
    display_free_list();

    // 采用最佳适应算法进行内存分配和回收
    printf("\n采用最佳适应算法进行内存分配和回收：\n");
    best_fit_alloc(80);
    display_free_list();
    best_fit_alloc(120);
    display_free_list();
    best_fit_alloc(200);
    display_free_list();
    my_free(80);
    display_free_list();
    best_fit_alloc(100);
    display_free_list();
    best_fit_alloc(250);
    display_free_list();
    my_free(200);
    display_free_list();

    return 0;
}