银行家算法仿真

内容

  • python实现银行家算法

1. 实验原理

死锁

定义：在多任务系统下，当一个或多个进程等待系统资源，而资源又被进程本身或其他进程占用时，就形成了死锁

死锁的四个条件是：

  • 禁止抢占（no preemption）：系统资源不能被强制从一个进程中退出

  • 持有和等待（hold and wait）：一个进程可以在等待时持有系统资源

  • 互斥（mutual exclusion）：资源只能同时分配给一个行程，无法多个行程共享。

  • 循环等待（circular waiting）：一系列进程互相持有其他进程所需要的资源

死锁只有在四个条件同时满足时发生，预防死锁必须至少破坏其中一项。

银行家算法

  • 伪代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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;
    • P - 进程的集合
    • Mp - 进程p的最大的请求数目
    • Cp - 进程p当前被分配的资源
    • A - 当前可用的资源
    • need=max-allocate

2. 实验内容

3. 输入

allocate

1
2
3
4
0   0   1   4
1   4   3   2
1   3   5   4
1   0   0   0

max

1
2
3
4
０  ６  ５  ６
１  ９  ４  ２
１  ３  ５  ６
１  ７  ５  ０

available

1
１  ５  ２  ０

4. 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from beeprint import pp
from collections import defaultdict
plist = list()
alist = list()
flist = defaultdict(bool)
global cnt
cnt = 0


class Proc():
    pass


def setProc():
    global cnt
    global alist
    with open('alloc.txt', 'r+', encoding='utf-8') as f:
        for line in f.readlines():
            P = Proc()
            P.alloc = line.split()
            P.alloc = [int(x) for x in P.alloc]
            plist.append(P)
    with open('max.txt', 'r+', encoding='utf-8') as f:
        for line in f.readlines():
            plist[cnt].max = line.split()
            plist[cnt].max = [int(x) for x in plist[cnt].max]
            cnt += 1
    for P in plist:
        P.need = [P.max[i]-P.alloc[i] for i in range(cnt)]

    with open('avail.txt', 'r+', encoding='utf-8') as f:
        for line in f.readlines():
            alist = line.split()
        alist = [int(x) for x in alist]


def banker():
    global cnt
    global alist
    for idx, P in enumerate(plist):
        if not flist[idx]:
            tp = [alist[i]-P.need[i] for i in range(4)]
            if sorted(tp)[0] >= 0:
                flist[idx] = True
                pp("Progress {idx} finished!".format(idx=idx+1))
                alist = [alist[i] + P.alloc[i] for i in range(4)]


if __name__ == "__main__":

    setProc()
    while True:
        tp = flist.copy()
        s = set(flist[i] for i in range(cnt))
        if False not in s:
            break
        banker()
        if tp == flist:
            raise

简要说明

  • Proc类：进程数据结构，有alloc、max和need三个属性
  • plist：进程序列
  • alist：available序列

5. 结果

1
2
3
4
'Progress 2 finished!'
'Progress 3 finished!'
'Progress 4 finished!'
'Progress 1 finished!'

6. 参考资料

维基百科编者. 死锁[G/OL]. 维基百科, 2019(20191226)[2019-12-26]. https://zh.wikipedia.org/w/index.php?title=%E6%AD%BB%E9%94%81&oldid=57440760.

维基百科编者. 银行家算法[G/OL]. 维基百科, 2018(20181128)[2018-11-28]. https://zh.wikipedia.org/w/index.php?title=%E9%93%B6%E8%A1%8C%E5%AE%B6%E7%AE%97%E6%B3%95&oldid=52184777.