Operating System Concepts¶
第二章:操作系统结构¶
2.8 操作系统结构¶
本节介绍了宏、微内核等设计结构,结合具体操作系统的例子。
- 宏内核(monolithic):
- 编写简单,内核内部通信快,性能好。但调试和维护困难。
- 例子:
- 原始 UNIX 是宏内核,扩展后成为层次化的。
- Linux、Windows
- 层次化(layered):
- 在计算机网络中取得成功。
- 但事实上没有操作系统这样设计,因为:
- 难以正确划分层次。
- 层次间调用开销大。
- 微内核:
- 内核仅提供最基本服务,如:IPC、内存管理、CPU 调度。
- 例子:
- Windows NT 第一版为微内核,但比 Windows 95 性能差很多;Windows NT 4.0 将更多用户空间的服务移到内核,性能提高。到 Windows XP,整体架构变得更偏向宏内核。
- 苹果 macOS 和 iOS 的内核 Darwin 是微内核。
- 鸿蒙 OS 是微内核。
- 模块(module)
- 内核支持在启动时或运行时加载内核模块(loadable kernel modules,LKM)。
- 是在现代操作系统上最为常见的一种设计。
事实上现代操作系统都是混合架构的,不会严格遵循某种设计结构。
本节剩余部分介绍了 Darwin 和 Android,旁注甚至还介绍了 WSL 的原理。
-
Darwin:源码在 apple-oss-distributions/xnu,描述如下:
XNU kernel is part of the Darwin operating system for use in macOS and iOS operating systems. XNU is an acronym for X is Not Unix. XNU is a hybrid kernel combining the Mach kernel developed at Carnegie Mellon University with components from FreeBSD and a C++ API for writing drivers called IOKit. XNU runs on x86_64 and ARM64 for both single processor and multi-processor configurations.
2.10 调试操作系统¶
本节主要介绍 BCC/eBPF。
第六章:进程同步工具¶
当共享的数据访问不受控制时,存在竞争条件,可能导致数据不一致。进程同步指的是使用一些工具控制对共享数据的访问,以避免竞争条件。
6.1 背景¶
进程的并发和并行执行使得下面的简单程序都可能产生不同的结果:
6.2 临界区¶
临界区问题:当一个进程进入临界区时,其他进程不能进入。
临界区问题的解需要满足三个条件:
- Mutual exclusion(互斥):如果一个进程在临界区内,其他进程不能进入。
- Progress(进展):如果没有进程在临界区内,等待进入的进程最终能进入。
- Bounded waiting(有界等待):在一个进程请求进入临界区和进入临界区之间,其他进程的进入次数是有限的。
在单核系统上,可以通过禁用中断来解决临界区问题,使得进程在临界区内时不会被抢占。在多核系统上无法这样做的原因有两点:
- 慢。消息需要传到所有核心。
- 如果系统时钟依靠中断,会影响系统时钟。
Peterson 算法¶
Peterson 算法在软件层面解决两个进程的临界区问题。
int turn; // 现在轮到谁进入临界区
boolean flag[2]; // 是否准备好进入临界区
while(true)
{
flag[i] = true; // 我已准备好进入临界区
turn = j; // 先让对方进入临界区
while(flag[j] && turn == j); // 等待对方离开临界区
// 临界区
flag[i] = false;
// 余下部分
}
- 互斥:
- 如果进程进入临界区,那么要么
flag[j] == false
,要么turn == i
。 - 注意到进入临界区时
flag[i] = true
。 - 如果两个进程都进入临界区,则有
flag[0] == flag[1] == true
,那么一定是turn == i && turn == j
,矛盾。
- 如果进程进入临界区,那么要么
- 进展:
- 如果进程在等待,说明
flag[j] == true && turn == j
。 - 如果另一个进程退出临界区,那么
flag[j] = false
,等待的进程可以进入。
- 如果进程在等待,说明
- 有界等待:
- 如果另一个进程重新设置
flag[j] = true
(即再次进入临界区),必定同时设置turn = i
。 - 此时等待的进程在 while 循环中,不会改变
turn
,所以可以进入。 - 证明了在进程请求进入临界区和进入临界区之间,其他进程最多进入一次。
- 如果另一个进程重新设置
6.4 硬件支持同步¶
内存屏障¶
现代计算机体系结构中,内存模型可以分为两类:
- Strongly ordered:一个处理器对内存的修改立刻对其他处理器可见。
- Weakly ordered:一个处理器对内存的修改不立刻对其他处理器可见。
Memory barriers(也称为 fences)是一种硬件指令,用于强制对内存的修改立刻对所有处理器可见。这可以避免指令重排产生的问题。
硬件指令¶
现代计算机指令集提供一些原子指令,比如 test_and_set
、compare_and_swap
。可以用它们方便地解决临界区问题。
TS 锁:
boolean test_and_set(boolean *lock)
{
boolean old = *lock;
*lock = true;
return old;
}
do {
while(test_and_set(&lock)); // 当 lock 为 false 时,将取得锁并进入临界区
// 临界区
lock = false;
// 余下部分
} while(true);
CAS 锁:
int compare_and_swap(int *lock, int old, int new)
{
int temp = *lock;
if(temp == old)
*lock = new;
return temp;
}
while(true)
{
while(compare_and_swap(&lock, 0, 1) != 0); // 当 lock 为 0 时,将取得锁并进入临界区
// 临界区
lock = 0;
// 余下部分
}
上面两段只实现了互斥,没有实现有界等待。下面的算法可以实现有界等待:
// 共享数据
boolean waiting[n]; // n 个进程,初始化为 false
int lock; // 初始化为 0
while(true){
waiting[i] = true; // 我在等待
key = 1;
while(waiting[i] && key == 1)
key = compare_and_swap(&lock, 0, 1); // 尝试取得锁
waiting[i] = false;
// 临界区
j = (i + 1) % n; // 下一个进程
while(j != i && !waiting[j]) // 找到下一个等待的进程
j = (j + 1) % n;
if(j == i)
lock = 0;
else
waiting[j] = false;
}
- 互斥:
- 如果进程进入临界区,那么要么
waiting[j] == false
,要么key == 0
。 - 只有第一个执行 CAS 的进程能够成立
key == 0
。 - 只有其他进程离开临界区时,才可能使
waiting[j] = false
,并且只使一个waiting[j] = false
。
- 如果进程进入临界区,那么要么
- 进展:
- 进程退出临界区时,要么将
waiting[j] = false
,要么将lock = 0
,都能使等待的进程进入。
- 进程退出临界区时,要么将
- 有界等待:
- 进程退出临界区时,按序找到下一个等待的进程。因此每个进程最多等待 \(n-1\) 次。
原子变量¶
大多数支持原子变量的系统提供了原子类型,底层使用 CAS 等实现。例子:
void increment(atomic_int *v)
{
int temp;
do {
temp = *v;
} while(temp != compare_and_swap(v, temp, temp + 1)); // 不断尝试获取锁
}
6.5 互斥锁¶
硬件支持的同步对应用开发者来说太难用。操作系统包装好互斥锁,提供了更高层次的抽象。
互斥锁 mutex
有成员 available
和操作 acquire()
、release()
,这两个操作都是原子的(可以用 CAS 实现)。
上面这种互斥锁称为自旋锁(spin lock),因为它需要忙等(busy waiting)。
实践中,spin lock 最好用在临界区很短的情况下(比相邻两次进程上下文切换的时间短)。
6.6 信号量¶
Semaphore 只能被两种原子操作 wait()
/P()
和 signal()
/V()
修改。前者减少信号量,后者增加信号量。
信号量分为 count 和 binary 两种。
第八章:死锁¶
多个 thread 竞争有限资源。如果一个线程请求的资源不可用,它会进入等待状态。有时它永远无法退出等待,因为资源被其他等待的线程占用,这就是死锁。
定义:死锁
一个进程集合中的每个进程都在等待一个事件,这个事件只能由集合中的其他进程引发。
操作系统一般不提供死锁预防(prevention)机制,要求程序员设计不死锁(deadlock-free)的程序。
本章目标
- 演示使用互斥锁(mutex)时死锁如何发生。
- 定义死锁的四个必要条件。
- 在资源等待图(resource-allocation graph)中识别死锁。
- 评估四种预防死锁(deadlock preventing)的方法。
- 使用银行家(banker's)算法避免死锁(deadlock avoidance)。
- 使用死锁检测(deadlock detection)算法。
- 评估从死锁中恢复(deadlock recovery)的方法。
8.1 系统模型¶
本书只讨论内核中资源的死锁。对于应用程序,死锁的资源可能位于其他进程,涉及进程间通信等。
- 资源(resource)可以按种类划分。每种资源有若干个实例,其中的每一个实例都可以满足对一种资源的请求。
- 进程同步工具(mutex、semaphore 等)也是资源,并且它们是最常见的导致死锁的资源。
- 线程使用资源的步骤:请求(request)、使用(use)、释放(release)。如果请求时无法立即分配,线程必须等待。
- 请求和释放一般都是系统调用,如文件的
open()
和close()
、内存的allocate()
和free()
、信号量的wait()
和signal()
、互斥锁的acquire()
和release()
。
- 请求和释放一般都是系统调用,如文件的
本书考虑的死锁时等待的事件一般是资源的请求和释放。此外死锁可能等待其他时间,比如从网络接口或 IPC 接收数据等。
Example
哲学家就餐问题中,如果所有哲学家都拿起自己右手边的筷子,就进入了死锁状态。每一位哲学家都必须等待另一位哲学家放下筷子。
8.2 多进程应用中的死锁¶
本节通过 Pthread 介绍进程中的死锁。
pthread_mutex_t mutex1, mutex2;
// 初始化为 unlocked
pthread_mutex_init(&mutex1, NULL);
pthread_mutex_init(&mutex2, NULL);
// 线程 1
void *thread1(void *arg)
{
// 该函数将阻塞,直到 mutex 可用
pthread_mutex_lock(&mutex1);
pthread_mutex_lock(&mutex2);
// do something
pthread_mutex_unlock(&mutex2);
pthread_mutex_unlock(&mutex1);
}
// 线程 2
void *thread2(void *arg)
{
pthread_mutex_lock(&mutex2);
pthread_mutex_lock(&mutex1);
// do something
pthread_mutex_unlock(&mutex1);
pthread_mutex_unlock(&mutex2);
}
死锁究竟会不会发生,还取决于线程调度器的行为。
定义:活锁(livelock)
活锁与死锁都意味着进程无法继续执行,但不同在于:活锁不是进程因为等待而无法继续执行,而是进程不断重复相同的操作但始终失败。
活锁通常可以通过让进程延迟随机的时间再次尝试来避免。在以太网中,碰撞检测就是通过随机时延避免活锁的。
Example
两个人在走廊中相遇,一人总是向右让,另一人总是向左让,两人始终无法通过。
pthread_mutex_trylock()
可以非阻塞地尝试获取锁,可以演示活锁的发生:
8.3 死锁特征¶
死锁的必要条件
如果下面四个条件在系统中同时成立,那么死锁可能发生:
- 互斥(mutual exclusion):至少有一个资源以非共享方式使用。
- 占有并等待(hold and wait):一个进程持有一个资源,并且希望获取正在被其他进程持有的资源。
- 无抢占(no preemption):资源只能在进程使用完后才能释放,不允许抢占。
- 循环等待(circular wait):存在一个进程等待链,每个进程都在等待下一个进程持有的资源。\(\{T_0, T_1, \ldots, T_n\}\)。
- 这隐含了占有并等待。
资源分配图(resource-allocation graph)
- 顶点 \(V\)分为两类:线程 \(T\) 用圆形表示,资源 \(R\) 用方形表示。如果资源有多个实例,用方形中的点表示。
- 边 \(E\) 也有两类:
- 请求边(request edge) \(T_i \rightarrow R_j\)
- 分配边(assignment edge) \(R_j \rightarrow T_i\)
使用资源的三个步骤对应图中的三个操作:建立请求边,请求边变为分配边,删除分配边。
识别 RAG 中的死锁
- 如果每个资源都只有一个实例,则分配图中的环表明死锁发生。这种情况既是充分(sufficient)也是必要(necessary)条件。
- 如果资源有多个实例,那么环是必要条件,但不是充分条件。
- 总之:环是死锁的必要条件。
8.4 处理死锁的方法¶
概括地说有三种:
- 假装死锁永远不会发生。
-
使用协议(protocol)预防死锁,保证系统永远不会进入死锁状态。
Tip
还记得数据库系统课上的两阶段锁协议吗?
-
允许系统进入死锁状态。检测(detect)并恢复(recover)。
第一种方法被大多数操作系统使用(包括 Linux 和 Windows)。第二种方法被内核和程序开发者使用。第三种方法在数据库系统中使用。
为了保证死锁永远不会发生:
- 死锁预防(deadlock prevention)破坏死锁的四个必要条件中的至少一个。一般通过限制对资源的请求实现。
- 死锁避免(deadlock avoidance)向操作系统提供额外的信息,即线程在生命周期中将要请求的资源及其数量。操作系统根据这些信息决定线程是否需要等待。操作系统需要为每个线程考虑:当前分配(allocated)的资源、未来的请求(request)和释放(release)。
8.5 死锁预防¶
从死锁的四个条件入手:
- 互斥:该条件必须成立,因为非共享资源本来就没法在多个进程间共享。
-
占有并等待:保证当线程请求资源时,不持有其他资源。
- 一种协议:线程在开始执行前请求并分配得到所有资源。然而对大部分应用来说不可行,它们都需要动态分配资源。
- 另一种协议:线程在请求资源时释放已经持有的资源。
两种协议都会导致资源利用率降低,且可能产生饥饿,因为等待较多资源的线程可能永远无法满足。
-
无抢占:
- 一种协议:当线程持有资源,并且要请求其他不能被立即分配的资源(必须等待)时,它自己持有的资源应当可以被抢占(可以理解为隐式地释放了)。当资源被抢占后,应当加入其请求的资源队列。
- 另一种协议:
- 首先检查线程请求的资源是否可用,可用就分配。
- 不可用,则检查是否被分配到其他在等待更多资源的线程。如果是,就从等待的线程抢占资源。
- 如果没有,就让线程等待。此时它的资源可以被抢占。
这些协议往往用在容易保存和恢复状态的资源,比如 CPU 寄存器和数据库事务。
-
循环等待:四个条件中最能实践的一种条件。
主要思想是线性化资源,即给资源编号。考虑函数 \(F: R \rightarrow N\):
- 一种协议:线程只能按编号递增的顺序请求资源 \(F(R_j) > F(R_i)\)。
- 另一种协议:要求线程在请求资源 \(R_i\) 时,必须释放编号更大的资源 \(F(R_j) \geq F(R_i)\)。
编号是针对资源的类别。对于同种资源,必须用一个请求请求所有实例。
利用反证法可以证明使用这种协议可以避免循环等待。
证明
- 假设发生了循环等待,其中 \(T_i\) 等待资源 \(R_i\),被 \(T_{i+1}\) 持有。
- 因为 \(T_{i+1}\) 持有 \(R_i\) 并且在等待 \(R_{i+1}\),所以 \(F(R_{i+1}) > F(R_i)\)。
- 依此类推,得到 \(F(R_0) < F(R_1) < \ldots < F(R_n) < F(R_0)\),矛盾。
Warning
编程时有几个难点:
- 资源数量非常多时,难以建立编号并保证按顺序请求。
- 资源动态分配时,编号可能会变化。
下面的代码就会产生死锁:
// 两个线程 transaction(checking account, savings account, 25.0); transaction(savings account, checking account, 50.0); void transaction(Account from, Account to, double amount) { mutex lock1, lock2; lock1 = get lock(from); lock2 = get lock(to); acquire(lock1); acquire(lock2); withdraw(from, amount); deposit(to, amount); release(lock2); release(lock1); }
8.6 死锁避免¶
Info
在 Linux 中可以使用 lockdep
调试、检测死锁。
- 安全状态(safe state):如果系统可以按某种顺序分配资源,同时保证不会进入死锁状态,那么系统处于安全状态。
- 安全状态意味着死锁一定不会发生。不安全状态意味着死锁可能发生,但不一定会发生。
- 序列写为 \(<T_1, T_2, \ldots, T_n>\)。对于每个 \(T_i\),有两种意思:前面的线程的资源已经满足后,仍然能满足 \(T_i\) 的资源请求(就是 \(T_i\) 不需要等待);前面的线程的资源已经满足后执行完毕,释放资源后,然后可以满足 \(T_i\) 的资源请求(就是 \(T_i\) 需要等待)。
- 死锁避免算法就是要保证系统始终处于安全状态。
资源分配图算法¶
适用于每种资源只有一个实例的情况。
向资源分配图中添加一种边:需求边(request edge) \(T_i \rightarrow R_j\),为虚线。表示线程 \(T_i\) 对 \(R_j\) 有需求,但尚未请求。
- 当线程请求资源时,将需求边变为请求边。
- 当线程释放资源时,将请求边变为需求边。
在线程开始执行时,就必须告知操作系统所有需求,在图中绘制所有需求边。
资源分配图算法
当线程请求资源(将需求边 \(T_i \rightarrow R_j\) 变为请求边)时,使用环检测算法(\(n^2\))检查:将该请求边转换为分配边 \(R_j \rightarrow T_i\) 时是否会导致环。
如果会,那么就会让系统进入不安全状态,需要让线程等待。否则,就可以分配资源。
银行家算法¶
适用于每种资源有多个实例的情况。
设 \(n\) 为线程数,\(m\) 为资源种类数。需要维护下列数据结构:
- 可用向量 \(Avail\):表示系统中每种资源的可用数量。
- 最大需求矩阵 \(Max\):\(n \times m\),表示每个线程对每种资源的最大需求。
- 分配矩阵 \(Alloc\):\(n \times m\),表示每个线程已经分配的资源。其中的每一列表示该进程已经分配各类资源的数量。
- 需求矩阵 \(Need\):\(n \times m\),表示每个线程还需要的资源。每一列表示该进程还需要各类资源的数量。
算法如下:
- 安全算法:检查系统是否处于安全状态。复杂度 \(O(n^2 \times m)\)。
- 令 \(Work = Avail\),\(Finish[i] = false\) 表示进程是否结束。
- 找到一个进程 \(i\),满足 \(Finish[i] = false\) 且 \(Need_i \leq Work\)。即寻找尚未结束的进程,且它的需求小于等于当前可用资源。如果找不到,转到步骤 4。
- \(Work = Work + Alloc_i\),\(Finish[i] = true\)。即为该进程分配资源,并等待进程结束。转到步骤 2。
- 如果所有进程都结束,那么系统处于安全状态。否则,系统处于不安全状态。
Note
一句话总结安全算法:遍历所有进程,寻找可行的资源分配序列。
- 资源分配算法:决定资源能否被安全地分配。
- 令 \(Request_i\) 为线程 \(i\) 对资源的请求。若 \(Request_i \leq Need_i\),进入下一步,否则报错,请求超过最大需求。
- 若 \(Request_i \leq Avail\),进入下一步,否则线程 \(i\) 必须等待。
- 假设系统分配资源给线程 \(i\),即 \(Avail = Avail - Request_i\),\(Alloc_i = Alloc_i + Request_i\),\(Need_i = Need_i - Request_i\)。然后运行安全算法。
Note
一句话总结资源分配算法:试探性地分配资源,然后运行安全算法。
8.7 死锁检测¶
做题笔记¶
- 至少要多少资源才能保证死锁不发生?见 [Solved] What is the minimum number of resources required to ensure t。思路是首先让所有进程都持有一个资源,然后计算每个进程需要的资源(即 \(max - 1\))。只要比所有进程的 \(max - 1\) 求和再多一个资源,就有让死锁不发生的空间。