linux内核学习小结(中/下)

Question

本帖最后由 chishanmingshen 于 2011-06-09 12:10 编辑

linux内核学习小结(中) by chishanmingshen

1.同步
在单cpu只有在进程主动要求睡眠或者返回进程空间前才会切到其它进程.
而smp则要考虑多个cpu同时访问共享数据了,更何况还有内核的抢占特性.
临界区是只能一个程序实例进入的代码段,
防止多个程序实例同时进入同一个临界区就称为同步.
内核中并发的情况:
1.中断/软中断/tasklet都会打断当前执行的代码
2.内核抢占
3.smp
4.进程主动放弃执行

同步的解决方法:
1.指令原子化
2.自旋锁,短时间的持有,避免进程切换的开销.用于smp.
如果在中断程序中使用自旋锁, 需要关本地中断.防止自旋锁的递归.
如果下半部和进程有共享数据,则在进程中需要加锁的同时,还要禁止下半部.因为
下半部会抢占进程.
如果中断处理程序和下半部有共享数据,则在下半部需要加锁的同时需要禁止中断.
同类tasklet之间的共享数据不需要保护,因为在同一个cpu上不支持tasklet抢占tasklet,在smp
上其它cpu不能运行跟本cpu相同类型的tasklet.
不同类tasklet之间如果有共享数据,则需要保护,即要先获得自旋锁来禁止其它cpu,但是
本cpu不需要禁止下半部,因为本cpu上不能有tasklet抢占tasklet.
如果软中断之间要共享数据,要用自旋锁,因为同种类型的软中断可能同时运行在多个cpu上,但是
本cpu上不需要禁止下半部,因为本cpu上不能有软中断抢占软中断.
3.信号量,长时间的持有,可以睡眠.
有互斥信号量/计数信号量.
自旋锁和信号量的区别:
在中断上下文等不能sleep的路径中就该用自旋锁,在可能sleep的路径中可以用信号量.
4.禁止抢占
禁止本地cpu抢占可以保护本cpu的多个内核路径中的共享数据.这个是通过抢占计数器实现的.
5.屏障
屏蔽编译器的优化,防止编译器对指令做重新排列导致问题.
读屏障,即该屏障前后的读已经隔离开.
写屏障,即该屏障前后的写一定隔离开.

2.定时器
1个tick即2次时钟中断之间的间隔,值等于1/hz.如果hz为1000,则tick为1ms.
缩短tick,有很多好处,比如提高调度的精确度,提高时间的精确度等.
但是也有坏处,增加了系统切换的开销.
jiffies变量是一个无符号整数,记录开机后记录的tick总和,即相对时间.
在周期性触发的时钟中断的处理函数中,要做:
给jiffies++,定时器打软中断标记(将到期的定时器在软中断中处理),检查调度,一些统计工作.
(在该中断处理程序执行时不一定很准确有1个tick的间隔,可能更长!)
内核定时器不是周期性的,都是执行一次即销毁.所以需要在销毁前再建.
删除定时器需要注意可能需要同步删除,即其它cpu上可能正在执行该定时器函数.
因为是在软中断中处理定时器函数,所以如果有与中断共享的数据则需要保护.

长延时:可以死循环,直到耗尽设置的tick数;可以sleep,当设置的时间到达时该进程会
被唤醒,注意此时一定不能在中断中或有锁时sleep且该进程应该设置为中断睡眠状态或不
可中断睡眠状态.
短延时:使用忙等来实现等待时间小于1个tick的情况.
依据是内核已经通过测试获得了一个循环耗费的时间.

内核定时器的实现
5个队列:一个2^8和4个2^6.
所以共255+64*4个定时器队列.
将超时时间为255/2^14/2^20/2^26/2^32个节拍内的定时器,分别可以加到
那5个个对应的队列中去.
每过一个节拍,都依据全局的节拍数变量timers_jiffies处理:
在255个队列中处理index+1中的定时器(index是上次处理的index),
其实也仅此2^8个队列能得到处理.
如果timers_jiffies过了2^14个节拍,则将2^6个队列前移.通过这种方法,
慢慢地,逐一地移到2^8个队列中去.

3.文件系统
VFS主要有4个对象类型:超级块;索引节点;目录项;文件.
超级块对象,标识哪种文件系统.
索引节点对象,标识一个文件或一个目录.
目录项对象,标识路径的一个部分.只有这个在磁盘中没有对应的存储,是内存中才创建的.
一个目录项对象把路径中一个分量和一个索引节点联系起来,其实就是缓存一个分量,以后
可以根据目录项对象直接找到对应的索引节点,该索引节点可能是目录也可能是文件.一个索引节点
可能有多个目录项对象对应,因为一个文件(目录也一样)可能有多个名字.
文件对象,标识进程打开的文件.
随机访问的设备,即块设备.
按字符流的方式有顺序地访问的设备,即字符设备.
块设备的最小单位是一个扇区,一个块包括一个或多个扇区,但是不能超过一个页面.
举例:一个read()操作,读块设备数据
1.用户进程用系统调用read(),进入VFS.
2.此时VFS计算出该数据对应的逻辑块号,如果VFS发现已经有数据缓存,则直接返回.
3.如果VFS(虚拟文件系统)中没有,则需要由映射层将逻辑块号转为物理块号
(这个关系由存在磁盘中的该文件的索引节点结构可以得知),
然后调用一个具体的块设备的函数.
4.通用层,发io操作请求,即bio结构体.
5.io调度层,将所有的io请求进行合并和排序.
6.驱动层,块设备驱动程序向硬件接口发送命令.

io调度算法
io调度程序就是管理下发给块设备的请求队列.通过合并和排序来减少
磁盘寻址时间,从而提供性能.
合并就是将多次相近的请求合并成一个请求.
排序就是使整个请求队列成一个增长队列,从而使磁盘头一直走直线,不是
反复折回.
1.linus电梯算法
能执行合并和排序,但是有一个饥饿问题,有些请求会由于队列中已经有一些
驻留时间很长的请求而不去插入合适的位置,而是插入到尾部.这样是为了解决
某些驻留时间过长得不到调度的问题,但有时又使自己这类请求得不到处理,
最终还是导致饥饿.
2.Deadline scheduler
每个请求(属于一个队列)都有一个超时时间,解决linus电梯算法的某些请求的饥饿问题.
一般给读请求fifo队列比写请求更短的超时时间.这样可以让读操作有更好性能,
而读操作的响应时间做系统系能影响最大.
3.Anticipatory scheduler
和Deadline scheduler基本一样,不同的地方是一个请求提交之后并不立即处理,
而是等待6ms,因为可能下次的请求和这次可以合并处理.
这就是预测的含义.
4.Completely Fair Queuing
对每个进程都维护一个队列,各个进程发的请求会以轮循方式处理。
也就是提供了对进程级的公平.
5.NOOP
除了合并,其它都是fifo.这是为随机设备准备的,因为它们就不需要排序.

更多文章在我的博客上:
http://chishanmingshen.blog.chinaunix.net

Answer 1

本帖最后由 chishanmingshen 于 2011-06-13 22:33 编辑

补上
linux内核学习小结(下)
http://blog.chinaunix.net/space. ... =blog&id=361439

linux内核学习小结(下)-内存管理部分 by chishanmingshen
这个系列的最后就差内存管理这部分了,本文纯属个人理解,
如有错误,还请指正.
1.内存区
内核用page结构表示所有的物理页.
由于2个硬件缺陷问题导致分为3种类型的内存区.
2个缺陷是
1.一些硬件只能使用<16M的内存做DMA
2.一些硬件的物理地址范围超过内核的虚拟地址范围
3种类型内存区是(以物理内存大于896M为例,看完全文会明白为何这个是依赖于实际物理内存)
1.ZONE_DMA 0..16M
2.ZONE_NORMAL 16M..896M
3.ZONE_HIGHMEM >896M
ZONE_DMA和ZONE_NORMAL也称为低端内存
ZONE_HIGHMEM即传说中的高端内存
2.申请函数
内核申请内存的函数有3个
1.alloc_pages()返回的是page的指针,故支持高端内存.
2.__get_free_pages() 返回的是线性地址,故只用于低端内存.
3.kmalloc()以字节为单位,内部也是调用了__get_free_pages(),
故也只支持低端内存.注意的是可能分配的内存比请求地多,
因为它是用的slab实现的.
分配器标志有3类:行为/区/类型修饰符.
1.行为描述符,比如__GFP_WAIT标识可以睡眠.(GFP就是get free page的缩写)
2.区描述符,
__GFP_DMA标志标识仅从ZONE_DMA区中申请.
__GFP_HIGHMEM标志标识从ZONE_HIGHMEM(优先)或ZONE_NORMAL中申请.
不指定标志表示从ZONE_NORMAL或ZONE_DMA中申请.
对于__GFP_HIGHMEM标志,其实只能用于alloc_pages(),因为仅它支持高端内存.
3.类型是前2个的组合.
kmalloc()中使用的GFP_KERNEL,可以睡眠,只从低端内存中申请.
故只能用在进程上下文中.
而kmalloc()中使用的GFP_ATOMIC,不能睡眠,只从低端申请.
在不能睡眠时(中断/软中断/tasklet),只能用此标志.
可见kmalloc()只从低端申请.
GFP_DMA标志,表示只能从ZONE_DMA中申请,用于设备驱动程序中.
附:
GFP_ATOMIC的含义
The allocation is high priority and must not sleep.
This is the flag to use in interrupt handlers,
in bottom halves, while holding a spinlock, and in other situations where you cannot sleep
GFP_KERNEL的含义
This is a normal allocation and might block.
This is the flag to use in process context code when it is safe to sleep.
The kernel will do whatever it has to in order to obtain the memory requested by the caller.
This flag should be your first choice.

3.关于高端内存
使用高端内存的2个途径
1.进程中调用alloc_pages(GFP_HIGHUSER)为用户空间分配内存.
2.进程上下文中,故可能会睡眠,常调vmalloc(),最终还是调用alloc_pages(),故
常用高端内存.
3.而在内核中,因为它的睡眠性极少用vmalloc(),但是当装载新模块需要申请大内存时会用到.
高端内存的映射有3种形式
1.永久,使用主内核页表的一页页表.
调用kmap完成映射.永久映射的个数是有限的.故会睡眠(睡前设置为不可中断的sleep状态等待),
因此kmap()只能用在进程上下文中.
2.临时,不会睡眠,故可以用在中断上下文中, 但是数量很少.
是一组保留的映射,被申请用作新建的临时映射.
kmap_atomic()建立临时映射,
映射时会禁止本cpu的中断,因为每个映射对于本cpu都是唯一的,如果切换会错误地覆盖.
而释放临时映射是空操作,因为本来就是在直接覆盖.
3.非连续
vmalloc()有3种非连续类型:
VM_ALLOC物理内存和线性地址同时申请,注意此时指定__GFP_HIGHMEM,故
不限于HIGHMEM,也可以用NORMAL;VM_MAP仅申请线性地址;
VM_IOREMAP仅申请线性地址,其物理内存一般都是超高的.
4.关于slab
slab是一种通用小块数据结构缓存机制,使用它的原因是
1.频繁分配释放,故需要缓存
2.频繁的结果是导致内存碎片,即找不到大的连续内存.为了避免,需要将空闲内存连续存放.
可见,slab主要还是解决连续性这个问题的,至于内碎片的浪费,并没避免.
3.回收后即可立即使用,这样提高了效率.
4.对对象着色,这样防止多个对象映射到同一个高速缓存行时,导致切换对象访问引起的颠簸.
每种slab对应一个高速缓存.
申请slab,其实是调用__get_free_pages()得到内存的,
故slab申请的空间也是从低端内存得到的.
kmalloc()其实是基于slab的,使用了一组通用的高速缓存.

5.最后
还是得附上code基础上聊聊高端内存,因为linux的内存管理中,理解高端内存很重要.
内核要管理4G空间,但是其线性空间仅为1G,这个是为了留出3G给用户空间的.
如果1G全部直接映射,则内核仅能寻址1G空间了,所以又留出128M给动态映射.
这样896M的直接映射+128M的动态映射(重复用)就够4G了.所有物理内存对应的
vm_page肯定都在直接映射区,但是如果访问的话就需要MMU准备映射了.
高端内存是指高于896M的部分,其有3种映射方式:
1.动态
通过vmalloc()申请,获得连续的线性空间.
2.永久
通过alloc_page()有可能是高端内存,此时需要获得PKMAP_BASE到FIXADDR_START
的4M(即pkmap_page_table代表一页页表)的永久映射,
通过kmap()即可将该page映射到该线性空间中.
特点是可能睡眠,因为数量有限.
3.临时
即FIXADDR_START到FIXADDR_TOP之间的空间,用kmap_atomic()获得.
每个cpu都有自己的临时映射空间,独立的.这部分空间又分为分page,每个page代表一个
功能.
特点就是禁止本cpu中断,不睡眠,可直接使用,其实就是直接覆盖上一个.
max_low_pfn = max_pfn;
#ifdef CONFIG_HIGHMEM
highstart_pfn = highend_pfn = max_pfn;
if (max_pfn > MAXMEM_PFN) {
  highstart_pfn = MAXMEM_PFN;
  printk(KERN_NOTICE "%ldMB HIGHMEM available.\n",
   pages_to_mb(highend_pfn - highstart_pfn));
}
#endif
可见:
刚开始把所有物理内存a都看做低端内存,
然后看a<=896M,则高端内存起始为a,终止为a.
如果a>896M,则高端起始为896M,终止为a.
所以高端内存是一个物理内存的概念.

#ifdef CONFIG_HIGHMEM
highmem_start_page = mem_map + highstart_pfn;
max_mapnr = num_physpages = highend_pfn;
#endif
high_memory = (void *) __va(max_low_pfn * PAGE_SIZE);
可见:
high_memory即高端内存, 是从max_low_pfn(16M<=max_low_pfn<=896M)开始的,
所以高端内存是从b(16M<=b<=896M)开始的,具体依赖于实际的内存大小.

#define VMALLOC_OFFSET (8*1024*1024)
#define VMALLOC_START (((unsigned long) high_memory + 2*VMALLOC_OFFSET-1) & \
      ~(VMALLOC_OFFSET-1))
可见:
VMALLOC_START是从high_memory+空洞(8M<空洞<16M)的地方开始的.
同样,在各个vmallco()分配得到的各个线性空间之间也有8k大小的空洞.
这些都是为了防止越界的.

种种分析推出最后的结论:
内核映像和mem_map[]开始于虚拟空间的3G+16M处,前16M用于DMA.
vmalloc()的作用就是将不连续物理内存映射到连续线性空间,
VMALLOC_RESERVE大小(128M)的空间就用于vmalloc()/永久/临时映射使用,
虽然在a<896M的情况下,内核其实可以有>128M的保留线性空间.
所以,
高端内存起址为b(896M>=b>=16M),但保留区间大小恒为128M,
而这就间接导致ZONE_NORMAL区的大小是0M到(896-b)M.

Answer 2

good

Answer 3

总结的还不错，中午没事的时候看一下。

Answer 4

感謝大神，學習了!!

Answer 5

很好的总结，谢谢分享