概述

多进程并发访问操作同一数据，且执行结果与访问顺序有关，这种现象称为竞争条件。为避免竞争条件，需要进行进程同步。

临界区问题中，没有两个进程可以同时在临界区内执行，代码可以分为进入区、临界区、退出区、剩余区。三个基本的要求是：互斥访问，空闲让进，有限等待。假设每个进程的执行速度非零，但相对速度没有任何假设。

非抢占内核中，处于内核态的进程会一直运行到退出内核态、阻塞或者主动放弃 CPU，这种模式下不会有竞争条件，但抢占内核更适合实时程序，响应更快。

解决临界区问题

临界区问题可以用较为繁复的软件方法解决，而一些简单的尝试可能不能同时满足三个要求。证伪一个要求的方式是构造恰当的执行顺序，很多时候一人一步或一人一直走等极端情况会很有效。

软件方法

单标志法中，我们维护 turn 表示接下来该由谁来访问，进入区只需要 turn=j; while(turn!=i);，即先谦让，等被让回自己时再走。这样不满足空闲让进。

双标志先检查法中，我们维护 flag[] 表示某个进程是否有访问的意愿。所谓先检查，就是先检查是否有他人有意愿，再提出自己意愿。这样不满足互斥访问。同理，双标志后检查法不满足空闲让进。

Peterson 算法是双标志后检查和单标志法的融合，“我有想法但下次归你，如果你有想法并且下次归你我就等。”三个要求同时得到满足。

Bakery 算法维护 choosing[] 表示某个进程是否在选号，选到的号存进 number[] 中，前项为摇号机摇到的号（为当前 number[] 中最大值 +1），后项为自身进程号。进程先标记 choosing[i] 然后计算一个 number，取消 choosing[i] 后扫描一遍，如果有人在选就等他选好，如果有人的编号比我小就等着。扫描完后即可进入邻接区，退出时别忘了清楚编号。注意 choosing[] 是必须的，不妨设想进程 1 已经计算出号 (1,1) 还未保存，切到进程 2 计算出号 (1,2)，但以为自己最小而进入临界区，此时切回进程 1 又进入临界区，未被互斥访问。

硬件方法

下面我们考虑如何构建一个互斥锁。用单标志 flag 显然是不行的，我们考虑一些硬件支持。

关中断是有效的，但它权限太高，不适用于多处理器，可能会丢失中断，也不够高效。

借助 Test-and-Set 指令，我们用 while(TAS(flag,1)==1); 就可以实现加锁，解锁只需 flag=0;，这样不满足有限等待，但一个标记数组和循环扫描也许会有所帮助，即解锁时按顺序考虑唤醒一个等待者。

借助 Compare-and-Swap 指令，我们用 while(CAS(flag,0,1)==1); 就可以实现加锁，类似地，它同样不满足有限等待。

条件变量

条件变量是一种显式队列，线程可以通过条件变量来等待一个条件变为真。执行条件不满足时，线程可以把自己加入队列。另一个线程改变了状态时可以通过发信号来唤醒等待线程。

wait(condition, mutex) 调用时 mutex 必须已是上锁状态，wait 会释放 mutex 并使调用线程休眠。线程被唤醒时必须重新获取 mutex 再返回调用者。signal(condition) 用于唤醒某个条件变量上的睡眠线程。

用条件变量可以实现线程的 join 和 exit，设条件变量 c 配套有互斥锁 m 和标记 done，则 join() 实现为 lock(m); while(!done) wait(c,m); unlock(m);，exit() 实现为 lock(m); done=1; signal(c); unlock(m);。如果去掉互斥锁 m 或者标记 done 都可能会导致先 signal 后 wait，因此通常条件变量会和互斥锁与标记配套使用。

信号量

信号量是一个整数变量，通过 wait() 和 signal() 原语来操作。最简单的信号量是个自旋锁，为了克服忙等待我们稍加修改。若 wait() 时发现信号量值不为正则必须阻塞自己，而 signal() 后若信号量值不为正则从对应的等待队列头部唤醒一个阻塞的进程。具体地，wait() 相当于 value--; if(value<0) push(this), block(this);，signal() 相当于 value++; if(value<=0) wakeup(pop());。另外，对 SMP 系统，还需要其它加锁机制来保证 wait 和 signal 的原子性。

多个进程无限等待只能由它们自己产生的事件，则它们称为死锁。进程在信号量内无限期等待称为饥饿。

经典同步问题

生产者-消费者问题

定义三个信号量，empty 表示空缓冲区数，full 表示满缓冲区数，mutex 用于保护缓冲区。

对于生产者，只需要 wait(empty); wait(mutex);，然后干活并释放即可。

注意 wait 的顺序不能颠倒，否则会出现死锁。

读者-写者问题

第一类读者-写者问题要求读者优先。实现时需要 readcnt 表示当前读者数量，readcnt_m 保护 readcnt，rw_m 表示当前是否有人在读或者有人在写。实现如下：

Write()
{
    wait(rw_m);
    write();
    signal(rw_m);
}
Read()
{
    wait(readcnt_m);
    readcnt++;
    if(readcnt==1) wait(rw_m);
    signal(readcnt_m);
    
    read();
    
    wait(readcnt_m);
    readcnt--;
    if(readcnt==0) signal(rw_m);
    signal(readcnt_m);
}

第二类读者-写者问题要求写者优先，即一旦有写者要写，下次就不得让读者进入。实现时需要 readcount 表示当前读者数量，writecount 表示当前写者数量，read_m 表示当前是否可读，write_m 表示当前是否可写。此外还需要保护数据一致性的 readcount_m 和 writecount_m。

哲学家进餐问题

在哲学家进餐问题中，可以通过限制进餐者总数，或者让部分人反手，来解决死锁。