操作系统：并发

intro

多线程共享相同的地址空间，但有不同的程序计数器和栈。

并发会引发十分多糟糕的问题，且人类的线性思维，适合观测串行运行的程序而非并行运行的程序，所以处理并发十分困难。详细的例子可以看jyy的os课体验一下并发互斥

临界区，(critical section)是指访问共享资源的代码。当多个线程同时进入临界区时，可能就会出现竞争条件(race condition)，导致计算机运行的结果具有不确定性(indeterminate)。为了避免出现竞态，线程应该使用互斥(mutual exclusion)原语。

我们希望拥有一些原子指令，他们可以构建出通用的集合，以此构建多线程代码。

API

// some basic api of thread
// to compile and exec multi-thread program:
// include pthread.h 
// gcc ... -lpthread
#include <pthread.h>

// to create a thread to start from function mythread
// and pass parameters args
void *mythread(void *arg){
	myret_t *r;
	...
	return (void *)r;
}
pthread_t p;
int rc = pthread_create(&p, NULL, mythread, &args)

// to wait for thread to terminate
myret_t *m;
pthread_join(p, (void **)&m);

// to create a lock
pthread_mutex_t lock;
int r = pthread_mutex_init(&lock, NULL);

pthread_mutex_lock(&lock);
...
pthread_mutex_unlock(&lock);

// other lock related function
// if lock is occupied, it failed
int pthread_mutex_trylock(pthread_mutex_t *mutex);
// if request timeout, it failed
int pthread_mutex_timedlock(pthread_mutex_t *mutex, struct timespec *abs_timeout);

// use condition variable for multi-thread
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t cond = PTHREAD_COND_INITIALIZER;
// thread1
pthread_mutex_lock(&lock);
while(ready == 0)
	pthread_cond_wait(&cond, &lock);
pthread_mutex_unlock(&lock);
// thread2
pthread_mutex_lock(&lock);
ready = 1;
pthread_cond_signal(&cond);
pthread_mutex_unlock(&lock);

Lock

最开始解决互斥的方案之一，是试图关闭中断。这种方法虽然简单但显然存在很多问题。比如出现恶意程序关闭中断并死循环，或者多处理器，等等。

显然用户不可以有暂停时间的权限，但操作系统可以有。我们可以编写一些原子指令来实现。

原子指令

一些基本的硬件支持的指令

• test-and-set：检查标志是否为1，并设置为1
• compare-and-exchange：比较两个值并更新值
• load-link + store-condition：条件式存储判断在加载地址链接某个值后，该值有无变化，若无，才会成功。

自旋锁

自旋锁，通过一直自旋，利用CPU周期直到锁可用。显然，如果持有锁的线程发生上下文切换，其他线程就只能一直自旋，等待该进程，浪费过多的资源和时间。有以下的解决方法。

放弃

当将要自旋时，线程可以主动放弃cpu，通过调用yield。但是，这样无法解决starving的问题，即可能导致进程处于让出的循环，直到其中一个线程终于释放锁。

队列+休眠

简单来说，我们可以通过队列来实现合理的调度，决定锁释放时谁抢到锁。核心思想是，在设置锁时，当多个线程同时竞争一把锁，未获得锁的线程会将自己加入队列并进入休眠。在释放锁时，会通过队列顺序来唤醒下一个线程。

值得注意的是，如果在进入休眠前，恰好锁释放了，可能导致该线程永久休眠，即wakeup/waiting race。可以添加新的调用，即表明自己即将要休眠，若刚好在休眠前调用了唤醒，该线程在进入休眠后会立即返回。

条件变量

很多情况下，为了实现同步，线程常常检查某一条件满足之后才会继续运行。在之前的实现中，我们可以通过自旋锁来完成，但显然在浪费cpu的时间。所以我们希望让未满足条件的进程休眠，直至条件满足时被唤醒。

我们可以声明条件变量，并通过wait()还有signal()的操作，来使该线程休眠等待，或者唤醒另一个线程。

生产者/消费者问题

描述一个模型：生产者负责将数据放入缓冲区，消费者负责将数据从缓冲区取走。两者都是线程。在执行的过程中，显然生产者的条件为缓冲区不满，消费者的条件为缓冲区不空，若不满足，可以通过上面的机制解决。真的吗？有什么要注意的问题？

why while

思考一下，如果我们用if来判断是否满足条件，判断出不满足时进入if让进程休眠，满足的话继续执行，最后唤醒其他进程。这在消费者和生产者都只有一个时，似乎可行，但如果消费者有两个呢？

若在一开始，缓冲区为空，两个消费者都进入了休眠状态。生产者填满了缓冲区，唤醒了消费者1，当消费者1就绪，正准备运行（从休眠处），消费者2抢先取数据（此时1还没有锁保护），轮到1时，1获取了锁，然后返回，但缓冲区已空。

上面的例子说明，当进程被唤醒时，只能暗示有状态发生变化，而不能推测在执行前条件一直满足。其次，用while代替if来判断是一个更好的选择。

还有问题吗？

more condition variables

不止上面的问题呢，想象一下，还是上面的场景，但我们已经把if换成while了。当消费者1取数据，显然这时2因为不满足条件，休眠了。1取完后，发送信号唤醒一个进程。问题来了，好像可能会把2给叫醒，2醒来发现条件还是不满足，继续睡了。结果是三个线程全部进入了休眠。

解决该问题的方法也很简单，通过两个变量，来保证信号的指向性，消费者发送信号1，接受信号2，生产者发送信号2，接受信号1。

covering condition

覆盖条件。当不知道唤醒哪个线程可以满足条件时，考虑唤醒所有等待线程。即可以覆盖所有需要唤醒线程的场景。在单个变量的生产者/消费者问题中，这是可行的。但如果程序只有改成广播信号，才能工作，大概率是程序本身有问题。（？

信号量

信号量为一个整数。可以通过wait()和post()来操作它。可以初始化信号量的值。wait的功能为令信号量减1，如果信号量小于0，就休眠。post为令信号量加一，唤醒等待线程。先假设信号量的变化都是原子的。

二值信号量

顾名思义，信号量开始时为1。第一个接触信号量的线程1，将其变为0并运行。在其结束前，其他试图进入临界区的线程，将信号量减为-1，等待。直到线程1释放锁信号量为0。如果结束前都没有其他线程访问临界区，信号量会恢复成1。这样就可以用于构成一般的锁。

信号量作条件变量

用于使线程暂停运行等待条件成立。信号量的初值设为0。假设一个线程1创建线程2并等待其结束。若创建后2并不开始运行，则1会将信号量减为-1并开始等待，直到2将信号量增加为0。如果2立即开始运行，2结束前信号量都为-1，1不会运行，结束后2就可以运行了。

生产者/消费者问题

实现其实在之前就写了，无非将对应的方法用信号量代替。但注意，如果我们在条件变量的外面加上锁，可能会导致死锁。比如，消费者持有锁，但在等消费的条件，当生产者试图运行时，因为没有锁，又进入等待。解决的方法就是缩小锁的范围，在条件变量内上锁。

读者-写者锁

mian idea是，写者和读者间显然只能有一把锁，但一旦有一个读者拿到锁，其他读者也可以使用。（因为读并不会修改状态）。写者需要等待所有的读者结束后才能开始，所以可能会导致starving。

哲学家就餐问题

假设有5个哲学家围在圆桌，两个哲学家之间放着一个餐具，每个哲学家需要左右手都拿到餐具才能开始吃饭。我们给餐具上锁，所以拿餐具的过程是原子的。若所有哲学家的策略都是一样的，先拿左手边的餐具，若恰好他们都拿到了左手边的餐具，都在等右手的，这时就会都阻塞。

一种可行的解决方法是，让其中一人先取右边，来破除这种依赖。

常见并发问题

非死锁缺陷

该问题占了并发问题的大部分，主要讨论以下的内容

违反原子性

指的是代码的愿意是原子的，然而并未按照原子性的实现。比如不加原子保护，判断一个指针非空后，试图访问改地址，有可能在访问时该指针已被其他线程变为空了。修复方法之一，就是加锁。

违反顺序

指的是预期访问内存的顺序被打破（多线程的不确定性），导致的缺陷。显然，通过强制顺序来修复该缺陷，比如用条件变量来同步。

死锁缺陷

产生条件

以下四个条件，只要一个不满足，死锁就不会产生：

• 互斥：比如需要抢锁
• 持有并等待：线程持有资源（如：锁），又在等待其他资源（如：需要的另一把锁）
• 非抢占：线程获得的资源，不能被抢占
• 循环等待：线程形成环路，环路上每个线程都额外持有一个资源，而这个资源又是下一个线程需要的

所以我们可以考虑四种策略，每种策略都试图阻止一个条件，从而避免死锁

预防循环等待

一个想法是，规定锁的获取必须有顺序。一种顺序叫全序(total ordering)，即全部锁都会按照一定的先后顺序获取，必须先申请锁1，才能申请锁2。然而在复杂的系统中，这可能很难做到，所以可以采用偏序(partial ordering)，仅包含所有锁中的几个锁的关系。

预防持有等待

可以原子抢锁来避免，原子地抢多个锁。然而这需要知道所需的全部锁，不适合封装，降低了并发。

预防非抢占

我们可以让线程在抢到锁1，抢不到锁2时，主动放出锁1。

值得注意的是，如果另一个线程的抢锁顺序不同，比如先2后1，可能会导致活锁，他们同时抢锁失败，一直循环。

这种方法的封装性一般，若代码在途中获得其他资源（比如内存），必须也要确保他们被释放。

预防互斥

不用锁，而使用硬件支持的原子操作。

调度

除了死锁的预防，我们还可以通过调度来避免死锁。让不竞争资源的线程并行运行，竞争的串行。

检查/恢复

允许死锁发生，采用死锁的检测和恢复技术。