嵌入式操作系统

陈香兰xlanchen@ustc.
edu.
cn助教:陈博、李春华Spring2009内存管理内存管理二级页表动态存储器Slab算法非连续存储区内存管理RAM的某些部分永久地分配给内核,用以存放内核代码以及静态数据RAM的其余部分称为动态存储器(dynamicmemory)Arm存储系统之粗粒度的2级页表第一级页表:每一项描述1MB空间的映射关系每个条目4B页表大小:16KB第二级页表:页框大小4KB每个条目大小4B页表大小:1KBLinux中虚拟地址空间:KERNEL_RAM_VADDR:3GB以上+TEXT_OFFSET(大多为0x8000)swapper_pg_dirKERNEL_RAM_VADDR-0x4000,大小为16KBHead.
S中:__create_page_tablesswapper_pg_dir__create_page_tables3GB虚拟物理0swapper_pg_dir第0项第3GB对应项动态存储器进程和内核都需要动态存储器属于稀缺资源整个系统的性能取决于如何有效地管理动态存储器对于动态存储器要尽可能做到:按需分配,不需要时释放主要内容内核如何给自己分配动态存储器页框管理小内存管理非连续存储区管理页框管理Linux采用页作为内存管理的基本单位Linux采用的标准的页框大小为4KB4KB是大多数磁盘块大小的倍数传输效率高管理方便例如:512M的物理内存对应于128K个页框算法:伙伴算法请求页框内核实现了一种底层的内存分配机制,并提供了几个接口供其他内核函数调用.
分配:alloc_pages/alloc_page__get_free_pages/__get_free_page/__get_dma_pages/get_zeroed_page释放free_pages/__free_pages/free_page__free_page页框数据结构内核必须记录每个页框当前的状态哪些属于进程,哪些存放了内核代码/数据是否空闲,即是否可用如果不可用,内核需要知道是谁在用这个页框这个页框可能的使用者有用户态进程、动态分配的内核数据结构、静态的内核代码、页面cache、设备驱动程序缓冲的数据等等页描述符页描述符:structpage每个物理页框都用一个页描述符表示count:页的使用引用计数器0:空闲>0:页已经分配给一个或多个进程或用户某些内核数据结构flags:页框状态,最多可以有32个,每个使用一个位表示参见枚举类型pageflags当内核调用一个页框分配函数时,必须指明请求页框所在的区.
这个一般是通过一些flag标志来指定的GFP_XXX关于NUMA不考虑物理内存被划分为若干个node存取时间不等考虑CPU局部性Node使用数据结构pg_data_t描述每个node被划分成若干个zone存储区(MemoryZones)在一个理想的体系结构中,一个页框就是一个物理存储单元,可以用于任何事情,例如存放内核数据/用户数据/缓存磁盘数据等实际上存在硬件制约:一些页框由于自身的物理地址的原因不能被一些任务所使用,例如ISA总线的DMA控制器只能对ram的前16M寻址在一些具有大容量ram的32位计算机中,CPU不能直接访问所有的物理存储器,因为线性地址空间不够zone为了应付这种限制,Linux把具有同样性质的物理内存划分成——区(zones)Linux把物理存储器划分为4个区ZONE_DMAZONE_DMA32(未见用)ZONE_NORMALZONE_HIGHMEM参见枚举类型zone_typeZONE_DMA和ZONE_NORMAL区包含存储器的"常规"页,通过把它们映射到线性地址空间的3GB以上,内核就可直接访问而ZONE_HIGHMEN区中包含的存储器页面不能由内核直接访问每个zone使用structzone表示关键:free_area所有物理页框的描述符,组织在mem_map的数组中mem_map数组mem_map的定义和初始化start_kernelsetup_archpaging_initbootmem_initbootmem_init_nodefree_area_init_nodealloc_node_mem_map页描述符将会占用很大的一段空间Mem_map、node、zone之间的关系请求页框内核实现了一种底层的内存分配机制,并提供了几个接口供其他内核函数调用.
分配:alloc_pages/alloc_page/alloc_pages_node/alloc_pages_current/…__get_free_pages/__get_free_page/__get_dma_pages/get_zeroed_page释放free_pages/__free_pages/free_page__free_page关于unsignedintgfp_mask指明可在何处并以何种方式查找空闲的页框GFP_ATOMIC,这种分配是高优先级的并且不能睡眠.
一般在中断处理程序,下半部分和其他不能睡眠的场合下使用GFP_KERNEL,这是普通的分配模式,允许睡眠.
一般在用户进程可能调用到的内核函数中使用,这个时候进程是可以安全的睡眠的GFP_DMA,设备驱动程序需要DMA内存时使用在内核中释放页框时要非常小心,必须确保只释放了所请求的页框,否则内核可能会崩溃page=__get_free_page(GFP_KERNEL,3);If(!
page){/*如果内存不足,分配失败,必须在这里处理这个失败*/}/*现在'page'变量指向了8个连续页框的起始线性地址*/free_pages(page,3);/*现在页框被释放,不应该再对page中存放的线性地址进行操作*/页框管理算法内核要为分配一组连续的页框建立一种稳定、高效的分配策略这种策略要解决碎片问题:即频繁的请求和释放不同大小的一组连续页框,必然导致在物理页框中分散许多小块的空闲页框这样,即使有足够的空闲页框页框满足请求,但要分配一个大块的连续页框可能就无法满足了有两种办法可以避免这样的碎片利用MMU把一组非连续的物理空闲页框映射到连续的线性地址空间使用一种适当的技术来记录现存的空闲连续页框的情况,以尽量避免为满足对小块的请求而把大块的空闲块进行分割基于下面的原因,Linux内核首选第二种方法在某些情况下,必须使用连续的页框,如DMA尽量少的修改内核页表buddy算法(伙伴算法)Linux使用著名的伙伴算法来解决碎片问题.
把所有空闲页框分组为10个块链表,每个块链表分别包含大小为1,2,4,6,8,16,32,64,128,256和512个连续的页框每个块的第一个页框的物理地址是该块大小的整数倍.
例如:大小为16个页框的块,其起址是16*4KB的倍数伙伴的定义例如:0和1是伙伴,1和2不是伙伴两个伙伴的大小必须相同,物理地址必须连续假定伙伴的大小为b那么第一个伙伴的物理地址必须是2*b*4KB对齐事实上伙伴是通过对大块的物理内存划分获得的假如从第0个页面开始到第3个页面结束的内存每次都对半划分,那么第一次划分获得大小为2页的伙伴进一步划分,可以获得大小为1页的伙伴,例如0和1,2和301230123数据结构Linux为每个zone使用各自独立的伙伴系统每个伙伴系统使用的主要数据结构为:空闲内存管理数组free_areamem_map数组前面介绍过的页描述符数组每个页描述符描述一个物理页框整个mem_map数组描述整个zone中的所有的物理内存空闲内存管理数组空闲内存按照伙伴管理的方法进行组织使用free_area结构伙伴当两个伙伴都为空闲的时候,就合并成一个更大的块该过程将一直进行,直到找不到可以合并的伙伴为止寻找伙伴给定一个要释放的空闲块找到其伙伴查看其状态:合并or不合并举例假设有128MB的ram.
128MB最多可以分成215=32768个页框,214=16384个8KB(2页)的块或213=8192个16KB(4页)的块,直至64个大小为512个页的块假设要请求一个大小为128个页框的块(0.
5MB).
算法先free_area[7]中检查是否有空闲块(块大小为128个页框)若没有,就到free_area[8]中找一个空闲块(块大小为256个页框)若存在这样的块,内核就把256个页框分成两等份,一半用作满足请求,另一半插入free_area[7]中如果在free_area[8]中也没有空闲块,就继续找free_area[9]中是否有空闲块.