1 linux在内存管理模块，为了解决外部碎片的问题，采用了Buddy System Algorithm。

所有的连续free page被分成11个组，每个组是一个块列表（块表示一个连续的未分配page区域）。每个列表的连续块大小分别是1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 到1024个page。

当请求一个256page的内存区域时，会先到256的这个列表里查找，如果能够找到一个256的空闲内存区域，那么直接返回；如果找不到，那么到更大的512列表里找，如果存在，那么返回256个page给请求，并把剩余的连续256个page的块分配到256列表；如果512列表找不到，那么继续往上找1024，如果1024也没有，那么返回内存分配失败。

http://ilinuxkernel.com/?p=1029

http://www.csdn123.com/html/blogs/20130607/20419.htm

尽管采用虚拟内存技术，连续的虚拟内存不一定得对应连续的物理内存。但是还是有一些原因要求内核在分配内存的时候必须要采用连续的物理内存，有这么几个原因：

 • In some cases, contiguous page frames are really necessary, because contiguous linear addresses are not sufficient to satisfy the request. A typical example is a memory request for buffers to be assigned to a DMA processor (see Chapter 13). Because most DMAs ignore the paging circuitry and access the address bus directly while transferring several disk sectors in a single I/O operation, the buffers requested must be located in contiguous page frames.

• Even if contiguous page frame allocation is not strictly necessary, it offers the big advantage of leaving the kernel paging tables unchanged. What’s wrong with modifying the Page Tables? As we know from Chapter 2, frequent Page Table modifications lead to higher average memory access times, because they make the CPU flush the contents of the translation lookaside buffers.

• Large chunks of contiguous physical memory can be accessed by the kernel through 4 MB pages. This reduces the translation lookaside buffers misses, thus

significantly speeding up the average memory access time (see the section

“Translation Lookaside Buffers (TLB)” in Chapter 2).

2 内存分配请求可以通过两种方式来满足，一种是如果有free page那么直接分配返回；如果没有free page那么阻塞请求，触发内存回收，直到有空闲的内存区域，才返回分配请求。

但是一些内存分配请求不允许阻塞，比如中断例程、执行临界区的请求。这个时候就需要一种非阻塞的内存请求机制-原子内存分配，如果没有可用内存区域，不阻塞，直接返回失败；但是操作系统还是会尽可能的保证请求成功，于是就有了一个系统保留页区域，这个区域的page由ZONE_DMA、ZONE_NORMAL贡献。当可用内存不足时，原子内存分配请求会使用这个保留区域的page。

3 尽管Buddy System Algorithm可以解决外部碎片的问题，但是依然没法解决内部碎片。内存管理的最小分配单位是页，页的尺寸一般为4kb，如果遇到小内存空间的请求，比如几十到几百byte，每次都分配一个完整的页，那么势必会造成很严重的内存碎片。于是就有了slab allocator，他是基于Buddy System上的一层逻辑

 http://en.wikipedia.org/wiki/Slab_allocation

使用Slab allocation有几个前提:分配的数据类型影响内存分配的特点，可以把分配的数据抽象成一类对象；用户会频繁的对同一类对象进行内存分配请求；对内存区域的请求可以按照频繁度分类；为了提高cpu cache的命中率，要尽量减少对buddy system allocator的请求，以免出现太多脏缓存。

slab allocator按照同类对象进行分组，放到缓存里（这里的缓存是指已经预先经过buddy system allocator

分配过page的内存区域）。每一个缓存都是同一类对象的仓库。缓存被划分成一个个slab。每个slab都有一个或者多个连续的page frame组成，slab里面放同一类的对象，同一类的对象对内存的占用大小类似。当一个对象被释放后，内存并不会被操作系统回收，而是在下次分配同一类对象的时候，直接复用这个已经分配的内存区域。

4 高端内存

内核线性地址空间（3G-4G）用于内核的运行，所谓内核线性地址空间就是说内核态下虚拟地址与物理地址是线性关系，两者相差一个固定偏差，计算公式为VA（虚拟地址）=PA（物理地址）+PAGE_OFFSET。这个和用户线性地址空间不一样，无需经过MMU的常规地址转换，直接和物理地址一一映射。

但是为了使内核地址空间能够使用大于1G的内存，提出了高端内存的技术，这部分高端内存需要MMU通过TLB表来建立动态的映射关系。

http://bbs.chinaunix.net/thread-1938084-1-1.html

http://blog.csdn.net/moonth1023/article/details/7081773

5 设备驱动

内核通过设备驱动和设备进行交互，设备驱动包括在内核里，一个驱动可能控制一个或者多个设备，如磁盘、键盘、鼠标、网卡等等，设备驱动是通过一个特殊的接口和内核挂接的。通过接口挂接的好处是增强设备驱动的可热拔插，设备驱动程序无需了解内核所有的代码，只需要循序指定接口的规范即可，设备子系统高度模块化。内核可以通过一个统一的固定接口来操作不同的设备。

用户进程要操作io，首先会向内核发起文件相关的系统调用，这些文件在/dev里，这些设备文件和某一个设备驱动相关联，内核通过调用设备驱动向硬件模块发起操作。

 
6 linux paging

虚拟内存线性地址，先从页目录找到页表，再从页表找到页，在页面由偏移量得到所要读取的数据。虚拟内存的页对应物理内存的页，是一块4kb的连续内存区域（如下图的offset12个bit可以表示4kb的数据）。32位系统的寻址过程如下。

 
 之所以采用两级的方式定位一个页是一种时间换空间的策略，因为每个进程都要维护一个页表数据结构，如果只用一级的话，那么要支持4GB的线性地址空间，需要一个页表存储2的20次方个页条目，每个条目4byte，初始化加载页表数据结构就要用4M内存。分为两级就大大减少了内存消耗，初始化只需要加载2的10次个页表条目，只要4k。只要当进程请求对应的页表时，才去加载页表数据，定位页条目。页条目里面包含了页所在的物理内存地址，如果找不到，那么发生页错误，由内核把页数据swap in，重新执行内存寻址，读取物理内存数据。

奔腾的80X86处理器还能支持扩展的分页，每页可以表示更大的存储空间，4Mb。如下图，这种技术减少了页表大小，节约了TLB。

7 cpu cache

访问cpu的速度比访问主存的速度高出好几个数量级，依据局部性原理，cpu引入了高速缓存。缓存的数据粒度为line，cpu认为内存相邻的数据，一起被访问的概率比较高。当写数据的时候，有两种策略，一种是write through,写数据不仅写缓存，还写到主存；一种是write back，写数据只写到缓存，只有当cpu触发flush指令或者flush硬件信号发生才会更新主存。

现在大多数cpu都是多核的，每个核都有独立的缓存，在更新缓存的时候，会触发一个cache snooping，他会check其他cpu有没有包含这个数据，有的话会通知其他cpu更新缓存数据。

另外，cpu的高速缓存也分为多级，有L1,L2,L3，每一级的速度都变慢，存储空间都变大。这些缓存的同步都是在硬件层面完成的，对于linux内核而言，它只认为cpu只有一级的缓存。

除了通用告诉缓存外，cpu还包含了Translation Lookaside Buffers (TLB ) ，用于提高线性地址转换。第一次访问某个线性地址是通过缓慢的读取主存页表的方式来转换；第二次访问同一个线性地址，则直接可以到TLB里面获取物理地址。

8 内核在初始化的时候，会构建保留的物理地址，这部分内存区域包括了内核代码和初始化数据结构以及一些不可用内存（映射到硬件设备io共享内存和BIOS数据）。这部分保留的页，不可被动态分配，也不能被swap out到磁盘。

线性地址空间被分为两部分，一部分是0x00000000-0xbfffffff，处于用户态或内核态的进程都可以寻址；一部分是0xc0000000-0xffffffff，处于内核态的进程才可以寻址。

9 进程地址空间

进程的地址空间由他所允许访问的线性地址组成，每个进程都有他自己的线性地址集合。内核通过添加或者删除内存区域来改变进程的地址空间。

所谓的内存区域是指一段线性地址的区间，它由一序列连续的页组成。每个内存区域由线性地址、长度和访问权限所标识。线性地址和长度必须是4kb的倍数。

以下操作会触发内存区域的增加或者删除

• When the user types a command at the console, the shell process creates a new process to execute the command. As a result, a fresh address space, and thus a set of memory regions, is assigned to the new process

• A running process may decide to load an entirely different program. In this case,the process ID remains unchanged, but the memory regions used before loading the program are released and a new set of memory regions is assigned to the pro-cess 

• A running process may perform a “memory mapping” on a file (or on a portion of it). In such cases, the kernel assigns a new memory region to the process to map the file 

• A process may keep adding data on its User Mode stack until all addresses in the memory region that map the stack have been used. In this case, the kernel may decide to expand the size of that memory region 

• A process may create an IPC-shared memory region to share data with other cooperating processes. In this case, the kernel assigns a new memory region to the process to implement this construct

• A process may expand its dynamic area (the heap) through a function such as malloc(). As a result, the kernel may decide to expand the size of the memory region assigned to the heap 

内核通过需要搜索包含某个线性地址的内存区域，通过内存区域链表或者红黑树来实现查找（内存区域链表是有序的）。

10 页错误处理

当页错误处理器走向正常流程，会发生页请求。

页请求是一种延迟加载的技术，直到进程访问到某个地址才会触发页请求，由内核分配物理内存页框。这个技术大大提高了内存的利用率，但是需要多消耗cpu。好在进程都具备局部性的特点，大部分情况下，性能不会有明显牺牲。

当调用fork的时候，内核需要给子进程分配页表和页，同时把父进程的数据复制到子进程。这种方式既消耗内存空间、速度也慢，需要进行多次主存访问。所以linux采用了更先进的方式就是，共享内存。当fork一个子进程的时候，子进程和父进程共享一个地址空间，地址空间标记为只读。当其中的一个进程要修改共享地址空间的page时，触发页错误处理，执行copy on write，复制这个page,然后修改，并去除只读标识。

而对于轻量级进程-线程，创建之后是直接使用父进程的地址空间。

11 当系统运行的进程以及系统的cache多到一定程度时，所有的物理page frame都会分配完。这个时候就会触发page frame reclaiming algorithm,他会steal用户进程和系统cache的paga frame重新填充到伙伴系统的free block列表。在steal的时候需要把目标page数据写到磁盘，执行写io操作本身也需要free page frame，用来分配io的缓冲。所以当系统一个free page都没有的时候，没法完成回收操作，系统会crash。

page frame reclaiming algorithm (PFRA)的目标是选择一个non-free的page然后free it。PFRA针对不同类型的page采用不同的处理方式。

 其中swap area是一个专用的磁盘区域或者文件。

要选择一个合适的回收page是很经验主义的，没有多少理论可以参考。最多就是使用LRU算法。一般来说会按照以下原则选择回收的page。

•       Free the “harmless” pages first.Pages included in disk and memory caches not referenced by any process should be reclaimed before pages belonging to the User Mode address spaces of the pro-cesses; in the former case, in fact, the page frame reclaiming can be done with-out modifying any Page Table entry. As we will see in the section “The Least Recently Used (LRU) Lists” later in this chapter, this rule is somewhat mitigated by introducing a “swap tendency factor.”
•      Make all pages of a User Mode process reclaimable With the exception of locked pages, the PFRA must be able to steal any page of a User Mode process, including the anonymous pages. In this way, processes that have been sleeping for a long period of time will progressively lose all their page  frames.
•      Reclaim a shared page frame by unmapping at once all page table entries that reference it When the PFRA wants to free a page frame shared by several processes, it clears all page table entries that refer to the shared page frame, and then reclaims the page frame.
•       Reclaim “unused” pages only.The PFRA uses a simplified Least Recently Used (LRU) replacement algorithm to classify pages as in-use and unused .If a page has not been accessed for a long time, the probability that it will be accessed in the near future is low and it can be considered “unused;” on the other hand, if a page has been accessed recently, the probability that it will continue to be accessed is high and it must be consid-ered as “in-use.” The PFRA reclaims only unused pages. 

PFRA触发的条件是

Low on memory reclaiming

The kernel detects a “low on memory” condition.

Hibernation reclaiming

The kernel must free memory because it is entering in the suspend-to-disk state

Periodic reclaiming

A kernel thread is activated periodically to perform memory reclaiming, if neces-sary.

 尽管有这么多内存回收的机制，但是当内存子系统负载很重的时候，也是有可能出现内存分配失败的情况。这个时候操作系统就必须断臂求生了，触发OOM killer。他会按照下面的策略选择一个进程来牺牲。

• The victim should own a large number of page frames, so that the amount of memory that can be freed is significant. (As a countermeasure against the “fork-bomb” processes, the function considers the amount of memory eaten by all children owned by the parent, too.)

• Killing the victim should lose a small amount of work—it is not a good idea to kill a batch process that has been working for hours or days.

• The victim should be a low static priority process—the users tend to assign lower priorities to less important processes.

• The victim should not be a process with root privileges—they usually perform important tasks.

• The victim should not directly access hardware devices (such as the X Window server), because the hardware could be left in an unpredictable state.

• The victim cannot be swapper (process 0), init (process 1), or any other kernel thread.

  由于PFRA是如此复杂，以至于在某些状况下会出现一些病态情况，比如swap thrashing。PFRA努力的释放内存，并把内存中的页换出，写入磁盘；但是被换出的页所在的进程也在执行，又不断的发生页错误，从磁盘读入数据到内存。这样一来大量的资源都在内耗做无用功，系统性能急剧下降。

为了解决这个问题，内核引用了swap token，相当于免死金牌。当一个进程被授予免死金牌后，那么就不会成为swap out的对象。

 12 swap

swaping的引用是作为非映射page在磁盘的一个备份，swaping子系统所处理的page包含以下：

• Pages that belong to an anonymous memory region of a process (User Mode stack or heap)

• Dirty pages that belong to a private memory mapping of a process

• Pages that belong to an IPC shared memory region

它对用户程序而言是透明的，是内存子系统的核心，他的主要特性有：

• Set up “swap areas” on disk to store pages that do not have a disk image.

• Manage the space on swap areas allocating and freeing “page slots” as the need occurs.

• Provide functions both to “swap out” pages from RAM into a swap area and to “swap in” pages from a swap area into RAM.

• Make use of “swapped-out page identifiers” in the Page Table entries of pages that are currently swapped out to keep track of the positions of data in the swap areas.

 通过swap才能做到，所有进程使用的内存能够大于物理ram。当然性能和直接使用ram不具备比较性。所有对于性能要求高的应用，当然内存还是越大越好。

swap area是通过内核自身一个磁盘分区来实现的，也可以是通过更大分区的一个文件来实现。

一个系统也有可能会有多个swap area分布于不同的磁盘，这样可以提高swap的并发能力。每个swap area都是由一系列的paga slot组成，每个slot大小为4kb用来存储swap out的page。swap out的时候，内核会尽量把数据放在连续的slot里面，减少之后swap in的磁盘seek提高性能。

下图是swap的描述符，其中slot的counter为0，表示这个slot free；为1表示被占用，大于1表示多个进程共享。

 一个page是否被swap out是在页表里面标示出来的，页表的page有三种可能的状态

Null entry ,The page does not belong to the process address space, or the underlying page frame has not yet been assigned to the process (demand paging). 

First 31 most-significant bits not all equal to 0, last bit equal to 0,The page is currently swapped out.

Least-significant bit equal to 1,The page is contained in RAM.

对于32位系统，总共有24位来表示slot号，也就是说swap area可以达到64G。
http://blog.csdn.net/tianlesoftware/article/details/8741873

13 VFS

linux的一个强大之处就是能够允许不同的文件系统共存，通过虚拟文件系统技术来解决。

VFS对上提供了统一的接口来访问不同类型的文件系统

$ cp /floppy/TEST /tmp/test

比如这个命令将MS-DOS格式的文件拷贝到ext2的文件系统，用户程序不需要知道不同文件系统的实现细节。可以这么理解VFS是用户程序和具体文件系统实现的中间层。

 VFS支持的文件系统可以分为三类：基于磁盘的文件系统，比如本地磁盘ext2\VFAT\NTFS\CD-ROOM，和仿磁盘的存储USB；基于网络的文件系统，比如NFS, Coda, AFS (Andrew filesystem), CIFS (Common Internet File System,used in Microsoft Windows), and NCP (Novell’s NetWare Core Protocol)；特殊文件系统，不需要管理磁盘空间，可能在本地或者远程，比如 /proc。

VFS通过抽象出通用的文件模型来支持这么多不同的文件系统，采用了面向对象的建模方式。通用文件模型包含以下几个部分

• The superblock object。Stores information concerning a mounted filesystem. For disk-based filesystems,this object usually corresponds to a filesystem control block  stored on disk.
• The inode object Stores general information about a specific file. For disk-based filesystems, this object usually corresponds to a file control block stored on disk. Each inode object is associated with an inode number , which uniquely identifies the file within the filesystem.
• The file object。Stores information about the interaction between an open file and a process.This information exists only in kernel memory during the period when a process has the file open.
• The dentry object。Stores information about the linking of a directory entry (that is, a particular name of the file) with the corresponding file. Each disk-based filesystem stores this information in its own particular way on disk.

 14 文件访问

linux访问文件有以下几种方式

• Canonical mode.The file is opened with the O_SYNCand O_DIRECTflags cleared, and its content is accessed by means of the read()and write() system calls. In this case, the read() system call blocks the calling process until the data is copied into the User Mode address space (however, the kernel is always allowed to return fewer bytes than requested!). The write() system call is different, because it terminates as soon as the data is copied into the page cache (deferred write). 
• Synchronous mode.The file is opened with theO_SYNCflag set—or the flag is set at a later time by the fcntl() system call. This flag affects only the write operation (read operations are always blocking), which blocks the calling process until the data is effectively written to disk. 
• Memory mapping mode.After opening the file, the application issues an mmap()system call to map the file into memory. As a result, the file appears as an array of bytes in RAM, and the application accesses directly the array elements instead of using read(), write() ,or lseek() . This case is discussed in the section “Memory Mapping.”
• Direct I/O mode.The file is opened with theO_DIRECTflag set. Any read or write operation transfers data directly from the User Mode address space to disk, or vice versa, bypassing the page cache. 
• Asynchronous mode.The file is accessed—either through a group of POSIX APIs or by means of Linux-specific system calls—in such a way to perform “asynchronous I/O:”this means the requests for data transfers never block the calling process; rather,they are carried on “in the background” while the application continues its normal execution. 

 值得注意的是Direct I/O，有些软件对性能的要求特别高，内核默认的pagecache机制起不了作用，应用需要自己管理缓存，比如高性能的数据库系统，这个时候就需要用直接IO。除了管理cache外，直接io还能减少数据复制次数。使用常规io，数据要先从磁盘复制到内核缓冲，再从内核缓冲复制到用户空间缓冲；而直接io，可以支持直接从磁盘复制到用户空间缓冲。