Linux2.6进程调度分析

1、Linux 2.6 进程调度分析,.杨帆 王凯 左尧 严丹. 322小组,源码阅读方法,在分析源码前，先从整体出发，知道该操作系统的工作原理 弄清Linux内核源代码的分布情况，即目录结构分析 随时Baidu 阅读代码的方法：纵向与横向。 纵向：顺着程序的执行顺序逐步进行； 横向：就是分模块进行 两种方法应交替进行,源码阅读工具 SourceInsight,想看变量某一定义，先把光标定位于该变量，然后点击工具条上的相应 选项，该变量的定义就显示出来，同样可以用该方法查看函数定义。 工具下载： 可在课程BBS里找到该地址,Source Insight 简介,该软件符合优秀软件的设计标准：用户不需

2、要专门的学习就能使用。,Linux 2.6调度系统的特性(1),继承和发扬 2.4 版调度器的特点： 交互式作业优先 轻载条件下调度/唤醒的高性能 公平共享 基于优先级调度 高 CPU 使用率 SMP 高效亲和 实时调度和 cpu 绑定等调度手段,Linux 2.6调度系统的特性(2),在此基础之上的新特性： O(1)调度算法，调度器开销恒定（与当前系统负载无关），实时性能更好 高可扩展性，锁粒度大幅度减小 新设计的 SMP 亲和方法 优化计算密集型的批处理作业的调度 重载条件下调度器工作更平滑 子进程先于父进程运行等其他改进 增加了对可抢占内核的支持,进程的几个要素的精僻描述,剧本：依赖的程

3、序。不同剧场可以演出同一个剧本-一个程序可以有多个进程。 私有财产：专用的系统堆栈和独享的用户空间 户口登记表：task_struct对进程的描述 （如果没有独享的用户空间，只能被称为线程）。,主要分析文件,/include/linux/sched.h /kernel/sched.c,进程控制块task_struct,类似uC/OS-II中的OS_TCB ，Linux的进程控制块task_struct包含有进程的描述信息、控制信息以及资源信息，是进程的静态描述 进程与任务：似乎是同一回事。Linux文档把process和 task的概念未加区分。 为了方便和出于个人习惯，后文在不会造成误解的条

4、件下，对task_struc也称为任务（进程）控制块或TCB。,进程控制块应包含哪些内容,进程标识符 优先级 堆栈空间 进程状态,任何操作系统的TCB都应该直接或间接地定义出这四个方面,task_struct定义在 /kernel/include/linux/sched.h 的第437行-587行,task_struct重要成员state,volatile long state; /* -1 unrunnable, 0 runnable, 0 stopped */,2.6与2.4的宏定义数值上有较大的差别 2.6新增了两种状态：TRACED、DEAD TASK_DEAD是表示已经退出且不需父进

5、程回收的进程的状态。 TASK_TRACED供调试使用（似乎有STOPPED有点儿重复？）,TASK_ZOMBIE一个已经终止的但仍保留有任务结构的进程（已经死了，户口未注销）。 TASK_RUNNING 就绪态(准确的说应该是task_runable) TASK_INTERRUPTIBLE、TASK_UNITERRUPTIBLE 不同深度的睡眠态 TASK_STOPPED 描述一个已经停止的进程，当进程接收到一个特殊信号或被使用ptrace系统调用的进程监控，并将控制权交给监控进程（我的理解就是断点调试）。,关于state的volatile修饰,据说是：“区分C程序员和嵌入式系统程序员的最基

6、本的问题” 一个变量加上修饰符volatile后：说明这个变量可能会被意想不到地改变，编译器就不会去假设这个变量的值了。这样，优化器在用到这个变量时必须每次都小心地重新读取这个变量的值(From Memory)，而不是使用保存在计算单元寄存器里的备份。 举例：计数器的寄存器， 多线程， 中断,Linux2.4任务堆栈,union task_union /cxl: 分配/回收/访问 struct task_struct task; unsigned long stackINIT_TASK_SIZE/sizeof(long); ; 课堂上的讲述：,2.4版中,内核在创建进程时,为每个进程分配两个连

7、续的物理页面(8KB),它的顶端(低地址部分)用作存储进程的task_struct结构(约1KB),剩下的约7KB就是进程的系统空间堆栈,内核可以通过栈寄存器指针ESP快速地访问该进程. 在Linux 2.6中,这两个页面顶端存放的不再是进程的整个task_struct结构,而是task_struct中的thread_info, task_struct的大部分信息保存在栈外,通过thread_info的task指针可以方便地访问到.,Linux2.6任务堆栈存储结构,在任务的系统堆栈顶部放入的是该任务的thread_info记录，而不是TCB,一个或两个物理页面 4/8k,系统堆栈空间,inc

8、lude/asm-i386/thread_info.h 中对thread_info的定义,thread_info是描述任务的一个重要结构体，当前进程运行的一些环境信息。,thread_info的重要成员,task指针指向其对应的任务控制块 preempt_count是用来表示内核能否被抢占的使能成员。如果它大于0，表示内核不能被抢占；如果等于0，则表示内核处于安全状态（即没有加锁），可以抢占。 flags里面有一个TIF_NEED_RESCHED位，如果此标志位为1，则表示应该尽快启动调度器。,有趣的0长度数组,_u8supervisor_stack0; 并不是每个编译器都支持0长度数组。 G

9、CC支持，方便计算对象的大小。 该数组没有占用结构体的空间，所以thread_info长度为52，数组空间需要以后用malloc()来分配。 该数组占据的空间和系统堆栈空间重叠，从该数组的位置和该数组的命名上推断，它就是指的该进程的系统堆栈。,thread_info和硬件相关,在asm-arm中的定义,其中，cpu_context用来保存CPU上下文。,task_struct的thread_info指针,struct thread_info *thread_info；,thread_info,task_struct,个人认为thread_info和task_struct一样，是任务的一个重要记

10、录，两者互相关联，并没有从属关系。,通过thread_info指针，我们可以把TCB和它的堆栈联系起来,arm中的current()定义,/include/asm-arm/current.h中实现current(),/include/asm-arm/thread_info.h中实现current_thread_info(),intprio,static_prio,prio是进程的动态优先级，是调度器选择候选进程next的主要依据 static_prio则是进程的静态优先级, 应该是进程开始时从父程继承来的 kernel/sched.c中定义了两个宏来完成将nice转换到prio的取值区间和将p

11、rioity转换到nice取值区间。 可见prioity和nice的关系是： priority = MAX_RT_PRIO+nice+20 进程优先级分实时和非实时两部分，二者不可逾越。,run_list 成员,struct list_head run_list; include/linux/list.h定义了一种抽象的双向链表struct list_head， 通过它可以将任意类型的结构体链接到一起。task_struct也是通过这种方式链接起来的。,activated成员,int activated;表示进程因什么原因进入就绪态，这一原因会影响到调度优先级的计算。activated 有四个

12、值： -1，进程从 TASK_UNINTERRUPTIBLE 状态被唤醒； 0，缺省值，进程原本就处于就绪态； 1，进程从 TASK_INTERRUPTIBLE 状态被唤醒，且不在中断上下文中； 2，进程从 TASK_INTERRUPTIBLE 状态被唤醒，且在中断上下文中。 TASK_INTERRUPTIBLE 状态进程由中断激活，则该进程最有可能是交互式的，因此，置 activated=2；否则置activated=1。 如果进程是从 TASK_UNINTERRUPTIBLE 状态中被唤醒的，则 activated=-1（在try_to_wake_up()函数中）。 activated 变

13、量的具体含义和使用见优化了的优先级计算方式。,其余的重要成员，诸如：进程号，父进程指针等，老师已经讲得很详细，不再冗述,就绪进程队列 runqueue,定义在/kernel/sched.c 中，第217行289行 2.6内核为每CPU的数据结构，每个处理器都维护一个自己的就绪队列。相对2.4公共的就绪队列而言，这将大大减小竞争，具有更好并行计算能力。,runqueue 源代码,队列进程个数nr_running,unsignedlongnr_running ； 本就绪队列中就绪进程的个数. 它是active队列和expired队列就绪进程个数的和: nr_running= active-nr_a

14、ctive +expired-nr_active,两个子队列active、expired,prio_array_t *active, *expired, arrays2; 就绪队列根据时间片是否被用完分为了active队列和expired队列。,queue是指定优先级进程list的指针,如queuei就是priority为 i 的进程的指针。 bitmap是一张优先级的位图，或者可以说的位数组，每一位代表了一个优先级（类似uC/OS-II）。 MAX_PRIO指的是优先级的数量.,其结构为,为什么要+1+7而不是直接+8 ? 0 MAX_PRIO之间，共了MAX_PRIO+1个优先级，所以要加

15、1 被除数为8, 加7是为了向上取整。 同理，被除数为sizof(long)时，先加上sizeof(long)-1,也是为了上取整。 这样就求出了需要的长整型变量数。 问题：为什么不用char，而要用long?,#define MAX_PRIO(MAX_RT_PRIO + 40) #define MAX_RT_PRIO MAX_USER_RT_PRIO #define MAX_USER_RT_PRIO100,include/asm-arm/bitops.h中寻找最高优先级函数,_ffs()用来查找一个长整型变量最右边的1是第几位,include/asm-i386/bitops.h中寻找最高优先级函数,按宏定义，会生成160bit的位数组（5个long)，构成一张表。 每一位对应一个