一种简单的死锁检测算法

1. 死锁检测

给出一组操作锁定过程的线程，确定是否会发生死锁？

例如: 有两个线程和两个资源，该线程对锁的操作如下:

其中T是线程ID，L是锁ID，S是操作（1表示获取锁，0表示释放锁）

T L S

1 1 1（线程1获得锁号1）

2 2 2（线程2获取2号锁）

1 2 1（线程1获得2号锁并一直等待）

2 1 1（线程2获得锁号1，导致死锁）

如果将最后一个操作更改为: 2 2 0，将没有死锁.

问题的关键是如何确定死锁的发生. 以上面的示例为例: 当线程2获得1号锁时，发现1号锁被1号线程占用，则有必要等待1号线程释放1号锁. 然后查看线程1，等待2号锁，线程2占用2号锁多线程死锁的伪代码，因此线程1必须等待2号线程释放2号锁，这形成了一个等待循环. : 线程2->线程1->线程2，发生死锁. 因此，检测死锁的方法是确定是否存在这样的等待循环.

对于给定的线程操作锁定序列: vector > tls，必须维护3个映射以确定是否发生死锁，

map lock2thread: lock-> thread多线程死锁的伪代码，标识当前锁所占用的线程

map waitedthread2lock: 确定当前线程正在等待哪个锁

map > thread2locks: 标识线程持有的锁.

伪代码如下（省略了一些更新和查询操作）:

bool DeadLock(vector<vector<int>> &tls) {
  int size = tls.size();
  map<int, int> lock2thread;
  map<int, int> waitedthread2lock;
  map<int, vector<int>> thread2locks; 
  for(int i = 0; i < size; i++) {
    int tid = tls[i][0];
    int lock = tls[i][1];
    int state = tls[i][2];
    if (state == 0) {
      //释放锁，这是一定不会引起死锁的，因此只需要更新3个map就可以了
      //1.从lock2thread中删除key==lock的元素
      lock2thread.erase(lock2thread.find(lock));
      //2.从thread2locks中移除lock
      thread2locks[tid].erase(find(thread2locks[tid].begin(), thread2locks[tid].end(),lock));
      //3.遍历waitedthread2lock，查看哪个线程等待lock
        //3.1如果有线程等待此lock，那么依次更新lock2thread和thread2locks
    } else {
      //说明tid想要获取lock，那么这个操作是可能导致死锁的
      if (lock2thread.find(lock) != lock2thread.end()) {
        //说明该锁已经被占用，那么可能引起死锁
        int nexttid = 0;//当前线程依赖的下一个线程
        int nextlock = lock;
        while(1) {
          nexttid = lock2thread[nextlock];
          if (nexttid == tid) return true;//发生死锁
          //查看nexttid在等待哪个资源
          if (waitedthread2lock.find(nexttid) != waitedthread2lock.end()) {
            nextlock = waitedthread2lock[nexttid];
          } else {
            //说明没有环路，不发生死锁
            更新waitedthread2lock;
            break;
          }
        }
      } else {
        //说明lock空闲，直接获取
        更新lock2thread和thread2locks;
        }
    }
  }
}

2. 防死锁: 银行家算法

这个想法很简单. 仅当资源池中有足够的资源时，才将资源分配给进程，否则认为可能存在死锁的风险.

有关详细信息，请参阅此简单明了的文章:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-242408-1.html