下载掌阅APP，畅读海量书库
立即打开
Linux是个多进程的环境，不但用户空间可以有多个进程，而且内核内部也可以有内核进程。在Linux内核中线程与进程在调度时没有太大区别，只是中间多了一层调度域，因此在讨论调度算法的时候称作线程和进程都是一样的。调度器调度的是CPU资源，按照特定的规则分配给特定的进程。然后进程去申请或使用硬件或资源。因此这里涉及以下两方面的问题。
（1）对于调度器而言：
· 调度程序在运行时，如何确定哪一个程序将被调度使用CPU资源？
· 如何不让任何一个进程饥饿？
· 如何更快地定位和响应交互式进程？
· 单个 CPU 只有一个流水线，能否一次调度多个进程，同时使用多个 CPU 的物理资源呢？
· 调度来的CPU如何让其释放资源？是任其自己释放还是有相关回收机制？
（2）对于希望被调度的进程而言：
· 如何定义自己被调度的概率？
· 如何在等待被调度的同时接收信号？
· 如何避免自己希望占用的资源在没有被调度时不被别的进程占用，或者在SMP环境下没有与其同时使用同一资源的进程？
Linux的调度策略分为分时系统和实时系统两种。Linux本身不是实时系统，但是本着兼容并包的原则，Linux也实现了实时系统的接口。在操作系统的发展历史上，也很可能就是这种兼容并包、什么都覆盖的思路，让Linux顽强地生存了下来。
对于整个内核而言，调度策略包括SCHED_NORMAL、SCHED_FIFO、SCHED_RR、SCHED_BATCH这4种。而标准的调度策略还有两种Linux没有实现，即SCHED_IDLE和SCHED_DEADLINE。SCHED_NORMAL就是我们最常说的Linux默认使用的分时调度策略。
无论是实时的调度策略还是普通的调度策略，优先级都是由数值表示的。普通的静态优先级全部为0，区别普通调度程序可以使用动态优先级，也就是nice值。实时调度的程序优先级的nice值为1～99，也就是说任何一个实时程序的优先级都高于普通程序。所以，内核由nice值、优先级和具体的调度算法综合作用来决定调度什么进程执行。
当使用SCHED_RR时时间片流转，虽然也有优先级的数字，但是即使是最高优先级的进程，在时间片用完的时候也会释放CPU。而SCHED_FIFO除非是主动释放，否则具有最高优先级的进程永远不会释放CPU（等待IO完成等阻塞操作除外）。当两者存在更高优先级进程时都会被抢占。
前面说了没有实现SCHED_IDLE调度的方式，那么Linux如何实现后台磁盘整理等操作呢？答案是使用功能类似的SCHED_BATCH调度方式。这种调度方式并不会在有正常程序的时候完全不执行，但是会保证正常程序的执行和交互程序的响应，也适合GCC等编译操作。
可以通过内核提供的API设置调度的办法，也可以通过命令行设置进程调度，命令是chrt，还可以配置实时进程的最大时间占用，因为如果实时进程出现Bug，那么最高优先级的进程几乎不可能释放CPU，将导致系统卡死。通过sysctl调用可以设置kernel.sched_rt_period_us等参数，可以配置最大的实时调度进程占用的CPU。
通过搭配cgroup和进程调度，还可以实现按照cgroup进行CPU资源的配置方式，这也是通过cgroup文件系统完成的。
绝对的公平是不存在的，社会上人与人之间能获得的社会资源和自然资源也是不一样的。进程也是如此，因此所有的进程调度算法都会有优先级的划分。我们都知道现在的大部分进程的调度算法都是划分CPU的时间片，但是以前UNIX划分绝对的时间片的方法已经被Linux淘汰了，Linux改用基于比例的划分模型，而不是基于绝对时间片的方法。例如如果是绝对时间不同的同优先级的进程分别获得10ms和5ms的时间片，相差了一个时间片（假设一个是5ms），且将90ms和85ms两个划分也只相差了一个5ms的时间片，但是这在应用程序的表现上就有极大的区别，因为前者是两倍的差距，后者差距程度相比自身的时间片来说微不足道。前者由于时间片本身就短，还得担负更多进程切换的开销，所以时间片就更短了。因此绝对时间是对机器友好，而不是对用户友好，但使用这个算法的是用户。
Linux的做法是使用CFS，即使用完全公平的方法来实现不公平。简单地说，就是根据目前有多少个进程，用总CPU资源除以进程个数就知道每个进程要占多久的时间片了。如果要定义有高优先级的进程，可以让它占有多份时间（但不一定是整数）。比起绝对时间的最大区别是根据进程数目的比例时间。例如优先级是5和0的两个进程与优先级是10和15的两个进程，在一个CPU上获得的时间片是一样的（假设只有这两个进程），因为是使用差值和比例计算的（具体算法略过）。学过cgroup的读者就会发现，这种被叫作完全公平调度的算法是整个系统不公平调度的基础，cgroup就是使用公平的CFS划分出一部分占比，然后在占比内使用CFS，如此cgroup内的公平相对于cgroup外部就是完全不公平的，因为这个cgroup子系统占据的比例本身就是不同的。
内核中的很多操作都是使用一些内核基础设施完成的，例如workqueue、tasklet、softirq等，这些基础设施一般可以完成特定的任务。既然是用来完成任务的，就必须参与调度，而调度的单位只能是内核线程。所以这些机制虽然对用户来说是一些拿来即用的调用接口，但其执行却是通过特定的内核守护线程执行的。
Linux中的中断分为上下两部分，下半部分可以关中断，产生上半部分的中断任务；上半部分不需要关中断，可以调度执行。出现这种情况的原因是系统中关中断的时间必须短，否则就会失去响应。产生的软中断被加入内核守护线程ksoftirqd的执行队列，这个线程后续会调度执行相关软中断。tasklet与软中断类似，只是在SMP系统中，软中断可以被多个CPU一起执行，是可重入的。而tasklet一次只允许一个CPU执行，是不可重入的。用户可以根据软中断是否允许重入来决定是否使用tasklet或softirq。
因为softirq和tasklet不能睡眠，所以不能使用信号量或其他阻塞函数，而且它们对应的都是由一个内核线程执行的（ksoftirqd），如果阻塞了，系统将无法响应其他软中断。工作队列workqueue本身就是作为一个可用的单元提供给用户的，一个workqueue就是一个内核线程（前提是不使用pool的kworker内核线程）。内核模块可以生成一个workqueue，然后添加自己的任务进去，也可以使用内核已经有的workqueue，向其中添加任务。workqueue是一个容器，内核模块可以向已有的workqueue中添加任务。该workqueue就会调度执行自己的子任务，可以说是进程中的进程。