互斥与同步
互斥与同步
计算机运行过程中，大量的进程在使用有限、独占、不可抢占的资源。这种对资源的争用称为竞争（race）；竞争条件指程序结果依赖未受控制的并发执行顺序。
进程间的制约关系可分为两类：
- 互斥（mutual exclusion）：两个或多个进程没有内在的先后关系，但由于争用临界资源（不能被多个进程同时使用的资源，如打印机）而产生制约关系。
- 同步（synchronization）：两个或多个进程存在内在的先后关系，例如前一个进程执行完某项操作，其他进程才能继续执行。
操作系统中的进程各有独立的数据存储，不能直接访问其他进程的私有数据。通过管道等机制可以实现进程间通信。但是不同的进程操作同一个资源时，必须考虑数据同步的问题。
要理解同步概念，首先要清楚进程不同步所带来的问题。
售票操作（Bug版本）
import multiprocessing
import time
def sell_ticket(dict):
while True:
num = dict.get("ticket")
if num > 0:
time.sleep(1)
num -= 1
print("[Ticket Machine %d] Ticket sold. Ticket remaining: %d" % (
multiprocessing.current_process().pid,
num
))
dict.update({"ticket": num})
else:
break
def main():
manager = multiprocessing.Manager()
ticket_dict = manager.dict(ticket=5)
sellers = [
multiprocessing.Process(
target=sell_ticket, args=(ticket_dict,)
)
for _ in range(5)
]
for seller in sellers:
seller.start()
for seller in sellers:
seller.join()
if __name__ == "__main__":
main()多个进程同时判断票数，而读取、判断和修改没有整体同步时，就会出现重复售票或覆盖更新的问题。
解决互斥的等待方法有两种：
- 忙等待（busy waiting）：等待时不断检查测试，直到能够继续。
- 睡眠与唤醒（sleep and wakeup）：利用信号量等机制使等待的进程阻塞，由其他进程触发唤醒。
抢票现场：两部手机，一个座位
解锁完整互动实验、进阶解析与精选参考答案。
临界区（Critical Section）
临界资源是各进程采取互斥方式、一次仅允许一个进程使用的共享资源。属于临界资源的有打印机、变量、缓冲区等。
每个进程中访问临界资源的那段代码称为临界区，同一临界资源每次只允许一个进程进入相应临界区。不论是硬件临界资源还是软件临界资源，多个进程必须互斥地访问。临界区运行时间不宜过长，等待者可能自旋或阻塞，因此会影响程序的运行性能。
WHILE true DO
执行进入区：请求进入临界区
执行临界区：访问共享资源
执行退出区：释放访问权限
执行剩余区：完成其他工作
END WHILEPeterson算法
Peterson算法由Gary L. Peterson于1981年提出，用于控制两个参与者对共享资源的互斥访问。其正确性需要原子读写及适当的内存顺序，不能直接用未同步的普通C变量实现。
Peterson算法要求两个进程共享两个数据项：
int turn;
bool flag[2];互斥锁（Mutex）
互斥锁是用一种简单的加锁方法来控制对共享资源的访问，互斥锁只有两种状态，即上锁（lock / acquire）和解锁（unlock / release）。
互斥锁的获取必须是一个原子操作（atomic operation），这意味着如果一个进程锁定了一个互斥量，没有其它进程在同一时间可以成功锁定这个互斥量。检查可用状态与加锁不能是两个分离的普通读写操作；下例仅表示获取与释放的流程，不是可直接用于并发的原子实现。
void acquire(void) {
while (!available) {
; // busy wait
}
available = false;
}
void release(void) {
available = true;
}
do {
acquire();
// critical section
release();
// remainder section
} while (true);并发进程的执行如果要进行同步处理，那么就必须对一些核心代码进行同步。Python中提供了一个Lock同步锁机制，利用这种锁机制可以实现部分代码的同步锁定，保证每一次只允许有一个进程执行这部分的代码。
售票操作（正确版本）
import multiprocessing
import time
def sell_ticket(lock, dict):
while True:
if not lock.acquire(timeout=5):
break
try:
num = dict.get("ticket")
if num > 0:
time.sleep(1)
num -= 1
print("[Ticket Machine %d] Ticket sold. Ticket remaining: %d" % (
multiprocessing.current_process().pid,
num
))
dict.update({"ticket": num})
else:
break
finally:
lock.release()
def main():
lock = multiprocessing.Lock()
manager = multiprocessing.Manager()
ticket_dict = manager.dict(ticket=5)
sellers = [
multiprocessing.Process(
target=sell_ticket, args=(lock, ticket_dict)
)
for _ in range(5)
]
for seller in sellers:
seller.start()
for seller in sellers:
seller.join()
if __name__ == "__main__":
main()一旦程序中追加了同步锁，那么相应临界区就只能由一个进程执行，这可能增加等待和同步开销；为了保证共享数据操作安全，需要使用适当的锁机制。
硬件实现
test_and_set()由硬件提供原子性；下面以C语法描述操作语义，普通C函数的分步读写不能保证原子性。
bool test_and_set(bool *target) {
bool rv = *target;
*target = true;
return rv;
}共享锁lock初始化为false，while (test_and_set(&lock));中的分号表示循环等待解锁。
do {
while (test_and_set(&lock)) {
; // do nothing
}
// critical section
lock = false;
// remainder section
} while (true);compare_and_swap()同样必须以原子操作实现；下面以C语法表示其操作语义，普通分步读写不能保证原子性。
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected) {
*value = new_value;
}
return temp;
}互斥锁lock初始化为0。
do {
while (compare_and_swap(&lock, 0, 1) != 0) {
; // do nothing
}
// critical section
lock = 0;
// remainder section
} while (true);使用机器指令的优点是简单且易于证明，可以支持多个临界区，每个临界区都可以用自己的变量定义。缺点是需要忙等待，并且可能引发饥饿。当一个进程离开临界区且有多个进程正在等待时，如果没有公平的选择规则，某些进程可能被无限地拒绝进入。
知识测验
一张座位票：后来的人要不要等？
A08仅剩1张票，两位买家使用同一把互斥锁。
- B应该立即进入购票操作，还是等A释放锁？
- A买走最后一张票并释放锁。B获取锁后看到余票为0，应该出票还是提示售罄？