跳至主要內容

4.死锁

𝓳𝓭𝔂𝓼𝔂𝓪大约 10 分钟

死锁的概念

死锁的定义

所谓死锁,是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进。

死锁产生的原因

1.系统资源的竞争

只有对不可剥夺资源的竞争才可能产生死锁,对可剥夺资源的竞争是不会引起死锁的。

2.进程推进顺序非法

进程在运行过程中,请求和释放资源的顺序不当,也同样会导致死锁

死锁产生的必要条件

  1. 互斥条件
  2. 不剥夺条件
  3. 请求并保持条件
  4. 循环等待条件

注意

注意区分不剥夺条件与请求并保持条件。一个简单的例子进行说明:若你手上拿着一个苹果(即便你不打算吃),别人不能把你手上的苹果拿走,则这就是不剥夺条件;若你左手拿着一个苹果,允许你右手再去拿一个苹果,则这就是请求并保持条件。

死锁的处理策略

  1. 死锁预防
  2. 避免死锁
  3. 死锁的检测与解除

死锁处理策略的比较

资源分配策略各种可能模式主要优点主要缺点
死锁预防保守,宁可资源闲置一次请求所有资源，资源剥夺，资源按序分配适用于突发式处理的进程,不必进行剥夺效率低,进程初始化时保守,宁可资源闲置间延长:剥夺次数过多; 不便灵活申请新资源
死锁避免是“预防”和“检测”的折中（在运行时判断是否可能死锁）寻找可能的安全允许顺序不必进行剥夺必须知道将来的资源需求；进程不能被长时间阻塞
死锁检测宽松,只要允许就分配资源定期检查死锁是否已经发生不延长进程初始化时间，允许对死锁进行现场处理通过剥夺解除死锁，造成损失

死锁预防

  1. 破坏互斥条件
  2. 破坏不剥夺条件
  3. 破坏请求并保持条件
  4. 破坏循环等待条件

死锁避免

提示

在资源动态分配过程中,防止系统进入不安全状态,以避免发生死锁

系统安全状态

所谓安全状态,是指系统能按某种进程推进顺序(P1,P2,P3,…,Pn)(P_{1},P_{2},P_{3},\dots,Pn)为每个进程PiP_{i}分配其所需的资源,直至满足每个进程对资源的最大需求,使每个进程都可顺序完成。此时称(P1,P2,P3,…,Pn)(P_{1},P_{2},P_{3},\dots,Pn)为安全序列。若系统无法找到一个安全序列,则称系统处于不安全状态。
并非所有的不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状态; 反之,只要系统处于安全状态,系统便可避免进入死锁状态。

银行家算法

提示

银行家算法是最著名的死锁避免算法,其思想是:

  1. 把操作系统视为银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家货款。操作系统按照银行家制定的规则为进程分配资源。
  2. 进程运行之前先声明对各种资源的最大需求量,当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。
  3. 若超过则拒绝分配资源,若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。

数据结构

  1. 可利用资源向量 Available,含有mm个元素的数组,其中每个元素代表一类可用的资源数目
  2. 最大需求矩阵Max，定义系统中nn个进程中的每个进程对mm类资源的最大需求
  3. 分配矩阵 Allocation，系统中每类资源当前己分配给每个进程的资源数
  4. 需求矩阵 Need，表示每个进程接下来最多还需要多少资源
  5. 工作向量Work,有mm个元素,表示系统中的剩余可用资源数目。在执行安全性算法开始时,Work =Available。

存在关系Need = Max- Allocation

流程图

算法描述

安全性算法

算法举例

image.png
image.png
image.png
image.png
image.png
image.png
实验数据

实验数据借鉴的是《计算机操作系统第四版汤小丹》中银行家算法例题的数据(P121)

初始数据的输入

初始结果的输出

指定进程请求资源

  1. 指定 P1 请求资源,请求向量(1,0,2)
  1. 指定 P4 请求资源,请求向量(3,3,0)
  1. 指定 P0请求资源,请求向量(0,2,0)
  1. 指定 P0请求资源,请求向量(0,1,0)
#include "iostream"

using namespace std;

/**
 * 对于初始矩阵，这里按照教材上例题进行赋值
 * 方便调试（只需将主函数中的getInput()函数的调用注释即可）
 * 若需要输入自定义数据，则不需要改动
 */
int Max[5][3] = {7, 5, 3, 3, 2, 2, 9, 0, 2, 2, 2, 2, 4, 3, 3};
int Allocation[5][3] = {0, 1, 0, 2, 0, 0, 3, 0, 2, 2, 1, 1, 0, 0, 2};//定义已分配矩阵
int Need[5][3] = {7, 4, 3, 1, 2, 2, 6, 0, 0, 0, 1, 1, 4, 3, 1};//定义需求矩阵
int Available[3] = {3, 3, 2};
int Request[5][3];
bool Finish[5];
int safeOrder[5]; //安全序列
int Work[3];
int WorkList[5][3];


/**
 * 资源分配情况的输出
 * type = 1 --> 初始资源分配输出
 * type == 2 --> 对应的安全序列下的资源分配输出
 * @param type
 */
void outPrint(int type);

/**
 * 获取安全序列,若找不到则返回false
 * @return bool
 */
bool getSafeOrder();

/**
 * 变量初始化
 */
void stateInit();

/**
 * 数据的输入
 */
void getInput();

/**
 * 判断是否可以分配
 * @return
 */
bool isAllocation(int num);


int main() {
    cout << "银行家算法，开始:" << endl;
    getInput(); //进行信息的输入
    outPrint(1);
    if (!getSafeOrder()) {
        cout << "银行家算法，结束" << endl;
        exit(0);
    }
    while (true) {
        int num; //当前请求的进程号
        while (true) {
            cout << "请输入你想发出请求的进程号以及对应的请求向量:" << endl;
            cin >> num;
            for (int i = 0; i < 3; ++i) cin >> Request[num][i];
            if (Request[num][0] <= Need[num][0]
                && Request[num][1] <= Need[num][1]
                && Request[num][2] <= Need[num][2])
                break; //请求资源需要不大于所需要的资源，否则重新输入
        }
        // 判断是否可以分配资源
        if (isAllocation(num)) {
            // 进行资源分配
            for (int i = 0; i < 3; ++i) {
                Available[i] -= Request[num][i];
                Allocation[num][i] += Request[num][i];
                Need[num][i] -= Request[num][i];
            }

            // 分配后，输出当前的分配情况
            outPrint(1);

            // 进行安全性检查，若找不到安全序列，则恢复到之前的状态
            if (!getSafeOrder()) {
                cout << "本次分配不安全，恢复到原来的状态!" << endl;
                for (int i = 0; i < 3; ++i) {
                    Available[i] += Request[num][i];
                    Allocation[num][i] -= Request[num][i];
                    Need[num][i] += Request[num][i];
                }
                // 输出恢复后的资源分配情况
                outPrint(1);
            }
        } else {
            cout << "P" << num << "等待" << endl;
        }
        cout << "是否还需要发送请求?输入y或者n:" << endl;
        char isExit;
        cin >> isExit;
        if (isExit == 'n') {
            cout << "银行家算法结束，再见！" << endl;
            break;
        }

    }
    return 0;
}

void outPrint(int type) {
    switch (type) {
        case 1:
            cout << "以下是当前的资源分配情况:" << endl;
            cout << "资源情况\tMax\tAllocation\tNeed\tAvailable" << endl;
            cout << "进程  \tA B C\tA B C\tA B C\tA B C" << endl;
            for (int i = 0; i < 5; ++i) {
                cout << "P" << i << "    ";
                for (int j = 0; j < 3; ++j) cout << Max[i][j] << " ";
                cout << "\t";
                for (int j = 0; j < 3; ++j) cout << Allocation[i][j] << " ";
                cout << "\t";
                for (int j = 0; j < 3; ++j) cout << Need[i][j] << " ";
                if (i == 0) {
                    cout << "\t";
                    for (int j = 0; j < 3; ++j) cout << Available[j] << " ";
                }
                cout << endl;
            }
            break;
        case 2:
            cout << "以下是当前安全序列下的资源分配情况:" << endl;
            cout << "资源情况\tWork\tNeed\tAllocation\tWork+Allocation\tFinish" << endl;
            cout << "进程  \tA B C\tA B C\tA B C\tA B C" << endl;
            for (int i = 0; i < 5; ++i) {
                int order = safeOrder[i];
                cout << "P" << order << "    ";
                for (int j = 0; j < 3; ++j) cout << WorkList[order][j] << " ";
                cout << "\t";
                for (int j = 0; j < 3; ++j) cout << Need[order][j] << " ";
                cout << "\t";
                for (int j = 0; j < 3; ++j) cout << Allocation[order][j] << " ";
                cout << "\t";
                for (int j = 0; j < 3; ++j) cout << WorkList[order][j] + Allocation[order][j] << " ";
                cout << "\t";
                if (Finish[i])cout << "true";
                cout << endl; //一行结束，换行
            }
            break;
    }
}

bool getSafeOrder() {
    stateInit();
    int index = 0; //安全序列数组的下标
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 5; ++j) {
            if (!Finish[j]
                && Need[j][0] <= Work[0]
                && Need[j][1] <= Work[1]
                && Need[j][2] <= Work[2]) {
                // 可以分配资源
                safeOrder[index] = j; // 记录当前的进程号
                // 释放资源
                for (int k = 0; k < 3; ++k) {
                    WorkList[j][k] = Work[k];
                    Work[k] += Allocation[j][k];
                }
                Finish[j] = true;
                index++;
            }
        }
    }
    // 判断是否找到了安全序列
    if (index == 5) {
        // 存在安全序列
        cout << "找到安全序列:" << endl;
        for (int i = 0; i < 4; ++i) cout << "P" << safeOrder[i] << "->";
        cout << "P" << safeOrder[4];
        cout << endl;
        outPrint(2);
    } else {
        // 不存在安全序列
        cout << "找不到安全序列，系统处于不安全状态" << endl;
        return false;
    }
    return true;


}

void stateInit() {
    //Work和Finish以及安全序列数组的初始化
    for (int i = 0; i < 3; ++i) Work[i] = Available[i];
    for (int i = 0; i < 5; ++i) Finish[i] = false;
    for (int i = 0; i < 5; ++i) safeOrder[i] = 0;
}

bool isAllocation(int num) {
    bool flag = true;
    for (int i = 0; i < 3; ++i) {
        if (Request[num][i] > Available[i]) {
            flag = false;
            break;
        }
    }
    return flag;
}

void getInput() {
    cout << "请输入Max矩阵(5x3):" << endl;
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < 3; ++j)
            cin >> Max[i][j];


    cout << "请输入Allocation矩阵(5x3):" << endl;
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < 3; ++j)
            cin >> Allocation[i][j];


    // Need = Max - Allocation
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < 3; ++j)
            Need[i][j] = Max[i][j] - Allocation[i][j];


    cout << "请输入Available矩阵:" << endl;
    for (int i = 0; i < 3; ++i) cin >> Available[i];
}

死锁检测和解除

1.资源分配图

image.png|300
资源分配示例

在图2.15 所示的资源分配图中,进程 P1己经分得了两个R1资源,并又请求一个R2资源;进程P2分得了一个R1资源和一个R2资源,并又请求一个R1资源。

2.死锁定理

简化资源分配图可检测系统状态S 是否为死锁状态

  1. 在资源分配图中,找出既不阻塞又不孤点的进程PiP_{i},消去它所有的请求边和分配边, 使之成为孤立的结点。
  2. 进程PiP_{i}所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程。若能消去图中所有的边,则称该图是可完全简化的
    资源分配图的化简

S为死锁的条件是当且仅当S 状态的资源分配图是不可完全简化的,该条件为死锁定理。

3.死锁解除

一旦检测出死锁,就应立即采取相应的措施来解除死锁

  1. 资源剥夺法
  2. 撤销进程法
  3. 进程回退法
默认页脚
Copyright © 2023 𝓳𝓭𝔂𝓼𝔂𝓪