Linuxjournal-The Linux Scheduler

这篇文章 The Linux Scheduler作者Moshe Bar发表在linuxjournal, 是一篇2000年的文章.从Linux版本时间线可以看到,那时Linux内核版本2.2, 过了一年后2001正式发布2.4版本

图片来源wiki/Linux内核

目录隐藏

正文

了解内核如何为单处理器和多处理器计算机调度任务。

上个月，我们开始了一个关于Linux内核内部的新系列。在第一部分中，我们研究了Linux如何管理流程以及为什么Linux在许多方面比许多商业UNIX系统更好地创建和维护流程。

这一次，我们详细讨论了调度问题。令我惊讶的是，在这里，Linux走向非传统的方式，无视核心理论中的传统智慧。结果非常好。我们来看看如何。

调度类

在Linux 2.2.x中有三类进程，从调度程序的数据定义可以看出（来自linux/include/linux/sched.h）：

调度策略


#define SCHED_OTHER 0
#define SCHED_FIFO 1
#define SCHED_RR 2

SCHED_OTHER任务是正常的用户任务（默认）。

在SCHED_FIFO中运行的任务永远不会被抢占。它们将仅在等待同步内核事件或者如果已从用户空间请求显式睡眠或重新调度,释放CPU资源。

在SCHED_RR中运行的任务是实时(RT)的，但如果运行队列中有另一个实时任务，它们将离开CPU。因此CPU资源将在所有SCHED_RR任务之间分配。如果至少有一个实时任务正在运行，则不允许在任何CPU中运行其他SCHED_OTHER任务。每个实时任务都有一个rt_priority，因此允许SCHED_RR类随意在所有SCHED_RR任务之间分配CPU资源。 SCHED_RR类的rt_priority与SCHED_OTHER（默认）类的普通优先级字段完全相同。

只有root用户才能通过sched_setscheduler系统调用更改当前任务的类。

内核的任务之一是确保即使在异常进程的情况下系统仍然处于其控制之下。一个这样异常的程序可能会过快地fork太多进程。因此，内核变得如此忙碌以至于无法满足其他职责。我发现Linux对用户态程序生成子进程的速度没有限制。 HP-UX，Solaris和AIX每个处理器的时间限制(tick)为一个fork（在Linux下称为jiffie）。清单1中的补丁（请参阅参考资料）将允许每个jiffie最多一个fork（一个jiffie通常是1/100秒，除了Alpha架构，它是1/1024）。

文中提到的清单1 （稍微调整了下格式）


2.3.26/kernel/fork.c   Thu Oct 28 22:30:51 1999
+++ /tmp/fork.c Tue Nov  9 01:34:36 1999
@@ -591,6 +591,14 @@
    int retval = -ENOMEM;
    struct task_struct *p;
    DECLARE_MUTEX_LOCKED(sem);
 +  static long last_fork;
 +  while (time_after(last_fork+1, jiffies))
 +  {
 +      __set_current_state(TASK_INTERRUPTIBLE);
 +      schedule_timeout(1);
 +  }
 +  last_fork = jiffies;
    if (clone_flags & CLONE_PID) {
     /* This is only allowed from the boot up thread */

个人理解,如果last_fork+1>jiffies说明当前进程在1个jiffie内创建,设置进程休眠,类似delay功能(这个地方也不是很确认:(, 后续需要再验证一下)

关于线程

必须使用线程来允许您的进程使用多个处理器。从内存管理和调度的角度来看，Linux并没有真正区分进程和线程。某些操作系统（如Solaris）通过线程调度库管理用户进程内的线程。内核只看到进程，并且不知道哪个线程（如果有）实际在用户进程内执行。这样可以使内核免于管理列表，每个进程的每个线程都有数千个条目。

显然，不允许在单个用户进程的线程在SMP上同时运行，因此用户空间方法在SMP机器上不能很好地扩展。只有当所有线程都受CPU限制且主要不是面向I/O时，线程才是必需的。如果所有线程都受CPU限制，那么您肯定希望能够扩展SMP。

仅使用线程等待事件是过度的。另一方面，线程休眠是浪费资源和性能。 Linux中的几乎所有子系统（例如TCP/IP）都提供异步事件注册。通过SIGIO信号使用异步事件类似于IRQ驱动的处理。

使用用户空间方法，您至少会避免TLB（转换后备缓冲区）刷新，因为所有线程将共享相同的地址空间。

通过线程库在用户空间中管理线程的优点是内核将在用户空间中花费调度CPU成本。确实，在用户空间中，您可以选择实现一个非常快速的循环调度程序，与Linux调度程序相比，可以降低调度成本,但在执行路径方面更加昂贵。

说到SMP，从Linux 2.4开始，我发现没有办法声明任何给定用户空间进程的处理器亲和性。

调度程序可以跟踪进程的CPU关联声明，或者它可以自己确定进程的首选CPU。前几天，我与意大利的Andrea Arcangeli一起设计了清单2中的简单内核补丁（请参阅参考资料），该补丁实现了处理器关联。请注意，当其他进程被排除在此CPU上运行时，处理器关联性最有意义。实现此修补程序的更好方法是让系统管理员与外部调用设置关联，例如nice。

看下提到的清单2 , (稍微调整了下格式)


--- 2.3.38-pset/include/linux/sched.h.~1~   Tue Jan 11 14:46:45
2000
+++ 2.3.38-pset/include/linux/sched.h   Tue Jan 11 17:58:52 2000
@@ -363,6 +363,7 @@
    u32 self_exec_id;
/* Protection of fields allocatio/deallocation */
    struct semaphore exit_sem;
+   int bind_cpu;
 };
 /*
@@ -430,6 +431,7 @@
 /* signals */  SPIN_LOCK_UNLOCKED, &init_signals, {{0}}, {{0}}, NULL,
&init_task.sigqueue, 0, 0, \
 /* exec cts */ 0,0, \
 /* exit_sem */ __MUTEX_INITIALIZER(name.exit_sem), 
+NO_PROC_ID,
 }
 #ifndef INIT_TASK_SIZE
--- 2.3.38-pset/kernel/sched.c.~1~  Sun Jan  9 20:45:31 2000
+++ 2.3.38-pset/kernel/sched.c  Tue Jan 11 18:16:45 2000

@@ -72,11 +72,13 @@
    struct schedule_data {
        struct task_struct * curr;
        cycles_t last_schedule;
+       int bind;
    } schedule_data;
    char __pad [SMP_CACHE_BYTES];
 } aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0}}};
 #define cpu_curr(cpu) aligned_data[(cpu)].schedule_data.curr
+#define cpu_bind(cpu) (aligned_data[(cpu)].bind)
 struct kernel_stat kstat = { 0 };

@@ -94,6 +96,25 @@

 void scheduling_functions_start_here(void) { }
+static int not_deadlocking(void)
+
+   int i;
+
+   for (i = 0; i < smp_num_cpus; i++) {
+       int cpu;
+
+       cpu = cpu_logical_map(i);
+       if (!cpu_bind(cpu))
+           return 1;
+   }
+   return 0;
+}
+
+void set_bind_cpu(int cpu, int set)
+{
+   cpu_bind(cpu_logical_map(cpu)) = set;
+}
+
 /*
  * This is the function that decides how desirable a process is..
  * You can weigh different processes against each other depending*/
@@ -111,6 +132,9 @@
 static inline int goodness(struct task_struct * p, int this_cpu,
struct
mm_struct *this_mm)
 {
    int weight;
+
+   if (not_deadlocking() && cpu_bind(this_cpu) && p->bind_cpu != this_cpu)
+       return 0;
    /*
     * Realtime process, select the first one on the*/

--- 2.3.38-pset/kernel/sys.c.~1~    Tue Nov  2 12:06:25 1999
+++ 2.3.38-pset/kernel/sys.c    Tue Jan 11 18:18:34 2000

@@ -1027,6 +1027,19 @@
            }
            current->dumpable = arg2;
            break;
+       case PR_SET_CPU:
+           {
+               extern void set_bind_cpu(int, int);
+
+               error = -EINVAL;
+               if (arg2 >= smp_num_cpus || arg2 < 0)
+                   break;
+
+               error = 0;
+               current->bind_cpu = cpu_logical_map(arg2);
+               set_bind_cpu(arg3, 1);
+               break;
+           }
        default:
            error = -EINVAL;
            break;

2.2.x SMP内核调度程序有一些错误，有时会使它不如UP(单处理器)内核调度程序有效。尽管如此，Andrea修复了所有这些错误，并从头开始重写了启发式算法，SMP调度程序在负载下提供了令人印象深刻的SMP改进。 SMP更改只在2.3.x内核中，我计划将其集成到2.2.x中。您可以在 ftp.suse.com/pub/people/andrea/kernel-patches/my-2.2.12/SMP-scheduler-2_2_11-E 获取Andrea的补丁。该补丁可用于2.2.11和2.2.12，并加速SMP系统上的两个内核。该补丁被合并到2.3.15中，但尚未在2.2.x中，因为它只是一个性能问题而不是真正的错误修复。

SMP调度程序启发式机制作的工作（不是以任何特定顺序）：

空闲的CPU
wakenup任务运行的最后一个CPU
任务的内存管理（用于优化内核线程重新安排）
在忙碌的CPU上运行的任务的“goodness”
使运行的CPU上的L2缓存无效所需的时间（cacheflush_time）
唤醒任务的平均时间片（avg_slice）（任务在返回睡眠之前运行的时间）

该算法收集上述数据并选择最佳CPU来重新安排唤醒任务。

Linux调度程序行为涉及两个路径：

schedule：running / current任务是一个SCHED_OTHER任务，它的时间片已到期（因此内核运行一个调度，同时从定时器IRQ返回以切换到下一个正在运行的任务）。
reschedule_idle：一个任务得到了唤醒（通常来自IRQ），因此我们尝试通过调用它上面的调度来重新安排最佳CPU中的这种唤醒任务（这是一种受控的调度）。

两条路径共享良好功能。 goodness函数可以被认为是SMP调度程序的核心。它根据以下内容计算任务的“优点”：

当前正在运行的任务
想要运行的任务
当前的CPU

可以在清单3中找到goodness函数的源代码（请参阅参考资料）。

看下清单3 ,（稍微调整下格式）


/* linux/kernel/sched.c
* This is the function that decides how desirable a process is.
* You can weigh different processes against each other depending
 * on what CPU they've run on lately etc to try to handle cache
 * and TLB miss penalties.
 *
 * Return values:
 *   -1000: never select this
 *       0: out of time, recalculate counters (but it might still
 *       be
 *      selected)
 *     +ve: "goodness" value (the larger, the better)
 *   +1000: realtime process, select this.
 */

static inline int goodness(struct task_struct * p, int this_cpu, struct
mm_struct *this_mm)
{
    int weight;

    /*
     * Realtime process, select the first one on the
     * runqueue (taking priorities within processes
     * into account).
     */
    if (p->policy != SCHED_OTHER) {
        weight = 1000 + p->rt_priority;
        goto out;
    }
    /*
     * Give the process a first-approximation goodness value
     * according to the number of clock-ticks it has left.
     *
     * Don't do any other calculations if the time slice is
     * over..
     */

    weight = p->counter;
    if (!weight)
        goto out;

#ifdef __SMP__
    /* Give a largish advantage to the same processor...  */
    /* (this is equivalent to penalizing other processors) */

    if (p->processor == this_cpu)
        weight += PROC_CHANGE_PENALTY;
#endif
    /* .. and a slight advantage to the current MM */
    if (p->mm == this_mm)
        weight += 1;
    weight += p->priority;
out:
    return weight;
}

简单的基于goodness的调度。如清单3所示，普通的调度是SMP感知的。如果最后一个CPU是当前CPU，那么潜在的下一个任务的goodness就会增加。

然而，reschedule_idle对CPU亲和性和调度程序延迟更为重要;例如，如果您注释掉reschedule_idle，则调度程序延迟将变为无限。此外，reschedule_idle负责缓存刷新时间和任务平均时间片，这是SMP调度程序真正有趣的部分。在UP中reschedule_idle没有SMP版本那么有趣。清单4（请参阅参考资料）是从2.3.26（很快2.4）开始的reschedule_idle实现。

reschedule_idle的最终目标是在CPU调用schedule,重新调度唤醒任务。我们在reschedule_idle中使用goodness，因为我们想要预测我们将发送到该CPU的未来计划的效果。通过预测未来计划的效果，我们可以选择在唤醒时重新安排的最佳CPU。当然，这样可以省去在没有正确TLB设置的情况下在CPU上执行的麻烦。如果要重新安排的CPU不是当前的，我们通过CPU间消息传递发送重新安排事件（i386上的SMP-IPI中断）。

goodness是Linux调度程序的核心，而reschedule_idle聪明的SMP启发式核心

看下上面提到的清单4


static void reschedule_idle(struct task_struct * p)
{
#ifdef __SMP__
    int this_cpu = smp_processor_id(), target_cpu;
    struct task_struct *tsk, *target_tsk;
    int cpu, best_cpu, i;
    unsigned long flags;
    spin_lock_irqsave(&amp;runqueue_lock, flags);
    /*
     * shortcut if the woken up task&#039;s last CPU is
     * idle now.
     */
    best_cpu = p-&gt;processor;
    target_tsk = idle_task(best_cpu);
    if (cpu_curr(best_cpu) == target_tsk)
        goto send_now;
    target_tsk = NULL;
    for (i = 0; i &lt; smp_num_cpus; i++) {
        cpu = cpu_logical_map(i);
        tsk = cpu_curr(cpu);
        if (tsk == idle_task(cpu))
            target_tsk = tsk;
    }
    if (target_tsk &amp;&amp; p-&gt;avg_slice &gt; cacheflush_time)
        goto send_now;

    tsk = cpu_curr(best_cpu);
    if (preemption_goodness(tsk, p, best_cpu) &gt; 0)
        target_tsk = tsk;
    /*
     * found any suitable CPU?
     */
    if (!target_tsk)
        goto out_no_target;

send_now:
    target_cpu = target_tsk-&gt;processor;
    target_tsk-&gt;need_resched = 1;
    spin_unlock_irqrestore(&amp;runqueue_lock, flags);
    /*
     * the APIC stuff can go outside of the lock because
     * it uses no task information, only CPU#.
     */
    if (target_cpu != this_cpu)
        smp_send_reschedule(target_cpu);
    return;

out_no_target:
    spin_unlock_irqrestore(&amp;runqueue_lock, flags);
    return;
#else /* UP */
    int this_cpu = smp_processor_id();
    struct task_struct *tsk;
    tsk = cpu_curr(this_cpu);
    if (preemption_goodness(tsk, p, this_cpu) &gt; 0)
        tsk-&gt;need_resched = 1;
#endif
}

内核抢占和用户抢占

Linux只能做用户抢占。 Linus Torvalds似乎并不相信内核抢占。这并不像看起来那么糟糕; 一切都适合信号量。受信号量保护的关键部分可以随时被抢占，因为每个争用都将在计划中结束，并且不会出现任何死锁。但是，除非我们阻止定时器IRQ，否则不能抢占受快速自旋锁或手锁保护的关键部分。所以所有旋转锁都应该是IRQ安全的。此外，通过避免内核抢占，内核变得更健壮和更简单，因为可以通过这种方式保存许多复杂的代码。

顺便说一下，有一些工具可以监控调度程序延迟，以便让感兴趣的黑客能够捕获需要条件调度的潜在代码段。

Linux 后续版本支持了:)
摘自 Linux kernel preemption
Linux内核在某些条件下提供抢占式调度。在内核版本2.4之前，只有用户进程是抢占式的，即除了时间量程到期之外，如果更高的动态优先级进程进入TASK_RUNNING状态，则用户模式中当前进程的执行将被中断。对于2.6系列的Linux内核，增加了一个中断执行内核代码的任务的能力，尽管并非内核代码的所有部分都可以被抢占。
Linux内核包含不同的调度程序类。默认情况下，内核使用2.6.23版内核中引入的称为完全公平调度程序的调度程序机制。在内部，这个默认调度程序类也称为SCHED_OTHER，但内核还包含两个符合POSIX标准的实时调度类，名为SCHED_FIFO（实时先进先出）和SCHED_RR（实时循环），两者都优先于默认类。
通过使用实时Linux内核补丁PREEMPT_RT，可以支持对关键部分，中断处理程序和“中断禁用”代码序列的完全抢占的支持。实时Linux内核补丁的部分主线集成已经为内核主线带来了一些功能。抢占可以提高延迟，提高响应速度，并使Linux更适合桌面和实时应用程序。较旧版本的内核有一个所谓的大内核锁，用于整个内核的同步，最终由Arnd Bergmann于2011年删除。
在2014年3月30日发布的内核版本3.14中添加了称为SCHED_DEADLINE的附加调度策略，实现了最早的截止时间优先算法（EDF）。

对Linux的影响

Linux由于其GPL特性，允许我们比其他人更快地完成任务，因为您可以调整和重新编译自己的内核，而不是使用标准的fit-all内核。例如，在一些流行的专有操作系统（如Solaris 7）中，许多代码段已经打包在spin_lock和spin_unlock中，以使相同的代码在UP和SMP系统中都能很好地工作。虽然这些商业操作系统的供应商认为这是重型SMP系统的明显优势，但这些锁实际上阻碍了UP系统和简单的SMP机器，因为相同的二进制驱动程序必须同时适用于SMP和UP内核。 spin_unlock是一个锁定的ASM指令：

#define spin_unlock_string \
        &quot;lock ; btrl $0,%0&quot;

并通过函数指针调用这样的清除位指令是完全矫枉过正的。

另一方面，Linux具有UP和SMP系统的内联代码部分，适应其运行的机器。因此，如果只有一个单核系统托管内核，则不会丢失锁定不需要它的代码段的时间。

最后但同样重要的是，正如我们上面所看到的，goodness使得Linux中的SMP调度程序非常聪明。拥有一个聪明的SMP调度程序对性能至关重要。如果调度程序不支持SMP，OS理论告诉我们SMP机器上的性能甚至比UP机器上的性能更差。（这种情况发生在没有新启发式的2.2.x中，但现在已经修复了。）

就是这个月。我希望您对Linux如何在UP和SMP系统上安排任务有了更深入的了解。

GPL:GNU通用公共许可协议（英语：GNU General Public License，缩写GNU GPL 或 GPL），是被广泛使用的自由软件许可证，给予了终端用户运行、学习、共享和修改软件的自由。

文中相关资源下载链接

Linuxjournal-The Linux Scheduler

正文

调度类

关于线程

内核抢占和用户抢占

对Linux的影响

garlic

Be First to Comment

发表回复