死锁入门与银行家算法

· 2022-06-03 ·

定义：
A有B的依赖资源，B有A的依赖资源，双方都不能抢夺走对方的资源，也不放弃目前拥有的，为了完成自己的目标采取互相等待,导致程序无法进行下去的现象。

死锁产生的条件，四个条件都发生时，才可能会产生死锁。

互斥使用，某些资源只能交由一个线程使用，不能共享；
不可抢占，别的线程需要急需某资源，涌终止另外正在运行的线程。
占有且等待，保持对原有资源的占有，不轻易放弃
循环等待，多个线程间的等待关系成环

解决死锁

一般互斥使用这个条件是很难破坏的，在设计层面一开始就决定了，要避免或解决死锁，就要从另外三个条件入手。

破坏“不可抢占”
当要去尝试获取另一个资源，获取不到，就放弃当下拥有的资源，避免自己手上资源被人依赖。
破坏“占有且等待”：

让程序每次执行时申请所有需要的资源，如果有部分未完成就阻塞。
破坏“循环等待”

给每个资源标上优先级序号，用线性方式去申请资源。

循环等待是因为各资源没有线性关系。




Object a = new Object();
Object b = new Object();




new Thread( ()->{
    synchronized (a) {
        System.out.println("i get a ");
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("I want get b");
        synchronized(b) {
            System.out.println("I get b");
        }
    }
});


new Thread( ()->{
    synchronized (b) {
        System.out.println("i get b");
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("I want get a");
        synchronized(a) {
            System.out.println("I get a");
        }
    }
});







数据库中的死锁

文章： https://levelup.gitconnected.com/understanding-why-a-database-deadlock-occurs-8bbd32be8026

使用jstack 可以看到


Java stack information for the threads listed above:
===================================================
"Thread-0":
        at dealock.Example.lambda$main$0(Example.java:22)
        - waiting to lock <0x000000043f83b988> (a java.lang.Object)
        - locked <0x000000043f83b978> (a java.lang.Object)
        at dealock.Example$$Lambda$14/0x0000000800066840.run(Unknown Source)
        at java.lang.Thread.run(java.base@11.0.15/Thread.java:829)
"Thread-1":
        at dealock.Example.lambda$main$1(Example.java:37)
        - waiting to lock <0x000000043f83b978> (a java.lang.Object)
        - locked <0x000000043f83b988> (a java.lang.Object)
        at dealock.Example$$Lambda$15/0x0000000800066c40.run(Unknown Source)
        at java.lang.Thread.run(java.base@11.0.15/Thread.java:829)

Found 1 deadlock.

银行家算法

事先预防策略，避免系统进入不安全状态。

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

pseudo-code

P 进程的集合
Mp 进程p的最大请求数目
Cp 进程p当前被分配资源
A 当前可用资源

while (P != ∅) {
    found = FALSE;
    foreach (p ∈ P) {
        if (Mp − Cp ≤ A) {
             /* p可以獲得他所需的資源。假設他得到資源後執行；執行終止，並釋放所擁有的資源。*/
             A = A + Cp ;
             P = P − {p};
             found = TRUE;
        }
    }
    if (! found) return FAIL;
}
return OK;