C语言实现动态分区分配与回收_c语言 动态分区分配与回收

一、实验目的

熟悉动态分区的四个算法，回收的四种情况。掌握动态重定位的思想。

二、实验原理

首次适应算法：空闲分区链以地址递增的次序链接，进行内存分配时，从链首开始顺序查找。

循环首次适应算法：空闲分区链以地址递增的次序链接，进行内存分配时，从上次找到的空闲分区的下一个空闲分区开始查找。

最佳适应算法：每次为作业分配内存时，总是把满足要求的、最小的空闲分区分配给作业。

最坏适应算法：每次为作业分配内存时，总是把满足要求的、最大的空闲分区分配给作业。

动态重定位：单个空闲分区不满足要求时，将所有的空闲分区进行紧凑，拼出较大的空闲分区来满足进程所需的内存空间。

源程序：

definition.h

 

#include<stdio.h>

#include<stdlib.h>

#pragma warning (disable:4996)

//空闲分区链

typedef struct FreeLink

{

    char name;    //区号

    int startAddr;    //起始地址

    int size;     //大小，以K为单位

    struct FreeLink* next;

}FreeBlockLink;

 

//进程块

typedef struct Process

{

    char name;    //进程名称

    int addr;     //分配后进程所在内存的首地址

    int size;     //进程大小

    int flag;     //分配状态

    struct Process* next;

}ProcessLink;

 

int LengthBlock(FreeBlockLink* L)

{

    int length;

    FreeBlockLink* p;

    p = L;

    length = 0;

    while(p->next !=NULL)

    {

       length ++;

       p = p->next ;

    }

    return length;

 

}

 

int LengthProcess(ProcessLink* L)

{

    int length;

    ProcessLink* p;

    p = L;

    length = 0;

    while(p->next !=NULL)

    {

       length ++;

       p = p->next ;

    }

    return length;

 

}

 

void BlockTailInsert(FreeBlockLink* L)    //尾插空闲分区块

{

    char name;

    int size;

    int startAddr;

    FreeBlockLink* link;

    FreeBlockLink* p;

    p = L ;

    link = (FreeBlockLink*)malloc(sizeof(FreeBlockLink));

    printf("请输入内存的空闲分区的区号、大小和起始地址,以空格区分：\n");

    scanf("%c%d%d",&name,&size,&startAddr);

    fflush(stdin);

 

    link->name = name;

    link->size = size;

    link->startAddr = startAddr;

    while(p->next !=NULL)

    {

       p = p->next ;

    }

    link->next = p->next ;

    p->next = link;

   

   

}

void ProcessTailInsert(ProcessLink* L)    //尾插请求分配内存进程

{

    //（初始首地址为0）

    char name;

    int size;

    ProcessLink* link;

    ProcessLink* p;

    p = L ;

    link = (ProcessLink*)malloc(sizeof(ProcessLink));

    printf("请输入请求分配内存的进程的进程名、大小,以空格区分：\n");

    scanf("%c %d",&name,&size);

    fflush(stdin);

    //printf("%c,%d",name,size);

 

    link->name = name;

    link->size = size;

    link->addr = 1000;   //处于未分配状态下按地址排序会放在最后一个

    link->flag = 0;

    while(p->next !=NULL)

       p = p->next;

    link->next = p->next ;

    p->next = link;

    //printf("%c,%d,%d\n",link->name ,link->size ,link->addr );

}

void init(FreeBlockLink* L)            //初始化内存空闲分区

{

    int freeNum;      //空闲分区的个数

    int i;

    /*FreeBlockLink* link;

    link = (FreeBlockLink*)malloc(sizeof(FreeBlockLink));*/

    freeNum = 0;

    printf("请输入初始空闲分区的个数：");

    scanf("%d",&freeNum);

    getchar();

    printf("请输入各个空闲分区的信息：\n");

    for(i= 0;i< freeNum;i++)

    {

       BlockTailInsert(L);

    }

}

void creat(ProcessLink* L)             //创建进程分配内存请求

{

    int processNum;

    int i;

    processNum = 0;

    printf("请输入请求分配内存的进程个数：");

    scanf("%d",&processNum);

    getchar();

    for(i = 0;i < processNum;i++)

    {

       ProcessTailInsert(L);

    }

}

 

void PrintFreeBlock(FreeBlockLink* L)

{

    int i;

    FreeBlockLink* p;

    p = L ;

    i = 0;

    while(p->next!= NULL)

    {

       i++;

       printf("第%d个空闲分区信息：\n",i);

       printf("区号\t大小\t起始地址\n");

       printf("%c\t%dK\t%dK\n",p->next->name,p->next->size ,p->next->startAddr );

       p = p->next ;

    }

    printf("\n");

}

void PrintProcess(ProcessLink* L)

{

    int i;

    ProcessLink* p;

    p = L ;

    i = 0;

    while(p->next!= NULL)

    {

       i++;

       printf("第%d个进程信息：\n",i);

       printf("进程名\t大小\t在内存的起始地址\n");

       printf("%c\t%dK\t%dK\n",p->next->name,p->next->size ,p->next->addr );

       p = p->next ;

    }

    printf("\n");

}

 

sort.h

 

#include<stdio.h>

#include<stdlib.h>

#include"defination.h"

#pragma warning (disable:4996)

void sortForDynamic(ProcessLink* L)

{

    ProcessLink* p;

    int i,j,len;

    char tempName;

    int tempSize,tempAddr;

    p = L;

   

    len = LengthProcess(L);

    //printf("%d\n",len);

    tempName = '@';

    tempSize = 0;

    tempAddr = 0;

    for(i = 0;i< len;i++)

    {

       p = L;

       for(j=0;j<len - i -1;j++)

       {

           if(p->next != NULL)

           {

              p = p->next ;

              if(p->addr >p->next->addr )

              {

                  tempAddr = p->addr ;

                  p->addr = p->next->addr ;

                  p->next->addr = tempAddr;

 

                  tempName = p->name ;

                  p->name = p->next->name ;

                  p->next->name = tempName;

 

                  tempSize = p->size ;

                  p->size = p->next->size ;

                  p->next->size = tempSize;

              }

           }

       }

    }

}

void sortByMaxSize(FreeBlockLink* L)   //按空闲分区大小从大到小排序

{

    FreeBlockLink* p;

    int i,j,len;

    char tempName;

    int tempSize,tempStartAddr;

    p = L;

   

    len = LengthBlock(L);

    //printf("%d\n",len);

    tempName = '@';

    tempSize = 0;

    tempStartAddr = 0;

    for(i = 0;i< len;i++)

    {

       p = L;

       for(j=0;j<len - i -1;j++)

       {

           if(p->next != NULL)

           {

              p = p->next ;

              if(p->size <p->next->size )

              {

                  tempStartAddr = p->startAddr ;

                  p->startAddr = p->next->startAddr ;

                  p->next->startAddr = tempStartAddr;

 

                  tempName = p->name ;

                  p->name = p->next->name ;

                  p->next->name = tempName;

 

                  tempSize = p->size ;

                  p->size = p->next->size ;

                  p->next->size = tempSize;

              }

           }

       }

    }

}

 

void sortByMinSize(FreeBlockLink* L) //按空闲分区大小从小到大排序

{

    FreeBlockLink* p;

    int i,j,len;

    char tempName;

    int tempSize,tempStartAddr;

    p = L;

   

    len = LengthBlock(L);

    //printf("%d\n",len);

    tempName = '@';

    tempSize = 0;

    tempStartAddr = 0;

    for(i = 0;i< len;i++)

    {

       p = L;

       for(j=0;j<len - i -1;j++)

       {

           if(p->next != NULL)

           {

              p = p->next ;

              if(p->size >p->next->size )

              {

                  tempStartAddr = p->startAddr ;

                  p->startAddr = p->next->startAddr ;

                  p->next->startAddr = tempStartAddr;

 

                  tempName = p->name ;

                  p->name = p->next->name ;

                  p->next->name = tempName;

 

                  tempSize = p->size ;

                  p->size = p->next->size ;

                  p->next->size = tempSize;

              }

             

           }

       }

    }

}

void sortByAddr(FreeBlockLink* L)

{

    FreeBlockLink* p;

    int i,j,len;

    char tempName;

    int tempSize,tempStartAddr;

    p = L;

   

    len = LengthBlock(L);

    //printf("%d\n",len);

    tempName = '@';

    tempSize = 0;

    tempStartAddr = 0;

    for(i = 0;i< len;i++)

    {

       p = L;

       for(j=0;j<len - i -1;j++)

       {

           if(p->next != NULL)

           {

              p = p->next ;

              if(p->startAddr >p->next->startAddr )

              {

                  tempStartAddr = p->startAddr ;

                  p->startAddr = p->next->startAddr ;

                  p->next->startAddr = tempStartAddr;

 

                  tempName = p->name ;

                  p->name = p->next->name ;

                  p->next->name = tempName;

 

                  tempSize = p->size ;

                  p->size = p->next->size ;

                  p->next->size = tempSize;

              }

           }

       }

    }

   

}

 

algorithm.h

 

#include"sort.h"

#pragma warning (disable:4996)

void Dynamic(FreeBlockLink* L1,ProcessLink* L2,ProcessLink* m,int size);

//删除链表元素算法

void dellFreeBlock(FreeBlockLink* L1,FreeBlockLink* p)

{

    FreeBlockLink* m;

    m = L1;

    while(m->next != NULL)

    {

       if(m->next == p)

       {

           m->next = p->next ;

           free(p);

           break;

       }

       m= m->next ;

    }

}

void dellProcess(ProcessLink* L2,ProcessLink* q)

{

    ProcessLink* m;

    m = L2;

    while(m->next != NULL)

    {

       if(m->next == q)

       {

           m->next = q->next ;

           free(q);

           break;

       }

       m= m->next ; 

    }

}

//进程分配算法

void allocation(FreeBlockLink* L1,FreeBlockLink* p,ProcessLink* q,int size)

{

    while(p->next != NULL)

    {

       if(p->next->size >= q->next->size )    //分配空闲分区

       {

           if(p->next->size - q->next->size < size)  //小于最小容量，直接将整个空闲分区分出去

           {

              q->next->addr = p->next->startAddr ;

              q->next->size = p->next->size;

              q->next->flag = 1;

              dellFreeBlock(L1,p->next);

              break;

           }

           else

           {

              //改进程在内存的起始地址 和分配状态

              q->next->addr = p->next->startAddr ;

              q->next->flag = 1;

              //改空闲分区

              p->next->startAddr += q->next->size ;

              p->next->size -= q->next->size ;

              //flag = 1;

              break;

           }

       }

       p = p->next;

       //flag++;

    }

    //return flag;

}

//--------------首次适应算法-------------

void FirstFind(FreeBlockLink* L1,ProcessLink* L2,int size)

{

    int i;

    int m; //表示需要分配内存的进程个数

    //int flag;   //标识 进程分配成功与否

    FreeBlockLink* p;

    ProcessLink* q;

   

    sortByAddr(L1);      //按地址递增的顺序排序

    m = LengthProcess(L2);

    //printf("%d\n",m);

    //PrintProcess(L2);

    p = L1;

    q = L2;

    //flag = 0;

    for(i = 0;i<m;i++)       //对每一个进程都进行分配

    {

       if(q->next->flag == 0)

       {

           p = L1;

           allocation(L1,p,q,size);

       }

       if(q->next->flag == 0)

       {

           Dynamic(L1,L2,q->next,size);  //对内存进行动态重定位

       }

       if(q->next->flag == 0)

           printf("进程%c分配内存失败！！",q->next->name);

       q = q->next ;

       //PrintFreeBlock(L1);

    }

}

//-----------循环首次适应算法-----------

void ScanFirstFind(FreeBlockLink* L1,ProcessLink* L2,int size)

{

    int i,m,n;

    FreeBlockLink* p;

    ProcessLink* q;

    p = L1;

    q = L2;

    //flag = 0;       //内存分配成功或者失败标志

    sortByAddr(L1);

    m = LengthProcess(L2);

    //n = LengthBlock(L1);

    for(i = 0;i<m;i++)       //对每一个进程都进行分配

    {

       //flag = 0;

       if(q->next->flag == 0)

       {

           allocation(L1,p,q,size);

       }

       if(q->next->flag == 0)

       {

           p = L1;

           allocation(L1,p,q,size);

       }

       if(q->next->flag == 0)

           Dynamic(L1,L2,q->next,size);

       if(q->next->flag == 0)

           printf("进程%d分配内存失败！！",q->next->name);

       q = q->next ;

    }

}

//----------最佳适应算法-----------

void BestFind(FreeBlockLink* L1,ProcessLink* L2,int size)

{

    int i,m;

    FreeBlockLink* p;

    ProcessLink* q;

    p = L1;

    q = L2;

    sortByMinSize(L1);

    m = LengthProcess(L2);

    for(i= 0;i< m;i++)

    {

       if(q->next->flag == 0)

       {

           p = L1;

           allocation(L1,p,q,size);

       }

       sortByMinSize(L1);

       if(q->next->flag == 0)

           Dynamic(L1,L2,q->next,size);

       if(q->next->flag == 0)

           printf("进程%d分配内存失败！！",q->next->name);

       q = q->next ;

    }

}

//----------最坏适应算法------------

void WorstFind(FreeBlockLink* L1,ProcessLink* L2,int size)

{

   

    int i,m;

    FreeBlockLink* p;

    ProcessLink* q;

    p = L1;

    q = L2;

    sortByMaxSize(L1);

    m = LengthProcess(L2);

    for(i= 0;i< m;i++)

    {

       if(q->next->flag == 0)

       {

           p = L1;

           allocation(L1,p,q,size);

       }

       sortByMaxSize(L1);

       if(q->next->flag == 0)

           Dynamic(L1,L2,q->next,size);

       if(q->next->flag ==0)

           printf("进程%d分配内存失败！！",q->next->name);

       q = q->next ;

    }

}

 

 

//回收算法

void Reco(FreeBlockLink* L1,int addr,int size,char name,int choice)

{

    FreeBlockLink* p;

    FreeBlockLink* q;

    FreeBlockLink* m;

    int min;   //在最佳适应算法中帮助找到回收区域

    p = L1;

    q = L1;

    min = 10000;

    if(choice == 1 || choice == 2)

    {

       while(p->next != NULL)

       {

           p = p->next ;

           if(p->startAddr > addr)

              break;

           q = p;

       }

    }

    else

    {

       sortByAddr(L1);

       while(p->next != NULL)

       {

           p = p->next ;

           if(p->startAddr >addr && p->startAddr <min)

              break;

           q = p;

       }

 

    }

    if(p == L1->next && p->next != NULL) //不可能有上临临界分区的可能性  

    {

        if(addr + size < p->startAddr ) //上不临下不临

       {

           m = (FreeBlockLink*)malloc(sizeof(FreeBlockLink));

           m->name = name;

           m->size = size;

           m->startAddr = addr;

           //头插空闲分区链

           m->next = p;

           L1->next = m;

       }

       else

           //(addr+ size == p->startAddr ) //下临空闲分区

       {

           p->size += size;

           p->startAddr = addr;

       }

 

    }

    else if(p->next == NULL) 

    {//两种情况：1.找到了p，在空闲分区链的最后一个。2.没有找到p,要回收的进程的首地址要大于p->startAddr;

       if(p->startAddr > addr)

       {

           if(q->startAddr + q->size == addr && addr + size < p->startAddr ) //上临临界区

           {

              q->size += size;

           }

          else if((q->startAddr + q->size < addr && addr + size < p->startAddr) )    //上不临下不临

           {

              m = (FreeBlockLink*)malloc(sizeof(FreeBlockLink));

              m->name = name;

              m->size = size;

              m->startAddr = addr;

              //中间插入一个空闲分区

              m->next = p;

              q->next = m;

           }

          else if(q->startAddr + q->size == addr && addr + size == p->startAddr )    //上临下临

           {

              q->size = q->size + size + p->size ;

              q->next = p->next;

              free(p);

           }

           else       //下临

           {//q->startAddr + q->size < addr && addr+ size == p->startAddr

              p->startAddr = addr;

              p->size += size;

           }

       }

       else       //情况2，不可能下临临界分区了

       {

           if(p->startAddr + p->size == addr) //上临临界分区

           {

              p->size += size;

           }

           else if(p->startAddr + p->size < addr) //上不临下不临

           {

              m = (FreeBlockLink*)malloc(sizeof(FreeBlockLink));

              m->name = name;

              m->size = size;

              m->startAddr = addr;

              //尾部插入一个空闲分区

              m->next = p->next ;

              p->next = m;

           }

       }

    }

    else

    {

       if(q->startAddr + q->size == addr && addr + size < p->startAddr )    //上临空闲分区 万一是最后一块空间？

       {

           q->size += size;

       }

       else if(addr+size == p->startAddr && q->startAddr + q->size < addr)    //下临空闲分区

       {

           p->startAddr = addr;

           p->size += size;

       }

       else if(q->startAddr + q->size == addr && addr + size == p->startAddr )       //上下都临空闲分区

       {

           q->size = size + q->size + p->size ;

           q->next = p->next ;

           free(p);

       }

       else //上不临下不临

       {

           m = (FreeBlockLink*)malloc(sizeof(FreeBlockLink));

           m->name = name;

           m->size = size;

           m->startAddr = addr;

           m->next = p;

           q->next = m;

       }

    }

 

}

void Recov(FreeBlockLink* L1,ProcessLink* L2,char m,int choice)

{

    ProcessLink* q;

    int addr;

    int size;

   

    addr = -1;

    size = 0;

 

    q = L2;

    while(q->next !=NULL)

    {

       if(q->next->name == m)

       {

           addr = q->next->addr ;

           size = q->next->size ;

           break;

       }

       q = q->next ;

    }

    if(q->next == NULL)

    {

       printf("内存中没有此进程！\n");

       //printf("进程已回收完\n");

       exit(0);

    }  

    else

    {

       Reco(L1,addr,size,m,choice);

       dellProcess(L2,q->next);

    }

}

void Recovery(FreeBlockLink* L1,ProcessLink* L2,int choice)

{

    int flag;

    char name;

    flag = 1;

   

    //while(flag)

    //{

       printf("请输入要回收的进程名：\n");

       scanf("%c",&name);

       getchar();

       Recov(L1,L2,name,choice);

       if(choice == 1 || choice == 2)

           sortByAddr(L1);

       else if(choice == 3)

           sortByMinSize(L1);

       else

           sortByMaxSize(L1);

       //printf("回收后空闲分区情况如下：\n");

       //PrintFreeBlock(L1);

       //printf("是否要继续回收？Yes,输入1，No,输入0\n");

       //scanf("%d",&flag);

       //getchar();

    //}

}

 

//引入动态重定位算法

void Dynamic(FreeBlockLink* L1,ProcessLink* L2,ProcessLink* m,int size)

{

    //紧凑空闲分区，将已分配的内存放在低址区，将空闲区放在高地址区域

    //如果紧凑后的空闲分区的大小大于要申请的大小，分配，并修改进程状态、各进程的起始地址

    //不满足大小，分配失败

    FreeBlockLink* p;

    FreeBlockLink* n; //指向p的前一个

    ProcessLink* q;

    ProcessLink* mm; //指向q的前一个

    int sum;

    sum =0;

    p = L1;

   

    n = p;

    sortForDynamic(L2);   //将在内存中的进程（已分配，或等待分配）按地址排序，便于后续重定位

    q = L2;

    mm = q;

    while(p->next != NULL)

    {

       sum += p->next->size ;

       p = p->next ;

    }

    p = L1;

    if(sum >= m->size )      //空闲区>=申请大小

    {

       printf("耶！重定位后可以分配了\n");

       m->flag = 1;

       //printf("%d\t%d\n",p->next->startAddr,q->next->addr );

       if(p->next->startAddr > q->next->addr )

       {

           q = q->next;

           while(q->next!=NULL )

           {

              mm = q;

              q->next->addr = mm->addr + mm->size ;

              //printf("%d\n",q->next->addr);

              q = q->next ;

           }

           //删除第一个结点后面的所有结点。也就是合并为一个空闲区，并改起始地址和大小

           p = p->next;

           n = p;

           while(p->next !=NULL)

           {

             

              p = p->next;

              n->next = p->next ;

              free(p);

              p = n;

           }

           n->startAddr = q->addr + q->size ;

           printf("%d\t%d\n",sum,m->size );

           n->size = sum - m->size ;

       }

       else //

       {

           q = q->next ;

           q->addr = p->next->startAddr ;

           mm = q;

           while(q->next!=NULL )

           {

              mm = q;

              q->next->addr = mm->addr + mm->size ;

              q = q->next ;

           }

           //删除第一个结点后面的所有结点。也就是合并为一个空闲区，并改起始地址和大小

           p = p->next;

           n = p;

           while(p->next !=NULL)

           {

             

              p = p->next;

              n->next = p->next ;

              free(p);

              p = n;

           }

           n->startAddr = q->addr + q->size ;

           printf("lala%d\t%d\n",sum,m->size );

           n->size = sum - m->size ;

       }

    }

    //printf("%d\n",m->flag);

}

 

dynamic_partition.c

 

#include<stdio.h>

#include<stdlib.h>

#include"algorithm.h"

#pragma warning (disable:4996)

void Choice(int choice,FreeBlockLink* L1,ProcessLink* L2,int size)

{

    switch(choice)

    {

       case 1: FirstFind(L1,L2,size);break;

       case 2: ScanFirstFind(L1,L2,size);break;

       case 3: BestFind(L1,L2,size); break;

       case 4: WorstFind(L1,L2,size); break;

       default: exit(0);

    }

}

int main()

{

    int choice;       //选择算法

    int size;     //空闲分区最小大小

    int flag;     //选择分配还是回收

    int end;      //结束标志

    FreeBlockLink* head1;

    ProcessLink* head2;

    head1 =(FreeBlockLink*)malloc(sizeof(FreeBlockLink));

    head2 =(ProcessLink*)malloc(sizeof(ProcessLink));

    head1->next = NULL;

    head2->next = NULL;

    choice = 0;

    size = 0;

    flag = 1;  //初始化为分配

    end = 0;   //初始化为未结束

    printf("请输入最小分区的大小：\n");

    scanf("%d",&size);

    getchar();

    printf("请录入内存的初始分配情况\n");

    init(head1);

    /*printf("开始内存分配与回收情况：\n");

    PrintFreeBlock(head1);*/

 

    printf("请选择分区分配算法：1.首次适应算法 2.循环首次适应算法 3.最佳适应算法 4. 最坏适应算法\n");

    scanf("%d",&choice);

    getchar();

    while(!end)

    {

       if(flag== 1)

       {

           printf("请录入进程的分配请求：\n");

           creat(head2);

           //PrintProcess(head2);

           Choice(choice,head1,head2,size);

           //printf("此时的内存分配与回收情况：\n");

           //PrintFreeBlock(head1);

           //PrintProcess(head2);

       }

       else

           Recovery(head1,head2,choice);

 

       printf("此时的内存分配与回收情况：\n");

       PrintFreeBlock(head1);

       //PrintProcess(head2);

       printf("要结束吗？1.结束。0.继续");

       scanf("%d",&end);

       getchar();

       if(!end)

       {

           printf("继续分配还是回收？1.继续分配。 2.回收");

           scanf("%d",&flag);

           getchar();

       }

      

      

    }

    return 0;

}