死锁

定义

一组进程处于死锁状态是指: 如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件, 则称一组进程或系统此时发生了死锁.

必要条件

1971 年 Coffman 总结出了系统产生死锁的四个 必要条件:

  1. 互斥条件 (mutual exclusion)

    任一时刻, 一个资源仅能被一个进程独占. 另一个进程请求已被占用的资源时, 它将被设置成等待状态, 直到占用者释放资源.

  2. 占有和等待条件 (hold and wait)

    一个进程因请求资源得不到满足而等待时, 不释放已占有的资源.

  3. 不剥夺条件 (no preemption)

    任一进程不能从另一进程那里抢夺资源.

  4. 循环等待条件 (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

Makefile 生成文件追踪

很多大型开源项目使用 make 来构建, 有时候我们想知道一个文件是怎么被构建出来的, 或者说是从哪些文件构建出来的, 知道这些对于找到程序的入口是很有帮助的. 那么该怎么做呢?

第一反应肯定是直接看 Makefile, 但是大型项目的 Makefile 都很复杂, 各种 include 和变量. 虽然 make 提供 -n-p 选项, 但是因为构建命令里还会调用 make 命令, 当使用 -n 选项时, 这些命令并不会执行, 所以看不到最终执行的所有指令.

那么该怎么办呢? 其实很简单, 直接构建然后从构建输出的日志里来寻找答案, 因为 make 默认会将构建时执行的命令打印出来 (如果使用了 -s 选项或者命令加了 @ 前缀就不会输出).

下面我们以查看 OpenJDK 中 bin/java 是如何构建出来的为例来看下具体的操作:

  1. 首先将项目完整的构建一遍

  2. 将你想要追踪的文件删除, 这里我们将 bin/java 删掉

  3. 重新构建一遍项目同时将输出重定向到一个文件里

    步骤 1 和 2 主要是为了减少构建日志输出的量从而方便搜索

  4. 最后就是从输出日志里搜索相关的信息

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 !

临界区管理

多线程编程中, 互斥 (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 提出的算法利用 bc 这两个保护变量来进行同步.

这个算法存在一个问题, 就是 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;

操作系统教程

经典互斥算法 - 郑思遥

101 - OS

  1. Endianess

    尾: 表示低的地方即低地址位

    大/小: 表示权重

    所以, 大尾: 权重大的字节放在低地址位. 小尾: 权重小的字节放在低地址位.

    Endianness

  2. 分段分页

    分段分页是 处理器 提供的功能.

    逻辑地址 –(分段机制)–> 线性地址 –(分页机制)–> 物理地址

  3. 内存

    内存 (Memory) 不等同于内存条, 内存条只是其中一部分. 内存还包括显存, BIOS 等等.

  4. 端口

    处理器和外设通讯使用 IN/OUT 指令来读写相应的端口.

101 - C/C++

  1. C++ 有两类创建对象的方式: 1). 分配在栈上 2). 分配在堆上

     class Foo: public Bar {
         public:
             Foo() { std::cout << "Empty constructor" << std::endl; }
             Foo(const Foo&) { std::cout << "Copy constructor" << std::endl; }
             Foo(const char* str) { std::cout << "char constructor: " << str << std::endl; }
             ~Foo() { std::cout << "destructor" << std::endl; }
     };
     // 对象分配在在栈上, 当离开该作用域时, 会自动 delete 该对象
     Foo foo; // 调用 Empty constructor
     Foo foo {}; // 同上
     Foo foo = {} // 同上
    
     Foo foo("test"); // 调用带参数的构造方法
     Foo foo {"test"}; // 同上
     Foo foo = {"test"}; //同上
    
     Foo foo(); // 这是个方法声明, 不是创建对象!
    
     // 理论上是先调用了 Empty constructor 然后再调用了 Copy constructor
     // 不过一般编译器都会进行优化, 所以实际上等价于 Foo foo;
     Foo foo = Foo();
     Foo foo = Foo {}; // 同上
    
     Bar bar = Foo {} // 这里编译器不会优化, bar 的实际类型是 Bar 而不是 Foo!
    
    
     // 对象分配在堆上, 需要自己 delete 该对象
     Foo *foo = new Foo();
     Foo *foo = new Foo {}; // 同上
     delete foo;
    

    new/delete 操作的都是 pointer.

    Prefer {} initialization over alternatives unless you have a strong reason not to.

    Calling constructors in c++ without new

    What is difference between instantiating an fooect using new vs. without

    C++ default Constructor not being called

    Why is list initialization (using curly braces) better than the alternatives?

  2. 初始化私有的 static 成员变量:

     // foo.hpp
     class Foo {
         private:
             static int bar;
     };
    
     // foo.cpp
     Foo::bar = 1;
    

    一开始觉得 foo.cpp 访问不到 bar, 觉得应该通过方法初始化, 不过转念一想, 应该和方法一样 define 是不受访问控制影响的.

    static member variable when declared private

  3. 友元声明在 private, protectedpublic 中没有任何区别.

    声明为友元的类或方法可以访问该类的私有成员.

    Friend declaration in C++ - difference between public and private

  4. virtual 相当于 Java 指令里的 invokevirtual.

    不管一个方法是否被声明成 virtual, 它都可以被子类 override.

    当调用一个不是 virtual 的方法时, 调用哪个方法是在编译时就确定的. 相反, virtual 的方法是在运行时决定调用哪个的, 即多态.

     class Foo {
         public:
             void print() { std::cout << "Foo print" << std::endl; }
             virtual void virtualPrint() { std::cout << "Foo virtual print" << std::endl; }
     };
    
     class Bar: public Foo {
         public:
             void print() { std::cout << "Bar print" << std::endl; }
             virtual void virtualPrint() { std::cout << "Bar virtual print" << std::endl; }
     };
    
     Foo *foo = new Bar {};
     foo->print(); // Foo print
     foo->virtualPrint(); // Bar virtual print
    

    C++ Virtual/Pure Virtual Explained

  5. C++ 中没有 super 的关键字, 通过 namespace 调用父类的方法. 主要还是因为 C++ 支持多继承, 用 super 的话会有 MRO 的问题.

    How to call a parent class function from derived class function?

  6. 继承时指定的 private, protectedpublic 就是对继承关系的访问控制.

    Difference between private, public, and protected inheritance

  7. A reference can be thought of as a constant pointer (not to be confused with a pointer to a constant value!) with automatic indirection, i.e. the compiler will apply the * operator for you.

    但是你还是得把它当成一个对象来用.

     Foo& foo = *(new Foo {});
    

    What are the differences between a pointer variable and a reference variable in C++?

make

  1. Makefile 由 rules 组成, 语法如下:

     target ... : prerequisite ... 
     <tab>recipe
     <tab>...
    

    或者

     target ... : prerequisite ... ; recipe
     <tab>recipe
     <tab>...
    

    Rule Syntax

  2. make 默认执行第一个名称开头不是 . 的 target.

    How does “make” app know default target to build if no target is specified?

  3. 同一个 target 可以出现在多个 rule 中, 只要多条 rule 中的 prerequisite 有一个修改时间晚于 target 那么 recipe 就会被执行. 如果有多个 recipe, 那么只有最后出现的那条 rule 的 recipe 会被执行, 同时会抛出 warning.

    但是, 上面说的情况并不是总是成立的:

    target 后面如果接的是 :: 而不是 : 那么这条 rule 被称为 double-colon rule. 如果一个 target 出现在多个 rule 中时这些 rule 必须是相同的类型.

    如果同一个 target 出现在多个 rule 中, 并且这些 rule 是 double-colon rule 时, 这些 rule 是相互独立的, 只要一条 rule 中的 prerequisite 修改时间晚于 target 那么 recipe 就会被执行.

    Multiple Rules for One Target

    Double-Colon Rules

  4. 通常变量赋值使用 =, 这样赋值的变量被称为 recursively expanded variables:

     foo = $(bar)
     bar = $(ugh)
     ugh = Huh?
    
     # 输出 Huh?
     all:;echo $(foo)
    

    GNU make 变量赋值还可以使用 := 或者 ::= (::= 是 POSIX 标准), 这样定义的变量被称为 simply expanded variables:

     x := foo
     y := $(x) bar
     x := later
    

    等价于

     y := foo bar
     x := later
    

    The Two Flavors of Variables

  5. 默认情况下 (不带 -s 选项) make 执行时, 会输出 recipe 执行的命令. 但是如果 recipe 加上 @ 前缀, 那么命令本身就不会被输出, 对于 echo 这种命令很有用.

    Recipe Echoing