固定分区、可变式分区分配及段页式分区分配c代码实现

墨蓝 2022-05-23 00:46 173阅读 0赞

本实验通过三种分区分配的方法，分别是固定分区分配、可变分区分配及段页式分区分配，从连续内存分区分配方式到离散分区分配方式。段页式的采用减少了碎片的产生，极大地提高了内存空间的利用率，但是却增加了访存的次数，因此，可以采用快表机制，减少访存的次数，对段页式存储管理进行优化。

1、固定分区分配回收内存空间代码

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    #define getpch(type) (type*)malloc(sizeof(type))
    int SIZE;
    struct sif //内存分区使用说明表
    {
        int id;
        int size;
        int begin_adress;
        char status;//F-已分配，T-未分配
        struct sif *next;
    }*p,*ready=NULL;
    
    typedef struct sif SIF;
    
    int allocate(int size)//分配内存，返回0代表分配成功
    {
        p=ready;
        while(p!=NULL)
        {
            if((p->status=='T')&&(p->size>=size))
            {
                p->status='F';
                return 1;
            }
            p=p->next;
        }
        return 0;
    }
    void disp()//打印内存分配情况
    {
        printf("\n 当前内存分配情况如下：\n");
        printf("\n |id |size |begin_adress |status \n");
        p=ready;
        while(p!=NULL)
        {
            printf("\n %d| %d| %d| %c\n",p->id,p->size,p->begin_adress,p->status);
            p=p->next;
        }
    }
    void Input()
    {
        int num,i,j,d=0,id=0;
        SIF *last=ready;
        printf("\n 请输入现有内存的大小:  (起始地址从0开始) \n");
        scanf("%d",&SIZE);
        //初始化内存信息
        printf("\n 请输入固定分区不同内存块的个数: ");
        scanf("%d",&num);
        for(i=0; i<num; i++)
        {
            int n;
            printf("\n 请输入%f KB内存的个数: ",pow(2,4+i));
            scanf("%d",&n);
            for(j=0; j<n; j++)
            {
                p=getpch(SIF);
                p->id=id++;
                p->size=(int)(pow(2,4+i));//size是按照2的指数递增的
                p->begin_adress=d;
                if((rand()%2)==0)//是否被分配初始化
                    p->status='T';
                else
                    p->status='F';
                p->next=NULL;
                d+=p->size;
                if(d>=SIZE)
                {
                  printf("\n 已超出系统总内存量,%d号分配失败 \n",p->id);
                  break;
                }
                if(ready==NULL)
                {
                    ready=p;
                    last=ready;
                }
                else
                {
                    last->next=p;
                    last=last->next;
                }
            }
        }
        disp();//打印内存说明表
    }
    void allocation()
    {
        int num1;
        int i,s;
        //给作业分配内存空间
        printf("\n 请输入待分配内存的作业个数：");
    
    
        scanf("%d",&num1);
        for(i=0; i<num1; i++)
        {
            printf("\n 请输入第%d个作业的大小: ",i);
            scanf("%d",&s);
            if(allocate(s)==1)
            {
                printf("\n 已为该作业分配内存空间\n");
                printf("\n 存储该作业内存空间的详细信息如下：\n");
                printf("\n 内存块号：%d, 内存大小：%d \n",p->id,p->size);
            }
            else
                printf("\n 未能该该作业分配内存 \n");
        }
        disp();
    }
    void recover()//作业完成后回收资源
    {
        int i,k,num;
        printf("\n 请输入需要释放的作业个数: ");
        scanf("%d",&num);
        for(i=0; i<num; i++)
        {
            printf("\n 请输入存储该作业的内存分区说明表的ID \n");
            scanf("%d",&k);
            p=ready;
            while(p!=NULL)
            {
                if(p->id==k)
                {
                    p->status='T';
                    printf("\n 已释放该作业所占用的资源 \n");
                    break;
                }
                p=p->next;
            }
        }
        disp();
    }
    int main()
    {
        int command;
        Input();//初始化内存说明表
        printf("\n 请输入命令，给作业分配资源输入1，释放资源输入2，退出请输入任意键：\n");
        scanf("%d",&command);
        while(1)
        {
            if(command==1)
                allocation();
            else if(command==2)
                recover();
            else
                break;
            printf("\n 请继续输入命令 \n");
            scanf("%d",&command);
        }
        return 0;
    }

2、可变分区分配并回收内存空间（首次适应法）

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #define getpch(type) (type*)malloc(sizeof(type))
    int SIZE;
    int id=0;
    struct sif //内存分区使用说明表
    {
        int id;
        int size;
        int begin_adress;
        char status;//F-已分配，T-未分配
        struct sif *next;
    }*p,*ready=NULL;
    
    typedef struct sif SIF;
    
    int allocate(int size)//分配内存
    {
        p=ready;
        while(p!=NULL)
        {
            if((p->status=='T')&&(p->size>=size))
            {
                p->status='F';
                if(((p->size)-size)>0)//若分配后存在碎片
                {
                    if((p->next->status)=='T')//若下一相邻存储块未被分配，将此碎片与相邻存储片合并
                    {
                        p->next->begin_adress=p->next->begin_adress-(p->size-size);
                        p->next->size=p->next->size+(p->size-size);
                        p->next=p->next->next;
                    }
                    else//若下一相邻存储块已被分配，为此碎片新建一存储块
                    {
                        SIF *q=getpch(SIF);
                        q->id=id++;
                        q->size=(p->size)-size;
                        q->status='T';
                        q->begin_adress=p->begin_adress+size;
                        q->next=p->next;
                        p->next=q;
                        p->size=size;
                    }
                }
                return 1;
            }
            p=p->next;
        }
        return 0;
    }
    void disp()//显示当前内存分配情况
    {
        printf("\n 当前内存分配情况如下：\n");
        printf("\n |id |size |begin_adress |status \n");
        p=ready;
        while(p!=NULL)
        {
            printf("\n %d| %d| %d| %c\n",p->id,p->size,p->begin_adress,p->status);
            p=p->next;
        }
    }
    void Input()
    {
        int d=0;
        SIF *last=ready;
        printf("\n 请输入现有内存的大小:  (起始地址从0开始) \n");
        scanf("%d",&SIZE);
        //初始化内存信息
        while(d!=SIZE)
        {
            p=getpch(SIF);
            p->id=id++;
            p->size=rand()%(63-1+1)+1;//使用随机函数分配存储块size
            p->begin_adress=d;
            if((id%2)==1)
                p->status='F';
            else
                p->status='T';
    
            p->next=NULL;
            if(d>(SIZE-(p->size)))
            {
                p->size=SIZE-d;
            }
            d+=p->size;
            if(ready==NULL)
            {
                ready=p;
                last=ready;
            }
            else
            {
                last->next=p;
                last=last->next;
            }
        }
        disp();//打印内存说明表
    }
    void allocation()//采用首次适应算法分配内存
    {
        int num1;
        int i,s;
        //给作业分配内存空间
        printf("\n 请输入待分配内存的作业个数：");
    
        scanf("%d",&num1);
        for(i=0; i<num1; i++)
        {
            printf("\n 请输入第%d个作业的大小: ",i);
            scanf("%d",&s);
            if(allocate(s)==1)
            {
                printf("\n 已为该作业分配内存空间\n");
                printf("\n 存储该作业内存空间的详细信息如下：\n");
                printf("\n 内存块号：%d, 内存大小：%d \n",p->id,p->size);
            }
            else
                printf("\n 未能该该作业分配内存 \n");
        }
        disp();
    }
    void recover()//作业完成后回收资源
    {
        int i,k,num;
        printf("\n 请输入需要释放的作业个数: ");
        scanf("%d",&num);
        for(i=0; i<num; i++)
        {
            printf("\n 请输入存储该作业的内存分区说明表的ID \n");
            scanf("%d",&k);
            p=ready;
            SIF *q=getpch(SIF);
    
            while(p!=NULL)
            {
                if(p->id==k)
                {
                    p->status='T';
    
                    if((q->status=='T')&&(p->next->status=='T'))//释放资源上下相邻块均未存储信息,合并三块为一块
                    {
                        (q->size)+=p->size+p->next->size;
                        (q->next)=p->next->next;
                    }
                    if((q->status=='T')&&(p->next->status=='F'))//相邻上块未分配，下层已分配，合并上层及当前块
                    {
                        (q->size)+=p->size;
                        (q->next)=p->next;
                    }
                    if((q->status=='F')&&(p->next->status=='T'))//相邻下块未分配，上层已分配，合并下层及当前块
                    {
                        p->size=(p->size)+(p->next->size);
                        p->next=p->next->next;
                    }
    
                    printf("\n 已释放该作业所占用的资源 \n");
                    break;
                }
                q=p;
                p=p->next;
            }
        }
        disp();
    }
    int main()
    {
        int command;
        Input();//初始化内存说明表
        printf("\n 请输入命令，给作业分配资源输入1，释放资源输入2，退出请输入任意键：\n");
        scanf("%d ",&command);
        while(1)
        {
            if(command==1)
                allocation();
            else if(command==2)
                recover();
            else
                break;
            printf("\n 请继续输入命令 \n");
            scanf("%d",&command);
        }
        return 0;
    }

3、段页式存储管理分配内存空间并实现逻辑地址转换功能

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #define getpch(type) (type*)malloc(sizeof(type))
    
    int n;//全局变量，段表长度
    
    typedef struct page//页表
    {
        int id;
        int b_num;
        struct black *b;
    }pg;
    
    typedef struct paragraph//段表
    {
        int id;//段号
        int size;
        struct page *adress;//页内地址
    }ph;
    
    ph PH[10];
    pg PG[10][10];
    
    void disp()
    {
        printf("\n 当前段表分配情况如下：\n");
        printf("\n |id |pagesize |page_b_adress \n");
        int i;
        for(i=0; i<(int)(sqrt(n)); i++)
        {
            printf("\n %d\t%d\t%d \n",PH[i].id,PH[i].size,PH[i].adress);
        }
    
        printf("\n 当前页表分配情况如下：\n");
        int j;
        for(i=0; i<(int)(sqrt(n)); i++)
        {
            printf("\n  第%d段页内分配情况如下：\n",i);
            printf("\n |id  | b_num \n");
            for(j=0;j<(int)(sqrt(PH[i].size));j++)
            printf("\n %d\t%d \n",PG[i][j].id,PG[i][j].b_num);
        }
    }
    void Input()//输入函数
    {
        int i,d,m;
        printf("\n 初始化段表 \n");
        printf("\n 请输入段表的起始地址、段表的长度：");
        scanf("%d%d",&d,&n);
    
        m=d;
        for(i=0; i<(int)(sqrt(n)); i++)
        {
            PH[i].id=i;
            int j=rand()%4;
            PH[i].size=(int)(pow(2,j));//页表长度
            PH[i].adress=m;
            m+=PH[i].size;
            int k;
            for(k=0; k<j; k++)
            {
                PG[i][k].id=k;//每个页面2KB
                PG[i][k].b_num= rand()%(127-0+1)+1;
            }
        }
        disp();
    }
    int adress_mapping()//地址映射函数
    {
        int a,b,c,n1=0,d=0;
        printf("\n请依次输入作业的段号、段内页号及业内地址： ");
        scanf("%d%d%d",&a,&b,&c);
        if(a>n)//判断是否越界
        {
            printf("\n 您输入的段号已越界 \n");
            return -1;
        }
    
        //若未越界,则进入页表
        int j=sqrt(PH[a].size);
        if(b>j)
        {
            printf("\n 您输入的页号已越界 \n");
            return -1;
        }
    
        //若未越界，则返回物理地址
        return PG[a][b].b_num*256+c;
    
    }
    
    int main()
    {
        Input();
        int command;
        printf("\n 计算物理地址请按1，退出请按0 \n");
        scanf("%d",&command);
        while(command==1)
        {
            printf("\n %d \n",adress_mapping());
            printf("\n 计算物理地址请按1，退出请按0 \n");
            scanf("%d",&command);
        }
    }