操作系统实验实现银行家算法

网友投稿 1031 2022-05-30

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_t mutex=PTHREAD_MUTEX_INITIALIZER; 2.pthread_mutex_t mutex; pthread_mutex_init(&mutex); 以上两种方式都行

1

2

3

4

实现

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

1

2

3

要执行的代码段

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

上锁解锁过程

当一个线程调用锁的acquire()方法获得锁时,锁就进入“locked”状态。

每次只有一个线程可以获得锁。如果此时另一个线程试图获得这个锁,该线程就会变为“blocked”状态,称为“阻塞”,直到拥有锁的线程调用锁的release()方法释放锁之后,锁进入“unlocked”状态。

线程调度程序从处于同步阻塞状态的线程中选择一个来获得锁,并使得该线程进入运行(running)状态。

2.3 多线程创建

2.3.1pthread方法

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

创建线程函数———pthread_create函数

#include int pthread_create(pthread_t * thread, const pthread_arrt_t* attr,void*(*start_routine)(void *), void* arg);

1

2

(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,是一个正整数值。

1

2

3

#include #include #include 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; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

2.3.2 fork()函数

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

#include #include int main() { pid_t pid=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); } }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

3 银行家算法实现

3.1 流程图

3.2代码

#include #include #include #include #include #include #define random_1(a,b) ((rand()%(b-a))+a) //随机值将含a不含b int 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,不安全返回false bool 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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

操作系统实验:实现银行家算法

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

3.3 运行结果(随机性)

编译时不要忘记加-pthread

任务调度 数据结构

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:【AI理论】华为提出自动编码变换网络AET:用无监督逼近全监督效果
下一篇:疯狂Java之学习笔记(25)-------------修饰符
相关文章