操作系统内存管理
PS：楼主终于把内存管理给憋出来了，上个周末两天都在想这个，这两天上班的时候也在想这个(向师父忏悔3分钟...)，接下来的几天我要小放松一下，好久没看电影了的说。本文包括我设计的内存管理模型、为什么这样设计、数据结构和主要算法、少量代码。
我设计的内存管理分3层：
最底层的是对内存页的申请、释放(内核、用户程序都用它申请页)；
再上一层是对内核逻辑空间的申请、释放(只在内核代码中使用)；
顶层是vmalloc函数，跟malloc函数一样的功能(只在内核代码中使用，用户程序中的malloc应该在库中实现)。
内存页管理
x86系统的分页管理是这样的(页大小为4KB的情形，其他大小的情况不了解)：
1. 页的映射分了两级；
2. CR3寄存器指向的页目录表，4KB大小，有1024个页目录项，
每个页目录项指向一张页表(也可以是一个无效的项，不需要1024个项都进行地址映射，否则就太费内存了)；
3. 页表也是4KB大小，有1024个页表项，页表项指向的是一张物理内存页(也可以是无效的)；
4. 页目录项、页表项中记录的都是物理地址。
从上面可以计算得出一张页目录表可映射1024*1024*4KB = 4GB的内存；
而这些页表也占用了一些内存，是4KB*1025，差不多是4MB的内存；
页式管理有效的避免了外部碎片的产生，但是也是有一定开销的，但这个1/1000的开销我们是完全可以接受的。
(x86的页式管理更详细的介绍在《Linux内核完全注释2.01》中有)
考虑到我们的操作系统需要保留16位下的中断、BIOS代码，以保持良好的兼容性(其实是我们目前对付不了那些硬件)，有几片内存我们是不能动的：
A0000 ~ BFFFF 显示缓冲区
F0000 ~ FFFFF BIOS代码
总之这最低的x86在实模式下也能访问的1M内存，我们要谨慎处理(内核代码还是要装在这里的)；
另外，x86的一些硬件只能在低24位的地址空间中执行DMA，而且硬件只认物理地址，分页也忽悠不了它，
于是低24位，也就是16M的内存，在页管理中我们将它们的逻辑地址都映射为真实的物理地址，
并且内核逻辑空间管理和vmalloc都不使用这16M的内存。
在linux0.01中所有进程共用一张页目录表，每个进程占用16个页目录项，也就是最多能够享用64M的内存，最多有64个进程。
要突破单个进程的内存限制，以及进程数的限制，只需要每个进程独占一个页目录表就可以了，
在这个页目录表中一部分供用户程序使用，一部分是内核使用(中断、系统调用的时候要执行的内核代码必须在任何页目录表中都能访问到)，
我将内核使用的地址空间规定为0 ~ 512M，用户程序使用余下的 512M ~ 4G的地址空间，在启动一个新进程的时候内核空间只需要复制页目录项就可以了，
多个页目录表并不会产生太大的内存浪费。
为了初始化内核空间的页映射，我们需要一片不小的内存来存页表，另加上一些内存动态管理需要的数据结构，
我将16M到20M之间的4M内存用做了这个用途(之后会对这4M内存进行详细的划分)。
页的申请我参考了linux0.01的方式，由于fork复制进程的时候首先是重用父进程的页并设置为只读(之后子进程如果写内存会进行写时复制)，也就是一个内存页是可以多次被引用到，于是linux0.01用一个short数组来记录每一页被引用的次数，如果为0则是未被使用的页，可以被申请。
在申请页的时候会遍历这个数组，一直找到引用次数为0的页。我对这个遍历过程进行了改进：我的short数组有(4G-20M)/4K略小于1M的长度，占用小于2M的空间，然后我还用一个4KB的int数组pg_dir来记录已使用页的数量，例如：20M到24M的1024个页中已使用了100个页，那么pg_dir就为100，于是内核可以利用pg_dir中的数据来跳过一些全满的页(模仿了页映射的机制)。
页管理部分就是这样的，一些宏、全局变量的定义如下：
#define PAGE_SHIFT 12
#define PAGE_SIZE (1 << PAGE_SHIFT)
#define M *(1024*1024)
#define MEM_DMA_END (16 M)
#define MEM_KHEAP_START (20 M)
#define MEM_KHEAP_END (512 M)
typedef unsigned int uint;
typedef unsigned short ushort;
static uint* pg_dir;
static ushort* pages;
这一层提供两个函数：
extern void get_free_pages(int count, uint* holder);// 申请count个页，将它们的物理地址存放到holder数组中
extern void free_pages(int count, uint* holder);//释放holder数组中的页，count是数组长度
16M~20M中为这个部分分配了1张页目录表4KB + (512M/4K*4B=512KB的页表) + pg_dir数组4KB + (pages数组(4G-20M)/4K*2B=2038KB) = 2558KB
内核逻辑空间管理
这里就是20M~512M的逻辑空间的管理，其实针对的就是这片内存的页表中的页表项的管理，内核中要用到某块内存，就得把那块内存的页都放到这片空间的页表中，
而哪里有空闲的表项可以装这些页就是这一层负责的，由于管理的粒度比较大(最小单位为页)，一般调用到这层的函数的可以认为是高级别的内存申请行为，
调用的次数不多，因此我认为可以含糊点，用离散内存分配的方式来管理(http://wenku.baidu.com/view/24e2b62a647d27284b735169.html 之后的vmalloc也用的是这里边的算法)，
使用(首次适应算法、最佳适应算法 或 最差适应算法来进行搜索匹配的块，还没确定用哪个)，相应的数据结构和函数为：
typedef struct _KPage
{
uint len:24; // 这个内存块包含的页个数
uint in_use:8; // 正在使用?
struct _KPage* prev;
}KPage;
static KPage* pages;// 指向第一个KPage
extern void* kalloc_pages(int count); // 申请count个页，返回逻辑地址
extern void kfree_pages(void* addr); // 释放之前申请的页，addr是逻辑地址
每一页对应一个KPage结构，KPage结构其实是一个双向链表从pages可依次访问到所有的块。
初始化的时候将第一个KPage设置为{len = (512M-20M)/4K; in_use= false; prev=NULL;};
pages数组在16M~20M的4M空间中又需要占用(512M-20M)/4K*8B = 984KB的内存
另外，解开了一个之前一直想不通的问题：操作系统启动段页式后，内核占一块内存我这里是0~512M，用户程序占另一块内存512M~4G，
那么内核怎么编辑映射在用户程序空间中的内存页呢？现在我想到3个方案：
1. 用fs这样的用户程序使用的段寄存器去访问(不方便)
2. 将内核段长设置为4G(太暴力)
3. 将用户空间的页临时映射到内核空间中(不错哦)
于是在这一层中我又加了两个函数：
extern void* map_page(void* physical_addr);// 将一个物理地址为physical_addr的页临时映射到内核空间，返回映射后的逻辑地址
extern void unmap_page(void* logical_addr);// 取消逻辑地址为logical_addr的页的映射
vmalloc
之前看linux0.01的源码，觉得linus太牛X了，linux0.01中居然没有malloc这样的函数。其实也不是完全没有，它有两个地方是有点动态分配内存的意思的：一个是内存页的管理；一个是IO缓冲块的管理。作为一个平凡的程序员，在写代码的时候没有一个类似于malloc的函数，而只能使用局部变量和全局变量是多么痛苦的一件事啊！因此，我还是决定在我们的内核中需要提供一个malloc这样的函数：
extern void* vmalloc(uint size);
extern void vfree(void* addr);
这里使用的算法是Mckusick-Karels分配算法：
它会管理一片连续的页，然后按照需要将其中的页进行拆分，每个页拆分为等大的2的幂次大小的块，例如页为4KB，将一个页拆分为1024个4B的块；
有个指针数组管理着这些块，每个指针存储着空闲的等大的块，如：4B的块、8B、16B、……，
因此根据需要的内存大小来找空闲块会很快。
由于手痒，我就把vmalloc和vfree敲好了：
#include "memory.h"
#define MIN_SHIFT 2
#define MIN_BUF_SIZE (1 << MIN_SHIFT)
#define POOL_PAGES 999
typedef struct _Buffer
{
struct _Buffer* next_free;
}Buffer;
typedef union _Entry
{
union _Entry* next_free;
int buffer_shift;
}Entry;
typedef struct _Pool
{
union
{
struct
{
struct _Pool* next;
Buffer* free_buffers;
Entry* free_entrys; // 相当于文档中的 freepages
Entry entrys; // 相当于文档中的 kmemsizes[], 不过这里边存的是shift不是size
};
char stub;
};
char buffers;
}Pool;
Pool* pools;
#include <stdio.h>
#include <stdlib.h>
#define LOOP_BEGIN(pool) \
if (!pools)\
;\
else\
{\
Pool* end = pools;\
pool = pools;\
do\
{
#define LOOP_END(loop) \
pools = pool = pool->next;\
} while(pool != end);\
}\
pool = new_pool();\
if (!pool)\
return NULL;
static void init_pool(Pool* pool)
{
int i;
Entry* entry;
for (i = 0; i < (PAGE_SHIFT - MIN_SHIFT); ++i)
pool->free_buffers = NULL;
pool->free_entrys = pool->entrys;
entry = pool->entrys + (POOL_PAGES - 1);
entry->next_free = NULL;
for (i = POOL_PAGES - 1; i > 0; --i, --entry)
(entry - 1)->next_free = entry;
}
static Pool* new_pool()
{
Pool* pool = (Pool*)kalloc_pages(POOL_PAGES + 1);
if (!pool)
printf("没内存了.");
else
{
init_pool(pool);
if (!pools)
pool->next = pool;
else
{
pool->next = pools->next;
pools->next = pool;
}
pools = pool; // 为了速度, 优先使用先添加的pool
}
return pool;
}
static int index_of_buffer(Pool* pool, Buffer* buf)
{
return (((char*)buf) - ((char*)pool->buffers)) >> PAGE_SHIFT;
}
static int index_of_entry(Pool* pool, Entry* entry)
{
return entry - pool->entrys;
}
static void split_page(Pool* pool, Entry* free_entry, int shift)
{
int i;
int size = 1 << shift;
int count = PAGE_SIZE >> shift;
char *buffer;
free_entry->buffer_shift = shift;
buffer = &(pool->buffers);
((Buffer*)buffer)->next_free = NULL;
for (i = count - 1; i > 0; --i, buffer -= size)
((Buffer*)(buffer - size))->next_free = (Buffer*)buffer;
pool->free_buffers = (Buffer*)buffer;
}
static void* mk_malloc(int shift)
{
int index = shift - MIN_SHIFT;
Pool* pool;
LOOP_BEGIN(pool)
Buffer* buf = pool->free_buffers;
if (buf)
{
pool->free_buffers = buf->next_free;
return buf;
}
else if (pool->free_entrys)
{
Entry* entry = pool->free_entrys;
pool->free_entrys = entry->next_free;
split_page(pool, entry, shift);
return mk_malloc(shift);
}
LOOP_END(pool)
return mk_malloc(shift);
}
void* vmalloc(uint size)
{
int shift;
if (size > PAGE_SIZE) // 需要多页
{
int pages = (size + PAGE_SIZE - 1) >> PAGE_SHIFT;
return kalloc_pages(pages);
}
else if (size > (PAGE_SIZE >> 1)) // 只要一页
{
Pool* pool;
LOOP_BEGIN(pool)
Entry* entry = pool->free_entrys;
if (entry)
{
pool->free_entrys = entry->next_free;
entry->buffer_shift = PAGE_SHIFT;
return pool->buffers;
}
LOOP_END(pool)
return vmalloc(size);
}
else if (size < MIN_BUF_SIZE)
size = MIN_BUF_SIZE;
// 半页以下
shift = MIN_SHIFT;
while ((1U << shift) < size)
shift++;
return mk_malloc(shift);
}
void vfree(void* addr)
{
Pool* pool;
if (!pools)
;
else
{
pool = pools;
do
{
int index = index_of_buffer(pool, (Buffer*)addr);
if (index >= 0 && index < POOL_PAGES)
{
Entry* entry = &pool->entrys;
if (entry->buffer_shift == PAGE_SHIFT) // 是整页的, 归还到 free_entrys 中
{
entry->next_free = pool->free_entrys;
pool->free_entrys = entry;
}
else // 被划分了的, 归还到 free_buffers 中
{
int index = entry->buffer_shift - MIN_SHIFT;
((Buffer*)addr)->next_free = pool->free_buffers;
pool->free_buffers = ((Buffer*)addr);
}
return;
}
pool = pool->next;
} while(pool != pools);
}
// 是底层申请的多个页的
kfree_pages(addr);
}
void func()
{
void *p1, *p4, *p8;
p1 = vmalloc(1);
p4 = vmalloc(4);
p8 = vmalloc(8);
vfree(p1);
vfree(p4);
vfree(p8);
printf("%x\n%x\n%x\n", p1, p4, p8);
}
但是这个算法也有弱点：
一个页只能拆分一次，所以如果某次突发的大量申请4B的块，然后全部释放了，这时候虽然有大量的空闲空间，但是你连一个8B的块都申请不到；
因为块大小是2的幂，因此对于那些没有对齐到2的幂的内存大小的申请会达到最高50%的空间浪费，如申请1025B的空间，我们不得不给它一个2048B的块。
当然以上两点能避免则避免，不能避免还可以申请大块内存自己去管理。
这一层不需要占用16M~20M的内存，因此，16M~20M的内存被使用了2558KB+984KB=3542KB<4096KB,4M是足够的。
也可以总结出我们的内存管理的代价是20M，系统内存超过20M的都基本可以运行，耗费的内存不多，而内核的堆空间(可用于以后装载DLL)可达到512M，应用程序的最大使用内存可以达到3.5G(不知道我还有没有没考虑到的情况)。
页:
[1]