操作系统第二章：同步、互斥、死锁
学完本章需要回答的几个问题
- 进程互斥指？四个部分？需要遵循的原则？
- 进程互斥的软件实现方法？各违反了什么原则？为什么？
- 进程互斥的硬件实现方法？
- 互斥锁/自旋锁缺点？
- 信号量机制——整型信号量与记录型信号量，PV操作
- 生产者与消费者问题、多生产者与消费者问题、读者写者问题、哲学家进餐问题、管程
- 死锁、饥饿和死循环；死锁的四个必要条件；死锁的处理策略（预防、避免、检测和解除）
同步、互斥
我们把一段时间内只允许一个进程访问的资源称为临界资源
进入临界区后，不解锁的情况下，仍然有可能下处理机。这是导致忙等的一大核心原因
互斥实现方法
TSL（Test-and-Set Lock）指令
作用：
原子地把某个内存单元设置为 1，并返回它原来的值。
用途：
实现忙等待锁（spinlock）
判断锁是否已被占用
依赖硬件保证“一气呵成”，不会被中断
示例行为：
old = *lock *lock = 1 return old
如果返回的 old 为 0 → 你获取到了锁
如果是 1 → 锁已被占用
Swap 指令（交换指令）
作用：
原子地交换内存变量和寄存器中的值。
用途：
也用于实现互斥锁
同样依赖硬件原子性
示例行为：
temp = *lock *lock = register register = temp
常用方式：让寄存器事先装入“1”，用它与 lock 交换。
如果交换后 lock 原来是 0，你就拿到了锁；如果是 1，代表锁忙。
锁
已学过的硬件/软件实现方法都是自旋锁
信号量
- wait/P/请求/阻塞操作，判断value<0，成立即阻塞；
- signal/V/释放/唤醒操作，判断value<=0，成立即唤醒；
- 能与之前进程状态转换串起来，阻塞原语、唤醒原语、PV操作；
- 记录型信号量唤醒原语并不是直接会使得等待队列的队头进程直接使用被等待的临界资源，而是会有阻塞态变为就绪态
生产者与消费者问题
为什么互斥P一定在同步P之后？如果互斥P在同步P之前的话，后面还有一个同步P可能导致阻塞，陷入死锁
多生产者与多消费者问题
相当于把full分裂成了apple和orange，而empty变成了plate
读者写者问题
读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数（共享锁？）。我们可以用count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。另外，对count变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现应该想到用互斥信号量。
P（W）本质上是限制加共享锁
哲学家进餐问题
哲学家进餐问题的关键在于解决进程死锁。这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。
如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。可以参考哲学家就餐问题解决死锁的三种思路。
管程
死锁
SPOOLing在逻辑上把互斥资源表现为共享资源。
