Pthreads 中的互斥量
Pthreads 提供了一些功能用来同步线程。最基本的机制是使用互斥量变量，可以锁定和解锁，用来保护每个关键区域。希望进入关键区域的线程首先要尝试获取 mutex。如果 mutex 没有加锁，线程能够马上进入并且互斥量能够自动锁定，从而阻止其他线程进入。如果 mutex 已经加锁，调用线程会阻塞，直到 mutex 解锁。如果多个线程在相同的互斥量上等待，当互斥量解锁时，只有一个线程能够进入并且重新加锁。这些锁并不是必须的，程序员需要正确使用它们。
下面是与互斥量有关的函数调用
像我们想象中的一样，mutex 能够被创建和销毁，扮演这两个角色的分别是 Phread_mutex_init 和 Pthread_mutex_destroy。mutex 也可以通过 Pthread_mutex_lock 来进行加锁，如果互斥量已经加锁，则会阻塞调用者。还有一个调用Pthread_mutex_trylock 用来尝试对线程加锁，当 mutex 已经被加锁时，会返回一个错误代码而不是阻塞调用者。这个调用允许线程有效的进行忙等。最后，Pthread_mutex_unlock 会对 mutex 解锁并且释放一个正在等待的线程。
除了互斥量以外，Pthreads 还提供了第二种同步机制： 条件变量(condition variables) 。mutex 可以很好的允许或阻止对关键区域的访问。条件变量允许线程由于未满足某些条件而阻塞。绝大多数情况下这两种方法是一起使用的。下面我们进一步来研究线程、互斥量、条件变量之间的关联。
下面再来重新认识一下生产者和消费者问题：一个线程将东西放在一个缓冲区内，由另一个线程将它们取出。如果生产者发现缓冲区没有空槽可以使用了，生产者线程会阻塞起来直到有一个线程可以使用。生产者使用 mutex 来进行原子性检查从而不受其他线程干扰。但是当发现缓冲区已经满了以后，生产者需要一种方法来阻塞自己并在以后被唤醒。这便是条件变量做的工作。
下面是一些与条件变量有关的最重要的 pthread 调用
上表中给出了一些调用用来创建和销毁条件变量。条件变量上的主要属性是 Pthread_cond_wait 和 Pthread_cond_signal。前者阻塞调用线程，直到其他线程发出信号为止（使用后者调用）。阻塞的线程通常需要等待唤醒的信号以此来释放资源或者执行某些其他活动。只有这样阻塞的线程才能继续工作。条件变量允许等待与阻塞原子性的进程。Pthread_cond_broadcast 用来唤醒多个阻塞的、需要等待信号唤醒的线程。
需要注意的是，条件变量（不像是信号量）不会存在于内存中。如果将一个信号量传递给一个没有线程等待的条件变量，那么这个信号就会丢失，这个需要注意
下面是一个使用互斥量和条件变量的例子
#include <stdio.h> #include <pthread.h> /* 需要生产的数量 */ #define MAX 1000000000 pthread_mutex_t the_mutex; /* 使用信号量 */ pthread_cond_t condc,condp; int buffer = 0; /* 生产数据 */ void *producer(void *ptr){ int i; for(int i = 0;i <= MAX;i++){ /* 缓冲区独占访问，也就是使用 mutex 获取锁 */ pthread_mutex_lock(&the_mutex); while(buffer != 0){ pthread_cond_wait(&condp,&the_mutex); } /* 把他们放在缓冲区中 */ buffer = i; /* 唤醒消费者 */ pthread_cond_signal(&condc); /* 释放缓冲区 */ pthread_mutex_unlock(&the_mutex); } pthread_exit(0); } /* 消费数据 */ void *consumer(void *ptr){ int i; for(int i = 0;i <= MAX;i++){ /* 缓冲区独占访问，也就是使用 mutex 获取锁 */ pthread_mutex_lock(&the_mutex); while(buffer == 0){ pthread_cond_wait(&condc,&the_mutex); } /* 把他们从缓冲区中取出 */ buffer = 0; /* 唤醒生产者 */ pthread_cond_signal(&condp); /* 释放缓冲区 */ pthread_mutex_unlock(&the_mutex); } pthread_exit(0); }
管程
为了能够编写更加准确无误的程序，Brinch Hansen 和 Hoare 提出了一个更高级的同步原语叫做 管程(monitor)。他们两个人的提案略有不同，通过下面的描述你就可以知道。管程是程序、变量和数据结构等组成的一个集合，它们组成一个特殊的模块或者包。进程可以在任何需要的时候调用管程中的程序，但是它们不能从管程外部访问数据结构和程序。下面展示了一种抽象的，类似 Pascal 语言展示的简洁的管程。不能用 C 语言进行描述，因为管程是语言概念而 C 语言并不支持管程。
monitor example
integer i;condition c;
procedure producer();
...
end;
procedure consumer();
.
end;
end monitor;
管程有一个很重要的特性，即在任何时候管程中只能有一个活跃的进程，这一特性使管程能够很方便的实现互斥操作。管程是编程语言的特性，所以编译器知道它们的特殊性，因此可以采用与其他过程调用不同的方法来处理对管程的调用。通常情况下，当进程调用管程中的程序时，该程序的前几条指令会检查管程中是否有其他活跃的进程。如果有的话，调用进程将被挂起，直到另一个进程离开管程才将其唤醒。如果没有活跃进程在使用管程，那么该调用进程才可以进入。
进入管程中的互斥由编译器负责，但是一种通用做法是使用 互斥量(mutex) 和 二进制信号量(binary semaphore)。由于编译器而不是程序员在操作，因此出错的几率会大大降低。在任何时候，编写管程的程序员都无需关心编译器是如何处理的。他只需要知道将所有的临界区转换成为管程过程即可。绝不会有两个进程同时执行临界区中的代码。
即使管程提供了一种简单的方式来实现互斥，但在我们看来，这还不够。因为我们还需要一种在进程无法执行被阻塞。在生产者-消费者问题中，很容易将针对缓冲区满和缓冲区空的测试放在管程程序中，但是生产者在发现缓冲区满的时候该如何阻塞呢？
解决的办法是引入条件变量(condition variables) 以及相关的两个操作 wait 和 signal。当一个管程程序发现它不能运行时（例如，生产者发现缓冲区已满），它会在某个条件变量（如 full）上执行 wait 操作。这个操作造成调用进程阻塞，并且还将另一个以前等在管程之外的进程调入管程。在前面的 pthread 中我们已经探讨过条件变量的实现细节了。另一个进程，比如消费者可以通过执行 signal 来唤醒阻塞的调用进程。
Brinch Hansen 和 Hoare 在对进程唤醒上有所不同，Hoare 建议让新唤醒的进程继续运行；而挂起另外的进程。而 Brinch Hansen 建议让执行 signal 的进程必须退出管程，这里我们采用 Brinch Hansen 的建议，因为它在概念上更简单，并且更容易实现。
如果在一个条件变量上有若干进程都在等待，则在对该条件执行 signal 操作后，系统调度程序只能选择其中一个进程恢复运行。
顺便提一下，这里还有上面两位教授没有提出的第三种方式，它的理论是让执行 signal 的进程继续运行，等待这个进程退出管程时，其他进程才能进入管程。
条件变量不是计数器。条件变量也不能像信号量那样积累信号以便以后使用。所以，如果向一个条件变量发送信号，但是该条件变量上没有等待进程，那么信号将会丢失。也就是说，wait 操作必须在 signal 之前执行。
下面是一个使用 Pascal 语言通过管程实现的生产者-消费者问题的解法
monitor ProducerConsumer
condition full,empty;
integer count;
procedure insert(item:integer);
begin
if count = N then wait(full);
insert_item(item);
count := count + 1;
if count = 1 then signal(empty);
end;
function remove:integer;
begin
if count = 0 then wait(empty);
remove = remove_item;
count := count - 1;
if count = N - 1 then signal(full);
end;
count := 0;
end monitor;
procedure producer;
begin
while true do
begin
item = produce_item;
ProducerConsumer.insert(item);
end
end;
procedure consumer;
begin
while true do
begin
item = ProducerConsumer.remove;
consume_item(item);
end
end;
读者可能觉得 wait 和 signal 操作看起来像是前面提到的 sleep 和 wakeup ，而且后者存在严重的竞争条件。它们确实很像，但是有个关键的区别：sleep 和 wakeup 之所以会失败是因为当一个进程想睡眠时，另一个进程试图去唤醒它。使用管程则不会发生这种情况。管程程序的自动互斥保证了这一点，如果管程过程中的生产者发现缓冲区已满，它将能够完成 wait 操作而不用担心调度程序可能会在 wait 完成之前切换到消费者。甚至，在 wait 执行完成并且把生产者标志为不可运行之前，是不会允许消费者进入管程的。
尽管类 Pascal 是一种想象的语言，但还是有一些真正的编程语言支持，比如 Java （终于轮到大 Java 出场了），Java 是能够支持管程的，它是一种 面向对象的语言，支持用户级线程，还允许将方法划分为类。只要将关键字 synchronized 关键字加到方法中即可。Java 能够保证一旦某个线程执行该方法，就不允许其他线程执行该对象中的任何 synchronized 方法。没有关键字 synchronized ，就不能保证没有交叉执行。
下面是 Java 使用管程解决的生产者-消费者问题
public class ProducerConsumer {
// 定义缓冲区大小的长度
static final int N = 100;
// 初始化一个新的生产者线程
static Producer p = new Producer();
// 初始化一个新的消费者线程
static Consumer c = new Consumer();
// 初始化一个管程
static Our_monitor mon = new Our_monitor();
// run 包含了线程代码
static class Producer extends Thread{
public void run(){
int item;
// 生产者循环
while(true){
item = produce_item();
mon.insert(item);
}
}
// 生产代码
private int produce_item(){...}
}
// run 包含了线程代码
static class consumer extends Thread {
public void run( ) {
int item;
while(true){
item = mon.remove();
consume_item(item);
}
}
// 消费代码
private int produce_item(){...}
}
// 这是管程
static class Our_monitor {
private int buffer[] = new int[N];
// 计数器和索引
private int count = 0,lo = 0,hi = 0;
private synchronized void insert(int val){
if(count == N){
// 如果缓冲区是满的，则进入休眠
go_to_sleep();
}
// 向缓冲区插入内容
buffer[hi] = val;
// 找到下一个槽的为止
hi = (hi + 1) % N;
// 缓冲区中的数目自增 1
count = count + 1;
if(count == 1){
// 如果消费者睡眠，则唤醒
notify();
}
}
private synchronized void remove(int val){
int val;
if(count == 0){
// 缓冲区是空的，进入休眠
go_to_sleep();
}
// 从缓冲区取出数据
val = buffer[lo];
// 设置待取出数据项的槽
lo = (lo + 1) % N;
// 缓冲区中的数据项数目减 1
count = count - 1;
if(count = N - 1){
// 如果生产者睡眠，唤醒它
notify();
}
return val;
}
private void go_to_sleep() {
try{
wait( );
}catch(Interr uptedExceptionexc) {};
}
}
}
上面的代码中主要设计四个类，外部类(outer class) ProducerConsumer 创建并启动两个线程，p 和 c。第二个类和第三个类 Producer 和 Consumer 分别包含生产者和消费者代码。最后，Our_monitor 是管程，它有两个同步线程，用于在共享缓冲区中插入和取出数据。
在前面的所有例子中，生产者和消费者线程在功能上与它们是相同的。生产者有一个无限循环，该无限循环产生数据并将数据放入公共缓冲区中；消费者也有一个等价的无限循环，该无限循环用于从缓冲区取出数据并完成一系列工作。
程序中比较耐人寻味的就是 Our_monitor 了，它包含缓冲区、管理变量以及两个同步方法。当生产者在 insert 内活动时，它保证消费者不能在 remove 方法中运行，从而保证更新变量以及缓冲区的安全性，并且不用担心竞争条件。变量 count 记录在缓冲区中数据的数量。变量 lo 是缓冲区槽的序号，指出将要取出的下一个数据项。类似地，hi 是缓冲区中下一个要放入的数据项序号。允许 lo = hi，含义是在缓冲区中有 0 个或 N 个数据。
Java 中的同步方法与其他经典管程有本质差别：Java 没有内嵌的条件变量。然而，Java 提供了 wait 和 notify 分别与 sleep 和 wakeup 等价。
通过临界区自动的互斥，管程比信号量更容易保证并行编程的正确性。但是管程也有缺点，我们前面说到过管程是一个编程语言的概念，编译器必须要识别管程并用某种方式对其互斥作出保证。C、Pascal 以及大多数其他编程语言都没有管程，所以不能依靠编译器来遵守互斥规则。
与管程和信号量有关的另一个问题是，这些机制都是设计用来解决访问共享内存的一个或多个 CPU 上的互斥问题的。通过将信号量放在共享内存中并用 TSL 或 XCHG 指令来保护它们，可以避免竞争。但是如果是在分布式系统中，可能同时具有多个 CPU 的情况，并且每个 CPU 都有自己的私有内存呢，它们通过网络相连，那么这些原语将会失效。因为信号量太低级了，而管程在少数几种编程语言之外无法使用，所以还需要其他方法。
消息传递
上面提到的其他方法就是 消息传递(messaage passing)。这种进程间通信的方法使用两个原语 send 和 receive ，它们像信号量而不像管程，是系统调用而不是语言级别。示例如下
send(destination, &message);
receive(source, &message);
send 方法用于向一个给定的目标发送一条消息，receive 从一个给定的源接受一条消息。如果没有消息，接受者可能被阻塞，直到接受一条消息或者带着错误码返回。
消息传递系统的设计要点
消息传递系统现在面临着许多信号量和管程所未涉及的问题和设计难点，尤其对那些在网络中不同机器上的通信状况。例如，消息有可能被网络丢失。为了防止消息丢失，发送方和接收方可以达成一致：一旦接受到消息后，接收方马上回送一条特殊的 确认(acknowledgement) 消息。如果发送方在一段时间间隔内未收到确认，则重发消息。
现在考虑消息本身被正确接收，而返回给发送着的确认消息丢失的情况。发送者将重发消息，这样接受者将收到两次相同的消息。
对于接收者来说，如何区分新的消息和一条重发的老消息是非常重要的。通常采用在每条原始消息中嵌入一个连续的序号来解决此问题。如果接受者收到一条消息，它具有与前面某一条消息一样的序号，就知道这条消息是重复的，可以忽略。
消息系统还必须处理如何命名进程的问题，以便在发送或接收调用中清晰的指明进程。身份验证(authentication) 也是一个问题，比如客户端怎么知道它是在与一个真正的文件服务器通信，从发送方到接收方的信息有可能被中间人所篡改。
用消息传递解决生产者-消费者问题
现在我们考虑如何使用消息传递来解决生产者-消费者问题，而不是共享缓存。下面是一种解决方式
/ buffer 中槽的数量 /
#define N 100
void producer(void){
int item;
/ buffer 中槽的数量 /
message m;
while(TRUE){
/ 生成放入缓冲区的数据 /
item = produce_item();
/ 等待消费者发送空缓冲区 /
receive(consumer,&m);
/ 建立一个待发送的消息 /
build_message(&m,item);
/ 发送给消费者 /
send(consumer,&m);
}
}
void consumer(void){
int item,i;
message m;
/ 循环N次 /
for(int i = 0;i < N;i++){
/ 发送N个缓冲区 /
send(producer,&m);
}
while(TRUE){
/ 接受包含数据的消息 /
receive(producer,&m);
/ 将数据从消息中提取出来 /
item = extract_item(&m);
/ 将空缓冲区发送回生产者 /
send(producer,&m);
/ 处理数据 /
consume_item(item);
}
}
假设所有的消息都有相同的大小，并且在尚未接受到发出的消息时，由操作系统自动进行缓冲。在该解决方案中共使用 N 条消息，这就类似于一块共享内存缓冲区的 N 个槽。消费者首先将 N 条空消息发送给生产者。当生产者向消费者传递一个数据项时，它取走一条空消息并返回一条填充了内容的消息。通过这种方式，系统中总的消息数量保持不变，所以消息都可以存放在事先确定数量的内存中。
如果生产者的速度要比消费者快，则所有的消息最终都将被填满，等待消费者，生产者将被阻塞，等待返回一条空消息。如果消费者速度快，那么情况将正相反：所有的消息均为空，等待生产者来填充，消费者将被阻塞，以等待一条填充过的消息。
消息传递的方式有许多变体，下面先介绍如何对消息进行 编址。
- 一种方法是为每个进程分配一个唯一的地址，让消息按进程的地址编址。
- 另一种方式是引入一个新的数据结构，称为
信箱(mailbox)，信箱是一个用来对一定的数据进行缓冲的数据结构，信箱中消息的设置方法也有多种，典型的方法是在信箱创建时确定消息的数量。在使用信箱时，在 send 和 receive 调用的地址参数就是信箱的地址，而不是进程的地址。当一个进程试图向一个满的信箱发送消息时，它将被挂起，直到信箱中有消息被取走，从而为新的消息腾出地址空间。
屏障
最后一个同步机制是准备用于进程组而不是进程间的生产者-消费者情况的。在某些应用中划分了若干阶段，并且规定，除非所有的进程都就绪准备着手下一个阶段，否则任何进程都不能进入下一个阶段，可以通过在每个阶段的结尾安装一个 屏障(barrier) 来实现这种行为。当一个进程到达屏障时，它会被屏障所拦截，直到所有的屏障都到达为止。屏障可用于一组进程同步，如下图所示
在上图中我们可以看到，有四个进程接近屏障，这意味着每个进程都在进行运算，但是还没有到达每个阶段的结尾。过了一段时间后，A、B、D 三个进程都到达了屏障，各自的进程被挂起，但此时还不能进入下一个阶段呢，因为进程 B 还没有执行完毕。结果，当最后一个 C 到达屏障后，这个进程组才能够进入下一个阶段。
避免锁：读-复制-更新
最快的锁是根本没有锁。问题在于没有锁的情况下，我们是否允许对共享数据结构的并发读写进行访问。答案当然是不可以。假设进程 A 正在对一个数字数组进行排序，而进程 B 正在计算其平均值，而此时你进行 A 的移动，会导致 B 会多次读到重复值，而某些值根本没有遇到过。
然而，在某些情况下，我们可以允许写操作来更新数据结构，即便还有其他的进程正在使用。窍门在于确保每个读操作要么读取旧的版本，要么读取新的版本，例如下面的树
上面的树中，读操作从根部到叶子遍历整个树。加入一个新节点 X 后，为了实现这一操作，我们要让这个节点在树中可见之前使它"恰好正确"：我们对节点 X 中的所有值进行初始化，包括它的子节点指针。然后通过原子写操作，使 X 称为 A 的子节点。所有的读操作都不会读到前后不一致的版本
在上面的图中，我们接着移除 B 和 D。首先，将 A 的左子节点指针指向 C 。所有原本在 A 中的读操作将会后续读到节点 C ，而永远不会读到 B 和 D。也就是说，它们将只会读取到新版数据。同样，所有当前在 B 和 D 中的读操作将继续按照原始的数据结构指针并且读取旧版数据。所有操作均能正确运行，我们不需要锁住任何东西。而不需要锁住数据就能够移除 B 和 D 的主要原因就是 读-复制-更新(Ready-Copy-Update,RCU)，将更新过程中的移除和再分配过程分离开。
调度
当一个计算机是多道程序设计系统时，会频繁的有很多进程或者线程来同时竞争 CPU 时间片。当两个或两个以上的进程/线程处于就绪状态时，就会发生这种情况。如果只有一个 CPU 可用，那么必须选择接下来哪个进程/线程可以运行。操作系统中有一个叫做 调度程序(scheduler) 的角色存在，它就是做这件事儿的，该程序使用的算法叫做 调度算法(scheduling algorithm) 。
尽管有一些不同，但许多适用于进程调度的处理方法同样也适用于线程调度。当内核管理线程的时候，调度通常会以线程级别发生，很少或者根本不会考虑线程属于哪个进程。下面我们会首先专注于进程和线程的调度问题，然后会明确的介绍线程调度以及它产生的问题。
调度介绍
让我们回到早期以磁带上的卡片作为输入的批处理系统的时代，那时候的调度算法非常简单：依次运行磁带上的每一个作业。对于多道程序设计系统，会复杂一些，因为通常会有多个用户在等待服务。一些大型机仍然将 批处理和 分时服务结合使用，需要调度程序决定下一个运行的是一个批处理作业还是终端上的用户。由于在这些机器中 CPU 是稀缺资源，所以好的调度程序可以在提高性能和用户的满意度方面取得很大的成果。
进程行为
几乎所有的进程（磁盘或网络）I/O 请求和计算都是交替运行的
如上图所示，CPU 不停顿的运行一段时间，然后发出一个系统调用等待 I/O 读写文件。完成系统调用后，CPU 又开始计算，直到它需要读更多的数据或者写入更多的数据为止。当一个进程等待外部设备完成工作而被阻塞时，才是 I/O 活动。
上面 a 是 CPU 密集型进程；b 是 I/O 密集型进程进程，a 因为在计算的时间上花费时间更长，因此称为计算密集型(compute-bound) 或者 CPU 密集型(CPU-bound)，b 因为I/O 发生频率比较快因此称为 I/O 密集型(I/O-bound)。计算密集型进程有较长的 CPU 集中使用和较小频度的 I/O 等待。I/O 密集型进程有较短的 CPU 使用时间和较频繁的 I/O 等待。注意到上面两种进程的区分关键在于 CPU 的时间占用而不是 I/O 的时间占用。I/O 密集型的原因是因为它们没有在 I/O 之间花费更多的计算、而不是 I/O 请求时间特别长。无论数据到达后需要花费多少时间，它们都需要花费相同的时间来发出读取磁盘块的硬件请求。
值得注意的是，随着 CPU 的速度越来越快，更多的进程倾向于 I/O 密集型。这种情况出现的原因是 CPU 速度的提升要远远高于硬盘。这种情况导致的结果是，未来对 I/O 密集型进程的调度处理似乎更为重要。这里的基本思想是，如果需要运行 I/O 密集型进程，那么就应该让它尽快得到机会，以便发出磁盘请求并保持磁盘始终忙碌。
何时调度
第一个和调度有关的问题是何时进行调度决策。存在着需要调度处理的各种情形。首先，在创建一个新进程后，需要决定是运行父进程还是子进程。因为二者的进程都处于就绪态下，这是正常的调度决策，可以任意选择，也就是说，调度程序可以任意的选择子进程或父进程开始运行。
第二，在进程退出时需要作出调度决定。因为此进程不再运行（因为它将不再存在），因此必须从就绪进程中选择其他进程运行。如果没有进程处于就绪态，系统提供的空闲进程通常会运行
什么是空闲进程
空闲进程(system-supplied idle process) 是 Microsoft 公司 windows 操作系统带有的系统进程，该进程是在各个处理器上运行的单个线程，它唯一的任务是在系统没有处理其他线程时占用处理器时间。System Idle Process 并不是一个真正的进程，它是核心虚拟出来的，多任务操作系统都存在。在没有可用的进程时，系统处于空运行状态，此时就是System Idle Process 在正在运行。你可以简单的理解成，它代表的是 CPU 的空闲状态，数值越大代表处理器越空闲，可以通过 Windows 任务管理器查看 Windows 中的 CPU 利用率
第三种情况是，当进程阻塞在 I/O 、信号量或其他原因时，必须选择另外一个进程来运行。有时，阻塞的原因会成为选择进程运行的关键因素。例如，如果 A 是一个重要进程，并且它正在等待 B 退出关键区域，让 B 退出关键区域从而使 A 得以运行。但是调度程序一般不会对这种情况进行考量。
第四点，当 I/O 中断发生时，可以做出调度决策。如果中断来自 I/O 设备，而 I/O 设备已经完成了其工作，那么那些等待 I/O 的进程现在可以继续运行。由调度程序来决定是否准备运行新的进程还是重新运行已经中断的进程。
如果硬件时钟以 50 或 60 Hz 或其他频率提供周期性中断，可以在每个时钟中断或第 k 个时钟中断处做出调度决策。根据如何处理时钟中断可以把调度算法可以分为两类。非抢占式(nonpreemptive) 调度算法挑选一个进程，让该进程运行直到被阻塞（阻塞在 I/O 上或等待另一个进程），或者直到该进程自动释放 CPU。即使该进程运行了若干个小时后，它也不会被强制挂起。这样会在时钟中断发生时不会进行调度。在处理完时钟中断后，如果没有更高优先级的进程等待，则被中断的进程会继续执行。
另外一种情况是 抢占式 调度算法，它会选择一个进程，并使其在最大固定时间内运行。如果在时间间隔结束后仍在运行，这个进程会被挂起，调度程序会选择其他进程来运行（前提是存在就绪进程）。进行抢占式调度需要在时间间隔结束时发生时钟中断，以将 CPU 的控制权交还给调度程序。如果没有可用的时钟，那么非抢占式就是唯一的选择。
调度算法的分类
毫无疑问，不同的环境下需要不同的调度算法。之所以出现这种情况，是因为不同的应用程序和不同的操作系统有不同的目标。也就是说，在不同的系统中，调度程序的优化也是不同的。这里有必要划分出三种环境
批处理(Batch)交互式(Interactive)实时(Real time)
批处理系统广泛应用于商业领域，比如用来处理工资单、存货清单、账目收入、账目支出、利息计算、索赔处理和其他周期性作业。在批处理系统中，一般会选择使用非抢占式算法或者周期性比较长的抢占式算法。这种方法可以减少线程切换因此能够提升性能。
在交互式用户环境中，为了避免一个进程霸占 CPU 拒绝为其他进程服务，所以需要抢占式算法。即使没有进程有意要一直运行下去，但是，由于某个进程出现错误也有可能无限期的排斥其他所有进程。为了避免这种情况，抢占式也是必须的。服务器也属于此类别，因为它们通常为多个（远程）用户提供服务，而这些用户都非常着急。计算机用户总是很忙。
在实时系统中，抢占有时是不需要的，因为进程知道自己可能运行不了很长时间，通常很快的做完自己的工作并阻塞。实时系统与交互式系统的差别是，实时系统只运行那些用来推进现有应用的程序，而交互式系统是通用的，它可以运行任意的非协作甚至是有恶意的程序。
调度算法的目标
为了设计调度算法，有必要考虑一下什么是好的调度算法。有一些目标取决于环境（批处理、交互式或者实时）蛋大部分是适用于所有情况的，下面是一些需要考量的因素，我们会在下面一起讨论。
所有系统
在所有的情况中，公平是很重要的。对一个进程给予相较于其他等价的进程更多的 CPU 时间片对其他进程来说是不公平的。当然，不同类型的进程可以采用不同的处理方式。
与公平有关的是系统的强制执行，什么意思呢？如果某公司的薪资发放系统计划在本月的15号，那么碰上了疫情大家生活都很拮据，此时老板说要在14号晚上发放薪资，那么调度程序必须强制使进程执行 14 号晚上发放薪资的策略。
另一个共同的目标是保持系统的所有部分尽可能的忙碌。如果 CPU 和所有的 I/O 设备能够一直运行，那么相对于让某些部件空转而言，每秒钟就可以完成更多的工作。例如，在批处理系统中，调度程序控制哪个作业调入内存运行。在内存中既有一些 CPU 密集型进程又有一些 I/O 密集型进程是一个比较好的想法，好于先调入和运行所有的 CPU 密集型作业，然后在它们完成之后再调入和运行所有 I/O 密集型作业的做法。使用后者这种方式会在 CPU 密集型进程启动后，争夺 CPU ，而磁盘却在空转，而当 I/O 密集型进程启动后，它们又要为磁盘而竞争，CPU 却又在空转。。。。。。显然，通过结合 I/O 密集型和 CPU 密集型，能够使整个系统运行更流畅，效率更高。
批处理系统
通常有三个指标来衡量系统工作状态：吞吐量、周转时间和 CPU 利用率，吞吐量(throughout) 是系统每小时完成的作业数量。综合考虑，每小时完成 50 个工作要比每小时完成 40 个工作好。周转时间(Turnaround time) 是一种平均时间，它指的是从一个批处理提交开始直到作业完成时刻为止平均时间。该数据度量了用户要得到输出所需的平均等待时间。周转时间越小越好。
CPU 利用率(CPU utilization) 通常作为批处理系统上的指标。即使如此， CPU 利用率也不是一个好的度量指标，真正有价值的衡量指标是系统每小时可以完成多少作业（吞吐量），以及完成作业需要多长时间（周转时间）。把 CPU 利用率作为度量指标，就像是引擎每小时转动了多少次来比较汽车的性能一样。而且知道 CPU 的利用率什么时候接近 100% 要比什么什么时候要求得到更多的计算能力要有用。
交互式系统
对于交互式系统，则有不同的指标。最重要的是尽量减少响应时间。这个时间说的是从执行指令开始到得到结果的时间。再有后台进程运行（例如，从网络上读取和保存 E-mail 文件）的个人计算机上，用户请求启动一个程序或打开一个文件应该优先于后台的工作。能够让所有的交互式请求首先运行的就是一个好的服务。
一个相关的问题是 均衡性(proportionality)，用户对做一件事情需要多长时间总是有一种固定（不过通常不正确）的看法。当认为一个请求很复杂需要较多时间时，用户会认为很正常并且可以接受，但是一个很简单的程序却花费了很长的运行时间，用户就会很恼怒。可以拿彩印和复印来举出一个简单的例子，彩印可能需要1分钟的时间，但是用户觉得复杂并且愿意等待一分钟，相反，复印很简单只需要 5 秒钟，但是复印机花费 1 分钟却没有完成复印操作，用户就会很焦躁。
实时系统
实时系统则有着和交互式系统不同的考量因素，因此也就有不同的调度目标。实时系统的特点是必须满足最后的截止时间。例如，如果计算机控制着以固定速率产生数据的设备，未能按时运行的话可能会导致数据丢失。因此，实时系统中最重要的需求是满足所有（或大多数）时间期限。
在一些实事系统中，特别是涉及到多媒体的，可预测性很重要。偶尔不能满足最后的截止时间不重要，但是如果音频多媒体运行不稳定，声音质量会持续恶化。视频也会造成问题，但是耳朵要比眼睛敏感很多。为了避免这些问题，进程调度必须能够高度可预测的而且是有规律的。
批处理中的调度
现在让我们把目光从一般性的调度转换为特定的调度算法。下面我们会探讨在批处理中的调度。
先来先服务
很像是先到先得。。。可能最简单的非抢占式调度算法的设计就是 先来先服务(first-come,first-serverd)。使用此算法，将按照请求顺序为进程分配 CPU。最基本的，会有一个就绪进程的等待队列。当第一个任务从外部进入系统时，将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时，它们排到就绪队列尾部。当正在运行的进程阻塞，处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时，它会像一个新到达的任务，会排在队列的末尾，即排在所有进程最后。
这个算法的强大之处在于易于理解和编程，在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可；要添加一个新的作业或者阻塞一个进程，只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。
不过，先来先服务也是有缺点的，那就是没有优先级的关系，试想一下，如果有 100 个 I/O 进程正在排队，第 101 个是一个 CPU 密集型进程，那岂不是需要等 100 个 I/O 进程运行完毕才会等到一个 CPU 密集型进程运行，这在实际情况下根本不可能，所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行。
最短作业优先
批处理中，第二种调度算法是 最短作业优先(Shortest Job First)，我们假设运行时间已知。例如，一家保险公司，因为每天要做类似的工作，所以人们可以相当精确地预测处理 1000 个索赔的一批作业需要多长时间。当输入队列中有若干个同等重要的作业被启动时，调度程序应使用最短优先作业算法
如上图 a 所示，这里有 4 个作业 A、B、C、D ，运行时间分别为 8、4、4、4 分钟。若按图中的次序运行，则 A 的周转时间为 8 分钟，B 为 12 分钟，C 为 16 分钟，D 为 20 分钟，平均时间内为 14 分钟。
现在考虑使用最短作业优先算法运行 4 个作业，如上图 b 所示，目前的周转时间分别为 4、8、12、20，平均为 11 分钟，可以证明最短作业优先是最优的。考虑有 4 个作业的情况，其运行时间分别为 a、b、c、d。第一个作业在时间 a 结束，第二个在时间 a + b 结束，以此类推。平均周转时间为 (4a + 3b + 2c + d) / 4 。显然 a 对平均值的影响最大，所以 a 应该是最短优先作业，其次是 b，然后是 c ，最后是 d 它就只能影响自己的周转时间了。
需要注意的是，在所有的进程都可以运行的情况下，最短作业优先的算法才是最优的。
最短剩余时间优先
最短作业优先的抢占式版本被称作为 最短剩余时间优先(Shortest Remaining Time Next) 算法。使用这个算法，调度程序总是选择剩余运行时间最短的那个进程运行。当一个新作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程。这种方式能够使短期作业获得良好的服务。
交互式系统中的调度
交互式系统中在个人计算机、服务器和其他系统中都是很常用的，所以有必要来探讨一下交互式调度
轮询调度
一种最古老、最简单、最公平并且最广泛使用的算法就是 轮询算法(round-robin)。每个进程都会被分配一个时间段，称为时间片(quantum)，在这个时间片内允许进程运行。如果时间片结束时进程还在运行的话，则抢占一个 CPU 并将其分配给另一个进程。如果进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。轮询算法比较容易实现。调度程序所做的就是维护一个可运行进程的列表，就像下图中的 a，当一个进程用完时间片后就被移到队列的末尾，就像下图的 b。
时间片轮询调度中唯一有意思的一点就是时间片的长度。从一个进程切换到另一个进程需要一定的时间进行管理处理，包括保存寄存器的值和内存映射、更新不同的表格和列表、清除和重新调入内存高速缓存等。这种切换称作 进程间切换(process switch) 和 上下文切换(context switch)。如果进程间的切换时间需要 1ms，其中包括内存映射、清除和重新调入高速缓存等，再假设时间片设为 4 ms，那么 CPU 在做完 4 ms 有用的工作之后，CPU 将花费 1 ms 来进行进程间的切换。因此，CPU 的时间片会浪费 20% 的时间在管理开销上。耗费巨大。
为了提高 CPU 的效率，我们把时间片设置为 100 ms。现在时间的浪费只有 1%。但是考虑会发现下面的情况，如果在一个非常短的时间内到达 50 个请求，并且对 CPU 有不同的需求，此时会发生什么？50 个进程都被放在可运行进程列表中。如果 CP画U 是空闲的，第一个进程会立即开始执行，第二个直到 100 ms 以后才会启动，以此类推。不幸的是最后一个进程需要等待 5 秒才能获得执行机会。大部分用户都会觉得对于一个简短的指令运行 5 秒中是很慢的。如果队列末尾的某些请求只需要几号秒钟的运行时间的话，这种设计就非常糟糕了。
另外一个因素是如果时间片设置长度要大于 CPU 使用长度，那么抢占就不会经常发生。相反，在时间片用完之前，大多数进程都已经阻塞了，那么就会引起进程间的切换。消除抢占可提高性能，因为进程切换仅在逻辑上必要时才发生，即流程阻塞且无法继续时才发生。
结论可以表述如下：将上下文切换时间设置得太短会导致过多的进程切换并降低 CPU 效率，但设置时间太长会导致一个短请求很长时间得不到响应。最好的切换时间是在 20 - 50 毫秒之间设置。
优先级调度
轮询调度假设了所有的进程是同等重要的。但事实情况可能不是这样。例如，在一所大学中的等级制度，首先是院长，然后是教授、秘书、后勤人员，最后是学生。这种将外部情况考虑在内就实现了优先级调度(priority scheduling)
它的基本思想很明确，每个进程都被赋予一个优先级，优先级高的进程优先运行。
但是也不意味着高优先级的进程能够永远一直运行下去，调度程序会在每个时钟中断期间降低当前运行进程的优先级。如果此操作导致其优先级降低到下一个最高进程的优先级以下，则会发生进程切换。或者，可以为每个进程分配允许运行的最大时间间隔。当时间间隔用完后，下一个高优先级的进程会得到运行的机会。
可以静态或者动态的为进程分配优先级。在一台军用计算机上，可以把将军所启动的进程设为优先级 100，上校为 90 ，少校为 80，上尉为 70，中尉为 60，以此类推。UNIX 中有一条命令为 nice ，它允许用户为了照顾他人而自愿降低自己进程的优先级，但是一般没人用。
优先级也可以由系统动态分配，用于实现某种目的。例如，有些进程为 I/O 密集型，其多数时间用来等待 I/O 结束。当这样的进程需要 CPU 时，应立即分配 CPU，用来启动下一个 I/O 请求，这样就可以在另一个进程进行计算的同时执行 I/O 操作。这类 I/O 密集型进程长时间的等待 CPU 只会造成它长时间占用内存。使 I/O 密集型进程获得较好的服务的一种简单算法是，将其优先级设为 1/f，f 为该进程在上一时间片中所占的部分。一个在 50 ms 的时间片中只使用 1 ms 的进程将获得优先级 50 ，而在阻塞之前用掉 25 ms 的进程将具有优先级 2，而使用掉全部时间片的进程将得到优先级 1。
可以很方便的将一组进程按优先级分成若干类，并且在各个类之间采用优先级调度，而在各类进程的内部采用轮转调度。下面展示了一个四个优先级类的系统
它的调度算法主要描述如下：上面存在优先级为 4 类的可运行进程，首先会按照轮转法为每个进程运行一个时间片，此时不理会较低优先级的进程。若第 4 类进程为空，则按照轮询的方式运行第三类进程。若第 4 类和第 3 类进程都为空，则按照轮转法运行第 2 类进程。如果不对优先级进行调整，则低优先级的进程很容易产生饥饿现象。
多级队列
最早使用优先级调度的系统是 CTSS(Compatible TimeSharing System)。CTSS 是一种兼容分时系统，它有一个问题就是进程切换太慢，其原因是 IBM 7094 内存只能放进一个进程。
IBM 是哥伦比亚大学计算机中心在 1964 - 1968 年的计算机
CTSS 在每次切换前都需要将当前进程换出到磁盘，并从磁盘上读入一个新进程。CTSS 的设计者很快就认识到，为 CPU 密集型进程设置较长的时间片比频繁地分给他们很短的时间要更有效（减少交换次数）。另一方面，如前所述，长时间片的进程又会影响到响应时间，解决办法是设置优先级类。属于最高优先级的进程运行一个时间片，次高优先级进程运行 2 个时间片，再下面一级运行 4 个时间片，以此类推。当一个进程用完分配的时间片后，它被移到下一类
最短进程优先
对于批处理系统而言，由于最短作业优先常常伴随着最短响应时间，所以如果能够把它用于交互式进程，那将是非常好的。在某种程度上，的确可以做到这一点。交互式进程通常遵循下列模式：等待命令、执行命令、等待命令、执行命令。。。如果我们把每个命令的执行都看作一个分离的作业，那么我们可以通过首先运行最短的作业来使响应时间最短。这里唯一的问题是如何从当前可运行进程中找出最短的那一个进程。
一种方式是根据进程过去的行为进行推测，并执行估计运行时间最短的那一个。假设每个终端上每条命令的预估运行时间为 T0，现在假设测量到其下一次运行时间为 T1，可以用两个值的加权来改进估计时间，即aT0+ (1- 1)T1。通过选择 a 的值，可以决定是尽快忘掉老的运行时间，还是在一段长时间内始终记住它们。当 a = 1/2 时，可以得到下面这个序列
可以看到，在三轮过后，T0 在新的估计值中所占比重下降至 1/8。
有时把这种通过当前测量值和先前估计值进行加权平均从而得到下一个估计值的技术称作 老化(aging)。这种方法会使用很多预测值基于当前值的情况。
保证调度
一种完全不同的调度方法是对用户做出明确的性能保证。一种实际而且容易实现的保证是：若用户工作时有 n 个用户登录，则每个用户将获得 CPU 处理能力的 1/n。类似地，在一个有 n 个进程运行的单用户系统中，若所有的进程都等价，则每个进程将获得 1/n 的 CPU 时间。
彩票调度
对用户进行承诺并在随后兑现承诺是一件好事，不过很难实现。但是存在着一种简单的方式，有一种既可以给出预测结果而又有一种比较简单的实现方式的算法，就是 彩票调度(lottery scheduling)算法。
其基本思想是为进程提供各种系统资源（例如 CPU 时间）的彩票。当做出一个调度决策的时候，就随机抽出一张彩票，拥有彩票的进程将获得该资源。在应用到 CPU 调度时，系统可以每秒持有 50 次抽奖，每个中奖者将获得比如 20 毫秒的 CPU 时间作为奖励。
George Orwell 关于 所有的进程是平等的，但是某些进程能够更平等一些。一些重要的进程可以给它们额外的彩票，以便增加他们赢得的机会。如果出售了 100 张彩票，而且有一个进程持有了它们中的 20 张，它就会有 20% 的机会去赢得彩票中奖。在长时间的运行中，它就会获得 20% 的CPU。相反，对于优先级调度程序，很难说明拥有优先级 40 究竟是什么意思，这里的规则很清楚，拥有彩票 f 份额的进程大约得到系统资源的 f 份额。
如果希望进程之间协作的话可以交换它们之间的票据。例如，客户端进程给服务器进程发送了一条消息后阻塞，客户端进程可能会把自己所有的票据都交给服务器，来增加下一次服务器运行的机会。当服务完成后，它会把彩票还给客户端让其有机会再次运行。事实上，如果没有客户机，服务器也根本不需要彩票。
可以把彩票理解为 buff，这个 buff 有 15% 的几率能让你产生
速度之靴的效果。
公平分享调度
到目前为止，我们假设被调度的都是各个进程自身，而不用考虑该进程的拥有者是谁。结果是，如果用户 1 启动了 9 个进程，而用户 2 启动了一个进程，使用轮转或相同优先级调度算法，那么用户 1 将得到 90 % 的 CPU 时间，而用户 2 将之得到 10 % 的 CPU 时间。
为了阻止这种情况的出现，一些系统在调度前会把进程的拥有者考虑在内。在这种模型下，每个用户都会分配一些CPU 时间，而调度程序会选择进程并强制执行。因此如果两个用户每个都会有 50% 的 CPU 时间片保证，那么无论一个用户有多少个进程，都将获得相同的 CPU 份额。
实时系统中的调度
实时系统(real-time) 是一个时间扮演了重要作用的系统。典型的，一种或多种外部物理设备发给计算机一个服务请求，而计算机必须在一个确定的时间范围内恰当的做出反应。例如，在 CD 播放器中的计算机会获得从驱动器过来的位流，然后必须在非常短的时间内将位流转换为音乐播放出来。如果计算时间过长，那么音乐就会听起来有异常。再比如说医院特别护理部门的病人监护装置、飞机中的自动驾驶系统、列车中的烟雾警告装置等，在这些例子中，正确但是却缓慢的响应要比没有响应甚至还糟糕。
实时系统可以分为两类，硬实时(hard real time) 和 软实时(soft real time) 系统，前者意味着必须要满足绝对的截止时间；后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。在这两种情形中，实时都是通过把程序划分为一组进程而实现的，其中每个进程的行为是可预测和提前可知的。这些进程一般寿命较短，并且极快的运行完成。在检测到一个外部信号时，调度程序的任务就是按照满足所有截止时间的要求调度进程。
实时系统中的事件可以按照响应方式进一步分类为周期性(以规则的时间间隔发生)事件或 非周期性(发生时间不可预知)事件。一个系统可能要响应多个周期性事件流，根据每个事件处理所需的时间，可能甚至无法处理所有事件。例如，如果有 m 个周期事件，事件 i 以周期 Pi 发生，并需要 Ci 秒 CPU 时间处理一个事件，那么可以处理负载的条件是
只有满足这个条件的实时系统称为可调度的，这意味着它实际上能够被实现。一个不满足此检验标准的进程不能被调度，因为这些进程共同需要的 CPU 时间总和大于 CPU 能提供的时间。
举一个例子，考虑一个有三个周期性事件的软实时系统，其周期分别是 100 ms、200 m 和 500 ms。如果这些事件分别需要 50 ms、30 ms 和 100 ms 的 CPU 时间，那么该系统时可调度的，因为 0.5 + 0.15 + 0.2 < 1。如果此时有第四个事件加入，其周期为 1 秒，那么此时这个事件如果不超过 150 ms，那么仍然是可以调度的。忽略上下文切换的时间。
实时系统的调度算法可以是静态的或动态的。前者在系统开始运行之前做出调度决策；后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等信息时，静态调度才能工作，而动态调度不需要这些限制。
调度策略和机制
到目前为止，我们隐含的假设系统中所有进程属于不同的分组用户并且进程间存在相互竞争 CPU 的情况。通常情况下确实如此，但有时也会发生一个进程会有很多子进程并在其控制下运行的情况。例如，一个数据库管理系统进程会有很多子进程。每一个子进程可能处理不同的请求，或者每个子进程实现不同的功能（如请求分析、磁盘访问等）。主进程完全可能掌握哪一个子进程最重要（或最紧迫），而哪一个最不重要。但是，以上讨论的调度算法中没有一个算法从用户进程接收有关的调度决策信息，这就导致了调度程序很少能够做出最优的选择。
解决问题的办法是将 调度机制(scheduling mechanism) 和 调度策略(scheduling policy) 分开，这是长期一贯的原则。这也就意味着调度算法在某种方式下被参数化了，但是参数可以被用户进程填写。让我们首先考虑数据库的例子。假设内核使用优先级调度算法，并提供了一条可供进程设置优先级的系统调用。这样，尽管父进程本身并不参与调度，但它可以控制如何调度子进程的细节。调度机制位于内核，而调度策略由用户进程决定，调度策略和机制分离是一种关键性思路。
线程调度
当若干进程都有多个线程时，就存在两个层次的并行：进程和线程。在这样的系统中调度处理有本质的差别，这取决于所支持的是用户级线程还是内核级线程（或两者都支持）。
首先考虑用户级线程，由于内核并不知道有线程存在，所以内核还是和以前一样地操作，选取一个进程，假设为 A，并给予 A 以时间片控制。A 中的线程调度程序决定哪个线程运行。假设为 A1。由于多道线程并不存在时钟中断，所以这个线程可以按其意愿任意运行多长时间。如果该线程用完了进程的全部时间片，内核就会选择另一个进程继续运行。
在进程 A 终于又一次运行时，线程 A1 会接着运行。该线程会继续耗费 A 进程的所有时间，直到它完成工作。不过，线程运行不会影响到其他进程。其他进程会得到调度程序所分配的合适份额，不会考虑进程 A 内部发生的事情。
现在考虑 A 线程每次 CPU 计算的工作比较少的情况，例如：在 50 ms 的时间片中有 5 ms 的计算工作。于是，每个线程运行一会儿，然后把 CPU 交回给线程调度程序。这样在内核切换到进程 B 之前，就会有序列 A1,A2,A3,A1,A2,A3,A1,A2,A3,A1 。 如下所示
运行时系统使用的调度算法可以是上面介绍算法的任意一种。从实用方面考虑，轮转调度和优先级调度更为常用。唯一的局限是，缺乏一个时钟中断运行过长的线程。但由于线程之间的合作关系，这通常也不是问题。
现在考虑使用内核线程的情况，内核选择一个特定的线程运行。它不用考虑线程属于哪个进程，不过如果有必要的话，也可以这么做。对被选择的线程赋予一个时间片，而且如果超过了时间片，就会强制挂起该线程。一个线程在 50 ms 的时间片内，5 ms 之后被阻塞，在 30 ms 的时间片中，线程的顺序会是 A1,B1,A2,B2,A3,B3。如下图所示
用户级线程和内核级线程之间的主要差别在于性能。用户级线程的切换需要少量的机器指令（想象一下Java程序的线程切换），而内核线程需要完整的上下文切换，修改内存映像，使高速缓存失效，这会导致了若干数量级的延迟。另一方面，在使用内核级线程时，一旦线程阻塞在 I/O 上就不需要在用户级线程中那样将整个进程挂起。
从进程 A 的一个线程切换到进程 B 的一个线程，其消耗要远高于运行进程 A 的两个线程（涉及修改内存映像，修改高速缓存），内核对这种切换的消耗是了解到，可以通过这些信息作出决定。
</div>