《linux 24系统调度分析.doc》由会员分享，可在线阅读，更多相关《linux 24系统调度分析.doc（14页珍藏版）》请在三一办公上搜索。
1、一 前言在开源操作系统中，Linux的发展最为显著，到目前为止，它在低端服务器市场已经占据了相当大的份额。从最新的Linux 2.6系统来看，Linux的发展方向主要有两个：嵌入式系统和高端计算领域。调度系统对于操作系统的整体性能有着非常重要的影响，嵌入式系统、桌面系统和高端服务器对于调度器的要求是很不一样的。Linux调度器的特点主要有两个： 核心不可抢占； 调度算法简单有效。由于Linux适用于多种平台，本文所指缺省为i386下的SMP系统。二 相关数据结构在Linux中，进程用task_struct表示，所有进程被组织到以init_task为表头的双向链表中（见include/linux
2、/sched.hSET_LINKS()宏），该链表是全系统唯一的。所有CPU被组织到以schedule_data（对界后）为元素的数组之中。进程与所运行的CPU之间可以相互访问（详见下）。所有处于运行态的进程（TASK_RUNNING）被组织到以runqueue_head为表头的双向链表之中，调度器总是从中寻找最适合调度的进程。runqueue_head也是全系统唯一的。下面分别介绍这些与调度器工作相关的数据结构。1 init_tssTSS，Task State Segment，80x86平台特有的进程运行环境，尽管Linux并不使用TSS，但将TSS所需要描述的信息保存在以cpu号为索引的t
3、ss_struct数组init_tss中，进程切换时，其中的值将获得更新。2 task_struct在Linux中，线程、进程使用的是相同的核心数据结构，可以说，在2.4的内核里只有进程，其中包含轻量进程。一个进程在核心中使用一个task_struct结构来表示，包含了大量描述该进程的信息，其中与调度器相关的信息主要包括以下几个：i. stateLinux的进程状态主要分为三类：可运行的（TASK_RUNNING，相当于运行态和就绪态）；被挂起的（TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE和TASK_STOPPED）；不可运行的（TASK_ZOMBIE），调
4、度器主要处理的是可运行和被挂起两种状态下的进程，其中TASK_STOPPED又专门用于SIGSTP等IPC信号的响应，而TASK_ZOMBIE指的是已退出而暂时没有被父进程收回资源的僵尸进程。ii. need_resched布尔值，在调度器中用于表示该进程需要申请调度（详见调度器工作流程）。iii. policy在Linux 2.4中，进程的调度策略可以有三种选择：SCHED_FIFO（先进先出式调度，除非有更高优先级进程申请运行，否则该进程将保持运行至退出才让出CPU）、SCHED_RR（轮转式调度，该进程被调度下来后将被置于运行队列的末尾，以保证其他实时进程有机会运行）、SCHED_OTH
5、ER（常规的分时调度策略）。另外，policy中还包含了一个SCHED_YIELD位，置位时表示主动放弃CPU。iv. rt_priority用于表征实时进程的优先级，从1-99取值，非实时进程该项应该为0。这一属性将用于调度时的权值计算（详见就绪进程选择算法）。v. counter该属性记录的是当前时间片内该进程还允许运行的时间（以CPU时钟tick值为单位，每个进程的counter初值与nice值有关，nice越小则counter越大，即优先级越高的进程所允许获得的CPU时间也相对越多），并参与就绪进程选择算法。在Linux 2.4中，每个（非SCHED_FIFO实时）进程都不允许运行大于
6、某一时间片的时间，一旦超时，调度器将强制选择另一进程运行（详见调度器工作流程）vi. nice用户可支配的进程优先级，将参与就绪进程选择算法，同时该值也决定了该进程的时间片长度（详见下）。vii. cpus_allowed以位向量的形式表示可用于该进程运行的CPU（见调度器工作流程）。viii. cpus_runnable以位向量的形式表示当前运行该进程的CPU（相应位为1）。如果不在任何CPU上运行，则为全1。这一属性和cpus_allowed属性结合，可以迅速判断该进程是否能调度到某一CPU上运行（位与）。ix. processor本进程当前（或最近）所在CPU编号。x. thread用于
7、保存进程执行环境（各个寄存器的值以及IO操作许可权映射表），内容与TSS相近。因为TSS以CPU id为索引，而Linux无法预测被替换下来的进程下一次将在哪个CPU上运行，所以这些信息不能保存在TSS中。3 current核心经常需要获知当前在某CPU上运行的进程的task_struct，在Linux中用current指针指向这一描述符。current的实现采用了一个小技巧以获得高效的访问速度，这个小技巧与Linux进程task_struct的存储方式有关。在Linux中，进程在核心级运行时所使用的栈不同于在用户级所分配和使用的栈。因为这个栈使用率不高，因此仅在创建进程时分配了两个页（8KB
8、），并且将该进程的task_struct安排在栈顶。（实际上这两个页是在分配task_struct时申请的，初始化完task_struct后即将esp预设为页尾作为进程的核心栈栈底，往task_struct方向延伸。）因此，要访问本进程的task_struct，只需要执行以下简单操作：_asm_(andl %esp,%0; :=r (current) : 0 (8191UL);此句将esp与0x0ffffe0作与运算，获得核心栈的首页基址，此即为task_struct的地址。4 schedule_datatask_struct是用于描述进程的数据结构，其中包含了指向所运行CPU的属性。在Lin
9、ux中，另有一个数据结构对应于CPU，可以利用它访问到某CPU上运行的进程，这个数据结构定义为schedule_data结构，包含两个属性：curr指针，指向当前运行于该CPU上的进程的task_struct，通常用cpu_curr(cpu)宏来访问；last_schedule时间戳，记录了上一次该CPU上进程切换的时间，通常用last_schedule(cpu)宏来访问。为了使该数据结构的访问能与CPU的Cache line大小相一致，schedule_data被组织到以SMP_CACHE_BYTES为单位的aligned_data联合数组中，系统中每个CPU对应数组上的一个元素。5 ini
10、t_tasks调度器并不直接使用init_task为表头的进程链表，而仅使用其中的idle_task。该进程在引导完系统后即处于cpu_idle()循环中（详见其他核心应用的调度相关部分之IDLE进程）。SMP系统中，每个CPU都分别对应了一个idle_task，它们的task_struct指针被组织到init_tasksNR_CPUS数组中，调度器通过idle_task(cpu)宏来访问这些idle进程（详见调度器工作流程）。6 runqueue_head以runqueue_head为表头的链表记录了所有处于就绪态的进程（当前正在运行的进程也在其中，但idle_task除外），调度器总是从中
11、选取最适合调度的进程投入运行。三 进程切换过程从一个进程的上下文切换到另一个进程的上下文，因为其发生频率很高，所以通常都是调度器效率高低的关键。在Linux中，这一功能是以一段经典的汇编代码实现的，此处就着力描述这段代码。这段名为switch_to()的代码段在schedule()过程中调用，以一个宏实现：/* 节选自include/asm-i386/system.h */#define switch_to(prev,next,last) do asm volatile(pushl %esint pushl %edint pushl %ebpnt 保存esi、edi、ebp寄存器 movl %
12、esp,%0nt esp保存到prev-thread.esp中 movl %3,%espnt 从next-thread.esp恢复esp movl $1f,%1nt 在prev-thread.eip中保存1：的跳转地址，当prev被再次切换到的时候将从那里开始执行 pushl %4nt 在栈上保存next-thread.eip，_switch_to()返回时将转到那里执行，即进入next进程的上下文 jmp _switch_ton 跳转到_switch_to()，进一步处理(见下) 1:t popl %ebpnt popl %edint popl %esint 先恢复上次被切换走时保存的寄存器
13、值，再从switch_to()中返回。 :=m (prev-thread.esp), %0 =m (prev-thread.eip),%1 =b (last) ebx，因为进程切换后，恢复的栈上的prev信息不是刚被切换走的进程描述符，因此此处使用ebx寄存器传递该值给prev :m (next-thread.esp), %3 m (next-thread.eip), %4 a (prev), d (next), eax,edx b (prev); ebx while (0)进程切换过程可以分成两个阶段，上面这段汇编代码可以看作第一阶段，它保存一些关键的寄存器，并在栈上设置好跳转到新进程的地址
14、。第二阶段在switch_to()中启动，实现在_switch_to()函数中，主要用于保存和更新不是非常关键的一些寄存器（以及IO操作许可权映射表ioperm）的值： unlazy_fpu()，如果老进程在task_struct的flags中设置了PF_USEDFPU位，表明它使用了FPU，unlazy_fpu()就会将FPU内容保存在task_struct:thread中； 用新进程的esp0（task_struct:thread中）更新init_tss中相应位置的esp0； 在老进程的task_struct:thread中保存当前的fs和gs寄存器，然后从新进程的task_struct:
15、thread中恢复fs和gs寄存器； 从新进程的task_struct:thread中恢复六个调试寄存器的值； 用next中的ioperm更新init_tss中的相应内容switch_to()函数正常返回，栈上的返回地址是新进程的task_struct:thread:eip，即新进程上一次被挂起时设置的继续运行的位置（上一次执行switch_to()时的标号1:位置）。至此转入新进程的上下文中运行。在以前的Linux内核中，进程的切换使用的是far jmp指令，2.4采用如上所示的手控跳转，所做的动作以及所用的时间均与far jmp差不多，但更利于优化和控制。四 就绪进程选择算法Linux s
16、chedule()函数将遍历就绪队列中的所有进程，调用goodness()函数计算每一个进程的权值weight，从中选择权值最大的进程投入运行。进程调度权值的计算分为实时进程和非实时进程两类，对于非实时进程（SCHED_OTHER），影响权值的因素主要有以下几个：1. 进程当前时间片内所剩的tick数，即task_struct的counter值，相当于counter越大的进程获得CPU的机会也越大，因为counter的初值与（-nice）相关，因此这一因素一方面代表了进程的优先级，另一方面也代表了进程的欠运行程度；（weight = p-counter;）2. 进程上次运行的CPU是否就是当前
17、CPU，如果是，则权值增加一个常量，表示优先考虑不迁移CPU的调度，因为此时Cache信息还有效；（weight += PROC_CHANGE_PENALTY;）3. 此次切换是否需要切换内存，如果不需要（或者是同一进程的两个线程间的切换，或者是没有mm属性的核心线程），则权值加1，表示（稍微）优先考虑不切换内存的进程；(weight += 1;)4. 进程的用户可见的优先级nice，nice越小则权值越大。（Linux中的nice值在-20到+19之间选择，缺省值为0，nice()系统调用可以用来修改优先级。）(weight += 20 - p-nice;) 对于实时进程（SCHED_FIF
18、O、SCHED_RR），权值大小仅由该进程的rt_priority值决定（weight = 1000 + p-rt_priority;），1000的基准量使得实时进程的权值比所有非实时进程都要大，因此只要就绪队列中存在实时进程，调度器都将优先满足它的运行需要。如果权值相同，则选择就绪队列中位于前列的进程投入运行。除了以上标准值以外，goodness()还可能返回-1，表示该进程设置了SCHED_YIELD位，此时，仅当不存在其他就绪进程时才会选择它。如果遍历所有就绪进程后，weight值为0，表示当前时间片已经结束了，此时将重新计算所有进程（不仅仅是就绪进程）的counter值，再重新进行就绪
19、进程选择（详见调度器工作流程）。五 调度器Linux的调度器主要实现在schedule()函数中。1调度器工作流程schedule()函数的基本流程可以概括为四步：1). 清理当前运行中的进程2). 选择下一个投入运行的进程3). 设置新进程的运行环境4). 执行进程上下文切换5). 后期整理其中包含了一些锁操作：就绪队列锁runquque_lock，全局核心锁kernel_flag，全局中断锁global_irq_lock，进程列表锁tasklist_lock。下面先从锁操作开始描述调度器的工作过程。A. 相关锁 runqueue_lock，定义为自旋锁，对就绪队列进行操作之前，必须锁定；
20、kernel_flag，定义为自旋锁，因为很多核心操作（例如驱动中）需要保证当前仅由一个进程执行，所以需要调用lock_kernel()/release_kernel()对核心锁进行操作，它在锁定/解锁kernel_flag的同时还在task_struct:lock_depth上设置了标志，lock_depth小于0表示未加锁。当发生进程切换的时候，不允许被切换走的进程握有kernel_flag锁，所以必须调用release_kernel_lock()强制释放，同时，新进程投入运行时如果lock_depth0，即表明该进程被切换走之前握有核心锁，必须调用reacquire_kernel_loc
21、k()再次锁定； global_irq_lock，定义为全局的内存长整型，使用clear_bit()/set_bit()系列进行操作，它与global_irq_holder配合表示当前哪个cpu握有全局中断锁，该锁挂起全局范围内的中断处理（见irq_enter()）； tasklist_lock，定义为读写锁，保护以init_task为头的进程列表结构。B. prev在schedule中，当前进程（也就是可能被调度走的进程）用prev指针访问。对于SCHED_RR的实时进程，仅当该进程时间片结束（counter=0）后才会切换到别的进程，此时将根据nice值重置counter，并将该进程置于就
22、绪队列的末尾。当然，如果当前就绪队列中不存在其他实时进程，则根据前面提到的goodness()算法，调度器仍将选择到该进程。如果处于TASK_INTERRUPTIBLE状态的进程有信号需要处理（这可能发生在进程因等待信号而准备主动放弃CPU，在放弃CPU之前，信号已经发生了的情况），调度器并不立即执行该进程，而是将该进程置为就绪态（该进程还未来得及从就绪队列中删除），参与紧接着的goodness选择。如果prev不处于就绪态，也不处于上面这种有信号等待处理的挂起态（prev为等待资源而主动调用schedule()放弃CPU），那么它将从就绪队列中删除，此后，除非有唤醒操作将进程重新放回到就绪队
23、列，否则它将不参与调度。被动方式启动调度器工作时，当前进程的need_resched属性会置位（见下调度器工作时机）。在schedule()中，该位会被清掉，表示该进程已经在调度器中得到了处理（当然，这一处理并不意味着该进程就一定获得了CPU）。C. goodness调度器遍历就绪队列中的所有进程，只要它当前可被调度（cpus_runnable & cpus_allowed & (1 mm是否为空就能知道该进程是不是核心线程，如果是，则继续使用prev的active_mm（next-active_mm = prev-active_mm），并通过设置cpu_tlbstatecpu.state为T
24、LBSTATE_LAZY，告诉内存管理部件不要刷新TLB；否则就调用switch_mm()函数进行内存的切换（具体过程牵涉到内存管理模块的知识，这里就从略了）。实际上，在switch_mm()中还会对prev-active_mm和next-mm判断一次，如果两值相等，说明两个进程是同属于一个进程的两个线程（实际上是轻量进程），此时也不需要执行内存的切换，但这种情况TLB还是需要刷新的。设置好next的内存环境以后，就可以调用mmdrop()释放掉prev的内存结构了。所有不在运行中的进程，其active_mm属性都应该为空。E. switch进程切换的过程在上文中已经描述得比较详细了。F. s
25、chedule_tail完成切换后，调度器将调用_schedule_tail()。这一函数对于UP系统基本没什么影响，对于SMP系统，如果被切换下来的进程（用p表示）仍然处于就绪态且未被任何CPU调度到，_schedule_tail()将调用reschedule_idle()，为p挑选一个空闲的（或者是所运行的进程优先级比p低的）CPU，并强迫该CPU重新调度，以便将p重新投入运行。进程从休眠状态中醒来时也同样需要挑选一个合适的CPU运行，这一操作是通过在wake_up_process()函数中调用reschedule_idle()实现的。挑选CPU的原则如下： p上次运行的CPU目前空闲。很
26、显然，这是最佳选择，因为不需要抢占CPU，CPU Cache也最有可能和p吻合。不过，既然p可运行，调度器就不可能调度到idle_task，所以这种情况只会发生在wake_up_process()的时候。 所有空闲的CPU中最近最少活跃（last_schedule(cpu)最小）的一个。该CPU中的Cache信息最有可能是无用的，因此这种选择方式可以尽最大可能减少抢占CPU的开销，同时也尽可能避免频繁抢占。值得注意的是，在使用支持超线程技术的CPU的SMP平台上，一旦发现一个物理CPU的两个逻辑CPU均空闲，则该CPU的其中一个逻辑CPU立即成为p候选的调度CPU，而不需要继续寻找最近最少活跃
27、的CPU。 CPU不空闲，但所运行的进程优先级比p的优先级低，且差值最大。计算优先级时使用的是goodness()函数，因为它所包含的信息最多。找到合适的CPU后，reschedule_idle()就会将目标进程（正在该CPU上运行的进程，可能是idle_task）的need_resched置为1，以便调度器能够工作（见调度器工作时机）。同时，因为idle_task很多情况下都使cpu处于停机（halt）状态以节电，所以有必要调用smp_send_reschedule(cpu)向cpu发RESCHEDULE_VECTOR中断（通过IPI接口），以唤醒该cpu。注：对于目标进程是idle_tas
28、k的情况，还要判断它的need_resched标志位，仅当它为0的时候才会启动调度，因为非0状态的idle_task本身一直都在检查need_resched值，它自己会启动schedule()（见下IDLE进程）。G. clear调度器工作的结果有两种：发生了切换、没有发生切换，但调度器退出前的清理工作是一样的，就是恢复新进程的状态。主要包含两个动作： 清被切换走的进程的SCHED_YIELD位（不管它是否置位）； 如果新进程（p）的lock_depth大于等于0，则重新为核心锁kernel_flag加锁（见上相关锁）。2. 调度器工作时机调度器的启动通常有两种方式：A. 主动式在核心应用中直
29、接调用schedule()。这通常发生在因等待核心事件而需要将进程置于挂起（休眠）状态的时候-这时应该主动请求调度以方便其他进程使用CPU。下面就是一个主动调度的例子： /* 节选自drivers/input/mousedev.c mousedev_read() */ add_wait_queue(&list-mousedev-wait, &wait); current-state = TASK_INTERRUPTIBLE; while (!list-ready) if (file-f_flags & O_NONBLOCK) retval = -EAGAIN; break; if (signa
30、l_pending(current) retval = -ERESTARTSYS; break; schedule(); current-state = TASK_RUNNING; /* 这一句实际上可以省略，因为进程的状态在唤醒过程中就已经恢复到TASK_RUNNING了 */ remove_wait_queue(&list-mousedev-wait, &wait); 其过程通常可分为四步： 将进程添加到事件等待队列中； 置进程状态为TASK_INTERRUPTIBLE（或TASK_UNINTERRUPTIBLE）； 在循环中检查等待条件是否满足，不满足则调用schedule()，满足了就
31、退出循环； 将进程从事件等待队列中删除。从调度器工作流程中我们知道，调度器会将处于休眠状态的进程从就绪队列中删除，而只有就绪队列中的进程才有可能被调度到。将该进程重新放到就绪队列中的动作是在事件发生时的唤醒过程中完成的。在以上所示的鼠标驱动中，鼠标中断将调用mousedev_event()函数，该函数的最后就会使用wake_up_interruptible()唤醒等待鼠标事件的所有进程。wake_up_interruptible()将最终调用try_to_wake_up()函数：/* 节选自kernel/sched.c */static inline int try_to_wake_up(st
32、ruct task_struct * p, int synchronous) unsigned long flags; int success = 0; spin_lock_irqsave(&runqueue_lock, flags); p-state = TASK_RUNNING; if (task_on_runqueue(p) goto out; add_to_runqueue(p); /* 添加到就绪队列中 */ if (!synchronous | !(p-cpus_allowed & (1 need_resched) idle(); schedule(); check_pgt_cac
33、he();初始化过程中第一次执行cpu_idle()，因need_resched为1，所以直接启动schedule()进行第一次调度。如上文所述，schedule()会清掉need_resched位，因此，之后本循环都将执行idle()函数，直至need_resched再被设置为非0（比如在reschedule_idle()中，见上调度器工作时机）。idle()函数有三种实现可能： default_idle()，执行hlt指令； poll_idle()，如果核心参数上定义了idle=poll，则pm_idle会指向poll_idle()，它将need_resched设置为特殊的-1，然后反复循
34、环直到need_resched不等于-1。因为poll_idle()采用更高效的指令，所以运行效率比default_idle()要高； 电源管理相关的idle过程，例如APM和ACPI模块中定义的idle过程。因为仅当就绪队列为空的时候才会调度到idle进程，所以，只有在系统完全空闲时才会执行check_pgt_cache()操作，清理页表缓存。2. 进程创建系统中除了init_task是手工创建的以外，其他进程，包括其他CPU上的idle进程都是通过do_fork()创建的，所不同的是，创建idle进程时使用了CLONE_PID标志位。在do_fork()中，新进程的属性设置为： state
35、：TASK_UNINTERRUPTIBLE pid：如果设置了CLONE_PID则与父进程相同（仅可能为0），否则为下一个合理的pid cpus_runnable：全1；未在任何cpu上运行 processor：与父进程的processor相同；子进程在哪里创建就优先在哪里运行 counter：父进程counter值加1的一半；同时父进程自己的counter也减半，保证进程不能通过多次fork来偷取更多的运行时间（同样，在子进程结束运行时，它的剩余时间片也将归还给父进程，以免父进程因创建子进程而遭受时间片的损失） 其他值与父进程相同子进程通过SET_LINKS()链入进程列表，然后调用wake_up_process()唤醒（见上调度器工作时机）。3. smp系
