Framist's Little House

◇ 自顶而下 - 面向未来 ◇

0%

【操作系统概念 - 作业 7】Deadlocks

发表于 更新于 分类于 ， ，

Operating System Concepts Exercises 7

Deadlocks

操作系统作业 7

  • 7.1, 7.3, 7.10
  • 7.17, 7.18, 7.22, 7.25, 7.26

每题最后一个引用块是老师提供的参考答案

Practice Exercises

7.1, 7.3, 7.10

答：

  • 车让车
  • 人撞人
  • 保险箱里放钥匙

Answer:

  • Two cars crossing a single-lane bridge from opposite directions.

  • A person going down a ladder while another person is climbing up the ladder.

  • Two trains traveling toward each other on the same track.

  • 两辆汽车从相反方向穿过单车道的桥。

  • 一个人从梯子上下来，而另一个人正在爬上梯子。

  • 两辆火车在同一轨道上向对方行驶。

7.3 Consider the following snapshot of a system:

考虑下面的系统快照：

1
2
3
4
5
6
7
8
        Allocation   Max    Available
        ——————————   ———    —————————
        ABCD        ABCD    ABCD
P0      0012        0012    1520
P1      1000        1750
P2      1354        2356
P3      0632        0652
P4      0014        0656

Answer the following questions using the banker’s algorithm:

a. What is the content of the matrix Need?

矩阵Need的内容是什么？

答：

1
2
3
4
5
6
7
8
        Need
        ————
        ABCD
P0      0000
P1      0750
P2      1002
P3      0020
P4      0642

b. Is the system in a safe state?

系统是否处于安全状态？

答：是。

c. If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately?

如果进程 P1 的请求到达 (0,4,2,0)，该请求能否立即被批准？

答：是

1
2
3
4
5
6
7
8
9
P0 -> P2 -> P1 -> P3 -> P4 -> 
============================================================
进程    	Max     		Allo    		Need
P0      [0 0 1 2]       [0 0 1 2]       [0 0 0 0]
P1      [1 7 5 0]       [1 4 2 0]       [0 3 3 0]
P2      [2 3 5 6]       [1 3 5 4]       [1 0 0 2]
P3      [0 6 5 2]       [0 6 3 2]       [0 0 2 0]
P4      [0 6 5 6]       [0 0 1 4]       [0 6 4 2]
当前剩余资源: [1 1 0 0]

Answer:

a. The values of Need for processes P0 through P4 respectively are (0, 0, 0, 0), (0, 7, 5, 0), (1, 0, 0, 2), (0, 0, 2, 0), and (0, 6, 4, 2).

b. The system is in a safe state? Yes. With Available being equal to (1, 5, 2, 0), either process P0 or P3 could run. Once process P3 runs, it releases its resources, which allow all other existing processes to run.

c. The request can be granted immediately? This results in the value of Available being (1, 1, 0, 0). One ordering of processes that can finish is P0, P2, P3, P1, and P4. So the request can be granted.

a. 过程 P0 到 P4 的需要值分别是（0，0，0，0），（0，7，5，0），（1，0，0，2），（0，0，2，0），和（0，6，4，2）。

b. 系统处于安全状态？是的。由于 Available 等于（1，5，2，0），进程 P0 或 P3 都可以运行。一旦进程 P3 运行，它就会释放其资源，从而使所有其他现有的进程得以运行。

c. 该请求可以立即被批准？这导致 Available 的值为（1，1，0，0）。可以完成的进程的一个排序是 P0, P2, P3, P1, 和 P4。所以该请求可以被批准。

7.10 Is it possible to have a deadlock involving only one single-threaded process? Explain your answer.

有可能出现只涉及一个单线程进程的死锁吗？解释一下你的答案。

答：是。如自己请求了自己还未释放的资源。

Answer:

Yes. If a Process acquires a non-recursive lock twice.

img

Exercises

7.17, 7.18, 7.22, 7.25, 7.26

7.17 Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock free.

考虑一个由四个相同类型的资源组成的系统，由三个进程共享，每个进程最多需要两个资源。证明该系统是无死锁的。

答：根据抽屉原理，最差出现以下情况

1
2
3
4
5
        Allocation   Max    Available
        ——————————   ———    —————————
P0      1            2            1
P1      1            2
P2      1            2

这是又有一个进程请求新的一个资源，它在请求结束后总能释放 2 个资源，更不会产生死锁。

Answer:

Yes, this system is deadlock-free.

Proof by contradiction. Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting for one more. Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources and, therefore it will return its resources when done.

是的，这个系统是无死锁的。

通过矛盾证明。假设该系统是死锁的。这意味着每个进程持有一个资源，并在等待另一个资源。由于有三个进程和四个资源，一个进程必须能够获得两个资源。这个进程不需要更多的资源，因此，它将在完成后归还其资源。

7.18 Consider a system consisting of $m$ resources of the same type being shared by $n$ processes. A process can request or release only one resource at a time. Show that the system is deadlock free if the following two conditions hold:

考虑一个由 n 个进程共享的相同类型的$m$资源组成的系统。一个进程一次只能请求或释放一个资源。说明如果以下两个条件成立，该系统是无死锁的。

a. The maximum need of each process is between one resource and $m$ resources.

每个进程的最大需求是在一个资源和$m$个资源之间。

b. The sum of all maximum needs is less than $m+n$.

所有最大需求的总和小于$m+n$。

答：根据抽屉原理，最差出现以下情况

1
2
3
4
5
6
        Allocation   Max       Available
        ——————————   ———       —————————
P0      m/n(-1)      m/n+1(-1)     1
P1      m/n          m/n+1
..
Pn      m/n          m/n+1

可以预见，这时向 P0 分配一个资源可解决问题。

Answer:

Suppose N = Sum of all Need(i), A = Sum of all Allocation(i), M = Sum of all Max(i).

Use contradiction to prove.

Assume this system is not deadlock free. If there exists a deadlock state, then A = m because there’s only one kind of resource and resources can be requested and released only one at a time.

From condition b, N + A = M < m + n. So we get N + m < m + n. So we get N < n. It shows that at least one process i that Need(i) = 0. (contradict with necessary condition of deadlock)

From condition a, Pi can release at least 1 resource.

So there are n-1 processes sharing m resources now, condition a and b still hold. Go on the argument, no process will wait permanently, so there’s no deadlock.

假设 N=所有 Need(i) 之和，A=所有 Allocation(i) 之和，M=所有 Max(i) 之和。

用矛盾法来证明。

假设这个系统不是无死锁的。如果存在死锁状态，那么A=m，因为只有一种资源，而且资源一次只能请求和释放一个。

从条件 b 来看，N + A = M < m + n. 所以我们得到 N + m < m + n. 所以我们得到 N < n. 这表明至少有一个进程 i，Need(i) = 0. (与死锁的必要条件相矛盾)

从条件 a 来看，Pi 至少可以释放 1 个资源。

所以现在有 n-1 个进程共享 m 个资源，条件 a 和 b 仍然成立。继续论证，没有进程会永久等待，所以不存在死锁。

7.22 Consider the following snapshot of a system:

Using the banker’s algorithm, determine whether or not each of the following states is unsafe. If the state is safe, illustrate the order in which the processes may complete. Otherwise, illustrate why the state is unsafe.

使用银行家算法，确定以下每个状态是否不安全。如果该状态是安全的，说明这些过程可能完成的顺序。否则，说明为什么该状态是不安全的。

1
2
3
4
5
6
7
8
	    Allocation 	 Max
        ——————————   ———
	    ABCD 		ABCD
P0 	    3014 		5117
P1 	    2210 		3211
P2 	    3121 		3321
P3 	    0510 		4612
P4 	    4212 		6325

a. Available = (0, 3, 0, 1)

b. Available = (1, 0, 0, 2)

Answer:

a. Not safe. Processes P2, P1, and P3 are able to finish, but no remaining processes can finish.

b. Safe. Processes P1, P2, and P3 are able to finish. Following this, processes P0 and P4 are also able to finish.

7.25

A single-lane bridge connects the two Vermont villages of North Tunbridge and South Tunbridge. Farmers in the two villages use this bridge to deliver their produce to the neighboring town. The bridge can become deadlocked if a northbound and a southbound farmer get on the bridge at the same time. (Vermont farmers are stubborn and are unable to back up.) Using semaphores and/or mutex locks, design an algorithm in pseudocode that prevents deadlock. Initially, do not be concerned about starvation (the situation in which northbound farmers prevent southbound farmers from using the bridge, or vice versa).

一座单车道的桥梁连接着佛蒙特州的两个村庄北屯桥和南屯桥。这两个村庄的农民利用这座桥将他们的产品运送到邻近的城镇。如果一个北行的农民和一个南行的农民同时上桥，这座桥就会陷入僵局。(佛蒙特州的农民很顽固，无法退让。) 使用信号量和/或互斥锁，用伪代码设计一个算法，以防止死锁。最初，不要担心饥饿问题（北行农民阻止南行农民使用桥梁的情况，反之亦然）。

使用信号量实现：

1
2
3
4
5
6
7
int 农民上桥(){
    wait(桥);
    上桥();
    下桥();
    singal(桥)
    exit(0);
}

Answer:

img

7.26 Modify your solution to Exercise 7.25 so that it is starvation-free.

修改你对练习 7.25 的解答，使其没有饥饿。

1
2
3
4
5
6
7
8
9
10
11
12
FIFO 等待队列[];

int 农民上桥(){
    进入(等待队列);
    while(查询是否下一个出(等待队列))==false)
        ;
    wait(桥);
    上桥();
    下桥();
    singal(桥);
    exit(0);
}

Answer:

img

img

注：

参考资料：

[1] 银行家算法的 Python 代码实现 - 操作系统_Xerrors-CSDN 博客

稍作修改如下：

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import numpy as np

def security(work, need, allocation):
    """安全性算法"""
    n = need.shape[0]
    finish = np.array([False] * n, dtype=bool)
    while not(finish.all()):
        flag = False
        for i in range(n):
            if not finish[i] and (need[i] <= work).all():
                print("P{}".format(i), end=' -> ')
                flag = True
                work += allocation[i]
                finish[i] = True
                break
        if not flag:
            return False
    print('安全')
    return True


def printTable(available, max_table, allocation, need):
    """输出表格"""
    print("=="*30)
    print("进程\tMax\tAllo\tNeed")
    for i in range(5):
        print("P{}\t{}\t{}\t{}".format(
            i, max_table[i], allocation[i], need[i]))
    print("当前剩余资源：", available)


def loadTestData():
    """导入测试数据"""
    # available, max_table, allocation
    return (np.array([1,0,0,2], dtype=int),
        np.array([[5,1,1,7],
                  [3,2,1,1],
                  [3,3,2,1],
                  [4,6,1,2],
                  [6,3,2,5]], dtype=int),
        np.array([[3,0,1,4],
                  [2,2,1,0],
                  [3,1,2,1],
                  [0,5,1,0],
                  [4,2,1,2]], dtype=int))


def main():
    """主循环算法"""
    # 导入测试数据，不用一次次手动输入
    available, max_table, allocation = loadTestData()
    need = max_table - allocation

    # 不用计算出剩余资源
    # for i in allocation:
    #     available -= i

    printTable(available, max_table, allocation, need)

    while (need != 0).any():
        proc_ind, req = input("输入请求，如：P1, 1 0 1: ").split(',')
        proc_ind = int(proc_ind[1:])
        req = np.array(req.split(), dtype=int)

        # 判断合法性
        if (req > max_table[proc_ind]).any():
            print("[ERROR] 输入有误，重新输入")

        # 判断安全性
        else:
            available -= req
            allocation[proc_ind] += req
            need[proc_ind] -= req
            if security(available.copy(), need, allocation):
                printTable(available, max_table, allocation, need)
                continue
            else:
                print("[ERROR] 不安全，不能分配")
                available += req
                allocation[proc_ind] -= req
                need[proc_ind] += req


if __name__ == '__main__':
    main()

[2] Operating System Concepts – 9th Edition 及其答案