基于索引的动态分区分配算法c实现

以下是基于索引的动态分区分配算法的C语言实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_PROCESS 100

typedef struct {
    int id;         // 进程ID
    int size;       // 进程大小
} Process;

typedef struct {
    int start;      // 分区起始地址
    int size;       // 分区大小
    int pid;        // 存放进程ID，若为空则为-1
} Partition;

int num_partition;  // 分区数量
Partition partitions[MAX_PROCESS];  // 分区表
int num_process;    // 进程数量
Process processes[MAX_PROCESS];     // 进程表

void initialize() {
    int i;
    for (i = 0; i < MAX_PROCESS; i++) {
        partitions[i].start = -1;
        partitions[i].size = -1;
        partitions[i].pid = -1;
        processes[i].id = -1;
        processes[i].size = -1;
    }
    num_partition = 0;
    num_process = 0;
}

void print_partitions() {
    int i;
    printf("Partition Table:\n");
    printf("Start\tSize\tPID\n");
    for (i = 0; i < num_partition; i++) {
        printf("%d\t%d\t%d\n", partitions[i].start, partitions[i].size, partitions[i].pid);
    }
    printf("\n");
}

void print_processes() {
    int i;
    printf("Process Table:\n");
    printf("ID\tSize\n");
    for (i = 0; i < num_process; i++) {
        printf("%d\t%d\n", processes[i].id, processes[i].size);
    }
    printf("\n");
}

int allocate_partition(int pid) {
    int i, j;
    for (i = 0; i < num_partition; i++) {
        if (partitions[i].pid == -1 && partitions[i].size >= processes[pid].size) {
            partitions[i].pid = pid;
            j = i + 1;
            while (j < num_partition && partitions[j].pid == -1 && partitions[j].size >= processes[pid].size) {
                partitions[j - 1].size = partitions[j].size;
                partitions[j - 1].pid = partitions[j].pid;
                j++;
            }
            partitions[j - 1].size = processes[pid].size;
            partitions[j - 1].pid = pid;
            partitions[j].start = partitions[j - 1].start + partitions[j - 1].size;
            partitions[j].size = partitions[i].start + partitions[i].size - partitions[j].start;
            partitions[j].pid = -1;
            num_partition++;
            return i;
        }
    }
    return -1;
}

void deallocate_partition(int index) {
    int i;
    partitions[index].pid = -1;
    for (i = index + 1; i < num_partition && partitions[i].pid == -1; i++) {
        partitions[i - 1].size = partitions[i].size;
        partitions[i - 1].pid = partitions[i].pid;
    }
    partitions[i - 1].pid = -1;
    num_partition--;
}

int main() {
    int choice, pid, index;
    initialize();
    while (1) {
        printf("1. Add process\n2. Remove process\n3. Print partition table\n4. Print process table\n5. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                printf("Enter process ID: ");
                scanf("%d", &pid);
                printf("Enter process size: ");
                scanf("%d", &processes[pid].size);
                index = allocate_partition(pid);
                if (index == -1) {
                    printf("Unable to allocate partition for process %d.\n", pid);
                } else {
                    printf("Process %d allocated partition %d.\n", pid, index);
                }
                break;
            case 2:
                printf("Enter process ID: ");
                scanf("%d", &pid);
                deallocate_partition(partitions[pid].start);
                printf("Process %d deallocated partition.\n", pid);
                break;
            case 3:
                print_partitions();
                break;
            case 4:
                print_processes();
                break;
            case 5:
                exit(0);
            default:
                printf("Invalid choice.\n");
                break;
        }
    }
    return 0;
}

该算法的主要思路是维护一个分区表和一个进程表，每当有新的进程需要分配内存时，就在分区表中查找合适的空闲分区来存放该进程，并将分区表中的分区重新调整以保证空闲分区连续。当进程需要释放内存时，就在分区表中查找该进程所占用的分区，并将该分区释放。