1 实验题目要求

1.1

查看P231页中编程项目，里面有对银行家算法的具体要求，特别要注意实现部分。 注意命令行参数 ./a.out 10 5 7 仅是个列子，你所涉及的程序需要支持n个线程对m个资源的并发访问请求，因此需要对上面的命令行进行扩展。

1.2

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

1.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_tmutex=PTHREAD_MUTEX_INITIALIZER;

2.pthread_mutex_tmutex;

pthread_mutex_init(&mutex);

以上两种方式都行

实现

pthread_mutex_tmutex=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>

intpthread_create(pthread_t*thread, constpthread_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);

intmain(intargc, char*argv[])

{

   pthread_tpthread=0;  //创建一个子线程

   intret=pthread_create(&pthread, NULL, myfun, NULL);

   printf("parent thread id: %ld\n", pthread_self);

   sleep(2);  //避免主线程运行后，就死亡了，而子线程没机会

   for (inti=0; i<5; i++) {  //验证子线程，并不会执行这里面的代码，只会执行回调函数 muyfun 里面的

       printf("i = %d\n", i);

   }

   

   return0;

}

void*myfun(void*arg)

{

   printf("child thread id: %ld\n", pthread_self);

   returnNULL;

}

2.3.1.3 运行结果

2.3.2 fork()函数

2.3.2.1说明

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

2.3.2.2代码

#include<stdio.h>

#include<unistd.h>

intmain()

{

pid_tpid=fork();//创建子进程

//如果创建子进程失败，pid的返回值小于0,子进程创建出现错误

//如果创建子进程成功，pid返回值有两个，子进程返回0,父进程返回子进程ID

if(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不含b

intnResources=0,nProcesses=0;//定义输入的资源种类和进程数量

intresources[99];//资源数

intallocated[99][99];//为每个进程分配的实例数量

intmaxRequired[99][99];//每个进程的最大需求

intneed[99][99];//每个进程还需要的资源

intsafeSeq[99];//判断系统是否处于安全状态

intnProcessRan=0;//已经执行过的进程数量

pthread_mutex_tlockResources;//进程互斥锁

pthread_cond_tcondition;//进程等待

//系统如果处于安全状态返回true，不安全返回false

boolgetSafeSeq();

// 多进程互斥部分代码

void*processCode(void* );

intmain() {

    srand((int)time(NULL)); //设置随机数种子，防止每次产生的随机数相同

       printf("请输入进程的数量：\n ");

       scanf("%d", &nProcesses);

       printf("请输入资源类型的种类：\n ");

       scanf("%d", &nResources);

       printf("请依次输出每种资源目前可得到的数量：\n");

       for(inti=0; i<nResources; i++)

               scanf("%d", &resources[i]);

       // 每个进程已经得到的资源数量

       printf("\n");

       for(inti=0; i<nProcesses; i++) {

               for(intj=0; j<nResources; j++)

               {            

                       allocated[i][j]=random_1(1,10);//假设每个进程已经得到的资源数目为0-10之间的随机数

               }

       }

   // 每个进程需要的最大资源数量

      for(inti=0; i<nProcesses; i++) {

               for(intj=0; j<nResources; j++)

               {            

                       maxRequired[i][j]=random_1(5,10);//假设每个进程已经得到的资源数目为1-10之间的随机数

               }

       }

     

       for(inti=0; i<nProcesses; i++)//

               for(intj=0; j<nResources; j++)

                       need[i][j] =maxRequired[i][j] -allocated[i][j];

printf("进程执行前资源清单\n");

   printf("***************************************************************************************\n");    

   printf("进程ID   已分配资源数量   进程还需要资源数量\n    ");

   for(intx; x<nProcesses; x++)

   {

   printf("%d\t", x+1);//进程ID

    for(inti=0; i<nResources; i++)

               printf("%3d", allocated[x][i]);printf("\t"      );//已分配资源数量

               for(inti=0; i<nResources; i++)

       {

       if(need[x][i]<0)

       need[x][i]=0; //防止所需资源量出现负数

               printf("%3d", need[x][i]);

        }

                 printf("\n    ");

               

   }

       for(inti=0; i<nProcesses; i++) safeSeq[i] =-1;

       if(!getSafeSeq()) {

               printf("系统处于不安全状态\n\n");

               exit(-1);

       }

       printf("\n\n系统安全执行顺序 : ");

       for(inti=0; i<nProcesses; i++) {

               printf("%-3d", safeSeq[i]+1);

       }

       printf("\n执行进程...\n\n");

       sleep(1);

   // 开启进程

   pthread_tprocesses[nProcesses];

       pthread_attr_tattr;

       pthread_attr_init(&attr);

   intprocessNumber[nProcesses];

   for(inti=0; i<nProcesses; i++)

   processNumber[i] =i;

   printf("进程执行后资源清单\n");

   printf("***************************************************************************************\n");

   printf("进程ID    已分配资源数量 进程还需要资源数量 每种资源可用数量 执行完该进程后资源可用数量\n");

   //创建进程

       for(inti=0; i<nProcesses; i++)

               pthread_create(&processes[i], &attr, processCode, (void*)(&processNumber[i]));

       for(inti=0; i<nProcesses; i++)

               pthread_join(processes[i], NULL);

       printf("\n所有进程执行完毕\n");

}

// 进程代码

void*processCode(void*arg) {

       intp=*((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(inti=0; i<nResources; i++)//已分配资源数量

               printf("%3d", allocated[p][i]);printf("\t"      );

       for(inti=0; i<nResources; i++)//进程还需要资源数量

       {

       if(need[p][i]<0)

       need[p][i]=0; //防止所需资源量出现负数

               printf("%3d", need[p][i]);

        }

                 printf("\t    ");

       for(inti=0; i<nResources; i++)//每种资源可用数量

               printf("%3d", resources[i]);printf("\t");

   for(inti=0; i<nResources; i++)

               resources[i] +=allocated[p][i];

       for(inti=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