29 Jul 2017
定义
一组进程处于死锁状态是指: 如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件,
则称一组进程或系统此时发生了死锁.
必要条件
1971 年 Coffman 总结出了系统产生死锁的四个 必要条件:
-
互斥条件 (mutual exclusion)
任一时刻, 一个资源仅能被一个进程独占. 另一个进程请求已被占用的资源时,
它将被设置成等待状态, 直到占用者释放资源.
-
占有和等待条件 (hold and wait)
一个进程因请求资源得不到满足而等待时, 不释放已占有的资源.
-
不剥夺条件 (no preemption)
任一进程不能从另一进程那里抢夺资源.
-
循环等待条件 (circular wait)
存在一个循环等待链.
注意了, 这里是死锁产生的必要条件, 不是充分条件.
也就是说当这四个条件满足时, 并不是说系统此时一定发生死锁了,
但是当系统发生死锁时, 这四个条件一定是满足的.
解决
可以从三个方面来解决死锁问题，它们是 死锁防止 (deadlock prevention);
死锁避免 (deadlock avoidance); 死锁检测和恢复 (deadlock detection and recovery).
比较难区分的是死锁防止和死锁避免, 我的理解是, 死锁防止是 客观 上防止四个必要条件满足,
死锁避免是 主观 上避免四个必要条件满足.
如果我们把死锁比喻成在高速公路上开车撞到障碍物导致死亡,
那么死锁防止等同于政府派环卫工人去清理障碍物; 死锁避免是驾驶员通过驾驶技巧来规避障碍物;
死锁检测与恢复是撞倒障碍物之后通过安全气囊防止死亡.
死锁防止
层次化分配是一种有效的死锁防止策略. 简单来说就是将资源排序, 请求资源时只能按照顺序请求.
这样就破坏了四个必要条件中的循环等待条件.
以银行转账为例, 我们可以让程序必须按照用户 ID 大小顺序来锁定账户. (呃, 这个好像是主观避免了)
死锁避免
银行家算法是最有名的死锁避免算法, 但是因为算法要求进程提前知道自己所需的最大资源数量,
这就导致该算法并不具有多大的实际价值. 算法并不复杂, 直接上代码:
import numpy as np
n_processes = int(input('Number of processes? '))
n_resources = int(input('Number of resources? '))
available_resources = [int(x) for x in input('Claim vector? ').split(' ')]
currently_allocated = np.array([[int(x) for x in input('Currently allocated for process ' + str(i + 1) + '? ').split(' ')] for i in range(n_processes)])
max_demand = np.array([[int(x) for x in input('Maximum demand from process ' + str(i + 1) + '? ').split(' ')] for i in range(n_processes)])
total_available = available_resources - np.sum(currently_allocated, axis=0)
running = np.ones(n_processes) # An array with n_processes 1's to indicate if process is yet to run
while np.count_nonzero(running) > 0:
at_least_one_allocated = False
for p in range(n_processes):
if running[p]:
if all(i >= 0 for i in total_available - (max_demand[p] - currently_allocated[p])):
at_least_one_allocated = True
print(str(p) + ' is running')
running[p] = 0
total_available += currently_allocated[p]
if not at_least_one_allocated:
print('Unsafe')
exit()
print('Safe')
死锁检测和恢复
这是一种比较有实际意义的解决方案, 当检测到系统发生死锁了,
可以强制破坏上述四个必要条件, 比如, 让优先级低的进程释放已占用的资源.
总结
总而言之, 解决死锁就从四个必要条件出发.
操作系统教程
Banker’s algorithm
14 Jun 2017
很多大型开源项目使用 make 来构建, 有时候我们想知道一个文件是怎么被构建出来的, 或者说是从哪些文件构建出来的,
知道这些对于找到程序的入口是很有帮助的. 那么该怎么做呢?
第一反应肯定是直接看 Makefile, 但是大型项目的 Makefile 都很复杂, 各种 include 和变量.
虽然 make 提供 -n 和 -p 选项, 但是因为构建命令里还会调用 make 命令,
当使用 -n 选项时, 这些命令并不会执行, 所以看不到最终执行的所有指令.
那么该怎么办呢? 其实很简单, 直接构建然后从构建输出的日志里来寻找答案,
因为 make 默认会将构建时执行的命令打印出来 (如果使用了 -s 选项或者命令加了 @ 前缀就不会输出).
下面我们以查看 OpenJDK 中 bin/java 是如何构建出来的为例来看下具体的操作:
-
首先将项目完整的构建一遍
-
将你想要追踪的文件删除, 这里我们将 bin/java 删掉
-
重新构建一遍项目同时将输出重定向到一个文件里
步骤 1 和 2 主要是为了减少构建日志输出的量从而方便搜索
-
最后就是从输出日志里搜索相关的信息
以 bin/java 为例, 我们在构建日志里搜索 bin/java, 找到如下日志:
/Applications/Xcode.app/Contents/Developer/usr/bin/llvm-gcc -o /Users/yoncise/Downloads/openjdk/build/macosx-x86_64/bin/java -m64 -Xlinker -rpath -Xlinker @loader_path/. -Xlinker -install_name -Xlinker @rpath/java -L/Users/yoncise/Downloads/openjdk/build/macosx-x86_64/lib -Wl,-all_load /Users/yoncise/Downloads/openjdk/build/macosx-x86_64/tmp/java/jli/obj64/static/libjli.a -framework Cocoa -framework Security -framework ApplicationServices -sectcreate __TEXT __info_plist ../../../../src/macosx/lib/Info-cmdline.plist \
/Users/yoncise/Downloads/openjdk/build/macosx-x86_64/tmp/java/java/obj64/main.o -pthread -lz -pthread
我们可以发现 bin/java 的构建依赖 /Users/yoncise/Downloads/openjdk/build/macosx-x86_64/tmp/java/java/obj64/main.o.
根据目录我们可以知道, 这个文件是第一次完整构建的时候生成的并不是程序的源码, 删掉它, 再重复上面的步骤构建一遍.
再一次构建完成后, 我们在构建日志里搜索 obj64/main.o 可以找到如下日志:
/Applications/Xcode.app/Contents/Developer/usr/bin/llvm-gcc -Os -fno-strict-aliasing -fPIC -W -Wall -Wno-unused -Wno-parentheses -pipe -m64 -fno-omit-frame-pointer -D_LITTLE_ENDIAN -F/System/Library/Frameworks/JavaVM.framework/Frameworks -F/System/Library/Frameworks/ApplicationServices.framework/Frameworks -I/usr/X11R6/include -D_DARWIN_UNLIMITED_SELECT -DNDEBUG -DARCH='"x86_64"' -Dx86_64 -D_ALLBSD_SOURCE -DRELEASE='"1.7.0-internal"' -DFULL_VERSION='"1.7.0-internal-yoncise_2017_06_13_23_02-b00"' -DJDK_MAJOR_VERSION='"1"' -DJDK_MINOR_VERSION='"7"' -D_LARGEFILE64_SOURCE -D_GNU_SOURCE -D_REENTRANT -DMACOSX -D_LP64=1 -I/usr/X11R6/include -D_DARWIN_UNLIMITED_SELECT -I. -I/Users/yoncise/Downloads/openjdk/build/macosx-x86_64/tmp/java/java/CClassHeaders -I../../../../src/macosx/javavm/export -I../../../../src/share/javavm/export -I../../../../src/share/bin -I../../../../src/macosx/bin -I../../../../src/solaris/bin -DPACKAGE_PATH='"/opt/local"' -DPROGNAME='"java"' -DEXPAND_CLASSPATH_WILDCARDS -DLAUNCHER_NAME='"openjdk"' -c -o /Users/yoncise/Downloads/openjdk/build/macosx-x86_64/tmp/java/java/obj64/main.o \
-DRELEASE='"1.7.0-internal"' -DFULL_VERSION='"1.7.0-internal-yoncise_2017_06_13_23_02-b00"' -DJDK_MAJOR_VERSION='"1"' -DJDK_MINOR_VERSION='"7"' ../../../../src/share/bin/main.c
至此, 我们发现 bin/java 的入口文件是 src/share/bin/main.c !
02 Jun 2017
多线程编程中, 互斥 (mutual exclusion, a.k.a. mutex) 是一个很重要的概念.
而互斥的本质就是对于临界区 (critical section) 的管理.
以前一直以为, 要实现互斥必须需要 CPU 提供相关的原语指令 (比如 Test and Set 指令) 才行.
现在发现原来有很多算法可以实现互斥.
软件方案
互斥这一问题最早是由 Dijkstra 在 1965 年提出的,
要求一个算法使得 N 台计算机在任意时刻, 有且只有一台计算机在执行临界区的代码.
N 台电脑之间通过一块共享的存储区域传递消息, 对于共享区域的读或者写是原子操作.
如果一个变量会被多个线程读写的话, 我们称之为 公共变量 (Public).
如果一个变量会被多个线程读但只会被一个线程写的话, 我们称之为 保护变量 (Protected).
如果一个变量只会被一个线程读写的话, 我们称之为 私有变量 (Private).
保护变量被多个线程读取并在一定条件下使用是没有问题的.
我们会发现, 下面提到的互斥算法从本质上来讲都是 通过使用保护变量来对公共变量的读写进行同步.
我们来看一个具体的 Java 的多线程问题: N 个线程对一个变量加 M 次 1,
如何不用任何现成的锁机制使得最后这个变量的值为 N * M.
public class MutualExclusion {
static final int N = 10;
static final int M = 10000;
volatile static int count = 0;
public static void main(String[] args) {
Thread[] threads = new Thread[N];
for (int i = 0; i < N; i++) {
Thread t = new Worker(i);
threads[i] = t;
t.start();
}
for (Thread t: threads) {
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
if (count != N * M) {
System.out.println("count (" + count + ") != N * M (" + String.valueOf(N * M) + ")");
}
}
static class Worker extends Thread {
int id;
Worker(int id) {
this.id = id;
}
@Override
public void run() {
for (int i = 0; i < M; i++) {
this.lock();
// critical section
count++;
if (i % 1000 == 0) {
System.out.println(this.getName() + ": " + count);
}
this.unlock();
}
}
void lock() {
// TODO
}
void unlock() {
// TODO
}
}
}
Dijkstra 提出的算法
这个算法是 Dijkstra 在提出互斥问题的那篇论文里给出的:
static AtomicIntegerArray b = new AtomicIntegerArray(N);
static AtomicIntegerArray c = new AtomicIntegerArray(N);
volatile static int k = 0;
void lock() {
b.set(this.id, 0);
outer:
for (;;) {
if (k == this.id) {
c.set(this.id, 0);
for (int i = 0; i < N; i++) {
if (i != this.id && c.get(i) == 0) {
continue outer;
}
}
break;
} else {
c.set(this.id, 1);
if (b.get(k) == 1) {
k = this.id;
}
}
}
}
void unlock() {
b.set(this.id, 1);
c.set(this.id, 1);
}
为了防止因为 JMM 中的 cache 影响程序的正常运行, 所以这里使用 AtomicIntegerArray 替代 boolean[].
这里的 k 是公共变量, Dijkstra 提出的算法利用 b 和 c 这两个保护变量来进行同步.
这个算法存在一个问题, 就是 k == this.id 的线程可能会一直获得执行权, 从而导致其它线程一直等待.
后来 Knuth 等人针对这个问题对算法进行了改进, 感兴趣的可以找相关文献看看.
Perterson 算法
这个算法是解决两线程的互斥算法, 结构非常简单, 这里就直接把 Peterseon 原文里的代码摘抄过来:
/* trying protocol for P1 */
Q1 := true;
TURN := 1;
wait until not Q2 or TURN = 2;
Critical Section;
/* exit protocol for P1 */
Q1 := false.
/* trying protocol for P2 */
Q2 := true;
TURN := 2;
wait until not Q1 or TURN = 1;
Critical Section;
/* exit protocol for P2 */
Q2 := false.
Filter 算法
Peterson 在同一篇论文里把互斥算法扩展到支持 N 个线程, 这个算法又被称作 Filter 算法.
static AtomicIntegerArray level = new AtomicIntegerArray(N);
static AtomicIntegerArray lastToEnter = new AtomicIntegerArray(N - 1);
void lock() {
for (int i = 0; i < (N - 1); i++) {
level.set(this.id, i);
lastToEnter.set(i, this.id);
outer:
while (lastToEnter.get(i) == this.id) {
for (int k = 0; k < N; k++ ) {
if (k != this.id && level.get(k) >= i) {
continue outer;
}
}
break;
}
}
}
void unlock() {
level.set(this.id, -1);
}
算法中, 每个线程都有个 level, 线程需要一级一级的升级, 直到 level 达到 N
(算法中并没有真的达到 N, 但相当于升级到 N) 才获得执行权限.
在每个 level 中应用 Peterson 算法确保会有一个线程维持在该等级.
P.S. 互斥算法不仅仅上面介绍的这几种, 还有很多,
比如 Dekker 算法和面包店算法, 感兴趣的就自己查阅资料吧, 本质都差不多的.
硬件方案
解决互斥问题的关键就是对公共变量的读写进行同步, 如果硬件上能保证对一个公共变量的读写是同步的就可以解决互斥问题.
下面简单介绍几种常见的方案.
关中断
实现互斥最简单的办法就是关中断. 但是这样会导致系统的性能严重下降,
对于多 CPU 的系统关中断也不能解决问题.
Test and Set 指令
硬件提供的 TS 指令可以看做是一个函数(函数的执行不会被打断):
int TS(int* locked) {
if (*locked == 0) {
*locked = 1;
return 1;
}
return 0;
}
有了 TS 指令, 可以很容易对临界区进行管理:
while (TS(locked) == 0) {
// wait
}
// critical section
*locked = 1
对换 (Swap) 指令
和 TS 指令类似, Swap 也可以看作是一个函数:
void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
进程可以这样使用 Swap 指令:
int pi = 1; // 私有变量
while (pi == 1) {
swap(locked, &pi);
}
// critical section
*locked = 0;
操作系统教程
经典互斥算法 - 郑思遥