如果保证相互排斥，例如使用信号量，那么程序是否没有死锁? [英] If mutual exclusion is guaranteed, say with semaphores, is a program deadlock-free?

问题描述

我分别定义互斥和死锁如下: 如果每时每刻将每个共享资源分配给一个进程，或者每个共享资源都可用，则存在互斥条件. 如果一组进程中的每个进程都在等待只有该组中的另一个进程才可能引起的事件，则该进程将陷入僵局.

I define mutual exclusion and deadlock as below, respectively: The mutual exclusion condition exists if at every moment, each shared resource is either assigned to exactly one process, or available. A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause.

说，使用二进制信号量，以确保它们中只有一个可以同时进入其关键区域.由于每个进程在进入关键区域之前都会发生下降，而在离开关键区域之后则会发生上升，因此可以确保相互排斥.

Say, binary semaphores are used, ensuring that only one of them can enter its critical region at the same time. Since each process does a down just before entering its critical region and an up just after leaving it, mutual exclusion is guaranteed.

我了解要使死锁发生必须同时满足四个条件，其中之一是互斥条件(在临界区中不能同时存在两个进程).

I understand there are four conditions which must all hold for deadlock to occur, one of which is the mutual exclusion condition (no two processes may be simultaneously inside their critical sections).

由于保证了互斥，程序在这种情况下是否没有死锁?

Since mutual exclusion is guaranteed, is the program, in this case, deadlock-free?

致谢.

推荐答案

不一定.想象一下这两个线程:

Not necessarily. Imagine these two threads:

 Thread 1          Thread 2
 ============      =============
 Acquire A         Acquire B
 Acquire B         Acquire A
 Release B         Release A
 Release A         Release B

在这里，确实可以保证互斥-在每个瞬间，信号量A和B要么由一个线程拥有，要么在整个系统范围内可用-但是，如果线程1和2各自获得了第一个锁，则仍然可能出现死锁(对于线程，A 1，B代表线程2)，但随后将死锁，等待对方持有的资源.

Here, mutual exclusion is indeed guaranteed - at each instant, semaphores A and B are either owned by one of the threads or available systemwide - but deadlock is still possible if Thread 1 and 2 each acquire their first lock (A for Thread 1, B for Thread 2), but then will deadlock waiting for the resource that the other is holding.

希望这会有所帮助！

这篇关于如果保证相互排斥，例如使用信号量，那么程序是否没有死锁?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！