银行家算法的实验报告

银行家算法的实验报告

一、实验内容

银行家算法是避免死锁的一种重要方法，本实验要求编写和调试一个简单的银行家算法程序。

1．设计进程对各类资源最大申请表示及初值的确定。
2．设定系统提供资源的初始状况。
3．设定每次某个进程对各类资源的申请表示。
4．编制程序，依据银行家算法，决定其资源申请是否得到满足。
5．显示资源申请和分配时的变化情况。

二、背景知识

1．死锁的相关知识。在多道程序环境中，多个进程可以竞争有限数量的资源。当一个进程申请资源时，如果这时没有可用资源，那么这个进程进入等待状态。有时，如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变状态。这种情况称为死锁。

2．银行家算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

3．系统安全性检查。

1）设置两个向量：
工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;
工作向量Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］=false; 当有足够资源分配给进程时， 再令Finish［i］=true。

2）从进程集合中找到一个能满足下述条件的进程： 
Finish［i］=false;
Need［i,j］≤Work［j］；若找到，执行 (3)，否则，执行 (4)

3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work［j］=Work［i］+Allocation［i,j］;
Finish［i］=true;
go to step 2;

4）如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态;

三、思路

四、核心代码(添加注释)

#include <malloc.h> 
#include <string.h>
#include <iostream> 
using namespace std;

struct p {
    int Max[100][100];//最大需求矩阵 
    int Allocation[100][100];//分配矩阵 
    int Need[100][100];//需求矩阵 
    int Available[100];//可利用资源 
    int Resource[100];//总资源 
    int Work[100];//正工作资源 
    int Finish[100]; //判断进程是否已完成 
    int List[100];//存放安全序列的下标序列 
};
class yinhangjia {
public:
    void initial(int N, int M, struct p* s); //输入数据 
    void printState(int N, int M, struct p* s);//输出当前状态表 
    int isfinish(int N, int M, struct p* s, int C);//判断是否满足资源更换条件 
    int issafe(int N, int M, struct p* s);//判断是否为合法资源 
    void printList(int N, int M, struct p* s);//输出安全序列表 
    void reqresource(int N, int M, struct p* s, int i, int Request[]);//输入更改资源，并判断是否合法 
};



void yinhangjia :: initial(int N, int M, struct p* s)
//创建初始状态：先输入 Resource、Max和 Allocation，再计算出 Need、Available。   
{
    int i, j;
    cout << "Resource--输入M种资源的总数量:\n";
    for (i = 0; i < M; i++)
    {
        cin >> s->Resource[i];
        s->Available[i] = s->Resource[i];
    }
    cout << "Max--输入N个进程分别对M种资源的最大需求量:\n";
    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            cin >> s->Max[j][i];
    cout << "Allocation--输入N个进程获得M种资源的数量:\n";
    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            cin >> s->Allocation[j][i];
    /****************************************/
    for (j = 0; j < N; j++)//求出需求need量 ，通过最大需求量-已经占用的资源数量 
        for (i = 0; i < M; i++)
            s->Need[j][i] = s->Max[j][i] - s->Allocation[j][i];
    for (j = 0; j < M; j++)//求出可用Available量  
        for (i = 0; i < N; i++)
            s->Available[j] = s->Available[j] - s->Allocation[i][j];
}

void yinhangjia ::printState(int N, int M, struct p* s)
//输出当前的状态表|Process     |Max         |Allocation  |Need         |Available   | 
{
    int j, i;
    cout << "\n状态表如下:\n";
    cout << "|Process     ";
    cout << "|Max";
    for (int k = 0; k < M * 4 - 3; k++)
        cout << " ";
    cout << "|Allocation";
    for (int k = 0; k < M * 4 - 10; k++)
        cout << " ";
    cout << "|Need";
    for (int k = 0; k < M * 4 - 4; k++)
        cout << " ";
    cout << "|Available";
    for (int k = 0; k < M * 4 - 9; k++)
        cout << " ";
    cout << "|\n";
    for (i = 0; i < N; i++)
    {
        cout << i;
        for (int k = 0; k < M; k++)
            cout << s->Max[i][k];
        cout << "|";
        for (int k = 0; k < M; k++)
            cout << s->Allocation[i][k];
        cout << "|";
        for (int k = 0; k < M; k++)
            cout << s->Need[i][k];
        cout << "|";
        if (i == 0) {
            for (int k = 0; k < M; k++)
                cout << s->Available[k];
            cout << "|";
        }
        cout << endl;
    }
}

int yinhangjia :: isfinish(int N, int M, struct p* s, int C)
//返回同时满足两个条件{①Finish[i]=false;  ②Need[i][j]≤Work[j]}的进程下标 i(修改Finish[i]=true)，否则返回-1。 
{
    int i, j, count, b = 0;
    static int k = 0;
    //printf("%d\n",k);
    cout << k << endl;
    for (i = C; i < N; i++)
    {
        for (j = 0, count = 0; j < M; j++)//判断单个进程是否符合安全序列 
            if (s->Finish[i] == 0 && s->Need[i][j] <= s->Work[j])
            {
                count++;
            }
        if (count == M)
        {
            for (j = 0; j < M; j++)
                s->Work[j] += s->Allocation[i][j];//进程完成后，释放的空间加到现在闲置的空间内 
            s->Finish[i] = 1;//将进程修改为已完成状态 
            k++;
            if (k == N)
                k = 0;
            //printf("%d\n",k);
            cout << k << endl;
            return i;
        }
        if (i == N - 1 && k < N) {
            i = -1;
            b++;
        }
        if (b == 2)
            break;
    }
    return -1;
}

int yinhangjia :: issafe(int N, int M, struct p* s)
//判定当前状态是否为安全状态 （返回 true 或 false），把安全序列的下标放入 List[N]数组。 
{
    int i, a, count = 0, C = 0;
    for (i = 0; i < M; i++)
        s->Work[i] = s->Available[i];//工作资源数 
    for (i = 0; i < N; i++)
        s->Finish[i] = 0;
    for (i = 0; i < N; i++)
    {
        a = isfinish(N, M, s, C);
        //printf("%d ?a\n",a);
        //cout << a << endl;
        if (a != -1)
        {
            s->List[i] = a;
            C = a;
            count++;
            //printf("%d  ,\n",count);
            //cout << count << endl;
        }
        else if (a == -1) C = 0;
    }
    if (count == N)
        return 1;
    else
        return 0;
}

void yinhangjia :: printList(int N, int M, struct p* s)
//输出安全序列表|Process |Work  |Need   |Allocation  |Work+Alloc   |Finish  | 
{
    int i, j;
    cout << "\n安全序列表如下:\n";
    cout << "|Process     ";
    cout << "|Work";
    for (int k = 0; k < M * 4 - 4; k++)
        cout << " ";
    cout << "|Need";
    for (int k = 0; k < M * 4 - 4; k++)
        cout << " ";
    cout << "|Allocation";
    for (int k = 0; k < M * 4 - 10; k++)
        cout << " ";
    cout << "|Work+Alloc";
    for (int k = 0; k < M * 4 - 10; k++)
        cout << " ";
    cout << "|Finish";
    for (int k = 0; k < M * 4 - 6; k++)
        cout << " ";
    cout << endl;
    for (j = 0; j < M; j++)
    {
        s->Work[j] = s->Available[j];
    }
    for (i = 0; i < N; i++)
    {
        cout << s->List[i];
        for (int k = 0; k < M; k++)
            cout << s->Work[k];
            cout << "|";
        for (int k = 0; k < M; k++)
            cout << s->Need[s->List[i]][k];
            cout << "|";
        for (int k = 0; k < M; k++)
            cout << s->Allocation[s->List[i]][k];
            cout << "|";
        for (int k = 0; k < M; k++)
            cout << s->Work[k] + s->Allocation[s->List[i]][k];
            cout << "|true";
        for (int k = 0; k < M * 4 - 4; k++)
            cout << " ";
            cout << "|\n";
        for (j = 0; j < M; j++)
            s->Work[j] += s->Allocation[s->List[i]][j];
    }
}

void yinhangjia :: reqresource(int N, int M, struct p* s, int i, int Request[])
//表示第 i个进程请求 M类资源 request[M] 
{
    int flag, count1, count2;
    int j;
    //Step1:  判断条件 Request[j]≤Need[i][j] 
    for (j = 0, count1 = 0; j < M; j++)
        if (Request[j] <= s->Need[i][j])
            count1++;
    //Step2:  判断条件 Request[j]≤Available[j]
    for (j = 0, count2 = 0; j < M; j++)
        if (Request[j] <= s->Available[j])
            count2++;
    if (count2 != M)  
        cout << "\n尚无足够的资源，第" << i << "个进程堵塞。\n";
    //Step3:  预先分配 
    if (count2 == M && count1 == M)
    {
        for (j = 0; j < M; j++)
        {
            s->Available[j] = s->Available[j] - Request[j];
            s->Allocation[i][j] = s->Allocation[i][j] + Request[j];
            s->Need[i][j] = s->Need[i][j] - Request[j];
            //printf("%d %d %d\n",s->Available[j],s->Allocation[i][j],s->Need[i][j]);
            //cout << s->Available[j];
            //cout << s->Allocation[i][j];
            //cout << s->Need[i][j];
            //cout << endl;
        }
        if (issafe(N, M, s) == 0)
        { 
            cout << "\n不存在安全序列，不是安全状态。\n";
            for (j = 0; j < M; j++)
            {
                s->Available[j] = s->Available[j] + Request[j];
                s->Allocation[i][j] = s->Allocation[i][j] - Request[j];
                s->Need[i][j] = s->Need[i][j] + Request[j];
            }
        }
        else
        {
            cout << "\n是安全序列分配成功!\n";
        yinhangjia:printList(N, M, s);
        }
    }
}
int main(void)
{
    int reqid = -1, j, req[100];
    struct p s;
    int N, M;
    cout << "please input MAX resources and MAX processes :";
    cin >> M >> N;
    yinhangjia a;//构造银行家类a
    a.initial(N, M, &s); //创建数据 
    if (a.issafe(N, M, &s) == 0)
    {
        printf("Initial state is unsafe!\n");
    }
    else
    {
       a.printState(N, M, &s); //输出当前状态表 
        cout << "\nInitial state is safe!\n" << endl;
        a.printList(N, M, &s); //输出安全序列表 
        cout << "Input the id of request process:"  ;
        cin >> reqid;
        while (reqid >= 0 && reqid < N)   //输入进程 id是否合法 
        {  
            cout << "Input request resources:";
                for (j = 0; j < M; j++)
                {
                    cin >> req[j];
                }
            a.reqresource(N, M, &s, reqid, req);
            a.printState(N, M, &s);
            cout << "Input the id of request process:";
            cin >> reqid;
        }
        cout << "\n输入错误，退出程序!\n";
    }
    return 0;
}

五、运行结果

输出状态表和安全序列表

若有足够的资源给请求的资源，则输出新的状态表

若没有足够的资源给请求的资源，则显示进程堵塞并输出状态表

六、结论
1.银行家算法是一种用来避免操作系统死锁出现的有效算法。

2.死锁：是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

3.死锁的发生必须具备以下四个必要条件：

1）互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。

2）请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

3）不抢占条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

4）循环等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

4.银行家算法是避免死锁的一种重要方法，防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。

5.为实现银行家算法，系统必须设置若干数据结构，同时要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

6.安全序列:是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

7.安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。

8.安全状态一定是没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁文章来源地址https://www.toymoban.com/news/detail-425938.html

到了这里，关于银行家算法的实验报告的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！