嵌入式操作系统内存管理

UCOS上使用的内存管理机制

基本原理

首先将一块大的内存堆分为若干个分区，每个分区又分割成若干个内存块，这些内存块的大小是相同的；不同内存分区中内存块的大小是不同的；利用这种机制，使得内存申请和释放的时间固定下来。
应用在申请内存时可以在不同的分区得到不同大小的内存块，特定的内存块在释放时，必须重新归还到它所属的内存分区；采用上面的算法，可以解决内存碎片的问题。

数据结构的实现

内存分区采用OS_MEM结构体进行表述：

typedef struct os_men{
  void *OSMemAddr;            //内存分区的其实地址
  void   *OSMemFreeList;                //内存分区中空闲内存块的起始地址
  INT32U  OSMemBlkSize;                 //内存块的大小
  INT32U  OSMemNBlks;                   //内存块的个数
  INT32U  OSMemNFree;                   //空闲内存块的个数
  INT8U   OSMemName[OS_MEM_NAME_SIZE];  //内存块的名称
}OS_MEM;

具体函数实现

内存管理器初始化

OS_MemInit()函数初始化多个内存分区管理结构体（OS_MEM）；

初始化内存分区块中的内存控制块
OSMemCreate函数将内存分区中的内存块使用单向链表连接起来；
申请内存块

OSMemGet()函数从指定的内存分区中获取内存块

释放内存块
OSMemPut()函数用于将指定内存块释放到所属的内存分区中。

优缺点
需要应用程序认为的去判断所需要的内存大小对应的内存块，进而寻找相应的内存分区。并没有从根本上解决内存碎片的问题，或者说，使用了较为低级内存分区的策略解决了内存碎片的问题。导致用户需要提前规划内存分区的类型。

典型值的内存管理机制

基本原理
首先获得一块较大的内存，然后设计了若干个嵌入式应用开发过程中可能用到的内存大小的典型值。

当应用需要申请内存时，根据申请内存的大小，计算出比申请内存大且最小的典型值，用这个典型值的大小作为实际要从内存堆中割取的内存块大小；将此内存块加入到内存使用队列中去。
当应用使用完内存以后，将使用完成的内存块加入到其对应典型值的空闲队列中，等待下一次申请时，若相应的典型值队列有未被使用的内存块，先从该典型值队列中获取，如果该典型值队列中没有相应的内存块，则从大块的内存堆中割取。
为了对这些内存块节点进行统一管理，设了内存块管理结构体OS_MEM_HEAP_MAN，并由内存初始化时进行初始化，在内存申请、释放时进行维护。

优缺点
应用程序不在需要人为的去判断所需要的内存大小的内存块，内存分配时做了相应的典型值匹配。同样并没有从根本上解决内存碎片的问题。

FreeRTOS操作系统内存管理

FreeRTOS操作系统将内核与内存管理分开来实现，内核仅仅规定了必要的内存管理函数原型，而不用关心内存管理函数如何实现，这样做的优点是可以增加系统的灵活性。在不同的应用场合可以使用不同的内存分配实现，选择对于自己更加有利的内存管理策略。
FreeRTOS提供了5中内存管理实现，可以适用于多数的场合。且提供的内存管理都是从内存堆栈中分配内存的。默认情况下，内核创建任务、队列、信号量等都是借助于内存管理函数从内存堆中分配内存。但是最新的FREERTOS同样也提供静态分配方式，也就是不使用任何内存堆。
对于heap_1.c heap_2.c heap_4.c这三种内存管理策略，内存堆实际上是一个很大的数组，定义为：static uint8_t ucHeap[configTOTAL_HEAP_SIZE];
对于heap_3.c，这种策略只是简单的包装了标准库中的malloc和free函数，包装后的函数具有线程保护。因此，内存堆需要通过编译器或者启动文件设置堆空间。
heap_5.c允许程序设置多个非连续的内存堆，比如需要快速访问的内存堆设置在片内RAM，稍微访问慢点的内存堆设置在外部RAM。每个内存堆的起始地址和大小由应用程序设计。

heap_1.c策略

该策略是最简单的内存分配策略，整个内存堆设置为一个数组，内存一旦分配以后就不允许再次释放。这是一种较为简洁与安全的内存分配策略，因为在特定的使用环境下，嵌入式软件有时并不需要将内存返回，所申请的内存以及信号量等会一直使用下去。

heap_2.c策略

这种内存分配策略较第一种来说会复杂一些，使用一个最佳匹配算法，允许释放之前已经分配的内存块，但是它不会把相邻的空闲块合并成一个更大的块。（即会产生内存碎片）。
该策略用于重复的分配和删除具有相同堆栈空间的任务、队列、信号量等等，并且不考虑内存碎片的应用程序，不适用于分配和释放随机字节堆栈空间的应用程序。
与第一种内存管理策略一样，内存堆栈仍然是一个大的数组。

内存申请

与第一种内存管理策略不同，第二种内存管理策略使用一个链表结构来跟踪记录空闲内存块，将空闲块组成一个链表。结构体定义为：

typedef struct A_BLOCK_LINK
{
    struct A_BLOCK_LINK *pxNextFreeBlock;   /*指向列表中下一个空闲块*/
    size_t xBlockSize;                      /*当前空闲块的大小，包括链表结构大小*/
} BlockLink_t;

该策略的优缺点

特点：

空闲块是按照大小进行排列的
相邻的空闲块不会组合为一个大块

优点：

速度足够快，实现起来较为简单
可以动态的释放内存

缺点：

释放内存时不会将相邻的内存块合并，所以可能会造成内存碎片。对应用场景要求苛刻
每次创建的任务、信号量、队列必须等同
如果申请和释放的顺序不可预料，也会导致危险的情况。

heap_3.c策略

这种管理策略与前两种管理策略并不相同，该策略仅仅是简单的对malloc和free进行封装。采用的封装方式是操作内存前挂起调度器、完成后再恢复调度器。所以封装以后的malloc和free函数具有线程保护的功能。
这种管理策略不需要定义内存堆，而是使用编译器设置内存堆空间，一般在启动代码中设置。

heap_4.c策略

第四种分配策略与第二种分配策略类似，只是增加了一个合并算法。将相邻的空闲内存块合并成了一个大块。
与第一种和第二种内存管理策略一样，内存堆仍然是一个大数组，定义为：
static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];

内存申请

和第二种内存管理策略一样，它也使用一个链表结构来跟踪记录空闲内存块。结构体定义为：

typedef struct A_BLOCK_LINK
{
    struct A_BLOCK_LINK *pxNextFreeBlock;   /*指向列表中下一个空闲块*/
    size_t xBlockSize;                      /*当前空闲块的大小，包括链表结构大小*/
} BlockLink_t;

与第二种内存管理策略一样，空闲内存块也是以单链表的形式组织起来的，BlockLink_t类型的局部静态变量xStart表示链表头，但第四种内存管理策略的链表尾保存在内存堆空间最后位置，并使用BlockLink_t指针类型局部静态变量pxEnd指向这个区域（第二种内存管理策略使用静态变量xEnd表示链表尾），如图4-1所示。
第四种内存管理策略和第二种内存管理策略还有一个很大的不同是：第四种内存管理策略的空闲块链表不是以内存块大小为存储顺序，而是以内存块起始地址大小为存储顺序，地址小的在前，地址大的在后。这也是为了适应合并算法而作的改变。

从图4-1中可以看出，整个有效空间组成唯一一个空闲块，在空闲块的起始位置放置了一个链表结构，用于存储这个空闲块的大小和下一个空闲块的地址。由于目前只有一个空闲块，所以空闲块的pxNextFreeBlock指向指针pxEnd指向的位置，而链表xStart结构的pxNextFreeBlock指向空闲块。xStart表示链表头，pxEnd指向位置表示链表尾。
当申请x字节内存时，实际上不仅需要分配x字节内存，还要分配一个BlockLink_t类型结构体空间，用于描述这个内存块，结构体空间位于空闲内存块的最开始处。当然，和第一种、第二种内存管理策略一样，申请的内存大小和BlockLink_t类型结构体大小都要向上扩大到对齐字节数的整数倍。
我们先说一下内存申请过程：首先计算实际要分配的内存大小，判断申请内存合法性，如果合法则从链表头xStart开始查找，如果某个空闲块的xBlockSize字段大小能容得下要申请的内存，则将这块内存取出合适的部分返回给申请者，剩下的内存块组成一个新的空闲块，按照空闲块起始地址大小顺序插入到空闲块链表中，地址小的在前，地址大的在后。在插入到空闲块链表的过程中，还会执行合并算法：判断这个块是不是可以和上一个空闲块合并成一个大块，如果可以则合并；然后再判断能不能和下一个空闲块合并成一个大块，如果可以则合并！合并算法是第四种内存管理策略和第二种内存管理策略最大的不同!经过几次内存申请和释放后，可能的内存堆如图4-2所示：

heap_5.c策略

第五种内存管理策略允许内存堆跨越多个非连续的内存区，并且需要显示的初始化内存堆，除此之外其它操作都和第四种内存管理策略十分相似。
第一、第二和第四种内存管理策略都是利用一个大数组作为内存堆使用，并且只需要应用程序指定数组的大小（通过宏configTOTAL_HEAP_SIZE定义），数组定义由内存管理策略实现。第五种内存管理策略有些不同，首先它允许跨内存区定义多个内存堆，比如在片内RAM中定义一个内存堆，还可以在片外RAM再定义内存堆；其次，用户需要指定每个内存堆区域的起始地址和内存堆大小、将它们放在一个HeapRegion_t结构体类型数组中，并需要在使用任何内存分配和释放操作前调用vPortDefineHeapRegions()函数初始化这些内存堆。
让我们看一个例子：假设我们为内存堆分配两个内存块，第一个内存块大小为0x10000字节，起始地址为0x80000000；第二个内存块大小为0xa0000字节,起始地址为0x90000000。HeapRegion_t结构体类型数组可以定义如下：

HeapRegion_t xHeapRegions[] =
 {
      { ( uint8_t * ) 0x80000000UL, 0x10000 }, 
      { ( uint8_t * ) 0x90000000UL, 0xa0000 }, 
      { NULL, 0 }                
 };

两个内存块要按照地址顺序放入到数组中，地址小的在前，因此地址为0x80000000的内存块必须放数组的第一个位置。数组必须以使用一个NULL指针和0字节元素作为结束，以便让内存管理程序知道何时结束。
定义好内存堆数组后，需要应用程序调用vPortDefineHeapRegions()函数初始化这些内存堆：将它们组成一个链表，以xStart链表结构开头，以pxEnd指针指向的位置结束。我们看一下内存堆数组是如何初始化的，以上面的内存堆数组为例，初始化后的内存堆如图5-1所示（32为平台，sizeof(BlockLink_t)=8字节）。

内核内存分配

内核栈上的静态分配

对于用户空间来说，一般不用担心栈上的内存不足，也不用担心内存的管理问题。即使出问题也有内核保证系统正常运行。
但是在内核空间时不同的，不仅占空间有限，而且是为了管理的效率和尽量减少问题的发生。内核栈一般是小而且固定的，在x86体系结构下，内核栈的大小一般就是1页或者2页。
配置为1页的好处是分配时比较简单，只有一页，不存在内存碎片的情况，因为一页是本就是分配的最小单位。
当有中断发生时，如果共享内核栈，中断程序和被中断程序共享一个内核栈会可能导致空间不足，
于是，每个进程除了有个内核栈之外，还有一个中断栈，中断栈一般也就1页大小。

按照CPU分配

与单处理器不同，SMP环境下的并行是真正的并行，单CPU环境是宏观并行，微观串行。
SMP环境下加锁过多的话，会严重影响并行的效率，如果是自旋锁的话，还会浪费其他CPU的执行时间。
所以内核中才有了按CPU分配数据的接口。
按CPU分配数据之后，每个CPU自己的数据不会被其他CPU访问，虽然浪费了一点内存，但是会使系统更加的简洁高效。

按照CPU分配的优势

按CPU来分配数据主要有2个优点：
最直接的效果就是减少了对数据的锁，提高了系统的性能
由于每个CPU有自己的数据，所以处理器切换时可以大大减少缓存失效的几率 (*注1)

注1：如果一个处理器操作某个数据，而这个数据在另一个处理器的缓存中时，那么存放这个数据的那个
处理器必须清理或刷新自己的缓存。持续的缓存失效成为缓存抖动，对系统性能影响很大。

内存分配管理

在众多的内存分配函数中，如何选择合适的内存分配函数很重要，下面总结了一些选择的原则：

应用场景	分配函数选择
如果需要物理上连续的页	选择低级页分配器或者 kmalloc 函数
如果kmalloc分配是可以睡眠	指定 GFP_KERNEL 标志
如果kmalloc分配是不能睡眠	指定 GFP_ATOMIC 标志
如果不需要物理上连续的页	vmalloc 函数 (vmalloc 的性能不如 kmalloc)
如果需要高端内存	alloc_pages 函数获取 page 的地址，在用 kmap 之类的函数进行映射
如果频繁撤销/创建教导的数据结构	建立slab高速缓存

虚拟内存地址空间

为什么要有虚拟地址空间

普通进程在申请内存空间时会被内核认为是不紧要的，优先级较低。因而总是延迟处理，在之后的某个时候才会真正为其分配物理内存空间。
比如，普通进程中的 malloc 函数在申请物理内存空间时，内核不会直接为其分配页框。
另一方面，普通进程对应的可执行程序文件较大，不能够立即装入内存，而是采取运行时按需装入。
要实现这种延迟分配策略，就需要引入一种新的地址空间，即虚拟地址空间。可执行文件在装入时或者进程在执行 malloc 时，内核只会为其分配适当大小的虚拟地址空间。
虚拟地址空间只是针对普通进程。
这样的话，就会产生普通进程所要访问的页面不在内存区域而产生的缺页异常。
用户态下的普通进程只能访问 0-3GB 的用户空间；
内核态下的普通进程既能访问 0-3GB 的用户空间，也能访问 3-4GB 的内核空间（内核态下的普通进程有时也会需要访问用户空间）。

普通线程的用户堆栈与寄存器

对于多线程环境，虽然所有线程都共享同一片虚拟地址空间，但是每个线程都有自己的用户栈空间和寄存器，而用户堆仍然是所有线程共享的。

普通进程的页表

有两种页表，一种是内核页表（会在后面说明），另一种是进程页表。
普通进程使用的则是进程页表，而且每个普通进程都有自己的进程页表。如果是多线程，则这些线程共享的是主线程的进程页表。

四级页表

现在的 Linux 内核中采用四级页表，分别为：

页全局目录 (Page Global Directory, pgd)；
页上级目录 (Page Upper Directory, pud)；
页中间目录 (Page Middle Directory, pmd)；
页表 (Page Table, pt)。

task_struct 中的 mm_struct 对象用于管理该进程（或者线程共享的）页表。准确地说，mm_struct 中的 pgd 指针指向着该进程的页全局目录。

普通进程的页全局目录

普通进程的页全局目录中，第一部分表项映射的线性地址为 0-3GB 部分，剩余部分存放的是主内核页全局目录（后面会提到）中的所有表项。

内核线程

内核线程是一种只运行在内核地址空间的线程。所有的内核线程共享内核地址空间（对于 32 位系统来说，就是 3-4GB 的虚拟地址空间），所以也共享同一份内核页表。这也是为什么叫内核线程，而不叫内核进程的原因。
由于内核线程只运行在内核地址空间中，只会访问 3-4GB 的内核地址空间，不存在虚拟地址空间，因此每个内核线程的 task_struct 对象中的 mm 为 NULL。
普通线程虽然也是同主线程共享地址空间，但是它的 task_struct 对象中的 mm 不为空，指向的是主线程的 mm_struct 对象。
普通进程与内核线程有如下区别：
内核线程只运行在内核态，而普通进程既可以运行在内核态，也可以运行在用户态；
内核线程只使用 3-4GB (假设为 32 位系统) 的内核地址空间（共享的），但普通进程由于既可以运行在用户态，又可以运行在内核态，因此可以使用 4GB 的虚拟地址空间。
系统在正式启动内核时，会执行 start_kernel 函数。在这个函数中，会自动创建一个进程，名为 init_task。其 PID 为 0，运行在内核态中。然后开始执行一系列初始化。

主内核页全局目录

内核维持着一组自己使用的页表，也即主内核页全局目录。当内核在初始化完成后，其存放在 swapper_pg_dir 中，而且所有的普通进程和内核线程就不再使用它了。

内核线程如何访问页表

active_mm

对于内核线程，虽然它的 task_struct 中的 mm 为 NULL，但是它仍然需要访问内核空间，因此需要知道关于内核空间映射到物理内存的页表。然而不再使用 swapper_pg_dir，因此只能另外想法解决。
由于所有的普通进程的页全局目录中的后面部分为主内核页全局目录，因此内核线程只需要使用某个普通进程的页全局目录就可以了。
在 Linux 中，task_struct 中还有一个很重要的元素为 active_mm，它主要就是用于内核线程访问主内核页全局目录。
对于普通进程来说，task_struct 中的 mm 和 active_mm 指向的是同一片区域；
然而对内核线程来说，task_struct 中的 mm 为 NULL，active_mm 指向的是前一个普通进程的 mm_struct 对象。

mm_users 和 mm_count

但是这样还是不行，因为如果因为前一个普通进程退出了而导致它的 mm_struct 对象也被释放了，则内核线程就访问不到了。
为此，mm_struct 对象维护了一个计数器 mm_count，专门用来对引用这个 mm_struct 对象的自身及内核线程进行计数。初始时为 1，表示普通进程本身引用了它自己的 mm_struct 对象。只有当这个引用计数为 0 时，才会真正释放这个 mm_struct 对象。
另外，mm_struct 中还定义了一个 mm_users 计数器，它主要是用来对共享地址空间的线程计数。事实上，就是这个主线程所在线程组中线程的总个数。初始时为 1。

操作系统基础知识学习

操作系统内存管理机制