Archive for 2012 年 4 月

pipe和fifo二三事

23 4 月, 2012

1.管道是什么?

管道是一种只存在于内存的特殊文件,没有磁盘文件与之对应。管道是通过虚拟文件系统pipefs而实现的,pipefs与proc、sysfs等特殊文件系统一样,只存在于内存中。另外,管道只能用于半双工通信。

2.pipe()一个管道意味着什么?

pipe()在pipefs文件系统中创建一个新的索引节点,同时创建两个file对象,一个file对象用于读操作,一个file对象用于写操作。pipe()最终将两个file对象对应的文件描述符返回给用户态进程,也就是向pipe()中传递的fd数组。

3.子进程execv()后是否还能继续共享父进程的管道?

子进程execv()后,不能再继续使用父进程创建的管道,因为子进程当前的上下文已经完全被可执行文件替换。如果要继续使用管道,子进程可以在execv()之前将两个文件描述符重定向到标准输入和输出。

4.描述管道的数据结构与索引节点的关系?

管道虽然是一种特殊文件,它仍然通过VFS框架中的inode来描述。由于VFS要对所有不同的文件进行抽象描述,因此inode只对所有文件的共性进行描述。inode中的i_pipe字段指向pipe_inode_info结构,该结构用于描述管道的特性。

5.写管道时写入的字节量与管道大小的关系?

管道缓冲区通常为一个单独的页框,因此大小默认为4096字节。如果两个或者多个进程并发的写入一个管道,那么任何少于4096字节的写操作都是原子的。但是,如果向管道写入大于管道缓冲区大小的数据,则写操作是可以分割的,也就是说多个进程的写操作可以交叉进行,此时应该注意进程的同步。

6.有名管道是什么?

有名管道是一种设备文件,有对应的磁盘索引节点。因为存在于磁盘上,因此可以被任何进程打开使用。有名管道是一种半双工通信方式。

7.ls | more 的大致执行过程?

在终端执行ls | more时,shell进程fork()出一个进程A用来执行上述命令。A进程调用pipe(),返回文件描述符fd1和fd2,分别用于读和写管道。进程A两次调用fork(),产生两个子进程。进程A关闭fd1和fd2。

对于第一个子进程,它调用dup2(fd2,1)将写文件描述符重定向到标准输出。接下来调用execv()系统调用执行ls程序,该程序将自己的输出写入管道。

对于第二个子进程,它调用dup2(fd1,0)将读文件描述符重定向到标准输入。接下来调用execv()系统调用执行more程序,该程序从管道中读取数据。

Linux物理内存管理概述

10 4 月, 2012

在内核态申请内存比在用户态申请内存要更为直接,它没有采用用户态那种延迟分配内存技术。内核认为一旦有内核函数申请内存,那么就必须立刻满足该申请内存的请求,并且这个请求一定是正确合理的。相反,对于用户态申请内存的请求,内核总是尽量延后分配物理内存,用户进程总是先获得一个虚拟内存区的使用权,最终通过缺页异常获得一块真正的物理内存。

1.物理内存的内核映射

IA32架构中内核虚拟地址空间只有1GB大小(从3GB到4GB),因此可以直接将1GB大小的物理内存(即常规内存)映射到内核地址空间,但超出1GB大小的物理内存(即高端内存)就不能映射到内核空间。为此,内核采取了下面的方法使得内核可以使用所有的物理内存。

1.高端内存不能全部映射到内核空间,也就是说这些物理内存没有对应的线性地址。不过,内核为每个物理页框都分配了对应的页框描述符,所有的页框描述符都保存在mem_map数组中,因此每个页框描述符的线性地址都是固定存在的。内核此时可以使用alloc_pages()和alloc_page()来分配高端内存,因为这些函数返回页框描述符的线性地址。

2.内核地址空间的后128MB专门用于映射高端内存,否则,没有线性地址的高端内存不能被内核所访问。这些高端内存的内核映射显然是暂时映射的,否则也只能映射128MB的高端内存。当内核需要访问高端内存时就临时在这个区域进行地址映射,使用完毕之后再用来进行其他高端内存的映射。

由于要进行高端内存的内核映射,因此直接能够映射的物理内存大小只有896MB,该值保存在high_memory中。内核地址空间的线性地址区间如下图所示:

从图中可以看出,内核采用了三种机制将高端内存映射到内核空间:永久内核映射,固定映射和vmalloc机制。

2.物理内存管理机制

基于物理内存在内核空间中的映射原理,物理内存的管理方式也有所不同。内核中物理内存的管理机制主要有伙伴算法,slab高速缓存和vmalloc机制。其中伙伴算法和slab高速缓存都在物理内存映射区分配物理内存,而vmalloc机制则在高端内存映射区分配物理内存。

伙伴算法

伙伴算法负责大块连续物理内存的分配和释放,以页框为基本单位。该机制可以避免外部碎片。

per-CPU页框高速缓存

内核经常请求和释放单个页框,该缓存包含预先分配的页框,用于满足本地CPU发出的单一页框请求。

slab缓存

slab缓存负责小块物理内存的分配,并且它也作为高速缓存,主要针对内核中经常分配并释放的对象。

vmalloc机制

vmalloc机制使得内核通过连续的线性地址来访问非连续的物理页框,这样可以最大限度的使用高端物理内存。

3.物理内存的分配

内核发出内存申请的请求时,根据内核函数调用接口将启用不同的内存分配器。

3.1 分区页框分配器

分区页框分配器 (zoned page frame allocator) ,处理对连续页框的内存分配请求。分区页框管理器分为两大部分:前端的管理区分配器和伙伴系统,如下图:

管理区分配器负责搜索一个能满足请求页框块大小的管理区。在每个管理区中,具体的页框分配工作由伙伴系统负责。为了达到更好的系统性能,单个页框的申请工作直接通过per-CPU页框高速缓存完成。

该分配器通过几个函数和宏来请求页框,它们之间的封装关系如下图所示。

这些函数和宏将核心的分配函数__alloc_pages_nodemask()封装,形成满足不同分配需求的分配函数。其中,alloc_pages()系列函数返回物理内存首页框描述符,__get_free_pages()系列函数返回内存的线性地址。

3.2 slab分配器

slab 分配器最初是为了解决物理内存的内部碎片而提出的,它将内核中常用的数据结构看做对象。slab分配器为每一种对象建立高速缓存。内核对该对象的分配和释放均是在这块高速缓存中操作。一种对象的slab分配器结构图如下:

可以看到每种对象的高速缓存是由若干个slab组成,每个slab是由若干个页框组成的。虽然slab分配器可以分配比单个页框更小的内存块,但它所需的所有内存都是通过伙伴算法分配的。

slab高速缓存分专用缓存和通用缓存。专用缓存是对特定的对象,比如为内存描述符创建高速缓存。通用缓存则是针对一般情况,适合分配任意大小的物理内存,其接口即为kmalloc()。

3.3 非连续内存区内存的分配

内核通过vmalloc()来申请非连续的物理内存,若申请成功,该函数返回连续内存区的起始地址,否则,返回NULL。vmalloc()和kmalloc()申请的内存有所不同,kmalloc()所申请内存的线性地址与物理地址都是连续的,而vmalloc()所申请的内存线性地址连续而物理地址则是离散的,两个地址之间通过内核页表进行映射。

vmalloc()的工作方式理解起来很简单:

1.寻找一个新的连续线性地址空间;

2.依次分配一组非连续的页框;

3.为线性地址空间和非连续页框建立映射关系,即修改内核页表;

vmalloc()的内存分配原理与用户态的内存分配相似,都是通过连续的虚拟内存来访问离散的物理内存,并且虚拟地址和物理地址之间是通过页表进行连接的,通过这种方式可以有效的使用物理内存。但是应该注意的是,vmalloc()申请物理内存时是立即分配的,因为内核认为这种内存分配请求是正当而且紧急的;相反,用户态有内存请求时,内核总是尽可能的延后,毕竟用户态跟内核态不在一个特权级。

后记:本文将Linux内核中物理内存管理这部分内容进行框架性总结,对内存管理感兴趣的同学可以从伙伴算法,slab和vmalloc()三个角度去了解和学习物理内存管理。

基于CFS算法的schedule()源码分析

5 4 月, 2012

内核中的调度算法在不断变化,2.4内核中的调度器是在所有的进程中选择优先级最高的进程,2.6内核前期的调度器是基于O(1)算法的,而2.6.23版本之后的内核采用CFS调度算法,并同时对调度器进行了比较大的改善。内核主要是引入了调度器类来增加调度器的可扩展性。调度器类将各种调度策略模块化,封装了对不同调度策略的具体实现。

内核中对进程调度的方法有两种,其一为周期性调度器(generic scheduler),它对进行进行周期性的调度,以固定的频率运行;其二为主调度器(main scheduler),如果进程要进行睡眠或因为其他原因主动放弃CPU,那么就直接调用主调度器。

内核的主调度器是通过schedule()实现的,该函数的主要工作就是挑选下一个应该被调度的进程next。
该函数首先禁止内核抢占,并且依次获取当前CPU编号cpu、当前CPU对应的运行队列rq、当前进程的切换次数switch_count以及当前进程的描述符prev。

asmlinkage void __sched schedule(void)
{
	struct task_struct *prev, *next;
	unsigned long *switch_count;
	struct rq *rq;
	int cpu;

need_resched:
	preempt_disable();
	cpu = smp_processor_id();
	rq = cpu_rq(cpu);
	rcu_sched_qs(cpu);
	prev = rq->curr;
	switch_count = &prev->nivcsw;

	release_kernel_lock(prev);
need_resched_nonpreemptible:

	schedule_debug(prev);

	if (sched_feat(HRTICK))
		hrtick_clear(rq);

接下来通过update_rq_clock()更新就绪队列上的时钟,接着通过clear_tsk_need_resched()清除当前进程prev的重新调度标志TIF_NEED_RESCHED。

	raw_spin_lock_irq(&rq->lock);
	update_rq_clock(rq);
	clear_tsk_need_resched(prev);

如果当前进程是可中断睡眠状态(可运性状态TASK_RUNNING宏的值为0),但它却收到了某个唤醒它的信号,那么当前进程的标志被更新为TASK_RUNNING,等待再次被调度。否则,通过deactivate_task()将当前进程prev从就绪队列中删除。

这里的deactivate_task()根据调度类的不同实现也有所不同,但这些差异对主调度器是透明的,因为调度器类在各种调度实例和调度器之间起到了连接作用。该函数的核心语句即为:

p->sched_class->dequeue_task(rq, p, sleep);

sched_class是进程描述符中描述当前进程所属调度类的字段,通过这个字段回调钩子函数dequeue_task()。

	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
		if (unlikely(signal_pending_state(prev->state, prev)))
			prev->state = TASK_RUNNING;
		else
			deactivate_task(rq, prev, 1);
		switch_count = &prev->nvcsw;
	}

	pre_schedule(rq, prev);

	if (unlikely(!rq->nr_running))
		idle_balance(cpu, rq);

通过put_prev_task()将prev进程重新插入到就绪队列合适的位置中。再通过pick_next_task()在当前的就绪队列中挑选下一个应该被执行的进程next。这两个函数都属于调度器类中的钩子函数,它们的具体实现根据调度实例的不同而不同。

	put_prev_task(rq, prev);
	next = pick_next_task(rq);

有时候,调度器所选的下一个被执行的进程恰好就是当前进程,那么调度器就不必耗费精力去执行上下文切换,但这种情况不是经常发生的。如果prev和next不是同一个进程,那么先通过sched_info_switch()更新两个进程描述符的相关字段,并且更新可运行队列的相关字段。

接下来调用context_switch()进行prev和next两个进程的上下文切换,该函数由一段汇编代码组成。

	if (likely(prev != next)) {
		sched_info_switch(prev, next);
		perf_event_task_sched_out(prev, next);

		rq->nr_switches++;
		rq->curr = next;
		++*switch_count;

		context_switch(rq, prev, next); /* unlocks the rq */
		/*
		 * the context switch might have flipped the stack from under
		 * us, hence refresh the local variables.
		 */
		cpu = smp_processor_id();
		rq = cpu_rq(cpu);
	} else
		raw_spin_unlock_irq(&rq->lock);

切换完毕后,当前的进程就是新选择的进程,它会开始执行。而被切换出去的进程重新运行时会从切换函数的下一条语句开始执行。

	post_schedule(rq);

	if (unlikely(reacquire_kernel_lock(current) < 0)) { 		prev = rq->curr;
		switch_count = &prev->nivcsw;
		goto need_resched_nonpreemptible;
	}

	preempt_enable_no_resched();
	if (need_resched())
		goto need_resched;
}

根据上述对主调度器函数源码的分析,可以总结出主调度器的主要功能如下:

1.获取当前进程的描述符以及本地CPU的运行队列

2.将当前进程prev放入可运行队列中,等待下一次被重新调度

3.在当前的可运行队列中选取下一个被调度的新进程next

4.从当前进程切换到新进程

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key