学习目标：

1、了解多道程序系统中，多个进程并发执行的资源分配
2、掌握死锁产生的原因，产生死锁的必要条件和处理死锁的基本方法
3、掌握银行家算法，了解资源在进程并发执行中的资源分配策略

学习内容：

考虑某一系统，它有3类资源R1，R2，R3，有5个并发进程P0，P1，P2，P3，P4。资源分配情况如下：

如果进程依次有资源请求：P0为（1,1,0），P1为（2,3,0），P3为（0,1,1），系统将怎样进行资源分配？

为什么会产生死锁？

首先我们需要知道在多道处理系统中进程是并发执行，共享消耗系统资源，这样可以提高系统的资源利用率。
比如说：有两个进程P1,P2需要竞争R1，R2两个资源，每个进程都要单独占用这两个资源一段时间

def P1():
{
	request R1
	request R2
	release R1
	release R2
}
def P2():
{
	request R2
	request R1
	release R2
	release R1
}

图中描述了各个进程是如何获取释放共享资源的过程：

P1获得了R1，P2获得了R2，由于继续执行过程中P2阻塞在R1上，R1被P1占用没有释放，但是P1要获得的R2又被P2占用着，就发生了死锁现象。
用严谨科学的术语解释死锁：在多道程序系统中，一组进程中的每一个进程均无限期的等待被该组进程中的另一个进程占用且永远不会释放的资源，这种现象称作为系统的死锁状态。

产生死锁的原因

归纳起来有两点：

• 竞争资源。多个进程所共享的资源不够，引起进程间的抢夺。我家养了两条狗，但只有一个碗，每次给的饭不够两个狗吃，那不得打起来嘛！
• 进程推进的顺序不当，进程运行过程中释放资源的顺序不当，导致死锁。还是两条狗，假如说大黄先吃，吃完了再让二黄吃，这样两条狗就不会打架
  

产生死锁的必要条件

• 互斥条件。即某一段时间资源只能被一个进程占用
• 请求和保持条件。当进程因请求资源而阻塞时，对已经获取的资源保持不妨
• 不剥夺条件。进程在获得的资源未使用完之前，不能被剥夺，只能自己释放
• 环路等待条件。在发生死锁时，必然存在一个进程-资源的环形链。

实验结果：

代码：

import numpy as np


class BankerAlgorithm():
    def __init__(self, available, max, allocation, need):
        """
        初始化参数
        :param available: 可利用资源向量
        :param max: 最大需求矩阵
        :param allocation: 分配矩阵
        :param need: 需求矩阵
        """
        self.available = available
        self.max = max
        self.allocation = allocation
        self.need = need

    def Request(self, P, request):
        """
        请求资源
        :param P: 进程号，从0开始
        :param request: 所请求的资源向量
        :return: 若成功，打印安全序列，进行分配；否则，拒绝请求。
        """
        # 判断请求向量是否小于需求向量
        length = len(request)
        i = 0
        for i in range(length):
            if request[i] > self.need[P][i]:
                break
        if i != len(request) - 1:
            print("进程{0}所需资源超过它所宣布的最大值\n".format(P))
            return

        # 判断请求向量是否小于可用资源向量
        j = 0
        for j in range(length):
            if request[i] > self.available[i]:
                break
        if j != length - 1:
            print("尚未足够的资源供{}使用", P)
            return

        # 试分配
        avi_temp = self.available
        all_temp = self.allocation
        need_temp = self.need

        for k in range(length):
            avi_temp[k] = avi_temp[k] - request[k]
            all_temp[P][k] = all_temp[P][k] + request[k]
            need_temp[P][k] = need_temp[P][k] - request[k]

        # 执行安全性算法，若存在安全序列，执行分配
        if self.Security():
            self.need = need_temp
            self.allocation = all_temp
            self.available = avi_temp
            print("请求成功！各数据结构修改为\nNeed={0}\nAllocation={1}\nAvailable{2}\n".format(self.need, self.allocation,
                                                                                   self.available))

        else:
            print("如此分配会导致系统处于不安全状态，拒绝本次分配")
            return

    def Security(self):
        """
        安全性算法，检验试分配后系统是否处于安全状态。
        :return: 若分配后系统处于安全状态，打印安全序列并返回True；否则返回False
        """
        work = self.available
        finish = [False for i in range(self.need.shape[0])]
        pro_number = self.need.shape[0]
        pro_list = [i for i in range(pro_number)]
        length = self.need.shape[1]
        secureSeq = ""

        # 寻找安全序列
        for k in range(pro_number):
            for i in pro_list:
                flag = 1
                for j in range(length):
                    if self.need[i][j] > work[j]:
                        flag = 0
                        break

                if flag and finish[i] is False:
                    work += self.allocation[i]
                    finish[i] = True
                    secureSeq += str(i) + "->"
                    pro_list.remove(i)
                    break

        for i in range(len(finish)):
            if finish[i] is not True:
                return False
        print("存在安全序列为{0}".format(secureSeq.strip("->")))
        return True


if __name__ == "__main__":
    avi = np.array([3, 3, 2])  # 可利用资源向量

    all = np.array([[2, 3, 1],
                    [1, 5, 2],
                    [2, 1, 0],
                    [3, 1, 2],
                    [1, 1, 1]])  # 分配矩阵
    max = np.array([[10, 7, 3],
                    [5, 6, 4],
                    [4, 3, 1],
                    [4, 2, 5],
                    [3, 5, 2]])  # 最大需求矩阵

    need = max - all  # 需求矩阵

    Test = BankerAlgorithm(avi, max, all, need)
    Test.Request(0, np.array([1, 1, 0]))
    Test.Request(1, np.array([2, 3, 0]))
    Test.Request(2, np.array([0, 1, 1]))

结果：

存在安全序列为2->1->3->0->4
请求成功！各数据结构修改为
Need=[[7 3 2]
 [4 1 2]
 [2 2 1]
 [1 1 3]
 [2 4 1]]
Allocation=[[3 4 1]
 [1 5 2]
 [2 1 0]
 [3 1 2]
 [1 1 1]]
Available[12 14  8]

进程1所需资源超过它所宣布的最大值

存在安全序列为0->1->2->3->4
请求成功！各数据结构修改为
Need=[[7 3 2]
 [4 1 2]
 [2 1 0]
 [1 1 3]
 [2 4 1]]
Allocation=[[3 4 1]
 [1 5 2]
 [2 2 1]
 [3 1 2]
 [1 1 1]]
Available[22 26 14]


Process finished with exit code 0

Dijkstra在1965年提出的银行家算法是著名的死锁避免算法，这个用于一个银行家给多个顾客贷款的算法可以直接用于操作系统给进程分配资源，这时只要把银行家换成操作系统，把顾客换成进程，把资金换成资源，把银行家决定是否放贷时所用的判断过程（即判断顾客是否有信誉和偿还能力）换成操作系统决定是否分配资源时所用的判断过程（即判断进程是否能及时归还资源）即可。为了描述银行家算法，下面先介绍一下系统的安全状态的概念。

一、安全序列

 注意：

（1）系统在某一时刻的安全状态可能不唯一，但这不影响对系统安全性的判断。
（2）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅可能进入死锁状态。

二、银行家算法

银行家算法的实质就是要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。即没当进程提出资源请求且系统的资源能够满足该请求时，系统将判断满足此次资源请求后系统状态是否安全，如果判断结果为安全，则给该进程分配资源，否则不分配资源，申请资源的进程将阻塞。

银行家算法的执行有个前提条件，即要求进程预先提出自己的最大资源请求，并假设系统拥有固定的资源总量。下面介绍银行家算法所用的主要的数据结构。

三、具体实例

假定操作系统中的4个进程P1、P2、P3、P4和3类资源R1、R2、R3(资源数量分别为9、3、6)，在t0时刻的资源分配情况如表2-1：

四、测试代码

#include<iostream>
using namespace std;
// p 进程数，r资源种类
int p ;
int r ;
int maxs[10][10]; //最大需求矩阵
int allocation[10][10]; //分配矩阵
int need[10][10];   //需求矩阵
int available[10]; //可用资源向量
int request[10];   //请求向量当前进程对各类资源的申请量,算法的入口参数
//输入函数
void infInput()
{
    int i,j;
    cout<<"请输入最大需求矩阵max\n";
    for(i=0; i<p; i++)
    {
        for(j=0; j<r; j++)
        {
            cin>>maxs[i][j];
        }
    }
    cout<<"请输入分配矩阵allocation\n";
    for(i=0; i<p; i++)
    {
        for(j=0; j<r; j++)
        {
            cin>>allocation[i][j];
        }
    }
    cout<<"请输入需求矩阵need\n";
    for(i=0; i<p; i++)
    {
        for(j=0; j<r; j++)
        {
            cin>>need[i][j];
        }
    }
    cout<<"请输入可用资源向量available\n";
    for(i=0; i<r; i++)
    {
        cin>>available[i];
    }
}

//比较函数
//比较进程为m中的元素全大于n中的元素返回1，否则返回0
int compare(int m[],int n[])
{
    int i;
    for(i=0; i<r; i++)
    {
        if(m[i]<n[i])
        {
            return 0;
        }
    }
    return 1;
}


//安全性检验函数，检测是否存在安全序列
int stest()
{
    int i,j,k,l,flag=0;
    int finish[p];
    int work[r];
    for(i=0; i<p; i++)
    {
        finish[i]=0;
        //vis为1即表示available满足第i进程的资源需要
    }
    for(i=0; i<r; i++)
    {
        work[i]=available[i];
    }
    cout<<"分配序列：\n";
    cout<<"            allocation            need              avilable"<<endl;
    for(k=0; k<p; k++)
    {
        for(i=0; i<p; i++)
        {
            if(finish[i]==1)
            {
                continue;
            }
            else
            {
                if(compare(work,need[i]))//available>=need
                {
                    finish[i]=1;
                    cout<<'\n'<<"进程"<<i+1<<'\t';
                    flag=1;
                    for (j =0; j<r; j++)
                    {
                        printf("  %2d ", allocation[i][j]);
                    }
                    cout<<"     ";
                    for (j = 0; j < r; j++)
                    {
                        printf("  %2d ", need[i][j]);
                    }
                    cout<<"     ";
                    for (j = 0; j <r; j++)
                    {
                        printf("  %2d ", work[j] +allocation[i][j]);
                    }
                    for(l=0; l<r; l++)
                    {
                        work[l]=work[l]+allocation[i][l];
                        //进程完成，释放资源
                    }
                    break;
                }
            }
            if(flag==1)
            {
                break;
            }
        }
    }
    cout<<'\n';
    for(l=0; l<p; l++)
    {
        if(finish[l]==0)
        {
            return 0;//不存在安全序列
        }
    }
    return 1;//存在安全序列
}

//申请进程后的安全性检验函数

void rtest(int n)
{
    int j;
    //n=n-1;
    if(compare(available,request)&&compare(need[n-1],request))//available>=request 并且 need >=request
    {
        for(j=0; j<r; j++)
        {
            allocation[n-1][j]=allocation[n-1][j]+request[j];
            need[n-1][j]=need[n-1][j]-request[j];
            available[j]=available[j]-request[j];
        }
        if(stest())
        {
            cout<<"允许"<<n<<"进程申请资源！\n";
        }
        else
        {
            cout<<"不允许"<<n<<"进程申请资源！\n";
            for(j=0; j<r; j++)
            {
                allocation[n-1][j]=allocation[n-1][j]-request[j];
                need[n-1][j]=need[n-1][j]+request[j];
                available[j]=available[j]+request[j];
            }
        }
    }
    else
    {
        cout<<"申请资源量越界！\n";
    }
}

int main()
{
    int i,n;       //n-第n个资源申请
    cout<<"请输入进程数：";
    cin>>p;
    cout<<"请输入资源种类数：";
    cin>>r;
    //默认状态4、3
    infInput();//输入函数
    if(stest()==1)
    {
        cout<<"存在安全序列，初始状态安全。\n";
    }
    else
    {
        cout<<"不存在安全序列，初始状态不安全。\n";
    }
    cout<<"请输入发出请求向量request的进程编号：";
    cin>>n;
    cout<<"请输入请求向量request\n";
    for(i=0; i<r; i++)
    {
        cin>>request[i];
    }
    rtest(n);
    return 0;
}
/*
4
3
3 2 2
6 1 3
3 1 4
4 2 2
1 0 0
5 1 1
2 1 1
0 0 2
2 2 2
1 0 2
1 0 3
4 2 0
1 1 2
*/