《操作系统之哲学原理》-锁
养金鱼的故事
金鱼有一个很大的特点，就是没有饱的感觉。因此，金鱼吃东西不会因为吃饱就停止，它们会不停的吃
一直到鱼缸里的食物都被吃完为止。所以，如果你一直喂，它就一直吃，直到胀死。
现在假设小明和小刚两个人合住一套公寓，共同养了一条金鱼，该金鱼一天进食一次。
两个人想把金鱼养活，一天只喂一次，也只能喂一次。如果有一天两人都喂了鱼，鱼就胀死，
如果一天内两人都没有喂鱼，鱼就饿死。
他们二人为了把鱼养好，做出如下约定：
每天喂鱼一次，且仅一次
如果今天小明喂了鱼，小刚今天就不能再喂，反之亦然
如果今天小明没有喂鱼，小刚就必须喂，反之亦然
一、不具备任何协调能力
小明与小刚不进行任何沟通，没人觉得要喂鱼时，查看一下鱼的状态，如果感觉鱼像是没有进食，则喂鱼，否则不喂
下面是给出的是在没有同步情况下的程序
小明：
if (noFeed) {
feed fish
}小刚：
if (noFeed) {
feed fish
}假设小明和小刚都是养鱼高手，一眼就能看出鱼是否喂过，上述的程序也能正确的执行吗？
答案是否定的
由于线程的执行可以任意穿插，小明可以先检查鱼，发现没有喂鱼，就准备喂鱼
但是就在小明准备喂时，程序切换，轮到小刚执行，小刚一看鱼还没喂，就喂鱼，喂完之后，线程切换到小明，
小明充检查完鱼状态的指令开始执行，于是就喂鱼，这样鱼就被喂了两次，鱼就胀死了
时序图:
| 时序 | 小明 | 小刚 |
|---|---|---|
| 1 | look at fish(no feed) | |
| 2 | look at fish(no feed) | |
| 3 | feed fish | |
| 4 | feed fish |
两个或多个线程争相执行同一段代码或访问同一资源的现象称为竞争(race)。
这个可能造成竞争的共享代码段或者资源称为临界区(critical section)
二、第一种同步机制：留字条
要防止与胀死，就需要防止竞争，想要避免竞争，就需要防止两个或多个进程同时进入临界区
要达到这一点，就需要某种协调手段
协调的目的就是在任何时刻都只能有一个人在临界区里，这称为互斥(mutual exclusion)
互斥需要满足4个条件
不能有两个进程同时在临界区里面
进程能够在任何数量和速度的CPU上正确执行
在互斥区域外不能阻止另一个进程的运行
进程不能无限制地等待进入临界区
第一种同步方式：小明与小刚商定，每人在喂鱼之前留下字条，告诉对方自己将检查鱼，并在需要时喂鱼
小明
if (noNote) {
leave note
if (noFeed) {
feed fish
}
remove note
}小刚：
if (noNote) {
leave note
if (noFeed) {
feed fish
}
remove note
}字条没有防止两个人同时进入临界区，鱼胀死的概率降低了，只有在交叉执行的情况下，才可能发生鱼胀死
改进留字条方法
小明
leave noteMing
if (no noteGang) {
if (noFeed) {
feed fish
}
}
remove noteMing小刚
leave noteGang
if (no noteMing) {
if (noFeed) {
feed fish
}
}
remove noteGang上面的程序，鱼是不会胀死了，但是如果穿插执行，鱼会被饿死。对应计算机来说，饿死比胀死好，所以这还是有改进的。
循环等待
小明
leave noteMing
// 循环等待
while (noteGang) {
do nothing
}
if (noFeed) {
feed fish
}
remove noteMing小刚
leave noteGang
if (no noteMing) {
if (noFeed) {
feed fish
}
}
remove noteGang不过循环等待是一种很大的浪费，还可能造成优先级倒挂。
事实上上面都在鱼缸和鱼这个层面，也就相当于一条条低级的指令，我们必须站在更高一层，把两条低级指令变成原子操作，
把保护鱼缸和鱼，提高到房鱼缸的房间，如何保证房间一次只有一人呢？那就是给房间加锁。
锁的特性
锁的初始状态是打开的
进临界区前必须获得锁
出临界区时必须打开锁
如果别人持有锁则必须等待
死锁的4个必要条件
死锁发生的必要条件是 资源有限
持有等待
不能抢占资源
循环等待条件
哲学家就餐问题
- 哲学家每天只做两家事情：思考 吃饭
吃饭规矩：哲学家围在一张圆桌边，每个人的左右两边均放着一根筷子。如果要吃饭，需要获得左右的筷子（不能用一根筷子吃饭）运行的算法：
1. 等待左边的筷子可用，然后拿起左边的筷子
2. 等待右边的筷子可用，然后拿起右边的筷子
3. 吃饭
4. 放下两根筷子如果每个哲学家穿插执行，将出现每个哲学家都拿起左边筷子，而等待右边筷子的情况，死锁将发生。
死锁的应对
两种策略：
一、允许死锁发生
假装没看见，不予理睬
死锁发生的概率比较低，防止死锁的代价很高，还不如重启在死锁发生后，想办法予以解决(基本行不通，检测死锁不能肯定死锁发生、可能检测死锁的线程自己发生了死锁)
首先需要检测死锁，利用资源分配矩阵、资源等待矩阵、系统总资源、当前系统可用资源 死锁恢复，可用使用抢占、终止占用最多资源的线程、杀掉整个线程、rollback动态避免
在每次进行资源分配时，必须经过仔细的计算，确保该资源请求批准后系统不会进入死锁或者潜在死锁状态
系统当前可用资源：3
| 线程 | 已持有 | 总需求 |
|---|---|---|
| A | 3 | 9 |
| B | 2 | 4 |
| C | 2 | 7 |
这个状态是否是安全状态？答案是 是安全状态
B先运行 取得2个系统资源运行结束，系统资源为 5
C运行，取5个系统资源运行结束，系统资源为 7
A运行，取6个系统资源运行结束
系统当前可用资源：2
| 线程 | 已持有 | 总需求 |
|---|---|---|
| A | 4 | 9 |
| B | 2 | 4 |
| C | 2 | 7 |
谁先执行都会发送死锁
难题所在：不能准确的预测线程的最大资源需求，只能粗略估算，如果计算超额会浪费资源，更为严重的是会
造成死锁误判，因为安全不安全的状态判断依据之一就是最大资源需求。如果估算过大，超过线程的实际资源需求
将造成在实际安全的情况下，系统被判为不安全，从而造成可以执行的任务也得不到执行
二、不允许死锁发生
仔细检查，避免死锁发生
通过将发生死锁的必要条件消除，避免死锁发生
消除死锁的必要条件
将资源无限增加、把资源变为共享，无限是不现实的，资源共享适合部分资源，例如键盘输入就无法共享
一个线程必须一次请求其所需要的所有资源，而不是一般情况下的请求一点资源做一点事情，缺点是不利于资源的有效利用。
一种变通的方法是，还像以前那样请求资源，不过如果请求的资源被拒绝，则该线程需要将其现在已经拥有的资源也释放。
这样的缺点是，本来完成了一半的工作，因为某个资源获取不到而放弃了以前的全部工作，也会造成浪费
允许抢占资源，如CPU和内存，但也不是所有的资源都能抢占，例如锁就不能抢占
出现循环等待的原因就是因为线程请求资源的顺序是随机的，我们可以规定资源的请求顺序
解决哲学家吃饭问题
- 杜绝循环等待：对筷子编号123456，拿筷子的人必须按照这个顺序拿
- 杜绝保持并等待：要求要么同时拿起两根筷子，要么一根都不拿
- 动态避免：在拿起一根筷子时，判断他是否可以拿起这根筷子，有哲学家在吃饭或者这根筷子后还有多余的筷子
锁的实现
硬件实现的原子操作(指令)：
- 中断禁止、启用(interrupt disable/enable)，这个操作由操作系统封装成锁
- 内存加载、存入(load/store)
- 测试与设置(test&set)
一、以中断启用与禁止来实现锁
进程切换必须发生上下文切换，而发生上下文切换只能有两种可能：线程自愿(yield)放弃CPU而将控制权交个操作系统调度器，
另一个是线程被强制（周期性的时钟中断）放弃CPU而失去控制权获得锁的伪代码：
lock() {
// 先禁止中断
disable interrupts;
// 检查 value，如果是FREE表示这个资源没有被占用
// 循环等待为 FREE
while (value != FREE) {
// 启用中断让其它进程有将 value 设置为 FREE时间
enable interrupts;
// 这中间是其它进程的时间
disable interrupts;
}
// 设置为 BUSY 开启中断
value = BUSY;
enable interrupts;
}释放锁：
unlock() {
// value 赋值为 FREE 需要中断保护，因为赋值语句不是原子操作
disable interrupts;
value = FREE;
enable interrupts;
}缺点：频繁的中断可能造成对重要的事件处理不及时，在锁的实现中留给其它进程获得CPU的机会也不大
二、以测试与设置指令来实现锁
原子操作：将内存指定位置的存储单元的内容读取到寄存器，将新的值写入到刚才的内存单元;
test&set 将值写入指定的内存单元，并返回内存单元原来的值test_and_set(X) {
tmp = X;
X = 1;
return tmp;
}
lock() {
while(test_and_set(value) == 1) {
}
}
// 调用unlock的进程移动是已经获得锁的，所以不需要保护
unlock() {
value = 0;
}三、以非繁忙等待、中断启用与禁止来实现锁
一和二的两种锁的实现都有繁忙等待的问题，繁忙等待浪费资源，并且有可能造成优先级倒挂和死锁- 使用中断禁止，但不进行繁忙等待。
- 如果拿不到锁，等待进程放弃CPU并进入睡眠状态，以便持有锁的进程可以更好的运行
- 当释放锁的时候将睡眠进程叫醒
错误的方式:
lock (){
// 如果别的线程没有执行中断，那么系统将进入死锁状态
disable interrupts;
if (value == FREE) {
value = BUSY;
} else {
// 加入该锁的队列
add thread to queue of threads waiting for this lock;
// 切换进程
switch to next runable thread;
}
enable interrupts;
}只能要求所有的线程遵循下列约定：
所有线程承诺在调用线程切换是将中断留在禁止状态
所有线程承诺在从切换返回是将中断重启启用
但是依赖别人来遵循是很危险的
四、以最少繁忙等待、测试与设置来实现锁
只用繁忙等待来执行闭锁操作，如果不能获得锁就得放弃CPUlock() {
while(test_and_set(guard)) {
}
if (value == FREE) {
value = BUSY;
guard = 0;
} else {
// 加入该锁的队列
add thread to queue of threads waiting for this lock;
guard = 0;
// 切换进程
switch to next runable thread;
}
}
unlock() {
while(test_and_set(guard)) {
}
value = FREE;
if (any thread is waiting for this lock) {
move waiting thread from waiting queue to ready queue;
value = BUSY;
}
guard = 0;
}
