linux内核源代码分析-进程管理及调度

进程管理、调度,进程管理任务进程管理与其他模块的依赖关系进程描述符及任务队列进程的创建(FORK,copy-on-write)线程实现进程的终止进程调度,进程管理的任务,允许进程复制自己（真正作到一个应用多进程）确定哪个进程能够拥有CPU接受中断并将中断导向相应的内核子系统向用户进程发送信号管理时钟硬件当一个进程结束时，释放其资源动态装载执行模块,进程模块与其他模块的依赖关系在整个内核中的功能位置和源码依赖关系,进程模块与其他模块的依赖关系进程调度模块的内外界面,对用户进程提供了一组简单的系统调用接口；对内核的其他模块提供了丰富的接口功能。,进程模块与其他模块的依赖关系进程调度模块和其他模块的相互依赖关系,内存管理模块：当一个进程被调度的时候，为它建立内存映射。IPC子模块：bottom-half处理使用了其中的信号量队列。文件系统模块：在装载module的时候为进程调度提供实际设备的访问途径。所有的其他模块都依赖于进程调度模块，因为当要进行硬件访问的时候它们需要CPU挂起用户进程，切换到系统态进行处理。,.,进程描述符及任务队列,分配进程描述符（http:/lxr.linux.no）预分配描述符（SLAB机制），把动态分配的过程省略掉一部分（不需要频繁调用内存管理响应功能），相当于一种高级缓存，提高效率。最后的操作主要是直接填写结构。,进程描述符的存放PID(为兼容原来的PID为unsignedshort,最大32767，可以通过/proc修改设置)获得当前进程描述符的指针（CURRENT宏、专门寄存器）,进程描述符及任务队列,进程状态#defineTASK_RUNNING0（进程是可执行的或正在执行）#defineTASK_INTERRUPTIBLE1（进程睡眠或阻塞，等待某一事件到来中断它）#defineTASK_UNINTERRUPTIBLE2（进程睡眠或阻塞，不能其他进程的信号打断，直接等待硬件条件）#defineTASK_ZOMBIE4（僵尸，呆傻状态，已结束，但其父进程未接到通知，描述符未释放）#defineTASK_STOPPED8（进程停止，接受到SIGSTP信号）#defineTASK_SWAPPING16（进程页面被兑换出内存）,进程描述符及任务队列,进程状态转换图（见书17页）设置当前进程状态（有很多情况会设置进程状态（思考）set_task_state(task,state)）进程的上下文（进程环境：用户、资源等）系统调用时，内核“代表进程”执行，上下文有效进程之间的联系也属进程的环境（INIT为第一个进程，描述符中Parent,Children指针将这种环境连接起来，可以从任一个进程出发遍历系统的所有进程）,进程描述符及任务队列,索引组织形式之一：队列,进程描述符及任务队列,索引组织形式之二：树,进程的创建(FORK,copy-on-write),进程创建过程描述Linux中，进程的创建是通过拷贝已存在进程来实现的。在Linux内核启动的时候，首先由start_kernel()初始化各个系统数据结构，同时生成了和系统共存亡的后台进程：init。init进程通过拷贝自身，产生了若干内核子进程。然后这些进程就可以通过系统调用fork()生成它们的子进程，当然这些子进程的原始数据都是他们的父亲的副本。进程的终止是通过系统调用_exit()实现的。,LINUX中的进程创建FORK()：进程复制自身产生其子进程EXEC()：加载可执行代码模块覆盖自身代码COPY_ON_WRITE：写时copy,进程的创建(FORK,copy-on-write),FORK()FORK（）、VFORK（）、_CLONE()=CLONE()=DO_FORK()(在kernel/fork.c中)=COPY_PROCESS(),并执行dup_task_struct(建内核栈、thread_info、task_struct);检查进程数目限制；描述符设置，以区别于父进程；子进程状态设置为TASK_UNINTERRUPTIBLEcopy_flagsget_pid资源引用复制父子进程平分剩余时间片返回指向子进程的指针（一般子进程先执行）（注意：此时并未复制代码）,进程的创建(FORK,copy-on-write),EXEC()对应内核中一族函数：execve(),execv(),execlp(),execvp()负责加载可执行的代码，覆盖本进程的代码、数据。,COPY_ON_WRITE：写时copyLINUX的FORK()过程并未为新生成的进程马上复制代码，开始的进程仅仅读共享父进程代码。直到进程第一次要对进程空间有写请求时，再复制代码。这样做的好处：效率高（一般新进程要有自己的代码，第一条就是EXEC()）,进程的创建(FORK,copy-on-write),FORK()应用实例main()pid_tpid;pintf(“thislocationinparentprocessn”);if(pid=fork()=0)printf(“thislocationinchildprocessn”);execlv(.);,进程的创建(FORK,copy-on-write),VFORK()除不拷贝父进程的页表项和FORK（）完全相同。目前已基本不用。体会一下书上20页有关VFORK（）主要过程的描述,线程实现,Linux没有真正的线程（线程与进程的比较）仅仅是进程之间资源直接共享的一种机制通过CLONE时参数实现：请看一下书21页的有关描述（有些参数标明共享打开文件）。相当于实现了线程概念的一部分（资源共享）。内核线程独立运行在内核的标准进程（后面章节再做讨论）,进程的终止,进程运行结束时要释放相应的资源，通过EXIT()调用实现（显式或隐式）EXIT()实现时调用了do_exit()完成以下工作Task_struct中标志成员设为：PF_EXITING调用_exit_mm()调用sem_exit()调用_exit_files(),_exit_fs(),exit_name_space,exit_sighand退出代码替换为EXIT()提供的代码调用Exit_notify()向父进程发信号，（标为ZOOMBIE)调用shedule切换到其他进程,进程的终止,删除进程描述符父进程得知子进程终止的消息后才能删除子进程的描述符。（思考：若父进程异常终止，将会发生什么情况）父进程WAIT()，返回时可以根据代码做相应动作（或者IGNORE），动作完成后真正释放描述符（调用release_task）调用free_uid:进程记数Unhash_process()：删除pidhash中的项同时删除task_list中的项若有trace删除ptrace_list对应项调用put_task_struct释放描述符，（内核栈、threadinfo所占的页、slab高速缓存。,进程调度,抢占式（preemtive）和非抢占式（cooprative）进程调度的策略IO消耗型和CPU消耗型进程UNIX系列的倾向于IO消耗型优先进程的优先级动态优先级（调度程序根据情况增或减其优先数-20-19）时间片长短定义是个很矛盾的事情（默认一个值）LINUX提供可变长的时间片进程抢占LINUX用抢占式调度（一个新的进程进入时，要看优先级别）调度策略的活动（一个编辑程序和一个后台程序比较）,进程调度,调度算法-LINUX调度在2.5以后的实现目标O(1)调度SMP的可扩展性强化SMP的亲和力（尽量将相关的一组任务分配给一个CPU）加强交互性保证公平对多CPU的支持增强（忙时每个CPU都有进程执行）主要问题：怎样实现了O(1)调度？,进程调度,LINUX围绕以下几个方面对调度算法进行改进运行队列在2.4内核中，就绪进程队列是一个全局数据结构，调度器对它的所有操作都会因全局自旋锁而导致系统各个处理机之间的等待，使得就绪队列成为一个明显的瓶颈。在2.6中，就绪队列定义为一个复杂得多的数据结构structrunqueue，并且，尤为关键的是，每一个CPU都将维护一个自己的就绪队列，-这将大大减小竞争。1）prio_array_t*active,*expired,arrays2每个CPU的就绪队列按时间片是否用完分为两部分，分别通过active指针和expired指针访问，active指向时间片没用完、当前可被调度的就绪进程，expired指向时间片已用完的就绪进程。每一类就绪进程都用一个structprio_array的结构表示：,进程调度,图中的task并不是task_struct结构指针，而是task_struct:run_list，这是一个小技巧，详见下面run_list的解释。2.4版本里选择最佳侯选进程是schedule（）进行的（O(n)）,在新的O(1)调度中，这一查找过程分解为n步，每一步所耗费的时间都是O(1)量级的。prio_array中包含一个就绪队列数组，数组的索引是进程的优先级（共140级，详见下“static_prioqueue中。调度时直接给出就绪队列active中具有最高优先级的链表中的第一项作为候选进程（参见”调度器“），而优先级的计算过程则分布到各个进程的执行过程中进行”属性的说明），相同优先级的进程放置在相应数组元素的链表。为了加速寻找存在就绪进程的链表，2.6核心又建立了一个位映射数组来对应每一个优先级链表，如果该优先级链表非空，则对应位为1，否则为0。核心还要求每个体系结构都构造一个sched_find_first_bit()函数来执行这一搜索操作，快速定位第一个非空的就绪进程链表。采用这种将集中计算过程分散进行的算法，保证了调度器运行的时间上限，同时在内存中保留更加丰富的信息的做法也加速了候选进程的定位过程。这一变化简单而又高效，是2.6内核中的亮点之一。arrays二元数组是两类就绪队列的容器，active和expired分别指向其中一个。active中的进程一旦用完了自己的时间片，就被转移到expired中，并设置好新的初始时间片；而当active为空时，则表示当前所有进程的时间片都消耗完了，此时，active和expired进行一次对调，重新开始下一轮的时间片递减过程,进程调度,structprio_arrayintnr_active;/*本进程组中的进程数*/structlist_headqueueMAX_PRIO;/*以优先级为索引的HASH表，见下*/unsignedlongbitmapBITMAP_SIZE;/*加速以上HASH表访问的位图，见下*/;,进程调度,2）spinlock_tlockrunqueue的自旋锁，当需要对runqueue进行操作时，仍然应该锁定，但这个锁定操作只影响一个CPU上的就绪队列，因此，竞争发生的概率要小多了。3）task_t*curr本CPU正在运行的进程。4）tast_t*idle指向本CPU的idle进程，相当于2.4中init_tasksthis_cpu()的作用。5）intbest_expired_prio记录expired就绪进程组中的最高优先级（数值最小）。该变量在进程进入expired队列的时候保存。6）unsignedlongexpired_timestamp当新一轮的时间片递减开始后，这一变量记录着最早发生的进程耗完时间片事件的时间（jiffies的绝对值，在schedule_tick()中赋），它用来表征expired中就绪进程的最长等待时间。它的使用体现在EXPIRED_STARVING(rq)宏上。,上面已经提到，每个CPU上维护了两个就绪队列，active和expired。一般情况下，时间片结束的进程应该从active队列转移到expired队列中（schedule_tick()），但如果该进程是交互式进程，调度器就会让其保持在active队列上以提高它的响应速度。这种措施不应该让其他就绪进程等待过长时间，也就是说，如果expired队列中的进程已经等待了足够长时间了，即使是交互式进程也应该转移到expired队列上来，排空active。这个阀值就体现在EXPIRED_STARVING(rq)上：在expired_timestamp和STARVATION_LIMIT都不等于0的前提下，如果以下两个条件都满足，则EXPIRED_STARVING()返回真：（当前绝对时间-expired_timestamp）=（STARVATION_LIMIT*队列中所有就绪进程总数+1），也就是说expired队列中至少有一个进程已经等待了足够长的时间；正在运行的进程的静态优先级比expired队列中最高优先级要低（best_expired_prio，数值要大），此时当然应该尽快排空active切换到expired上来。,进程调度,7）structmm_struct*prev_mm保存进程切换后被调度下来的进程（称之为prev）的active_mm结构指针。因为在2.6中prev的active_mm是在进程切换完成之后释放的（mmdrop()），而此时prev的active_mm项可能为NULL，所以有必要在runqueue中预先保留。8）unsignedlongnr_running本CPU上的就绪进程数，该数值是active和expired两个队列中进程数的总和，是说明本CPU负载情况的重要参数。9）unsignedlongnr_switches记录了本CPU上自调度器运行以来发生的进程切换的次数。10）unsignedlongnr_uninterruptible记录本CPU尚处于TASK_UNINTERRUPTIBLE状态的进程数，和负载信息有关。,进程调度,11）atomic_tnr_iowait记录本CPU因等待IO而处于休眠状态的进程数。12）unsignedlongtimestamp_last_tick本就绪队列最近一次发生调度事件的时间，在负载平衡的时候会用到。13）intprev_cpu_loadNR_CPUS记录进行负载平衡时各个CPU上的负载状态（此时就绪队列中的nr_running值），以便分析负载情况。,进程调度,运行时间片的计算老版本的LINUX的计算for(系统中的每个任务)重新计算优先级重新计算时间片新版本不用这样计算。（见书32页图）1)time_slice基准值和counter类似，进程的缺省时间片与进程的静态优先级（在2.4中是nice值）相关，使用如下公式得出：MIN_TIMESLICE+(MAX_TIMESLICE-MIN_TIMESLICE)*(MAX_PRIO-1-(p)-static_prio)/(MAX_USER_PRIO-1)代入各个宏的值后，结果如下图所示：,核心将100139的优先级映射到200ms10ms的时间片上去，优先级数值越大，则分配的时间片越小。和2.4中进程的缺省时间片比较，当nice为0时，2.6的基准值100ms要大于2.4的60ms。,2)time_slice的变化进程的time_slice值代表进程的运行时间片剩余大小，在进程创建时与父进程平分时间片，在运行过程中递减，一旦归0，则按static_prio值重新赋予上述基准值，并请求调度。时间片的递减和重置在时钟中断中进行（sched_tick()），除此之外，time_slice值的变化主要在创建进程和进程退出过程中：a)进程创建和2.4类似，为了防止进程通过反复fork来偷取时间片，子进程被创建时并不分配自己的时间片，而是与父进程平分父进程的剩余时间片。也就是说，fork结束后，两者时间片之和与原先父进程的时间片相等。b)进程退出进程退出时（sched_exit()），根据first_time_slice的值判断自己是否从未重新分配过时间片，如果是，则将自己的剩余时间片返还给父进程（保证不超过MAX_TIMESLICE）。这个动作使进程不会因创建短期子进程而受到惩罚（与不至于因创建子进程而受到奖励相对应）。如果进程已经用完了从父进程那分得的时间片，就没有必要返还了（这一点在2.4中没有考虑）。,3）time_slice对调度的影响在2.4中，进程剩余时间片是除nice值以外对动态优先级影响最大的因素，并且休眠次数多的进程，它的时间片会不断叠加，从而算出的优先级也更大，调度器正是用这种方式来体现对交互式进程的优先策略。但实际上休眠次数多并不表示该进程就是交互式的，只能说明它是IO密集型的，因此，这种方法精度很低，有时因为误将频繁访问磁盘的数据库应用当作交互式进程，反而造成真正的用户终端响应迟缓。2.6的调度器以时间片是否耗尽为标准将就绪进程分成active、expired两大类，分别对应不同的就绪队列，前者相对于后者拥有绝对的调度优先权-仅当active进程时间片都耗尽，expired进程才有机会运行。但在active中挑选进程时，调度器不再将进程剩余时间片作为影响调度优先级的一个因素，并且为了满足内核可剥夺的要求，时间片太长的非实时交互式进程还会被人为地分成好几段（每一段称为一个运行粒度，定义见下）运行，每一段运行结束后，它都从cpu上被剥夺下来，放置到对应的active就绪队列的末尾，为其他具有同等优先级的进程提供运行的机会。,优先级计算方法在2.4内核中，优先级的计算和候选进程的选择集中在调度器中进行，无法保证调度器的执行时间，这一点在前面介绍runqueue数据结构的时候已经提及。2.6内核中候选进程是直接从已按算法排序的优先级队列数组中选取出来的，而优先级的计算则分散到多处进行。这一节分成两个部分对这种新的优先级计算方法进行描述，一部分是优先级计算过程，一部分是优先级计算（以及进程入队）的时机。1）优先级计算过程动态优先级的计算主要由effect_prio()函数完成，该函数实现相当简单，从中可见非实时进程的优先级仅决定于静态优先级（static_prio）和进程的sleep_avg值两个因素，而实时进程的优先级实际上是在setscheduler()中设置的（详见“调度系统的实时性能”，以下仅考虑非实时进程），且一经设定就不再改变。相比较而言，2.4的goodness()函数甚至要更加复杂,它考虑的CPUCache失效开销和内存切换的开销这里都已经不再考虑。2.6的动态优先级算法的实现关键在sleep_avg变量上，在effective_prio()中，sleep_avg的范围是0MAX_SLEEP_AVG，经过以下公式转换后变成-MAX_BONUS/2MAX_BONUS/2之间的bonus：(NS_TO_JIFFIES(p)-sleep_avg)*MAX_BONUS/MAX_SLEEP_AVG)-MAX_BONUS/2如下图所示：,再用这个bonus去减静态优先级就得到进程的动态优先级（并限制在MAX_RT_PRIO和MAX_PRIO之间），bonus越小，动态优先级数值越大，优先级越低。也就是说，sleep_avg越大，优先级也越高。2)优先级计算时机优先级的计算不再集中在调度器选择候选进程的时候进行了，只要进程状态发生改变，核心就有可能计算并设置进程的动态优先级：,a)创建进程在wake_up_forked_process()中，子进程继承了父进程的动态优先级，并添加到父进程所在的就绪队列中。如果父进程不在任何就绪队列中（例如它是IDLE进程），那么就通过effect_prio()函数计算出子进程的优先级，而后根据计算结果将子进程放置到相应的就绪队列中。b)唤醒休眠进程核心调用recalc_task_prio()设置从休眠状态中醒来的进程的动态优先级，再根据优先级放置到相应就绪队列中。c)调度到从TASK_INTERRUPTIBLE状态中被唤醒的进程实际上此时调度器已经选定了候选进程，但考虑到这一类型的进程很有可能是交互式进程，因此此时仍然调用recalc_task_prio()对该进程的优先级进行修正（详见进程平均等待时间sleep_avg），修正的结果将在下一次调度时体现。d)进程因时间片相关的原因被剥夺cpu在schedule_tick()中（由时钟中断启动），进程可能因两种原因被剥夺cpu，一是时间片耗尽，一是因时间片过长而分段。这两种情况都会调用effect_prio()重新计算优先级，重新入队。e)其它时机这些其它时机包括IDLE进程初始化（init_idle()）、负载平衡（move_task_away()，详