大二作业——操作系统实验——C语言用双向链表，模拟实现动态分区式存储管理

实验：动态分区式存储管理

实验内容：

编写程序模拟完成动态分区存储管理方式的内存分配和回收。实验具体包括：首先确定内存空闲分配表；然后采用最佳适应算法完成内存空间的分配和回收；最后编写主函数对所做工作进行测试。

实验提示

由于是实验，没有真正的内存分配。所以在实验中首先应建立一张空闲区表，初始状态只有一个空闲登记项（假定的内存空闲区）和一张所有状态都为“空”的已分配区表。假定内存空间110KB，OS占用10KB，其余为空闲区。然后可以选择进行内存分配或回收：若是分配，要求输入作业名和所需内存空间大小；若是回收，输入回收作业的作业名。程序循环进行内存分配和回收，直到用户选择退出系统。在每次作业提交（内存分配）及作业结束（内存回收）时显示两张表的内容，以检查内存的分配和回收是否正确。

用C语言编程实现：

#include<stdio.h>
#include<malloc.h>
typedef struct storage
{
    int name;
    int size;
    int startaddress;
    int stuta;//0表示空闲；1表示已分配
    storage* next;
    storage* front;
}storage;
//初始化
void initialize(storage *s,int name){
    s->name=name;
    s->size=0;
    s->startaddress=0;
    s->stuta=0;
    s->front=NULL;
    s->next=NULL;
}
//判断是否可以分配0表示不能分配，1表示可以分配
int IFallocation(storage *s,int Size)
{
    storage *p;
    while (s!=NULL)
    {
        p=s->next;
        if(s->stuta==0 && s->size>Size)//空闲而且存在 够分的情况
        {
            return 1;
        }
        s=p;
    }
    printf("不允许分配\n");
    return 0;
}
//分配
void allocation(storage* head,int name,int size)
{
    //找最佳位置
        //创建两个指针 一个扫描移动 一个记录最佳
        //假设头指针就是最佳插入位置
        //扫描 先看是不是空闲区  在看能不能分配  在看是不是最佳位置
    storage *h,*p,*great;
    h=head;
    while(h){
        p=h->next;
        if(h->stuta==0)
        {
            great=h;
            if(h->size>size)
            {
                if(h->size<great->size)
                {
                    great=h;
                }
            }
        }
        h=p;
    }
    //创建节点
    p=(storage*)malloc(sizeof(storage));
    initialize(p,great->name);
    //修改数据
    p->size=great->size-size;
    p->startaddress=great->startaddress+size;
    great->size=size;
    great->stuta=1;
    //链接
        //分为尾部为空的链接  和不为空的链接
    if(great->next==NULL)
    {
        p->next=great->next;
        p->front=great;
        great->next=p;
    }
    else
    {
        p->next=great->next;
        p->next->front=p;
        great->next=p;
        p->front=great;
    }
    printf("分配成功\n");
}
//回收有四种情况
//return 0则是找不到name return 1是成功
int recycle(storage** head,int name)
{
    //根据名字找到节点
    storage *h,*p;
    h=*head;
    while (h!=NULL)
    {
        p=h->next;
        if(h->name==name && h->stuta==1)
        {
            break;
        }
        h=p;
    }
    if(h==NULL)
    {
        printf("任务不存在\n");
        return 0;
    }
    //根据几点前后 区块 和区块 空闲情况回收
        //如果不用合并只需要把状态设置为0
        //如果下面有节点而且空闲则合并
        //如果上面有几点而且空闲则合并
    h->stuta=0;
    if(h->next && h->next->stuta==0)
    {
        //修改值
        h->next->size+=h->size;
        h->next->startaddress=h->startaddress;
        //链接
        if(h==*head)
        {
            *head=h->next;
            h->next->front=NULL;
        }
        else{
            h->next->front=h->front;
            h->front->next=h->next;
        }
        //释放
        p=h->next;
        free(h);
        h=p;
    }
    if(h->front &&h->front->stuta==0)
    {
        //修改值
        h->front->size+=h->size;
        //链接
        if(h->next)
        {
            h->next->front=h->front;
            h->front->next=h->next;
        }
        else{
            h->front->next=NULL;
        }
        //释放
        free(h);
    }
    printf("回收成功\n");
    return 1;
}
//显示分配情况
void display(storage*head){
    storage*p;
    while (head)
    {
        p=head->next;
        printf("片号%d，大小%d，状态%d，起始位置%d\n",head->name,head->size,head->stuta,head->startaddress);
        head=p;
    }
}
void Menu()
{
    printf("按1添加任务，按2删除任务，按0退出\n");
}
//退出
void Exit(storage*head)
{
    printf("1\n");
    storage*p,*h;
    h=head;
    while (h)
    {
        p=h->next;
        free(h);
        h=p;
    }
}
int main()
{
    int menu;
    storage*head;
    head=(storage*)malloc(sizeof(storage));    
    initialize(head,1);
    head->size=100;
    Menu();
    scanf("%d",&menu);
    while (menu)
    {
        display(head);
        if(menu==1)
        {
            int name,size;
            printf("请输入任务号");
            scanf("%d",&name);
            printf("请输入任务大小");
            scanf("%d",&size);
            if(IFallocation(head,size))
                {
                allocation(head,name,size);    
            }
        }
        if(menu==2)
        {
            int name;
            printf("请输入要删除的任务号");
            scanf("%d",&name);
            recycle(&head,name);
        }
        printf("本操作结束请再次选择操作");
        scanf("%d",&menu);
        Menu();
    }
    Exit(head);
    return 0;
}

欢迎批评指正。