这是本节的多页打印视图。 点击此处打印.

返回本页常规视图.

进程管理

重点内容，在选择题和大题中都会考察。主要分为进程、CPU调度、同步和互斥以及死锁四个部分，需熟练掌握。
# 进程管理

## 进程和线程

- 进程、线程概念
- 进程、线程状态和转换
- 线程的实现
- 进程、线程的组织和控制
- 进程间通信

## CPU调度和上下文切换

- 概念和目标
- 调度实现方式
- 调度算法
- 上下文及其切换机制

## 同步与互斥

- 概念
- 软件和硬件实现方法
- 锁
- 信号量
- 条件变量
- 经典同步问题

## 死锁

- 概念
- 死锁预防
- 死锁避免
- 死锁检测和解除

1 - 进程和线程

需熟练掌握进程和线程的概念，以及进程的状态转换和内存空间结构，是后续内容的基础，在选择题中会考察。也需了解进程间通信的方式、用户级线程和内核级线程的概念，可能在选择题中考察。

进程和线程

两者的对比

进程主要特点如下：

  • 系统资源分配的基本单位： 进程拥有独立的系统资源，包括内存空间、文件描述符、CPU 时间片等，这些资源的分配由操作系统负责。

线程主要特点如下：

  • 系统调度的基本单位： 多核处理器可以将系统中的不同线程调度到不同的CPU逻辑核心上，所以在同一个时刻，系统中的线程可能会在不同的逻辑核心上并行运行。

进程的状态

状态种类

  1. 创建状态（New）：当进程被创建但还未分配资源或执行时，它处于创建状态。
  2. 就绪状态（Ready）：在就绪状态中，进程已准备好执行，但由于操作系统调度算法或其他原因，尚未获得CPU时间片。
  3. 运行状态（Running）：在运行状态中，进程正在执行指令并占用CPU。
  4. 阻塞状态（Blocked）：当进程在等待某些事件发生时，如等待I/O操作完成或等待其他资源时，它会进入阻塞状态。在阻塞状态下，进程暂停执行，直到等待的事件发生。
  5. 终止状态（Terminated）：当进程执行完毕或被操作系统终止时，它进入终止状态。

状态转化

新建
就绪
运行
终止
阻塞
创建
调度
时间到
事件等待
事件发生
退出
  1. 就绪状态到运行状态:
    • 调度: 当操作系统的调度器选择一个就绪状态的进程分配给处理器时，该进程就会从就绪状态转换到运行状态。
  2. 运行状态到就绪状态:
    • 时间片用完: 如果系统使用时间共享调度，当进程的时间片用完，它会被中断并放回就绪队列。
    • 优先级更高的进程就绪: 在优先级调度算法中，如果一个优先级更高的进程变为就绪状态，当前运行的进程可能会被挂起。
    • 自愿放弃CPU: 进程可能主动放弃CPU，比如它发出了一个系统调用请求其他资源。
  3. 运行状态到阻塞状态:
    • I/O请求: 进程进行I/O操作，由于I/O设备比CPU慢得多，进程会被挂起直到I/O完成。
    • 等待资源: 进程等待不可用的资源，如信号量、互斥锁等。
    • 等待事件: 如等待其他进程的信号、消息或者某个条件的发生。
  4. 阻塞状态到就绪状态:
    • I/O完成: 当I/O操作完成，相应的进程会被移至就绪队列。
    • 资源获得: 进程所等待的资源变得可用，如获得了互斥锁。
    • 事件发生: 进程所等待的事件发生了，如接收到了另一个进程发出的信号。

进程内存空间

  • 用户空间（User Space）：包含进程执行的用户程序代码和数据。在用户空间中，进程可以执行各种任务，如运行应用程序、访问文件系统等。用户空间对于应用程序是可见的，但对于操作系统中的核心功能是不可见的。
    1. 代码区（Text Segment）：也称为"可执行代码区"，存储了进程的可执行代码，包括程序的指令和只读数据。这个区域通常是只读的，因为程序的指令在运行时不应该被修改。
    2. 数据区（Data Segment）， 数据区分为两个子区域：
      • 初始化数据区（Initialized Data Segment）：存储全局和静态变量以及初始化的数据。这些变量在程序运行前就已经分配了内存并初始化。
      • 未初始化数据区（Uninitialized Data Segment）：也称为"BSS"（Block Started by Symbol）段，存储全局和静态变量，但这些变量没有显式的初始化值。操作系统会在程序启动时自动将这个区域初始化为零。
    3. 堆区（Heap）：堆区是动态分配内存的地方，用于存储程序运行时需要的变量和数据结构。在堆中分配的内存需要手动释放，以避免内存泄漏。
    4. 栈区（Stack）：栈区用于存储函数调用和局部变量。每个函数调用都会在栈上创建一个栈帧，栈帧包含了函数的参数、局部变量以及函数返回地址。栈是一种后进先出（LIFO）的数据结构，它的大小通常有限，由操作系统或编程语言定义。
    5. 内存映射区域（Memory Mapped Region）：这是一些操作系统或运行时库的扩展，用于存储动态链接库（DLL）和共享库的信息以及其他系统数据结构。
  • 内核空间（Kernel Space）：内核空间包含了操作系统的核心代码和数据结构，如页表、调度程序和系统调用接口等。内核空间具有更高的特权级别，可以执行特权指令并且访问系统的各种资源，内核空间对于用户程序是不可见的。
Process-specific data
structures
(e.g. page tables, tasks and kernel stack)
Physical Memory
Kernel code and data
User stack
Memory-mapped region
for shared libraries
Run-time heap
Uninitialized data (.bss)
Initialized data (.data)
Code (.text)
Different for
each process
Identical for
each process
Kernel
virtual
memory
Process
virtual
memory
low
address
space
high
address
space

进程间通信

  • 共享内存（Shared Memory）：共享内存允许多个进程访问相同的物理内存区域，这样它们可以直接共享数据，而不需要复制数据。这是一种高效的通信方式，但需要谨慎管理共享数据以避免竞态条件。
  • 管道（Pipes）：管道是一种单向通信方式，通常用于父子进程之间或兄弟进程之间的通信。有命名管道和匿名管道两种，匿名管道只能在有亲缘关系的进程之间使用。
  • 消息队列（Message Queues）：消息队列是一种进程间通信的机制，允许进程通过消息来进行异步通信。消息队列通常由操作系统维护，可以支持多个读者和写者。
  • 信号（Signals）：信号是一种轻量级的通信机制，用于通知进程发生了某些事件。进程可以发送信号给其他进程，比如终止信号、挂起信号等。
  • 套接字（Sockets）：套接字是一种通用的进程间通信方式，通常用于不同计算机之间的网络通信。它支持多种协议，如TCP和UDP，可以实现客户端-服务器通信。
  • 信号量（Semaphores）：信号量是一种计数器，用于控制多个进程对共享资源的访问。信号量可以用于解决竞争条件和进程同步的问题。

用户级线程和内核级线程

  • 用户级线程（user level thread）：用户级线程是在用户空间中创建和管理的线程，不依赖于操作系统的内核支持。这些线程由用户程序或用户级线程库管理，而不需要操作系统内核的介入。
  • 内核级线程（kernel level thread）：内核级线程是由操作系统内核管理和调度的线程。每个内核级线程都有自己的内核数据结构（例如，进程控制块，PCB），由操作系统内核负责创建、销毁和调度。

这个东西其实不太好理解，以真实的应用场景为例，当我们使用linux的pthread library创建线程时，这个线程其实是由操作系统进行管理和调度的，并不需要用户程序进行管理，所以当我们使用系统调用创建线程时，可以理解为创建的实际是内核级线程。

那么用户级线程在实际应用中到底是怎样的呢，根据其定义，用户级线程由程序或用户级线程库管理，这里举实际的例子的话，就是go语言中的goroutine或者python异步库asyncio中的的coroutine，这两者都是协程模型的实现，协程可以理解为更轻量的线程，协程库在用户空间内实现了一个调度机制，可以在系统执行一个线程的时间片内，创建多个协程并且在这个时间片内调度多个协程执行。由于协程的切换是在用户空间内实现的，不需要系统调用，所以效率更高，占用的资源更少。

用户级线程和内核级线程的映射方式（这里了解即可）包含多对一、一对一、多对多模型：

多对一模型
一对一模型
多对多模型
用户线程
内核线程

视频讲解

2 - 处理机调度

需熟练掌握系统调度指标以及调度算法，常在选择题中考察。

调度的指标

  1. CPU利用率:
    • 定义：它是CPU活跃时间与总观察时间的比率。通常表示为百分比。
    • 说明：CPU利用率是衡量CPU工作效率的一个关键指标。如果CPU利用率接近100%，则表示CPU几乎一直在工作。如果利用率很低，可能意味着CPU有大量的空闲时间。
  2. 系统吞吐量:
    • 定义：在单位时间内系统完成的工作量或进程数。
    • 说明：高吞吐量意味着系统能在短时间内完成更多的工作或处理更多的进程。
  3. 周转时间:
    • 定义：进程从提交到完成所经过的总时间。这包括了进程在等待、执行以及在其他各种队列中的时间。
    • 说明：较短的周转时间通常是预期的，因为这意味着进程更快地得到处理和完成。
  4. 等待时间:
    • 定义：进程在就绪队列中等待CPU时间的总时间。
    • 说明：等待时间不包括任何I/O操作或其他需要的资源的等待时间。较低的等待时间是理想的，因为这意味着进程花费较少的时间只是在等待执行。
  5. 响应时间:
    • 定义：从提交一个请求到收到第一个响应所经过的时间。在交互式系统中，响应时间通常非常关键。
    • 说明：对于交互式任务（例如在GUI系统中的任务），响应时间尤为重要，因为用户通常期望快速的反馈。较短的响应时间提供了更好的用户体验。

系统调度过程

进程调度是计算机操作系统中的一种核心功能，它决定了哪个进程应该在给定的时间段内使用处理器。为了有效地管理和调度进程，操作系统通常采用多级调度机制。这些调度机制分为三个层次：高级调度、中级调度和初级调度。

Pull of
job in
disk
Pull of...
Ready Queue
Ready Queue
Waiting Queue
Waiting Queue
I/O
I/O
Dispatcher
Dispatcher
CPU
CPU
END
END
Long term
Scheduler
Long term...
Short term
Scheduler
Short term...
Mid-term
Scheduler
Mid-term...
Mid-term
Scheduler
Mid-term...Text is not SVG - cannot display
  1. 高级调度（长程调度，Long-term Scheduling）:
    • 功能：高级调度主要决定哪些进程应当被加载到内存中成为一个可运行的进程。
    • 主要目标：保持内存中适当数量的进程。不要过多也不要过少。
    • 当进程首次进入系统时，它们首先被放置在磁盘的一个区域，称为作业池。高级调度器从作业池中选择进程，根据某种策略将其加载到内存中，从而使其成为一个可运行的进程。
  2. 中级调度（中程调度，Mid-term Scheduling）:
    • 功能：中级调度涉及到进程的暂停和重启。当系统的进程数超过内存容量时，中级调度器可能会将一些进程从内存移出到磁盘上（这称为交换或页面置换），从而为新的或等待的进程腾出空间。
    • 主要目标：为高级和初级调度器优化内存使用。
    • 中级调度器在必要时将进程从内存交换到磁盘，并在适当的时机将其交换回内存。
  3. 初级调度（短程调度，Short-term Scheduling）:
    • 功能：初级调度决定哪个进程应当被赋予CPU时间片，即决定下一个运行在处理器上的进程。
    • 主要目标：确保CPU的高效利用。
    • 它的决策频率非常高，因为在多任务环境中，每个时间片的长度可能只有几十毫秒。因此，初级调度器必须是非常快速的。

调度的实现

调度器

调度器/调度程序（scheduler）:

  • 调度器是操作系统中负责决定下一个要执行的进程或线程的部分。
  • 基于特定的调度算法（如轮转、优先级调度、短作业优先等），它决定哪个进程或线程应当获得CPU时间。
  • 调度器通常分为长程、中程和短程调度器，如前文所述。

调度时机

调度的时机可能包括以下情况：

  • 进程进入或退出系统
  • 进程从运行状态变为阻塞状态
  • 或者一个时间片结束。

调度方式

  • 抢占式调度（Preemptive）：在这种调度方式下，当一个进程正在执行时，操作系统可以中断该进程的执行并将CPU分配给另一个进程。这常常发生在一个更高优先级的进程变为就绪状态时。
  • 非抢占式调度（Non-Preemptive）：在这种方式下，一旦CPU分配给一个进程，它会继续运行直到完成或者转为非运行状态（例如，等待I/O操作）。

闲逛进程

当没有其他进程可以执行时，系统会运行一个特殊的进程，称为闲逛进程或空闲任务。它的主要任务通常是简单的：使CPU保持忙碌。在某些系统中，闲逛进程可能会执行一些简单的任务，如背景清理。该进程通常具有最低的优先级，因此只有在没有其他进程可以运行时才会执行。

两种线程的调度

  • 内核级线程：由操作系统内核直接支持的线程。操作系统知道这些线程的存在，并可以直接进行调度。
  • 用户级线程：完全在用户空间中实现的线程，不需要内核的介入。
  • 对于内核级线程，操作系统可以直接调度它们，并可以利用多核或多处理器的优势。
  • 对于用户级线程，因为内核不知道它们的存在，所以内核无法直接调度它们。线程之间的上下文切换可能比内核级线程更快，但在多处理器系统中，它们可能无法充分利用所有的处理器。

调度算法

1. 先来先服务

先来先服务（First-Come, First-Served，FCFS）按照进程到达的顺序分配CPU时间。先到达的进程先执行，直到完成或阻塞。

2. 最短作业优先

最短作业优先（Shortest Job First，SJF）该算法选择具有最短执行时间的进程，以最小化平均等待时间。它需要知道每个进程的执行时间，通常在实际系统中难以获得。

3. 优先级调度

进程被分配一个优先级，CPU总是分配给具有最高优先级的进程。这种算法可以是静态的（进程创建时分配优先级）或动态的（根据进程的行为和状态进行动态调整）。

4. 最高响应比优先

最高响应比优先（Highest Response Ratio Next，HRRN）这种算法根据进程的等待时间和执行时间比来选择下一个执行的进程，以提高响应性。

5. 时间片轮转

时间片轮转（Round Robin，RR）这是一种基于时间片的算法，每个进程被分配一个固定的时间片，当时间片用完时，进程被放回队列尾部，下一个进程开始执行。这样可以实现公平的CPU时间分配。

6. 多级反馈队列

多级反馈队列（Multilevel Feedback Queue）这是一种混合算法，将进程分为多个队列，每个队列有不同的优先级和时间片大小。新创建的进程进入最高优先级队列，如果没有完成，它将下降到较低优先级的队列，直到完成。

CPU
CPU
CPU
CPU
CPU
CPU
Level 1 Queue
(Round Robin, Quantum = 8)
Level 1 Queue...
Level 2 Queue
(Round Robin, Quantum = 16)
Level 2 Queue...
Level n Queue
(FCFS)
Level n Queue...
Finish
Finish
Finish
Finish
Finish
Finish
Not Finish
Not Finish
Not Finish
Not FinishText is not SVG - cannot display

上下文及其切换机制

进程的上下文是进程执行的环境。在操作系统中，它指的是一个进程在特定时间点上的系统状态，包括多种信息，这些信息使得进程在被中断后可以再次恢复并继续执行。当操作系统从一个进程切换到另一个进程时，它会保存当前进程的上下文并恢复下一个进程的上下文。这个过程被称为上下文切换。

进程上下文内容

  1. 寄存器值：这包括通用寄存器、程序计数器、栈指针、状态寄存器等。它们保存了进程的当前执行位置和状态。
  2. 程序计数器：表示进程的下一个指令的位置。
  3. 虚拟内存信息：这包括进程的页表、页目录等信息，描述了进程的地址空间布局。
  4. I/O状态信息：包括打开的文件描述符、网络连接、I/O指针等。
  5. CPU调度信息：例如进程优先级、计划器状态等。
  6. 资源使用情况：这可能包括该进程所使用的各种资源的跟踪信息，如内存、文件句柄等。

上下文切换流程

  1. 保存当前进程的状态：操作系统保存当前正在运行的进程的上下文。这意味着它会将当前的寄存器值、程序计数器等保存到进程的进程控制块（PCB）中。
  2. 选择下一个要执行的进程：调度器决定下一个要运行的进程。
  3. 恢复下一个进程的状态：操作系统从新进程的PCB中恢复其上下文信息，包括寄存器值、程序计数器等。
  4. 开始执行新进程。

3 - 同步和互斥

同步和互斥是操作系统中考察的重中之重，关于各个概念的理解经常在选择题中出现，需要熟练掌握信号量的用法。

实现互斥的方法

软件互斥

Peterson’s Algorithm

Peterson’s Algorithm 基于两个线程之间的竞争条件来实现互斥。它使用两个布尔变量和一个整数变量，分别表示两个线程的意愿和当前正在运行的线程。通过这些变量的协作，可以确保只有一个线程能够进入临界区。

Peterson’s Algorithm 通常用于理论教学和理解互斥原理，但在实际多线程编程中并不常用，因为它只适用于两个线程之间的互斥。

// 初始化
bool flag[2] = {false, false};  // 两个线程的意愿
int turn = 0;                   // 当前运行的线程（0 或 1）

// 线程 1 希望进入临界区
void thread0() {
    flag[0] = true;
    turn = 1; // 通知线程 2 你可以运行了
    while (flag[1] && turn == 1) {
    // 等待线程 2 退出临界区或让出 CPU
    }
    // 进入临界区
    // ...
    // 退出临界区
    flag[0] = false;
}

// 线程 2 希望进入临界区
void thread1() {
    flag[1] = true;
    turn = 0; // 通知线程 1 你可以运行了
    while (flag[0] && turn == 0) {
    // 等待线程 1 退出临界区或让出 CPU
    }
    // 进入临界区
    // ...
    // 退出临界区
    flag[1] = false;
}

硬件互斥

硬件互斥是一种在计算机体系结构层面实现的互斥机制，通常用于保护共享资源，以确保在多核处理器系统中同时只有一个线程或核心能够访问这些资源。硬件互斥的实现通常依赖于底层硬件支持，包括原子指令和特殊的寄存器。

原子指令：原子指令（Atomic Instructions），也称为原子操作或原子操作指令，是计算机体系结构中的一种特殊指令，它们被设计为在单个处理器指令周期内执行完毕，不会被中断或其他线程干扰。

这里主要掌握 TAS 和 CAS 两种原子指令即可：

  • Test-and-Set（TAS）指令：TAS 指令用于原子地设置一个内存位置的值，并返回该位置的先前值。互斥锁可以用一个整数变量表示，0 表示锁是空闲的，1 表示锁已经被占用。锁定操作可以使用 TAS 指令来尝试将锁的值从 0 设置为 1，如果返回的先前值为 0，则表示锁定成功。解锁操作将锁的值设置为 0。
  • Compare-and-Swap（CAS）指令：CAS 指令用于原子地比较内存位置的当前值与一个预期值，并只有在它们匹配时才会更新该位置的值。互斥锁可以用 CAS 指令来实现。例如，锁定操作可以使用 CAS 指令来将锁的值从 0 修改为 1，如果 CAS 操作成功，则表示锁定成功。解锁操作可以使用 CAS 来将锁的值从 1 修改为 0。

利用 TAS 来实现互斥：

// TAS 原子指令相当于以下函数被原子性地执行
bool TestAndSet(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

// 通过 TAS 实现自旋锁
void acquire_lock(bool *lock) {
    while (!TestAndSet(lock)) {
        // 锁被占用，继续自旋等待
    }
}

void release_lock(bool *lock) {
    *lock = false;
}
// CAS 原子指令相当于以下函数被原子性地执行
bool CompareAndSet(bool *lock, bool expected, bool new_value) {
    if (*lock == expected) {
        *lock = new_value;
        return true;  // 操作成功
    } else {
        return false; // 操作失败
    }
}

// 通过 CAS 实现自旋锁
void acquire_lock(bool *lock) {
    while (!CompareAndSet(lock, false, true)) {
        // 锁被占用，继续自旋等待
    }
}

void release_lock(bool *lock) {
    *lock = false;
}

C 语言通过 TAS 实现自旋锁

互斥锁

互斥锁（Mutex，来源于“mutual exclusion”，即相互排斥）是并发编程中用于确保多个线程不会同时访问共享资源或执行特定代码段的同步原语。互斥锁提供了一种机制，确保在任何时刻只有一个线程能够持有该锁，从而确保共享资源的安全访问。

基本特点：

  • 互斥性：任何时候，只有一个线程可以持有互斥锁。其它试图获取该互斥锁的线程将被阻塞，直到持有锁的线程释放该锁。
  • 所有权：只有锁的持有者才能释放它。这确保了非持有者不能误释放锁。

基本操作：

  • 锁定（Lock 或 Acquire）：当线程试图获取互斥锁时，如果锁已被其他线程持有，则该线程将被阻塞，直到锁被释放。
  • 解锁（Unlock 或 Release）：持有互斥锁的线程在完成其对共享资源的访问后，应该释放锁以使其他线程可以获取锁。

线程是如何在互斥锁操作中被阻塞或唤醒的？

当线程尝试获取一个已经被持有的锁时，它会被挂起，并且不会消耗 CPU 资源。只有当锁被释放并且该线程被选择为下一个获取锁的线程时，它才会恢复执行。这样的机制确保了临界区的互斥访问，同时也尽量减少了不必要的 CPU 浪费。

  • 阻塞：
    • 当线程尝试获取一个已经被其他线程持有的互斥锁时，该线程会进入一个等待状态，也称为阻塞状态。
    • 操作系统维护了一个与该互斥锁关联的等待队列。尝试获取锁但未成功的线程会被放入这个队列中。
    • 被阻塞的线程会从“运行”状态转为“等待”或“睡眠”状态。这意味着该线程将不再获得 CPU 时间，直到它被唤醒。
  • 唤醒：
    • 当持有互斥锁的线程释放该锁时，操作系统会检查与该锁关联的等待队列。
    • 通常，队列中的下一个线程（取决于调度策略，可能是队列的第一个线程或其他）会被选中并被唤醒，允许它获取锁。
    • 被唤醒的线程转换为“就绪”状态，并在适当的时候由调度器重新分配 CPU 时间，从而继续执行。
thread A
Pending Queue for Lock L
Thread A is holding
the lock currently
thread B
thread C
thread D
Thread D is trying to acquire the lock,
and it's appended to the pending queue 
LOCK L
thread B
Pending Queue for Lock L
Thread A release lock and
execute the following code
thread C
thread D
LOCK L
thread A
acquire(l)
critical section
release(l)
following code
Thread B is holding
the lock currently
acquire(l)
critical section
release(l)
following code
acquire(l)
critical section
release(l)
following code
acquire(l)
critical section
release(l)
following code
Thread A release the lock
and operating system pick a thread from pending queue
and grant the lock to it

需要注意的是，上述描述是一个高级和简化的过程。实际的操作系统实现可能会有更多的优化和特性，如优先级反转控制、超时机制、自旋锁等。

条件变量

条件变量（Condition Variable） 是一种同步原语，用于线程之间的有条件同步。它允许线程等待某个条件成立，同时释放已获取的锁，这样其他线程可以获取锁并可能更改共享数据的状态，使得条件成立。

用途

  • 实现同步操作：有时，线程需要等待某个条件才能继续执行。条件变量使线程可以等待，直到其他线程更改了共享数据的状态并满足了该条件。
  • 避免忙等（busy-waiting）：而不是使线程不停地轮询共享数据以检查条件是否满足（这会浪费 CPU 资源），条件变量使线程可以休眠直到条件满足。

操作

  • wait()：这个操作做两件事。首先，它会释放与条件变量关联的锁，从而使其他线程可以获取锁并更改共享数据的状态。其次，它会使调用它的线程休眠，直到另一个线程来唤醒它。
  • signal()：这个操作用于唤醒等待在条件变量上的某个线程。如果多个线程在等待，通常只有一个线程被唤醒（但这取决于具体实现）。唤醒的线程将重新获取锁并从其调用 wait() 的地方继续执行。
  • broadcast() 或 notify_all()：这个操作唤醒所有等待在条件变量上的线程。当共享数据的状态变化可能影响多个等待的线程时，这很有用。

信号量

信号量（Semephore）是一个同步原语，相比锁，信号量可以解决一些更加复杂的同步问题。

在逻辑上我们将信号量理解为一个整数值，信号量提供两个原子操作：

  • P （proberen，荷兰语的“尝试”之意）
  • V （verhogen，荷兰语的“增加”之意）。

P 操作

P 操作也被称为 wait 操作， P 操作的具体流程如下：

  • 如果信号量值大于 0，则减少信号量的值，并继续执行后续代码。
  • 如果信号量值为 0，则执行 P 操作的线程将被阻塞，直到信号量变为正值。

简而言之，就是尝试（正如荷兰语的原义）将信号量的值减一，若不至于将信号量的值减为负数。 则尝试成功，线程可继续执行后续代码。若尝试失败，则线程被阻塞。

V 操作

V 操作也被称为 signal 操作， V 操作的具体流程如下：

增加信号量的值。如果有任何线程因为 P 操作被阻塞，则选取一个被阻塞的线程（选择机制可能依赖于具体的实现）并唤醒它。 接着继续执行后续代码。

信号量是如何实现的

只需要在逻辑上理解信号量的机制即可，信号量中有维护有一个整数值，并且与一个阻塞队列和运行队列相关联。

  • 当线程的 P 操作执行成功后，线程被加入信号量的运行队列。
  • 当线程的 P 操作执行失败后，线程被加入信号量的阻塞队列。
  • 当线程的 V 操作执行成果后，线程被从运行队列中移除，并尝试从阻塞队列中选取线程继续执行 P 操作。

线程是如何在 PV 操作中被阻塞或唤醒的？

当一个线程尝试执行 P 操作并发现信号量的值为 0 或负数时，该操作会导致该线程阻塞。具体地说，线程会被移出运行队列并放入一个特定的阻塞队列。这个阻塞队列是与信号量关联的，其中保存了因该信号量被阻塞的所有线程。

当其他线程对该信号量执行 V 操作并增加其值时，一个被阻塞的线程（或多个，具体取决于实现和信号量的增量）会从等待队列中被选出并被唤醒，随后它可以继续执行。

信号量应用

用信号量实现同步操作

先执行 P1 中的 code1，再执行 P2 中的 code2：

semphore S = 0;

P1() {
    code1;       // 先执行 code1
    V(S);        // 告诉线程 P2，code1 已经完成
    ...
}

P2() {
    ...
    P(S);        // 检查 code1 是否完成
    code2;       // 检查无误，运行 code2
}

用信号量实现互斥操作

当信号量的初始值为 1 时，可以把信号量当作锁使用：

semaphore S = 1;

P1() {
    P(S);
    // critical section
    V(S);
}

P2() {
    P(S);
    // critical section
    V(S);
}

用信号量实现前驱关系

S4
S2
S6
S5
S1
c
d
b1
b2
a1
S3
a2
e
semphore a1 = a2 = b1 = b2 = c = d = e = 0;

S1() {
    ...;
    V(a1); V(a2);
}

S2() {
    P(a1);
    ...
    V(b1); V(b2);
}

S3() {
    P(a2);
    V(e);
}

S4() {
    P(b1);
    V(c);
}

S5() {
    P(b2);
    V(d);
}

S6() {
    P(c); P(d); P(e);
}

管程

管程（Monitor）是一个并发编程中的同步原语，用于封装共享数据及其操作以确保对共享数据的并发访问是安全的。它提供了一种结构化的方式来封装共享数据、对数据的操作方法以及同步机制（如条件变量）。

管程的核心思想是仅在给定的时间允许一个线程进入并执行管程中的代码，从而实现对共享资源的互斥访问。当其他线程试图进入同一管程时，它们将被阻塞，直到当前执行的线程退出管程。

管程基本组成：

  • 共享数据：管程封装了需要被多个线程共享和访问的数据。
  • 方法：定义了如何操作共享数据的函数或方法。这些方法是唯一可以访问和修改共享数据的方式。
  • 条件变量：用于控制线程的执行顺序，让线程在某些条件下等待，或通知等待的线程继续执行。

管程和锁、信号量的区别？

锁和信号量是更低级的同步原语。尽管它们非常有用并且广泛应用，但在某些情况下直接使用它们可能导致代码复杂且难以理解。另外，使用这些低级原语可能会增加死锁、饥饿或其他同步问题的风险。

管程的设计是为了将这些低级的细节隐藏起来，并提供一个更高级、更抽象的接口，使得程序员可以更容易地编写正确、安全的并发代码。

管程的实际例子

用管程封装生产者消费者问题。

视频讲解

4 - 经典同步问题

在考题中，经常需要你基于信号量的PV操作去实现某个同步问题，你首先需要熟练掌握本节的经典同步问题，并能在真实场景中自定义数据结构以及信号量，去设计同步问题的解决方案。

生产者消费者问题

Producer
Producer
Consumer
ConsumerText is not SVG - cannot display

生产者-消费者问题是并发编程中的经典问题，涉及到两种线程——生产者和消费者，它们共享一个固定大小的缓冲区或存储区。生产者的任务是生成数据并将其放入缓冲区，而消费者的任务是从缓冲区中取出并消费这些数据。关键的挑战在于确保生产者不会在缓冲区满时添加数据，同时确保消费者不会在缓冲区空时尝试消费数据。

semaphore mutex = 1;          // 临界区互斥信号量
semaphore empty = n;          // 空闲缓冲区数量
semaphore full  = 0;          // 忙缓冲区数量

producer() {
    while (1) {
        P(empty)              // 等待一个空位置
        P(mutex)              // 进入临界区前先获取mutex
        ....                  // 将数据项添加到缓冲区
        V(mutex)              // 离开临界区，释放mutex
        V(full)               // 增加一个数据项的计数
    }
}

consumer() {
    while (1) {
        P(full)               // 等待一个数据项
        P(mutex)              // 进入临界区前先获取mutex
        ...                  // 从缓冲区取出数据项并消费
        V(mutex)              // 离开临界区，释放mutex
        V(empty)              // 增加一个空位置的计数
    }
}

生产者消费者问题C代码实现

读者-写者问题

reader
reader
reader
reader
writer
writer
x
reader
writer
writer
x
x
writer
reader is holding the resource
writer is holding the resource

读者-写者问题是另一个经典的并发编程问题，涉及到对共享数据或资源的访问，这些资源可以被多个读者同时读取，但只能被一个写者写入，而且当写者正在写入数据时，没有其他读者或写者可以访问该资源。

这个问题的挑战在于：

  • 允许多个读者同时读取资源。
  • 确保当有一个写者访问资源时，没有其他读者或写者可以同时访问。
int read_count = 0;
semaphore wrt  = 1;
semphore mutex = 1;

reader() {
    while (1) {
        P(mutex)                     // 获取互斥访问权，以修改read_count
        read_count += 1
        if (read_count == 1) {       // 如果这是第一个读者，需要锁定资源，防止写者写入
            P(wrt)
        }
        V(mutex)                     // 释放互斥访问权
        ...                          // 读取资源
        P(mutex)                     // 获取互斥访问权，以修改read_count
        read_count -= 1
        if (read_count == 0) {       // 如果没有读者在读取，释放资源，允许写者写入
            V(wrt)
        }
        V(mutex)                     // 释放互斥访问权
    }
}

writer() {
    while (1) {
        P(wrt)                       // 获取资源的互斥访问权
        ...                          // 写入资源
        V(wrt)                       // 释放资源的互斥访问权
    }
}
int read_count = 0;
int write_count = 0;
semaphore wrt = 1;
semaphore mutex = 1;
semaphore write_mutex = 1;

reader() {
    while (1) {
        P(write_mutex)                  // 在读取之前，确保没有写者正在等待或写入
        P(mutex)                        // 获取互斥访问权，以修改read_count
        read_count += 1
        if (read_count == 1) {
            P(wrt)
        }
        V(mutex)
        V(write_mutex)

        ...                             // 读取资源

        P(mutex)                        // 获取互斥访问权，以修改read_count
        read_count -= 1
        if (read_count == 0) {
            V(wrt)
        }
        V(mutex)
    }
}

writer() {
    while (1) {
        P(write_mutex)                  // 获取互斥访问权，以修改write_count
        write_count += 1
        if (write_count == 1) {         // 如果这是第一个写者，锁定资源，防止新的读者读取
            P(wrt)
        }
        V(write_mutex)

        ...                             // 写入资源

        P(write_mutex)                  // 获取互斥访问权，以修改write_count
        write_count -= 1
        if (write_count == 0) {         // 如果没有其他写者在等待或写入，释放资源
            V(wrt)
        }
        V(write_mutex)
    }
}
int read_count = 0;
int write_count = 0;
semaphore wrt = 1;
semaphore mutex = 1;
semaphore queue = 1; // 新增队列信号量，以确保公平性

reader() {
    while (1) {
        P(queue);                 // 进入队列
        P(mutex);                 // 获取互斥访问权，以修改read_count
        read_count += 1;
        if (read_count == 1) {
            P(wrt);               // 如果是第一个读者，锁定资源
        }
        V(mutex);
        V(queue);                 // 离开队列
        ...                       // 读取资源
        P(mutex);                 // 获取互斥访问权，以修改read_count
        read_count -= 1;
        if (read_count == 0) {
            V(wrt);               // 如果是最后一个读者，释放资源
        }
        V(mutex);
    }
}

writer() {
    while (1) {
        P(queue);                 // 进入队列
        P(wrt);                   // 锁定资源
        ...                       // 写入资源
        V(wrt);                   // 释放资源
        V(queue);                 // 离开队列
    }
}

读者优先C代码实现

哲学家就餐问题

假设有五位哲学家坐在一个圆桌周围，每两位哲学家之间有一把叉子。哲学家的生活由思考和吃饭两种活动组成。为了吃饭，一个哲学家需要两把叉子——左边和右边的一把。问题在于，如何设计一个算法使得哲学家们可以正常就餐，而不会因为竞争叉子而导致死锁或饥饿。

哲学家就餐问题有多种解法，这里只提供一种最直观的解法，对于包含N各哲学家的问题：

  • 前N-1个哲学家先拿起左边的叉子，再拿起右边的叉子
  • 最后一个哲学家先拿起右边的叉子，再拿起左边的叉子
semaphore fork[5] = {1, 1, 1, 1, 1};      // 五个叉子，初始都是可用的

void philosopher(int i) {
    if (i < 5) {
        // 对于前面的哲学家，先左后右
        first = i;
        second = (i + 1) % 5;
    } else {
        // 对于最后一个哲学家，先右后左
        first = (i + 1) % 5;
        second = i;
    }
    while (1) {
        think();
        P(fork[first]);
        P(fork[second]);
        eat();
        V(fork[first]);
        V(fork[second]);
    }
}

哲学家就餐问题C代码实现

视频讲解

5 - 死锁

重点内容，需熟练掌握死锁的产生条件、处理策略、预防方法以及银行家算法，在选择题中会考察，偶尔也在大题中考察。

死锁产生的必要条件

只有以下四个条件同时满足，死锁才会发生：

  1. 互斥条件 （Mutual Exclusion）: 指的是至少有一个资源必须处于非共享模式，也就是说，一次只有一个线程可以使用资源。如果其他线程请求该资源，那么请求的线程必须等到该资源的持有者释放该资源。
  2. 占有并等待 （Hold and Wait）: 指的是一个线程因请求资源而阻塞时，对当前获得的资源保持不放。换句话说，线程至少已经持有一个资源，但又申请新的资源；由于其他线程持有这些资源，所以它现在是阻塞的。
  3. 非抢占 （No Preemption）: 资源不能被抢占，也就是说，只有资源的持有者才可以释放它。资源在完全自愿的基础上被释放，不能被强行从持有线程中夺走。
  4. 循环等待 （Circular Wait）： 存在一个线程资源的等待链，链中的每一个线程都在等待下一个线程所持有的资源。这导致了一个循环的等待链。

为了避免死锁，需要破坏上述的任意一个条件。

死锁处理策略

  1. 死锁预防：设置限制条件，破坏产生死锁的 4 个必要条件之一。
  2. 死锁避免：在资源的动态分配过程中，用某种算法避免系统进入不安全状态。
  3. 死锁的检测和解除：允许线程在运行过程中发生死锁，通过系统检测机构及时检测出死锁的发生，然后采取某种措施解除死锁。

死锁预防

死锁预防是通过确保系统永远不会满足死锁产生的四个必要条件中的某些条件，从而避免死锁的发生：

  1. 破坏互斥条件
    • 互斥条件在某些情况下是不可避免的，例如打印机等硬件资源。但在某些场景下，通过资源复制或虚拟化技术，可以尝试减少资源的互斥使用。
  2. 破坏占有并等待
    • 要求线程在开始时一次性申请其需要的所有资源。只有当所有资源都可用时，线程才被分配资源并开始执行。这样，线程在执行期间不会等待其他资源。
    • 另一个方法是，如果线程申请新资源而被拒绝，则它必须释放所有已分配的资源，再重新申请。
  3. 破坏非抢占
    • 当一个线程需要的资源被另一个线程所占有时，它可以抢占另一个线程的资源。
  4. 破坏循环等待
    • 对线程申请资源的顺序进行限制

死锁避免

死锁避免是系统级的算法，需要对系统的资源和实体进行抽象，进行统筹规划，其中最经典的算法是银行家算法。

银行家算法

这里首先说一下次算法的命名，为什么叫“银行家”。一般而言，银行家都具备以下特点：

  • 掌管金库（即资源），可以放贷（即满足线程申请的资源）
  • 理性地作出决策，避免银行破产（即系统进入不安全状态）

相对于银行家的就是客户（即线程），线程需要申请一定量的资源。 但是线程可能不会立即申请全部的资源，线程也许会依次申请所有请求资源中的一部分， 当线程申请完全部的资源之后，它才会释放这些资源。

为了对刚刚描述的过程进行建模，我们需要定义如下的 数据结构：

  • 系统
    • Available：表示每种资源的可用数量。
  • 线程
    • Max：表示每个线程对每种资源的最大需求量。
    • Allocation：表示已经分配给每个线程的资源数量。
    • Need：表示每个线程还需要的资源数量，Need = Max - Allocation

算法步骤：

  1. 初始化：为每个线程和每种资源设置 Max、Allocation 和 Need。
  2. 当一个线程请求资源时，检查请求的资源数量是否小于等于 Need，如果大于则请求失败。
  3. 检查请求的资源数量是否小于等于 Available，如果大于则请求失败。
  4. 如果请求合法（满足上述两个条件），则模拟分配资源给该线程（预分配），即将资源从系统的 Available 减去，加到线程的 Allocation 中，并从线程的 Need 中减去相应数量的资源。
  5. 然后，进行安全性检查，判断是否存在一种 安全分配序列，使得所有线程都能顺利执行完成。
  6. 如果存在安全分配序列，则执行资源分配，否则拒绝请求，因为分配资源可能导致死锁，并且回收预先模拟分配的资源。
  7. 当线程完成任务时，释放已分配的资源，将它们从 Allocation 减去，加到 Available 中。

什么是安全分配序列：

安全分配序列是线程的一个排列，它保证了对于序列中的每个线程，当这些线程都申请 Need 中的全部资源时，系统都能够满足这些需求。

如果系统存在一个安全分配序列，则系统处于 安全状态。

注意：不安全状态不意味着死锁，但它意味着有死锁的风险。不安全状态只是死锁的一个先兆，但不是死锁本身。

如何判断是否存在安全分配序列

假设系统中存在 N 个线程的话，则最多进行 N 轮遍历，每一轮至少找到一个 need 小于或等于 available 的线程，如果可以找到的话，就回收这些线程的 allocation，并将其加入 available 中，直到回收了所有线程的资源。如果有一轮存在这种情况：剩余的线程（任务未完成的线程）中的每一个 need 都大于 available，那么则说明无法找到一个安全分配序列，系统处于不安全状态。

这种判断方式的背后具有这样的逻辑：因为线程必须申请完所有需要的资源（即max）才能返还已申请的资源，所以系统在当下肯定是尽量满足那些可以返还资源的线程，因为只有回收了一些资源之后，才能满足之前可能无法满足的线程。

但是如果在某一个时刻，剩余的线程的资源一个都无法回收了，那么系统就进入了不安全状态。

这里还要需要注意的是，在实际的算法中，我们需要用 work 替代 available 来帮助我们完成安全性检查的过程，因为检查只是一种 “逻辑推演”，我们并不希望实际修改系统中的资源情况，具体的代码实现可以参考如下链接：

银行家算法代码实现

死锁的检测和删除

为了能对系统是否已发生了死锁进行检测，必须：

  1. 用某种数据结构来保存资源的请求和分配信息：
  2. 提供一种算法， 利用上述信息来检测系统是否已进入死锁状态。

一般来说，一种简单的建模方式是使用资源分配图：

  • 将系统中的所有资源和进程表示为图中的节点。
  • 如果进程 P1 请求资源 R1，绘制从 P1 到 R1 的有向边。
  • 如果资源 R1 分配给了进程 P2，绘制从 R1 到 P2 的有向边。

在构建完资源分配图，可以通过使用 DFS 检查图中是否存在环路以判断是否存在死锁。

视频讲解