memory.c

用单链表实现的模拟linux内存管理的first算法

/*
 * 内存管理实验程序残缺版 1.2.2
 * 把一个数组模拟为内存，然后针对该块内存实现内存的分配和回收算法
 * 作者：Sunner Sun
 * 最后修改时间：2005-3-25 16:53
 */
#include "conio.h"
#include <stdio.h>

#define MEM_SIZE 80
char memory[MEM_SIZE];

/*单项链表的结点用于记录内存的使用情况
    p记录此段占有内存的首地址；
    size记录此段占有内存的大小*/
struct node
{
    void* p;
    int size; /**/
    struct node* next;
};
typedef struct node* Mem_Manage_List;
struct node head_node ={memory,0,NULL};/*声明Mem_Manage_List的头结点的内容*/
Mem_Manage_List head = &head_node;

void* GetBlock(unsigned int size);
int FreeBlock(void* pBlock);
int IsFree(int unit);

/* 在数组memory的分配size大小的内存块，把首地址返回。
   如果分配失败，返回NULL */
void* GetBlock(unsigned int size)
{ /*from找到的空闲内存的首地址，to为其对应的末地址加上1,temp为此空闲内存的大小*/
    long from,to,temp;
    struct node *p,*q;
    p = head;
    while(p != NULL)
    {
        if(p->next != NULL)
            to = (long)p->next->p;
        else
            to = (long)&memory[MEM_SIZE-1]+1;

        from = (long)p->p + p->size;
        temp = to - from;
        if(temp >= (long)size)
        {/*第一块空闲的内存足够用，则按照从前到后的顺序分配出size大小的内存块，
            并按内存段首地址递增的顺序把结点添加到单项链表里*/
            q= (Mem_Manage_List *)malloc(sizeof(struct node));
            q->p = (void*)((long)p->p + p->size);
            q->size = size;
            q->next = p->next;
            p->next = q;
            return q->p;
        }
        p = p->next;
    }
    return NULL;
}

/* 释放首地址为pBlock的内存块。
   成功返回非0值，失败返回0 */
int FreeBlock(void* pBlock)
{ /*用顺序查找方法来释放内存段*/
    struct node *p,*q;
    p = head;
    while(p->next!=NULL)
    {
        if(p->next->p == pBlock)
        {
            q = p->next;
            p->next = q->next;
            free(q);
            return !0;
        }
        p = p->next;
    }
    return 0;
}

/* 判断数组memory中下标为unit的单元是否被占用。
   空闲返回非0，否则返回0 */
int IsFree(int unit)
{
   struct node *p;
   p = head;
   while(p->next != NULL)
   {/*查找从内存开始到最后一个内存块之前的内存是否为空闲*/
        if(p->next->p >&memory[unit])
        {
            if((long)p->p + p->size >(long)&memory[unit])
                return 0;
            else
                return !0;
        }
        p = p->next;
   }
   /*查找指向最后一个内存块及其之后的内存是否为空闲*/
   if((long)p->p + p->size >(long)&memory[unit])
        return 0;
   else
        return !0;
}

/************************************************
 * 下面为测试代码，不需要修改，也不许使用其定义 *
 * 的各种变量、宏、结构等                       *
 ************************************************/

#define MAX_BLOCK_SIZE    10
#define BLOCK_COUNT        80
struct BLOCK
{
    void* p;
    int size;
};

void PrintMemoryUsage(void);
int New(struct BLOCK *pBlocks);
int Delete(struct BLOCK *pBlocks);

int main(void)
{
    struct BLOCK blocks[BLOCK_COUNT] = {0,0};

    int ch = 0;
    int rtn = 1;
    int i;

    do
    {
        switch (ch)
        {
        case 'n':
            rtn = New(blocks);
            break;
        case 'd':
            rtn = Delete(blocks);
            break;
        case '\n':
            continue;
            break;
        }
        if (!rtn)
            printf("\nError!!!!\n");
        PrintMemoryUsage();
        printf("Input \'n\' to new, \'d\' to delete and \'q\' to quit:");

    } while ((ch=getchar()) != 'q');

    /* 删除所有已申请的block */
    for (i=0; i<BLOCK_COUNT; i++)
    {
        if (blocks[i].p != NULL)
        {
            FreeBlock(blocks[i].p);
        }
    }
    
    return 0;
}

/* 打印memory分配情况 */
void PrintMemoryUsage(void)
{
    int i;

    putchar('\n');
    
    for (i=0; i<MEM_SIZE; i++)
    {
        if (i%10 == 0)
            putchar('|');
        else
            putchar(' ');
    }
    
    putchar('\n');

    for (i=0; i<MEM_SIZE; i++)
    {
        if (IsFree(i))
            putchar('-');
        else
            putchar('*');
    }

    putchar('\n');
}

/* 新申请block */
int New(struct BLOCK *pBlocks)
{
    int size = 0;

    while (size < 1 || size > MAX_BLOCK_SIZE)
    {
        printf("Size?[1-%d]", MAX_BLOCK_SIZE);
        scanf("%d", &size);
    }

    while (pBlocks->p != NULL)
        pBlocks++;

    pBlocks->p = GetBlock(size);
    pBlocks->size = size;

    return (pBlocks->p != NULL);
}

/* 删除已经申请的block */
int Delete(struct BLOCK *pBlocks)
{
    int i;

    for (i=0; i<BLOCK_COUNT; i++)
    {
        if (pBlocks[i].p != NULL)
        {
            printf("%d:%d\t", i, pBlocks[i].size);
        }
    }
    printf("\nWhich to delete:");
    scanf("%d", &i);
    if (FreeBlock(pBlocks[i].p))
    {
        pBlocks[i].p = NULL;
        return !0;
    }
    else
        return 0;
}