first aid.txt

操作系统中实现内存分配中要用到的首次适应算法

首次适应算法的模拟。


看资料的一个总结，经验有限，欢迎大家拍砖，图没有拷贝上来：（。
   模拟内存分配和内存释放函数的实现原理，主要目的是以一个简单的方法说明操作系统是如何进行内存分配和内存释放的，其原理参考了早期的UNIX操作系统内核中内存分配和释放函数。
当程序调用Mmalloc申请空间时，Mmalloc首先查找函数系统已经e建立的自由空间链表，如果由足够大小的空间，则返回指向此空间的地址。
链表中每个节点包含两个内容：自由空间大小、自由空间本身的起始地址。链表中自由空间块按其首地址从小到大排序。链表中最后一个节点自由空间大小为0。
操作系统分配连续内存空间的算法有：首次适应、最佳适应、最差适应，这里实现Mmalloc采用首次适应算法。
下面是源代码：
#include <stdio.h>

static char Alloc[1024];                                ⑴

typedef struct  _Node                                 ⑵
{

        char *m_addr;
        unsigned int m_size;

}Node;

Node *mp;                                          ⑶

/*CreateList函数，创建自由链表*/
void CreateList()                                     ⑷
{
        int i;
        mp = (Node*)malloc(sizeof(Node)*10);                ⑸

        for(i=0; i<4; i++)                                  ⑹
        {
                   mp.m_addr=Alloc+i*256;
        mp.m_size = 256;
        }

        mp[4].m_addr = Alloc+1024;                         ⑺
        mp[4].m_size = 0;                                  ⑻

}

/*Mmalloc函数*/

void *Mmalloc(Node *mp, unsigned int size)               ①
{
        char* a;
        register Node *bp;                                  ②

        for(bp=mp; bp->m_size; bp++)
        {
                   if(bp->m_size >= size)                           ③
        {
                           a = bp->m_addr;
                           bp->m_addr += size;

                           if(bp->m_size == size)                       ④
                           {
                                  do
                                  {
                                          bp++;
                                          (bp-1)->m_addr = bp->m_addr;
                                          (bp-1)->m_size = bp->m_size;
                                  } while (bp->m_size);
                         }
                         else
                         {
                                  bp->m_size -= size;                     ⑤
                         }

                        return a;                                    ⑥
                 }
}

        return 0;
}

/*Mfree函数*/

void Mfree(Node *mp,unsigned int size, void* pa)
{

        register Node *bp;
        register int t;
        char* s;

   s = (char*)pa;

        for(bp=mp; bp->m_addr<=(char*)pa && bp->m_size!=0; bp++); i

        if(bp>mp && (bp-1)->m_addr + (bp-1)->m_size == (char*)pa)  ii
        {
                (bp-1)->m_size += size;                             
                if((char*)pa+size = = bp->m_addr)                    iii
                {
                           (bp-1)->m_size += bp->m_size;                    

                          do                                            iv
                          {
                                  bp++;
                                  (bp-1)->m_addr = bp->m_addr;
                                  (bp-1)->m_size = bp->m_size;
                          }        while (bp->m_size);
                   }
        }
        else
        {
                    if((char*)pa+size = = bp->m_addr && bp->m_size)       v
                {
                           bp->m_addr -= size;
                           bp->m_size += size;
                    }
                   else if(size)                                        vi
        do
{
                          t = (int)bp->m_addr;
                          bp->m_addr = s;
                          s = (char*)t;

                          t = bp->m_size;
                          bp->m_size = size;
                          bp++;
        }while(size = t);
        }
}

/*FreeList函数，释放自由链表节点*/
void FreeList() 
{ 
free(mp);
mp = NULL;
}

/*TraverList函数，遍历链表节点*/
void TraverList()
{
Node *pl = NULL;
int i = 0;

if(mp = = NULL)
    return;

pl = mp;
While(pl->m_size)
{
printf("mp[%d].m_addr=%08lx, mp[%d].m_size=%d  ", i,pl->m_addr,i, pl->m_size);
printf(“\r\n”);

pl++;
i++;
}
   
    printf(“\r\n”);
}
1.3.1程序分析
?        全局变量
⑴ 建立一个全局静态的数组，开辟一块内存空间。
⑵ 建立一个结构类型的节点，其包含节点自由空间的起始地址和长度。
⑶ Node类型的指针，指向自由链表的首地址。
?        CreateList函数
⑷ CreateList函数，建立一个自由链表，使mp指向头节点，最后一个节点的自由空间长度为0。
⑸ 使用malloc函数分配了10个节点。
⑹ for循环的目的是使自由链表的每个节点的m_addr指向静态数组Alloc的不同地址，起始地址为Alloc，以256个字节递增，即每个节点（除了第5个节点）的自由空间为256个字节。
⑺ 尾节点的地址指向数组的末端。
⑻ 尾节点m_size等于0，自由链表结束的标志。链表结构如图1.17所示。










图1.17  自由链表示意图
?        Mmalloc函数
① Mmalloc函数，模拟操作系统提供的malloc函数，进行内存空间的分配。参数mp指向自由链表的首节点，size为分配的字节数。 
② 建立Node类型的临时节点，指向自由链表的首节点。
③ 遍历整个自由链表，if语句判断是否找到足够的可分配的内存空间，如果找到，则指向自由空间的地址做相应的改变。
④ if语句判断找到的自由空间是否与所要分配的空间大小一样，如果一样，使用do_while语句，使链表向前移动一个节点。如图1.18所示的情况。






图1.18
⑤ 出现③的情况而未出现④的情况，说明此节点的自由空间减小了，则m_size减去已经分配的字节数。
⑥ 返回分配空间的首地址。
?        Mfree函数
Mfree函数比较复杂，因为释放空间以后，如果其相邻的空间未被分配，则与未被分配
的空间合并，形成一个比较大内存空间，防止造成过多的内存碎片。
i 空循环，找到自由空间的地址大于所需要释放空间的地址，亦即不满足条件：
bp->m_addr <= a;          bp->m_size !=0 ; 
ii判断是否bp-1节点自由空间与释放的空间（起始地址pa）相邻。如图1.19展示了if语句为真的情况,那么与bp-1节点的自由空间合并。







图  1.19
iii 判断bp节点自由空间与释放的空间（起始地址pa）是否相邻，即需要释放的空间不仅与bp-1节点的自由空间相邻，而且与bp节点的自由空间相邻，那么，它们合并为一个节点，组成一个更大的自由空间，do_while结构使链表向前移动一个节点。如图1.20展示了if语句为真的情况。








图1.20
iv 如果释放空间只与bp节点的自由空间相邻，则与其合并。如图1.21展示了此种情况。
vi 如果释放的空间不满足以上条件，即既不与bp节点相邻，也不与bp-1节点相邻，则在自由链表中新增加一个节点，do_while语句使链表向后移动一个节点。







图1.21
?        FreeList函数
FreeList函数用来释放自由链表分配给每个节点的内存空间。
?        TraverList函数
TraverList函数用来遍历链表中的每个节点，输出每个节点自由空间的首地址和其长度。