这几天一直在读经典的linux入门书《Linux kernel development》第三版即LKD，这是我第一次读英文版的技术书，颇有些高兴。之所以读，一是因为学过操作系统的理论知识，想看看货真价实的OS到底怎么实现的，其二则是在知乎上请教了一位linux的大牛，他给的建议就是初学linux最好的是这本《linux kernel development》，遂读了一番。读过之后，感觉读英文版总体不是很难，但是有一些地方确实不容易理解。而且以前读其他外国人写的书，就发现外国人习惯一句话至少说三遍，前前后后的写，这本书也是其中之一。这本书总体是对linux 2.6版本的概况，没有大篇幅的源代码，有对主要部件例如process、schedule、Interrupt、synchronization、MM、VFS、page等概述，有比喻和例子，而且语言幽默。尤其对一些主要struct、function和parameters讲解地很清楚，尤其是参数中有flag传参时对各种可选项列表而出。中断的一章难度大，有读不懂的地方只能去看中译版，而且很多知识细想一下就必须查查资料才能懂得。然而读着读着发现，内核的总体编程思想和OOP极为相似，而且作者也在书中提到VFS虚拟文件系统中结构体的设计和面向对象的思想很类似，也是C语言中支持函数指针，可以在struct中设置指向函数的指针，这样的话和面向对象中的对象有何区别？同时发现书中也是有些许错误的。这本书之后应该是《深入理解LINUX内核》。在此记录读书笔记和心得。
linux kernel 中大量使用了macro宏，由于他的便捷利用，这点在开始的几章就有提到。
kernel中使用task_struct来表示进程，同时linux坚持thread线程只是共享资源的进程，不另对线程进程表示。process的状态被linux分为了五种：TASK_RUNNING、TASK_INTERRUPTIBEL、TASK_UNINTERRUPTIBEL、__TASK_TRACED、__TASK_STOPPED和僵死状态，其中TASK_INTERRUPTIBEL和TASK_UNINTERRUPTIBEL区别在于前者可以收到signal或者event发生而转换为RUNNING，而后者对signal信号的到来没有反应。不同状态的进程链接在不同的双向链表中，受到不同的调度。但是在网上查资料看到不同的linux版本中进程状态不同。每一个进程都有自己标识符PID。linux中包括用户级进程、用户级线程和内核级线程。用户级线程在用户空间实现，自我调度，因为linux内核看不到用户级线程，这样线程切换不必陷入内核效率高速度快，但是用户级线程阻塞则代表整个进程阻塞也就是其他同进程的用户级线程也阻塞因为内核看不到线程只见线程导致内核对该进程schedule了。内核线程，标准的内核空间进程，可调度和抢占，是为了运行后台操作例如flush、ksoftirqd软中断由内核自我管理，且只运行于内核态不能切换到用户态，内核线程可能一直处于等待状态或者周期运行的状态来实现特定任务。4G内存空间中，低3G由用户进程访问，高1G空间由内核和用户进程使用，每个用户进程私有空间3G，因为进程进行系统调用的时候可以陷入内核空间导致进程能够使用的空间是4G。一个CPU上同一时间只能运行一个进程。程序在编译之后形成的地址空间是虚拟地址空间，由虚拟到物理的映射需要段描述符表或者页表，linux支持页表，即使CPU架构本身在于段表。内核占据最高1G的空间，但是是虚拟地址，映射到物理地址之后一定是从0X00000000开始，而3G位置0XC0000000在linux称为PAGE_OFFSET。所以用户空间的虚拟地址到物理地址的映射需要段描述符表或页表和TLB快表由硬件支持提供，而内核则是对于一个虚拟内存空间x其物理空间为x-0xc0000000，该PAGE_OFFSET值在linux的page.h文件作于预编译命令定义。为什么linux要把内核放在0XC0000000~0XFFFFFFFF中，网上写的大多是null指针在用户空间和中断向量在高地址。
linux2.6通过sys_fork()函数进行进程创建，实际调用do_fork()函数传递不同CLONE_FLAGS来实现对fork() / clone() / vfork()函数的调用，而do_fork()函数核心调用copy_process()函数。fork()之后子进程完全复制父进程的资源，有自己的task_struct和pid，但是考虑到复制性能和子进程是否会用到复制的资源问题，采用COW写时复制推迟真正的复制，如果子进程发生写入则资源复制。fork()调用执行一次返回两个值，对于父进程，fork函数返回子程序的进程号，而对于子程序，fork函数则返回零。而fork之后的父和子进程不共享堆栈、变量等数据空间，自己有自己的运行空间，但是共享程序指令，父子进程各自执行，其执行顺序收到linux kernel进程调度算法的控制。vfork()之后的父子进程共享地址空间，vfork（）的子进程必须显式调用exit()来结束，同时vfork()也是返回两个值。vfork()之后父进程会被阻塞直至子进程调用exit()或者调用exec()执行另一程序，也就是父进程挂起而子进程运行。而clone()则有选择的复制父进程的资源具体复制哪些资源由CLONE_FLAGS指明，没有复制的采用指针的形式给子进程共享，clone（）返回子进程的pid，clone()通过CLONE_VFORK参数说明父进程挂起而子进程运行直至子进程唤醒父进程，若没有CLONE_CFORK则两者抢占运行。
linux进程调度考虑到I/O密集型和CPU密集型即计算密集型的不同，并没有采用简单的时间片方法，采用了CFS完全公平算法，实质上是根据nice值按照优先级为进程分配处理机比例而非单纯的时间片即采用几何加权的方式而非算法加权方式，而这个比例来源于当前可运行进程runnable的整体运行时间，每次选择最小的运行时间的进程调度。nice值衡量分配处理器比例的值，值越大优先级越低。同时CFS设置了一个估值targeted latency。CFS引入了一个minimum granularity，为1毫秒。linux在调度实体sched_entity中使用vruntime变量来记录真实运行时间进而分析他还能运行多长时间，所以CFS的核心在于：pick the task with the smallest vruntime，就是其抢占时机取决于新的可运行程序消耗多少处理器使用比。如果消耗的使用比比当前进程小，则新进程立刻投入运行，抢占当前进程。此时红黑树上场了，linux使用RBTREE管理runnable进程，这样可以直接从最左子节点得到最小值因为rbtree也是一颗排序树同时是自平衡树是根据其自身性质实现平衡，而且linux将下一个最左子节点缓存起来进一步提高效率，但改变的时候要考虑到cache的更改。之前采用CFS进行调度的普通进程，基于优先级进行调度。linux2,6中支持的实时调度策略有两种：FIFO和RR。实时调度的优先级高于普通调度这是为了更快响应用户请求。进程的调度方式是schedule()函数。进程休眠是自己将自己状态状态改变移除红黑树放在相应队列中，而唤醒则是进程被设置为可运行状态移入树中。同时里虐支持用户级进程抢占式运行和内核线程抢占运行。
用户级进行通过系统调用陷入内核态，此时内核代表用户进程运行，之后再返回用户状态。系统调用的实现在X86中是通过汇编指令软中断INT 0X80或者SYSENTER。在系统调用前，参数被写入CPU寄存器，在调用系统调用服务程序前，把参数拷贝到内核堆栈中，返回值写入EAX寄存器供用户态进程读取。
linux中中断的产生是随机异步的，而异常是在一条执行之后同步产生的。linux将中断处理分为两个阶段The Top Halves 和The Bottom Halves，之所以分开执行是为了让top halves执行的尽可能快，而其他工作留在bottom havles中。尽可能快的执行中断处理程序，可以中断嵌套，不能sleep。中断分为可屏蔽的和不可屏蔽的。硬件设备控制器通过IRQ线向CPU发出中断，可以通过禁用某条IRQ线来屏蔽中断。中断描述符表是根据中断类型码来取得中断处理程序入口地址，进而处理中断。linux的top halves即interrupt handler运行在interrupt context中，而bottom halves则分为三种softirq / tasklet / work queue，仅有work queue运行于process context中，其实就是一个进程。tasklet基于softirq。这些bottom halves的执行就需要靠内核线程运行来实现了，每个处理器都有一组辅助处理他们的内核线程。，softirq由softirq_action表示，函数__do_softirq()：
u32 pending;
pending = local_softirq_pending();
if(pending) {
struct softirq_action * h;
set_softirq_pending(0);
h = softirq_vec;
do {
if (pending & 1) h->action(h);
h++;
pending >>= 1;
}while(pending);
}
softirq适用于时间要求最高的bottom halves。softirq支持中断不能sleep，同一个处理器上不能同时运行相同的softirq，但是不同的processor可以，所以需要锁来处理同步问题，使得更加复杂。tasklet由tasklet_struct表示，tasklet不存在这个问题因为tasklet不能在不同处理器上运行相同的tasklet，即相同的tasklet不会并发的执行即使在不同处理器上。tasklet分为两种：HI_SFOTIRQ和TASKLET_SOFTIRQ，两者优先级不同前者高。tasklet的调度通过tasklet_schedule()和tasklet_hi_schedule()来运行。当大量的软中断触发时内核唤醒一组最低优先级最高nice值的线程处理，以免其他线程一直由于软中断的触发而starve。最后一种是work queue,运行于process context,而非interrupt context中，可被调度可sleep，由workqueue_struct表示，其核心是一个cpu_workqueue_struct数组，使用work_struct代表需要处理的工作，有很多类型的工作线程，而对于一种工作线程一个处理器上只有一个，由cpu_workqueue_struct表示，而workqueue_struct表示的就是整台机器上同一种工作线程的集合。
产生并发原因书中列举了五个：INTERRUPT / SOFTIRQ AND TASKLET / KERNEL PREEMPTION / SLEEPING AND SYNCHRONIZATION WITH USER-SPACE / SYMMERTICAL MULTIPROCESSING。而对于同步问题，涉及原子类型操作atomic operation，原子类型的定义：
typedef struct {
volatile int counter;
} atomic_t;
spin lock自旋锁，linux中与其他OS不同的是他不会递归自旋的。自旋锁是最多由一个线程拥有的锁机制，等待锁的线程是不sleep的，所以持有自旋锁的线程应该是短时间完成任务的。例如自旋锁可以用在中断处理程序中而信号量不能因为信号量运行线程睡眠，而在将自旋锁使用在中断处理程序上时，获取锁之前要禁止当前处理器上的中断处理请求，因为如果不禁止的话中断处理请求可能会中断内核代码去请求获得已经被持有的锁，但是持有锁的中断被该请求中断了，造成死锁。使用自旋锁来保护那些可抢占进程上下文代码的bottom half，或者保护top half和bottom half共享的数据因为top half可以抢占bottom half的运行。第三个涉及读写自旋锁rw spin lock，一个或多个读者可以拥有一把锁而最多只能有一个写者有一个锁，而且linux中读写锁是读者优先的。第四，支持PV操作的信号量semaphore，支持线程sleep，就是得不到锁就加入等待队列里，等到持有锁的进程释放的时候就抢占式运行。这很适合长时间持有锁的进程，不适用于短时进程，因为短时进程使用semaphore会导致频繁的context switch这些额外功增加之后导致进程运行时间受到压榨，不适用interrupt context，而且取得semaphore的时候不能持有spin lock因为你能睡眠啊。semaphore有锁最多持有者数量的计数变量，当该变量为1的时候就成了mutex，信号量也可以分为rw semaphore。第五，mutex，就是可sleep的spin lock，解锁的进程必须是持有锁的进程，进程持有mutex的时候不能exit，中断程序不能获取mutex。第六，支持写者优先的顺序锁。涉及到锁的问题，就会考虑到编译器为了优化而做的重排序，而linux kernel提供使用rmb()设置读内存屏障防止读屏障两侧的读操作被out of order，wmb()提供写操作屏障，而mb()提供两者，barrier()组织编译器的重排序优化。
阶段性发生的事件使用系统时钟，可以产生时钟中断的可编程硬件，其中断类型码依赖于不同的架构设计。而实时时钟RTC则是由主板上的小电池供电一直运行，记录时间。定时器用于执行延后的任务，设置延后时间和执行任务启动定时器，定时器不会周期运行，超时后自动撤销，应用广泛，由timer_list表示。内核在时钟中断发生后执行定时器，他作为软中断在bottom half中运行，内核按照超时时间将所有的定时器分作五组，当定时器超时时间接近时向下移。
linux对内存的管理采用分页式管理，对页的抽象struct page，采用page来跟踪所有的页，他是相关物理页的映射。内核把不同的页划分为不同的zone区，有四个区：ZONE_DMA / ZONE_DMA32 / ZONE_NORMAL / ZONE_HIGHMEM，区使用struct zone表示。kmalloc()函数获得至少size字节的物理上连续的内存空间，释放使用kfree()，而空间分配也需要标识，因为不同的zone功能权限不同，flag分为三种：action modifiers / zone modifier / type。action modifier说明内核如何分配请求的内存，zone modifier说明区哪里分配，type表明内存分配的特定类型。vmalloc()分配虚拟地址连续不保证物理地址连续的空间。linux增加slab层作为通用数据结构缓存层，来加快数据结构的请求和释放，slab层把不同的对象划分为高速缓存组，每个组存放不同类型的对象，这些cache又划分为多个slab，每个slab中才把持着这些数据结构对象，就是一种为了加快数据结构对象分配和释放效率的分作多层的层级结构，而kmalloc()接口建立在slab上，当然slab采用struct slab结构表示。
用户进程通过system call陷入内核态之后内核使用内核栈来运行的，内核栈很小而且固定，而每个进程创建的时候都会获得一个内核栈空间，一般是2页大小，所以系统调用的底层函数不能是递归的。内核栈与进程体struct task_struct使用两个指针完成：
linux为中断处理程序提供中断栈的概念
VFS虚拟文件同是应为一个系统内可以安装很多种不同类型的文件系统，而采用一种存储于内存的中间层来屏蔽掉这些差异为上层系统调用提供统一的服务接口。而对于VFS，存在四种主要的struct：保存具体文件系统元信息的superblock ：super_block；存储内核操作文件或目录所有信息的inode ； 代表路径组件的dentry ; 代表进程中打开的文件的file。dentry的状态分为三种：used / unused / negative。dentry和file并不是真正与磁盘上数据对应而是存储在内存中结构体类型。描述每个filesystem功能和行为的struct：file_system_type，他代表了文件系统的一个具体实例。从进程角度来看，每个进程打开的文件使用files_struct来表示，其中fd_array指向了打开文件列表。而task_struct中使用fs来指向fs_struct来表示和该进程相关的文件系统信息。
外设分为块式、字符式和网络式，各有特点。linux采用块缓存的方式，实际上就是内存和磁盘之间的cache，一个块可以包含几个部分但不超过一页，使用buffer_head表示，他的作用就是描述从磁盘块到物理内存块的映射。linux使用bio来代表正在执行的块式I/O操作，他本身不存储I/O内容，而是通过bi_io_vec指向bio_vec数组的首地址，通过bi_idx对该数组进行索引，而该数组中的每一项bio_vec都指向者page，这才是操作的内容或者说数据。bio_vec结构体实际上由page、offset和len构成。从另一个角度看，每一个块I/O请求由一个bio实体表示，每一个请求可能要操作一个或多个块，这些块是存储在bio_vec结构体数组中，表示每一个块的方式是使用页指针、偏移量和块长度来表示的。而bio中使用bio_cnt来计数bio结构体的使用次数，当其为0时就撤销bio。linux采用请求队列的方式对请求进行管理，每一个节点都是一个请求，而这些请求会对磁盘操作。如何调度这些请求来最大地提高磁盘访问效率就是个问题。linux采用merge and sort方式，把对相近位置磁盘区域的请求进行合并就可以一次访问磁盘满足多个请求，同时以对磁盘访问的位置为依据进行sort。这里面涉及到linux 电梯算法、最后期限算法、预测I/O算法（没看明白）、完全公平队列I/O算法、空I/O调度。
mm_struct描述一个进程的地址空间。虚拟内存区域由vm_area_struct描述，指定了地址空间内连续区间上的一个独立内存范围，每个内存区域由其自己的属性和访问权限，每个vma代表不同类型的内存区域，不同类型的虚拟内存区域例如C库程序段、代码段、数据段、栈段、bss段等，其权限和属性由vm_area_struct中的vm_flags设置。通过mm_struct中两个变量mmap和mm_rb之一访问内存区域，但是两者包含完全相同的vm_area_struct结构体指针。内核使用mmap()和do_mmap()来扩展进程内存区域。另外linux采用三级页表管理页：PGD / PMD / PTE，PTE指向page结构。对于页的管理涉及页缓存和页写回。页cache缓存的内存页面，在执行对磁盘操作之前会检查是否在cache中已经有了该页缓存。收集脏页的时候采用LRU 、LRU/N。linux使用address_space结构体来管理缓存项和页I/O操作。一个被缓存的文件只与一个address_space关联，但是可以有多个vm_area_struct，即一个物理页对多个虚拟页。从磁盘块的角度看，每个磁盘块也以块式I/O缓冲映射在物理内存中存储于页cache中，就是说实际上就只有页cache，但是里面存储磁盘块的缓存。脏页写回发生在低于设置的阀值时；脏页驻留内存超过一定时间时；用户主动调用sync()和fsync()方法时，内核由一组flusher线程完成该工作，这组线程周期性的被唤醒，这就需要system timer和内核线程的概念了。
遗留问题：其实linux才学了一点点，先列出看书的时候想到的不明白的问题和来自网络的答案，以后一定回来好好看看。
linux内核抢占和用户抢占：http://blog.csdn.net/gatieme/article/details/51872618
linux为何采用红黑树来维护进程管理：https://www.zhihu.com/question/20545708/answer/44370878
可重定位装入: http://blog.csdn.net/xinshen1860/article/details/22733953
可重入性 ：http://blog.csdn.net/acs713/article/details/20034511
异常、中断、陷入的区别 ： http://blog.chinaunix.net/uid-26931176-id-3216697.html
机器字长、存储字长： http://www.cnblogs.com/claremore/p/4802881.html
linux中的radix tree。
http://soft.chinabyte.com/os/339/11875339.shtml
http://blog.csdn.net/chenjiayi_yun/article/details/26242245
