剖析虚幻渲染体系（18）- 操作系统（2）(上）

18.6 同步机制

本章涉及线程和进程间的通信、竞争条件、关键部分、互斥、硬件解决方案、严格交替、彼得森解决方案、生产者-消费者问题、信号量、事件计数器、监视器、消息传递和经典IPC问题，以及死锁的定义、特征、预防、避免等。

利用多线程并发提高性能的方式有两种：

• 任务并行（task parallelism）。将一个单个任务分成几部分，且各自并行运行，从而降低总运行时间。这种方式虽然看起来很简单直观，但实际操作中可能会很复杂，因为在各个部分之间可能存在着依赖。
• 数据并行（data parallelism）。任务并行的是算法（执行指令）部分，即每个线程执行的指令不一样；而数据并行是指令相同，但执行的数据不一样。SIMD也是数据并行的一种方式。

上面阐述了多线程并发的益处，接下来说说它的副作用。总结起来，副作用如下：

• 导致数据竞争。多线程访问常常会交叉执行同一段代码，或者操作同一个资源，又或者多核CPU的高度缓存同步问题，由此变化带来各种数据不同步或数据读写错误，由此产生了各种各样的异常结果，这便是数据竞争。
• 逻辑复杂化，难以调试。由于多线程的并发方式不唯一，不可预知，所以为了避免数据竞争，常常加入复杂多样的同步操作，代码也会变得离散、片段化、繁琐、难以理解，增加代码的辅助，对后续的维护、扩展都带来不可估量的阻碍。也会引发小概率事件难以重现的BUG，给调试和查错增加了数量级的难度。
• 不一定能够提升效益。多线程技术用得到确实会带来效率的提升，但并非绝对，常和物理核心、同步机制、运行时状态、并发占比等等因素相关，在某些极端情况，或者用得不够妥当，可能反而会降低程序效率。

18.6.1 同步基础

18.6.1.1 并行和并发

并行（Parallelism）是至少两个线程同时执行任务的机制。一般有多核多物理线程的CPU同时执行的行为，才可以叫并行，单核的多线程不能称之为并行。

并发（Concurrency）至少两个线程利用时间片（Timeslice）执行任务的机制，是并行的更普遍形式。即便单核CPU同时执行的多线程，也可称为并发。

并发的两种形式——上：双物理核心的同时执行（并行）；下：单核的多任务切换（并发）。

事实上，并发和并行在多核处理器中是可以同时存在的，比如下图所示，存在双核，每个核心又同时切换着多个任务：

部分参考文献严格区分了并行和并发，但部分文献并不明确指出其中的区别。虚幻引擎的多线程渲染架构和API中，常出现并行和并发的概念，所以虚幻是明显区分两者之间的含义。

18.6.1.2 阿姆达尔定律

阿姆达尔定律揭示的核心数和加速比图例。由此可见，可并行的任务占比越低，加速比获得的效果越差：当可并行任务占比为50%时，16核已经基本达到加速比天花板，无论后面增加多少核心数量，都无济于事；如果可并行任务占比为95%时，到2048个核心才会达到加速比天花板。

18.6.1.3 竞争条件

同个进程允许有多个线程，这些线程可以共享进程的地址空间、数据结构和上下文。进程内的同一数据块，可能存在多个线程在某个很小的时间片段内同时读写，这就会造成数据异常，从而导致了不可预料的结果。这种不可预期性便造就了竞争条件（Race Condition）。

在某些操作系统中，协同工作的进程可能共享一些共同的存储，每个进程都可以读写。共享存储可能在主存中（可能在内核数据结构中），也可能是共享文件；共享内存的位置不会改变通信的性质或出现的问题。为了了解进程间通信在实践中是如何工作的，现在让我们考虑一个简单但常见的示例：打印假脱机程序。当一个进程想要打印一个文件时，它会在一个特殊的后台处理程序目录中输入文件名。另一个进程，打印机守护进程，定期检查是否有要打印的文件，如果有，它会打印这些文件，然后从目录中删除它们的名称。

假设我们的后台处理程序目录有大量的插槽，编号为0、1、2…，每个插槽都可以保存一个文件名。还可以想象有两个共享变量，out指向下一个要打印的文件，in指向目录中的下一个空闲插槽。这两个变量很可能保存在所有进程都可以使用的两个字的文件中。在某一时刻，插槽0至3为空（文件已打印），插槽4至6已满（文件名列队打印）。进程A和B或多或少同时决定要将文件排队打印。这种情况如下图所示。

适用于墨菲定律（Murphy’s law），可能会发生以下情况。进程A读入并将值7存储在称为next_free_slot的局部变量中。就在这时，一个时钟中断发生了，CPU决定进程A已经运行了足够长的时间，因此它切换到进程B。进程B也读入并得到一个7，也将其存储在下一个空闲插槽的本地变量中。此时，两个进程都认为下一个可用插槽是7。

进程B现在继续运行，将其文件名存储在插槽7中，并在中更新为8，然后关闭并执行其他操作。

最后，进程A再次运行，从它停止的地方开始，查看下一个空闲插槽，在那里找到一个7，并将其文件名写入插槽7，擦除进程B刚才放在那里的名称。然后计算下一个空闲插槽+1，即8，并设置为8。后台处理程序目录现在在内部是一致的，因此打印机守护程序不会发现任何错误，但进程B永远不会收到任何输出。用户B将在打印机周围徘徊数年，渴望永远不会输出。像这样的情况，两个或多个进程正在读取或写入一些共享数据，最终结果取决于谁在何时运行，称为竞争条件。调试包含竞争条件的程序一点也不有趣。大多数测试运行的结果都很好，但偶尔会发生一些奇怪和无法解释的事情。不幸的是，随着内核数量的增加，并行度也在增加，争用情况变得越来越普遍。

18.6.1.4 互斥实现机制

常见的简单的互斥实现机制包含禁用中断（Disabling Interrupt）、锁变量（Lock Variable）、严格轮换法（Strict Alternation）等。

• 禁用中断

在单处理器系统上，最简单的同步解决方案是让每个进程在进入其关键区域后立即禁用所有中断，并在离开之前重新启用它们。禁用中断时，不会发生时钟中断。毕竟，由于时钟或其他中断，CPU只能从一个进程切换到另一个进程，中断关闭后，CPU将不会切换到其他进程。因此，一旦进程禁用了中断，它就可以检查和更新共享内存，而不用担心任何其他进程会干预。

这种方法通常没有吸引力，因为给用户进程关闭中断的能力是不明智的。如果其中一个这样做了，再也没有打开过呢？可能导致系统崩溃。此外，如果系统是多处理器（具有两个或更多CPU），禁用中断只影响执行禁用指令的CPU。其他的将继续运行，并可以访问共享内存。

另一方面，在更新变量或特别是列表时，内核本身常常可以方便地禁用一些指令的中断。例如，如果在就绪进程列表处于不一致状态时发生中断，则可能会出现争用条件。总之，禁用中断通常是操作系统本身的一项有用技术，但不适合作为用户进程的一般互斥机制。

由于多核芯片的数量不断增加，即使在低端PC中，通过禁用内核内的中断来实现互斥的可能性也越来越小。双核已经很常见，许多机器中有四个，8个、16个或32个也不远。在多核（即多处理器系统）中，禁用一个CPU的中断不会阻止其他CPU干扰第一个CPU正在执行的操作。因此，需要更复杂的方案。

• 锁变量

考虑使用一个共享（锁）变量，初始值为0。当进程想要进入其关键区域时，它首先测试锁。如果锁为0，进程将其设置为1并进入临界区域。如果锁已经是1，进程只会等待，直到它变为0。因此，0表示没有进程处于其关键区域，1表示某些进程处于其临界区域。

不幸的是，这个想法包含了与我们在后台处理程序目录中看到的完全相同的致命缺陷。假设一个进程读取锁并看到它是0，在它可以将锁设置为1之前，另一个进程被调度、运行并将锁设置成1。当第一个进程再次运行时，它也将把锁设置成了1，并且两个进程将同时处于其关键区域。

现在，可能认为我们可以通过先读取锁值，然后在存储到其中之前再次检查它来解决这个问题，但并无实质作用。如果第二个进程在第一个进程完成第二次检查后修改了锁，则会发生争用。

• 严格轮换法

下面代码显示了互斥问题的第三种方法。整数变量轮数（最初为0）跟踪进入关键区域的轮数，并检查或更新共享内存。最初，进程0检查回合，发现它为0，并进入其关键区域。进程1也发现它为0，因此处于一个严密的循环中，不断地测试它何时变为1。不断地测试变量，直到出现某个值，此行为称为忙等待（busy waiting），通常应该避免，因为会浪费CPU时间。只有当有合理的预期等待时间很短时，才会使用繁忙等待，使用繁忙等待的锁称为自旋锁（spin lock）。

// 关键区域问题的建议解决方案。
// 进程0
while (TRUE) 
{ 
    while (turn != 0) /* loop */ ;
    critical_region(); 
    turn = 1; 
    noncritical_region(); 
} 

// 进程1
while (TRUE) 
{
    while (turn != 1) /* loop */ ;
    critical_region();
    turn = 0;
    noncritical_region();
}

• 彼得森的解决方案

通过将轮流思想与锁定变量和警告变量的思想相结合，荷兰数学家T.Dekker是第一个为互斥问题设计不需要严格修改的软件解决方案的人。1981年，G.L.Peterson发现了一种更简单的实现互斥的方法，从而使Dekker的解决方案过时，其算法如下代码所示（忽略原型）。

#define FALSE 0
#define TRUE  1
#define N     2 /* number of processes */

int turn; /* whose turn is it? */
int interested[N]; /* all values initially 0 (FALSE) */

void enter_region(int process); /* process is 0 or 1 */
{
    int other; /* number of the other process */

    other = 1 − process; /* the opposite of process */
    interested[process] = TRUE; /* show that you are interested */
    turn = process; /* set flag */
    while (turn == process && interested[other] == TRUE) /* null statement */ ;
}

void leave_region(int process) /* process: who is leaving */
{
    interested[process] = FALSE; /* indicate departure from critical region */
}

• TSL指令

现在让我们来看一个需要硬件帮助的提案。有些计算机，特别是那些设计有多处理器的计算机，有如下指令：

TSL RX, LOCK

（测试并设置锁定），其工作原理如下。它将内存字锁的内容读入寄存器RX，然后在内存地址锁处存储一个非零值。读字和存储字的操作保证是不可分割的，在指令完成之前，任何其他处理器都不能访问内存字。执行TSL指令的CPU锁定内存总线，以禁止其他CPU访问内存，直到完成。

需要注意的是，锁定内存总线与禁用中断非常不同。禁用中断，然后对内存字执行读操作，然后再执行写操作，不会阻止总线上的第二个处理器访问读操作和写操作之间的字。事实上，禁用处理器1上的中断对处理器2没有任何影响。在处理器1完成之前，保持处理器2不在内存中的唯一方法是锁定总线，需要特殊的硬件设施（基本上是一条总线，声明总线已锁定，除锁定它的处理器外，其他处理器无法使用它）。

要使用TSL指令，我们将使用一个共享变量lock来协调对共享内存的访问。当锁为0时，任何进程都可以使用TSL指令将其设置为1，然后读取或写入共享内存。完成后，进程使用普通的移动指令将锁设置回0。

如何使用此指令来防止两个进程同时进入其关键区域？下图给出了解决方案，图中显示了虚拟（但典型）汇编语言中的四指令子程序。第一条指令将旧的锁值复制到寄存器，然后将锁设置为1。然后将旧的值与0进行比较。如果它不为零，则表示锁已设置，因此程序只需返回到开始处并再次测试它。它迟早会变为0（当当前处于其关键区域的进程完成其关键区域时），子例程返回并设置了锁。清除锁非常简单，程序只将0存储在锁中，不需要特殊的同步指令。

关键区域问题的一个解决方案现在很容易。在进入其关键区域之前，进程调用enter region，它会忙于等待直到锁空闲；然后它获取锁并返回。离开关键区域后，进程将调用leave region，该区域将0存储在锁中。与所有基于关键区域的解决方案一样，进程必须在正确的时间调用进入区域和离开区域，以便方法工作。如果一个进程作弊，互斥将失败。换言之，关键区域只有在进程合作的情况下才能发挥作用。

TSL的另一条指令是XCHG，自动交换两个位置的内容，例如寄存器和内存字。代码如下所示，可以看出，它与TSL的解决方案基本相同。所有Intel x86 CPU都使用XCHG指令进行低级同步。

18.6.2 线程同步

18.6.2.1 原子操作

一些看似简单快捷的操作实际上并不是线程安全的。即使是简单的C变量增量（x++）也不是线程或多处理器安全的。例如，考虑在两个处理器上并行运行的两个线程，它们对同一内存位置执行增量（下图）。

即使是简单的增量也需要读写。在上图中，每个线程可以将初始值（0）读入CPU寄存器，每个线程递增其处理器的寄存器，然后写回结果，写入X的最终结果是1而不是2。该图是一个粗略的简化，因为还有其他因素在起作用，如CPU缓存。但即使忽略这一点，也明显是一场数据争用。事实上，其中一个线程（比如T2）可能被抢占（例如在R递增之后），并且当T1继续递增X时，一旦T2接收到CPU时间，它将1写回X，明显地终止线程T1所做的所有递增。Windows常用的原子操作API如下：

LONG     InterlockedIncrement([in, out] LONG volatile *Addend);
SHORT     InterlockedIncrement16([in, out] SHORT volatile *Addend);
LONG64     InterlockedIncrement64([in, out] LONG64 volatile *Addend);
LONG    InterlockedIncrementNoFence(_Inout_ LONG volatile *Addend);

LONG     InterlockedDecrement([in, out] LONG volatile *Addend);
LONG     InterlockedDecrement16([in, out] LONG volatile *Addend);
LONG     InterlockedDecrement64([in, out] LONG volatile *Addend);

LONG     InterlockedOr([in, out] LONG volatile *Destination, [in] LONG Value);
LONG     InterlockedExchange([in, out] LONG volatile *Target, [in] LONG Value);

// 将指定的32位变量的值作为原子操作递增（加1）, 使用获取内存顺序语义执行。
LONG     InterlockedIncrementAcquire(_Inout_ volatile *Addend);
LONG      InterlockedIncrementRelease(_Inout_ LONG volatile *Addend);

(...)

18.6.2.2 临界区

对于简单的情况，例如整数增量，互锁函数族非常适用。然而，对于其他操作，需要更通用的机制。临界区（Critical Section）是基于最多一个线程获取锁的经典同步机制。我们需要具备四个条件才能找到一个好的解决方案：

1、临界区域内不可能同时存在两个进程。

2、不能对速度或CPU数量进行假设。

3、在其临界区域之外运行的任何进程都不会阻塞任何进程。

4、任何进程都不应该永远等待进入其关键区域。

抽象地说，我们想要的行为如下图所示。过程A在时间T1进入其临界区，稍后，时间T2，过程B试图进入其临界区域，但失败了，因为另一个过程已经在其临界区，我们一次只允许一个进程。因此，当A离开其临界区域时，B暂时暂停，直到时间T3，允许B立即进入。最终B离开（在T4），我们回到了最初的情况，在其关键区域没有过程。

一旦一个线程获得了一个特定的锁，其他线程就无法获得同一个锁，直到首先获得它的线程释放它。只有这样，等待线程中的一个（并且只有一个）才能获得锁。意味着在任何给定时刻，只有一个线程获得了锁。（下图）

获取锁的线程也是其所有者，意味着两件事：

1、所有者线程是唯一可以释放关键部分的线程。

2、如果所有者线程第二次（递归地）尝试获取临界区，则它会自动成功，并递增内部计数器。意味着所有者线程现在必须释放临界区相同的次数才能真正释放它。

获取锁和释放锁之间的代码称为临界区域（critical region）。

Windows涉及临界区的常用API如下所示：

// 初始化临界区
void InitializeCriticalSection(LPCRITICAL_SECTION lpCriticalSection);
BOOL InitializeCriticalSectionAndSpinCount(LPCRITICAL_SECTION lpCriticalSection, DWORD dwSpinCount);
BOOL InitializeCriticalSectionEx(LPCRITICAL_SECTION lpCriticalSection, DWORD dwSpinCount, DWORD Flags);

// 删除临界区
void DeleteCriticalSection(LPCRITICAL_SECTION lpCriticalSection);

// 进入临界区
void EnterCriticalSection(LPCRITICAL_SECTION lpCriticalSection);
// 离开临界区
void LeaveCriticalSection(LPCRITICAL_SECTION lpCriticalSection);

由于进入和离开临界区必须成对出现，我们可以使用RAII机制来确保这一点，示例代码：

struct AutoCriticalSection 
{
    AutoCriticalSection(CRITICAL_SECTION& cs)
    : _cs(cs) 
    {
        ::EnterCriticalSection(&_cs);
    }
    ~AutoCriticalSection()
    {
        ::LeaveCriticalSection(&_cs);
    }

    // delete copy ctor, move ctor, assignment operators
    AutoCriticalSection(const AutoCriticalSection&) = delete;
    AutoCriticalSection& operator=(const AutoCriticalSection&) = delete;
    AutoCriticalSection(AutoCriticalSection&&) = delete;
    AutoCriticalSection& operator=(AutoCriticalSection&&) = delete;

private:
    CRITICAL_SECTION& _cs;
};

当然，也可以将临界区封装成一个C++对象，以便提供更友好、安全的访问接口：

class CriticalSection : public CRITICAL_SECTION 
{
public:
    CriticalSection(DWORD spinCount = 0, DWORD flags = 0)
    {
        ::InitializeCriticalSectionEx(this, (DWORD)spinCount, flags);
    }
    ~CriticalSection()
    {
        ::DeleteCriticalSection(this);
    }

    void Lock()
    {
        ::EnterCriticalSection(this);
    }
    void Unlock()
    {
        ::LeaveCriticalSection(this);
    }
    bool TryLock()
    {
        return ::TryEnterCriticalSection(this);
    }
};

临界区的问题：考虑一个由n个进程（P0，P1，……，Pn-1）组成的系统，每个进程都有一段代码，这段代码称为临界区，其中进程可能会更改公共变量、更新表格、写入文件等。系统的重要特征是，当进程在其临界区执行时，不允许其他进程在其重要部分执行，进程对临界区的执行是相互排斥的。

临界区问题是设计一个协议，进程可以使用该协议来合作，每个进程必须请求许可才能进入其临界区。实现此请求的代码部分是入口区，出口区遵循临界段，剩余的代码是剩余区。

临界区问题的解必须满足以下三个条件：

• 互斥：如果进程Pi在其临界区执行，则任何其他进程都不能在其临界区域执行。互斥要求：
• 必须强制互斥：在具有同一资源或共享对象的临界区的所有进程中，每次只允许一个进程进入其临界区。
• 在非临界区停止的进程必须在不干扰其他进程的情况下停止。
• 要求访问临界区的进程不能无限期延迟：不能出现死锁或饥饿。
• 当没有进程处于临界区时，必须允许任何请求进入其临界区的进程立即进入。
• 没有对相对进程速度或处理器数量进行假设。
• 一个进程只在其临界区内停留有限的时间。
• 进程：如果没有进程正在其临界区执行，并且某些进程希望进入其临界区，那么只有那些未在其剩余区执行的进程才能进入其临界区。
• 限制等待：在进程发出请求后，允许其他进程进入其临界区的次数有限制。

硬件互斥方法如下：

• 中断禁用

在单处理器机器中，并发进程不能重叠，只能交错。此外，进程将继续运行，直到它调用操作系统服务或被中断。因此，为了保证互斥，只要防止进程被中断就足够了。此功能可以以系统内核定义的原语形式提供，用于禁用和启用中断。使用锁解决临界区问题：

do
{
    acquire lock
        critical section;
    release lock
        remainder section;
} while (TRUE);

因为临界区不能被中断，所以可以保证互斥。

缺点是它只能在单处理器环境中工作，如果不及时维护，中断可能会丢失，等待进入临界区的进程可能会挨饿。

• 测试和设置指令

它是用于避免相互排斥的特殊机器指令，测试和设置指令可定义如下：

boolean TestAndSet (boolean *target)
{
    boolean rv = *target;
    *target = TRUE;
    return rv:
}

上述功能自动执行。使用TestAndSet的解决方案，共享布尔变量锁已初始化为false：

do 
{
    while ( TestAndSet (&lock ))
        ; // do nothing
     // critical section
    lock = FALSE;
    // remainder section
} while (TRUE);

优势：简单易验证，适用于任何数量的进程，可用于支持多个临界区。缺点：可能会出现繁忙等待，可能出现饥饿，可能出现死锁。

• 交换指令

void Swap (boolean *a, boolean *b)
{
    boolean temp = *a;
    *a = *b;
    *b = temp:
}

共享布尔变量锁初始化为FALSE，每个进程都有一个局部布尔变量键：

do 
{
    key = TRUE;
    while( key == TRUE)
        Swap(&lock, &key);
    // critical section
    lock = FALSE;
    // remainder section
} while (TRUE);

带TestandSet()的有界等待互斥：

do 
{
    waiting[i] = TRUE;
    key = TRUE;
    while (waiting[i] && key)
        key = TestAndSet(&lock);
    waiting[i] = FALSE;
        // critical section
    j = (i + 1) % n;
    while ((j != i) && !waiting[j])
        j = (j + 1) % n;
    if (j == i)
        lock = FALSE;
    else
        waiting[j] = FALSE;
    // remainder section
} while (TRUE);

彼得森（Peterson）的解决方案：互斥问题是设计一个预协议（或入口协议）和一个后协议（或现有协议），以防止两个或多个线程同时处于其临界区。Tanenbaum研究了临界区问题或互斥问题的建议。问题是当一个进程更新其临界区中的共享可修改数据时，不应允许其他进程进入其临界区。临界区的建议如下：

• 禁用中断（硬件解决方案）。

每个进程在进入其临界区后禁用所有中断，并在离开临界区前重新启用所有中断。中断关闭后，CPU无法切换到其他进程。因此，没有任何其他进程会进入临界区的互斥状态。

禁用中断有时是一种有用的中断，有时是操作系统内核中的一种有用技术，但它不适合作为用户进程的一般互斥机制。原因是，给用户进程关闭中断的权力是不明智的。

• 锁定变量（软件解决方案）。

在这个解决方案中，我们考虑一个单一的共享（锁）变量，初始值为0。当一个进程想要进入其临界区时，它首先测试锁。如果lock为0，进程首先将其设置为1，然后进入临界区。如果锁已经是1，则进程只会等待（lock）变量变为0。因此，0表示其临界区没有进程，1表示某些进程在其临界区。

这个建议中的缺陷可以用例子来解释。假设进程A看到锁为0，在它可以将锁设置为1之前，另一个进程B被调度、运行并将锁设置成1。当进程A再次运行时，它也会将锁设置到1，并且两个进程将同时处于其临界区。

• 严格的替代方案。

在这个建议的解决方案中，整数变量“turn”跟踪谁将进入临界区。最初，进程A检查回合，发现它为0，并进入其临界区。进程B还发现它为0，并处于循环中，不断测试“turn”以查看它何时变为1，不断测试等待某个值出现的变量称为忙碌等待（Busy-Waiting）。

当其中一个进程比另一个慢得多时，轮流进行并不是一个好主意。假设进程0很快完成了它的临界区，所以这两个进程现在都处于非临界区，这种情况违反了上述条件3（限制等待）。

18.6.2.3 读写锁

使用临界区保护共享数据不受并发访问的影响效果很好，但这是一种悲观的机制——最多允许一个线程访问共享数据。在某些情况下，一些线程读取数据，而其他线程写入数据，可以进行优化：如果一个线程读取该数据，则没有理由阻止仅读取数据的其他线程同时执行，亦即“单写入多读取”机制。Windows API提供了表示这种锁的SRWLOCK结构（S表示“Slim”），其定义和相关API如下：

typedef struct _RTL_SRWLOCK 
{
    PVOID Ptr;
} RTL_SRWLOCK, *PRTL_SRWLOCK;

typedef RTL_SRWLOCK SRWLOCK, *PSRWLOCK;

void InitializeSRWLock(_Out_ PSRWLOCK SRWLock);
void AcquireSRWLockShared(_InOut_ PSRWLOCK SRWLock);
void AcquireSRWLockExclusive(_InOut_ PSRWLOCK SRWLock);
void ReleaseSRWLockShared(_Inout_ PSRWLOCK SRWLock);
void ReleaseSRWLockExclusive(_Inout_ PSRWLOCK SRWLock);

读写锁也可以用RAII封装起来：

class ReaderWriterLock : public SRWLOCK 
{
public:
    ReaderWriterLock();
    ReaderWriterLock(const ReaderWriterLock&) = delete;
    ReaderWriterLock& operator=(const ReaderWriterLock&) = delete;
    void LockShared();
    void UnlockShared();
    void LockExclusive();
    void UnlockExclusive();
};

struct AutoReaderWriterLockExclusive 
{
    AutoReaderWriterLockExclusive(SRWLOCK& lock);
    ~AutoReaderWriterLockExclusive();
private:
    SRWLOCK& _lock;
};

struct AutoReaderWriterLockShared 
{
    AutoReaderWriterLockShared(SRWLOCK& lock);
    ~AutoReaderWriterLockShared();
private:
    SRWLOCK& _lock;
};

// 相关接口的实现
ReaderWriterLock::ReaderWriterLock() 
{
    ::InitializeSRWLock(this);
}
void ReaderWriterLock::LockShared() 
{
    ::AcquireSRWLockShared(this);
}
void ReaderWriterLock::UnlockShared() 
{
    ::ReleaseSRWLockShared(this);
}
void ReaderWriterLock::LockExclusive() 
{
    ::AcquireSRWLockExclusive(this);
}
void ReaderWriterLock::UnlockExclusive() 
{
    ::ReleaseSRWLockExclusive(this);
}
AutoReaderWriterLockExclusive::AutoReaderWriterLockExclusive(SRWLOCK& lock)
: _lock(lock) 
{
    ::AcquireSRWLockExclusive(&_lock);
}
AutoReaderWriterLockExclusive::~AutoReaderWriterLockExclusive() 
{
    ::ReleaseSRWLockExclusive(&_lock);
}
AutoReaderWriterLockShared::AutoReaderWriterLockShared(SRWLOCK& lock)
: _lock(lock) 
{
    ::AcquireSRWLockShared(&_lock);
}
AutoReaderWriterLockShared::~AutoReaderWriterLockShared() 
{
    ::ReleaseSRWLockShared(&_lock);
}

18.6.2.4 条件变量

条件变量（Condition Variable）是另一种同步机制，提供了等待临界区或SRW锁的能力，直到出现某种条件。条件变量的一个经典应用示例是生产者/消费者场景。假设一些线程生成数据项并将它们放置在队列中，每个线程都执行生成项目（item）所需的任何工作，同时，其他线程充当消费者——每个线程从队列中删除一个项目，并以某种方式处理它（下图）。

如果项目的生产速度快于消费者的处理速度，则队列不为空，消费者继续工作。另一方面，如果消费者线程处理所有项目，它们应该进入等待状态，直到生成新的项目，在这种情况下，它们应该被唤醒——正是条件变量提供的行为。与之无关的使用者线程（队列为空）不应自旋（spin），定期检查队列是否变为非空，因为会毫无理由地消耗CPU周期。条件变量允许高效等待（不消耗CPU），直到线程被唤醒（通常由生产者线程唤醒）。

Windows的条件变量由CONDITION_VARIABLE不透明结构表示，使用类似于SRWLOCK，相关API如下：

void InitializeConditionVariable(PCONDITION_VARIABLE ConditionVariable);
BOOL SleepConditionVariableCS(PCONDITION_VARIABLE ConditionVariable, PCRITICAL_SECTION CriticalSection, DWORD dwMilliseconds);
BOOL SleepConditionVariableSRW(PCONDITION_VARIABLE ConditionVariable, PSRWLOCK SRWLock, DWORD dwMilliseconds, ULONG Flags);
VOID WakeConditionVariable (PCONDITION_VARIABLE ConditionVariable);
VOID WakeAllConditionVariable (PCONDITION_VARIABLE ConditionVariable);

线程一旦被唤醒，将重新获取同步对象并继续执行。此时，线程应该重新检查它等待的条件，如果不满足，则再次调用Sleep*函数。如下图所示（使用临界区）。

上图涉及的步骤如下：

1、使用者线程获取临界区。

2、线程检查是否可以继续，例如可以检查应该处理的队列是否为空。

3、如果它为空，则线程调用SleepConditionVariableCS，将释放临界区（以便另一个线程可以获取它）并进入睡眠（等待状态）。

4、在某些时候，生产者线程将通过调用WakeConditionVariable来唤醒消费者线程，例如向队列中添加了一个新的项。

5、SleepConditionVariableCS返回，获取临界区并返回检查是否可以继续。如果没有，它将继续等待。

6、现在可以继续了，线程可以执行它的工作（例如从队列中删除项）。临界区仍然保留。

7、最后，工作完成，临界区分必须释放。

18.6.2.5 等待地址

Windows 8和Server 2012添加了另一种同步机制，允许线程高效地等待，直到某个地址的值更改为所需值，然后它可以醒来继续工作。当然可以使用其他同步机制来实现类似的效果，例如使用条件变量，但等待地址（Waiting on Address）更有效，并且不容易死锁，因为没有直接使用临界区（或其他软件同步原语）。线程可以通过调用WaitOnAddress进入等待状态，直到某个值出现在“受监视”数据上，相关API：

BOOL WaitOnAddress(volatile VOID* Address, PVOID CompareAddress, SIZE_T AddressSize, DWORD dwMilliseconds);
VOID WakeByAddressSingle(_In_ PVOID Address);
VOID WakeByAddressAll(_In_ PVOID Address);

18.6.2.6 同步屏障

Windows 8中引入的另一个同步原语是同步屏障（Synchronization Barrier），它允许同步线程，这些线程需要到达工作中的某个点才能继续。例如，假设系统有几个部分，在主应用程序代码可以继续之前，每个部分都需要分两个阶段初始化。实现这一点的一种简单方法是顺序调用每个初始化函数：

void RunApp()
{
    // phase 1
    InitSubsystem1();
    InitSubsystem2();
    InitSubsystem3();
    InitSubsystem4();

    // phase 2
    InitSubsystem1Phase2();
    InitSubsystem2Phase2();
    InitSubsystem3Phase2();
    InitSubsystem4Phase2();

    // go ahead and run main application code...
}

虽然以上可行，但是如果每个初始化都可以同时进行，那么每个初始化都由不同的线程执行。在所有其他线程完成phase 1之前，每个线程不得继续进行phase 2初始化。当然，可以通过使用其他同步原语的组合来实现这种方案，但已经存在用于这种目的的同步屏障。Windows使用SYNCHRONIZATION_BARRIER不透明结构表示，且使用InitializeSynchronizationBarrier进行初始化，相关API：

BOOL InitializeSynchronizationBarrier(LPSYNCHRONIZATION_BARRIER lpBarrier, LONG lTotalThreads, LONG lSpinCount);
BOOL EnterSynchronizationBarrier(LPSYNCHRONIZATION_BARRIER lpBarrier, DWORD dwFlags);

该函数仅在释放屏障后，对单个线程返回TRUE，对所有其他线程返回FALSE。在前面描述的场景中，以下是在单独线程中运行的初始化函数之一：

DWORD WINAPI InitSubSystem1(PVOID p) 
{
    auto barrier = (PSYNCHRONIZATION_BARRIER)p;

    // phase 1
    printf("Subsystem 1: Starting phase 1 initialization (TID: %u)...\n", ::GetCurrentThreadId());
    // do work...
    printf("Subsystem 1: Ended phase 1 initialization...\n");

    // 进入屏障
    ::EnterSynchronizationBarrier(barrier, 0);

    printf("Subsystem 1: Starting phase 2 initialization...\n");
    // do work
    printf("Subsystem 1: Ended phase 2 initialization...\n");

    return 0;
}

phase 1初始化完成后，调用EnterSynchronizationBarrier，等待所有其他线程完成phase 1初始化。主函数可以这样编写：

SYNCHRONIZATION_BARRIER sb;
// 初始化屏障
InitializeSynchronizationBarrier(&sb, 4, -1);
LPTHREAD_START_ROUTINE functions[] = {InitSubSystem1, InitSubSystem2, InitSubSystem3, InitSubSystem4};
printf("System initialization started\n");

HANDLE hThread[4];
int i = 0;
for (auto f : functions) 
{
    hThread[i++] = ::CreateThread(nullptr, 0, f, &sb, 0, nullptr);
}
// 等待所有屏障
::WaitForMultipleObjects(_countof(hThread), hThread, TRUE, INFINITE);

printf("System initialization complete\n");
// close thread handles...

18.6.3 进程通信和同步

进程间通信（Inter process communication，IPC）是一种允许进程相互通信并同步其操作的机制。这些进程之间的通信可以看作是它们之间合作的一种方法，操作系统中并发执行的进程可以是独立进程，也可以是协作进程。如果一个进程不能影响或不受系统中执行的其他进程的影响，则该进程是独立的，任何不与任何其他进程共享数据的进程都是独立的。如果一个进程可以影响或受到系统中执行的其他进程的影响，那么它就是在合作。显然，任何与其他进程共享数据的进程都是一个协作进程。进程合作的原因：

• 信息共享。由于多个用户可能对同一条信息感兴趣（例如，共享文件），我们必须提供一个允许并发访问此类信息的环境。
• 计算加速。如果我们希望某个特定任务运行得更快，我们必须将其分解为子任务，每个子任务将与其他任务并行执行。请注意，只有当计算机具有多个处理核心时，才能实现这种加速。
• 模块化。我们可能希望以模块化的方式构建系统，将系统功能划分为单独的进程或线程。
• 便利性。即使是单个用户也可以同时处理许多任务。例如，用户可以同时编辑、听音乐和编译。

进程间通信机制。

进程间通信有两种基本模型：

• 共享内存。在共享内存模型中，建立了协作进程共享的内存区域。然后，进程可以通过将数据读写到共享区域来交换信息。共享内存可能比消息传递更快，因为消息传递系统通常使用系统调用实现，因此需要更耗时的内核干预任务。
• 消息传递。在消息传递模型中，通信通过协作进程之间交换的消息进行。消息传递对于交换少量数据非常有用，因为不需要避免冲突，在分布式系统中比共享内存更容易实现。

消息传递示例。

Solaris同步数据结构。

Windows同步对象。

非直接进程通信。

在共享内存系统中，使用共享内存的进程间通信要求通信进程建立共享内存区域。通常，共享内存区域驻留在创建共享内存段的进程的地址空间中。其他希望使用此共享内存段进行通信的进程必须将其连接到其地址空间，通常操作系统会尝试阻止一个进程访问另一个进程的内存。共享内存要求两个或更多进程同意删除此限制。然后，他们可以通过读取和写入共享区域中的数据来交换信息，数据的形式和位置由这些进程决定，不受操作系统的控制。这些进程还负责确保它们不会同时写入同一位置。

竞争条件（Race Condition）的情况是多个进程同时访问和操作相同的数据，执行结果取决于访问发生的特定顺序。假设两个进程P1和P2共享全局变量a，在执行过程中，P1会将a更新为值1，而在执行过程的某个时刻，P2会将a更新为值2，因此，这两个任务正在竞争地写入变量a。在本例中，比赛的“失败者”（最后更新的进程）决定a的最终值。

因此，操作系统关注以下事项：

• 操作系统必须能够跟踪各种进程。
• 操作系统必须为每个活动进程分配和取消分配各种资源。
• 操作系统必须保护每个进程的数据和物理资源免受其他进程的意外干扰。
• 相对于其他并发进程的速度、功能及输出必须独立于其执行速度。

进程交互可以定义为相互之间的不感知、间接感知和直接感知。并发进程在以下情形之一会发生冲突：

• 争夺同一资源的使用。
• 两个或多个进程在执行过程中需要访问资源。
• 每个进程都不知道其他进程的存在。
• 竞争进程之间没有信息交换。

进程经常需要与其他进程进行通信，最好是以结构良好的方式进行，而不是使用中断。简单地说，有三个问题：

1、一个进程如何向另一个进程传递信息。

2、与确保两个或多个进程不会相互妨碍有关，例如，航空公司预订系统中的两个进程，每个进程都试图为不同的客户抢占飞机上的最后一个座位。

3、涉及存在依赖项时的正确排序：如果进程A生成数据，进程B打印它们，B必须等到A生成了一些数据后才能开始打印。

同样重要的是，其中两个问题同样适用于线程。。

18.6.3.1 调度对象

Windows内核对象相关的最重要的几点描述如下：

• 内核对象位于系统（内核）空间，理论上可以从任何进程访问，前提是进程可以获得请求对象的句柄。
• 句柄和进程相关。
• 有三种方法可以跨进程共享对象：句柄继承、名称和句柄复制。

一些内核对象更为特殊，称为调度对象（dispatcher object）或可等待对象（waitable object）。此类对象可以处于两种状态之一：有信号（signaled）或无信号（non-signaled）。有信号和非信号的含义取决于对象的类型，下表总结了常见调度对象的这些状态的含义。

对象类型    有信号    无信号
进程（Process）    Exited/Terminated    Running
线程（Thread）    Exited/Terminated    Running
作业（Job）    已达到作业结束时间    未达到或未设置限制
互斥体（Mutex）    免费（无拥有者）    被拥有
信号量（Semaphore）    计数大于0    计数等于0
事件（Event）    事件被设置    事件未被设置
文件（File）    I/O操作完成    I/O操作正在进行或未开始
可等待计时器（Waitable Timer）    计时器计数已过期    计时器计数未过期
I/O完成    异步I/O操作已完成    异步I/O操作未完成

等待对象发出信号通常由以下两个功能之一完成（I/O完成端口除外，该端口具有自己的等待功能）：

DWORD WaitForSingleObject(HANDLE hHandle, DWORD dwMilliseconds);
DWORD WaitForMultipleObjects(DWORD nCount, CONST HANDLE* lpHandles, BOOL bWaitAll, DWORD dwMilliseconds);

WaitForSingleObject可能有四个返回值：

• WAIT_OBJECT_0：等待结束，因为对象在超时到期之前发出信号。
• WAIT_TIMEOUT：在线程等待时，对象没有发出信号。如果超时是无限的，则永远不会返回此值。
• WAIT_FAILED：由于某种原因，该功能失败。
• WAIT_ABANDONED：等待在互斥对象上，互斥对象已被放弃。

如果等待函数成功，因为一个或多个对象发出信号，线程将被唤醒并可以继续执行。刚刚发出信号的对象是否仍处于信号状态？取决于对象的类型。某些对象仍保持其信号状态，例如进程和线程。一个进程一旦退出或终止，就会发出信号，并在其剩余生命周期内保持这种状态（当该进程有打开的句柄时）。

某些类型的对象可能在成功等待后改变其信号状态。例如，对互斥体的成功等待会将其返回到无信号状态。另一个在发出信号时表现出特殊行为的对象是自动重置事件。当发出信号时，它会释放一个线程（并且只释放一个），当这种情况发生时，它的状态会自动切换到无信号状态。

如果多个线程等待同一个互斥体，并且它发出信号，会发生什么？只有一个线程可以在互斥体翻转回无信号状态之前获取互斥体。在背后，对象的等待线程存储在先进先出（FIFO）队列中，因此队列中的第一个线程是被唤醒的线程（无论其优先级如何）。但是，不应依赖这种行为。一些内部机制可能会使线程不再等待（例如，如果线程被挂起，例如使用调试器），然后当线程恢复时，它将被推到队列的后面。所以这里的简单规则是，无法确定哪个线程将首先唤醒。该算法可能在未来的Windows版本中随时更改。

18.6.3.2 互斥体

互斥体（mutex，mutual exclusion的缩写）也常被称为互斥锁、互斥量、互斥对象等，提供了与临界区类似的功能，保护共享数据免受并发访问。一次只有一个线程可以成功获取互斥体，并继续访问共享数据。等待互斥体的所有其他线程必须继续等待，直到获取线程释放互斥体。Windows的相关API：

HANDLE CreateMutex(LPSECURITY_ATTRIBUTES lpMutexAttributes, BOOL bInitialOwner, LPCTSTR lpName);
HANDLE CreateMutexEx(LPSECURITY_ATTRIBUTES lpMutexAttributes, LPCTSTR lpName, DWORD dwFlags, DWORD dwDesiredAccess);

HANDLE OpenMutexW(DWORD dwDesiredAccess, BOOL bInheritHandle, LPCWSTR lpName);

BOOL ReleaseMutex(_In_ HANDLE hMutex);

如果拥有互斥的线程退出或终止（无论出于什么原因），会发生什么？由于互斥体的所有者是唯一可以释放互斥体，可能会导致死锁，其他等待互斥的线程永远不会获取它。这种互斥体称为废弃互斥体（abandoned mutex），是由其所有者线程废弃的。

幸运的是，内核知道互斥体的所有权，因此如果看到一个线程在持有互斥体时终止（如果是这样的话，则会有多个），内核会显式释放被放弃的互斥体。这会导致成功获取互斥锁的下一个线程从其WaitForSingleObject调用中取回WAIT_ABANDONED，而不是WAIT_OBJECT_0。意味着线程正常获取互斥体，但特殊返回值用作提示，以指示前一个所有者在终止前没有释放互斥体。

18.6.3.3 信号量

信号量（Semaphore）是一个整数变量，除了初始化之外，只能通过两个标准原子操作访问：wait()和signal()。wait()操作最初称为P，signal()最初称为V。

P和V操作示意图。图中显示了一个任务T0执行的P()函数调用序列，以及另一个任务或ISR对同一信号量执行的V()函数。

信号量作为通用同步工具：

• 计数信号量：整数值可以覆盖非限制域。
• 二进制信号量：整数值的范围只能介于0和1之间。
• 可以更简单地实现。
• 也被称为互斥锁，可以将计数信号量实现为二进制信号量。
• 提供互斥信号量互斥。

// initialized
do 
{
    wait (mutex);
    // Critical Section
    signal (mutex);
} while (TRUE);

信号量实现：必须保证没有两个进程可以同时对同一信号量执行wait()和signal()。因此，实现成为临界区问题，其中等待和信号代码放置在临界区。现在可以使用忙碌等待临界区的实现，实现代码很短，如果临界区很少被占用，则很少忙碌等待。请注意，应用程序可能会在临界区花费大量时间，因此不是一个好的解决方案。

无忙碌等待的信号量实现：每个信号量都有一个相关的等待队列，等待队列中的每个条目都有两个数据项：值（整数类型）和指向列表中下一条记录的指针。有两种操作：阻塞——将调用操作的进程放在适当的等待队列中；唤醒——删除等待队列中的一个进程，并将其放入就绪队列。

// 等待实现
wait(semaphore *S) 
{
    S->value--;
    if (S->value < 0) 
    {
        add this process to S->list;
        block();
    }
}

// 信号实现
signal(semaphore *S) 
{
    S->value++;
    if (S->value <= 0) 
    {
        remove a process P from S->list;
        wakeup(P);
    }
}

信号量不被硬件支持，但有几个吸引人的特性：

• 信号量与设备无关。
• 信号量易于实现。
• 正确性易于确定。
• 可以有多个不同的临界区和不同的信号量。
• 信号量同时获得许多资源。

信号量的不足：

• 本质上是共享的全局变量。
• 可以从程序中的任何位置访问信号量。
• 无法控制或保证正确使用。
• 信号量和信号量控制访问的数据之间没有语言连接。
• 它们有两个目的：互斥和调度约束。

虽然信号量为进程同步提供了一种方便而有效的机制，但错误地使用它们会导致难以检测的定时错误，因为这些错误只有在发生特定的执行序列时才会发生，而这些序列并不总是发生。

信号量机制示意图。

进程访问受信号量保护的共享数据。

监视器是一种编程语言结构，提供与信号量等效的功能，并且更易于控制。监视器结构已经在许多编程语言中实现，包括Concurrent Pascal、Pascal Plus、Modula-2、Modula-3和Java。抽象数据类型或ADT用一组函数封装数据，以对该数据进行操作，这些函数独立于ADT的任何特定实现。监视器类型是一种ADT，包含一组程序员定义的操作，这些操作在监视器中互斥。监视器类型还声明其值定义该类型实例状态的变量，以及操作这些变量的函数体。它也被实现为一个程序库，允许程序员在任何对象上放置监视器锁。监视器语法：

monitor monitor_name
{
    /* shared variable declarations */
    function P1(...) 
    {
        ...
    }
    function P2 (...) 
    {
        ...
    }

    ...

    function Pn (...) 
    {
        ...
    }
    initialization code (...) 
    {
        ...
    }
}

因此，在监控器中定义的函数只能访问监控器中局部声明的变量及其形式参数。类似地，监视器的局部变量只能由局部函数访问。

在Windows中，信号量的作用是以线程安全的方式限制某些东西。信号量用当前和最大计数初始化。只要其当前计数高于零，它就处于信号状态。每当一个线程调用信号量上的WaitForSingleObject并且它处于信号状态时，信号量的计数就会减少，并且允许线程继续。一旦信号量计数达到零，它就变成无信号的，任何试图等待它的线程都将阻塞。相反，想要“释放”一个信号量计数（或更多）的线程调用ReleaseSemaphore，导致信号量计数增加并再次将其设置为有信号状态。

HANDLE CreateSemaphore( LPSECURITY_ATTRIBUTES lpSemaphoreAttributes, ...);
HANDLE CreateSemaphoreEx( LPSECURITY_ATTRIBUTES lpSemaphoreAttributes, ...);
BOOL   ReleaseSemaphore( HANDLE hSemaphore, ...);

18.6.3.4 事件

在某种意义上，事件（Event）是最简单的同步原语——它只是一个可以设置（信号状态）或重置（非信号状态）的标志。作为（可能命名的）内核对象，它具有在单个进程内或跨进程工作的灵活性。与事件相关联的复杂性在于有两种类型的事件：手动重置和自动重置。下表总结了它们的特性。

Windows相关的API：

HANDLE CreateEvent( LPSECURITY_ATTRIBUTES lpEventAttributes, BOOL bManualReset, BOOL bInitialState, LPCTSTR lpName);
HANDLE CreateEventEx( LPSECURITY_ATTRIBUTES lpEventAttributes, LPCTSTR lpName, DWORD dwFlags, DWORD dwDesiredAccess);

HANDLE OpenEvent( DWORD dwDesiredAccess, BOOL bInheritHandle, LPCTSTR lpName);

BOOL SetEvent(_In_ HANDLE hEvent); // signaled
BOOL ResetEvent(_In_ HANDLE hEvent); // non-signaled

BOOL PulseEvent(_In_ HANDLE hEvent);

18.6.3.5 可等待计时器

Windows API提供了对具有不同语义和编程模型的多个计时器的访问。主要有：

• 对于窗口场景，SetTimer API提供了一个计时器，通过将WM_TIMER消息发布到调用线程的消息队列来工作。此计时器适用于GUI应用程序，因为计时器消息可以在UI线程上处理。
• Windows多媒体API提供了一个用timeSetEvent创建的多媒体计时器，该计时器在优先级为15的单独线程上调用回调函数。计时器可以是一次性的，也可以是周期性的，并且非常精确（其分辨率可由函数设置），分辨率值为零要求系统能够提供最高分辨率。

相关API：

HANDLE CreateWaitableTimer( LPSECURITY_ATTRIBUTES lpTimerAttributes, BOOL bManualReset, LPCTSTR lpTimerName);
HANDLE CreateWaitableTimerEx( LPSECURITY_ATTRIBUTES lpTimerAttributes, LPCTSTR lpTimerName, DWORD dwFlags, DWORD dwDesiredAccess);

HANDLE OpenWaitableTimer( DWORD dwDesiredAccess, BOOL bInheritHandle, LPCTSTR lpTimerName);

BOOL SetWaitableTimer( HANDLE hTimer, const LARGE_INTEGER* lpDueTime, LONG lPeriod, PTIMERAPCROUTINE pfnCompletionRoutine, LPVOID lpArgToCompletionRoutine, BOOL fResume);
BOOL SetWaitableTimerEx( HANDLE hTimer, const LARGE_INTEGER* lpDueTime, LONG lPeriod, PTIMERAPCROUTINE pfnCompletionRoutine, LPVOID lpArgToCompletionRoutine, PREASON_CONTEXT WakeContext, ULONG TolerableDelay);

18.6.3.6 消息传递

消息传递允许进程进行通信并同步其操作，而无需共享相同的地址空间。在分布式环境中特别有用，其中通信进程可能位于通过网络连接的不同计算机上。消息传递设施至少提供两种操作：发送（信息）和接收（消息）。如果P和Q希望通信，他们需要在他们之间建立通信链路，通过发送/接收交换消息。实现通信链路物理（如共享内存、硬件总线）逻辑（如逻辑属性）。

如果是直接通信，进程必须明确命名：

• 发送（P，消息）：向进程P发送消息。
• 接收（Q，消息）：从进程Q接收消息。

通信链路的属性，自动建立链接，链接只与一对通信进程相关联，每对之间只有一条链路，链接可能是单向的，但通常是双向的。

如果是间接通信，邮件从邮箱（也称为端口）定向和接收，每个邮箱都有唯一的id，进程只有在共享邮箱时才能通信。通信链路的属性，仅当进程共享公共邮箱时才建立链接，链接可能与许多进程关联。每对进程可以共享多个通信链路，链接可以是单向的或双向的。

对应消息的同步，消息传递可以是阻塞的或非阻塞的，阻塞被认为是同步的，阻止发送会阻止发件人，直到收到消息。阻止接收会阻止接收器，直到消息可用，非阻塞被认为是异步的，非阻塞发送让发送方发送消息并继续，非阻塞接收使接收器接收到有效消息或空。

连接到链接的消息队列以三种方式之一实现：

• 零容量：0条消息发送方必须等待接收方（集合）。
• 有限容量：n条消息的有限长度如果链接已满，发送方必须等待。
• 无限容量：无限长度发送程序从不等待。

18.6.3.7 队列

尽管信号量为抢占式多任务提供了最强大的数据结构，但它们只是偶尔显式使用。更常见的是，它们被另一种称为队列的数据结构隐藏。队列也称为FIFO（先进先出），是至少提供两个函数的缓冲区：Put()和Get()。存储在队列中的项目的大小可能会有所不同，因此queue最好作为模板类实现。项目的数量也可能不同，因此类的构造函数将使用所需的长度作为参数。

队列的最简单形式是环形缓冲区（Ring Buffer）。内存的连续部分（称为Buffer）被分配，两个变量GetIndex和PutIndex被初始化为0，从而指向内存空间的开始。对GetIndex和PutIndex执行的唯一操作是递增它们。如果它们碰巧超过了内存的末尾，它们将被重置为开始。这种在结尾处的缠绕将笔直的记忆变成了一个环。当且仅当GetIndex=PutIndex时，缓冲区为空。

否则，PutIndex总是领先于GetIndex（尽管如果PutIndex末尾已经环绕，而GetIndex尚未环绕，则PutIndexe可能小于GetIndex）。在下图中，环形缓冲区显示为直存储器和逻辑环。

可以使用环形缓冲区来放入或获取信号量，以实现无锁同步。

18.6.3 同步问题

18.6.3.1 死锁

死锁的定义：在多道程序设计环境中，几个进程可能会竞争有限数量的资源。进程请求资源时如果资源不可用，进程将进入等待状态。有时，等待进程再也无法更改状态，因为它请求的资源由其他等待进程持有。这种情况称为死锁（Deadlock）。

死锁场景示意图。

系统可能由有限数量的资源组成，并分布在多个进程中，这些资源被划分为多个实例，每个实例都具有相同的实例。进程必须在使用资源之前请求资源，并且必须在使用后释放资源，可以请求任意数量的资源来执行指定的任务，请求的资源量不得超过可用资源的总数。进程只能按以下顺序使用资源：

• 请求：如果没有立即批准请求，则请求进程必须等待，才能获取资源。
• 使用：进程可以对资源进行操作。
• 释放：进程在使用资源后释放资源。

死锁可能涉及不同类型的资源。示例：考虑一个有一台打印机和一个磁带驱动器的系统。如果进程Pi当前持有打印机，进程Pj持有磁带驱动器。如果进程Pi请求磁带驱动器，而进程Pj请求打印机，则会发生死锁。多线程程序很可能会出现死锁，因为它们会争夺共享资源。

死锁的具体示例。

处理死锁的方法有：

• 使用协议来防止死锁，确保系统永远不会进入死锁状态。
• 允许系统进入死锁状态，检测并从中恢复。
• 忽略这个问题，并假装死锁从未在系统中发生过。包括UNIX在内的大多数操作系统都使用此选项。

为了确保死锁永远不会发生，系统可以使用死锁避免或死锁预防。死锁预防是一套确保至少一种必要条件不会发生的方法。死锁避免要求操作系统提前获得有关进程在其生存期内将请求和使用哪些资源的信息。如果系统不使用死锁避免或死锁预防，则可能会出现死锁情况。在此期间，它可以提供一个算法来检查系统状态，以确定是否发生了死锁，以及从死锁中恢复的算法。未检测到的死锁将导致系统性能下降。

没有死锁的具体示例。

要发生死锁，必须满足以下所有4个必要条件。只要有一个条件不成立，那么我们就可以防止死锁的发生。

• 互斥。适用于不可共享的资源，如一台打印机一次只能由一个进程使用。可共享资源中不可能存在互斥，因此它们不会陷入死锁。只读文件是共享资源的好例子，进程从不等待访问可共享资源。因此，我们不能通过否认不可共享资源中的互斥条件来防止死锁。
• 保留并等待。当进程请求资源（即不可用）时，可以通过强制进程释放其持有的所有资源来消除这种情况。可以使用的一种协议是，每个进程在开始执行之前都会分配其所有资源。例如：考虑一个将数据从磁带机复制到磁盘，对文件进行排序，然后将结果打印到打印机的过程。如果在开始时分配了所有资源，则会将磁带驱动器、磁盘文件和打印机分配给进程。主要问题是它导致资源利用率低，因为最终需要打印机，并且从一开始就分配给它，这样其他进程就无法使用它。

另一个可使用的协议是，当进程没有资源时，允许进程请求资源。例如，进程分配有磁带驱动器和磁盘文件，它执行所需的操作并释放两者，然后，该过程再次请求磁盘文件和打印机，但是可能导致饥饿问题。

• 非抢占式。为了确保这种情况永远不会发生，必须抢占资源。可以使用以下协议：如果一个进程持有某些资源并请求另一个无法立即分配给它的资源，那么请求进程当前持有的所有资源都会被抢占，并添加到其他进程可能正在等待的资源列表中。只有当进程重新获得其请求的旧资源和新资源时，才会重新启动该进程。

当流程请求资源时，我们检查它们是否可用。如果它们可用，我们就分配它们，否则我们会检查它们是否分配给其他等待进程。如果是这样，我们会抢占等待进程中的资源，并将其分配给请求进程。请求进程必须等待。

• 循环等待。死锁的第四个也是最后一个条件是循环等待条件，确保永远不会出现这种情况的一种方法是对所有资源类型强制排序，并且每个进程以递增的顺序请求资源。

避免死锁（仅概念）：死锁预防算法可能导致设备利用率低，并降低系统吞吐量。避免死锁需要关于如何请求资源的附加信息。了解请求和发布的完整序列后，我们可以决定每个请求的进程是否应该等待。对于每个请求，它都需要检查当前可用的资源，当前分配给每个进程的资源将处理每个进程的未来请求和释放，以决定是否可以满足当前请求，或者必须等待以避免将来可能出现的死锁。死锁避免算法动态检查资源分配状态，以确保循环等待条件永远不存在。资源分配状态由可用资源和已分配资源的数量以及每个进程的最大需求定义。

安全状态：状态是一种安全状态，其中至少存在一个顺序，所有进程都将完全运行，而不会导致死锁。如果存在安全序列，则系统处于安全状态。如果对于每个Pi，Pi可以请求的资源可以由当前可用的资源满足，则进程序列是当前分配状态的安全序列。如果Pi请求的资源当前不可用，则Pi可以获得完成其指定任务所需的所有资源。

安全状态不是死锁状态。每当进程请求资源（即当前可用的资源）时，系统必须决定是否可以立即分配资源，或者进程是否必须等待。只有当分配使系统处于安全状态时，才会批准请求。在这种情况下，如果进程请求资源，即当前可用的资源，则必须等待。因此，资源利用率可能低于没有死锁避免算法的情况。

资源分配图算法：只有当我们有一个资源类型的实例时，才使用此算法。除了请求边缘和赋值边缘外，还使用了一个称为索赔边缘的新边缘。例如，结合下图，其中索赔边缘由虚线表示，索赔边缘Pi->Rj表示流程Pi将来可能会请求Rj。当进程Pi请求资源Rj时，声明边缘将转换为请求边缘。当资源Rj由进程Pi释放时，分配边Rj->Pi被声明边Pi->Rj替换。

当进程Pi请求Rj时，仅当将请求边缘Pi->Rj转换为分配边缘Rj->Pi不会导致循环时，才会批准请求。循环检测算法用于检测循环。如果没有周期，那么要处理的资源分配将使系统处于安全状态。

银行家算法适用于具有每个资源类型的多个实例的系统，但其效率低于资源分配图算法。当一个新进程进入系统时，它必须声明它可能需要的最大资源数，此数字不能超过系统中的资源总数。系统必须确定资源分配是否会使系统处于安全状态，如果是这样的话，那么应该等待进程释放足够的资源。使用了几种数据结构来实现银行家算法。设“n”为系统中的进程数，“m”为资源类型数。我们需要以下数据结构：

• 可用：长度为m的矢量表示可用资源的数量。如果Available[i]=k，则资源类型Rj的k个实例可用。
• 最大：nxm矩阵定义了每个进程的最大需求，如果Max[i, j]=k，则Pi最多可以请求k个资源类型Rj的实例。
• 分配：一个nxm矩阵定义了当前分配给每个进程的每种类型的资源数量。如果Allocation[i, j]=k，那么Pi当前是资源类型Rj的k个实例。
• 需求：nxm矩阵表示每个流程的剩余资源需求。如果Need[i, j]=k，那么Pi可能还需要k个资源类型Rj的实例来计算其任务。因此需要[i, j]=最大[i, j]-分配[i]

安全算法用于确定系统是否处于安全状态，伪代码：

// Step 1: 设Work和Finish分别为长度m和n的向量，初始化
Work = Available
For i = 1,2, …, n,
if Allocationi 0, then
    Finish[i] = false;
otherwise, 
    Finish[i] = true

// Step 2: 查找索引i，以便
Finish[i] == false
Requesti <= Work
If no such i exists then
    go to step 4

// Step 3:
Work = Work + Allocation
Finish [i] = true
Go to step 2

//Step 4:
If Finish [i] = false
for some i, 1<=i<= n, then 
    the system is in a deadlock state
    Moreover
    if Finish[i] = false then 
        process Pi is deadlocked

安全状态的计算过程。

非安全状态的计算。

资源分配算法：请求=流程Pi的请求向量，如果Requesti[j]=k，则进程Pi需要k个资源类型Rj的实例。

步骤1：若Requesti<=Needi，则转到步骤2。否则，引发错误条件，因为进程已超过其最大声明。

步骤2：如果Requesti<=可用，转至步骤3。否则，由于资源不可用，Pi必须等待。

步骤3：通过如下修改状态，假装将请求的资源分配给Pi：

• Available = Available – Request;
• Allocationi = Allocationi + Requesti;
• Needi = Needi – Requesti;

如果安全的话，资源分配给Pi；如果不安全，Pi必须等待，并恢复旧的资源分配状态。

死锁的检测示例。

从死锁中恢复：中止所有死锁进程，一次中止一个进程，直到消除死锁循环。我们应该选择什么顺序中止？答案是：

• 进程的优先级。
• 进程计算的时间以及完成的时间。
• 进程使用的资源。
• 资源进程需要完成。
• 需要终止多少个进程？
• 进程是交互式的还是批处理的？

资源抢占：选择受害者——将成本降至最低；回滚——返回到某个安全状态，重新启动该状态的进程；饥饿——同一进程可能总是被选为受害者，包括成本因素中的回滚次数。

处理临界区似乎很简单。然而，即使我们使用各种RAII封装器，仍然存在死锁的危险。当拥有锁1的线程A（例如临界区）等待线程B拥有的锁2，而线程B正在等待锁1时，就会发生典型的死锁。

避免死锁的方法另一种简单的方法：总是以相同的顺序获取锁，意味着每个需要多个锁的线程应该总是以相同的顺序获取锁，保证了死锁不会发生（至少不会因为这些锁）。实际问题是如何强制顺序，无需编写任何代码，只需记录顺序，以便将来的代码继续遵守规则。另一种选择是编写一个多锁封装器（multi-lock wrapper），该封装器总是以相同的顺序获取锁，一种简单的实现方法是通过锁在内存中的地址来命令获取。

18.6.3.2 生产者-消费者问题

生产者进程生成消费者进程使用的信息，例如，编译器可以生成汇编程序使用的汇编代码。反过来，汇编程序可能会生成加载程序使用的目标模块。生产者-消费者问题也为客户机-服务器模式提供了一个有用的隐喻。

生产者-消费者问题的一个解决方案是使用共享内存，为了允许生产者和消费者进程同时运行，我们必须有一个项目缓冲区，可以由生产者填充，也可以由消费者清空。该缓冲区将驻留在由生产者和消费者进程共享的内存区域中。生产者可以生产一种商品，而消费者可以消费另一种商品。

生产者和消费者必须同步，以便消费者不会尝试消费尚未生产的数据项。可以使用两种类型的缓冲器：无限缓冲区、有限缓冲区。无限缓冲区对缓冲区的大小没有实际限制，消费者可能不得不等待新产品，但生产者总是可以生产新产品。有限缓冲区假定缓冲区大小固定，在这种情况下，如果缓冲区为空，消费者必须等待。如果缓冲区已满，生产者必须等待。

让我们更仔细地看一下有限缓冲区如何使用共享内存演示进程间通信，以下变量位于生产者和消费者进程共享的内存区域中：

#define BUFFER SIZE 10
typedef struct 
{
. . .
} item;

item buffer[BUFFER SIZE];
int in = 0;
int out = 0;

共享缓冲区实现为具有两个逻辑指针的循环数组：in和out，变量in指向缓冲区中的下一个空闲位置，变量out指向缓冲区中的第一个完整位置。

• 当in==out时，缓冲区为空；
• 当((in + 1) % BUFFER SIZE) == out时，缓冲区已满。

生产者进程具有下一个生成的局部变量，其中存储了要生产的新项目。消费者进程有一个局部变量，该变量下一次被使用，存储了要使用的项。

// 使用共享内存的生产者进程。
item next produced;
while (true) 
{
    /* produce an item in next produced */
    while (((in + 1) % BUFFER SIZE) == out)
    ; /* do nothing */
    buffer[in] = next produced;
    in = (in + 1) % BUFFER SIZE;
}

// 使用共享内存的消费者进程.
item next consumed;
while (true) 
{
    while (in == out)
    ; /* do nothing */
    next consumed = buffer[out];
    out = (out + 1) % BUFFER SIZE;
    /* consume the item in next consumed */
}

编写C程序以实现生产者和消费者问题（信号量）：

• 初始化信号量互斥体、full和empty。
• 对于生产者进程：
• 在临时变量中生成项。
• 如果缓冲区中有空空间，请检查互斥量值以进入临界区。
• 如果互斥量值为0，则允许生产者将临时变量中的值添加到缓冲区。
• 对于消费者进程：
• 如果缓冲区为空，则应等待。
• 如果在互斥量值的缓冲区检查中有任何项，如果互斥量==0，则从缓冲区中删除数据项。
• 发出互斥值信号，并将空值减少1。
• 消费数据项。
• 输出结果。

对应的示例代码：

#include<stdio.h>

int mutex=1, full=0, empty=3, x=0; 
int n;

void producer();
void consumer();
int wait(int);
int signal(int);

void main()
{
    printf("\n 1.producer\n2.consumer\n3.exit\n"); 

    while(1)
    {
        printf(" \nenter ur choice");
        scanf("%d",&n);
        switch(n)
        {
        case 1: 
            if((mutex==1)&&(empty!=0))
                producer();
            else
                printf("buffer is full\n");
            break;
        case 2: 
            if((mutex==1)&&(full!=0))
                consumer();
            else
                printf("buffer is empty");
            break;
        case 3: 
            exit(0);
            break;
        }
    }
}

int wait(int s)
{
    return(--s);
}

int signal(int s)
{
    return (++s);
}

void producer()
{
    mutex = wait(mutex);
    full = signal(full);
    empty = wait(empty);
    x++;
    printf("\n producer produces the items %d", x); 
    mutex = signal(mutex);
}

void consumer()
{
    mutex = wait(mutex);
    full = wait(full);
    empty = signal(empty);
    printf("\n consumer consumes the item %d", x);
    x--;
    mutex = signal(mutex);
}

18.6.3.3 经典IPC问题

经典IPC问题几乎用于测试每个新提出的同步方案。在解决这些问题的方法中，我们使用信号量进行同步，因为是呈现此类解决方案的传统方式。然而，这些解决方案的实际实现可以使用互斥锁代替二进制信号量。

有界缓冲区问题
它通常用于说明同步原语的威力。在我们的问题中，生产者和消费者流程共享以下数据结构：

• int n;
• semaphore mutex = 1;
• semaphore empty = n;
• semaphore full = 0

假设池由n个缓冲区组成，每个缓冲区可以容纳一个项目。互斥信号量为访问缓冲池提供互斥，并初始化为值1。空信号量和满信号量统计空缓冲区和满缓冲区的数量。信号量empty被初始化为值n，信号量full被初始化为值0。

// 生产者进程的结构
do 
{
    (...)
    /* produce an item in next produced */
    (...)
    wait(empty);
    wait(mutex);
    (...)
    /* add next produced to the buffer */
    (...)
    signal(mutex);
    signal(full);
} while (true);

// 消费者进程的结果
do {
    wait(full);
    wait(mutex);
    (...)
    /* remove an item from buffer to next consumed */
    (...)
    signal(mutex);
    signal(empty);
    (...)
    /* consume the item in next consumed */
    (...)
} while (true);

读取者-写入者问题

假设一个数据库将在多个并发进程之间共享。其中一些进程可能只想读取数据库，而其他进程可能想更新（即读写）数据库。如果两个阅读器同时访问共享数据，则不会产生不利影响。如果写入程序和其他进程（读卡器或写入程序）同时访问数据库，则可能会出现问题，没有读取者应该仅仅因为写入者在等待而等待其他读取者完成。

一旦写入者准备就绪，该写入者将尽快执行其写入。任何一个问题的解决方案都可能导致饥饿。在第一种情况下，写入者可能会挨饿；在第二种情况下，读取者可能会挨饿。在解决第一个写入者问题时，写入者进程共享以下数据结构：

• semaphore rw mutex = 1;
• semaphore mutex = 1;
• int read count = 0;

信号量rw_mutex对于读写器进程都是通用的，互斥信号量用于确保更新变量读取计数时互斥，read_count变量跟踪当前有多少进程正在读取对象，信号量rw_mutex用作编写器的互斥信号量。

// 写入者进程代码
do 
{
    wait(rw mutex);
    (...)
    /* writing is performed */
    (...)
    signal(rw mutex);
} while (true);

// 读取者进程代码
do 
{
    wait(mutex);
    read count++;
    if (read count == 1)
        wait(rw mutex);
    signal(mutex);
    (...)
    /* reading is performed */
    (...)
    wait(mutex);
    read count--;
    if (read count == 0)
        signal(rw mutex);
    signal(mutex);
} while (true);

如果一个写入者在临界区，n个读取者在等待，则rw_mutex上会有一个读取者排队，n−1个读取者在互斥体上排队。当一个写入者执行signal(rw_mutex)时，我们可以继续执行等待的读取者或单个等待的写入者，由调度程序进行选择。

用餐哲学家问题

用餐哲学家（dining-philosophers）问题被认为是一个经典的同步问题。

想想五位哲学家，他们一生都在思考和吃饭。哲学家们共享一张圆桌，周围有五把椅子，每把椅子都属于一位哲学家，桌子中央是一碗饭，桌子上放着五根筷子。

当哲学家思考时，他不会与同事互动。有时，一位哲学家饿了，试图拿起离他最近的两根筷子（她和左右邻居之间的筷子）。 哲学家一次只能拿起一根筷子，且无法拿起邻居手中的筷子。当一个饥饿的哲学家同时拥有两只筷子时，他吃饭时不会松开筷子。 当吃完饭，他放下两只筷子，开始重新思考。

哲学家试图通过对信号量执行wait()操作来抓住筷子，通过对适当的信号量执行signal()操作来释放筷子。因此，共享数据是筷子的所有元素初始化为1的地方。

semaphore chopstick[5];
do 
{
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
    (...)
    /* eat for awhile */
    (...)
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    (...)
    /* think for awhile */
    (...)
} while (true);

虽然上述这种解决方案可以保证没有两个邻居同时吃饭，但必须予以拒绝，因为可能会造成死锁。假设五位哲学家同时都饿了，每个人都抓着左边的筷子。此时，筷子的所有元素现在都等于0。当每个哲学家都试图抓住右边的筷子时，他将永远被耽搁。以下是解决死锁问题的几种可能方法：

• 最多允许四位哲学家同时坐在桌子旁。
• 只有当两支筷子都可用时，才允许哲学家拿起筷子（为此，他必须在临界区拿起筷子）。
• 使用非对称解决方案，即奇数哲学家先拿起他的左筷子，然后拿起右筷子，而偶数哲学家则拿起他的右筷子，然后拿起左筷子。

18.6.4 同步总结

除了以上所述的同步方式，Windows还提供了其它诸多方式，完整列表：

Asynchronous functions
Condition variable and SRW lock functions
Critical section functions
Event functions
One-time initialization functions
Interlocked Functions
Mutex functions
Private namespace functions
Semaphore functions
Singly-linked list functions
Synchronization barrier functions
Timer-queue timer functions
Wait functions
Waitable-timer functions

此外，C++标准库也提供了同步原语，可以用作Windows API的替代品，特别是对于跨平台代码。通常，这些对象的自定义非常有限，例如：

• std::mutex：它像一个关键部分，不支持递归获取。
• std::recursive_mutex：其作用就像一个关键部分（支持递归获取）。
• std::shared_mutex：类似于SRW锁。
• std::condition_variable：等效于条件变量。
• 其他。

显然，C++中可能缺少一些东西，例如等待地址和同步屏障，但它们可以在未来添加到标准中。在任何情况下，所有C++标准库类型仅在同一进程中工作，无法跨进程使用它们。关于C++的更多同步技术，可以参阅2.1.3.3 C++多线程同步 。

18.7 线程高级主题

18.7.1 线程局部存储

线程可以访问其堆栈数据，并处理广泛的全局变量。然而，有时在线程基础上拥有一些存储是很方便的，可以以统一的方式访问。一个经典的例子是我们熟悉的GetLastError函数，尽管任何线程都可以调用GetLastError，但访问的每个线程的结果都不同。处理这种情况的一种方法是存储由线程ID键控的哈希表，然后根据该键查找值。虽然可行，但它有一些缺点：第一，哈希表需要同步，因为多个线程可能同时访问它；第二，搜索正确的线程可能没有预期的那么快。

线程本地存储（Thread Local Storage，TLS）是一种用户模式机制，允许在多线程的基础上存储数据，进程中的每个线程都可以访问，但只能访问自己的数据。但是访问方法是统一的。

TLS使用的另一个经典示例是C/C++标准库。早在20世纪70年代初，C标准库就被构想出来了，当时还没有多线程的概念。因此，C运行时维护一组全局变量作为某些操作的状态。例如，以下经典C代码尝试打开文件并处理可能的错误：

FILE* fp = fopen("somefile.txt", "r");
if(fp == NULL) 
{
    // something went wrong
    switch(errno) 
    {
        case ENOENT: // no such file
        break;
        case EFBIG:
        break;
    }
}

任何I/O错误都反映在全局errno变量中。但在多线程应用程序中，是一个问题。假设线程1进行I/O函数调用，导致errno更改。在检查其值之前，线程2也进行I/O调用，再次更改errno，导致线程1检查了由于线程2活动而产生的值。

解决方案是errno不能是全局变量。如今的errno不是一个变量，而是一个宏，它调用一个函数errno()，该函数使用线程本地存储来检索当前线程的值。类似地，I/O函数的实现（如fopen）使用TLS将错误结果存储到当前线程。

18.7.1.1 动态TLS

Windows API为TLS使用提供以下接口：

DWORD  TlsAlloc();
BOOL   TlsFree(DWORD dwTlsIndex);

BOOL   TlsSetValue(DWORD dwTlsIndex, PVOID pTlsValue);
PVOID  TlsGetValue(DWORD dwTlsIndex);

TlsAlloc函数返回一个可用的槽索引，并将所有现有线程的所有对应单元格归零。TLS对于DLL非常有用，因为DLL可能希望在每个线程的基础上存储一些信息，因此在加载时会分配大量信息，并在需要时使用。

TLS中的每个单元格都是指针大小的值，因此这里的最佳实践是使用单个插槽，并动态分配所需的任何结构，以保存TLS中需要存储的所有信息，并仅将指向数据的指针存储在插槽本身中。索引可用后，将使用TlsSetValue、TlsGetValue来存储或从槽中检索值。

调用这些函数的线程只能访问特定槽索引中自己的值，没有直接访问另一个线程的TLS插槽的方法——因为会破坏TLS的本意。也意味着访问TLS时不需要同步，因为只有一个线程可以访问内存中的相同地址。TLS数组如下图所示。

18.7.1.2 静态TLS

线程本地存储也以更简单的形式提供，在全局或静态变量上使用Microsoft扩展关键字，或使用C++11或更高版本的编译器。Windows有两种定义方式，如下所示：

// 方式1：Microsoft特定说明符
__declspec(thread) int counter;

// 方式2：C++标准定义
thread_local int counter;

此TLS是“静态”的——不需要任何分配，并且不能被销毁。在内部，编译器将所有线程局部变量捆绑到一个块（chunk）中，并将信息存储在PE中名为.tls的部分中。进程启动时读取此信息的加载器（NTDLL）调用TlsAlloc来分配一个插槽，并为启动包含所有线程局部变量的内存块的每个线程动态分配。在调用传递给CreateThread的“实”函数之前，每个用户模式线程都在NTDLLProved函数中启动。

18.7.2 远程线程

Windows下可以使用CreateThread函数在当前进程中创建一个线程。然而，在某些情况下，一个进程可能希望在另一个进程中创建线程。典型示例是调试器，当需要强制断点时，例如当用户按下“中断”按钮时，调试器会在目标进程中创建一个线程，并将其指向DebugBreak函数（或发出中断指令的CPU内部函数），从而导致进程中断，并通知调试器。以下API可以创建远程线程：

HANDLE WINAPI CreateRemoteThread(HANDLE hProcess, ...);
HANDLE CreateRemoteThreadEx(HANDLE hProcess, ...);

使用线程来实现远程过程调用（RPC）的示意图如下：

18.7.3 缓存和缓存行

在微处理器的早期，CPU的速度和内存（RAM）的速度是相当的。然后CPU速度上升，内存速度滞后，导致CPU大量停顿（stall），等待内存读取或写入值。为了补偿，CPU和内存之间引入了缓存，如下图所示。

缓存和内存结构图例。

与主内存相比，高速缓存是一种快速内存，允许CPU减少停顿。高速缓存虽然没有主内存那么大，但它的存在在今天的系统中是必不可少的，其重要性不言而喻。举个具体的例子。下面是两种不同的计算矩阵之和的方式：

long long SumMatrix1(const Matrix<int>& m) 
{
    long long sum = 0;
    // 行优先（Row major）
    for (int r = 0; r < m.Rows(); ++r)
        for (int c = 0; c < m.Columns(); ++c)
            sum += m[r][c];

    return sum;
}

long long SumMatrix2(const Matrix<int>& m) 
{
    long long sum = 0;
    // 列优先（Col Major）
    for (int c = 0; c < m.Columns(); ++c)
        for (int r = 0; r < m.Rows(); ++r)
            sum += m[r][c];

    return sum;
}

Matrix<>类是一维数组的简单包装器。从算法角度来看，两个函数中矩阵元素求和所需的时间应该相同。毕竟，代码一次遍历所有矩阵元素。但实际结果可能令人惊讶。下面是运行一个不同矩阵大小和元素求和所需的时间（都是单线程）：

差异相当大，因为有缓存的存在。当CPU读取数据时，它不会读取单个整数或任何被指示读取的数据，而是读取整个缓存行（通常为64字节），并将其放入内部缓存。然后，当读取内存中的下一个整数时，不需要内存访问，因为该整数已经存在于缓存中。这是最佳的，并且是SumMatrix1的工作方式——它线性遍历内存。另一方面，SumMatrix2读取一个整数（以及缓存行的其余部分），而下一个整数位于更远的另一个缓存行（对于除最小矩阵之外的所有矩阵），需要读取另一缓存行，可能会丢弃可能很快需要的数据，使情况变得更糟。

从技术上讲，在大多数CPU中实现了3个缓存级别。缓存离处理器越近，速度越快，但容量越小。下图显示了4核CPU（采用超线程技术）的典型缓存配置。

1级缓存由数据缓存（D-cache）和指令缓存（I-cache）组成，每个逻辑处理器有一个。然后是2级缓存，由属于同一核心的逻辑处理器共享。最后，3级缓存是全系统的。这些缓存的大小相当小，大约比主内存小3个数量级。系统上的缓存大小在任务管理器的性能/CPU选项卡中很容易看到，如下图所示。

在上图中，3级缓存大小为16 MB（系统范围），2级缓存大小为4MB，但包括所有内核。由于该系统有8个内核，每个2级缓存实际上是4MB/8=512KB。类似地，1级缓存大小为640KB，分布在16个逻辑处理器上，使每个缓存640KB/16=40KB。与主内存大小（以千兆字节为单位）相比，缓存大小较小。

缓存、主内存结构。

缓存读取操作过程。

让我们看另一个例子，其中缓存和缓存行起着重要（甚至至关重要）的作用。下面的示例演示了如何遍历一个大数组，计算数组中的偶数，它是通过多个线程完成的——每个线程都被分配了数组的一个连续部分。计数本身被放置在另一个数组中，每个单元格由相应的线程修改。下图显示了具有4个线程的这种布置。

下面是计算偶数的第一个版本：

using namespace std;
struct ThreadData 
{
    long long start, end;
    const int* data;
    long long* counters;
};

long long CountEvenNumbers1(const int* data, long long size, int nthreads) 
{
    auto counters_buffer = make_unique<long long[]>(nthreads);
    auto counters = counters_buffer.get();
    auto tdata = make_unique<ThreadData[]>(nthreads);

    long long chunk = size / nthreads;
    vector<wil::unique_handle> threads;
    vector<HANDLE> handles;

    for (int i = 0; i < nthreads; i++) 
    {
        long long start = i * chunk;
        long long end = i == nthreads - 1 ? size : ((long long)i + 1) * chunk;
        auto& d = tdata[i];
        d.start = start;
        d.end = end;
        d.counters = counters + i;
        d.data = data;

        wil::unique_handle hThread(::CreateThread(nullptr, 0, [](auto param) -> DWORD 
        {
            auto d = (ThreadData*)param;
            auto start = d->start, end = d->end;
            auto counters = d->counters;
            auto data = d->data;

            for (; start < end; ++start)
                if (data[start] % 2 == 0)
                    ++(*counters);
            return 0;
        }, tdata.get() + i, 0, nullptr));

        handles.push_back(hThread.get());
        threads.push_back(move(hThread));
    }

    ::WaitForMultipleObjects(nthreads, handles.data(), TRUE, INFINITE);

    long long sum = 0;
    for (int i = 0; i < nthreads; i++)
        sum += counters[i];

    return sum;
}

启动为每个线程准备数据的循环，并调用CreateThread启动线程循环，看看线程的循环：

for (; start < end; ++start)
    if (data[start] % 2 == 0)
        ++(*counters);

对于每个偶数，计数器指针的内容递增1。注意，这里没有数据竞争——每个线程都有自己的单元，因此最终结果应该是正确的。这段代码的问题在于，当某个线程写入单个计数时，会写入一个完整的缓存行，使其他处理器上查看该内存的任何缓存失效，迫使它们通过再次从主内存读取来刷新缓存——导致性能很慢。这种情况被称为伪共享（false sharing）。

另一种方法是不写与其他线程共享缓存线的单元，至少不是经常写：

// 将统计的中间数据放在局部变量count
size_t count = 0;
for (; start < end; ++start)
    if (data[start] % 2 == 0)
        count++;
*(d->counters) = count;

主要的区别是将计数保持在局部变量count中，并且仅在循环完成时向结果数组中的单元格写入一次。由于count位于线程的堆栈上，并且堆栈大小至少为4KB，因此它们不可能与其他线程中的其他count变量位于同一缓存行上，大大提高了性能。当然，通常使用局部变量可能比间接访问内存快，因为编译器更容易将该变量缓存在寄存器中。但真正的影响是避免线程之间共享缓存行。主函数使用不同数量的线程测试这两种实现，如下所示：

Initializing data...

Option 1
1 threads count: 2147483647 time: 4843 msec
2 threads count: 2147483647 time: 3391 msec
3 threads count: 2147483647 time: 2468 msec
4 threads count: 2147483647 time: 2125 msec
5 threads count: 2147483647 time: 2453 msec // 线程多了反而降低性能！！
6 threads count: 2147483647 time: 1906 msec
7 threads count: 2147483647 time: 2109 msec // 线程多了反而降低性能！！
8 threads count: 2147483647 time: 2532 msec // 线程多了反而降低性能！！

Option 2
1 threads count: 2147483647 time: 4046 msec
2 threads count: 2147483647 time: 2313 msec
3 threads count: 2147483647 time: 1625 msec
4 threads count: 2147483647 time: 1328 msec
5 threads count: 2147483647 time: 1062 msec
6 threads count: 2147483647 time: 953 msec
7 threads count: 2147483647 time: 859 msec
8 threads count: 2147483647 time: 855 msec

请注意，在选项1中，在某些情况下，更多线程会降低性能。在选项2中，随着线程数量的增加而持续改进性能。

• 缓存性能

主内存缓存机制是计算机架构的一部分，在硬件中实现，通常对操作系统不可见。然而，还有两个两级内存方法的实例，它们也利用了局部性的特性，并且至少部分地在操作系统中实现：虚拟内存和磁盘缓存（下表）。我们将研究所有三种方法中常见的两级内存的一些性能特征。

下表测量了若干研究者在执行不同语言过程中各种语句类型的外观。

关于断言，PATT85中报告的研究提供了证实（下图），它显示了调用返回行为。每一个调用都由向下和向右移动的行表示，每一个返回都由向上和向右移动行表示。在图中，定义了一个深度等于5的窗口。只有一系列调用和返回，在任意方向上净移动6，才会导致窗口移动。如图所示，正在执行的程序可以长时间保持在一个固定窗口内。

程序的调用返回行为样例。

命中率作为相对内存大小的函数。

两个内存的相对大小是否满足成本要求？答案显然是肯定的。如果我们只需要一个相对较小的上层内存来实现良好的性能，那么这两层内存的平均每比特成本将接近较便宜的下层内存。

18.7.4 线程池

Windows提供线程池，是一种允许某些线程从线程池发送操作的机制。与手动创建和管理线程相比，使用线程池的优势如下：

• 客户端代码不进行显式线程创建或终止——线程池管理器会处理。
• 已完成的操作不会销毁工作线程——返回给线程池以服务另一个请求。
• 池中的线程数量可以根据工作项负载动态增长和收缩。

Windows 2000提供了第一个版本的线程池，为每个进程提供了一个线程池。从Windows Vista开始，线程池API得到了显著增强，包括添加了专用线程池，意味着一个进程中可以存在多个线程池。相关API：

PTP_WORK CreateThreadpoolWork(PTP_WORK_CALLBACK pfnwk, PVOID pv, PTP_CALLBACK_ENVIRON pcbe);
void CloseThreadpoolWork(PTP_WORK pwk);
VOID CloseThreadpoolWait(PTP_WAIT pwa);

VOID SubmitThreadpoolWork(PTP_WORK Work);
BOOL TrySubmitThreadpoolCallback(PTP_SIMPLE_CALLBACK pfns, PVOID pv, PTP_CALLBACK_ENVIRON pcbe);
void WaitForThreadpoolWorkCallbacks(PTP_WORK pwk, BOOL fCancelPendingCallbacks);
VOID SetThreadpoolWait(PTP_WAIT pwa, HANDLE h, PFILETIME pftTimeout);

18.7.5 用户模式调度

用户模式和内存模式之间的切换存在大量的基础消耗，所以，减少两者之间的切换可以提升性能。

早期的Windows版本提供纤程，但其存在诸多问题（如TLS未正确传递，线程环境块不符），已被废弃。从Windows 7和Windows 2008 R2开始，Windows支持一种称为用户模式调度（UMS）的替代机制，其中用户模式线程成为各种调度程序，可以从用户模式调度线程，而无需进行用户模式/内核模式转换。该机制是内核已知的，因此UMS不存在纤程的缺点，因为使用的是真正的线程，而不是共享线程的纤程。

不幸的是，但是构建一个使用UMS的真实系统并非易事。微软（自2010年起）提供了一个名为并发运行时的库，缩写为Concrt，发音为“concert”，它在需要并发执行时，在后台使用UMS提供线程的高效使用。

18.7.6 仅初始化一次

许多应用程序中的一个常见模式是使用单例对象。在某些观点中，这是一种反模式。事实上，单例是有用的，有时是必要的。单例的一个常见要求是只初始化一次。在多线程应用程序中，多个线程最初可能同时访问单实例，但单实例必须初始化一次。如何实现这一目标？有几种众所周知的算法，如果实施得当，可以完成任务。Windows API提供了一种内置的方法来调用函数，并保证只调用一次：

INIT_ONCE init = INIT_ONCE_STATIC_INIT;
VOID InitOnceInitialize(_Out_ PINIT_ONCE InitOnce);
BOOL InitOnceExecuteOnce(PINIT_ONCE InitOnce, __callback PINIT_ONCE_FN InitFn, PVOID Parameter, LPVOID Context);

18.8 作业

18.8.1 作业概述

如果进程处于作业之下，则作业（Job）对象在Process Explorer中间接可见。在这种情况下，作业选项卡出现在进程的属性中（如果进程处于无作业状态，则该选项卡不存在）。另一种收集作业的方法是在选项/配置颜色中启用作业颜色（默认为棕色）…。下图显示了Process Explorer，其中作业颜色可见，所有其他颜色均已移除。

Windows 8引入了将进程与多个作业关联的功能，使得作业比以前有用得多，因为如果希望通过作业控制的进程已经是作业的一部分，则无法将其与其他作业关联。分配了第二个作业的进程会导致创建作业层次结构（如果可能），第二份作业成为第一份工作的子项。基本规则如下：

父作业施加的限制会影响作业和所有子作业（以及这些作业中的所有进程）。
父作业施加的任何限制不能由子作业删除，但可以更严格。例如，如果父作业将作业范围内的内存限制设置为200MB，则子作业可以将（其进程）限制设置为150MB，但不能设置为250MB。
下图显示了通过调用以下操作（按顺序）创建的作业的层次结构：

1、将进程P1分配给作业J1。

2、将进程P1分配给作业J2，形成层次结构。

3、将进程P2分配给作业J2，进程P2现在受作业J1和J2的影响。

4、将进程P3分配给作业J1。

查看作业层次结构并不容易。例如，Process Explorer显示作业的详细信息，包括显示作业和所有子作业（如果有）的信息。例如，从图上图中查看作业J1的信息，将列出三个进程：P1、P2和P3。此外，由于作业访问是间接的——如果一个进程在作业下，则作业选项卡可用——显示的作业是该进程所属的直接作业，未显示任何父作业。以下代码创建了上图所示的层次结构：

#include <windows.h>
#include <stdio.h>
#include <assert.h>
#include <string>

HANDLE CreateSimpleProcess(PCWSTR name) 
{
    std::wstring sname(name);
    PROCESS_INFORMATION pi;
    STARTUPINFO si = { sizeof(si) };
    if (!::CreateProcess(nullptr, const_cast<PWSTR>(sname.data()), nullptr, nullptr, FALSE, CREATE_BREAKAWAY_FROM_JOB | CREATE_NEW_CONSOLE, nullptr, nullptr, &si, &pi))
    {
        return nullptr;
    }
    ::CloseHandle(pi.hThread);
    return pi.hProcess;
}

HANDLE CreateJobHierarchy() 
{
    auto hJob1 = ::CreateJobObject(nullptr, L"Job1");
    assert(hJob1);
    auto hProcess1 = CreateSimpleProcess(L"mspaint");
    auto success = ::AssignProcessToJobObject(hJob1, hProcess1);
    assert(success);
    auto hJob2 = ::CreateJobObject(nullptr, L"Job2");
    assert(hJob2);
    success = ::AssignProcessToJobObject(hJob2, hProcess1);
    assert(success);
    auto hProcess2 = CreateSimpleProcess(L"mstsc");
    success = ::AssignProcessToJobObject(hJob2, hProcess2);
    assert(success);
    auto hProcess3 = CreateSimpleProcess(L"cmd");
    success = ::AssignProcessToJobObject(hJob1, hProcess3);
    assert(success);
    // not bothering to close process and job 2 handles
    return hJob1;
}

int main()
{
    auto hJob = CreateJobHierarchy();
    printf("Press any key to terminate parent job...\n");
    ::getchar();
    ::TerminateJobObject(hJob, 0);
    return 0;
}

当违反作业限制或发生某些事件时，作业可以通过与作业关联的I/O完成端口通知相关方。I/O完成端口通常用于处理异步I/O操作的完成，但在这种特殊情况下，它们被用作通知某些作业事件发生的机制。

作业是一个调度程序（可等待）对象，当发生CPU时间冲突时发出信号。对于这个简单的情况，线程可以等待WaitForSingleObject（作为一个常见示例），然后处理CPU时间冲突。设置新的CPU时间限制将作业重置为无信号状态。

18.8.2 Silos

Windows 10版本1607和Windows Server 2016引入了称为Silos的作业的增强版本。Silos有两种变体：

• 应用程序Silos。用于使用桌面桥接技术转换为UWP的应用程序，几乎没有服务器Silos那么强大（也不需要）。作业资源管理器有Silos类型列，通过列出作业的类型来指示作业是否实际上是Silos。
• 服务器Silos。仅在Windows Server 2016起的机器上受支持，用于实现Windows容器，即沙盒进程的能力，创建虚拟环境，使进程认为自己在自己的机器上。需要将文件系统、注册表和对象名称空间重定向为特定Silos的一部分，因此内核必须在内部进行重大更改才能感知思洛存储器。

总之，作业提供了许多控制和限制进程的机会，都由内核本身实现。Windows 8中嵌套作业的引入使作业更有用，限制更少。

作者：向往
文章来源：https://zhuanlan.zhihu.com/p/579031521