分区式存储管理

设计性实验报告

实验题目：     分区式存储管理            

学    号：                   

姓    名：                     

完成时间：                   

一、实验概述

1.1 实验目的

1.通过本次实验，加深对内存管理的认识，进一步掌握内存的分配、回收算法的思想。

2.通过本次实验，加深掌握对数据结构的理解和进一步提高自己的编程能力。

1.2 任务描述

设计程序模拟内存的动态分区法存储管理。内存空闲区使用自由链管理，采用最坏适应算法从自由链中寻找空闲区进行分配，内存回收时假定不做与相邻空闲区的合并。

假定系统的内存共0K，初始状态为操作系统本身占用K。在t1时间之后，有作业A、B、C、D分别请求8K、16K、K、124K的内存空间；在t2时间之后，作业C完成；在t3时间之后，作业E请求50K的内存空间；在t4时间之后，作业D完成。要求编程序分别输出t1、t2、t3、t4时刻内存的空闲区的状态。

二、主要数据结构设计

1. 程序中自由链队列的结点类型可描述如下：

  struct freelink{

int len, address;  /* len为分区长度；address为分区起始地址

struct freelink    /* next;

}

2. 内存占用区用链表描述，其结点类型描述如下：

  struct busylink{

char name;   /*  作业或进程名  name=’S’ 表示OS占用

int len , address;

struct  busylink *next;

} 

3.设全程量：

struct  freelink   *free_head=NULL;     // 自由链队列（带头结点）队首指针

struct  busylink  *busy_head=NULL,    // 占用区队列队（带头结点）首指针

 struct  busylink  *busy_tail=NULL；   // 占用区队列队尾指针

三、主要函数设计

1．函数名称: requireMemo(char  name, int  require)

功能描述：在空闲区域链中找到第一个满足条件的结点，将其分配掉，如果结点的长度大于require，则剩下的又将作为一个空闲结点插入到空闲区域链中 

输入参数：char  name, int  require

输出参数：无

程序流程图： 

2．函数名称：void  freeMemo(char name)  

   功能描述：找到要回收的结点，将其释放，并将这个结点重新插入到空闲区域链中去

  输入参数：char name

  输出参数：无

  程序流程图：

将w插入到空闲区域链中时前的归并算法的流程图如下：

四、测试数据及运行结果

4．1 测试数据准备

假定系统的内存共0K，初始状态为操作系统本身占用K。在t1时间之后，有作业A、B、C、D分别请求8K、16K、K、124K的内存空间；在t2时间之后，作业C完成；在t3时间之后，作业E请求50K的内存空间；在t4时间之后，作业D完成。要求编程序分别输出t1、t2、t3、t4时刻内存的空闲区的状态。

4．2 运行结果及说明

1.测试目标:运用按最佳适应算法[1]（空闲区未归并时的）

运行结果:

2.测试目标:运用按最佳适应算法（空闲区归并时的）

运行结果:

五、实验总结

   首先，对链表又有进一步的理解，还有就是加深理解内存的分配与回收，分配与回收的策略，并掌握动态分区这种内存管理的具体实施方法。

   再者，就是在编程中遇到的困难，在编写归并程序首先是自己考虑问题不全面，写的程序就只顾及到一个结点，而没有实现有两个结点的情况，于是后来再加了一条else语句，就没有出现问题。还有一个问题就是将多余的结点free时也出现问题，加了一条if(s==NULL）,成立就释放掉。一开始把free语句写在while循环内，一旦把找到的结点释放掉，则找不到下一个结点，也会出错，所以应该把free放到while循环外。

六、参考文献

[1] 左万历，周长林，彭涛.计算机操作系统教程.第3版.北京：高等教育出版社,2010

附：程序源代码

按最先适应算法

#include 

#include

#include

struct freelink

{

    int len, address;  // len为分区长度；address为分区起始地址

    struct freelink  * next;

};

 //内存占用区用链表描述，其结点类型描述如下：

struct busylink

{

    char name;   //  作业或进程名  name='S' 表示OS占用

    int len , address;

    struct  busylink *next;

} ;

//并设全程量：

struct  freelink   *free_head=NULL;     // 自由链队列带头结点）队首指针?        

struct  busylink   *busy_head=NULL, *busy_tail=NULL;   // 占用区队列队（带头结点）首指针               

                       // 占用区队列队尾指针

// 设计子函数：

void  start(void)   /* 设置系统初始状态*/ 

{  

    struct freelink * p;

    struct busylink *q;

    free_head=(struct  freelink*)malloc(sizeof(struct  freelink));

free_head->next=NULL; // 创建自由链头结点

    busy_head=busy_tail=(struct busylink*)malloc(sizeof(struct busylink));

busy_head->next=NULL; // 创建占用链头结点

    p=( struct freelink *)malloc(sizeof(struct freelink));

p->address=;

p->len=0-; //（OS占用了K）

p->next=NULL;

free_head->next=p;

    q=( struct  busylink *)malloc(sizeof(struct busylink));

q->name='S';  /* S表示操作系统占用  */

q->len=; q->address=0; q->next=NULL;

busy_head->next=q; busy_tail=q;

}

void  requireMemo(char  name, int  require) /*模拟内存分配*/

{

    struct  freelink *w,*u,*v,*x,*y;

    struct busylink *p;

    x=free_head;

y=free_head->next;

    while((y!=NULL) &&(y->len    {

        x=y;

     y=y->next;

    }

    if(y!=NULL)

    {

        p=(struct busylink*)malloc(sizeof(busylink));

     p->name=name;

     p->address=y->address;

     p->len=require;

     p->next=NULL;

     busy_tail->next=p; //把p插入到busy_head的尾部

        busy_tail=p;

     w=x->next;

     x->next=w->next;

        if(w->len==require)

        {

            free(w);

        }

        else

        {

         w->address=w->address+require;

         w->len=w->len-require;

            u=free_head;

         v=free_head->next;

            while((v!=NULL) && (v->lenlen))//如果此结点还有多余，就此又重新插入到空闲区域链中（按照长度由小到大的次序排列）

            {

                u=v;

             v=v->next;

            }

         u->next=w;

         w->next=v;

        }

    }

    else 

        printf("can't allocate!\\n");

}

void  freeMemo(char name)  /* 模拟内存回收*/ 

{

    struct busylink *p,*q;

    struct freelink *w,*u,*v,*s1=NULL,*s2=NULL;

    int len,address;

    int flag1=1,flag2=1;

p=busy_head->next;

    while((p!=NULL)&&(p->name!=name)) //找到要回收的结点

    {

        q=p;

     p=p->next;

    }

    if(p==NULL)

    {

        printf("%c is not exist\\n",name);

    }

    else

    {

        if  (p==busy_tail) 

            busy_tail=q;

     q->next=p->next;

     len=p->len;

     address=p->address;

        free(p);

        w=(struct freelink*) malloc(sizeof(freelink));

     w->len=len;

     w->address=address;

        u=free_head;

     v=free_head->next;

        while((v!=NULL) && (flag1==1 || flag2==1))  //归并算法

        {

            if((w->address==(v->address+v->len)) &&flag1)

            {

                s1=v;

             u->next=s1->next;

             w->address=v->address;

             w->len+=v->len;

         v=v->next;

                flag1=0;

            }

            else if(((w->address+w->len)==v->address) &&flag2)

            {

                s2=v;

             u->next=s2->next;

             w->len+=v->len;

             v=v->next;

                flag2=0;

            }

            else

            {

                u=v;

             v=v->next;

            }

        }

        if(s1!=NULL)

            free(s1);

        if(s2!=NULL)

            free(s2);

        u=free_head;

     v=free_head->next;

        if(v!=NULL)

        {

            while((v!=NULL) && (v->lenlen))

            {

                u=v;

             v=v->next;

            }

        }

         u->next=w;

         w->next=v;

    }

}

void  past(int  time)  /* 模拟系统过了时间time，用sleep(),或者用个空循环*/

{

    sleep(5);

        printf("时间%d后：\\n",time);

}

void  printlink()  /* 输出内存空闲情况（自由链的结点） */ 

{

    struct  freelink   *p;

p=free_head->next;

    if(p==NULL)

        printf("无空闲区！\\n");

    else

    {

        while(p!=NULL)

        {

        printf("首地址:%d\长度:%d\\n",p->address,p->len);

     p=p->next;

        }

    }

    printf("----------------------------------------\\n");

}

void  printlink1()  /* 输出内存占用的情况 */ 

{

    struct  busylink   *p;

p=busy_head->next;

    if(p==NULL)

        printf("无内存占有区！\\n");

    else

    {

        while(p!=NULL)

        {

        printf("名字:%c\首地址:%d\长度:%d\\n",p->name,p->address,p->len);

     p=p->next;

        }

    }

}

//    设计主函数：

int main()

{ 

    start();

    past(5);

    requireMemo('A',8);  requireMemo('B',16); 

    requireMemo('C',); requireMemo('D',124);

    printf("内存占用区为：\\n");

    printlink1();

    printf("内存空闲区为:\\n");

    printlink();

    past(10);

    freeMemo('C');

    printf("内存占用区为：\\n");

    printlink1();

    printf("内存空闲区为:\\n");

    printlink();

    past(15);

    requireMemo('E',50);

    printf("内存占用区为：\\n");

    printlink1();

    printf("内存空闲区为:\\n");

    printlink();

    past(20);

    freeMemo('D' );

    printf("内存占用区为：\\n");

    printlink1();

    printf("内存空闲区为:\\n");

    printlink();

    return 0;

}