85Linux2.6进程调度算法

CompanyLOGOLinux2.6进程调度分析西安邮电学院武特[e-mail]2CompanyLogo主要内容与调度有关的数据结构2调度算法3调度策略13CompanyLogo1.调度策略关键词：I/O消耗型进程CPU消耗型进程时间片优先级4CompanyLogo调度策略理想的进程调度目标应该是：最小化的进程响应时间，最大化的系统吞吐量，保持系统各个功能部件均处于繁忙状态和提供貌似公平的机制。Linux的调度策略基于时间片和进程优先级。所谓时间片即将CPU时间划分为很小的单位，给每个可运行的进程分配一片。进程优先级是指通过某种算法为每个进程关联一个值，这个值表示把进程如何适当的分配给CPU。5CompanyLogo进程分类进程可以被分为两种类型：I/O消耗型和CPU消耗型。I/O消耗型进程频繁使用I/O设备，并且大部分时间都处于等待状态。为了使系统有较强的响应能力，I/O消耗型进程必须很快能被唤醒，以实现进程的切换;否则，用户会感到系统反应迟钝。大多数人机交互进程都属于I/O消耗型进程。CPU消耗型进程则大部分时间都在占用CPU，它们常常位于后台运行，并且没有过多的I/O需求，因此系统并不需要对这类进程做出快速反应。这类进程的典型代表为用于科学计算的进程。6CompanyLogo两种进程产生的矛盾调度程序面临的矛盾：如果系统要有迅速的响应能力，那么必须倾向于I/O消耗型进程，这样系统吞吐量会很低。反之，如果系统要有最大的系统吞吐量，那么必须倾向于CPU消耗型进程，这样会导致系统的交互性很差。调度程序为了调和这种冲突，采取了一种貌似公平的办法：通常会倾向于I/O消耗型进程。也就是说，调度程序会优先调用这类进程以提高系统的响应能力，而尽量将CPU消耗型进程压后执行。但这并不意味着这类进程就被调度程序忽略。7CompanyLogo时间片将CPU时间被划分成一小段，即所谓的时间片(slice)。时间片的划分既不能过长又不能过短。I/O消耗型进程希望时间片越短越好，这样那些等待I/O的进程就能被迅速切换；而CPU消耗型进程则希望时间片越长越好，这样它们就可以一直占用CPU。因此，I/O消耗型进程和CPU消耗型进程的矛盾再一次显现出来。Linux调度程序解决这种矛盾的方法是，提供一个较长的默认时间片，但是却提高交互进程的优先级，以使得这些进程运行的更频繁。8CompanyLogo静态优先级每个进程与生俱来（即从父进程那里继承而来）都有一个优先级，我们将其称为静态优先级。普通进程的静态优先级范围从100(最高优先级)到139(最低优先级)。静态优先级越高，进程得到的基本时间片越长静态优先级120，基本时间片=(140-静态优先级)*20静态优先级=120，基本时间片=(140-静态优先级)*59CompanyLogo动态优先级当调度程序选择新进程运行时就会使用进程的动态优先级，动态优先级和静态优先级的关系可参考下面的公式：动态优先级=max(100,min(静态优先级–bonus+5),139)动态优先级的生成是以静态优先级为基础，再加上相应的惩罚或奖励(bonus)。这个bonus并不是随机的产生，而是根据进程过去的平均睡眠时间做相应的惩罚或奖励。10CompanyLogo平均睡眠时间平均睡眠时间（task_struct结构的sleep_avg）记录了进程睡眠和执行的时间，它用来判断进程交互性强弱。它随着进程的睡眠而增长，随着进程的运行而减少。平均睡眠时间有很快的反应速度，反应进程当前的交互状态。交互性强的进程会得到调度程序的奖励（bonus为正），而那些一直霸占CPU的进程会得到相应的惩罚（bonus为负）。其实bonus相当于平均睡眠时间的缩影，此时只是将sleep_avg调整成bonus数值范围内的大小。11CompanyLogo2.与进程调度有关的数据结构关键词：可运行队列优先级数组过期进程活跃进程12CompanyLogo可运行队列Linux内核使用runqueue数据结构表示一个可运行队列，每个CPU都有且只有一个这样的结构。该结构不仅描述了每个处理器中处于可运行状态（TASK_RUNNING）的进程链表，而且还描述了该处理器的调度信息。具体的，可运行状态进程所组成的链表由runqueue结构中的arrays数组来体现，该数组的元素为prio_array_t类型。13CompanyLogorunqueue结构runqueue结构中的部分字段：spinlock_tlock：保护进程链表的自旋锁；unsignedlongnr_running：运行队列链表中进程数量；unsignedlonglongnr_switches：该CPU上进程切换的次数；task_t*idle：指向本地CPU上的idle进程描述符的指针；prio_array_t*active：指向可运行队列中活动链表；prio_array_t*expired：指向可运行队列中过期链表；prio_array_tarrays[2]：该数组的元素分别表示可运行队列中的活动进程集合和过期进程集合；intbest_expired_prio：过期进程中优先级最高的进程；14CompanyLogo过期进程和活动进程运行态和就绪态与可运行状态(TASK_RUNNING)的关系。可运行状态进程分为两类：活动进程，它们还没有用完他们的时间片，等待被运行；过期进程，已经用完了的时间片，在其他进程没有用完它们的时间片之前，它们不能再被运行。调度程序的工作就是在活动进程集合中选取一个最佳优先级的进程，如果该进程时间片恰好用完，就将该进程放入过期进程集合中。在可运行队列结构中，arrays数组的两个元素分别用来表示刚才所述的活动进程集合和过期进程集合。此外，active和expired两个指针也分别直接指向这两个集合。15CompanyLogo优先级数组O(1)算法的另一个核心数据结构即为prio_array结构体。该结构体中有一个用来表示进程优先级的数组queue，它包含了每一种优先级进程所形成的链表。#defineMAX_USER_RT_PRIO100#defineMAX_RT_PRIOMAX_USER_RT_PRIO#defineMAX_PRIO(MAX_RT_PRIO+40)typedefstructprio_arrayprio_array_t;structprio_array{unsignedintnr_active;unsignedlongbitmap[BITMAP_SIZE];structlist_headqueue[MAX_PRIO];};16CompanyLogo数据结构关系图17CompanyLogo3.调度算法关键词：时间片分配最佳进程的选择18CompanyLogo调度算法早期内核调度算法容易理解：在每次进程切换时，内核依次扫描就绪队列上的每一个进程，计算每个进程的优先级，选择出优先级最高的进程。该算法的缺点：系统中就绪进程越多，花费的时间就越大，时间复杂度为O(n)。2.6内核所采用的O(1)算法则很好的解决了这个问题，不管系统中可运行的进程有多少，该算法总能在有限的时间内选择出优先级最高的进程。19CompanyLogoO(1)中时间片的分配当所有进程的时间片用完时，调度程序会为每个进程重新分配时间片。早起调度算法中分配时间片的过程依赖可运行进程的数量，具体的做法是依次遍历每个进程，通过其优先级分配新的时间片。O(1)算法采用过期进程数组和活跃进程数组解决以往调度算法所带来的O(n)复杂度问题。过期数组中的进程都已经用完了时间片，而活跃数组的进程还拥有时间片。当一个进程用完自己的时间片后，它就被移动到过期进程数组中，同时这个过期进程在被移动之前就已经计算好了新的时间片。O(1)调度算法是采用分散计算时间片的方法，并不像以往算法中集中为所有可运行进程重新计算时间片。20CompanyLogoO(1)中时间片的分配的代码描述当活跃进程数组中没有任何进程时，说明此时所有可运行的进程都用完了自己的时间片。那么此时只需要交换一下两个数组即可将过期进程切换为活跃进程，进而继续被调度程序所调度。两个数组之间的切换其实就是指针之间的交换，因此花费的时间是恒定的。通过分散计算时间片、交换过期和活跃两个进程集合的方法可以使得O(1)算法在恒定的时间内为每个进程重新计算好时间片。21CompanyLogoO(1)最佳优先级的选取进程调度的本质就是在当前可运行的进程集合中选择一个最佳的进程，这个最佳则是以进程的动态优先级为选取标准的。早期内核选取最佳优先级进程的方法是依次遍历每个可运行状态的进程，最终选取一个优先级最高的进程。它的时间复杂度是O(n)。而在O(1)算法中，不管是过期进程集合还是活跃进程集合，都将每个优先级的进程组成一个链表，因此每个集合就有140个不同优先级的进程链表。同时，两个集合中还采用优先级位图来标记每个优先级链表中是否存在进程。由于进程优先级个数是定值，因此查找最佳优先级的时间恒定，它不会像以前的方法那样受可执行进程数量的影响。22CompanyLogoO(1)最佳优先级的选取的代码描述调度程序在选取最高优先级的进程时，首先利用优先级位图从高到低找到第一个被设置的位，该位对应着一条进程链表，这个链表内的所有进程都拥有相同的优先级，这个优先级是系统中目前最高的。在该优先级链表中选取第一个进程，该进程即为调度程序马上要执行的进程。上述进程的选取过程可用下述代码描述。23CompanyLogo与调度有关的函数scheduler_tick()更新时间片try_to_wake_up()唤醒睡眠进程recalc_task_prio()更新进程的动态优先级schedule()选择要被执行的新进程load_balance()维持多处理器系统中运行队列的平衡24CompanyLogoThanksforeveryone!Thanks!