Readers/Writers Lock 读写锁
四个全局变量
- AR：在读的读者
- WR：在等的读者
- AW：在写的写者
- WW：在等的写者
为什么要给写者优先度？
- 先改动再被读
这种实现，写者不会被饥饿，因为当WW>0的时候，读者不能读
一些问题
左边代码改为broadcast会通知所有写者，可以这么做，只有一个返回的写者能拿到锁，然后while((AW+AR))>0会重新判断
右边代码从broadcast改为signal会通知一个读者，会有问题，只唤醒一个读者，读者会积累。
如果R1唤醒了R2，但是R2由于(WW>0)无法读，所以会陷入死锁
实现读写锁
Deadlock 死锁
同一个顺序获取锁，就不会死锁
死锁一定会饥饿，饥饿不一定会死锁
草，当初上课看到这个图想到的是JOJO6里面的大总统拿餐巾纸
产生死锁的条件
两种或两种以上的资源才会死锁
Important
死锁的四个条件
- 互斥
- 获取并等待
- 没有抢占
- 循环等待
如何处理死锁
Allow system to enter deadlock and then recover(允许进入死锁状态并恢复)
- Requires deadlock detection algorithm
- Some technique for forcibly preempting resources and/or terminating tasks
Ensure that system will never enter a deadlock(不允许系统进入死锁状态)
- Need to monitor all lock acquisitions
- Selectively deny those that might lead to deadlock
Ignore the problem and pretend that deadlocks never occur in the system(鸵鸟算法，现实中使用最多的，OS不会管你是否进入死锁)
- Used by most operating systems, including UNIX
如何避免进入死锁
破除死锁的四个条件
- No circular wait
让所有锁的获取是顺序的，那么就不会陷入死锁
在函数内部不知道函数调用顺序的解决方式
问题是需要开发者小心地进行设计和编程
并不是所有资源在写前就知道要被用到的，很难满足要求
- 破除获取并等待
锁住锁的锁
问题是必须在用之前就知道哪些锁会被用到，而且并行度下降了
扩大了临界区的大小
- 打破互斥
为什么用while?防御性编程
上面的实现会有同步问题
- 智能调度
银行家算法
锁是一种资源
T1、T2是线程，R1、R2是资源
能改变的是多个线程之间获取和释放资源的先后关系
图2死锁
遍历T，找到满足资源的T，然后删掉；如果无法满足全部的T，那么就死锁
从出度为0的资源出发
银行家算法
不知道精确的资源获取数，但是知道资源所需的最大值。（要保证不会出现用户拿不出钱的情况）
每一个线程在试图获取资源的时候，调度器会判断，如果给了资源，是否会进入死锁；如果会，则跳过该线程，先服务其他的线程；如果不会，则给资源
安全状态：不管资源申请顺序，都存在一种调度的方法能让任务执行完
不安全状态：不管怎么调度，都会进入死锁状态
银行家算法的本质就是让自己一直保持在安全状态
如果算法可以跑完，说明在安全状态
注意这个表怎么画
不安全状态不一定导致死锁，但是安全状态一定不会死锁
Smart scheduling
- banking algorithm
- Cons: must know the entire set of tasks and their resource demands beforehand; concurrency decreased.
- Only used in limited scenarios such as embedded system.
无限资源
demanding paging可以将内存当作磁盘的缓存，当虚拟页放不下的时候，把一些页放到磁盘中，当需要的时候再调度回来
