五、死锁
（1）什么是死锁？
死锁是指多个进程在运行过程中因竞争资源而造成的一种僵局（互相等待），若无外力作用，则这些进程都将无法向前推进。
（2）死锁产生的原因？死锁的四个必要条件？
死锁产生的原因：系统资源竞争、进程推进顺序不当
竞争资源例如：系统中只有一台打印机，可供进程A使用，假定A已占用了打印机，若B继续要求打印机打印将被阻塞。
进程推进顺序不当例如：进程A和进程B互相等待对方的数据。
系统中资源可分为两类：
1. 可剥夺资源：是指某进程在获得这类资源后，该进程可以再被其他进程或系统剥夺，CPU和主存均属于可剥夺性资源。
2. 不可剥夺资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放，如磁带机、打印机。
死锁产生的四个必要条件：互斥、请求保持、不可剥夺、循环等待
1. 互斥条件：在一段时间内某资源只能被一个进程使用，如果有其他进程请求该资源，则请求进程只能等待；
2. 不可剥夺条件：进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放。
3. 请求与保持条件：进程保持了一定资源后，但对其他资源发出请求，但请求的资源被其他进程占用，此时请求阻塞，对自己已有资源又保持不放；
4. 循环等待条件：若干进程间形成首尾相接、循环等待资源的关系。
（3）解决死锁的基本方法？
解决死锁的基本方法：
1. 预防死锁
2. 避免死锁
3. 检测死锁
4. 解除死锁
预防死锁的方法：核心思想是破坏死锁的四个必要条件之一，即
1. 破坏互斥条件
破坏互斥条件而预防死锁不大可行，而且有的场合应该保持这种互斥性。
2. 破坏不可剥夺条件：当某进程获得了部分资源，但得不到其他资源，则释放已占有的资源。
缺点：反复申请和释放资源会增加系统开销，降低系统吞吐量。
3. 破坏请求保持条件：采用预先静态分配的方法，即进程在运行前一次申请完它所需要的全部资源；在未满足全部资源时不运行；
缺点：但系统资源被严重浪费，且易导致“饥饿”状态；
4. 破坏循环等待条件：采用顺序资源分配法，即给系统中的资源编号，规定每个进程必须按照编号递增顺序申请资源；释放则相反。
缺点：编号必须相对稳定，但限制了新类型设备的增加。
经常发生使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费。
这种按规定次序申请资源的方法，给用户编程带来麻烦。
避免死锁的方法：
避免死锁同一属于事先预防策略，但并不是事先采取某种限制措施破坏死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可以获得较好的系统性能。
1. 进程启动拒绝：如果一个进程的请求会导致死锁，则不执行该进程；
2. 资源分配拒绝：又名银行家算法，如果一个进程增加的资源请求会导致死锁，则不允许分配。
检测死锁的方法：
1. 为每个进程和每个资源制定唯一编号；
2. 设定一张资源分配表，记录各进程与占用资源之间的对应关系；
3. 设定一张进程等待表，记录各进程与申请资源之间的对应关系；
4. 判断是否出现环路，是则引发死锁。
解除死锁的方法：
1. 资源剥夺法：挂起某些死锁进程，并释放其所保持的资源，分配给其他死锁进程，
2. 撤销进程法：强制撤销部分、甚至全部死锁进程，并释放其所保持的资源；
3. 进程回退法：让某些死锁进行回退到足以回避死锁的地步，回退过程中自愿释放资源，
但要求系统保留进程的历史信息，设置还原点。
（4）单核机器上写多线程程序，是否需要考虑加锁？
在单核机器上写多线程程序，仍然需要线程锁。
* 因为线程锁通常用来实现线程的同步和通信。
在单核机器上的多线程程序，仍然存在线程同步的问题。
因为在抢占式操作系统中，通常为每个线程分配一个时间片，当某个线程时间片耗尽时，操作系统会将其挂起，然后运行另一个线程。
如果这两个线程共享某些数据，不使用线程锁的前提下，可能会导致共享数据修改引起冲突。
（5）介绍几种典型的锁
互斥锁（mutex）：用于保证在任何时刻，都只能有一个线程访问该对象。当获取锁操作失败时，线程会进入睡眠，等待锁释放时被唤醒。
互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒，而操作系统负责线程调度，为了实现锁的状态发生改变时唤醒阻塞的线程或者进程，需要把锁交给操作系统管理，所以互斥锁在加锁操作时涉及上下文的切换。
读写锁（rwlock）：分为读锁和写锁。（读读共享，读写互斥，写写互斥）
处于读操作时，可以允许多个线程同时获得读操作。
但是同一时刻只能有一个线程可以获得写锁。其他获取写锁失败的线程都会进入睡眠状态，直到写锁释放时被唤醒。
注意：写锁会阻塞其他读写锁。当有一个线程获得写锁在写时，读锁也不能被其他线程获取。
读写锁的区别：
1）读写锁分读者和写者，而互斥锁不区分
2）互斥锁同一时间只允许一个线程访问该对象，无论读写；
读写锁同一时间内只允许一个写者，但是允许多个读者同时读对象。
条件变量：
互斥锁的一个明显的缺点是它只有两种状态：锁定、非锁定。而条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足，它常和互斥锁一起使用，以免出现竞态条件。当条件不满足时，线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化，一旦其他的某个线程改变了条件变量，它将通知响应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。总的来说，互斥锁是线程间互斥的机制，条件变量则是同步机制。
自旋锁（spinlock）：在任何时刻同一只能有一个线程访问对象。但是当获取锁操作失败时，不会进入睡眠，而是在原地自旋，直到锁被释放。
优点：这样节省了线程从睡眠状态到被唤醒期间的消耗，在加锁时间短暂的环境下会极大的提高效率。但是加锁时间过长，则会非常浪费CPU资源。
RCU，read0copy-update：在修改数据时，首先需要读取数据，然后生成一个副本，对副本进行修改。修改完成后，再将老数据update成新的数据。
* 使用RCU时，读者几乎不需要同步开销，既不需要获得锁，也不使用原子指令，不会导致锁竞争，因此就不用考虑死锁问题了。
* 而对于写者的同步开销较大，它需要复制被修改的数据，还必须使用锁机制同步并行其它写者的修改操作。
* 在有大量读操作，少量写操作的情况下效率非常高。
（6）两个进程访问临界区资源，会不会出现都获得自旋锁的情况？
单核cpu，并且开了抢占可以造成这种情况
| 
