写点什么

linux 环境下实现银行间算法

作者:乌龟哥哥
  • 2022 年 6 月 12 日
  • 本文字数:6874 字

    阅读完需:约 23 分钟

1 要求

1.1 要求 1

在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量,在满足所有贷款要求时,客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在这样的描述中,银行家就好比操作系统,资金就是资源,客户就相当于要申请资源的进程。银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。为实现银行家算法,系统必须设置若干数据结构。要解释银行家算法,必须先解释操作系统安全状态和不安全状态。


特别要注意实现部分。 注意命令行参数 ./a.out 10 5 7 仅是个列子,你所涉及的程序需要支持 n 个线程对 m 个资源的并发访问请求,因此需要对上面的命令行进行扩展。

1.2 要求 2

在实验过程中,能够通过屏幕或者文件,保存每个客户线程申请资源的情况---申请多少;是否被分配等。(每个客户线程每次申请资源量不超过它们的 need 数组相应值)。

1.3 要求 3

完成的报告需要有详细的设计、代码及注释、实验结果及分析说明。

2 准备知识

2.1 银行家算法

2.1.1 什么是银行家算法?

银行家算法(Banker’s Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在 1965 年为 T.H.E 系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。  在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量,在满足所有贷款要求时,客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在这样的描述中,银行家就好比操作系统,资金就是资源,客户就相当于要申请资源的进程。  银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。为实现银行家算法,系统必须设置若干数据结构。

2.1.2 银行家算法中的数据结构

为了实现银行家算法,在系统中必须设置这样四个数据结构,分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配,以及所有进程还需要多少资源的情况。  (1) 可利用资源向量 Available。这是一个含有 m 个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。如果 Available[j] = K,则表示系统中现 Rj 类资源 K 个。  (2) 最大需求矩阵 Max。这是一个 n x m 的矩阵,它定义了系统中 n 个进程中的每个进程对 m 类资源的最大需求。如果 Max[i,j] = K,则表示进程 i 需要 Rj 类资源的最大数目为 K。  (3) 分配矩阵 Allocation。这也是一个 n x m 的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,jl = K,则表示进程 i 当前己分得 Rj 类资源的数目为 K。  (4) 需求矩阵 Need.这也是一个 n×m 的矩阵,用以表示每一个进程尚需的各类资源数。如果 Need[i,j] = K,则表示进程 i 还需要 Rj 类资源 K 个方能完成其任务。上述三个矩阵间存在下述关系:              Need[i,j] = Max[i,j] - allocation[i, j]

2.1.3 银行家算法详述

设 Request;是进程 Pi 的请求向量,如果 Requesti[j] = K,表示进程 Pi 需要 K 个 Rj 类型的资源。当 Pi 发出资源请求后,系统按下述步骤进行检査:  (1) 如果 Requesti[j] ≤ Need[i,j]便转向步骤(2);否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。  (2) 如果 Requesti[j] ≤ Available[j],便转向步骤(3);否则,表示尚无足够资源,Pi 须等待。  (3) 系统试探着把资源分配给进程 Pi,并修改下面数据结构中的数值    Available[j] = Available[j] - Requesti[j];    Allocation[i,j] = Allocation[i,j] + Requesti[j];    Need[i,j] = Need[i,j] - Requesti[j];  (4) 系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程 Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程 Pi 等待。

2.1.4 安全性算法

系统所执行的安全性算法可描述如下:  (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[j] + Allocation[i,j];    Finish[i] = true;    go to step 2;(goto 语句不推荐使用 _ )  (4)如果所有进程的 Finish[i] =true 都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

2.1.5 难点透析

本程序的难点在于安全性算法,对于一个安全的系统来说,此步骤较为容易,难在于判断不安全的系统。为什么这么说呢?由于本程序再设计寻找安全序列的部分使用 while 循环,就需要找到分别处理安全系统与不安全系统的终止循环条件,对于安全的系统,满足条件 Finish[i] = false 和 Need[i,j] ≤ Work[j] 的,必定也会按照预期的将 Finish[i] 向量全部置为 true,那是不是就可以设置一个变量来累加计数,当该变量与进程数量相等的时候,就说明已经全部置为 true 了,终止循环,也就是说系统安全。  对于不安全的系统,上述方法肯定是不行的,因为不可能将向量 Finish[i] 都置为 true ,必定存在 false。就得寻求一个跳出循环的条件,但是由于需要不断循环查找并尝试分配,寻求一个安全序列,到底该怎么算是已经找不到安全路径了呢?下面说本程序的解决办法,首先需要想到的是,当我们寻找一轮都没有找到一个可以安全执行的进程,是不是就说明往后也找不到了呢?没错,就是这样的!所以我们每次在记录 Finish[i] = true 的次数的时候,不妨把这个次数再使用另一个变量存放起来,然后在判断语句当中判断当寻找一轮下来,该值未发生改变,说明已经找不到安全的进程了,即可跳出循环,该系统不安全!

2.2 互斥锁

当多个线程几乎同时修改某一个共享数据的时候,需要进行同步控制线程同步能够保证多个线程安全访问竞争资源,最简单的同步机制是引入互斥锁。互斥锁为资源引入一个状态:锁定/非锁定某个线程要更改共享数据时,先将其锁定,此时资源的状态为“锁定”,其他线程不能更改;直到该线程释放资源,将资源的状态变成“非锁定”,其他的线程才能再次锁定该资源。互斥锁保证了每次只有一个线程进行写入操作,从而保证了多线程情况下数据的正确性。threading 模块中定义了 Lock 类,可以方便的处理锁定:创建锁 mutex = threading.Lock()#锁定 mutex.acquire()释放 mutex.release()注意:如果这个锁之前是没有上锁的,那么 acquire 不会堵塞如果在调用 acquire 对这个锁上锁之前 它已经被 其他线程上了锁,那么此时 acquire 会堵塞,直到这个锁被解锁为止定义:


1.pthread_mutex_t mutex=PTHREAD_MUTEX_INITIALIZER;2.pthread_mutex_t mutex;pthread_mutex_init(&mutex);以上两种方式都行
复制代码


实现


pthread_mutex_t mutex=PTHREAD_MUTEX_INITIALIZER;//创建互斥锁并初始化
pthread_mutex_lock(&mutex);//对线程上锁,此时其他线程阻塞等待该线程释放锁
复制代码

要执行的代码段

pthread_mutex_unlock(&mutex);//执行完后释放锁


上锁解锁过程当一个线程调用锁的 acquire()方法获得锁时,锁就进入“locked”状态。每次只有一个线程可以获得锁。如果此时另一个线程试图获得这个锁,该线程就会变为“blocked”状态,称为“阻塞”,直到拥有锁的线程调用锁的 release()方法释放锁之后,锁进入“unlocked”状态。线程调度程序从处于同步阻塞状态的线程中选择一个来获得锁,并使得该线程进入运行(running)状态。

2.3 多线程创建

2.3.1pthread 方法

2.3.1.1 说明

在 Linux 系统下,与线程相关的函数都定义在 pthread.h 头文件中。创建线程函数———pthread_create 函数


#include <pthread.h>int pthread_create(pthread_t * thread, const pthread_arrt_t* attr,void*(*start_routine)(void *), void* arg);
复制代码


(1)thread 参数是新线程的标识符,为一个整型。


(2)attr 参数用于设置新线程的属性。给传递 NULL 表示设置为默认线程属性。


(3)start_routine 和 arg 参数分别指定新线程将运行的函数和参数。start_routine 返回时,这个线程就退出了


(4)返回值:成功返回 0,失败返回错误号。


    线程id的类型是thread_t,它只在当前进程中保证是唯一的,在不同的系统中thread_t这个类型有不同的实现,调用pthread_self()可以获得当前线程的id
进程id的类型时pid_t,每个进程的id在整个系统中是唯一的,调用getpid()可以获得当前进程的id,是一个正整数值。
复制代码

2.3.1.2 代码

#include <stdio.h>#include <unistd.h>#include <pthread.h>void* myfun(void* arg);
int main(int argc, char *argv[]){ pthread_t pthread = 0; //创建一个子线程 int ret = pthread_create(&pthread, NULL, myfun, NULL); printf("parent thread id: %ld\n", pthread_self);
sleep(2); //避免主线程运行后,就死亡了,而子线程没机会 for (int i = 0; i < 5; i++) { //验证子线程,并不会执行这里面的代码,只会执行回调函数 muyfun 里面的 printf("i = %d\n", i); } return 0;}
void* myfun(void* arg){ printf("child thread id: %ld\n", pthread_self); return NULL;}
复制代码

2.3.1.3 运行结果

2.3.2 fork()函数

2.3.2.1 说明

调用 fork 时,系统将创建一个与当前进程相同的新进程。通常将原有的进程称为父进程,把新创建的进程称为子进程。子进程是父进程的一个拷贝,子进程获得同父进程相同的数据,但是同父进程使用不同的数据段和堆栈段。子进程从父进程继承大多数的属性,但是也修改一些属性。

2.3.2.2 代码

#include<stdio.h>#include<unistd.h>int main(){pid_t pid=fork();//创建子进程//如果创建子进程失败,pid的返回值小于0,子进程创建出现错误//如果创建子进程成功,pid返回值有两个,子进程返回0,父进程返回子进程IDif(pid<0){printf("创建子进程失败!\n");}
if(pid==0){printf("这个是执行子进程的输出结果,pid=%d\n",getpid());printf("他的父进程的pid为,pid=%d\n",getppid());}else{printf("这个是执行父进程的输出结果,pid=%d\n",getpid());printf("父进程创建的子进程的pid为,pid=%d\n",pid);}
}
复制代码

2.3.2.4 运行结果

3 银行家算法实现

3.1 流程图

3.2 代码

#include <stdio.h>#include <stdlib.h>#include <unistd.h>#include <pthread.h>#include <stdbool.h>#include <time.h>#define random_1(a,b) ((rand()%(b-a))+a)  //随机值将含a不含bint nResources=0,nProcesses=0;//定义输入的资源种类和进程数量int resources[99];//资源数int allocated[99][99];//为每个进程分配的实例数量int maxRequired[99][99];//每个进程的最大需求int need[99][99];//每个进程还需要的资源int safeSeq[99];//判断系统是否处于安全状态int nProcessRan = 0;//已经执行过的进程数量pthread_mutex_t lockResources;//进程互斥锁pthread_cond_t condition;//进程等待//系统如果处于安全状态返回true,不安全返回falsebool getSafeSeq();// 多进程互斥部分代码void* processCode(void* );int main() {   srand((int)time(NULL)); //设置随机数种子,防止每次产生的随机数相同        printf("请输入进程的数量:\n ");        scanf("%d", &nProcesses);        printf("请输入资源类型的种类:\n ");        scanf("%d", &nResources);        printf("请依次输出每种资源目前可得到的数量:\n");        for(int i=0; i<nResources; i++)                scanf("%d", &resources[i]);        // 每个进程已经得到的资源数量        printf("\n");        for(int i=0; i<nProcesses; i++) {                for(int j=0; j<nResources; j++)                {                                    allocated[i][j]=random_1(1,10);//假设每个进程已经得到的资源数目为0-10之间的随机数                }        }  // 每个进程需要的最大资源数量       for(int i=0; i<nProcesses; i++) {                for(int j=0; j<nResources; j++)                {                                    maxRequired[i][j]=random_1(5,10);//假设每个进程已经得到的资源数目为1-10之间的随机数                }        }               for(int i=0; i<nProcesses; i++)//                for(int j=0; j<nResources; j++)                        need[i][j] = maxRequired[i][j] - allocated[i][j];printf("进程执行前资源清单\n");  printf("***************************************************************************************\n");    printf("进程ID   已分配资源数量   进程还需要资源数量\n    ");  for(int x; x<nProcesses; x++)  {  printf("%d\t", x+1);//进程ID   for(int i=0; i<nResources; i++)                printf("%3d", allocated[x][i]);printf("\t"      );//已分配资源数量                for(int i=0; i<nResources; i++)        {        if(need[x][i]<0)        need[x][i]=0; //防止所需资源量出现负数                printf("%3d", need[x][i]);          }                  printf("\n    ");                  }        for(int i=0; i<nProcesses; i++) safeSeq[i] = -1;
if(!getSafeSeq()) { printf("系统处于不安全状态\n\n"); exit(-1); } printf("\n\n系统安全执行顺序 : "); for(int i=0; i<nProcesses; i++) { printf("%-3d", safeSeq[i]+1); } printf("\n执行进程...\n\n"); sleep(1); // 开启进程 pthread_t processes[nProcesses]; pthread_attr_t attr; pthread_attr_init(&attr); int processNumber[nProcesses]; for(int i=0; i<nProcesses; i++) processNumber[i] = i; printf("进程执行后资源清单\n"); printf("***************************************************************************************\n"); printf("进程ID 已分配资源数量 进程还需要资源数量 每种资源可用数量 执行完该进程后资源可用数量\n"); //创建进程 for(int i=0; i<nProcesses; i++) pthread_create(&processes[i], &attr, processCode, (void *)(&processNumber[i])); for(int i=0; i<nProcesses; i++) pthread_join(processes[i], NULL); printf("\n所有进程执行完毕\n"); }
// 进程代码void* processCode(void *arg) { int p = *((int *) arg); pthread_mutex_lock(&lockResources);// 资源互斥锁 while(p != safeSeq[nProcessRan])// 状态检查 pthread_cond_wait(&condition, &lockResources);//printf("进程ID \t已分配资源数量 \t进程还需要资源数量 \t每种资源可用数量\t执行完该进程后资源可用数量\n"); printf("%d\t ", p+1);//进程ID for(int i=0; i<nResources; i++)//已分配资源数量 printf("%3d", allocated[p][i]);printf("\t" ); for(int i=0; i<nResources; i++)//进程还需要资源数量 { if(need[p][i]<0) need[p][i]=0; //防止所需资源量出现负数 printf("%3d", need[p][i]); } printf("\t "); for(int i=0; i<nResources; i++)//每种资源可用数量 printf("%3d", resources[i]);printf("\t"); for(int i=0; i<nResources; i++) resources[i] += allocated[p][i]; for(int i=0; i<nResources; i++)//执行完该进程后资源可用数量 printf("%3d", resources[i]);printf("\t\n"); sleep(1); // 进程状态 nProcessRan++; pthread_cond_broadcast(&condition);//解锁 pthread_mutex_unlock(&lockResources); pthread_exit(NULL);}
复制代码

3.3 运行结果(随机性)



编译时不要忘记加-pthread

发布于: 刚刚阅读数: 3
用户头像

乌龟哥哥

关注

正在努力寻找offer的大四小菜鸟 2021.03.16 加入

擅长 Hbuilder、VS Code、MyEclipse、AppServ、PS 等软件的安装与卸载 精通 Html、CSS、JavaScript、jQuery、Java 等单词的拼写 熟悉 Windows、Linux、 等系统的开关机 看–时间过得多快,不说了,去搬砖了

评论

发布
暂无评论
linux环境下实现银行间算法_6月月更_乌龟哥哥_InfoQ写作社区