[CSAPP笔记][第十二章并发编程]

第十二章 并发编程

如果逻辑控制流在时间上是重叠，那么它们就是并发的(concurrent)。这种常见的现象称为并发(concurrency)。

• 硬件异常处理程序，进程和Unix信号处理程序都是大家熟悉的例子。

我们主要将并发看做是一种操作系统内核用来运行多个应用程序的机制。

• 但是，并发不仅仅局限于内核。它也可以在应用程序中扮演重要的角色。

  • 例如

    • Unix信号处理程序如何允许应用响应异步事件
      • 例如:用户键入ctrl-c
      • 程序访问虚拟存储器的一个未定义的区域

  • 其他情况

    • 访问慢速I/O设备

      • 当一个应用程序正在等待来自慢速I/O设备(例如磁盘)的数据到达时，内核会运行其他进程，使CPU保持繁忙。

    • 与人交互

      • 和计算机交互的人要求计算机有同时执行多个任务的能力。

    • 通过推迟工作以降低延迟

      • 有时，应用程序能够通过推迟其他操作和并发执行它们，利用并发来降低某些操作的延迟

    • 服务多个网络客户端

      • 一个慢速的客户端可能会导致服务器拒绝为所有客户端提供服务。

    • 在多核机器上进行并行运算

使用应用级并发的应用程序称为并发程序(concurrent program).

• 操作系统提供三种基本的构造并发程序的方法:
  • 进程

    • 每个逻辑控制流 都是一个进程

      • 由内核来调度和维护。

    • 因为进程有独立的虚拟地址空间

      • 和其他进程通信，控制流必须使用某种显式的进程间通信(interprocess communication,IPC)进制
  • I/O多路复用(暂时不太懂)
    • 应用程序在一个进程的上下文中显示地调度它们自己的逻辑流。
    • 逻辑流被模型化为状态机，数据到达文件描述符后，主程序显式地从一个状态转换到另一个状态。
    • 因为程序是一个单独的进程，所以所有的流都共享同一个地址空间。
  • 线程
    • 线程是运行在一个单一进程上下文中的逻辑流，有内核调度。
      • 像进程一样由内核进行调度。
      • 而像I/O多路复用一流一样共享一个虚拟地址空间。

12.1 基于进程的的并发编程

一个构造并发服务器的自然方法就是，在父进程中接收客户端连接请求，然后创建一个新的子进程来为每个新客户端提供服务。

• 服务器正在监听一个监听描述符(描述符3)上的连接请求
• 服务器接收客户端1的连接请求
• 并返回一个已连接描述符(描述符4)。

• 子进程获得服务器描述符表的完整拷贝(描述符3,4)
• 子进程关闭它的拷贝中的监听描述符3
• 服务器关闭描述符表中的描述符4

• 之后新的客户端又类似之前两个步骤。

12.1.1 基于进程的并发服务器

• 用Signal(SIGCHLD,sigchld_handler)回收僵死进程。

  • 具体细节见8.5.7

• 28行，33行 父子进程各自关闭他们不需要的拷贝。

• 因为文件表项的引用计数，直到父进程关闭它的描述符，才算结束一次连接

12.1.2 关于进程的优劣

对于在父，子进程间共享状态信息，进程有一个非常清晰的模型。

• 共享文件表，但是不共享用户地址空间。
• 进程拥有独立的虚拟地址空间即是 优点，也是 缺点。

  • 优点:一个进程不可能不小心覆盖另一个进程的虚拟存储空间。

    • 消除许多令人迷惑的错误。

  • 缺点:独立的地址空间使得进程间共享信息也很困难。

    • 必须使用显式的IPC(进程间通信)机制。

    • 往往还比较慢

      • 进程控制和IPC的开销都很大。

12.2 基于I/O多路复用的并发编程(暂时跳过)

假设要编写一个echo服务器。

• 服务器既能响应客户端的请求
• 也能对用户从标准输入输出的交互命令做出反应(如exit).

因此，服务器必须要响应两个相互独立的I/O事件

• 网络客户端发起连接
• 用户在键盘键入命令行。

无论先等待那个事件都不是理想的，解决办法之一是就是使用I/O多路复用技术。

• 基本的思路
  • 使用select函数，要求内核挂起进程，只有一个或多个I/O事件发生后，才将控制返回给应用程序。

12.3 基于线程的并发编程

线程(thread) 就是运行在进程上下文中的逻辑流。

• 线程由内核调度。

• 每个线程都有它自己的线程上下文(thread context).

  • 包括一个唯一的整数线程ID(Thread ID,TID).
  • 栈和栈指针
  • 程序计数器
  • 通用目的寄存器和条件码

• 所有运行在该进程里的线程共享该进程的整个虚拟地址空间。

  • 共享 包括代码，数据，堆，共享库和打开的文件。

12.3.1 线程执行模型

• 每个进程开始生命周期时都是单一线程，这个线程称为主线程(main thread)。

  • 某时刻，主线程创建一个对等线程(peer thread)。
    • 当主线程执行一个慢速系统调用，例如read或sleep
    • 或者被系统的间隔计时器中断。
    • 控制就会通过上下文切换传递到对等线程。
    • 对等线程执行一段时间，将控制传递回主线程。

• 在某些方面，线程执行是不等同于进程的。

  • 线程的上下文切换的开销比进程的小得多，快得多
  • 线程不是按照严格的父子层次来组织。
    • 和一个进程相关的线程组成一个线程池(pool)。
      • 线程池概念的主要影响是
      • 一个线程可以杀死它的任何对等线程，或等待任意对等线程终止。
      • 每个对等线程都能读写相同的共享数据。

12.3.2 Posix 线程

Posix线程 (Pthreads)是在C程序中处理线程的一个标准接口。

• 在大多数Unix系统可用
• 允许程序创建，杀死和回收线程，与对等线程安全共享数据，还可以通知对等线程系统状态的变化。

这是我们第一个线程化的代码，仔细解析。

• 线程的代码和本地数据被封装在一个线程例程(thread routine)中。

  • 如第2行代码所示:每个线程例程都以一个通用指针作为输入，并返回一个通用指针。

  • 如果想传递多个参数给线程例程

    • 你应该将参数放到一个结构中。
    • 并传递一个指向该结构的指针。

  • 如果想要线程例程返回多个参数。

    • 也可以返回一个指向结构的指针。

• tid存放对等线程的线程ID。

• 主线程调用pthread_create函数创建一个新的对等线程(第7行)。

  • 当对pthread_create的调用返回时，主线程和新创建的对等线程同时运行。

• 通过调用pthread_join,主线程等待对等线程的终止。

• 对等线程输出Hello,world。

• 主线程终止。

12.3.3 创建线程

线程通过调用pthread_create函数来创建其他线程。

#include<phread.h>
typedef void *(func)(void *);

int phread_create(pthread_t *tid,pthread_attr_t *attr,fun *f,void *arg)

                    //若成功则返回0,出错则为非0

pthread_create函数创建一个新的线程。

• 带着一个输入变量arg，在新线程的上下文中运行线程例程f.

• 能用attr参数改变新创建线程的默认属性。

  • 改变这些属性超过我们的学习范围。
  • 我们总是用NULL作为attr的参数。

• pthread_create返回时，参数tid包含新创建线程的ID。

  • 通过调用pthread_self函数来获得它自己的线程ID。

12.3.4 终止线程

一个线程是以下列方式之一来终止的

• 当顶层的线程例程返回时，线程会隐式地终止。

• 通过调用pthread_exit函数，线程会显示地终止。

  • 如果主线程调用pthread_exit.

    • 等待所有其他对等线程终止，然后终止主线程和其他整个进程。
    • 返回值为thread_return

  • 原型如下

      #include<pthread.h>
      
      void pthread_exit(void *thread_return)
          //成功返回0，出错返回非0
    

• 某个对等线程调用Unix的exit函数，函数终止进程和所有与该进程有关的线程。

• 对等线程通过以当前线程ID为参数调用pthread_cancle函数来终止当前线程。

  • 原型

      #include<pthread.h>
      
      void pthread_cancle(pthread_t tid);
          //成功返回0，出错返回非0
    

12.3.5 回收已终止的资源

线程通过调用pthread_join函数等待其他进程终止

#include<pthread.h>

int pthread_join(pthread_t tid,void **thread_return);

            //返回，成功则为0，出错为非0

• pthread_join函数会阻塞，知道线程tid终止，将线程返回的(void *)指针赋值给thread_return所指向的位置，然后回收已终止线程占用的存储器资源。

• pthread_join不像wait函数一样等待任意一个线程的结束。

  • 使得用不那么直观的方式，检测一个进程的终止。
  • Stevens在书中指出这是一个设计错误。

12.3.6 分离线程

在任何一个时间点上，线程是可结合的(joinable)或者 是分离的(detached)。

• 一个可结合的线程能够被其他线程收回其资源或者杀死。

  • 在被其他线程回收之前，它的存储器资源是没有被释放的。

• 一个分离的线程是不能被其他线程收回其资源或者杀死。

  • 系统自动释放资源。

pthread_detach函数分离可结合线程tid。

#include<pthread.h>

int pthread_detach(pthread_t tid);

            返回:若成功则返回0，若出错则返回非零。

12.3.7 初始化线程

pthread_once函数允许你初始化与线程例程相关的状态。

#include<pthread.h>

pthread_once_t once_control = PTHREAD_INIT;

int phread_once(phread_once_t *once_control,void (*init_routine)(void));

• once_control变量是一个全局或者静态变量，总是被初始化为PTHREAD_ONCE_INIT.

• 当你第一次用参数once_control调用pthread_once时，它调用init_routine。

  • 这是一个没有输入参数，也不返回什么的函数。

• 第二次，第三次以参数once_control调用pthread_once时，啥事也不发生。

  • 意思时仅仅第一次调用时有效果。

• 当你需要动态初始化多个线程共享的全局变量时，pthread_once函数是很有用的。

12.3.8 一个基于线程的并发服务器

• 注意使用malloc动态给一个connfdp，否则可能两个线程引用同一个connfdp的地址。

  • 这叫做竞争

• 为在线程例程中避免存储器泄露，使用分离线程。

• 还要注意释放在主线程中malloc的变量。

12.4 多线程程序中的共享变量

为了解一个C程序中的一个变量是否共享，有一些基本的问题要解答

• 线程的基础存储器模型是什么?
• 根据这个模型，变量实例是如何映射到存储器的?
• 有多少线程引用这些实例?

为了使共享讨论具体化，使用下图的程序作为示例。

示例程序由一个创建两个对等线程的主线程组成。主线程传递一个唯一的ID给每个对等线程，每个对等线程利用这个ID输出一个个性化的信息，以及调用该线程例程的总次数。

12.4.1 线程存储器模型

12.4.2 将变量映射到存储器

线程化的C程序中的变量根据它们的存储类型被映射到虚拟存储器:

• 全局变量

  • 全局变量是定义在函数之外的变量。
    • 在运行时,虚拟存储器中的读/写区域包含每个全局变量的一个实例。
    • 任何线程都可以引用。
    • 例如，第5行声明的ptr。

• 本地自动变量

  • 本地自动变量就是定义在函数内部但是没有static属性的变量。
    • 在运行时，每个线程的栈包含它自己的所有本地自动变量的实例。

• 本地静态变量

  • 本地静态变量是定义在函数内部有static属性的变量。
    • 和全局变量一样，存储在虚拟存储器的读/写区域。
    • 例如:第25行的cnt.

12.4.3 共享变量

我们说一个变量v是共享的，当期仅当它的一个实例被一个以上的线程引用。

例如:

• cnt 是共享的
• myid 不是共享的
• 认识到msgs这种本地自动变量也能被共享是很重要的。

12.5 用信号量同步线程

共享变量十分方便，但是他们也引入了同步错误(synchronization error)的可能性。

考虑下图的程序。

• 

到底哪里出错了呢?这个错误十分隐晦，必须通过研究计数器循环时的汇编代码才能看出。

当badcnt.c中的两个对等线程在一个单处理器上并发执行，机器指令以某种顺序一个接一个地完成。同一个程序每次运行的顺序都可能不同，这些顺序中有一些将会产生正确结果，但是其他的不会。这就是同步错误

关键点: 一般而言，你没有办法预测操作系统是否将为你的线程选择一个正确的顺序。

• 下图，就是cnt正确的顺序和错误的顺序(正确结果cnt=2，错误结果cnt=1)

我们可以借助于一种叫做进度图(progress graph)的方法来阐明这些正确和不正确的指令顺序的概念。将在接下来介绍。

12.5.1 进度图

进度图(process graph) 将n个并发进程的执行模型化为一条n维笛卡尔空间的轨迹线。

• 每条轴k对应于k的进度。

• 每个点(I1，I2，I3，I4...,In)代表线程k(k=1,...,n)已经完成到了Ik这条指令的状态。

• 图的原点对应于没有任何线程完成这一条指令的初始状态。

---

进度图将指令执行模型化为从一个状态到另一个状态的转换(transition)。

• 转换指从一点到相邻一点的有向边。
  • 合法的转换是向各个轴的正半轴走。

---

临界区

对于线程i，操作共享变量cnt内容的指令(Li,Ui，Si)构成了一个(关于共享变量cnt的)临界区(critical section)。(必须确保指令要这样执行)

• 这个临界区不应该和其他线程的临界区交替执行。(这一段的指令不能交叉)。

• 我们要确保每个线程在执行它的临界区中的指令时，拥有对共享变量的互斥的访问(mutually exclusive access)。

  • 通常这种现象叫做互斥(mutual exclusion)。

不安全区

在进程图中，两个临界区的交集形式称为不安全区(unsafe region)。

• 不安全区边缘的不算不安全区的一部分。

安全轨迹线，不安全轨迹线

• 绕过不安全区的轨迹线叫做安全轨迹线。
  • 能正确更新计数器
• 接触到不安全的轨迹线叫做不安全轨迹线。

我们必须以某种方式同步线程，使它们总是有一条安全轨迹线

• 一个经典的方法，就是基于信号量的思想。

12.5.2 信号量

Edsger Dijksta，并发编程领域的先锋任务，提出了一种经典的解决同步不同执行线程问题的方法

这种方法是基于一种叫做信号量(semaphore)的特殊类型变量。

• 信号量s是具有非负整数值的全局变量。

• 只能由两种特殊的操作来处理，这两种操作称为P和V

  • P(s),Proberen，测试

    • 如果s是非零的，那么P操作将s减1，并且立即返回。
    • 如果s为零，那么就挂起这个线程，直到s变为非零。
      • 而一个V操作会重启这个线程。
      • 在重启之后，P操作将s减1，并将控制返回给调用者。

  • V(s),Verhogen，增加

    • V操作将s加1.
    • 如果有任何线程阻塞在P操作等待s变成非零。
      • 那么V操作随机会重启这些线程中的一个。
      • 然后将s减去1，完成它的P操作。

  • 重点，P操作和V操作都是不可分割的，也就是自身确保了是一个带有安全轨迹的操作。(所以又叫原语)

    • 对比，上文中的cnt++的操作。
    • 例如，加1这个操作中，加载，加一，存储信号量过程是不可分割的。

---

P和V的定义确保了一个正在运行的程序绝不可能进入这样一种状态，也就是不可能有负值。
这个属性叫做信号量不变性(semaphore invariant)，为控制并发程序的轨迹线提供了强有力的工具。

12.5.3 使用信号量来实现互斥

信号量提供了一种很方便的方法来确保对共享变量的互斥访问。

基本的思想是

• 将每个共享变量(或一组相关的共享变量) 与一个信号量s(初始为)`联系起来。
• 然后用P(s)和V(s)操作相应的临界区包围起来。

---

以这种方式保护共享变量的信号量叫做二元信号量(binary semaphore)

• 因为它的值总是0或者1。

以提供互斥为目的的二元信号量常常也称为互斥锁(mutex)。

• 在一个互斥锁上执行P操作叫做互斥锁加锁。
• 在一个互斥锁上执行V操作叫做互斥锁解锁。
• 对一个互斥锁加了锁还没有解锁的线程称为占用这个互斥锁。

一个被用作一组可用资源的计数器的信号量称为计数信号量。

关键思想:

• P操作和V操作的结合创建了一组状态，叫做禁止区(forbidden regin)，其中s<0
  • 因为信号量的不变形，不可能有轨迹线进入这个区域
  • 而且禁止区包含了不安全区的任何部分。
    • 使得，每条可行的轨迹线都是安全的。

---

代码上的实现

正确实现上文中的cnt的线程同步。

• 第一步:声明一个信号量 mutex

    volatile int cnt = 0 ; 
    sem_t mutex;
  

• 第二步:主线程中初始化

    Sem_init(&mutex,0,1);
  

• 第三步，在线程例程中对共享变量cnt的更新包围P和V操作，从而保护了它们。

    for( i = 0 ;i < niters ;i++) {
        P(&mutex);
        cnt++;
        V(&mutex);
    }
  

12.5.4 利用信号量来调度共享资源

除了提供互斥外，信号量的另一个重要作用是调度对共享资源的访问。

• 在这种场景中，一个线程用信号量操作来通知另一个线程，程序状态中的某个条件为真了。

• 两个经典而有用的例子。

  • 生产者 - 消费者 问题
  • 读者 - 写者 问题

1.生产者和消费者

图给出了生产者消费者问题

• 生产者线程反复地生成新的项目，并把它们插入到缓冲区中。
• 消费者线程不断地从缓冲区取出这些项目，然后消费使用它们。
• 也可能有多个的变种。

因为插入和取出项目都涉及更新共享变量

• 所以我们必须保证对缓冲区的访问是互斥的
• 还需要调度对缓冲区的访问。
  • 如果缓冲区是满的，那么生产者必须等待直到有一个槽位变为可用。
  • 如果缓冲区是空的，那么消费者必须等待知道有一个项目变为可用。

---

我们将开发一个简单的包，叫做SBUF，用来构造生产者-消费者程序。

SBUF操作类型为sbuf_t的有限缓冲区。

• 项目存放在一个动态分配的n项整数数组(buf)中。
• front和rear索引值记录该队列的第一项和最后一项。
• 三个信号量同步对缓冲区的访问。
  • mutex信号量提供互斥的缓冲区访问
  • slots和items信号量分别记录空槽位和可用项目的数量。

以下给出SBUF函数的实现:

• sbuf_init函数进行初始。
  • 为缓冲区分配堆存储器
  • 设置front和rear表示一个空的缓冲区。
  • 并为3个信号量赋初值。

• sbuf_deinit函数是当应用程序使用完缓冲区时，释放缓冲区存储。

• sbuf_insert

  • 等待一个可用的槽位
  • 对互斥锁加锁，添加项目，对互斥锁解锁
  • 然后宣布有一个新项目可用。

• sbuf_remove

  • 等待一个可用的项目
  • 对互斥锁加锁，取出项目，对互斥锁解锁
  • 然后宣布有一个新槽位可用。

2.读者-写者问题

读者-写着问题是互斥问题的一个概括。

• 一组并发的线程要访问同一个数据对象。

  • 修改对象的线程叫做写者
  • 只读对象的线程叫做读者

• 写者必须拥有对对象的独占访问。

• 读者可以和无限多个其他读者共享对象。

• 一般来说有无数个并发的读者和写者。

---

读者-写者问题有几个变种，都是基于读者和写者的优先级

• 第一类读者-写者问题

  • 读者优先，要求不要让读者等待，除非已经把一个使用权限赋予了一个写者。
  • 换句话说，读者不会因为有一个写者在等待而等待。

• 第二类读者-写者问题(?)

  • 写者优先，要求一但一个写者准备好可以写，它就会尽可能地完成它的写操作。
  • 同第一类不同，在一个写者到达后的读者必须等待，即使这个写者也是在等待。

给出第一类读者-写者问题答案。

• 这个的优先级很弱，因为一个离开临界区的写者可能重启一个在等待的写者(随机重启)
  • 很有可能一群写者使得一个读者饥饿

• 信号量w控制对访问共享对象的临街区的访问。

  • 读者

    • w只对第一个读者上锁
    • w对最后一个走的读者解锁

  • 写者

    • 写者只要进入临界区就对w上锁
    • 写者只要离开临界区就对w解锁
• 信号量mutex保护对共享变量readcnt的访问。
  • readcnt统计当前临界区的读者数量。

所有读者-写者答案都有可能导致饥饿

• 饥饿就是一个线程无限期地阻塞，无法进展。

12.5.5 基于预线程化的并发服务器

为每个新的客户端创建新的线程，有不少的代价。

一个基于预线程化的服务器利用生产者-消费者模型构造一个更高效率的方式。

• 生产者: 主线程
• 消费者: 对等线程

12.6 使用线程提高并行性(暂略)

主要用于多核CPU的算法。

比如:利用并行来完成n路递归

12.7 其他并发问题

互斥和生产者-消费者同步的技术，只是并发问题的冰山一角。

同步问题从根本来说是很难的问题。

这章我们以线程为例讨论。

• 但是要知道同步问题在任何并发流操作共享资源时都会出现。
  • 比如之前学信号时，回收进程时的竞争。

12.7.1 线程安全

一个函数被称为线程安全的(thread-safe)，当且仅当被多个并发线程反复地调用时，它会一直产生正确的结果。否则就是线程不安全的(thread-unsafe)

我们能够定义出四个(不相交)线程不安全函数类:

• 第 1 类 : 不保护共享变量的函数。

  • 解决方案，利用P，V这样的同步操作来保护共享的变量

• 第 2 类 : 保持跨越多个调用状态的函数

  • 一个伪随机数生成器是这类线程不安全的例子。
    

  • 因为产生的结果依赖于上一个next的值。

    • 在单线程中，用同一个seed无论运行多少次，都是同样的结果。
    • 多线程中，这种情况就不会出现了，所以是线程不安全的

  • 解决方案: 重写

    • 使得它不能依赖static，而是依靠调用者在参数中传递状态信息。
    • 缺点: 需要在曾经成千上百个不同的调用位置，修改。十分麻烦。

• 第 3 类 :返回指向静态变量的指针的函数( 有点类似第一类 )

  • 危害:我们在并发线程中调用这些函数，可能发生灾难。
    • 因为一个正在被一个线程使用的变量，可能偷偷被另一个线程悄悄覆盖。
  • 解放方案

    • 重写函数:让调用者传递存放的结果的指针。

    • 加锁-拷贝技术:

      • 在一个调用位置，互斥锁加锁。
      • 调用线程不安全函数，将函数返回的结构拷贝到一个私有的存储器。
      • 然后互斥锁，解锁。

    • 用上面的原理写一个线程不安全函数的包装函数来实现线程安全。

      • 以ctime为例子

      

• 第 4 类 : 调用线程不安全函数的函数。

  • 如果函数f调用线程不安全函数g。那么f可能不安全。
    • 如果g是第二类，那么f一定不安全，也没有办法去修正，只能改变g.
    • 如果g是第一，三类，可以用加锁-拷贝技术来解决。

12.7.2 可重入性

有一类重要的线程安全函数，叫做可重入函数(reentrant function)

• 其特点在于它们有这样一种属性。

  • 当它们被多个线程调用时，不会引用任何共享数据。

• 被分为两类

  • 显示可重入
    • 参数都是值传递
    • 变量都是本地自动栈变量
  • 隐式可重入

    • 参数可以有指针

      • 但是不允许调用者传入指向共享数据的指针。

    • 是否可重入，同时取决于调用者，和被调用者。

• 可重入函数比较高效是因为不需要同步操作。

• 认识到可重入性有时即是调用者也是被调用者的属性。

  • 并不是被调用者的单独属性。

12.7.3 在线程化的程序中使用已存在的库函数

大多数Unix函数，包括大部分定义在标准C库的函数(malloc,free,realloc,printf和scanf)都是线程安全的。

部分线程不安全

• asctime,ctime,localtime函数是在不同时间和数据格式相互来回转换时经常使用的函数。

• gethostbyname,gethostbyaddr,inet_ntoa函数是经常用的网络编程函数。

• strtok函数是一个过时了的同来分析字符串的函数。

---

Unix系统提供大多数线程不安全函数的可重入版本。

• 可重入的版本总是以 _r后缀结尾。
• 例，gethostbyname_r。

12.7.4 竞争

当一个程序的正确性依赖于一个线程要在另一个线程到达y点之前到达它的控制流中的x点，就会发生竞争。

• 通常，竞争发生的理由是因为程序员假定某种特殊的轨迹线穿过执行状态空间。

例子:

程序十分简单。

主线程创建了四个对等线程，并传递一个指向循环变量i的指针作为线程的ID。并输出。

• 一般而言，循环变量i一定是四个不同的。所以会想当然觉得会输出四个不同的ID。

• 但是从结果来看，显然是错误的，有两个3，为什么?
  • 因为我们想当然的觉得对等线程给myid赋值结束后，i才会自增。
  • 竞争来源于 主线程中i++，和对等线程myid=*((int *)vargp)的 竞争。

解决方案:用一个临时地址保存i

12.7.5 死锁

信号量引入了一种潜在的令人厌恶的运行时错误，叫做死锁 (deadlock)。

• 指的是一组线程被阻塞，等待一个永远不为真的条件。

进度图对于理解死锁是一个无价的工具。

• 死锁的区域d是一个只能进，不能出的区域。

  • 位置是合法的，并不是禁止区，能进去。
  • 但是会发现无论向上，还是右，都只剩下禁止区了。

• 如果禁止区不重叠，一定不会发生死锁。

  • 否则，可能发生死锁。

• 死锁是一个相当困难的问题，因为它总是不可预测的。

  • 幸运的话，会绕开死锁区域。
  • 错误还不会重复，轨迹不同。

---

特殊解

使用二元信号量来实现互斥，可以应用一下有效的规则。

互斥锁加锁顺序规则:如果对于程序中每对互斥锁(s,t),每个占用s和t的线程都按照相同的顺序对它们加锁，那么这个程序就是无死锁的。

---

GGGGGGGGGGG，暂时告一段落了!!!!!!!!!!!!!!!!