第4章-内存管理

第四章内存管理内存管理内存管理子系统是操作系统的重要组成部分，它的主要任务是：管理系统中的内存资源，提供高效地分配和回收内存资源的手段；提高内存的利用率，减少对内存的浪费，充分发挥内存的作用。Linux共实现了五个内存管理器，它们是：物理内存管理器内核内存管理器虚拟内存管理器内核虚拟内存管理器用户空间内存管理器内存管理内核内存管理器虚拟内存管理器内核虚拟内存管理器物理内存管理器用户内存管理器物理内存系统其余部分4.1物理内存管理器物理内存管理器管理的基本内存单位是物理页，每个物理页用一个page结构描述，所有的page结构组成一个mem_map[]数组。typedefstructpage{ structpage *next; structpage *prev; structinode *inode; unsignedlong offset; structpage *next_hash; //用于页缓存 atomic_t count; unsignedlong flags; structwait_queue *wait; structpage **pprev_hash; //用于页缓存 structbuffer_head *buffers;}mem_map_t;4.1物理内存管理器flags各位的意义位名称意义0PG_locked加锁1PG_error页上出现I/O错2PG_referenced正被引用3PG_dirty脏页4PG_uptodate页的内容是否有效5PG_free_after页已写完8PG_DMA能否用作DMA传送9PG_Slab是否用做slab（内核内存管理器）31PG_reserved1：保留，0：可用4.1物理内存管理器系统中所有的空闲页都记录在数组free_area[]中。structfree_area_struct{ structpage*next; structpage*prev; unsignedint*map;};structfree_area_structfree_area[NR_MEM_LISTS];NR_MEM_LISTS的值是10或12。该数组已经建立并初始化。4.1物理内存管理器位图map用于记录页块及其伙伴是否在队列中，两个伙伴合用一位，其意义如下：1）如两伙伴全都不在队列中（已分配或已组成了更大的块），它们合用的位为0；2）如一个伙伴在队列中，一个不在队列中，则它们合用的位为1；3）如两个伙伴都在队列中，则它们应该合并成更大的块，加入到free_area[]数组中更上面的队列，所以它们合用的位应为0；4）在free_area数组的最大一个队列中，位图无用。位图的大小=物理页数/2i位，i是队列在数组free_area[]中的索引。（应该是物理页数/2（i+1））。4.1物理内存管理器用第一个物理页的page结构代表大小为2i页的连续物理页块，用它的编号代表整个页块的编号。大小为2i、编号为map_nr的页块的伙伴是：map_nr^（-（（~0）<<i））这两个伙伴在位图free_area[i]->map中共用的标志位是：(map_nr)>>(1+i)如：页块8、9、10、11（代表是8）的伙伴是12、13、14、15（代表是12），它们在位图free_area[2]->map中共用第1位。4.1物理内存管理器04321765物理内存……3210mapmapmapmap4561free_area[]4.1物理内存管理器物理内存管理器使用向量表free_area[]来分配和回收物理页。

全局变量nr_free_pages记录系统中当前的空闲页数。全局变量freepages为系统中的空闲物理内存划了三条基准线。typedefstructfreepages_v1{ unsignedint min; unsignedint low; unsignedint high;}freepages_v1;typedeffreepages_v1 freepages_t;freepages_t freepages；

4.1物理内存管理器分配原则（该原则在不断变化）：当系统中空闲物理页数少于freepages.min时，应该回收内存；一旦开始内存回收，每次分配前都要进行回收，直到系统中空闲物理页数大于freepages.high；当系统中空闲物理页数大于freepages.high时，每次都直接进行内存分配，直到空闲物理页数再次小于freepages.min；当系统中空闲内存数大于freepages.high时，可以立刻进行内存分配。4.1.2物理页分配物理内存管理器使用伙伴（Buddy）算法分配和释放物理页块，页块大小为2i个页。物理内存管理器返回的是在内核空间中看到的内存块的起始地址（物理地址+0xC0000000）。物理内存的分配和释放不影响页目录和页表。分配函数是__get_free_pages，定义为：unsignedlong__get_free_pages(intgfp_mask,unsignedlongorder)gfp_mask是对内存的要求，order是申请的大小（2的指数）。4.1.2物理页分配1、如果空闲物理内存较少（需要回收），则：1）唤醒内核交换守护进程kswapd。2）如果在gfp_mask中设置了__GFP_WAIT标志，则强行回收内存（自己调用回收函数）。2、如果不需要回收内存或已回收到了足够的内存，则查free_area数组的第order列：如果其中有满足要求的页块，则摘下一块，修改位图，累减nr_free_pages，返回物理页块的首地址。否则（队列为空），向上搜索free_area数组：如果整个free_area数组中都没有满足要求的页块，则此次分配失败，返回0。如果找到了一个满足要求的页块，则将其从队列中摘下、反复分割成伙伴，将一个大小适中的伙伴分配给用户，其余伙伴加入free_area数组。同时修改位图，累减变量nr_free_pages。4.1.2物理页分配04321765物理内存……3210mapmapmapmap456free_area申请1页4.1.2物理页分配04321765物理内存……3210mapmapmapmap4、5566free_area4.1.3物理页释放在物理页的释放过程中，必须尽可能地按照伙伴算法合并页块。函数free_pages用于释放页块，其定义如下：

voidfree_pages(unsignedlongaddr,unsignedlongorder)

addr是要释放页块的首地址；order是要释放页块的大小。4.1.3物理页释放1、根据首地址addr算出页块在mem_map[]中的索引map_nr（addr>>12），找到页块第一页对应的page结构（mem_map[map_nr]）。2、如果该页块是保留的，则不允许释放，返回。3、将page结构的引用计数（page.count）减1。4、如果count>0，说明页块还有别的使用者，因此不能释放它。返回。4.1.3物理页释放5、如果count=0，则释放它：1）清除page结构的flags域中的PG_referenced位。2）累加变量nr_free_pages（加上回收的物理页数）。3）将页块加入到数组free_area[]中：如果页块的伙伴不在队列free_area[order]中，则将其直接插入队列，修改位图。返回。如果页块的伙伴在队列中且order＝NR_MEM_LISTS-1，则将其直接插入队列。返回。如果页块的伙伴在队列中但order<NR_MEM_LISTS-1，则将页块的伙伴从队列中摘下、修改位图，将它们合并成一个更大的页块，重新插入数组free_area[]中（递归）。4.1.3物理页释放04321765物理内存……3210mapmapmapmap4、5566free_area4.1.4物理页回收内核交换守护进程kswapd负责物理页的回收，从而保证系统有足够的空闲页。其主体如下：while(1){ do{ if(nr_free_pages>=freepages.high) break; //不需要回收内存 if(!do_try_to_free_pages(GFP_KSWAPD)) break; //没有回收到内存 }while(!tsk->need_resched); run_task_queue(&tq_disk); //处理磁盘任务队列 tsk->state=TASK_INTERRUPTIBLE; schedule_timeout(HZ); //睡眠100个滴答}4.1.4物理页回收在函数do_try_to_free_pages中完成物理页的回收工作。为了提高效率，该函数要尝试多种回收手段，一次回收多个物理页（SWAP_CLUSTER_MAX==32）。

为了公平起见，该函数采用时钟算法搜索各种数据结构。不是每次都从头开始，也不是每次都检查完所有的结构。每次检查的数据结构的个数由对物理内存的需求决定。如果系统中的空闲页太少，就多检查一些，否则就少检查一些。4.1.4物理页回收函数do_try_to_free_pages回收内存的顺序如下：1、从内核内存管理器中回收空闲页。

kmem_cache_reap(gfp_mask)

2、回收可废弃的内存页。

shrink_mmap(priority,gfp_mask)

顺序搜索数组mem_map[]，回收：在交换缓存中且已经不再使用的页。用作buffer且所有buffer都不再使用的页。在页缓存中且没有任何进程使用的页。4.1.4物理页回收3、回收共享内存页。

shm_swap(priority,gfp_mask)

4、回收进程的虚拟内存，即将进程的某些页交换到外存。

swap_out(priority,gfp_mask)

5、从目录缓存中回收物理页。

shrink_dcache_memory(priority,gfp_mask)

4.1物理内存管理器当物理内存较大时（超过1GB），上述方法需要扩充，为此引入zone的概念：zone是具有相同属性的连续的物理页。通常定义三个zone：1、ZONE_DMA：16MB以内，用于DMA。2、ZONE_NORMAL：16MB～896MB，用于普通物理内存，在内核中有虚拟地址。3、ZONE_HIGHMEM：大于896MB，用于高端物理内存，在内核中没有虚拟地址。每个zone都有自己的free_area[]数组。4.1物理内存管理器随着NUMA结构的出现，系统所管理的物理地址空间不再一致。对一个CPU来说，有的内存近，有的内存远；有的速度快，有的速度慢。CPU希望使用尽可能一致的物理页，尤其是对一次申请。为此引入节点（node）的概念。节点的描述结构是pglist_data，其中定义了该节点的管理区（zone）、各类需求（GFP标志）的分配策略（每策略最多有4个可选的zone，它们按优先级排序，分配时按顺序搜索各zone并试图从中分配物理页）、其page结构数组等。系统中所有的节点组成一个队列pgdat_list。

4.2内核内存管理器内核在运行的过程中，需要大量而频繁地使用内存，如建立各种用于管理的数据结构、缓冲区等。这些内存有以下特点：尺寸一般都很小，远远小于一页，如果直接使用物理内存管理器按页管理，其利用率会非常低。要求动态分配和释放，无法预测使用量。不参与交换（不在进程的虚拟地址空间，也不在交换缓存、页缓存及Buffercache中，不会被换入、换出）。要求响应速度快，分配速度慢的管理器会导致整个系统性能的下降。4.2内核内存管理器内核内存管理器的种类：1、无内核内存管理器；2、资源映射图分配器；3、简单2次幂空闲表；4、McKusick-Karels分配器；5、伙伴系统；6、SVR4Lazy伙伴算法；7、Mach-OSF/1的Zone分配器；8、存储桶（bucket）；9、Solaris2.4的Slab分配器。Linux的内核内存管理器采用Slab分配器。4.2内核内存管理器cache_cachecache1cache2cache3……cachenslab1slab2slab3slab4s_freep物理页对象对象对象对象4.2内核内存管理器（cache结构）structkmem_cache_s{ kmem_slab_t *c_freep; //第一个有空闲对象的slab unsignedlong c_flags; //标志 unsignedlong c_offset; unsignedlong c_num; //每个slab中的对象数 unsignedlong c_magic; unsignedlong c_inuse; //keptatzero kmem_slab_t *c_firstp; //第一个slab kmem_slab_t *c_lastp; //最后一个slab spinlock_t c_spinlock; unsignedlong c_growing; //是否正在增长 unsignedlong c_dflags; size_t c_org_size; //对象原始大小 unsignedlong c_gfporder; //表示slab大小的指数 void(*c_ctor)(void,kmem_cache_t,unsignedlong); //构造函数 void(*c_dtor)(void,kmem_cache_t,unsignedlong); //析构函数 unsignedlong c_align; //对象对齐关系 size_t c_colour; //cache着色区的大小 size_t c_colour_next; //着色区中下一个可用的位置 unsignedlong c_failures; constchar *c_name; //cache名 structkmem_cache_s*c_nextp; //下一个cache结构 kmem_cache_t *c_index_cachep; //分配slab->s_index数组的cache};4.2内核内存管理器（cache结构）该结构描述了一个cache的所有信息，如：一个slab的大小（占多少物理页）：c_gfporder；slab中一个对象的大小：c_org_size；一个slab可以划分成多少对象：c_num；该cache所管理的第一个slab、最后一个slab和第一个有空闲对象的slab：c_firstp、c_lastp、c_freep；着色区：剩余空间，用于均匀分布slab对象。域c_offset的意义随slab对象的大小而变化：对小对象：它是从对象起始地址到对象指针kmem_bufctl_s之间的距离；对大对象：它是对象的大小。4.2内核内存管理器（slab结构）#define SLAB_OFFSET_BITS 16 typedefstructkmem_slab_s{ structkmem_bufctl_s *s_freep; //第一个空闲对象 structkmem_bufctl_s *s_index; //大对象指针数组 unsignedlong s_magic; unsignedlong s_inuse; //已用的对象数 structkmem_slab_s *s_nextp; structkmem_slab_s *s_prevp; void *s_mem; //第一个对象的地址 unsignedlong s_offset:SLAB_OFFSET_BITS, s_dma:1; //能否用做DMA}kmem_slab_t;4.2内核内存管理器（slab结构）结构kmem_slab_s描述了一个slab的所有信息，如：第一个对象的地址：s_mem；指向第一个空闲对象的指针：s_freep；slab中已经用掉的对象数：s_inuse；对象可否用于DMA等。slab结构所在的位置与对象大小有关：小对象（＜512字节）：与对象在同一个物理页块上；大对象（≥512字节）：在物理页块之外。目的是尽可能地减少内存的浪费。专门定义一个slabcache，用于管理slab结构的分配和回收。4.2内核内存管理器（slab结构）每一个小对象的尾部都加了一个kmem_bufctl_s结构，用于管理小对象。typedefstructkmem_bufctl_s{ union{ structkmem_bufctl_s *buf_nextp; kmem_slab_t *buf_slabp; void *buf_objp; }u;}kmem_bufctl_t;kmem_bufctl_s结构可以用作不同目的，如分配前用它将slab对象连接成链表，分配后用它指向对象所属的slab结构等。2.4以后，该结构已经退化成一个无符号小整数。4.2内核内存管理器（通用cache）系统初始化时，预定义了14个通用cache，并已将它们的cache结构保存在数组cache_sizes[]中。typedefstructcache_sizes{ size_t cs_size; kmem_cache_t *cs_cachep;}cache_sizes_t;cache_sizes_tcache_sizes[14]；32641282565121024204840968192163843276865536131072cachecachecachecachecachecache_sizes[]4.2.2cache的建立kmem_cache_t*kmem_cache_create(constchar*name, size_tsize,size_toffset,unsignedlongflags, void(*ctor)(void*,kmem_cache_t*,unsignedlong), void(*dtor)(void*,kmem_cache_t*,unsignedlong))完成如下工作：1、检查各参数的合法性。

2、从cache_cache中申请一个内存块用于建立新cache的kmem_cache_s结构。

3、计算并填写新cache结构的各个域。4、将新cache的结构插入系统中的cache链表中。4.2.3为cache增加slabintkmem_cache_grow(kmem_cache_t*cachep,intflags)完成如下工作：1、从物理内存管理器中申请物理页，页数由cache结构中的c_gfporder域指定。2、建立slab结构：小对象，在物理页的尾部（或首部）建立slab结构；大对象，在cache_slabp中申请一个slab结构。3、对大对象cache，再申请一块内存用于建立slab对象链表（kmem_bufctl_t结构数组）。slab的s_index域指向该结构数组。4.2.3为cache增加slab4、修改申请到的各物理页（不仅是第一页）的page结构：next指向kmem_cache_s结构，prev指向kmem_slab_s结构（便于对象的释放）；在域flags上加入PG_Slab标志。5、初始化slab结构及各slab对象。小对象：将各slab对象串成链表，让s_freep指向表头。大对象：将结构数组s_index的各元素串成链表，让s_freep指向表头。6、将新slab加入cachep中，同时调整cachep的c_freep、c_firstp、c_lastp指针。4.2.3为cache增加slabslab结构s_indexs_freeps_memkmem_bufctl_t结构数组大对象cache的slab结构物理页块对象对象对象对象4.2.3为cache增加slabs_freepkmem_bufctl_t着色区Slab结构……小对象cache的slab结构

小对象小对象小对象4.2.4对象的分配有两种对象分配函数：kmalloc(size_tsize,intflags)kmem_cache_alloc(kmem_cache_t*cachep,intflags)当只知大小不知cache时用第一个，知道cache时用第二个。kmalloc先根据size在cache_sizes[]中找到一个通用cache，而后再从cache中分配对象。从cache中分配对象的方法如下：1、如果还未为cache创建slab，或它的所有slab都没有空闲对象，则调用函数kmem_cache_grow()为其创建一个新的slab。4.2.4对象的分配2、找出该cache中有空闲对象的第一个slab，并找到它的第一个空闲对象（s_freep）。将第一个空闲对象分配出去（bufp），并调整slab的参数。3、返回空闲对象的首地址： 1）小对象： objp=((void*)bufp)-cachep->c_offset; //地址 bufp->buf_slabp=slabp; //指向它所属的slab 2）大对象： objp=((bufp-slabp->s_index)*cachep->c_offset) +slabp->s_mem; bufp->buf_objp=objp；4.2.5对象的释放三种释放操作：1、知道对象所属cache时，用：kmem_cache_free(kmem_cache_t*cachep,void*objp)2、不知对象所属cache时，用：kfree(constvoid*objp)1）mem_map[objp>>12]是objp所在物理页的page2）(kmem_cache_t*)(>next)是该页对应的cache结构3、知道对象大小时，用：kfree_s(constvoid*objp,size_tsize)增加一个大小检查。4.2.5对象的释放（小对象）1、利用对象尾部的指针找到它所属的slab。 bufp=(kmem_bufctl_t*)(objp+cachep->c_offset); slabp=bufp->buf_slabp;2、将对象加入slab的空闲对象队列中。3、调整cache的空闲队列：1）如果释放以后slab全部空闲，将该slab移到slab队列的队尾，以便归还给物理内存管理器。2）如果释放以前slab已被全部分完，则将该slab后移，以保证slab队列的顺序，必要时调整cache的c_freep指针。4.2.5对象的释放（大对象）1、根据对象地址objp，找到对象所在的物理页，并据此找到该对象所属的slab：slabp=(kmem_slab_t*)(mem_map[objp>>12].prev);2、算出该对象在指针数组中的位置：slabp->s_index[(objp-slabp->s_mem)/cachep->c_offset]3、将对象加入slab的空闲对象队列中。1）如果释放以后slab全部空闲，则将该slab移到队尾。2）如果释放以前slab已被全部分完，则将该slab后移，必要时调整cache的c_freep指针。4.2.6回收cache中的空闲slab函数kmem_cache_reap按照时钟算法，每次搜索10个cache，从中选择一个空闲slab最多的cache，将它的空闲slab归还给物理内存管理器。

1、从clock_searchp开始顺序搜索各cache，找出一个空闲slab最多的cache。

2、调整clock_searchp，使其指向找到的cache。3、回收该cache的空闲slab。下列cache不在回收之列：标志为SLAB_NO_REAP的cache正在增长的cache已经损坏的cache不满足要求的cache4.3虚拟内存管理器直接使用物理内存管理器可以运行程序，方法是：申请足够的内存，将程序一次性全部装入。但可能带来如下问题：1、当程序过大时（超过可用的物理内存量），无法将其装入内存，因而无法运行。2、多进程并发执行的开销很大（需要将进程整个或部分地换出/换入内存）。3、由于直接使用物理内存，因而进程之间难以实现隔离和保护。4、程序的设计依赖于物理内存的配置，编程困难且程序难以移植。4.3虚拟内存管理器但大程序、多进程、并发、保护、移植等是现代软件设计不可回避的问题，因而是操作系统必须解决的问题。人们提出了很多方法来解决上述问题，如覆盖、交换，但这两种技术都不能完全满足需要。软件覆盖技术：通过覆盖那些暂时不用的程序代码或数据来复用内存。

交换机制：进程被作为一个完整的单位，在内存和外存之间交换。4.3虚拟内存管理器为此又提出了基于分页机制的虚拟内存管理，其思路是：虚拟（欺骗），即给用户进程造成系统有大内存，而且它独占大内存的假象。方法：1、隔离：不让用户进程看到实际的物理内存，只给它看到一个美好的假象（虚拟内存）。2、勤快：频繁地在内、外存之间移动数据，保证进程当前使用到的代码和数据在内存中。3、小单位：量小、速度快，不易被察觉。规律：程序运行的局部性规律。4.3虚拟内存管理器1978年，Unix系统在VAX机上第一次实现了基于分页机制的虚拟内存管理器：1、将物理地址空间和程序的虚拟地址空间都分成固定大小的页，同时引入页表，实现虚拟空间与物理空间的隔离，并负责虚拟地址到物理地址的转换。2、地址的转换由硬件实现，转换所用的页表由操作系统内核维护。3、虚拟内存管理器负责在内外存之间交换页面，给用户造成假象，使得每个进程都认为自己是系统中唯一的一个程序，独占系统的全部地址空间（4GB）。分页机制、页表、虚拟内存的引入，是操作系统发展史上一个里程碑。4.3虚拟内存管理器OS程序逻辑地址空间物理地址空间页表交换外存搬入搬出搬入4.3虚拟内存管理器虚拟内存管理器的优点（设计目标）：1、大地址空间：进程可用的地址空间可超过物理内存总量。2、并发：允许多进程同时驻留内存。3、进程保护：不同进程的虚拟地址空间完全隔离。4、虚存共享：不同进程之间可以共享物理页。5、代码可移植：在设计程序时不必预先约定机器的配置。6、内存映射：将文件映射到进程的虚拟地址空间，使得对文件的访问与对内存单元的访问一样。7、允许程序重定位：程序可以放在物理内存中的任意位置，且可以在执行过程中任意移动。8、代价小：换入换出单个页面的代价比交换整个进程或内存段要小得多。4.3虚拟内存管理器虚拟内存管理器的功能：1、地址空间管理：负责进程虚拟地址空间的创建、回收和动态改变。2、地址转换：将进程产生的虚拟地址转换为物理地址。当无法转换时，产生缺页异常。（硬件和内核共同完成）3、缺页处理：当产生缺页异常时，把需要的页面装入内存。4、换出：当物理内存紧缺时，将进程的某些页面换出内存。5、内存保护：以页为单位实现内存的保护。当发现非法地址访问时，向进程发送段违例信号（SIGSEGV）。6、内存共享：允许别的进程共享其地址空间的某一部分。7、监视系统负荷：当系统超负荷时，采取相应措施，如停止启动新进程等。8、其它服务：提供对其它功能的支持，如文件映射、动态连接库等。4.3虚拟内存管理器几个概念： 装入 执行程序地址 进程地址 机器地址 描述符 页表逻辑地址 线性地址 物理地址

（虚拟地址）

逻辑地址空间 线性地址空间 物理地址空间

（虚拟地址空间）4.3.1虚拟内存抽象模型（页表）在虚拟内存管理结构中，页表是最关键、最基本的数据结构。在Intel处理器中分为两级：页目录、页表，以下统称为页表。页表是页表项的数组，具有以下特征：1、页表的内容只能由内核改变，进程无法看到、更无法修改自己的页表。2、页表项具有非常丰富的含义。当页在内存时，页表项记录映射关系和控制信息。当页不在内存时，页表项记录页面在外存中的位置。页表项中包含有丰富的控制信息，可以实现对页的管理和保护。4.3.1虚拟内存抽象模型（页表）3、页表及其内容可以动态变化。页表项甚至页表本身都可以动态地创建、修改、删除、切换，以反映映射关系的变化。所有这些改变均由内核完成，对用户透明。4、页表项的内容不受限制。映射关系可动态变化。映射顺序没有要求，不需要连续，也不需要有序。可以重叠，即可以将多个进程的虚拟页映射到同一个物理页（共享）。5、通过页表可以实现进程虚拟地址空间的隔离。每个进程都有自己的页目录和页表，一个进程不能使用别的进程的页表。进程切换时，其页目录要同时切换。4.3.1虚拟内存抽象模型（页表）由于虚拟空间很大，所以页表也很大。如4GB的虚拟地址空间有1024*1024个页表项。采用一级页表浪费空间，管理也不方便。所以，通常建立多级页表。为了统一起见，Linux采用三级页表。在Intel处理器中，第一级页表对应页目录，第二级页表称为页中间表（目录），第三级页表对应为处理器的页表。每个页目录中有1024个页目录项，每个页目录项描述一个页中间表；每个页中间表只有1个页中间项，每个页中间项描述一个页表；每个页表有1024个页表项，每个页表项描述一个虚拟页。4.3.1虚拟内存抽象模型（页表）页目录和页表描述了进程的整个虚拟地址空间。页表项可以为空，页目录项也可以为空。如果页目录项为空，它对应的整个页表都不存在。事实上，进程的页表是在使用的过程中动态建立的。因此，进程的页表实际占用的空间要远远小于4MB。页目录和页表是虚拟内存管理的重要数据结构，虚拟内存管理器通过不断地调整页目录和页表项来管理进程的虚拟地址空间。4.3.1虚拟内存抽象模型（VMA）进程的所有信息，包括代码、数据、堆栈、共享区等，都存放在它的虚拟地址空间中。由于属性的不同，进程对自己虚拟地址空间的使用方式也不同，因此对它们的管理方式也应该不同。如程序代码可以执行但不能修改，数据部分可以读写但不能执行，堆栈可以动态地增长等。因此，应该根据进程的具体情况，将它的虚拟地址空间划分成小的虚拟内存区域（区间）。每个虚拟内存区域就是一段具有相同属性的、连续的虚拟地址空间。虚拟内存区域可大可小，最小一页，最大不超过4GB。4.3.1虚拟内存抽象模型（VMA）structvm_area_struct{ structmm_struct *vm_mm; unsignedlong vm_start; unsignedlong vm_end; structvm_area_struct *vm_next; pgprot_t vm_page_prot; unsignedshort vm_flags; short vm_avl_height; //AVL树 structvm_area_struct *vm_avl_left; structvm_area_struct *vm_avl_right; structvm_area_struct *vm_next_share;//用于映射页和共享页 structvm_area_struct **vm_pprev_share; structvm_operations_struct*vm_ops; unsignedlong vm_offset; structfile *vm_file; unsignedlong vm_pte; //共享内存专用};4.3.1虚拟内存抽象模型（VMA）structvm_operations_struct{ void(*open)(structvm_area_struct*area); void(*close)(structvm_area_struct*area); void(*unmap)(structvm_area_struct*area,unsignedlong,size_t); void(*protect)(structvm_area_struct*area,unsignedlong, size_t,unsignedintnewprot); int(*sync)(structvm_area_struct*area,unsignedlong, size_t,unsignedintflags); void(*advise)(structvm_area_struct*area,unsignedlong, size_t,unsignedintadvise); unsignedlong(*nopage)(structvm_area_struct*area, unsignedlongaddress,intwrite_access); unsignedlong(*wppage)(structvm_area_struct*area, unsignedlongaddress,unsignedlongpage); int(*swapout)(structvm_area_struct*,structpage*); pte_t(*swapin)(structvm_area_struct*,unsignedlong, unsignedlong);};4.3.1虚拟内存抽象模型（VMA）vm_endvm_startvm_flagsvm_opsvm_offsetvm_filevm_nextvm_area_struct进程的虚拟内存opencloseunmapprotectsyncadvisenopagewppageswapoutswapin文件虚拟内存区域用来弥补页表项的不足。4.3.1虚拟内存抽象模型（MM）一个进程会有很多虚拟内存区域，虚拟内存管理器经常需要使用这些虚拟内存区域。如，当发生缺页异常时，要根据发生异常的虚拟地址，找到包含它的虚拟内存区域，从而决定具体的处理方式。因此需要一种机制来管理一个进程的所有vma结构。另外，虚拟内存管理器还需要一个结构来记录进程中与内存有关的信息。如进程页目录的位置，进程的代码、数据、堆栈、堆、参数、环境变量等在虚拟空间中的位置，进程驻留在物理内存中的页面个数，进程的LDT等。

为每个进程建立一个内存管理结构mm_struct。4.3.1虚拟内存抽象模型（MM）structmm_struct{ structvm_area_struct*mmap; //vma链表 structvm_area_struct*mmap_avl; //vma树 structvm_area_struct*mmap_cache; //最后一次使用的vma pgd_t *pgd; //进程的页目录 atomic_t count; //引用计数 int map_count; //VMAs个数 structsemaphore mmap_sem; unsignedlong context; unsignedlong start_code,end_code,start_data,end_data; unsignedlong start_brk,brk,start_stack; unsignedlong arg_start,arg_end,env_start,env_end; unsignedlong rss,total_vm,locked_vm; unsignedlong def_flags; unsignedlong cpu_vm_mask; unsignedlong swap_cnt; //可以换出的页数 unsignedlong swap_address; void *segments; //进程的LDT};4.3.1虚拟内存抽象模型（MM）

mmappgdvm_endvm_startvm_offsetvm_endvm_startvm_offsetvm_endvm_startvm_offsetmm_structvm_area_struct虚拟内存区域1区域3区域2数据数据程序可执行文件004.3.1虚拟内存抽象模型访问控制

每个vma中都包含有一个vm_page_prot域，其中记录了缺省情况下对该区域的所有页的保护权限设置。

真正对页起到保护作用的是定义在各个页表项中的访问控制信息，对页表项中访问控制信息的设置要参考vma中的域vm_page_prot。

当处理器转换虚拟地址时，它利用页表项中的控制信息检查进程对页的访问，防止进程非法使用内存。

限制对于内存区域的访问会提高系统的安全性。4.3.1虚拟内存抽象模型按需调页（DemandPaging）节省物理内存的一种方法是只加载进程当前正在使用的虚拟页。这种直到访问时才加载虚拟页的技术叫做按需调页（demandpaging）。由于按需调页，虚拟内存管理器必须处理pagefault异常。使用按需调页技术可以实现内存映射，即将文件的内容映射到进程的虚拟内存。4.3.1虚拟内存抽象模型交换（Swapping）

物理内存回收程序可能会回收进程的页，包括废弃和换出。如果需要回收的页来自磁盘上的映像或者数据文件，而且页没有被修改过，则可以直接将其废弃。如果需要回收的页已经被修改过，则必须保留它的内容以便恢复。保存到映像文件中保存到交换设备中虚拟内存管理器必须仔细地处理页的交换。有效的交换方案应该保证所有进程的工作集（workingset）都在物理内存中。4.3.1虚拟内存抽象模型高速缓存（Caches）：1、BufferCache2、PageCache

3、SwapCache

4、HardwareCache：TLB(TranslationLookasideBuffers)4.3.1虚拟内存抽象模型虚拟空间变化

1、在进程创建时，从父进程拷贝虚拟地址空间。

2、在进程需要装入新的执行映像时，根据执行映像的定义，重建它的内存管理结构，从而重建进程虚拟地址空间。3、缺页异常处理程序会将页读入内存，修改页表。4、物理内存回收程序会将暂时不用的页从内存中换出，修改页表。5、在进程结束时，释放它在内存中的所有页和它的所有内存管理结构，从而释放它的虚拟地址空间。4.3.2虚拟内存拷贝进程创建时要拷贝父进程的虚拟地址空间。好处是父子进程可以完成同样的工作（如Server），坏处是代价太高。解决的方法是：1、vfork：父进程将自己的地址空间借给子进程然后睡眠，直到子进程重建自己的虚拟地址空间或exit退出。2、Copyonwrite：父子进程有自己独立的虚存管理结构和页目录、页表，且页表项的内容相同，但各页都被设置为只读。如果父或子进程要修改某页，系统会产生保护异常。异常处理程序识别出这种情况后，为修改页面的进程创建一个副本。如果没有修改页面的动作，父子进程就会一直共享同一个页面，不需要拷贝。

Linux同时支持上述两种改进。4.3.2虚拟内存拷贝（一）inlineintcopy_mm(intnr,unsignedlongclone_flags,structtask_struct*tsk)

1、如果标志clone_flags中设置了CLONE_VM，则将父进程内存结构的引用记数加1，返回0。2、否则，要拷贝内存结构：1）申请一个mm_struct结构mm，将父进程mm_struct结构的内容拷贝到mm：*mm=*current->mm;

2）调整mm的部分内容，如mmap、引用计数等。3）为新进程建立页目录：用户部分（前0x300）清0，内核部分（后0x100）从init_task的页目录中拷贝。4）将新页目录的地址写入新进程TSS段和mm->pgd中。5）将父进程的所有虚拟内存区域都拷贝到新进程中来：dup_mmap(mm);4.3.2虚拟内存拷贝（二）inlineintdup_mmap(structmm_struct*mm)1、顺序搜索父进程的vma链表，对其中的每个vma结构mpnt做如下处理：1）从内核内存管理器申请一个vm_area_struct结构tmp，并将mpnt的内容拷贝到tmp中：*tmp=*mpnt;2）调整tmp的某些域，如vm_flags、vm_mm等。3）如果mpnt是一个文件映射区域，则将vm_file的引用计数加1，并将tmp加入文件inode结构的vma链表中。4）copy_page_range(mm,current->mm,tmp)；拷贝mpnt对应的页目录、页表项：5）如果tmp的操作集中定义有open操作，则执行它。6）将tmp加入内存管理结构mm的vma队列中。2、如果新进程的内存区域总数大于32，则为其建立AVL树，以加快查找速度。4.3.2虚拟内存拷贝（三）intcopy_page_range(structmm_struct*dst,structmm_struct*src,structvm_area_struct*vma)按照vma的开始和终止地址，找出它们在新、老页目录中的位置。顺序拷贝各页目录项：1、拷贝目录项：1）如果老目录项为空，则不需要拷贝；2）如果老目录项有错，则将其清0；3）如果新目录项为空，则创建一个新页表。2、找到vma在新、老页表中的位置，顺序拷贝各页表项：1）如果老页表项为空，则不需要拷贝；2）如果老页表项所指的页不在内存，则拷贝它，而后修改该页在交换设备中的引用计数；3）如果老页表项为保留页，则拷贝；4）如果老页表项是copyonwrite页，则将老页表项改为只读，拷贝；5）其余情况，清除老页表项中的存取标志，拷贝。4.3.3虚拟内存重建当进程希望改变自己的行为时，它可以调用函数exec，根据新的执行映像重建自己的虚拟地址空间（映像文件的装入）。Linux采用内存映射机制装入执行映像。实际是根据执行映像文件建立一组vm_area_struct结构。1、系统调用exec完成执行映像的加载。2、系统调用old_mmap或sys_mmap可以为数据文件建立虚拟映射区域。函数do_mmap用于建立一个虚拟内存区域。4.3.3虚拟内存重建函数do_mmap建立的内存映射区域有两种：1、共享区域的页允许多个进程共享，它在内存中只有一份拷贝，进程可以直接修改共享映射区域的页。当需要将共享映射页从内存换出时，系统会将修改过的共享映射页直接写回到映射文件。2、私有区域的页是进程专有的，多个进程可以同时读它，但当某进程试图写时，系统会为写进程创建一个副本，进程对私有映射页的写操作都在自己的副本上进行。当要将私有映射页换出内存时，系统会将其写入交换设备，而不是映射文件。共享区域和私有区域的换出操作不同。4.3.3虚拟内存重建unsignedlongdo_mmap(structfile*file,unsignedlongaddr,unsignedlonglen,unsignedlongprot,unsignedlongflags,unsignedlongoff)do_mmap完成如下工作：1、检查各参数的合法性。2、找出映射区域的开始地址（可能不同于addr）。3、申请一个vm_area_struct结构，并根据参数填写它。4、如果file不空，则执行其上的mmap操作（设置操作集）。5、将vma插入mm_struct中，如果必要，建立vma的avl树。

6、如果file不空，则将vma插入到文件inode的i_mmap队列中。7、如果可能，合并两个相临的内存区域。8、累计进程虚拟内存的总量，返回映射区域的开始地址。4.3.4缺页处理当CPU访问到以下进程页时，会产生pagefault异常：1、不在内存中的进程页；2、违反了保护约定的进程页。操作系统处理pagefault异常的一般过程是：1、找到发生异常的虚拟地址。2、根据虚拟地址查找包含它的虚拟内存区域vma。如果找不到这样的vma，或访问方式确实违反了vma的保护约定，则向进程发送SIGSEGV信号。3、找到异常页对应的页表项。根据页表项的内容、虚拟内存区域vma的内容和异常错误代码，决定如何处理异常。处理的方法包括：从映射文件上读入页，从交换设备上读入页，复制Copyonwrite页，建立匿名页等。4.3.4缺页处理当缺页异常发生时，处理器在系统堆栈上压入一个错误代码（error_code）。错误代码的意义如下：代码位

意义

第0位P位0：引起异常的页不在内存1：引起异常的页在内存第1位W/R位0：引起异常的操作是读1：引起异常的操作是写第2位U/S位0：异常发生时，处理器在超级用户模式1：异常发生时，处理器在普通用户模式4.3.4缺页处理缺页处理函数是do_page_fault，定义如下：asmlinkagevoiddo_page_fault(structpt_regs*regs,unsignedlongerror_code)

它有两个参数：指向pt_regs结构的指针和error_code。缺页异常的处理过程如下：1、找到当前进程的内存管理结构mm。2、找到发生异常的地址address（CR2寄存器）。4.3.4缺页处理3、检查，看address是否在某vma中。找vm_end比address大的第一个vm_area_struct结构vma。结果如下：1）找不到，转bad_area。2）address在vma内，转good_area。3）address在vma之下但vma不能或无法向下扩展，转bad_area。4）address在vma之下且vma能向下扩展（用户堆栈），则将其向下扩展至少1页。转good_area。4.3.4缺页处理4、good_area：根据异常错误码决定处理方法：1）读一个不存在的页：如vma不允许读或执行，转bad_area；否则，转5。2）读一个存在的页：该页肯定不可读，因此出错，转bad_area。3）写一个不存在的页：如vma不允许写，转bad_area；否则，转5。4）写一个存在的页：如vma不允许写，转bad_area；否则，说明要写的是一个copyonwrite页，转5。5、正常缺页处理handle_mm_fault()。如成功，则正常返回；否则，转do_sigbus。4.3.4缺页处理6、bad_area：1）如果异常发生时，处理器在用户模式，则向当前进程发送一个SIGSEGV信号，告诉进程出现段或页违例，返回。通常情况下，该信号会导致进程自杀。2）如果是CPU缺陷引起的异常，则修正它，返回。7、do_sigbus：1）给进程发送一个SIGBUS信号；2）如果发生异常时，处理器在用户态，则返回；否则，转no_context。8、no_context：1）内核错误。如果能修复则修复，返回。2）如果是对MMU写保护功能的测试，则设置参数，返回。3）坏页且无法修复。显示信息，终止整个系统的运行。4.3.4缺页处理函数handle_mm_fault()的处理如下：1、找出address对应的页目录项。如果页目录项有错（保护标志错），则将其标记为BAD_PAGETABLE，此次缺页处理失败，返回0。2、找出address对应的页表项：1）如果页表不存在（页目录项的值为0），则创建一个新的页表。2）根据address的第12到21位找到页表项。调用函数handle_pte_fault()处理单个页表项（单个虚拟页）的异常。如果成功，返回1；否则，返回0。4.3.4缺页处理函数handle_pte_fault()的处理过程如下：分析页表项的内容，找出页的位置。有如下情况：1、页不在内存（p位为0），则：1）如页表项为0，说明页在映射文件中。从映射文件中读入它：如果vma上没有操作集，或其操作集中没有nopage操作，则vma是匿名区域（不对应任何文件）。处理匿名页：do_anonymous_page()。调用vma操作集中的nopage操作，从映射文件或关系内存中读入页：filemap_nopage()、shm_nopage()。2）如页表项不为0，说明它在交换设备上。从交换设备上读入页：do_swap_page()。4.3.4缺页处理2、页在内存，则：1）如果发生异常的动作是写，且vma允许写而页不允许写，则该页是一个copyonwrite页。为该页创建一个拷贝：

do_wp_page(tsk,vma,address,pte)；2）如果发生异常的动作是写，且vma和页都允许写，则将页表项上脏页位设置为1、填入页表、刷新TLB。3）如果发生异常的动作是读，则将页表项上存取位置1，填入页表，刷新TLB表。4.3.4缺页处理归结起来，对缺页的处理过程如下：do_page_fault

handle_mm_fault handle_pte_faultdo_swap_page do_no_page do_wp_pagedo_anonymous_page

filemap_nopage shm_nopage 对缺页处理的方法有五种： 处理匿名页：do_anonymous_page

处理映射文件页：filemap_nopage

处理共享内存页：shm_nopage 处理交换设备页：do_swap_page 处理Copyonwrite页：do_wp_page4.3.4缺页处理intdo_anonymous_page(structtask_struct*tsk,structvm_area_struct*vma,pte_t*page_table,intwrite_access)1、匿名页都映射到empty_zero_page，该页不能写：1）如果引起异常的动作是读，则根据empty_zero_page的地址和vma的保护信息创建一个页表项，清除其中的_PAGE_RW标志，将该页设置为copyonwrite页。2）如果引起异常的动作是写，则：向物理内存管理器申请一个新页并将其清0。用新页的地址和vma的保护信息创建一个页表项，并在其中设置上_PAGE_DIRTY和_PAGE_RW标志。2、将创建好的页表项填入页表。

3、成功，返回1。4.3.4缺页处理unsignedlongfilemap_nopage(structvm_area_struct*area, unsignedlongaddress,intno_share)1、根据area找到文件，根据address算出页在文件中的偏移量offset。2、根据文件的inode和offset查找页缓存：1）页不在缓存中：申请物理页，将其加入页缓存，调用inode上的readpage操作读入该页的内容。此处可能一次读入多页。2）页在缓存但正被锁定（正在做I/O）：等待。3）页在缓存中但不是最新的：调用inode上的readpage操作读入该页。4）页在缓存中且是最新的：如果area是共享的，则可以直接使用它。返回页的开始地址。如果area是私有的，但引起异常的动作是读，则可以直接使用它（设为写保护）。返回该页的开始地址。如果area是私有的，且引起异常的动作是写，则创建页的一个副本。返回副本的开始地址。

5）如果上述任何一处出错，则返回0，表示失败。4.3.4缺页处理共享内存是进程间的一种通信机制，它允许多个进程通过共享内存页互相通信。由于一块共享内存对应的物理页可以出现在多个进程的页表中，因此对共享内存缺页的处理有些特别的地方。因为处理共享内存的缺页需要了解共享内存机制，因此，将把对函数shm_nopage的讨论推迟到第六章。4.3.4缺页处理intdo_swap_page(structtask_struct*tsk,structvm_area_struct*vma, unsignedlongaddress,pte_t*page_table,pte_tentry,intwrite_access)1、如果vma中没有定义swapin操作，则调用缺省的换入函数： swap_in(tsk,vma,page_table,pte_val(entry),write_access);目前的所有虚拟内存区域中都没有定义换入函数。swap_in的定义在交换一节中讨论。2、返回1，表示成功。4.3.4缺页处理intdo_wp_page(structtask_struct*tsk,structvm_area_struct*vma, unsignedlongaddress,pte_t*page_table)1、如果页本来就不在内存或已经允许写，则返回1。2、如果老物理页不存在，则向进程发送SIGKILL信号，错误返回0。3、下列情况不需要拷贝物理页：1）如果老物理页的唯一一个用户是当前进程；2）如果老物理页只有两个用户（当前进程和交换缓存），而且没有别的进程引用该交换页，则将其从交换缓存中删除。 将页置成可写、脏页，刷新页表，返回1。4、如果页有多个用户，则需要拷贝：1）申请一个物理页，将老页的内容拷贝到新页中。2）根据新页的物理地址和vma的保护权限构造一个页表项，在其中增加可写、脏页标志，将其填入页表中。3）释放对老页的引用，刷新TLB表，成功返回1。4.3.7页缓存从文件中读入页需要经过页缓存。使用页缓存（pagecache）的目的是：减少读文件的次数，加快对文件的访问速度。从文件系统中读入的每一页（缺页时读入的页和用read操作读入的页）都被缓存在页缓存中。页缓存中的页包括共享映射页和私有映射页的主本，私有映射页的副本不在页缓存中。页缓存是一个Hash表。structpage*page_hash_table[4096];

以VFSinode和文件中的偏移量为索引，来确定一个文件页在页缓存中的位置。4.3.7页缓存page_hash_tablepagepagepagepagepage……Page结构中的next_hash和pprev_hash指针用于将物理页加入页缓存4.3.7页缓存1、当需要从文件中读入页时，系统首先根据文件的VFSinode和页在文件中的偏移量查页缓存。如果需要的页在页缓存中，而且其内容是最新的，就可以立刻使用它，从而可以避免一次I/O操作。只有当要读入的页不在页缓存或虽在页缓存但内容不是最新的时，才需要将其从文件中读入。新读入的页也被加入页缓存。通常情况下，Linux会启动超前读，即一次将多个文件页读入到内存，并加入到页缓存。4.3.7页缓存2、当需要回收物理内存时，回收程序会搜索页缓存，找无进程引用的页（引用计数为1）：如页是干净的，可以直接将其废弃、回收。如页是脏的，可以先将其写回文件、再回收。共享映射页的回收是一种典型的情况。vm_endvm_startvm_flagsvm_opsvm_offsetvm_filevm_nextvm_area_struct虚拟内存文件4.3.5共享映射页的回收共享映射区域中的页是和映射文件直接对应的，其内容来源于文件，进程可以直接修改共享映射页。映射文件是共享映射页的备份。当需要回收共享映射页时：如页未修改过，可以直接将其收回；如页被修改过（脏的），可以先将其写回映射文件，而后再将其收回。在两种情况下，共享映射页会写回映射文件：1、物理内存回收程序在回收被修改过（脏页）的共享映射页时；2、内核守护进程kpiod活动时。4.3.5共享映射页的回收满足以下条件的共享映射页需要在回收前写出（淘汰）：1、在进程的虚拟地址空间中，即该页必须出现在进程的某个虚拟内存区域vma中。2、在内存，即它的页表项的存在位为1。3、最近未被存取过，即它的页表项中的A位为0。4、不是内核保留页。5、页上没有加锁，即在该页上没有正在进行的I/O操作。6、不在交换缓存中。7、是脏页（不脏的页可以直接废弃，不需要写出）。8、是共享映射页。4.3.5共享映射页的回收回收程序try_to_swap_out对共享映射页做如下工作：1、找到页表项和page结构。如果页表项的A位为1，则将其清0，将page中的PG_referenced置1。返回。2、将共享映射页在进程页表中的页表项清0。3、使共享映射页在TLB中失效。4、vma->vm_mm->rss--; //驻留内存的页数5、调用文件操作集上的写操作（vma->vm_file->f_op->write()），将page的内容写到文件的offset处。6、释放物理页：__free_page(page_map);4.3.5共享映射页的回收共享映射页同时出现在页缓存和进程页表中，因此该物理页的引用计数至少是2。函数__free_page()仅仅将它的引用计数减1，并不能真正释放它，物理页仍然在页缓存中。共享映射页页表物理内存页缓存4.3.5共享映射页的回收如果函数__free_page()执行后，物理页的引用计数大于1，说明还有别的进程引用它，该页不会被回收。如果物理页的引用计数为1，则在下一次回收物理内存时，函数shrink_mmap()会检查它的PG_referenced标志：如该标志为1，则将其清0，返回；否则，将它从页缓存中删除，从而真正将其回收。如果在页被真正回收之前，又有进程（包括释放该共享映射页的进程）访问了该页，则缺页处理程序会直接从页缓存中查到该页，从而又会将其加入到进程的页表，其引用计数就又会大于1，这样以来，物理内存回收程序就不会真正将其回收。4.3.5共享映射页的回收这就是Linux采用的二次机会淘汰算法，是一种“lazy”的处理方法。将共享页从进程的虚拟地址空间写出，但不立刻将其从页缓存中释放，有下列好处：1、如果该页很快又被访问，可以避免一次读盘操作，从而可以提高系统的性能，也可以减少因淘汰失误而造成的影响。2、如果到下次回收物理内存时，该页仍没有被访问，则根据局部访问原则，该页很快被访问的可能性就较小，因此可以放心地将其回收。4.3.6交换如果需要回收的页是私有映射页的副本，则不应该将它直接写回映射文件，只能将其写到外存的某个地方暂存。如果要回收的页不是内存映射页，则该页在磁盘上根本就没有对应的文件，因此只能将其写到外存的某个地方暂存。用于暂存换出页面的文件叫交换文件，用于暂存换出页面的设备叫交换设备。以下统称为交换设备。4.3.6交换在安装Linux系统时，一般都要求创建交换设备。交换设备可能是单独的块设备，也可能是磁盘设备的一个分区，当然也可以是独立的文件。为了提高性能，系统中可以建立多个交换设备，而且可以将这些交换设备分布在不同的块设备（如磁盘）上。交换设备上没有建立文件系统，但它的第0页上写有特殊的控制信息。如下：4.3.6交换第0页是下面形式的结构：unionswap_header{ struct{ charreserved[PAGE_SIZE-10]; //位图 charmagic[10]; //魔数 }magic; //老版本 struct{ char boo