第八章：并发 | orange’s blog

type

status

date

slug

summary

概念

同步互斥

多个线程想要访问同一个变量，当某个线程想要修改一个变量的值，但是其他线程想要读取这个变量的值时，由于线程之间的执行顺序不能提前预知（取决于操作系统的调度），导致各个线程对同一变量的读写操作序列不确定，这就会导致不同线程可能会看到与预期结果不一样的值，这就出现了数据不一致性的问题，而且每次执行的结果不确定。

我们把这种两个或多个线程在竞争访问同一资源时，执行结果取决于它们的不可预知的执行顺序的情况称为 线程的竞态条件（race condition）

互斥锁

互斥锁能够确保在任何时候只有一个线程访问共享资源，从而避免资源竞争导致的数据不一致的问题。可以使用Rust标准库中的 std::sync::Mutex 类型来实现互斥锁。

在获取互斥锁的时候，线程会被挂起，直到另一个线程释放了锁

条件变量

条件变量是操作系统中的一种同步原语，可用于在多个线程之间进行协作，即允许一个线程在另一个线程完成某些操作之前等待。条件变量与互斥锁经常一起使用，以保证在同一时刻只有一个线程在访问共享资源。

信号量

它通常是一个整数值，用于计数指定数量的资源可用。当一个线程需要使用资源时，它会执行信号量的 acquire 操作，如果信号量的值小于等于零，则线程将被挂起，（直到信号量的值变为正数，则会被唤醒）；否则将信号量的值减一，操作正常返回。另一方面，当一个线程完成使用资源后，它可以执行信号量的 release 操作，将信号量的值加一，并唤醒一个或所有挂起的线程。

Rust 标准库中没有信号量类型，但我们可以用Mutex和Condvar来构造信号量类型：

用户态的线程管理

用户态多线程应用

使用spawn创建一个线程

使用run执行线程

多线程的基本执行环境

线程是在用户态被创建和调度的，因此操作系统内核并不需要知道线程的存在。线程需要被一个东西来管理，当一个线程交出CPU使用权时，另一个线程才能被调度和执行。

为了实现用户态的协作式线程管理，我们首先需要考虑这样的线程大致的结构应该是什么？在上一节的线程的基本定义中，已经给出了具体的答案：

线程ID

执行状态

当前指令指针(PC)

通用寄存器集合

线程管理运行时初始化

延用之前进程的管理方式：

Runtime::new() 主要有三个步骤：

初始化应用主线程控制块（其TID为 0 ），并设置其状态为 Running 状态；
初始化 tasks 线程控制块向量，加入应用主线程控制块和空闲线程控制块，为后续的线程创建做好准备；
包含 tasks 线程控制块向量和 current 当前线程id（初始值为0，表示当前正在运行的线程是应用主线程），来建立 Runtime 变量；

Runtime::init() ，把线程管理运行时的 Runtime 自身的地址指针赋值给全局可变变量 RUNTIME

线程创建

当应用要创建一个线程时，会调用 runtime.spawn 函数

线程切换

通过 runtime.t_yield 函数来完成具体的切换过程。runtime.t_yield 这个函数主要完成的功能是：

第4~12行，在线程向量中查找一个状态为 Ready 的线程控制块；

第14~20行，把当前运行的线程的状态改为 Ready ，把新就绪线程的状态改为 Running ，把 runtime 的 current 设置为这个新线程控制块的id；

第23行，调用汇编代码写的函数 switch ，完成两个线程的栈和上下文的切换；

内核态的线程管理

系统调用函数

实验实现的线程模型：

只有三个状态：就绪态、运行态和等待态

共享所属进程的地址空间及资源

可调度，分时占用CPU执行

我们实现的线程模型建立在进程的地址空间抽象之上：每个线程都共享进程的代码段和和可共享的地址空间（如全局数据段、堆等），但有自己的独占的栈

线程创建系统调用：

进程会为新创建的线程分配独立的栈

由于用户态进程与内核之间有各自独立的页表，所以二者需要有一个跳板页 TRAMPOLINE 来处理用户态切换到内核态的地址空间平滑转换的事务

相比于创建进程的 fork 系统调用，创建线程不需要要建立新的地址空间，这是二者之间最大的不同

等待子线程系统调用：

主进程需要调用这个函数来回收线程占用的内核态的资源

一般来说子线程调用exit后就会退出，此时还没被回收干净的资源就需要主进程调用sys_waittid来回收

应用程序示例

线程管理的核心数据结构

线程控制块

tid：线程标识符

ustack_base：线程的栈顶地址

process：线程所属的进程

包含线程的进程控制块

线程管理机制的设计与实现

当一个进程执行中发出了创建线程的系统调用 sys_thread_create 后，操作系统就需要在当前进程的基础上创建一个线程

当一个非主线程的其他线程发出 sys_exit 系统调用时，内核会调用exit_current_and_run_next函数退出当前线程并切换到下一个线程，但不会导致其所属进程的退出

主线程通过系统调用 sys_waittid 来等待其他线程的结束

锁机制

对临界区的访问过程分为四个部分：

尝试取锁: 查看锁是否可用，即临界区是否可访问（看占用临界区标志是否被设置），如果可以访问，则设置占用临界区标志（锁不可用）并转到步骤 2 ，否则线程忙等或被阻塞;

临界区: 访问临界资源的系列操作

释放锁: 清除占用临界区标志（锁可用），如果有线程被阻塞，会唤醒阻塞线程；

剩余区: 与临界区不相关部分的代码

可以看到，如果临界区不可访问，那么可能会触发两种锁：忙等锁和睡眠锁

内核态操作系统级方法实现锁 — mutex 系统调用

使用 mutex 系统调用

mutex 系统调用的实现

ProcessControlBlockInner 里面存有一个互斥资源的向量列表

MutexBlockingInner 里面存有一个在这个锁上等待的线程的列表

互斥锁MutexBlockingInner：

locked表示锁现在不可获取（临界区不可访问）

wait_queue表示锁上挂起的线程

pub fn sys_mutex_create(blocking: bool) -> isize

在进程Inner里的mutex_list里面找一个未被占用的id，就在mutex_list的id处创建锁

如果没有空余id，就新增一个id，将锁push进mutex_list

pub fn sys_mutex_lock(mutex_id: usize) -> isize

调用 ID 为 mutex_id 的互斥锁 mutex 的 lock 方法

fn lock(&self)

主要用于锁上这个互斥锁

如果这个互斥锁已经在别的线程被获取，那么把当前线程放入等待队列

如果这个互斥锁没有被获取，那么当前线程获取互斥锁，互斥锁locked变为true

unlock也类似

信号量机制

伪代码思路

S表示可以访问临界区的线程数

当S为负数时，表示等待进入临界区的睡眠线程数

具体实现，数据结构

进程控制块Inner新增属性semaphore_list，表示进程中的信号量列表

信号量的数据结构SemaphoreInner主要有两个属性

一个表示信号量值（这个资源的剩余量）
一个表示在这个信号量上等待的线程

相当于之前的acquire和release

条件变量机制

实现线程需要检查某一条件（condition）满足之后，才会继续执行

死锁：

想要达成的目的：线程2在A==0时睡眠，直到线程1使得A=1后再继续执行

但实际上，如果线程2先执行，那么就会获取A的锁，然后它又一直睡眠，就会导致A永远不可能为1，导致死锁

这里需要解决的两个关键问题： 如何等待一个条件？ 和 在条件为真时如何向等待线程发出信号 。我们的计算机科学家给出了 管程（Monitor） 和 条件变量（Condition Variables） 这种巧妙的方法

条件变量的基本思路

管程：任一时刻只能有一个活跃线程调用管程中的过程，这一特性使线程在调用执行管程中过程时能保证互斥，这样线程就可以放心地访问共享变量

线程间的沟通机制：

等待机制：线程想调用管程中的过程，由于有条件不满足，开始等待
唤醒机制：另外一个线程可以在调用管程的过程中，把某个条件设置为真

解决思路：

Hoare 语义：线程发出唤醒操作后，马上阻塞自己，让新被唤醒的线程运行。注：此时唤醒线程的执行位置还在管程中。
Hansen 语义：是执行唤醒操作的线程必须立即退出管程，即唤醒操作只可能作为一个管程过程的最后一条语句。注：此时唤醒线程的执行位置离开了管程。
Mesa 语义：唤醒线程在发出行唤醒操作后继续运行，并且只有它退出管程之后，才允许等待的线程开始运行。注：此时唤醒线程的执行位置还在管程中。

下面介绍一个基于 Mesa 语义的沟通机制。这种沟通机制的具体实现就是 条件变量 和对应的操作：wait 和 signal

wait：条件变量其实是一个线程等待队列，当条件不满足时，线程通过执行条件变量的 wait 操作就可以把自己加入到等待队列中，睡眠等待（waiting）该条件

signal：另外某个线程，当它改变条件为真后，就可以通过条件变量的 signal 操作来唤醒一个或者多个等待的线程（通过在该条件上发信号），让它们继续执行

实现条件变量

主线程先创建了初值为 0 的互斥锁和一个条件变量，再创建了两个线程

线程 First 会先睡眠 10ms，而当线程 Second 执行时，会由于条件不满足执行条件变量的 wait 操作而等待睡眠

当线程 First 醒来后，通过设置 A 为 1，让线程 second 等待的条件满足，然后会执行条件变量的 signal 操作

实现 condvar 系统调用

要是条件还是不满足，线程将继续执行condvar_wait，直到下一次signal被调用，再判断条件是否满足了