http://www.qnx.com/developers/docs/6.4.1/neutrino/getting_started/s1_procs.html

进程和线程的基本原理

在我们开始讨论线程、进程、时间片和所有其他奇妙的“调度概念”之前，让我们建立一个类比。我首先要做的是说明线程和进程是如何工作的。我能想到的最好的方法(不深入研究实时系统的设计)是想象线程和进程的各种场景。

一个进程是一个房子

让我们用一个普通的日常对象——房子来类比进程和线程。房子实际上是一个容器，具有某些属性(如地板空间的数量，卧室的数量，等等)。如果你从这个角度来看，房子本身并没有主动地做任何事情——它是一个被动的物体。这就是所谓的进程。我们很快就会探讨这个问题。

居住者是线程

住在房子里的人是活动的对象——他们在使用不同的房间，看电视，做饭，洗澡，等等。我们很快就会看到线程的行为。

简单的线程

如果你曾经一个人住过，那么你就会知道这是什么样子的——你知道你可以在任何时候在房子里做任何你想做的事情，因为房子里没有其他人。如果你想打开音响，去洗手间，吃晚饭——不管怎样——你就去做吧。

多线程

当你把另一个人加到房子里时，事情会发生戏剧性的变化。假设你结婚了，现在你的配偶也住在那里。你不能在任何时候都大摇大摆地走进洗手间;你需要先确认你的配偶不在里面!
如果你有两个负责任的成年人住在一所房子里，通常你可以在“安全”方面相当松懈——你知道另一个成年人会尊重你的空间，不会试图(故意的!)放火烧厨房，等等。现在，再加上几个孩子，事情突然变得有趣多了。

返回进程和线程

就像房子占用一块不动产一样，进程占用内存。正如房子的居住者可以自由进入任何他们想要的房间一样，进程的线程都可以共同访问该内存。如果一个线程分配了一些东西(妈妈出去买了一款游戏)，所有其他线程都可以立即访问它(因为它存在于公共地址空间——它在房子里)。同样，如果进程分配了内存，那么这个新的内存也可以被所有线程使用。这里的技巧是识别内存是否应该对进程中的所有线程可用。如果是，那么你需要让所有线程同步它们对它的访问。如果不是，那么我们假设它是特定于特定线程的。在这种情况下，因为只有这个线程可以访问它，所以我们可以假定不需要同步——线程不会自己出错!

互斥

如果你想洗澡，但已经有人在用浴室了，你就得等。线程如何处理这个问题?
这就是所谓的相互排斥。它的意思和你想的差不多——当涉及到特定的资源时，多个线程是互斥的。
如果你正在洗澡，你会想要单独使用浴室。要做到这一点，你通常会走进浴室，从里面把门锁上。其他想上厕所的人都会被锁拦住。当你完成后，你会打开门，让其他人进入。
这就是线程所做的。线程使用一个叫做mutex(缩写MUTual EXclusion)的对象。这个对象就像门上的锁——一旦一个线程锁定了互斥锁，其他线程就不能得到互斥锁，直到拥有它的线程释放(解锁)它。就像门锁一样，等待获取互斥锁的线程将被禁止。
互斥锁和门锁的另一个有趣的相似之处是互斥锁实际上是一个“建议”锁。如果一个线程没有遵守使用互斥锁的约定，那么这种保护是没有用的。用我们的房子来比喻，这就像有人没有开锁进门，而是从一面墙闯入洗手间。

优先级

如果浴室现在是锁着的，很多人都在等着用呢?很明显，所有人都坐在外面，等在厕所里的人出来。真正的问题是，“门打开时会发生什么?”下一个轮到谁了?”
你会认为让等待时间最长的人下一个离开是“公平的”。或者让年龄最大的人下一个离开也可能是“公平的”。或最高。还是最重要的。有很多方法可以决定什么是“公平的”。
我们通过两个因素来解决这个问题:优先级和等待时间。
线程也是一样。线程从其父线程继承其调度算法，但可以调用pthread_setschedparam()来更改其调度策略和优先级(如果它有权限这么做的话)。
如果有许多线程正在等待，互斥锁被解锁，我们将把互斥锁给予优先级最高的等待线程。然而，假设两个人有相同的优先级。现在你要做什么?好吧，在这种情况下，允许等待时间最长的人下一个离开是“公平的”。这不仅是“公平的”，而且也是Neutrino内核所做的。在有一堆线程等待的情况下，我们首先按优先级，其次按等待时间长度。
互斥对象当然不是我们将遇到的唯一同步对象。让我们看一些其他的。

信号量

让我们从浴室走到厨房，因为那是一个被社会接受的同时容纳多人的地方。在厨房里，你可能不想让所有人同时进去。事实上，你可能想要限制在厨房的人数(太多厨师，等等)。
假设你不希望同时有超过两个人在里面。你可以用互斥来做吗?不像我们定义的那样。为什么不呢?这对于我们的类比来说是一个非常有趣的问题。让我们将其分解为几个步骤。

计数为1的信号量

浴室有两种情况，有两种状态是相互关联的:

• 门没锁，房间里也没人
• 门是锁着的，房间里有一个人
  没有其他的组合是可能的——房间里没有人的时候门不能上锁(我们怎么开锁?)，房间里有人的时候门也不能上锁(他们怎么保证他们的隐私?)这是一个计数为1的信号量的例子——在那个房间里最多只能有一个人，或者一个线程使用这个信号量。

计数大于1的信号量

假设我们在厨房里安装了传统的钥匙锁。这把锁的工作原理是，如果你有钥匙，你可以打开门进去。任何用这把锁的人都同意，当他们进到里面时，他们会立即从里面把门锁上，所以外面的人总是需要一把钥匙。
好了，现在控制厨房里要有多少人就变得很简单了——在门外挂两把钥匙!厨房总是锁着的。当有人想进厨房时，他们会看看门外是否挂着一把钥匙。如果是这样，他们就随身带着钥匙，打开厨房门，走进去，用钥匙锁上门。

作为互斥锁的信号量

我们刚刚问了一个问题“你能用互斥器来做吗?”，而答案是否定的。反过来怎么样?我们可以使用一个信号量作为互斥量吗?
是的。事实上，在某些操作系统中，这正是它们所做的——它们没有互斥，只有信号量!那么，为什么要费心使用互斥锁呢?
要回答这个问题，看看你的洗手间。你房子的建造者是如何实现互斥的?我猜你墙上没有挂钥匙吧!
互斥是一种“特殊用途”的信号量。如果你想让一个线程在特定的代码段中运行，那么互斥锁是目前为止最有效的实现。
稍后，我们将看看其他同步方案——称为condvars、barrier和sleepons的东西。

为了避免混淆，请注意互斥锁还有其他属性，比如优先级继承，它们将互斥锁与信号量区分开来。

内核的角色

单一CPU

house的类比很好地传达了同步的概念，但它在一个主要领域中并不适用。在我们家里，有许多线程同时运行。然而，在真实的系统中，通常只有一个CPU，所以一次只能运行一个“东西”。

多CPU

如果你的系统具有多个相同的cpu，它们都共享内存和设备，那么你就拥有一个SMP框(SMP代表对称多处理器，“对称”部分表示系统中的所有cpu都是相同的)。在这种情况下，可以并发(同时)运行的线程数量受到cpu数量的限制。(实际上，单处理器盒子也是这样!)由于每个处理器一次只能执行一个线程，因此使用多个处理器时，多个线程可以同时执行。
让我们暂时忽略当前cpu的数量——一个有用的抽象是将系统设计成多个线程同时运行，即使事实并非如此。稍后，在“使用SMP时要注意的事项”一节中，我们将看到SMP的一些非直观影响。

将内核作为仲裁者

那么，谁来决定在任何给定时刻哪个线程将运行呢?这是内核的工作。
内核决定在特定时刻哪个线程应该使用CPU，并将上下文切换到该线程。让我们看看内核对CPU做了什么。
CPU有许多寄存器(确切的数字取决于处理器家族，例如，x86和MIPS，以及特定的家族成员，例如，80486和奔腾)。当线程运行时，信息存储在这些寄存器中(例如，当前程序的位置)。
当内核决定运行另一个线程时，它需要:
1.保存当前运行线程的寄存器和其他上下文信息
2.将新线程的寄存器和上下文加载到CPU中
但是内核如何决定另一个线程应该运行呢?它查看特定线程是否能够在此时使用CPU。例如，当我们谈到互斥锁时，我们引入了阻塞状态(当一个线程拥有互斥锁，而另一个线程也想获得它时，就会发生阻塞状态;第二个线程将被阻塞)。
因此，从内核的角度来看，我们有一个线程可以消耗CPU，而另一个线程不能，因为它被阻塞了，在等待一个互斥锁。在这种情况下，内核允许可以运行的线程消耗CPU，并将另一个线程放入一个内部列表中(这样内核就可以跟踪它对互斥锁的请求)。
显然，这不是一个很有趣的情况。假设有很多线程可以使用CPU。还记得我们根据优先级和等待时间分配对互斥锁的访问吗?内核使用类似的方案来确定下一个运行的线程。有两个因素:优先级和调度算法，以这个顺序评估。

优先级

考虑两个能够使用CPU的线程。如果这些线程有不同的优先级，那么答案非常简单——内核将CPU分配给优先级最高的线程。Neutrino的优先级从1(可用性最低的)到1，就像我们在讨论获取互斥锁时提到的那样。注意，优先级0是为空闲线程保留的——你不能使用它。(如果你想知道系统的最小值和最大值，请使用sched_get_priority_min()和sched_get_priority_max()函数——它们的原型在< sched_h >中。在本书中，我们假设1为最低可用值，255为最高可用值。)
如果另一个具有更高优先级的线程突然能够使用CPU，内核将立即上下文切换到更高优先级的线程。我们称之为抢占——高优先级线程抢占了低优先级线程。当高优先级线程完成时，内核上下文切换回之前运行的低优先级线程，我们称之为恢复——内核继续运行前一个线程。
现在，假设两个线程能够使用CPU，并且具有完全相同的优先级。

调度算法

让我们假设当前有一个线程正在使用CPU。在本例中，我们将研究内核用来决定何时进行上下文切换的规则。(当然，整个讨论只适用于具有相同优先级的线程——当更高优先级的线程准备使用它得到的CPU时;这就是在实时操作系统中拥有优先级的全部意义。)
Neutrino内核理解的两种主要调度算法(策略)是轮循(或称RR)和FIFO(先入先出)。(也有零星的日程安排，但这超出了本书的范围;参见系统架构指南的QNX Neutrino内核章节中的“Sporadic_scheduling”。)

FIFO

在FIFO调度算法中，允许一个线程在它想要的时间内消耗CPU。这意味着，如果该线程正在进行非常长的数学计算，并且没有其他更高优先级的线程准备好，那么该线程可能会永远运行下去。那么具有相同优先级的线程呢?他们也被锁在外面了。(这一点应该很明显，较低优先级的线程也被锁定了。)
如果正在运行的线程退出或自愿放弃CPU，那么内核将寻找具有相同优先级、能够使用CPU的其他线程。如果没有这样的线程，那么内核将寻找能够使用CPU的低优先级线程。注意，术语“自愿放弃CPU”可能意味着两种情况之一。如果线程进入睡眠状态，或者阻塞信号量等，那么是的，低优先级线程可以运行(如上所述)。但是还有一个“特殊”调用，sched_yield()(基于内核调用SchedYield())，它只将CPU让给另一个具有相同优先级的线程——如果高优先级的线程准备运行，则不会给低优先级的线程运行的机会。如果一个线程确实调用了sched_yield()，并且没有其他具有相同优先级的线程准备运行，那么原始线程将继续运行。实际上，sched_yield()用于在CPU上为另一个具有相同优先级的线程提供漏洞。
在下图中，我们看到三个线程在两个不同的进程中运行:

Three threads in two different processes

Two threads on the READY queue, one blocked, one running

轮循

RR调度算法与FIFO相同，只是如果有另一个线程具有相同的优先级，该线程不会永远运行。它只对系统定义的时间片运行，其值可以通过使用sched_rr_get_interval()函数确定。时间片通常是4毫秒，但它实际上是ticksize的4倍，你可以用ClockPeriod()查询或设置它。
发生的情况是内核启动一个RR线程，并记录时间。如果RR线程正在运行一段时间，分配给它的时间将会结束(时间片将会过期)。内核会查看是否有另一个具有相同优先级的线程已经就绪。如果有，则由内核运行。如果没有，则内核将继续运行RR线程(即内核授予该线程另一个时间片)。

The rules

让我们总结一下调度规则(针对单个CPU)，按重要性排序:

• 一次只能运行一个线程。
• 最高优先级的就绪线程将运行。
• 线程将一直运行，直到阻塞或退出。
• RR线程将运行它的时间片，然后内核将重新调度它(如果需要的话)。

下面的流程图显示了内核所做的决定:

Scheduling roadmap

对于多cpu系统，除了多个cpu可以同时运行多个线程之外，其他规则都是相同的。线程的运行顺序(即哪个线程在多个CPU上运行)的确定方式与在单个CPU上完全相同——最高优先级的就绪线程将在一个CPU上运行。对于低优先级或等待时间较长的线程，内核在何时调度它们方面具有一定的灵活性，以避免使用缓存时效率低下。有关SMP的更多信息，请参见[Multicore Processing User's Guide]。(http://www.qnx.com/developers/docs/6.4.1/multicore_en/user_guide/about.html).

内核的状态

我们已经松散地讨论了“running”、“ready”和“blocked”——现在让我们形式化这些线程状态。

RUNNING

Neutrino的运行状态仅仅意味着线程现在正在积极地消耗CPU。在SMP系统中，会有多个线程在运行;在单处理器系统上，只有一个线程在运行。

READY

就绪状态意味着这个线程现在可以运行——除非它没有运行，因为另一个线程(具有相同或更高的优先级)正在运行。如果两个线程能够使用CPU，一个线程优先级为10，一个线程优先级为7，那么优先级为10的线程将正在运行，优先级为7的线程将准备就绪。

The blocked states

我们怎么称呼阻塞状态呢?问题是，不只有一个阻塞状态。在Neutrino的作用下，实际上有十几种阻塞状态。
为什么那么多?因为内核会跟踪为什么线程会被阻塞。
我们已经看到了两种阻塞状态——当线程阻塞等待互斥锁时，该线程处于互斥锁状态。当线程阻塞等待信号量时，它处于SEM状态。这些状态只是指示线程阻塞在哪个队列(和哪个资源)上。
如果多个线程在一个互斥锁上阻塞(处于互斥锁阻塞状态)，那么它们不会受到内核的关注，直到拥有互斥锁的线程释放它。此时，一个被阻塞的线程已经就绪，内核会做出重新调度决策(如果需要的话)。
为什么“如果需要吗?”刚刚释放互斥锁的线程可能仍然有其他事情要做，并且比等待的线程具有更高的优先级。在本例中，我们转向第二条规则，它声明“最高优先级的就绪线程将运行”，这意味着调度顺序没有改变——更高优先级的线程继续运行。

内核状态，完整的列表

下面是内核阻塞状态的完整列表，以及对每种状态的简要解释。顺便说一下，这个列表可以在 <sys/neutrino.h> ，你会注意到所有的状态都以STATE_作为前缀(例如，这个表中的“READY”在头文件中以STATE_READY的形式列出):

Kernel states, the complete list

需要记住的重要一点是，当一个线程被阻塞时，无论阻塞在哪个状态，它都不会消耗CPU。相反，线程消耗CPU的唯一状态是运行状态。
我们将在消息传递章节中看到发送、接收和应答阻塞状态。NANOSLEEP状态与sleep()之类的函数一起使用，我们将在关于时钟、计时器和不时得到踢脚的那一章中了解它。INTR状态与interrupwait()一起使用，我们将在中断一章中介绍。大多数其他状态将在本章中讨论。