内存管理算法实现

作者: 望月从良 | 来源:发表于2016-11-03 22:14 被阅读563次

    本节代码的调试和实现过程可参看视频:
    Linux kernel Hacker, 从零构建自己的内核

    在上一节,我们得知可用内存的大小后,我们就可以开发一个简单的管理算法去管理和分配可用用内存。

    首先创建一个头文件mem_util.h,用来定义内存管理模块相关的数值,变量和接口:

    #define  MEMMAN_FREES  4096
    
    struct FREEINFO {
        unsigned int addr, size;
    };
    
    struct MEMMAN {
        int frees, maxfrees, lostsize, losts;
        struct FREEINFO free[MEMMAN_FREES];
    };
    
    void memman_init(struct MEMMAN *man);
    
    unsigned int memman_total(struct MEMMAN *man);
    
    unsigned int memman_alloc(struct MEMMAN *man, unsigned int size);
    
    int memman_free(struct MEMMAN *man, unsigned int addr, unsigned int size);
    
    

    FREEINFO 结构用来表示可用内存的起始地址和大小,MEMMAN 表示内存管理器,其中的frees 表示当前可用内存对应的FREEINO结构体有多少个,maxfrees 表示我们的内存管理器最多可以容纳多少个可用内存片,一个可用内存片就是一个FREEINFO结构体。当有内存释放时,有些释放后的内存块无法重现加入内存管理器,这些内存块就得丢掉,那么lostsize 就用来记录,内存管理器总共放弃了多少内存碎片,losts记录的是碎片的数量。

    memman_init 用来初始化内存管理区结构体,memman_total用来计算一个内存管理区存储着多少可用的内存,memman_alloc 用来从指定的内存管理器对象中获取可用内存,memman_free 则用于释放不再需要的内存片。

    我们再看看相关实现(mem_util.c):

    #include "mem_util.h"
    
    void memman_init(struct MEMMAN *man) {
        man->frees = 0;
        man->maxfrees = 0;
        man->lostsize = 0;
        man->losts = 0;
    }
    
    unsigned int memman_total(struct MEMMAN *man) {
        unsigned int i, t = 0;
        for (i = 0; i < man->frees; i++) {
            t += man->free[i].size;
        }
    
        return t;
    }
    
    unsigned int memman_alloc(struct MEMMAN *man, unsigned int size) {
        unsigned int i, a;
        for (i = 0; i < man->frees; i++) {
            if (man->free[i].size >= size) {
                a = man->free[i].addr;
                man->free[i].size -= size;
                if (man->free[i].size == 0) {
                    man->frees--;
                }
    
                return a;
            }
        }
    
        return 0;
    }
    
    int memman_free(struct MEMMAN *man, unsigned int addr, unsigned int size) {
        int i, j;
        for (i = 0; i < man->frees; i++) {
            if (man->free[i].addr > addr) {
                break;
            }
        }
    
        if (i > 0) {
            if (man->free[i-1].addr + man->free[i-1].size == addr) {
               man->free[i-1].size += size;
               if (i < man->frees) {
                   if (addr + size == man->free[i].addr) {
                       man->free[i-1].size += man->free[i].size;
                       man->frees--;
                   }
               }
         
               return 0;
            }
        }
    
        if (i < man->frees) {
            if (addr + size == man->free[i].addr) {
               man->free[i].addr = addr;
               man->free[i].size += size;
               return 0;
            }
        }
    
        if (man->frees < MEMMAN_FREES) {
            for (j = man->frees; j > i; j--) {
                man->free[j] = man->free[j-1];
            }
    
            man->frees++;
            if (man->maxfrees < man->frees) {
                man->maxfrees = man->frees;
            }
    
            man->free[i].addr = addr;
            man->free[i].size = size;
            return 0;
        }
    
        man->losts++;
        man->lostsize += size;
        return -1;
    }
    
    

    头三个函数逻辑比较简单,复杂的是内存释放时的处理逻辑。当有内存释放的时候,我们需要把释放内存的起始地址和大小作为参数传入。假定我们要释放的内存片起始地址是 0x200, 大小是0x100, 如果内存管理对象中存在着一片可用内存,起始地址是0x100, 长度为0x100, 那么当前释放的内存片就可以跟原有可用内存合并,合并后的内存块就是起始地址为0x100, 长度为0x200的一片内存块。

    如果内存管理对象不但含有起始地址为0x100, 长度为0x100的内存片,而且还含有起始地址为0x300, 长度为0x100的内存片,这样的话,三块内存片就可以合并成一块内存,也就是起始地址为0x100, 长度为0x300的一个大块内存片。

    这就是代码if( i > 0) {....} 这个模块的逻辑。

    如果不存在上面的情况,比如当前内存管理模块存在的内存块是其实地址为0x100, 长度为0x50, 另一块内存块起始地址是0x350, 长度为0x100:
    FREEINFO{ addr : 0x100; size : 0x50;};
    FREEINFO{addr: 0x350; size: 0x100};

    这样的话,我们就构建一个对应于要释放内存的FREEINFO对象,然后把这个对象插入到上面两个对象之间:
    FREEINFO{ addr : 0x100; size : 0x50;};

    FREEINFO{addr: 0x200; size: 0x100};

    FREEINFO{addr: 0x350; size: 0x100};

    这就是对应于if (i < man->frees){...} 这个分支的主要逻辑。

    如果当前所有可用内存的起始地址都大于要释放的内存块,则将释放的内存块插到最前面,例如当前可用内存块为:

    FREEINOF {addr: 0x300; size: 0x100;}
    FREEINFO {addr: 0x450; size: 0x100;}

    那么释放起始地址为0x200的内存块后,情况如下:

    FREEINFO{addr: 0x200; size: 0x100;}
    FREEINOF {addr: 0x300; size: 0x100;}
    FREEINFO {addr: 0x450; size: 0x100;}

    这就是 if (man->frees < MEMMAN_FREES) {...} 的实现逻辑。

    如果以上情况都不满足的话,那么当前回收的内存块则直接丢弃。

    一般而言,操作系统的内存算法不可能如此简单,内存分配算法是系统内核最为复杂的模块之一,我们当前先从简单入手,后面在慢慢引入分页机制,实现更复杂的内存管理算法。

    由于当前内存管理模块与原来C语言实现的模块是分开的,因此它们需要单独编译,然后再把两个编译好的 .o 文件合并成一个模块,编译过程如下:

    1: 先使用命令编译mem_util.c
    gcc -m32 -fno-asynchronous-unwind-tables -s -c -o mem_util.o mem_util.c

    2: 再使用命令编译原来的C语言模块:
    gcc -m32 -fno-asynchronous-unwind-tables -s -c -o write_vga_desktop.o write_vga_desktop.c

    3:把两个编译好的模块链接成一个模块:
    ld -m elf_i386 -r write_vga_desktop.o mem_util.o -o ckernel.o

    4:把ckernel.o 反汇编,然后再添加到内核的汇编模块中一起编译:
    ./objconv -fnasm ckernel.o ckernel.asm

    把上面所以步骤完成后,执行效果如下:


    这里写图片描述

    从显示出的信息看,虚拟机总内存是1G, 3FE MB 等于 1022M, 也就是说可用内存为1022M.

    有了内存管理机制后,我们后面可以在此基础上,实现图层叠加管理,也就是窗口相互叠加时,互不影响,要实现这种功能,就需要为每个窗口分配相应的内存以便在叠加时能够互不影响。

    相关文章

      网友评论

        本文标题:内存管理算法实现

        本文链接:https://www.haomeiwen.com/subject/fasiuttx.html