锁

锁类型

悲观锁认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁
乐观锁假定冲突的概率很低，先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作

乐观锁也叫无锁编程，全程不加锁

当已经有一个线程加锁后，其他线程加锁则就会失败

互斥锁加锁失败后，线程会释放 CPU 给其他线程
自旋锁加锁失败后，线程会占据 CPU 忙等待直到拿到锁

互斥锁是一种独占锁，加锁失败时由操作系统内核实现阻塞

互斥锁存在两次线程上下文切换，因此当加锁执行的代码执行时间较短时，应选用自旋锁减小开销

自旋锁通过 CPU 提供的 CAS 函数完成加锁

CAS 函数将两个步骤合并成一条硬件级指令，形成原子指令，这样就保证了这两个步骤是不可分割的，要么一次性执行完两个步骤，要么两个步骤都不执行
CAS 本身为乐观锁，但自旋锁为借助 CAS 实现的悲观锁

在单核 CPU 上使用自旋锁需要抢占式的调度器(即不断通过时钟中断一个线程，运行其他线程)，因为一个自旋的线程永远不会放弃 CPU

当写锁没有被线程持有时，多个线程能够并发地持有读锁
一旦写锁被线程持有后，其他线程对于读锁和写锁的获取都会阻塞

读写锁适用于读多写少的场景

读写锁又可分为读优先锁和写优先锁

读优先锁和写优先锁都可能会产生饥饿问题，因此需要公平读写锁
公平读写锁比较简单的一种方式是：用队列把获取锁的线程排队，不管是写线程还是读线程都按照先进先出的原则加锁

计算机操作系统 - 死锁 | CS-Notes 面试笔记 (cyc2018.xyz)

死锁只有同时满足以下四个条件才会发生：

绘制资源分配图，方框表示资源，圆圈表示进程
资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源
图 a 可以抽取出环如图 b，满足了环路等待条件，因此会发生死锁

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生

上图中，有三个进程四个资源，每个数据代表的含义如下：

E 向量：资源总量
A 向量：资源剩余量
C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
R 矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

解决死锁问题只需要破坏其中一个条件

避免死锁还可将系统的状态分为 安全状态 和 不安全状态 ，每当在未申请者分配资源前先测试系统状态，若把系统资源分配给申请者会产生死锁，则拒绝分配，否则接受申请，并为它分配资源

解决死锁问题的另一条途径是死锁检测和解除，对资源的分配不加以任何限制，也不采取死锁避免措施，但系统定时运行死锁检测程序，判断系统内是否出现死锁，如果检测到系统发生了死锁，再采取措施去解除它
常用的解除死锁的方法有以下四种：

当一个进程申请使用资源的时候，银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待

安全性算法
假设资源 P1 申请资源，若申请的资源数量小于等于空闲资源数量，银行家算法先试探的分配给它，然后接着判断分配给 P1 后剩余的资源，能不能使进程队列的某个进程执行完毕

若没有进程可执行完毕，则系统处于不安全状态
若有进程可执行完毕，则假设回收已分配给它的资源(空闲资源数量增加)，把这个进程标记为可完成，并继续判断队列中的其它进程
- 若所有进程都可执行完毕，则系统处于安全状态，并根据可完成进程的分配顺序生成安全序列

银行家算法改善了 资源使用率低的问题 ，但是它要不断地检测每个进程对各类资源的占用和申请情况，以及做 安全性检查 ，时间开销较大