路上

　　我们前面的使用房子做的比喻对于解释同步的概念是非常合适的，但对系统中另一个重要方面就不合适了。在我们的比喻中，多个线程是同时运行的。可是，在实际的系统中，一般只有一个处理器，那么在一个时间点上只能运行一件“事”。

单处理器情况

　　下面看看在实际系统中的真实运行情况，在较“经济”的情况下，一个系统中只有一个中央处理器。这时，在任何时间点就只能有一个线程可以运行。系统内核使用数种规则来决定让哪个线程运行并运行该线程。

多处理器情况

　　如果你购买的计算机有多个、相同的CPU，并且这些CPU共享内存与设备，那么就可以说你有了一个SMP系统了（SMP是对称多处理器的简称，指系统中的这些处理器是一样的）。这时，可以同时运行的线程的数量就受限于CPU的个数了。由于一个CPU一次只能运行一个线程，在有多个CPU的情况下，多个线程就可以同步运行。

　　我们可以忽略CPU的个数，而抽象的设计系统能够让多个线程同步运行，虽然实际情况并不是这样。

内核作为仲裁者

　　那么谁来决定在指定时间哪个线程运行呢？这就是内核的工作职责。

　　内核决定了在特定时刻可以使用CPU的线程，并切换环境变量到那个线程。下面详细说明一下内核对CPU做了什么。

　　CPU有一定数量的寄存器（寄存器的具体数量依赖于处理器的类型）。当线程运行的时候，线程的一些信息就保存在这些寄存器里面，例如当前程序位置等等。

　　当内核确定要让另外一个线程运行时，它就会：

1. 保存当前运行线程的寄存器以及环境变量信息；
2. 将新线程的寄存器以及环境变量信息载入CPU。

　　不过内核是如何确定另外一个要运行的线程的呢？它先检查某个特定线程当前是否有能力使用CPU。以前我们讨论互斥体时，曾经提到过一个阻塞状态（当一个线程拥有互斥体，而另外一个线程想要获取它时，第二个线程就会进入阻塞状态）。

　　从内核的角度来看，一个线程正在使用CPU，而另外一个线程因为正在等待互斥体而进入阻塞状态而不能够使用CPU。这种情况下，内核就让可以运行的线程使用CPU，而将其他线程放入其内部列表中（从而内核就可以跟踪对于互斥体的请求）。

　　这显然不是一个有趣的情况。假设很多线程可以使用CPU。以前我们提到过线程对于互斥体的访问是基于优先级以及等待时间。内核也是使用一个类似的策略来决定哪个线程应该接下来跟着运行的。也就是说有两个因素：优先级和调度算法来确定这个线程的执行顺序。

优先级

　　假设两个线程有能力使用CPU。如果这两个线程的优先级不同，那么解决办法就非常简单——系统内核就将CPU交给优先级最高的那个线程。N系统的优先级从1（最低的可用优先级）向上计数。需要注意的是优先级0是保留给空闲线程的，用户是不能使用这个优先级的。

　　如果另外一个有更高优先级的线程突然能够使用CPU了，系统内核就会立即执行环境变量切换，将其切换为这个有较高优先级的线程。这就是我们经常说的抢占——有较高优先级的线程抢占较低优先级的线程。当较高优先级线程完成之后，系统内核就将环境变量切换回刚才运行的较低优先级线程，称这个为接续(resumption)，内核接续了前一个线程的运行。

　　如果现在的两个可以使用CPU的线程拥有同样的优先级，该如何处理呢？

调度算法

　　假设这两个线程中的一个正在使用CPU。系统内核在这种情况下是按照什么规则执行环境变量切换的？系统内核所使用的两个主要的调度算法就是环形(Round Robin)和先入先出(FIFO)。

FIFO

　　在这种算法中，线程可以按自己的意愿，使用CPU任意长的时间。这就意味着，如果这个线程执行一个非常长的数学计算，并且没有较高优先级的线程抢占CPU，那么这个线程可能会永远的运行下去了。那么和它优先级相同的线程会如何呢？它们就被据于CPU的使用之外了。至于更低优先级的同样也没有运行的机会了。

　　如果运行线程退出或自动释放CPU，那么系统内核就查找能够使用CPU的同优先级的其他线程。如果找不到这样的线程，内核就会查找可以使用CPU的较低优先级的线程。自动释放CPU可能有两种情况，一个是线程进入睡眠状态，另一个就是线程因为信号量而阻塞等等，之后较低优先级的线程就可能运行了。除此之外，还有一个特别的调用函数sched_yield()，这个函数会让线程放弃CPU，让同优先级的其他线程使用——如果有较高优先级的线程已经就绪的话，较低优先级的线程就永远没有机会运行。如果一个线程调用了这个函数，可是没有同优先级的其他线程可以运行，那么原来这个线程就会继续运行。简单来说，sched_yield()函数就是让同优先级的线程有一个得到CPU并运行的机会。

环形（Round Robin）

　　RR调度算法与FIFO十分类似，不过有一点不同就是，如果有同优先级的线程正在等待运行，当前运行的线程就不会永远运行。它只会运行系统所设定的时间片（timeslice）那么长的时间。时间片的具体数值可以通过调用系统函数sched_rr_get_intercal()进行查询。通常时间片的具体值为4毫秒，实际上就是最小时间间隔的四倍，而最小时间间隔可以通过函数ClockPeriod()查询或设定。

　　具体实现是这样的，系统内核开始一个RR线程并留意其时间。如果这个RR线程运行了一会，并且分配给它的时间就要用完了（时间片就要失效了）。系统内核就会查找是否有同优先级的其他线程已经准备运行了。如果有的话，就运行那个线程。如果没有，系统内核就会继续运行这个RR线程（也就是为这个线程再分配了一个时间片）。

运行规则

　　对于单CPU的系统，线程的调度规则按重要性总结如下：

• 一次只能运行一个线程
• 较高优先级并已就绪的线程先开始运行
• 一个线程除了阻塞或退出之前就一直运行
• RR线程会运行分配给它的时间片那么长的时间，之后内核会重新调度它

Related posts:

1. 进程间通信
2. 线程的调度
3. 进程与线程
4. 进程与线程
5. 在单CPU上使用多线程