Linux桌面环境下内存去重技术的研究与实现(第二章)

Linux桌面环境下内存去重技术的研究与实现

在这里可以下载原稿 www.ykyi.net/upload/Research_and_Implementation_of_Memory_Deduplication_in_the_Linux_Desktop_Environment.pdf

第二章 相关理论与技术

2.1 内存管理

内存管理是操作系统内核中极为重要的部分,它涉及物理地址、虚拟地址、分段、分页等诸多概念。

2.1.1 内存地址

程序使用地址来访问内存单元。对于x86架构的中央处理器,使用逻辑地址,虚拟地址,物理地址三种不同的地址[15]

逻辑地址包括段和偏移地址两部分,它们共同用来指定机器指令或者操作数在内存中的位置。逻辑地址对应下文提到的分段式内存管理。

虚拟地址也被称作线性地址,它表示一个寻址空间。在Linux操作系统中,使用一个无符号长整型存储虚拟地址。如果是针对32位x86处理器的内核,这是一个32位的无符号长整型,可以寻址至多232,即4GB空间。而Linux在x86_64处理器上,一个无符号长整型有64位,但实际上只使用了48位,即可寻址到248 ,即256TB的内存空间。引入虚拟地址使得用户空间的进程都独自拥有一个地址空间,方便操作系统在硬件的协助下隔离进程访问内存的操作,从而实现更高的安全性和便捷性。在32位处理器架构下,4G虚拟地址空间划分成两部分,高端的1G空间被称之为内核空间,低端的3G空间称之为用户空间。内核的代码和数据存在内核空间,用户空间的进程通过系统调用陷入内核空间执行内核空间的代码。对于64位处理器,虚拟地址同样分为内核空间和用户空间,只是针对64位处理器的内核拥有大得多的寻址范围,对内核空间和用户空间的地址划分有多种实现。

物理地址被中央处理器用来寻址内存芯片上的实际的物理单元。它对应了送往处理器的针脚上的高低电平信号。

       Linux中的内存管理单元 (Memory Management Unit, MMU)在硬件电路的帮助下把逻辑地址译成线性地址;而另一个硬件电路则帮助把线性地址翻译成物理地址。

2.1.2 段页式内存管理

内存分段是由80×86处理器引入的概念,它鼓励程序员在设计程序时把程序使用的内存按照逻辑上的意义相关性分成若干个部分,比如有些段存放全局数据,有些段存放程序代码[16]

内存管理单元的分页单元协助把虚拟地址译为物理地址,为了提高翻译的效率,虚拟地址被按照固定长度切分成一个个小单元,它们则被称之为页面。页面可以看成是MMU管理内存的最小单位。

      分段和分页都用来划分内存,在某种程度上,它们的功能有一定重合。实际上,Linux内核的内存管理机制倾向于使用分页技术。Linux进程运行在用户空间时使用的标志代码段的代码段选择子(segmentation selector)和数据段选择子是相等的;进程运行在内核空间时使用的代码段选择子和数据段选择子也是相等的。而且这四个段选择子的段基址都设置为0。这意味着在Linux操作系统中,无论寻址数据和还是寻址指令,无论在用户空间还是内核空间,逻辑地址的段基址部分为0,偏移地址部分刚好等于虚拟地址。

在Linux所支持的大多数硬件平台上,默认的页面大小是4K。但Linux同时也支持大于4K的页面的内存管理。运行在用户空间的代码可以使用glibc库中的getpagesize()函数得到当前使用的页面大小。本论文只针对在x86_64架构上页面大小是4K的Linux内核。实际上从内核2.6.38开始,内核中开始支持透明巨页(Transparent Huge Page)[17],内核中有些页面的大小实际上是2M,但这不影响按照4K的页面大小展开讨论。

Linux使用分级页表的方式把虚拟地址映射到页面。在32位处理器上使用二级页表,在x86_64架构的处理器上则使用四级页表。

 

 

图2-1 四级页表

 

       如图2-1所示,以针对x86_64架构处理器的Linux内核为例,64位虚拟地址的高16位不被使用,低48位被平均分为5段,offset段占12位,其它四个段各占9位。这个划分在源代码文件arch/x86/include/asm/pgtable_64_types.h中定义。cr3寄存器存储了页全局目录的物理地址。在把虚拟地址翻译到物理地址的过程中,MMU先从cr3寄存器中取出全局目录的物理地址,再加上GLOBALDIR段算出的偏移量,从而在页全局目录中得到页上级目录的物理地址。与此类似,从页上级目录中得到页中间目录的地址,然后得到页表的地址,再得到页面的地址,最后的OFFSET字段则定位到页面中的一个字节。至此,虚拟地址被翻译到了物理地址。

页全局目录,页上级目录,页中间目录,以及页表中的每一项都由相同的数据结构表示。它记载了一些重要的信息,与本论文相关的信息有:该项指向的下一级表或者页面是否存在的标志,如果访问时不存在则产生缺页中断,由do_page_fault函数负责把页面调入内存[18];下一级表或页面的物理地址;下一级表或页面是否可读可写的标志,利用该标志位可以写保护一个页面。

Linux内核用一个struct page结构体描述一个页面的信息。这个结构体定义在include/linux/mm_types.h文件中[19]。图2-2列出这个结构体中与本论文直接相关的字段。

 

图2-2 struct page的部分字段

 

其中的flags字段存储了页面的状态信息,例如:表示页面刚被写了数据的脏位;该页面是否被锁定在内存中不充许置换到交换分区的标志。_count字段和_mapcount字段都是引用计数,它们用来共同维护page页面的生命期。_mapcount表示一个页面拥有多少页表项指向它,_count被称为page的使用计数,所有的_mapcount计数只相当于_count计数中的一次计数。如果内核代码中某执行序列在访问某个页面时需要确保该页面存在,则在访问前给_count计数加一,访问结束后_count计数减一。当_count计数减到负数时表示没有任何内核需要使用该页面,则表示该页面没被使用。内核代码不应该直接访问_count计数,而应该使用page_count函数。该函数用一个struct page的指针做为参数,当该页空闲时函数返回0,否则返回一个正数表示参数指向的页面正被使用。当页面被页高速缓冲使用时,mapping域指向一个address_space对象,该对象与Linux文件系统中的文件是一对一映射的关系,描述了一个文件分配到的物理页面及相关数据结构。如果页面并不被页高速缓冲使用时,mapping则有其它的意义,比如mapping字段的最低位记载这是否是一个匿名页面。virtual字段是映射到该页面的内核空间的虚拟地址,如果该页面是属于高端内存区域则virtual字段为NULL。对于x86_64架构上的Linux内核,已经没有高端内存,因此该字段不会为NULL。

2.1.3 内核中的巨页

现代处理器的内存管理单元几乎都能处理除4KB大小外的多种页面尺寸。然而,Linux内核在几乎所以平台上的实现都选用最小的页面大小,即4KB,比4KB更大的页面,都被称之为巨页(huge page)。在某些工作环境下,巨页可以给操作系统带来性能上的提高。巨页能提高操作系统的性能主要是因为两点。第一,使用巨页可以减少发生页面出错处理的频率,因为在每次页面出错处理时内核调入比使用小页面更多的内存。第二,使用巨页减少翻译虚拟地址的时间。在x86_64加构的处理器上,从虚拟地址翻译到物理地理需要依次访问四级页表,非常耗时。而使用巨页可以减少页表的级数。实际上更大的性能提高源自使用巨页后提高了旁路转换缓冲区(Translation Lookaside Buffer,TLB)的命中效率[20]

在内核2.6.38版本之前,唯一使用巨页的方式是通过非常复杂的hugetlbfs文件系统。应用程序开发者和系统管理员都需要注意一些特别事项才能够开启巨页功能。因此只有极少数真正需要巨页带来性能提高的用户,如专用数据库系统,才使用巨页。

情况从内核版本2.6.38以后发生了变化,一个被称之为透明巨页的功能被合并进了内核主干代码。之前内核在VMA(Virtual Memory Area,虚拟内存区域)中的所有页面大小都是一样大的,而加入透明巨页后,VMA中的页面的大小可能不只一种。透明巨页的实现代码改写了页面出错处理函数,当一个出错发生时,内核尽力分配一个巨页,如果成功的话,其它相应的在巨页地址范围内的小页面就会被释放,巨页被插入到VMA中。如果不能分配到一个巨页,则仍然按照以前的方式分配一个小页面。当巨页需要被置换到交换分区时,透明巨页机制简单地把巨页切割成小页面,其它逻辑和处理小页面时一样。实际上不仅在置换到交换分区时需要切割巨页,很多其它的操作,如mprotect()和mlock()页面时也需要。本论文将详述的KSM在合并页面时同样需要把巨页切割成小页面。

透明巨页这种轻便地利用巨页的方式使得很多内核代码并没有感知到巨页的存在,对于应用程序则更没有感知到巨页,因此被称之为透明巨页。

2.1.4 内存描述符

Linux内核使用一个叫内存描述符(Memory Descriptor)的结构体描述每一个进程的地址空间[21]。这个结构体包括了所有和进程地址空间相关的信息。内存描述符和struct page一样在文件include/linux/mm_types.h中定义。图2-3列出这个结构体中与本论文直接相关的字段。

 

 

图2-3 struct mm_struct的部分字段

 

其中,mmap字段是用来实现一个链表。这个链表链接了属于这个内存描述符的所有vm_area_struct结构体。vm_area_struct结构体描述了一个内存区域。由于属于一个内存描述符的内存区域可能非常多,为了加快内存区域的查找以及添加删除等操作的速度,内核用mm_rb表示一棵链接了所有内存区域的红黑树。红黑树是一种二叉树,它被广泛地应用在Linux内核代码中。mmap和mm_rb是用两种不同的数据结构表示同一批数据。mm_users和mm_count是内存描述符的引用计数,它的实现原理和struct page的引用计数的原理一样。每一个进程如果拥有一个内存描述符,则会增加mm_users的计数,所有mm_users的计数只相当于mm_count的一个计数。比如n个Linux线程共享同一个内存描述符,那么对应的内存描述符的mm_users计数则为n,而mm_count则可能只是1。如果有内核执行序列想要访问一个内存描述符,则该执行序列先增加mm_count的计数,使用结束后减少mm_count的计数。一但mm_count减为0,表示该内存描述符没有任何引用,则它会被内核销毁。mmap_sem是一个读写锁,凡是需要操作内存描述符中的内存区域时,则需要先得到相应的读锁或者写锁,使用结束后释放该锁。mm_list字段是一个循环双链表。它链接了系统中所有的内存描述符。flags字段定义了内存描述符的标志,这些标志标记了内存描述符的一些状态和属性,内核代码需要使用原子操作访问该字段。

2.1.5 虚拟内存区域

同样被定义在inlude/linux/mm_types.h中的结构体vm_area_struct用来描述一个内存区域。在Linux内核中,内存区域经常被称之为虚拟内存区域(Virtual Memory Areas,VMA)。VMA描述的内存区域是一个地址空间中的地址连续的部分。而且该部分拥有一些特定的属性,比如访问权限和相关联的操作等。不同的VMA可以用来描述不同的内存区域。比如,映射到内存的文件,用户空间的栈,特别是本论文重点关注的匿名内存区域(Anonymous VMA)。下面讨论本论文关心的vm_area_struct的一些重要字段,这些字段如图2-4所示。

 

图2-4 struct vm_area_struct的部分字段

 

vm_mm字段指向该VMA属于的内存描述符。vm_start和vm_end字段表示该VMA描述的内存区域的起始和终点虚拟地址,但不包括vm_end指向的地址,即vm_end是虚拟内存区域的最后一个有效字节的后一个字节。vm_next和vm_rb分别把内存描述符拥有的内存区域用链表,和红黑树链接起来。vm_flags表示内存区域的属性。anon_vma与内核的页面回收机制回收匿名页时用到的页面反射表有关。vm_file是该内存区域对应的文件,如果内存区域是匿名的,则该字段被置为NULL。

2.1.6 Slab层

频繁地申请和回收同一类型的数据结构是内核中极为常见的操作。为了提高申请和回收某种特定数据结构的效率。Linux内核中引入了slab层的概念,通过slab层来管理某种数据结构的频繁申请和回收[22]

Slab层把不同的数据结构划分到不同的高速缓存(cache)中,每个缓存都用来维护某种数据结构的申请的回收。比如,从维护进程描述符的缓存中申请进程描述符时,缓存把一个标记为可用的进程描述符返回给调用者,同时把该描述符标记为已用;释放进程描述符则使得这个进程描述符在存放它的缓存中又被标记为可用。

      每个缓存被划分为好几个slab,这就是这个子系统被称之为slab层的原因。每个slab是一页或几页连续的内存。缓存维护的某种数据结构,称之为对象,就全部放在slab中。每个slab处于满,部分满或空三种状态。当slab 处于满状态时,表示该slab中维护的对象已经全部被分配。当slab处于空状态时,和半满状态时,slab可以有空闲的对象可供分配。当内核需要申请一个新对象时,就向对应的缓存申请。缓存找到自己维护的slab,从slab中拿出预先分配好的空闲对象返回给申请者。当内核使用完了该对象,这个对象就被缓存回收,一般情况下并不真正释放,而是在对应的slab上做空闲标记。缓存通过灵活的策略维护slab的大小和数量。使用slab,能够加速常用数据结构的分配和释放,并减少分配内存产生的碎片。

2.2 内核开发

      操作系统内核的开发和普通用户空间的程序开发有非常大的差异。本节将介绍理解KSM和在内核空间进行开发所需熟知的一些内容。

2.2.1 Linux内核简介

Linux由1991诞生开始就受到开源社区的热烈欢迎,并且一直处于极为活跃的持续开发状态。Linux的代码以GNU计划倡导的GPL协议自由分发,全世界的操作系统爱好者,硬件驱动编写者都非常活跃地为Linux贡献代码。Linux的开发如此成功,以至GNU计划中自己的操作系统内核GNU Hurd都未得到足够多的关注,Linux成为事实上GNU计划的操作系统内核。

Linux内核沿用Unix的单内核设计。单内核设计把整个内核设计成运行在同一个地址空间的一个“大”进程。所有的内核执行序列存在于同一个地址空间中,并在同一个地址空间内运行。因此,内核的不同执行序列之间的通信是极为快速的,基本不需要额外的开销,但由此也带来内核代码的复杂度过高的问题。较之单内核,另一个设计操作系统的思路是微内核,它的很多设计理念和单内核的设计相反,如windows XP, Vista 还有 windows 7等等。Linux内核在发展过程中引入了内核模块的概念,这使得Linux内核既保持了单内核设计性能快速的特点,又使得内核代码相对纯粹的单内核简洁和易于维护。

本论文选定的内核版本是2013年2月发布的3.0.66稳定版,在它的基础上研究开发。

2.2.2 内核线程

Linux的内核线程实际上是只存在于内核空间的一个进程。内核通常创建内核线程让它在后台周期性的处理一些事务。内核线程和普通进程一样可调度,可被抢先。他们的最显著的区别是内核线程的进程描述结构体task_struct的mm字段为NULL。而一般进程的进程描述结构体的mm字段指向该进程的地址空间。因为内核线程永远只运行在内核态,永远不必切换至用户空间,并且所有用户态进程的地址空间的内核虚拟地址部分都是一样的,所以当处理器调度到内核进程时,内核进程可以随便使用某个用户态进程的地址空间的内核虚拟地址部分。Linux内核线程的作法是借用上一个普通用户态进程的用户空间[23]

内核线程由内核API函数kthread_create()创建,也可由kthread_run()创建。他们的区别是前者创建的是一个处于非运行状态的内核线程,需要使用wake_up_process()把它转换为可运行状态;而kthread_run()创建的内核线程立即处于可运行状态,随时可能被调度而获得运行的机会。内核线程开始后会一直运行,直到它显式地调用do_exit()或者其它内核代码调用kthread_stop()。kthread_stop()函数需要传入先前创建内核线程函数返回的task_struct作为参数。该函数在调用后会一直阻塞,直到等待的内核线程完全退出了才返回。

2.2.3 内核的同步机制

竞争条件指的是程序设计中的一种缺陷,这种缺陷使得程序的输出会因为不受控制的事件出现的顺序或发生时间而发生改变。Linux内核提供了一套同步方法,正确地使用同步方法可以消除竞争条件[24]

atomic_t是内核中的特殊整型数,应用在该整型数上的方法使得对该整数的操作是原子操作,从而对该整数的操作不会被其它执行序列中断。如atomic_inc()和atomic_dec()分别是原子地给一个整型数加一或减一。

Linux内核中最常用的锁是自旋锁。对于一个自旋锁,内核在任何时候只能有一个执行序列持有该锁。如果在该自旋锁被其它执行序列持有时,当前执行序列也申请持有该锁,则这个执行序列就会使得处理器一直忙等该锁被持有者释放。为遵循迅速占有,迅速释放的原则,一个内核执行序列一但持有某自旋锁,则内核在该内核序列运行的当前处理器上被禁止抢先。另外,持有自旋锁的内核执行序列应该运行完简短的代码后迅速释放该自旋锁,而不应该在释放持有的自旋锁前执行可能造成睡眠的代码,也不能显式地调用放弃处理器而申请调度其它进程的代码,因为这样会使得其它申请该自旋锁的执行序列等待非常长的时间而大大损害了整个系统的性能。自旋锁的基本有法是:用DEFINE_SPINLOCK在编译期定义一个未被占用的自旋锁变量,用函数spin_lock()得到自旋锁,用spin_unlock()函数释放自旋锁。与普通自旋锁类似的还有读写自旋锁。当对自旋锁保护的资源的访问多数是读访问,少部分是写访问时,使用读写自旋锁比使用普通自旋锁的效率更高。

Linux内核中另一种常见的锁是信号量。信号量只能在进程上下文中才能使用,当一个进程或内核线程尝试获取一个不可用的信号量时,该进程或者该内核线程会被置于一个等待队列中,然后进入睡眠状态,处理器转而执行其它的代码。当该信号量被某持有者释放,信号量变为可用时,等待队队中的一个进程或内核线程会被唤醒而获得该信号量。因为未能立即获得锁时会使得执行序列进入睡眠,所以在不能被调度的中断上下文中不能使用信号量。同样因为未能立即获得信号量则被置于睡眠状态的原因,信号量非常适合需要长时间持有锁的情况。信号量的另一个显著的特点是它充许同时有若干个持有者,这个数量在声明信号量时指点。但大多数情况下信号量被设置为只能有一个持有者,这种情况下,信号量被称为二值信号量或者互斥锁。互斥锁常见的使用方法是:用DECLARE_MUTEX宏在编译期定义一个未被占用的互斥锁变量,或者用init_MUTEX在运行时初始化互斥锁,用down()函数获得信号量,用up()函数释放信号量。与读写自旋锁类似,Linux内核也有针对读多写少的情况做优化的读写信号量,它的特征和普通信号量基本相同。

2.2.4 内核的调试技术

调试内核代码是内核开发技术中非常困难的一部分,这是因为内核代码运行在软件栈的最底层,不像用户空间的进程可以轻易地被调试器跟踪。另外,因为很多情况下的内核错误会让整个操作系统崩溃或者运行在不可预测的不稳定状态,让开发者几乎没有机会收集到足够多的错误是如何出现的线索,所以内核错误在很多情况下也不能轻易地被重现。

       用printk()函数打印出程序的相关信息到日志文件或控制台是最古老也最常用且有效的调试方法[25]。printk()函数与用户空间的printf()库函数相似,其中的差别之一是printk()函数可以让用户指定打印信息的级别。目前printk()函数有八个信息级别,它们被定义在linux/kernel.h头文件中。级别的数字越小则表示级别越高。基于信息级别,内核可能把信息打印到当前的控制台。它可能是一个字符终端,可能是一个串口连接的设备,也可能是一个并口打印机。内核中的整型变量console_loglevel表示能被发往控制台的信息的最小级别。可以用sys_syslog系统调用改变它的值,用可以通过写文件/proc/sys/kernel/printk改变它。所有信息,包括信息级别的值大于console_loglevel而没能被发往控制台的信息都被添加到文件/var/log/messages的末尾。

除了最为常用的打印函数printk()是调试内核必备之外。内核开发者使用的内核在编译前通常都会打开一些方便调试的内核选项[26]。比如CONFIG_KALLSYMS选项使得内核代码的符号信息被编译进内核,这样当内核崩溃时,系统会用符号打印出出错时栈回溯信息,否则只有二进制的地址信息。还有一些特定的编译选项帮助开发者排查特定的错误,比如CONFIG_DEBUG_SLAB可以帮助排查忘记初始化内存和内存越界访问的错误;而CONFIG_DEBUG_SPINLOCK 可以排查非法使用自旋锁的错误。

KGDB是常用的调试Linux内核的调试器。最开始,它只是作为一个内核补丁发布,从内核2.6.26开始,它被合并到了内核的主干代码。用KGDB调试时,需要两台用串口连接的Linux机器,被调试的机器运行KGDB,另一台(调试机)则运行普通的GDB。GDB远程协议被用于它们之间的通讯[27]。配置KGDB比较麻烦,但目前桌面虚拟化技术非常成熟,开发者可以用两台Linux虚拟机使用KGDB,用虚拟的串口硬件连接两台机器。仅管如此,使用内核调试器还是相当之麻烦。被调试的内核在编译后输出的vmlinux文件是未压缩的linux内核,需要被拷贝到调试机;对应的源代码需要被拷贝到调试机调试时的当前目录;另外,调试时并不能在所有代码语句设置断点,因为内核代码的编译依赖于GCC的编译优化选项,开启相应的优化选项内核代码才能通过编译,而很多语句的变量经过GCC优化后会被去掉,调试者从源代码上看到的执行路径经常并非内核实际的执行路径。

2.3 本章小结

    本章首先介绍了Linux内核的内存管理的一些理论和技术,然后介绍了进行内核开发所必须掌握的基础知识。本章的内容是理解以后章节的基础。

Linux桌面环境下内存去重技术的研究与实现(第一章)

Linux桌面环境下内存去重技术的研究与实现

在这里可以下载原稿 https://as.goodas.gold/Research_and_Implementation_of_Memory_Deduplication_in_the_Linux_Desktop_Environment.pdf

第一章 绪论

1.1 课题背景

内存是操作系统中最为重要的资源之一。为了最有效地利用好有限的内存资源,现代操作系统使用了很多技术以节省内存的使用。在Linux程序的内存布局中,代码段具有只读属性,永远是共享的。具体地说,即使一个程序被实例化了多个进程,但是在物理内存中对于该程序的代码只有一份拷贝,同一个程序的不同进程之间共享这份拷贝。而且,所有共享库(Windows下被称之为动态链接库)的代码段在物理内存中也只有一份拷贝[1],所有加载了该共享库的进程虽然把共享库加载到了不同的虚拟地址中,但实际上都映射到相同的物理地址上以实现对共享库代码区的共享。除了共享只读的代码区外,可写的页面也可能在进程之间被共享,Linux在创建进程时的fork操作使用写时拷贝技术在父子进程之间共享内存。当父进程调用fork()函数后,所有的可写页面转成写时拷贝页面。只要父子进程都不写入某页面,则该页面一直被共享。

近年来,Linux操作系统中出现了一种新的节省内存的技术,它的出现源于云计算的发展。云计算能够通过互联网按需分发计算机的软硬件资源,被称之为IT产业的又一次革命[2]。虚拟机技术是云计算的基础,Xen和KVM(Kernel Virtual Machine,内核虚拟机)是开源社区最流行的两种虚拟化技术[3]。通过运用虚拟化技术,越来越多的Linux主机上同时运行着多个虚拟机,而虚拟机使用了相同的操作系统,操作系统中运行着相同的大型程序,如数据库服务器,邮件服务器,Web服务器等。在运行多个虚拟机的环境下,人们发现虚拟机之间存在着大量的相同内存页面,但Linux主机没有办法共享这些内存页面。为了解决虚拟机之间大量重复内存的问题,Linux社区诞生了KSM(Kernel Samepage Merging,内核相同页面合并)技术。KSM技术通过扫描内存区域,找到相同的内存页面,并把它们合并。该技术使得运行虚拟机的主机使用的内存明显下降,从而让同样的Linux主机在使用KSM技术后能运行更多的虚拟机。

KSM技术虽然是为基于KVM技术的虚拟机设计,但也能运用到普通的桌面应用程序。随着软硬件技术的不断进步,Linux桌面应用程序占用的内存也越来越多。普通的Linux桌面应用程序中存在多少重复页面,重复页面的分布有些什么特点,把KSM技术运用在桌面应用程序上存在什么问题,这些是本论文将要探讨的内容。针对桌面应用程序的重复内存,本文在KSM的基础上开发了KSM+,能方便有效地合并桌面应用程序的重复内存。

1.2 国内外研究现状

对于传统的节约内存技术,如共享只读代码区,fork的写时拷贝技术。这些技术非常成熟,现代操作系统中已经普通采用。

另外,文献[4]研究了一种比较特殊的节省内存技术。它针对的是科学计算中的特殊程序,通过用注释驱动的工具把源代码转译到更高效的代码,于是编译出节省内存的程序。

近年来研究较多的是基于合并相同内存页面的内存去重技术:通过查找系统中的相同内存页面,把这些页面合并从而节省系统内存。但国内外的研究基本集中在运行虚拟机的场景中。如VMware公司较早进行了虚拟机内存去重技术的研究工作,文献[5]研究了VMware公司的Hypervisor(虚拟机管理器)使用的基于合并相同内容内存页面的去重技术,以减少虚拟机之间的内存冗余。文献[6]详细论述了此类技术对于基于Xen的虚拟机的实现。Linux社区的类似技术称之为KSM。文献[7]以实证研究的方式通过大量实验研究了KSM用于合并虚拟机之间冗余内存的性能。文献[8]研究的是在数据中心中如何提高在虚拟机之间合并相同内存的效率。它实现了通过把虚拟机在各物理机中动态迁移到最适合的位置从而提高合并效率。文献[9]使用KSM技术解决了主机和虚拟机都需要维护自己的缓存的问题,提高了缓存的效率。KSM技术并不是总能高效地去除虚拟机之间的冗余内存,也存在一些问题。内存地址的ASLR(Address Space Layout Randomization,空间布局随机化技术)是为了提高程序安全性的一种技术。该技术提高了程序的安全性,却影响了页面对齐,从而影响了KSM的合并效率[10]。另外,KSM的运用也暴露了安全问题。运行在某台虚拟机上的程序可以通过构造特定的页面尝试让主机的KSM合并它,再计算写该页面所用的时间。因为写被KSM合并的页面的时候会发生写时拷贝,所以这个时间会比正常情况下延迟。通过利用这个时间差,运行在一台虚拟机上的程序可能会发现其它虚拟机上运行的程序[11],甚至让虚拟机之间秘密通信[12]

KSM技术应用在非虚拟机的场景下的研究则比较少。欧洲核子研究组织(CERN)的核子实验模拟程序产生海量的数据,并且并行工作的科学程序同时载入这些数据,使得内存中有大量的相同内容页面。CERN通过使用钩子技术修改C运行库的malloc()从而运行KSM,解决了内存中的大量重复页面的问题,节省了8%-48%的内存[13]

本论文将在一般桌面应用环境下研究并增强新的内存节省技术KSM,使之更适合运用在桌面应用环境下,更有效地减少应用程序的内存使用量。

1.3 研究意义

内存资源总是操作系统中稀缺的资源,研究节省内存的技术具有普遍的意义。另外,随着基于Linux内核的操作系统如Android在消费电子终端上的迅速普及[14],以及可预见到基于Linux的Chrome OS在PC桌面市场也将占有一定市场,而目前的应用程序普遍占用越来越多的内存,研究Linux平台下新的节省内存的技术KSM,对于开发Android平台等基于Linux内核的平台下的商用优化管理软件具有重要的技术指导作用。

1.4 论文的主要工作

      本论文重点研究了Linux内核的KSM模块的设计与实现,并在原来的基础上做了针对桌面应用环境的增强与改进,同时认真研究了Linux内核代码的组织方式,配置与编译方式,内核开发及调试的技术,以及Linux的内存管理单元的实现。增强后的KSM命名为KSM+,它比原来的KSM更方便地自动采集到应用程序的相同内容页面并合并这些页面,以达到节省应用程序消耗的内存的目的。论文用多个实验展示了KSM+的功能,并与修改前的KSM做了比较。此外,本论文还编写了内核模块用于统计Linux桌面应用程序的重复内存页面的特点,同时可以用来应证KSM+运行的效果。

1.5 论文的整体结构布局

    本论文的第二章介绍了x86体系的段页式内存管理方式,以及Linux的内存管理的实现,还介绍了编写Linux内核代码的一些基本理论。

第三章介绍了如何使用KSM以及KSM的设计和实现原理。

第四章讲述KSM+的设计与实现。KSM+是在KSM的基础上的增强与改进。

第五章用多个实验展示了KSM+合并程序的重复内存页面的效果,并设计了一个实验比较了KSM和KSM+的差别。最后编写了用于统计应用程序重复内存页面的内核模块,并用统计数据应证了KSM+的实验结果。这些统计数据反映了Linux桌面应用程序中重复内存页面的一些基本特点,对进一步改进KSM+的算法提供了依据。

1.6 本章小结

      本章首先介绍了Linux操作系统中传统的节省内存技术,然后引入了因为虚拟化兴起而发展的新的内存节省技术,它通过合并内容相同的内存页面从而减少系统的内存使用,也被称之为内存去重技术,接着叙述了国内外在该技术方面的相关研究。目前对该技术的研究多针对虚拟机环境,而本论文则是在Linux桌面环境中研究内存去重技术。

 

Linux桌面环境下内存去重技术的研究与实现(中英文摘要)

Linux桌面环境下内存去重技术的研究与实现

在这里可以下载原稿 www.ykyi.net/upload/Research_and_Implementation_of_Memory_Deduplication_in_the_Linux_Desktop_Environment.pdf

论文题目: Linux桌面环境下内存去重技术的研究与实现

专业:软件工程

硕士生:周霄

指导教师:王常吉

摘  要

内存管理是操作系统中至关重要的部分。优秀的操作系统高效地管理有限的内存资源。Linux内核的内核同页合并(KSM)模块是在虚拟化兴起后为节省虚拟机使用的内存而发展的一种节约内存的技术。KSM通过合并相同内容页面的方式显著地降低了多个基于内核虚拟机(KVM)技术的虚拟机同时运行时系统使用的内存。实际上,KSM也能合并一般应用程序中的相同内容页面。但一般应用程序为了使用KSM技术合并内存,需要在源代码级别显式地调用相应的系统调用来告知KSM需要扫描的内存区域。对于一般用户来说,需要修改应用程序的源代码显然是一个太高的门槛。

本论文在认真研究了KSM模块的实现的基础上,增强了KSM的功能。新设计实现的KSM+使得用户可以不必修改应用程序的源代码就能利用KSM+合并相同内容的内存页面。另外原来的KSM算法依赖程序指定的内存区域有大量的重复内存页面,而实际上,一般应用程序并没有大量的重复内存。在重复内存非常少的情况下,对这些程序应用KSM技术非但不能降低内存使用,而且因为运行KSM本身所需内存而增加了内存开销。本论文针对这一点在KSM的算法上做了改进,减少了运行KSM+算法本身所消耗的内存。然后论文用Linux桌面下的常用应用程序验证了KSM+的实际效果,并构造了一个实验比较了KSM和KSM+。最后,为了了解应用程序的重复内存页面的特点,还编写了专门统计重复页面的内核模块,发现应用程序的重复页面的一些规律,为持续改进KSM+提供了依据。

 

关键词:KSM,重复内存合并 ,内存管理

 

 

Title: Research and Implementation of Memory Deduplication in The Linux Desktop Environment

Major: Software Engineering

Name: Zhou Xiao

Supervisor: Wang Changji

Abstract

Memory management is one of the most important parts of the operating system. KSM (Kernel Samepage Merging) in Linux kernel is a kind of memory saving technology developed after the emerging of virtual machine. KSM can dramatically decrease the memory usage of the hypervisor running several virtual machines. Actually, KSM can also be applied to normal applications. But in order to use the KSM, application must explicitly evoke a system call in source code level to tell KSM the memory area where the KSM will scan. To normal users, modifying the source code is impossible at most of the time.

Base on the full grasp of the implementation of KSM, a new implementation named KSM+ is created, which allows users to merge same-content pages on the specified applications without modifying corresponding source code. Moreover, the original KSM algorithm relies heavily on the specified area is rich in same-content pages, while normal applications have much less same-content pages compared to virtual machines. So, when KSM is applied to those applications, it is possible that memory usage will rise rather than decrease. To combat with this situation, KSM+ employs a new algorithm to decrease the memory usage for running itself. Several experiments prove that the KSM+ can be easily applied to specified applications and memory usage can be reduced. And a case is designed to compare the effect between KSM and KSM+, which shows KSM+ behaves better in deduplication when the same-content pages’ density is very low. At last, in order to inspect the characteristics of same-content pages from normal desktop applications, an ad-hoc kernel module is developed to do the statistics which supplies significant data for the further development of KSM+.

Key Words KSM, Deduplication, Memory Management

copyright ykyi.net

It’s a mistake to include Xen in a Linux distro

As the title show, it's a mistake to include Xen in a linux distro. Why?

Somebody would argue that Xen is a very useful technology. Xen does the virtualization work very well and many projects are using Xen which prove Xen is so great.

I'm not mean Xen is not good. However, just because Xen is a hypervisor that is based on another microkernel that is not Linux kernel itself. Linux distros that ship Xen today actually are running an entirely different Operating System kernel that most users even don't notice that. Xen should be a separate, purpose-built kernel, so it should never be a part of the Linux kernel. Isn't it strange that you think you are running a linux OS, but this 'linux' has a kernel that is not linux, which is another kernel. You take away the Linux kernel, how could you say the OS is Linux.

Just before the born of the Linux native virtualization KVM, the distros shipped Xen because there exist no other choices. Many Linux developers at that time know little about virtualization. Xen seemed a pretty easy and pretty good choise. So the Linux community made the hasty decision to ship Xen instend of investing in makeing Linux's own hypervisor. But now KVM has come for more than five years(since kernel 2.6.20 in Feb, 2007. KVM actually has a longer history. It was out there before being merged into mainline kernel code.) and KVM has proven itself to be completent to replace Xen. The most important thing is that KVM as a part of the linux kernel leverages the features of kernel like memory management, process scheduling and so on, making the kernel a perfect hypervisor. So, there is no reasons to ship Xen in Linux distros any more.

COPYRIGHT WWW.DOGEYE.NET

什麼是敏感指令

1974年,Popek和Goldberg在美國电脑協會的通訊期刊上發表了一篇論文"虛擬化第三代架構的一般性要求"(Formal Requirements for Virtualizable Third Generation Architectures)。在這篇文章中,提出了敏感指令的概念。

敏感指令(Sensitive Instructions)的定義: 敏感指令是這樣一組指令,這些指令的行為取決於指令執行時處理器的工作模式,以及指令在記憶體中的位置。

——-

對敏感指令的處理是虛擬化技術的一個關鍵點。在用戶態執行的敏感指令如果總會造成陷入(always generates a trap),這樣的敏感指令也屬於特權 指令。在不使用Wmware提出的動態二進制翻譯機制的情況下,除非所有的敏感指令都是特權指令,虛擬機管理程式才能保證正確運行。換言之,如果某種處理器架構的所有的敏感指令都是特權指令的一個子集,我們就可以說這種處理器架構是可虛擬化的。在這種情況下,我們就可以肜經典的“陷入後模擬“(trap-and-emulate)的方法實現虛擬化。按照這個定義,在嵌入式工業中最常見的ARM架構則不是可虛擬化的,因為ARM的敏感指令有些是特權指令,有些則不是。

原文 from the paper "KVM for ARM" by Christoffer Dall and Jason Nieh, Columbia University:Popek and Goldberg define sensitive instructions as the group of instructions where the effect of their execution depends on the mode of the processor or the location of the instruction in physical memory. A sensitive instruction is also privileged if it always generates a trap, when executed in user mode. The VMM can only guarantee correct execution without the use of dynamic translation if all sensitive instructions are also privileged. In other words, an architecture is virtualizable if and only if the set of sensitive instrucctions is a subset of the seet of privileged instructions. If that is the case, the VMM can be implemented using a classic trap-and-emulate solution. Unfortunately, ARM is not virtualizable as the architecture defines both sensitive privileged instructions and sensitive non-privileged instructions.

ykyi.net 翻译

为什么要虚拟化

如今,虚拟化是炙手可热的一个高频词。一些质疑虚拟化的人经常会问:我们为什么要搞虚拟化呢,计算机硬件变得越来越便宜了啊!另一方面,一些痴迷虚拟化技术的狂人们在他们的桌式机上用虚拟机运行着四五个操作系统。他们或许也有同样的疑问。仅管他们看着虚拟机里旧式操作系统,模拟出的旧式硬件,觉得非常爽非常有成就感。但是他们却不太解释得清楚究竟为什么需要虚拟化技术。那么,这篇文章将要告诉你我们需要虚拟化技术的原因。

整合 Consolidation:

使用虚拟化技术的最常见原因是需要整合:把多台机器的工作负载全部整合到同一台机器上面。在更少的物理机器上运行更多的虚拟机。但是你肯定要问:计算机已经越来越便宜了呀。没错,计算机越来越便宜了。但是如果机器非常多的话,这个价格你是绝对不能忽略的。

典型的数据中心 A Typical(full) data center

让我们来看一看当今世界的数据中心。如今的数据中心里急缺存放机器的空间,房子里满满的塞满了机器,你找不到更多的地方来添置计算机或空调之类的设施。空间利用率已经接近极限了。但是,大多数机器的资源利用率却非常地低。大概平均只有10-20%的的资源利用率。简言之,数据中心的物理空间已经饱合,但是物理机器的使用能力确远远没有利用足够。那么,如果数据中心要承担多更的工作负载,你会再建一个数据中心呢还是想办法把没有利用好的资源利用起来。

只有数据中心还有空间让你添置机器,当然多加一台机器就相当容易的解决问题了。但无论如论你放不上新的机器的时候,你应该会有很大的麻烦说服BOSS新建一个数据中心。另外一个大问题是,即使BOSS答应新建一个数据中心来解决问题,但是巨大的电力供应从哪里来呢。一个一千万瓦功率的数据中心不是说接入电网就可以接入电网的。你或许还要说服电网的领导批准提升电网的供电能力。

虚拟化是解决这个问题的最佳办法。用虚拟化把所以机器的性能都利用起来吧!

隔离硬件(Hardware Isolation)

硬件的性能每个月都在快速提高。但是,当我们把工作负载转移到一台新的服务器的时候,我们还需要先在裸机上安装操作系统,然后再配置各种软件环境,再把所有的数据转移到这台新服务器上来。忙到最后我们还要心惊肉跳的祈祷一切顺利!

如果使用虚拟化,你就不必这么麻烦了,因为不再直接与硬件层交互。你只需要在新的机器上部署好虚拟环境,再把虚拟机整个移过来。不需要再额外配置什么鬼东西,因为配置就在虚拟机里面,你已经把虚拟机整个搬来了。

历史遗留的旧操作系统(Legacy Operating System)

计算机工业走了这么多年,碰到要维护旧的操作系统并不鲜见。不幸的是,你有一个致关重要的程序只能够在这个恐龙级别的操作系统下运行。但大多数老旧的操作系统不能够在新的硬件上运行呀,你又没有办法再配置一台旧硬件的机器。

解决方案就是使用虚拟化。比如Vmware的Binary rewriting,或者Xen又或者KVM都可以。工作原理则是虚拟层模拟了简单的硬件,从你的旧操作系统看过去,多核CPU变成了老旧操作系统支持的旧时代CPU,当然频率却变快了。多核,ACPI设备发现,中断路由,支持10G以太网,支持SATA都不会成为你运行旧操作系统的障碍,因为虚拟层(Virtualization Layer)!

当然了,虚拟化本身会占用一些性能。但是因为采用了虚拟化,你才能在非常快速的新硬件上运行旧操作系统,这样得到的效率提高要远远高于在原生态支持旧操作系统的旧硬件上运行。因此,还为你节省了电费。

测试(Testing)

不管你是学习软件开发的在校学生,还是大银行的首席信息官,你一定缺少足够多的测试硬件吧。

虚拟化可以解决这一问题。在虚拟机上测试新发布的Fedora Rawhide或者Debian Unstable先,而不是直接格掉机器安装。还能给你的开发团队一把虚拟机,让每人一台虚拟机想测试什么就测试什么。

维护(Maintenace)

有了虚拟化,能方便很多方面的维护。

比如使用即时迁移技术,像Vmware的vmotion,Xen的Live Migration,你可以在保持虚拟机上的操作系统正常工作的情况下把虚拟机从一台物理机器移动到另一台物理机器。这项技术确实非常有用啊,不仅仅可以用来在你的朋友面前炫燿。

还有很多情况,你可以使用到即时迁移技术。比如物理机的硬件故障。有一台机器的CPU风扇坏了,CPU的保护系统自动启用使用CPU工作在一个非常慢的速度。那么你就可以把虚拟机即时迁移到另一台健康的机器上,然后修理那台坏的机器而不致于产生Downtime。又如,某台虚拟机的工作负载越来越大,那么你可以这台虚拟机所在的物理机上另外一些虚拟机器迁移到其它物理机上,为这台需要更多资源的虚拟机提供更多支持。有时候你需要升级某台机器的硬件,那么先把这台机器上所有的虚拟机即时迁移到其它机器,再开始你的硬件升级工作,还是没有任何Downtime。酷毙了,是吗?

节省能源(Power Saveing)

举个例子,你有100台服务器运行着各种各样的100个服务程序。但每台服务器的负载只有不到50%,那么你可以用50台物理机器虚拟出100台虚拟机运行100个服务程序。一下子节省了50%的电力,不是吗?想想,一个功率是一千万瓦的数据中心如果能节省50%的电力,这是个多么了不起的数字啊!为你节省了电费钱,还为对抗全球变暖做出了贡献。

安全和性能隔离(Security and performance isolation)

如果你采用虚拟机把不同的程序运行在不同的虚拟机里面,那么如果其中有一个程序出错,吃光了所有的内存,它也不至于影响其它程序。因为其它程序运行在不同的虚拟机里,它们仍然运行得很好,一点都不会受到那个出错程序的影响。如果这些程序运行在同一个OS下,那情况就不妙了。

一个相似的情况下,如果有一台虚拟机被入侵者攻陷,那么入侵者仅仅只控制了这一台虚拟机,暂时不能对其它虚拟机造成直接威胁。当然,这些虚拟机应该相互隔离的很好,每台虚拟机都运行着自己的内核,大多数虚拟化技术都是这样做的。但有一种虚拟化技术叫做容器技术(Container Technoloties),如Linux VServer, Virtuozzo/OpenVZ和Solaris Zones,它们实现的虚拟化的隔离性要相当低一些,得到的好处是虚拟化自身消耗更少的硬件资源。

copyright ykyi.net