操作系统并发

Terms

• Critical section: piece of code that accesses a shared resource.
• Race condition: 多个线程同时进去 critical section。
• Indeterminate：指程序在多线程情况下，程序结果不唯一。
• Mutual exclusion：排他。

Locks

Evaluating Locks

• Mutual exclusion
• Fairness 当大量线程同时访问时，是否存在某些 thread starve 的可能。
• Performance

Controlling Interrupts

就是 lock 的时候直接关闭系统中断，但是这样很危险，而且不靠谱。因为一旦关闭中断，操作系统也无法获得操作权利。

而且不支持多核处理器。

所以这种方法只有在某些地方用用了。

Simple Spin Lock

这种 lock 方式由两个问题：

correctness：不正确

performance：spin wait 的方式会消耗大量的 CPU 时间片。

Spin Lock with Test-And-Set

硬件层面提供了如下原子操作：

Spin Lock With Compare-And-Swap

和 Test-And-Set 差不多，Java 里面的 CAS 就是 Compare-And-Swap。

Fetch-And-Add

有些硬件提供这种 premitive。

可以基于这个，开发一个 ticket lock。ticket lock 的好处就是维持了 fairness，保证每个 thread 一定能够被执行到，不会被 starve。

解决 spin lock 性能低下

解决办法很简单，就是要开始自旋的时候，放弃 CPU，进入 sleep 状态。然后把 thread id 放一个队列里面。当别的 thread 执行完成后，唤醒队列中的一个 thread。

除此之外，spin lock 还有一个缺点：priority inversion 。假设两个 thread，分别为 T1 和 T2。T2 的 priority 大于 T1。然后一开始，T2先运行，因为它优先级高。然后因为某种 IO 操作，blocked。此时操作系统让 T1 开始运行，然后 T1 hold 一个 T2 将来要用的 lock。然后 T2 IO 操作完毕，开始执行，操作系统将 T1 sleep 了，然而此时 T1 的 lock 并没有释放，结果使得 T2 卡在那里，等着 T1 的 lock，然而 T1 已经 sleep，永远不会释放 lock。

Two-Phase Locks

spin lock 也不是一无是处，因为如果你知道某些锁很快就会被释放，推荐就使用 spin lock，这样性能更高，

Two-phase lock 就是一开始先自旋一会，然后如果还是得不到 lock，就会采用 second plan，睡觉。

Condition Variables

wait() thread 希望 sleep。signal() 通知唤醒。

说明几点：

• 为什么要用变量 done：当假设没有 done 变量时，child 线程直接开始执行（在 thr_join() 之前），并且执行了 thr_exit() ，当他尝试 signal 线程时，因为没有线程 sleep，所以直接跳过。而此时 thr_join() 开始执行，然后睡着了，然而永远不会有线程去 signal 它了。
• 为什么要用 mutex 锁：假设没有了 mutex，此时先执行了 thr_join()，到 20 行，还没有开始 wait。此时 OS 调度子线程，直接执行完成了 thr_exit()。然后切换回 parent thread 执行后面的 wait，与上面一样，永远不会被唤醒了。

下面是基于 Java 的生产者消费者模型。

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Study {

    private static Lock lock = new ReentrantLock();
    static Condition empty = lock.newCondition();
    static Condition fill = lock.newCondition();

    private static int count = 0;
    private static int buf = 0;

    public static void main(String[] args) {
        Thread p = new Thread(new Producer());
        p.start();
        for (int i=0; i<10; i++) {
            new Thread(new Consumer()).start();
        }

        try {
            Thread.sleep(5000);
        } catch (InterruptedException e) {}
    }

    private static class Consumer implements Runnable {
        @Override
        public void run() {
            for (int i=0; i<10; i++) {
                lock.lock();
                while (count == 0) {
                    try {
                        empty.await();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                System.out.println(Thread.currentThread().getName() + ":" + buf);
                count = 0;
                fill.signal();
                lock.unlock();
            }
        }
    }

    private static class Producer implements Runnable {
        @Override
        public void run() {
            for (int i=0; i<100; i++) {
                lock.lock();
                while (count == 1) {
                    try {
                        fill.await();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                buf = i;
                System.out.println("produce: " + buf);
                count = 1;
                empty.signal();
                lock.unlock();
            }
        }
    }
}

在上面的代码中我们要注意，一定要使用 while 循环来判断 count==0 和 count ==1 这两个条件。比如 consumer 中，如果使用 if，count==0 进入后，睡眠了，然后被唤醒，就直接执行后面的语句了，而没有循环再次检查一遍 count 的值（因为有可能在你唤醒的过程中，这个 count 的值被其他线程消费了）。

在条件变量这块，用 while 肯定不会出错，用 if 反而有可能出错。

Semaphore

信号量使用 condition variable 和 mutex 实现

Event-based Concurrency

select, poll