僵局¶
死锁-定义¶
正式：两个或多个执行线程在一个周期中各自等待资源的状态。
非正式用法：当两条线进入一只鸡之前，鸡蛋处于锁定状态。
当发生死锁情况时，除非另外被破坏，否则所涉及的执行线程将保持暂停状态，直到它们在外部被终止。
如果僵局是可能的，它可能不会总是立即发生。如果有可能，只要时机得当，这最终是可以实现的。
餐饮哲学家问题¶
哲学家可以是吃的也可以是思考的
哲学家之间不能以任何方式进行交流
吃东西，哲学家需要左右叉。
餐饮哲学家--僵局场景¶
eat() {
pick up right fork;
pick up left fork;
proceed with eating;
}
T=0：P1、P2、P3、P4、P5各拿起右叉
T=1：P1尝试拿起左侧叉子，无法继续，因为P5已握住它
T=2：P2尝试拿起左叉子，无法继续，因为P1握住了它
T=......
等待行动将永远持续下去。每个哲学家手中都拿着一把叉子。每个哲学家都在等待另一个人拿着的叉子
餐饮哲人--锁图¶
在第一个算法中，可以以任何顺序获取锁。考虑到这一点，在图上画一个圈和死锁是可能的。
餐饮哲学家¶
我们可以为Eat()实现什么算法，以便不会出现死锁？
为什么我们会遇到僵局？
餐饮哲学家--解决方案1¶
eat() {
while(does not have both forks) {
pickup left fork
if(can pick up right fork) {
pick up right fork;
} else {
put down left fork;
}
}
proceed with eating
}
这种解决方案之所以有效，是因为它将两个叉子都作为原子操作来获得：如果哲学家无法获得第二个叉子，他们就会放下手中的叉子。他们要么两个叉子都有，要么没有叉子。
这防止了由于检查操作而导致的循环
餐饮哲学家--解决方案2¶
每个叉子都有一个编号
eat() {
pick up fork with lower number
pick up fork with higher number
proceed with eating
}
此解决方案之所以有效，是因为为资源分配了部分顺序。这有效地减少了在资源锁图中可以获得的锁的顺序中可能的边数。该图被简化为有向非循环图，根据定义，该图不能有圈，也不能死锁。
在解决方案2中，由于锁的顺序是一致的，所以图变成有向的和无环的。
根据这些规则，您不能在此图上画圈，也不能死锁
Dijkstra解/银行家算法¶
餐饮哲学家问题的解决方案#2也称为Dijkstra解或银行家算法
- 此解决方案的正面
易于实现和验证锁定顺序。
多锁算法可以通过比较内存地址来实现。也就是说，互斥锁可以按照它们在内存中出现的顺序锁定
- 此解决方案的不足之处
如果您检查前面的无向循环图，就会发现有几种获取锁的排列不会死锁。
在有向无环图中，所有的排列都是无死锁的，但无死锁排列的总数远远少于无向循环图
由于这些问题，可能的总并发性不是最优的
对Dijkstra解的优化¶
解决方案#1代表对Dijkstra的解决方案的优化。
在解决方案#1中，图保持无向和循环，但启发式被更改为只获得这两个资源，如果它们可以原子获得的话。
在解决方案#1中，可以实现所有可能的无死锁排列。正因为如此，更多的并发性成为可能。
解决方案#1的缺点是它通常更难实现
死锁避免实现¶
又名。银行家算法
又名。迪克斯特拉溶液
typedef struct {
int LockNumber;
void* LockObject;
} lock;
void multi_lock(lock* locks, int count) {
sort(locks, count);
for(int i = 0; i < count; i++) {
lock(locks[i]);
}
}
防止死锁的实施¶
又名。对Dijkstra解的优化
这只是一种实现方法。还存在涉及锁表或协调器的其他内容
typedef struct {
int LockNumber;
void* LockObject;
} lock;
void multi_lock(lock* locks, int count) {
while(1) {
int i = 0;
for(i = 0; i < count; i++) {
if(!try_lock(locks[i])) {
for(int j = 0; j < i; j++) {
unlock(locks[j]);
}
break;
}
}
if(i == count) {
return;
}
}
}
死锁的例子¶
僵局在哪里？
void method1() {
a.lock();
method2();
a.unlock();
}
void method2() {
b.lock();
c.lock();
b.unlock();
c.unlock();
}
void method3() {
c.lock();
method2();
method4();
c.unlock();
}
void method4() {
d.lock();
d.unlock();
}
Windows中的多锁解决方案¶
Windows中的C++方法是WaitForMultipleObjects()。
该方法接受N个锁句柄
- 此方法接受多种类型的资源和锁：
活动
互斥锁
信号量
计时器
还有其他许多人..。
Linux/Minix中的多锁解决方案¶
据我所知，在Linux或Minix中没有免费提供的多锁解决方案
一般的经验法则是，如果可能，通过设计，或者如果有必要使用锁的内存顺序作为排序，则尝试避免多重锁定。
如果使用共享内存信号量，则内存排序将不起作用，因为虚拟地址将不可靠。在这种情况下，必须通过某些其他机制强制执行锁排序，例如将锁存储在数组中并按数组的顺序锁定它们。
锁定顺序导致的死锁¶
虽然无序获取多个锁可能会导致死锁，但正确排序的锁也可能以其他方式导致死锁。
- 如果一个正在执行的线程锁定了一个资源，但未能释放该锁，则任何其他尝试获取该锁的线程都将死锁。这可能是由以下一个或多个原因造成的：
程序员错误：没有调用释放锁
线程在没有释放锁的情况下崩溃
释放锁的条件永远不会满足(无限循环、监视器中定义不正确的规则等)。
这些类型的死锁实际上更难处理。
饥饿¶
饥饿是僵局的近亲。饥饿意味着，实际上，一个线程将拥有资源的独占锁，而一个或多个线程不会。
就公平性而言，这类似于调度问题。
活锁问题示例：
线索1：
Queue _queue = new Queue();
Mutex _mutex = new Mutex();
void add() {
int value = 0;
while(1) {
_mutex-»Lock();
while(_queue-»count() » 0) {
value += _queue-»Dequeue();
printf("current value = %d\n", value);
}
_mutex-»Unlock();
}
}
线索2：
void read_values() {
while(1) {
int value = 0;
_mutex-»Lock();
scanf("%d\n", &value);
_queue-»Enqueue(value);
_mutex-»Unlock();
}
}
这里有两个潜在的饥饿问题。你能认出他们吗？
在thread1中，我们调用了printf()。这将导致线程1进入休眠状态，此时线程2将无法获得锁。
在线程2中，我们调用scanf()，同时等待输入，锁被持有，线程1将无法获取锁
我们如何才能使这段代码变得更好？
线索1：
Queue _queue = new Queue();
Mutex _mutex = new Mutex();
void add() {
int value = 0;
while(1) {
_mutex-»Lock();
while(_queue-»count() » 0) {
value += _queue-»Dequeue();
_mutex->Unlock();
printf("current value = %d\n", value);
_mutex->Lock();
}
_mutex-»Unlock();
}
}
线索2：
void read_values() {
while(1) {
int value = 0;
scanf("%d\n", &value);
_mutex-»Lock();
_queue-»Enqueue(value);
_mutex-»Unlock();
}
}
在这个版本的代码中，在像print tf或scanf这样的I/O操作(它们调用读和写)期间不持有锁。
因为在阻塞操作期间不持有锁，所以锁和解锁将更频繁地发生，这将减少接收锁的平均等待时间。
避免饥饿的指导方针¶
在可能的情况下，将锁限制为计算绑定的代码
关键部分要简短。如果计算运行时间较长，则设计代码以定期放弃锁。
- 如果可能，在临界区复制并在锁外执行计算。例如：
获取锁
复制队列中的项目
将项目更新为“正在进行”
释放锁
执行计算
获取锁
从队列中删除项目
释放锁定
确保您使用的锁库具有一定的公平性保证。
利夫洛克¶
Livelock类似于Deadlock。
Livelock基本上是一种竞争条件，以避免僵局。
活锁的一个例子是，如果一个进程试图通过测试进行多锁，然后轮流获取每个锁，而另一个进程正在执行相同的操作，则它们可能会通过纠正操作相互阻止。
示例：
void thread1() {
while(1) {
a.lock();
if(b.trylock()) {
//do work
b.unlock();
}
a.unlock();
}
}
void thread2() {
while(1) {
b.lock();
if(a.trylock()) {
//do work
a.unlock();
}
b.unlock();
}
}
T0：线程1锁定，上下文切换
T1：线程2锁定b，尝试锁定a，失败，上下文切换
T2：线程1尝试锁定b，失败，解锁a，上下文切换
T3：线程2解锁b，上下文切换
锁定公平性¶
锁公平性最好的描述是让每个执行线程等待一个锁，该锁的平均等待时间相似。
不公平的锁可能会导致资源匮乏。
- 两种最常见的方法涉及：
FIFO队列-常见
带有时间表和历史记录的锁调度程序-不常见
锁定公平。利弊得失¶
记住，虽然“公平”这个词听起来不错，但这个“公平”是要付出一些代价的。
要记住的关键点是，当一个线程被“选择”来获取锁时，在该选择和该线程执行之间将有一个非零的时间。这可以被认为是“公平成本”。
- 优点：
减少饥饿
创建更可预测的执行模式
- 缺点：
如果线程在循环中锁定，让线程在其量程未完成时重新获取锁定可以提高总体性能。公平的锁并不总是允许在量程未完成时重新获取锁。这可能会导致较短的量程，从而影响吞吐量。
锁公平可以为短锁创建较短的量程。这反过来又会损害当地