Linux2.6进程调度分析. . . .杨帆杨帆 王凯王凯 左尧左尧 严丹严丹. . . . 322322322322小组小组小组小组源码阅读方法在分析源码前，先从整体出发，知道该操作系统的工作原理弄清Linux内核源代码的分布情况，即目录结构分析随时Baidu阅读代码的方法：纵向与横向。纵向：顺着程序的执行顺序逐步进行；横向：就是分模块进行两种方法应交替进行源码阅读工具SourceInsight想看变量某一定义，先把光标定位于该变量，然后点击工具条上的相应选项，该变量的定义就显示出来，同样可以用该方法查看函数定义。工具下载：http:/home.ustc.edu.cn/phanyoung/index_in.html可在课程BBS里找到该地址SourceInsight简介该软件符合优秀软件的设计标准：用户不需要专门的学习就能使用。Linux 2.6调度系统的特性(1)继承和发扬 2.4 版调度器的特点： 交互式作业优先 轻载条件下调度/唤醒的高性能 公平共享 基于优先级调度 高 CPU 使用率 SMP 高效亲和 实时调度和 cpu 绑定等调度手段Linux 2.6调度系统的特性(2)在此基础之上的新特性：O(1)调度算法，调度器开销恒定（与当前系统负载无关），实时性能更好 高可扩展性，锁粒度大幅度减小 新设计的 SMP 亲和方法 优化计算密集型的批处理作业的调度 重载条件下调度器工作更平滑 子进程先于父进程运行等其他改进增加了对可抢占内核的支持进程的几个要素的精僻描述剧本：剧本：依赖的程序。不同剧场可以演出同一个剧本-一个程序可以有多个进程。私有财产：私有财产：专用的系统堆栈和独享的用户空间户口登记表：户口登记表：task_struct对进程的描述（如果没有独享的用户空间，只能被称为线程）。主要分析文件/include/linux/sched.h/kernel/sched.c进程控制块task_struct类似uC/OS-II中的OS_TCB，Linux的进程控制块task_struct包含有进程的描述信息、控制信息以及资源信息，是进程的静态描述进程与任务：似乎是同一回事。Linux文档把process和task的概念未加区分。为了方便和出于个人习惯，后文在不会造成误解的条件下，对task_struc也称为任务（进程）控制块或TCB。进程控制块应包含哪些内容进程标识符优先级堆栈空间进程状态任何操任何操作系统作系统的的TCBTCB都应该都应该直接或直接或间接地间接地定义出定义出这四个这四个方面方面task_struct定义在/kernel/include/linux/sched.h的第437行-587行task_struct重要成员statevolatilelongstate;/*-1unrunnable,0runnable,0stopped*/2.6与2.4的宏定义数值上有较大的差别2.6新增了两种状态：TRACED、DEADTASK_DEAD是表示已经退出且不需父进程回收的进程的状态。TASK_TRACED供调试使用（似乎有STOPPED有点儿重复？）TASK_ZOMBIE一个已经终止的但仍保留有任务结构的进程（已经死了，户口未注销）。TASK_RUNNING就绪态(准确的说应该是task_runable)TASK_INTERRUPTIBLE、TASK_UNITERRUPTIBLE不同深度的睡眠态TASK_STOPPED描述一个已经停止的进程，当进程接收到一个特殊信号或被使用ptrace系统调用的进程监控，并将控制权交给监控进程（我的理解就是断点调试）。关于state的volatile修饰据说是：“区分区分C程序员和嵌入式系统程序员程序员和嵌入式系统程序员的最基本的问题的最基本的问题”一个变量加上修饰符volatile后：说明这个变量可能会被意想不到地改变，编译器就不会去假设这个变量的值了。这样，优化器在用到这个变量时必须每次都小心地重新读取这个变量的值(FromMemory)，而不是使用保存在计算单元寄存器里的备份。举例：计数器的寄存器，多线程，中断Linux2.4任务堆栈uniontask_union/cxl:分配/回收/访问structtask_structtask;unsignedlongstackINIT_TASK_SIZE/sizeof(long);课堂上的讲述：http:/staff.ustc.edu.cn/xlanchen/EmbeddedOperatingSystems2008Spring/sched.h.html2.4版中,内核在创建进程时,为每个进程分配两个连续的物理页面(8KB),它的顶端(低地址部分)用作存储进程的task_struct结构(约1KB),剩下的约7KB就是进程的系统空间堆栈,内核可以通过栈寄存器指针ESP快速地访问该进程.在Linux2.6中,这两个页面顶端存放的不再是进程的整个task_struct结构,而是task_struct中的thread_info,task_struct的大部分信息保存在栈外,通过thread_info的task指针可以方便地访问到.Linux2.6任务堆栈存储结构在任务的系统堆栈顶部放入的是该任务的thread_info记录，而不是TCB一一个个或或两两个个物物理理页页面面4/8k系系统统堆堆栈栈空空间间thread_info52字节include/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长度数组。GCC支持，方便计算对象的大小。该数组没有占用结构体的空间，所以thread_info长度为52，数组空间需要以后用malloc()来分配。该数组占据的空间和系统堆栈空间重叠，从该数组的位置和该数组的命名上推断，它就是指的该进程的系统堆栈。thread_info和硬件相关在asm-arm中的定义其中，cpu_context用来保存CPU上下文。task_struct的thread_info指针structthread_info*thread_info；thread_infothread_infotask_structtask_struct个人认为thread_info和task_struct一样，是任务的一个重要记录，两者互相关联，并没有从属关系。通过thread_info指针，我们可以把TCB和它的堆栈联系起来arm中的current()定义/include/asm-arm/current.h中实现current()/include/asm-arm/thread_info.h中实现current_thread_info()intprio,static_prioprio是进程的动态优先级，是调度器选择候选进程next的主要依据static_prio则是进程的静态优先级,应该是进程开始时从父程继承来的kernel/sched.c中定义了两个宏来完成将nice转换到prio的取值区间和将prioity转换到nice取值区间。可见prioity和nice的关系是：priority=MAX_RT_PRIO+nice+20进程优先级分实时和非实时两部分，二者不可逾越。run_list成员structlist_headrun_list;include/linux/list.h定义了一种抽象的双向链表structlist_head，通过它可以将任意类型的结构体链接到一起。task_struct也是通过这种方式链接起来的。activated成员intactivated;表示进程因什么原因进入就绪态，这一原因会影响到调度优先级的计算。activated有四个值：-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变量的具体含义和使用见优化了的优先级计算方式。其余的重要成员，诸如：进程号，父进程指针等，老师已经讲得很详细，不再冗述就绪进程队列runqueue定义在/kernel/sched.c中，第217行289行2.6内核为每CPU的数据结构，每个处理器都维护一个自己的就绪队列。相对2.4公共的就绪队列而言，这将大大减小竞争，具有更好并行计算能力。runqueue 源代码队列进程个数nr_runningunsignedlongnr_running；本就绪队列中就绪进程的个数.它是active队列和expired队列就绪进程个数的和:nr_running=active-nr_active+expired-nr_active两个子队列active、expiredprio_array_t*active, *expired,arrays2;就绪队列根据时间片是否被用完分为了active队列和expired队列。queue是指定优先级进程list的指针,如queuei就是priority为i的进程的指针。bitmap是一张优先级的位图，或者可以说的位数组，每一位代表了一个优先级（类似uC/OS-II）。MAX_PRIO指的是优先级的数量. 其结构为为什么要+1+7而不是直接+8?0MAX_PRIO之间，共了MAX_PRIO+1个优先级，所以要加1被除数为8,加7是为了向上取整。同理，被除数为sizof(long)时，先加上sizeof(long)-1,也是为了上取整。这样就求出了需要的长整型变量数。问题：为什么不用char，而要用long?#defineMAX_PRIO(MAX_RT_PRIO+40)#defineMAX_RT_PRIO MAX_USER_RT_PRIO#defineMAX_USER_RT_PRIO100include/asm-arm/bitops.h中寻找最高优先级函数_ffs()用来查找一个长整型变量最右边的1是第几位include/asm-i386/bitops.h中寻找最高优先级函数按宏定义，会生成160bit的位数组（5个long)，构成一张表。每一位对应一个优先级，该优先级有active状态（时间片未用完）的，在相应位置1,否则置0。从右向左位扫描1，得到优先级最高（值最小）的优先级号k进入queuek数组为什么用long不用char?扫描算法，bitmap0bitmap3，if(bitmap0!=0)else这种算法效率还是没有uC/OS-II高。经验交流读代码前要有总体思想要讲究一定的阅读顺序好的工具猜测缩写的含义发散思维：学科间的联系网络资源：论坛+百度（残念，中国Google)谢谢大家！