动态分区存储管理

悠悠 2022-01-31 12:57 362阅读 0赞

实验目的：熟悉并掌握动态分区分配的各种算法。

熟悉并掌握动态分区中分区回收的各种情况，并能够实现分区合并。

实验内容：用高级语言模拟实现动态分区存储管理，要求：

1.  分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。
2.  分区的初始化——可以由用户输入初始分区的大小。（初始化后只有一个空闲分区，起始地址为0，大小是用户输入的大小）
3.  分区的动态分配过程：由用户输入作业号和作业的大小，实现分区过程。
4.  分区的回收：用户输入作业号，实现分区回收，同时，分区的合并要体现出来。（注意：不存在的作业号要给出错误提示！）
5.  分区的显示：任何时刻，可以查看当前内存的情况（起始地址是什么，大小多大的分区时空闲的，或者占用的，能够显示出来）

要求考虑：（1）内存空间不足的情况，要有相应的显示；

（2）作业不能同名，但是删除后可以再用这个名字；

（3）作业空间回收是输入作业名，回收相应的空间，如果这个作业名不存在，也要有相应的提示。

#include<stdio.h>
    #include<stdlib.h>
    #define SIZE 1024
    #define MINSIZE 5
    
    typedef struct Partition
    {
        int size;
        int addr;
        int state;// 分区状态(0为空闲，1为占用)
        int id;
        struct Partition* pre;
        struct Partition* next;
    
    }*part;
    
    part first,head;
    int a[1000000]={0} ;
    
    void show();
    int FF(int id,int size);
    void showPart();
    int BF(int id,int size);
    int freePart(int id);
    
    int main()
    {
        //初始化
    
        head = (struct Partition*)malloc(sizeof(struct Partition));
        first= (struct Partition*)malloc(sizeof(struct Partition));
        first->size = SIZE;
        first->addr =0;
        first->state =0;
        first->id =-1;
        first->pre =head;
        first->next = NULL;
    
        head->next = first;
        head->pre = NULL;
    
        show();
    
    
    
    
        return 0;
    }
    
    void show()
    {
        int flag,size,id;
        while(1)
        {
            printf("==============动态分区分配==================\n");
            printf("\n当前内存大小--->%d\n",SIZE);
            printf("\n1: 分配内存\n2: 回收内存\n0: 退出 \n");
    
            scanf("%d",&flag);
            if(flag == 0)
                break;
            else if(flag == 1)
            {
                while(1)
                {
                    int flag1 = 0;
                    printf("请输入要进行的算法：（1：首次适应、2：最佳适应）\n");
                    scanf("%d",&flag1);
                    if(flag1 == 1)
                    {
                        int temp =0;
                        printf(" 请输入作业名( >0 )： ");
                        scanf("%d", &id);
                        printf(" 请输入需要分配的内存大小( >0 )： ");
                        scanf("%d", &size);
    
                        if(a[id]!=0)
                        {
                            printf("作业名重复！请重新输入\n");
                            break;
                        }
                        else
                            a[id] =1;
    
                        temp = FF(id, size);
                        if(temp == 1)
                        {
                            system("cls");
                            printf("内存分配成功！ \n");
                            showPart();
                        }
                        else
                        {
                            printf("内存分配失败 ！\n");
                        }
    
                    }
                    else if(flag1 == 2)
                    {
    
                        int temp =0;
                        printf("请输入作业名( >0 )： ");
                        scanf("%d", &id);
                        printf("请输入需要分配的内存大小( >0 )： ");
                        scanf("%d", &size);
    
                        if(a[id]!=0)
                        {
                            printf("作业名重复！请重新输入\n");
                            break;
                        }
                        else
                            a[id] =1;
    
                        temp = BF(id, size);
                        if(temp == 1)
                        {
                            system("cls");
                            printf("内存分配成功！ \n");
                            showPart();
                        }
                        else
                        {
                            printf("内存分配失败！\n");
                        }
                    }
                    else
                        break;
                    printf("\n输入0即可退出！\n");
                }
            }
    
            else if(flag == 2)
            {
                int temp = 0;
                printf("请输入要回收的作业名： ");
                scanf("%d", &id);
                if(a[id] ==0)
                {
                    printf("作业名不存在！请重新输入\n");
                }
                else
                    a[id] =0;
                temp = freePart(id);
                if(temp == 1)
                {
                    system("cls");
                    printf("内存分区回收成功!\n");
                    showPart();
                }
                else
                    printf("内存分区回收失败!\n");
    
            }
            else
            {
                printf(" 输入错误，请重新输入！\n");
            }
        }
    }
    
    int FF(int id,int size)
    {
    
        part p = head->next;
        while(p != NULL)
        {
            //查找空闲分区
            if(p->state == 0 && p->size >= size)
            {
                if(p->size - size <= MINSIZE)
                {
                    p->state = 1;
                    p->id = id;
    
                }
                else
                {
                    //指针后移，腾出size大小的空间
    
                    part q = (struct Partition*)malloc(sizeof(struct Partition));
                    q->addr = p->addr + size;
                    q->size = p->size - size;
                    q->state = 0;
                    q->id = -1;
    
    
    
                    q->pre = p;
                    q->next = p->next;
                    if(p->next != NULL)
                    {
                        p->next->pre = q;
                    }
                    p->next = q;
    
    
                    // 修改分配的空间数据
                    p->size = size;
                    p->state = 1;
                    p->id = id;
                }
                return 1;
            }
            p = p->next;
        }
        return 0;
    }
    void showPart()
    {
    
        printf("\n");
        printf("=========================================\n");
        printf("起始地址 空间大小 工作状态 作业号\n");
        part p = head->next;
        while(p != NULL)
        {
            printf("\n");
            printf("%d\t ", p->addr);
            printf("%d\t ", p->size);
            printf("%d\t ", p->state);
            if(p->id > 0)
            {
                printf("%d ", p->id);
            }
            else
            {
                printf(" ");
            }
            printf("\n");
            p = p->next;
        }
        printf("=========================================\n");
    }
    
    int freePart(int id)
    {
        int flag =0;
        part p = head->next;
        part q;
    
        while(p!=NULL)
        {
            if(p->state == 1 && p->id == id)
            {
                flag =1;
                //合并上下分区
                if((p->pre != head && p->pre->state == 0)&&(p->next != NULL &&p->next->state ==0))
                {
                    q =p;
                    p = p->pre;
                    p->size += q->size;
                    p->next = q->next;
                    q->next->pre = p;
                    free(q);
    
    
    
                    q = p->next;
                    p->size += q->size;
                    p->next = q->next;
                    if(q->next != NULL)
                    {
                        q->next->pre = p;
                    }
                    free(q);
                }
                else if((p->pre == head || p->pre->state == 1)&&(p->next != NULL &&p->next->state ==0))//合并下分区
                {
                    q = p->next;
                    p->size += q->size;
                    p->state = 0;
                    p->id = -1;
                    p->next = q->next;
                    if(q->next != NULL)
                    {
                        q->next->pre = p;
                    }
                    free(q);
                }
    
                else if((p->pre != head && p->pre->state == 0)&&(p->next == NULL || p->next->state ==1))
                {
                    q = p;
                    p = p->pre;
                    p->size += q->size;
                    p->next = q->next;
                    if(q->next != NULL)
                    {
                        q->next->pre = p;
                    }
                    free(q);
                }
    
                else
                {
                    p->state = 0;
                    p->id = -1;
                }
            }
            p =p->next;
        }
    
    
        if(flag == 1)
            return 1;
        else
            return 0;
    }
    
    int BF(int id,int size)
    {
        part min = NULL;
        int minSize = SIZE+1;
    
        part p = head->next;
    
        while(p)
        {
            if(p->state == 0 && p->size >= size && p->size < minSize)
            {
                min = p;
                minSize = p->size;
            }
            p = p->next;
        }
        while(min != NULL)
        {
            //查找空闲分区
            if(min->state == 0 && min->size >= size)
            {
                if(min->size - size <= MINSIZE)
                {
                    min->state = 1;
                    min->id = id;
    
                }
                else
                {
                    //指针后移，腾出size大小的空间
    
                    part q = (struct Partition*)malloc(sizeof(struct Partition));
                    q->addr = min->addr + size;
                    q->size = min->size - size;
                    q->state = 0;
                    q->id = -1;
    
    
    
                    q->pre = min;
                    q->next = min->next;
                    if(min->next != NULL)
                    {
                        min->next->pre = q;
                    }
                    min->next = q;
    
    
                    // 修改分配的空间数据
                    min->size = size;
                    min->state = 1;
                    min->id = id;
                }
                return 1;
            }
            min = min->next;
        }
        return 0;
    }