对于多道程序设计的系统，就会有多个进程或者线程在同时竞争CPU。对于单核系统，调度问题，就是选择下一个要运行的进程或者线程是哪一个。

线程的调度与进程类似，对于按内核级别的调度，与线程所属的进程基本没有关系。

进程切换的代价是比较大的，包括用户态到内核态的切换、保存当前进程的状态、内存映像的改变、调度程序以及载入新进程的状态；另外，会导致高速缓存的失效。

调度程序要考虑的要素：

（1）进程是CPU密集型还是I/O密集型。I/O密集型可能会需要尽快运行，并且很快就阻塞。CPU密集型可能会长期占用CPU。

（2）何时调度。创建进程、进程退出、进程阻塞以及I/O中断发生。

（3）是否支持抢占。支持抢占的调度，可以不必等待当前进程运行完或阻塞，直接上CPU运行。

一、调度算法的分类

不同的环境需要不同的调度算法，也有不同的考量指标：

（1）批处理。批处理系统下，不需要特别快的响应速度，所以可以考虑非抢占以及每个进程都有长时间的抢占算法。指标主要是：吞吐量、周转时间以及CPU利用率。

（2）交互式。交互式系统下，抢占是必须的，因为操作者会希望比较快的得到响应。考虑的指标主要是最小响应时间、均衡性。

（3）实时。实时系统下，最重要的是满足截止时间要求，即在一定的时间内完成任务。

二、批处理系统中的调度

1、先来先服务（first-come-first-serve）。最简单的方式，非抢占式的先来先服务，从字面意思就可以看出，把任务作为一个队列，先来先服务。缺点是，无法体现任务的轻重缓急，达不到理想的指标性能。

2、最短作业优先。非抢占式下，即当一个任务完成时，从任务队列中挑选最短的一个作业执行。相对于先来先服务，提高了一些性能。运行时间必须提前掌握。

3、最短剩余时间优先。即最短作业优先的抢占版本。调度程序总是选择剩余运行时间最短的作业执行。每当一个新的作业到达，如果运行时间比当前进程的剩余运行时间短，就挂起当前进程并切换到新的进程。

三、交互式系统中的调度

1、轮转调度。最简单且最公平的方法，给每个进程分配一个时间片。时间片耗尽时，进程会下CPU并加入到就绪队列的末尾。问题的关键是选择合适的时间片。

2、优先级调度。进程有轻重缓急，于是给进程设置不同的优先级，每次调度优先级最高的进程运行。当然，这样可能会导致低优先级进程饥饿。解决方案是，实行奖惩机制，高优先级进程耗尽时间片时会降低它的优先级。

3、多级队列。给不同优先级的进程队列，设置不同单位的时间片。同时，也实行奖惩机制，耗尽时间片会改变进程的队列级别。

四、线程的调度

线程的调度，取决于支持的是内核级线程还是用户级线程。

对于用户级线程，内核不知道线程的存在，就给了进程很大的自主权。内核只是调度进程，进程中的调度程序选择哪个线程来运行。

对于内核级线程，线程的调度就交给了系统完成。

五、Linux中的进程与线程调度

首先明确一个概念，Linux系统中甚至没有真正的线程。不过，可以认为Linux是系统的线程是内核线程，所以调度是基于线程的。

一个进程由于其运行空间的不同, 从而有内核线程和用户进程的区分, 内核线程运行在内核空间, 之所以称之为线程是因为它没有虚拟地址空间, 只能访问内核的代码和数据, 而用户进程则运行在用户空间, 但是可以通过中断, 系统调用等方式从用户态陷入内核态。

用户进程运行在用户空间上, 而一些通过共享资源实现的一组进程我们称之为线程组, Linux下内核其实本质上没有线程的概念, Linux下线程其实上是与其他进程共享某些资源的进程而已。但是我们习惯上还是称他们为线程或者轻量级进程。

因此, Linux上进程分3种，内核线程（或者叫核心进程）、用户进程、用户线程, 当然如果更严谨的，也可以认为用户进程和用户线程都是用户进程。

Linux中，进程和线程都被维护为一个task_struct结构，线程和进程被同等对待来进行调度。

Linux将线程区分为3类：

（1）实时先入先出。

（2）实时轮转。

（3）分时。

实时先入先出有最高的优先级，不会被其他线程抢占，除非是另外一个刚刚准备好的且优先级更高的实时先入先出线程。

实时轮转线程与实时先入先出类似，不过有一个轮转体系，即分配一个时间片，时间到了就可以被抢占。时间片消耗完就进入实时轮转线程列表的末尾。其实，这两种都不是真的实时，因为执行的最后期限无法确定，只是比分时线程有更高的优先级。

实时线程的优先级从0-99,0是实时线程的最高优先级，99是实时线程的最低优先级。

传统的非实时线程，优先级从100-139。Linux系统根据非实时线程的优先级分配时间量。

Linux使用一个重要的结构，调度队列。每个CPU有自己的调度队列，包括两个数组：活动的和过期失效的。每个数组包括了140个链表头，对应140个优先级的链表。

调度器从正在活动数组中选择一个优先级最高的任务，如果时间片耗尽失效，就加入到过期失效数组中。如果进程在时间片内被阻塞，那么在时间片失效之前，等待的事件发生就可以继续运行，放回到正在活动的数组中。如果活动数组没有任务了，调度器交换指针，使得活动数组和失效数组调换。

不同的优先级被赋予不同的时间片长度，优先级越高的进程，时间片越长。

Linux采用静态优先级与动态优先级结合的方式。Linux采用了奖惩机制，目的在于奖励互动进程以及惩罚占用CPU的进程。一个进程初始被赋予了一个优先级，耗尽和阻塞会改变nice值，活动与过期进程转换时，动态改变进程优先级。

另外，对于多核处理器，运行队列数据结构与某一个处理器相对应，调度器尽量进行亲和调度，即将之前在某个处理器上运行过的任务再次调入该处理器。

调度器只考虑可以运行的任务，不可运行的任务和正在等待各种I/O操作的或内核事件的任务被放入等待队列中。每一种等待某种事件的任务组成一个等待队列。等待队列的头部包含一个指向任务链表的指针及一个自旋锁。