当前位置:文档之家› 银行家算法习题

银行家算法习题

银行家算法习题
银行家算法习题

银行家算法习题

假设一家银行拥有资金2000万,现有10家公司向其贷款进行筹建,每家均需300万才能建成。如果这家银行将2000万的资金平均贷给这10家公司,则每家公司将得到200万的贷款,都不能筹建成功,也就不能还贷,那么这10家公司都将“死锁”。若这家银行给其中的4家各贷300万,另4家各贷200万,这样将还有2家公司得不到贷款,不能开工建设,但有4家可筹建完成,这4家公司运营所得利润可向该银行还贷,银行可以利用还贷的资金继续向其他的公司贷款,从而保证所有公司筹建成功投入运营。

银行家算法是为了把一定数量的资金供多个用户周转,并保证资金的安全。银行家算法可归纳为:

(1)当一个用户对资金的最大需求量不超过银行家现有的资金时,就可接纳该用户。

(2)用户可以分期贷款,但贷款总数不能超过最大需求量。

(3)当银行家现有的资金不能满足用户的尚需贷款数时,可以推迟支付,但总能使用户在有限的时间里得到贷款。

(4)当用户得到所需的全部资金后,一定能在有限时间里归还所有的资金。

我们可以把操作系统看作银行家,把进程看作用户,把操作系统管理的资源看作银行家管理的资金,把进程向操作系统请求资源看作用户向银行家贷款。

操作系统按照银行家规定的规则为进程分配资源。当进程首次申请资源时,要测试该进程对资源的最大需求量。如果系统现存的资源可以满足它的最大需求量,则按当前的申请量分配资源,否则推后分配。

当进程在执行中继续申请资源时,先测试该进程已占有的资源数与本次申请的资源数之和是否超过该进程对资源的最大需求量。如果超过,则拒绝分配资源,否则再测试系统现存的资源能否满足该进程尚需的最大资源量。若能满足,则按当前的申请量分配资源,否则也要推迟分配。

这样做,能保证在任何时刻至少有一个进程可以得到所需要的全部资源而执行到结束,执行结束后归还资源,并把这些资源加入到系统的剩余资源中,用同样的方法为其他的进程分配资源。

银行家算法的数据结构包括:

(1)可用资源向量Available。

(2)最大需求矩阵Max。

(3)分配矩阵Allocation。

(4)需求矩阵Need。

银行家算法如下:

设Requesti是进程Pi的请求向量,Requesti (j)=k表示进程Pi请求分配Rj 类资源k个,当Pi发出资源请求后,系统按照下列步骤进行检查。

(1)若Requesti≤Need,则执行步骤(2);否则系统会因为它所需要的资源数已超过它要求的最大值而认为出错。

(2)若Requesti≤Available,则执行步骤(3);否则系统会因为系统中尚无足够的资源满足Pi的申请而使进程Pi等待。

(3)系统试探地把资源分配给进程Pi并修改如下数据结构中的值:Available=Available-Requesti

Allocationi=Allocationi+Requesti

Needi=Needi-Requesti

(4)系统执行安全算法,检查此次资源分配后,系统是否处于安全状态。若是则系统才真正将资源分配给进程Pi以完成本次分配;若不是则系统将试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

系统所执行的安全性算法描述如下:

(1)设置两个向量:Work和Finish。其中Work表示系统可提供给进程继续运行的各类资源数,初始时Work=Available;Finish表示系统是否有足够的资源分配给进程并使之运行结束,初始时Finish(i)=false,当有足够资源分配给进程Pi 时,令Finish(i)=true。

(2)从进程集合中找到一个能满足下述条件的进程:

①Finish(i)=false

②Needi≤Work

若能找到这样的进程则执行步骤(3),否则跳过步骤(3)而执行步骤(4)。

(3)当进程Pi 获得资源后可顺利执行直到完成,然后释放分配给它的资源,并做如下工作:

①Work=Work+Allocation ②Finish(i)=true

最后转去执行步骤(2)。

(4)若所有进程的Finish(i)的值都为true ,则说明系统处于安全状态;否则系统处于不安全状态。

例1.某系统有A 、B 、C 类型的3种资源,在T0时刻进程P1、P2、P3、P4对资源的占用和需求情况见下表。此刻系统可用资源向量为(2,1,2)。问:

(1)将系统中各种资源总数和进程对资源的需求数目用向量或矩阵表示出来。 (2)判定此刻系统的安全性。如果是安全的,写出安全序列,如果是不安全的,写出参与死锁的进程。

(3)如果此时P1和P2均再发出资源请求向量

Request (1,0,1),为了保持系统安全性,应该如何分配资源给这两个进程?说明你所采用策略的原因。

(4)如果(3)中的请求都立刻满足后,系统此刻是否处于死锁状态?最终能否进入死锁状态?若能,说明参与死锁的进程,若不能,说明原因。

解:(1)系统资源总数向量=available+Allocation =(2,1,2)+(7,2,4)=(9,3,6) 进程对资源的需求矩阵

1 0 0 4 1 1

2 1 1 0 0 2

3 2 2 6 1 3 3 1

4 4 2 2 P1 P2 P2 P4 A B C A B C 已分配资源 Allocation 最大需求量max 资源

请求进程

2 2 2 2 0 2 1 0

3

4 2 0

need=max -Allocation= 3 2 2

6 1 3

3 1

4 4 2 2 1 0 0 4 1 1 2 1 1 0 0 2 — =

(2)采用银行家算法进行计算步骤如下:

work=(2,1,2)

finish=(false,false,false,false)

①因为:need[2]

系统可以满足P2对资源的请求,将资源分配给P2后,P2可执行完成,然后释放它所占有的资源。因此,

finish[2]=true;

work = work +allocation[2] =(2,1,2)+(4,1,1)=(6,2,3)

②此时,need[1]< work ,故:

P1可执行完成。finish[1]=true;

work=work+allocation[1]=( 6,2,3)+(1,0,0)=(7,2,3)

③此时,need[3]< work ,故:

P3可执行完成。finish[3]=true;

work= work+allocation[3]=( 7,2,3)+(2,1,1)=(9,3,4)

④此时,need[4]< work ,故:

P4可执行完成。finish[4]=true;

work= work+allocation[4] =( 9,3,4)+(0,0,2)=(9,3,6)

结论:

系统至少可以找到一个安全的执行序,如(P2,P1,P3,P4)可使各进程正常运行终结。

(3)系统不能将资源分配给进程P1,因为虽然可利用资源还可以满足进程P1现在的需求,但是一旦分配给进程P1后,就找不到一个安全执行的序列保证各进程能够正常运行终结。所以进程P1应该进入阻塞状态。

(4)系统满足进程P1和P2的请求后,没有立即进入死锁状态,因为这时所有进程没有提出新的资源申请,全部进程均没有因资源没有得到满足而进入阻塞状态。只有当进程提出资源申请且全部进程都进入阻塞状态时,系统才处于死锁状态。但最终会进入死锁状态。

例2 :某系统有同类资源m个,n个并发进程可共享该类临界资源。求:每个进程最多可申请多少个该类临界资源,保证系统一定不会发生死锁。

解:设每个进程最多申请该类资源的最大量为x。

每个进程最多申请x个资源,则n个进程最多同时申请的该类临界资源数为:n*x。

为保证系统不会发生死锁,应满足下列不等式:

n(x-1)+1≤m (*)

则系统一定不会发生死锁。这是因为进程最多申请x个资源,最坏的情况是每个进程都已得到了(x-1)个资源,现均申请要最后一个资源。只要系统至少还有一个资源就可使其中一个或几个进程得到所需的全部资源,在它们执行结束后归还的资源可供其他进程使用,因而不可以发生死锁。

解不等式(*),可得:

x≤1+[(m-1)/n]

即:x的最大值为1+[(m-1)/n]。因而,当每个进程申请资源的最大数值为1+[(m-1)/n]时,系统肯定不会发生死锁。

例3:设系统中有3中类型的资源(A,B,C )和5个进程P1、P2、P3、P4、P5,A 类资源的数目为17,B 类资源的数目为5,C 类资源的数目为20。在T 0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。

Max

A B C

Allocation A B C Available A B C P1 5 5 9 2 1 2 2 3 3

P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5

4 2 4

3 1 4

(1)T 0时刻是否为安全状态?若是,给出安全序列。

(2)若在T 0时刻进程P2请求资源(0,3,4),是否能实施资源分配?为什么? (3)在(2)的基础上,若进程P4请求资源(2,0,1),是否能实施资源分配?为什么?

(1)由题目所给出的最大资源需求量和已分配的资源数量,可以计算出T 0时刻各进程的资源需求量Need ,Need =Max-Allocation ,利用银行家算法对T 0时刻的资源分配情况进行分析,可得此时的安全性分析情况,如下表:

Work A B C

Need A B C Allocation A B C Work+Allocation A B C Finish P5 2 3 3 1 1 0 3 1 4 5 4 7 true P4 5 4 7 2 2 1 2 0 4 7 4 11 true P3 7 4 11 0 0 6 4 0 5 11 4 16 true P2

11 4 16

1 3 4

4 0 2

15 4 18

true

P1 15 4 18 3 4 7 2 1 2 17 5 20 true 从T 0的安全性分析中可以看出,存在一个安全序列{ P5、P4、P3、P2、P1},故T 0时刻的状态是安全的。(6分)

(2)若在T 0时刻进程P2请求资源(0,3,4),因请求资源数(0,3,4)大于剩余资源数(2,3, 3),所以不能分配。(2分)

(3)在(2)的基础上,若进程P4请求资源(2,0,1),按银行家算法进行检查:

P4请求资源(2,0,1)<= P4需求资源(2,2,1)

P4请求资源(2,0,1)<=剩余资源数(2,3, 3)

试分配并修改相应的数据结构,由此形成的资源分配情况如下表所示:

进程

资源情况

资源情况

进程

Allocation A B C

Need A B C Available A B C P1 2 1 2 3 4 7 0 3 3

P2 4 0 2 1 3 4 P3 4 0 5 0 0 6 P4 4 0 5 0 2 0 P5

3 1 4

1 1 0

此时,如题(1)利用银行家算法检查系统的安全状态,存在一个安全序列{ P4、P5、P3、P2、P1},故该状态是安全的,可以立即将P4请求的资源分配给它。

例4 :某系统有同类资源m 个,n 个并发进程可共享该类临界资源。求:每个进程最多可申请多少个该类临界资源,保证系统一定不会发生死锁。 解:设每个进程最多申请该类资源的最大量为x 。 为保证系统不会发生死锁,应满足下列不等式: n(x-1)+1≤m (*) 解不等式(*),可得: x ≤1+[(m-1)/n]

即:x 的最大值为1+[(m-1)/n]。因而,当每个进程申请资源的最大数值为1+[(m-1)/n]时,系统肯定不会发生死锁。

某系统中有5个并发进程,都需要同类资源3个,试问该系统不会发生死锁的最少资源数是( 11 )。 某系统中有4个并发进程,都需要同类资源3个,试问该系统不会发生死锁的最少资源数是( 9 )。

某计算机系统中有8台打印机,有K 个进程竞争使用,每个进程最多需要3台打印机.该系统可能会发生死锁的K 的最小值是( 4 )

系统中有3个进程,每个进程需2台打印机,如果系统配有4台打印机,则系统______不可能________出现死锁的情况(本题要判断出现死锁的可能性:可能或不可能)。

进程

资源情况

若系统运行中出现如下表所示的资源分配情况,该系统是否安全?若是,给出安全序列;如果进程P2此时提出资源申请(1,2,2,2),系统能否将资源分配给它?为什么?

Allocation (已分配资源数)

Need (还需要资源数) Available (系统可以分配资源数) P0 0 0 3 2 0 0 1 2 1 6 2 2

P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4

0 0 1 4

0 6 5 6

答:(1)利用安全性算法对此刻的资源分配情况进行如下表的安全性检:

Work Need Allocation Work+Allocation

P0 1 6 2 2 0 0 1 2 0 0 3 2 1 6 5 4 P3 1 6 5 4 0 6 5 2 0 3 3 2 1 9 8 6 P4 1 9 8 6 0 6 5 6 0 0 1 4 1 9 9 10 P1 1 9 9 10 1 7 5 0 1 0 0 0 2 9 9 10 P2

2 9 9 10

2 3 5 6

1 3 5 4

3 12 1

4 14

从表中可以看出,此时存在一个安全序列{P0,P3,P4,P1,P2},故系统是安全的。

(2) P2请求资源(1,2,2,2)<= P2需求资源(2,3,5,6)&<=剩余资源数(1,6, 2,2)

Allocation Need Available

P0 0 0 3 2 0 0 1 2 0 4 0 0

P1 1 0 0 0 1 7 5 0 P2 2 5 7 6 1 1 3 4 P3 0 3 3 2 0 6 5 2 P4

0 0 1 4

0 6 5 6

进程

资源情况

进程

资源情况

进程

资源情况

此时,可利用资源(0,4,0,0)已不能满足任何进程的需要,故系统进入不安全状态,故不能将资源分配给P2。

资源分配图。系统死锁可以利用资源分配图来描述。该图是由一组方框、圆圈和一组箭头线组成的,

(1)资源分配图。资源分配图采用图素的含义分别是:

方框:表示资源。有几类资源就画几个方框,方框中的小圆圈表示该类资源的个数。当个数较大时可以在方框内用阿拉伯数字表示。

圆圈:表示进程。有几个进程就画几个圆圈,圆圈内标明进程名称。

箭头线:表示资源的分配与申请。由方框指向圆圈的箭头线表示资源的分配线,由圆圈指向方框的箭头线表示资源的请求线。

(2)死锁定理。在死锁检测时,可以利用把资源分配图进行简化的方法来判断系统当前是否处于死锁状态。具体方法如下:

①在资源分配图中,找出一个既非阻塞又非孤立的进程结点Pi。如果Pi 可以获得其所需要的资源而继续执行,直至运行完毕,就可以释放其所占用的全部资源。这样,就可以把Pi所有关连的资源分配线和资源请求线消去,使之成为孤立的点。

②重复进行上述操作。在一系列的简化后,如果消去了资源分配图中所有的箭头线,使所有进程结点都成为孤立结点,则称该资源分配图是可完全简化的;反之,则称该资源分配图是不可完全简化的。

如果当前系统状态对应的资源分配图是不可完全简化的,则系统处于死锁状态,该充分条件称为死锁定理。

什么是死锁定理?利用死锁定理判断下图的当前状态是否会产生死锁?

死锁定理:S为死锁状态的充分条件是,当且仅当S状态的资源分配图不可完全简化。

简化过程,结论:不会产生死锁。

死锁的检测

1.利用资源分配图

系统对资源的分配情况可以用有向图加以描述:该图由结对组成:G=(V ,E )。其中,V 是顶点的集合,E 是有向边的集合,顶点集合可分为两部分:P={P1,P2,…Pn},它由系统中全部进程组成;R={r1,r2,r3},它由系统中的全部资源组成。

由边组成的集合E 中,每一个元素都是一个有序结对(pi,rj )或(rj,pi )。其中,pi 是P 中的一个进程(pi ∈P ),rj 是R 中的资源类型(rj ∈R )。如果(pi ,rj )∈E ,则存在一条从进程pi 指向资源rj 的有向边,进程pi 申请一个rj 资源单位。当前pi 在等待资源。如果(pi ,rj )∈E ,则有向边是从资源rj 指向进程pi ,就表示有一个rj 资源分配给进程pi 。边(pi ,rj )称为申请边,而(rj,pi )称为赋给边。在资源分配图中,我们用圆圈表示每个进程,用方框表示各种资源的类型 。 方框中圆点的数量表示该类资源的个数。当然,申请边只能指向方框,而赋给边必须指向方框中的一个圆点。例如

如图所示的资源分配图表示:P1申请临界资源R ,同时R 已被进程P2占有。临界资源R 类中只有一个资源 。

P1

P2

● 资源分配图 R

2.资源分配图的简化

在利用资源分配图进行死锁检测时,目的是为了决定当前状态是否发生死锁。如果满足下列条件,那么一个连续可重被利用的资源图就能够通过进程P来进行化简:

(1)进程没有被阻塞

(2)进程没有请求边

(3)有分配边指向P

通过消除所有指向P的分配边,可以化简资源分配图。如果一个资源分配图不能通过任一个进程化简,那么它就是不可被简化的;如果有一个化简序列,导致图中没有任何种类的边,那么它就是可完全简化的。

3.死锁定理

通过资源分配图,我们就可以很直观地看出系统中的进程使用资源的情况。很显然,如果图中不出现封闭的环路,则系统中不会存在死锁。但如果系统出现由各有向边组成的环路,则是否产生死锁,还需进一步分析:如果环路可以通过化简的方式取消,则系统一定不产生死锁;如果环路通过化简的方式仍不能取消,即不能再进行简化,则系统一定会产生死锁。这就是著名的死锁定理。

某系统状态S为死锁状态的充分必要条件是:当且仅当S状态的资源分配图是不可完全简化的。即:如果资源分配图中不存在环路,则系统不存在死锁;如果资源分配图中存在环路,则系统中可能产生死锁,如果不可再简化,则系统产生死锁。

银行家算法例题——四步走解题

银行家算法例题 系统中原有三类资源A、B、C和五个进程P1、P2、P3、P4、P5,A资源17,B资源5,C资源20。当前(T0时刻)系统资源分配和进程最大需求如下表。 1、现在系统T0时刻是否处于安全状态? 2、是否可以允许以下请求? (1)T1时刻:P2 Request2=(0,3,4) (2)T2时刻:P4 Request4=(2,0,1) (3)T3时刻:P1 Request1=(0,2,0) 注:T0 T1 T2 T3时刻是前后顺序,后一时刻是建立在前一时刻的基础上。

解:由题设可知Need=Max-Allocation AvailableA=17-(2+4+4+2+3)=2(原有-分配) 同理AvailableB=3,AvailableC=3 可得T0时刻资源分配表如下所示(表中数据顺序均为A B C): 1、判断T0时刻是否安全,需要执行安全算法找安全序列,过程如下表: T0时刻能找到一个安全序列{P4,P3,P2,P5,P1},故T0时刻系统处于安全状态。

2、判断T1 T2 T3时刻是否满足进程请求进行资源分配。 (1)T1时刻,P2 Request2=(0,3,4) //第一步判断条件 ①满足Request2=(0,3,4)<=Need2(1,3,4) ②不满足Request2=(0,3,4)<=Available(2,3,3) 故系统不能将资源分配给它,此时P2必须等待。 (2)T2时刻,P4 Request4=(2,0,1) //第一步判断条件①满足Request4=(2,0,1)<=Need4(2,2,1) ②满足Request4=(2,0,1)<=Available(2,3,3) //第二步修改Need、Available、Allocation的值 Available=Available-Request4= (0,3,2) Allocation4=Allocation4+Request4=(4,0,5) Need4=Need4-Request4=(0,2,0) //第三步执行安全算法,找安全序列 (注解:先写上work,其初值是系统当前进行试分配后的Available(0,3,2) ,找五个进程中Need小于work的进程,比如Need4<=Work满足,则将P4写在第一行的最前面,同时写出P4的Need和Allocation,以此类推)

用银行家算法实现资源分配

南通大学 杏林学院 操作系统实验(用银行家算法实现资源分配)班级:计121 小组成员:方筱雯1213023008 周徐莲1213023014 指导老师:丁卫平

一:实验目的 为了了解系统的资源分配情况,假定系统的任何一种资源在任一时刻只能被一个进程使用。任何资源已经占用的资源只能由自己释放,而不能由其他进程抢占。当进程申请的资源不能满足时,必须等待。因此,只要资源分配算法能保证进程的资源请求,且不出现循环等待,则系统不会出现死锁。 编写模拟系统进行资源调度的程序,采用银行家算法,有效的避免死锁的产生。模拟进程的分配算法,了解死锁的产生和避免的办法。二:实验要求 (1):为了观察死锁产生和避免的情况,要求设计3到4个并发进程,共享系统的10个同类不可抢占的资源。各进程是动态进行资源的申请和释放。 (2):用银行家算法设计一个资源分配程序,运行这个程序,观察系统运行情况,并对系统运行的每一步进行显示。三:实验流程图

四:源程序 #include #include #include #include #define MaxNumber 100 //定义进程控制块 struct Process_struct{ int Available[MaxNumber]; //可利用资源数组 int Max[MaxNumber][MaxNumber]; //最大需求矩陈 int Allocation[MaxNumber][MaxNumber]; //分配矩陈 int Need[MaxNumber][MaxNumber]; //需求矩陈 int Request[MaxNumber][MaxNumber]; //M个进程还需要N类资源的资源量 int Finish[MaxNumber]; int p[MaxNumber]; }Process; int M,N; //M个进程,N类资源 int i,j,k,l=0; int Work[MaxNumber]; //可利用资源 int Pinput(); int Safe(); int Peques(); //进程输入 int Pinput() { int i,j; cout<<"输入进程的数目:\n"; cin>>M; cout<<"输入资源的种类:\n"; cin>>N; cout<<"输入每个进程最多所需的各类资源数,按照"<>Process.Max[i][j]; cout<<"输入每个进程已经分配的各类资源数,按照"<

操作系统之调度算法和死锁中的银行家算法习题答案

操作系统之调度算法和死锁中的银行家算法习 题答案 集团文件发布号:(9816-UATWW-MWUB-WUNN-INNUL-DQQTY-

1. 有三个批处理作业,第一个作业 10:00 到达,需要执行 2 小时;第二个作业在10:10到达,需要执行 1 小时;第三个作业在 10:25 到达,需要执行 25 分钟。分别采用先来先服 务,短作业优先和最高响应比优先三种调度算法,各自的平均周转时间是多少?解: 先来先服务: (结束时间=上一个作业的结束时间+执行时间 周转时间=结束时间-到达时间=等待时间+执行时间) 按到达先后,执行顺序:1->2->3 短作业优先: 1)初始只有作业1,所以先执行作业1,结束时间是12:00,此时有作业2和3; 2)作业3需要时间短,所以先执行; 3)最后执行作业2 最高响应比优先:

高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间,综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达,所以先执行作业1; 2)12:00时有作业2和3, 作业2:等待时间=12:00-10:10=110m;响应比=1+110/60=2.8; 作业3:等待时间=12:00-10:25=95m,响应比=1+95/25=4.8; 所以先执行作业3 3)执行作业2 2. 在一单道批处理系统中,一组作业的提交时刻和运行时间如下表所示。试计算一下三种 作业调度算法的平均周转时间 T 和平均带权周转时间 W。 ( 1)先来先服务;( 2)短作业优先( 3)高响应比优先 解: 先来先服务: 作业顺序:1,2,3,4 短作业优先: 作业顺序:

银行家算法例题

银行家算法例题 假定系统中有五个进程{P0,P1,P2,P3,P4} 和三类资源{A ,B,C},各种资源的数量分别为10、5、7,在T0 时刻的资源分配情况 (1)T0时刻的安全性 利用安全性算法对T0时刻的资源分配情况进行分析 (2)P1请求资源:P1发出请求向量Request1(1,0,2),系统按银行家算法进行检查 ①Request1(1,0,2)≤Need1(1,2,2) ②Request1(1,0,2)≤Available1(3,3,2) ③系统先假定可为P1分配资源,并修改Available ,Allocation1和Need1向量,由此形成 资源情况 进程 Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 资源情况 进程 Work A B C Need A B C Allocation A B C Work+Allocatio n A B C Finish P1 3 3 2 1 2 2 2 0 0 5 3 2 TRUE P3 5 3 2 0 1 1 2 1 1 7 4 3 TRUE P4 7 4 3 4 3 1 0 0 2 7 4 5 TRUE P2 7 4 5 6 0 0 3 0 2 10 4 7 TRUE P0 10 4 7 7 4 3 0 1 0 10 5 7 TRUE

银行家算法习题1

银行家算法流程

安全性算法流程图

银行家算法例题 1.假定系统中有4个进程1P ,2P ,3P ,4P , 3种类型的资源1R ,2R ,3R ,数量分别为9,3,6, 0T 时刻的资源分配情况如表2-1所示。 表2-1 T 0时刻的资源分配情况 试问: (1) T 0时刻是否安全? (2) T 0时刻以后,若进程P 2发出资源请求Request 2(1,0,1), 系统能否将资源分配给它? (3) 在进程P 2申请资源后,若P1发出资源请求Request 1(1,0,1), 系统能否将资源分配 给它? (4) 在进程P 1申请资源后,若P3发出资源请求Request 3(0,0,1), 系统能否将资源分配 给它? 2. 在银行家算法中,出现以下资源分配情况(见表2-2) 系统剩余资源数量=(3,3,2) (1) 该状态是否安全(给出详细的检查过程) (2) 如果进程依次有如下资源请求: P1:资源请求request (1,0,2) P2:资源请求request (3,3,0) P3:资源请求request (0,1,0) 则系统该如何进行资源分配才能避免死锁?

3.设系统中有3种类型的资源(A、B、C)和5个进程P1、P2、P3、P4、P5,A资源的数量为17,B资源的数量为5,C资源的数量为20。在T0时刻,系统状态见表2-3。系统采用银行家算法实现死锁避免。 (1)T0时刻是否为安全状态?若是,请给出安全序列 (2)在T0时刻,若进程P2请求资源(0,3,4),是否能实施资源分配?为什么? (3)在(2)的基础上,若进程P4请求资源(2,0,1),是否能实施资源分配? (4)在(3)的基础上,若进程P1请求资源(0,2,0),是否能实施资源分配? 4.某系统有R1、R2、R3共三种资源,在T0时刻P1、P2、P3、P4这四个进程对资源的占用和需求情况见表2-24,此时系统的可用资源矢量为(2,1,2)。试问: 1)将系统中各种资源总数和此刻各进程对各资源的需求数目用矢量或矩阵表示出来。2)如果此时进程P1和进程P2均发出资源请求矢量Request(1,0,1),为了保证系统的安全性,应如何分配资源给这两个进程?说明所采用策略的原因。 3)如果2)中两个请求立即得到满足后,系统此刻是否处于死锁状态? 5.考虑某个系统在表2-25时刻的状态

(完整版)操作系统课后题答案

2.OS的作用可表现在哪几个方面? 答:(1)OS作为用户与计算机硬件系统之间的接口;(2)OS作为计算机系统资源的管理者; (3)OS实现了对计算机资源的抽象。 5.何谓脱机I/O和联机I/O? 答:脱机I/O 是指事先将装有用户程序和数据的纸带或卡片装入纸带输入机或卡片机,在外围机的控制下,把纸带或卡片上的数据或程序输入到磁带上。该方式下的输入输出由外围机控制完成,是在脱离主机的情况下进行的。而联机I/O方式是指程序和数据的输入输出都是在主机的直接控制下进行的。 11.OS有哪几大特征?其最基本的特征是什么? 答:并发性、共享性、虚拟性和异步性四个基本特征;最基本的特征是并发性。 20.试描述什么是微内核OS。 答:(1)足够小的内核;(2)基于客户/服务器模式;(3)应用机制与策略分离原理;(4)采用面向对象技术。 25.何谓微内核技术?在微内核中通常提供了哪些功能? 答:把操作系统中更多的成分和功能放到更高的层次(即用户模式)中去运行,而留下一个尽量小的内核,用它来完成操作系统最基本的核心功能,称这种技术为微内核技术。在微内核中通常提供了进程(线程)管理、低级存储器管理、中断和陷入处理等功能。 第二章进程管理 2. 画出下面四条语句的前趋图: S1=a:=x+y; S2=b:=z+1; S3=c:=a – b;S4=w:=c+1; 答:其前趋图为: 7.试说明PCB 的作用,为什么说PCB 是进程存在的惟一标志? 答:PCB 是进程实体的一部分,是操作系统中最重要的记录型数据结构。作用是使一个在多道程序环境下不能独立运行的程序,成为一个能独立运行的基本单位,成为能与其它进程并发执行的进程。OS是根据PCB对并发执行的进程进行控制和管理的。 11.试说明进程在三个基本状态之间转换的典型原因。 答:(1)就绪状态→执行状态:进程分配到CPU资源;(2)执行状态→就绪状态:时间片用完;(3)执行状态→阻塞状态:I/O请求;(4)阻塞状态→就绪状态:I/O完成. 19.为什么要在OS 中引入线程?

《银行家算法的模拟实现》—实验报告

《银行家算法的模拟实现》 --实验报告 题目: 银行家算法的模拟实现 专业: 班级: 组员: 指导老师:

一、实验目的 死锁会引起计算机工作僵死,因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序,了解死锁产生的条件和原因,并采用银行家算法有效地防止死锁的发生,以加深对课堂上所讲授的知识的理解。 二、实验内容 模拟实现银行家算法实现死锁避免。要求:初始数据(如系统在T0时刻的资源分配情况、每一种资源的总数量)从文本文件读入,文件中给出最大需求矩阵Max、分配矩阵Allocation,在程序中求得需求矩阵Need和可利用资源向量Available。 三、实验分析过程 1、整个银行家算法的思路。 先对用户提出的请求进行合法性检查,再进行预分配,利用安全性检查算法进行安全性检查。 1)进程一开始向系统提出最大需求量. 2)进程每次提出新的需求(分期贷款)都统计是否超出它事先提出的最大需求量. 3)若正常,则判断该进程所需剩余剩余量(包括本次申请)是否超出系统所掌握的 剩余资源量,若不超出,则分配,否则等待 2、算法用到的主要数据结构和C语言说明。 (1)、可利用资源向量INT A V AILABLE[M] M为资源的类型。 (2)、最大需求矩阵INT MAX[N][M] N为进程的数量。 (3)、已分配矩阵INT ALLOCA TION[N][M] (4)、还需求矩阵INT NEED[N][N] (5)、申请各类资源数量int Request[x]; // (6)、工作向量int Work[x]; (7)、int Finish[y]; //表示系统是否有足够的资源分配给进程,0为否,非0为是 3、银行家算法(主程序) (1)、系统初始化。输入进程数量,资源种类,各进程已分配、还需求各资源数量,各资源可用数量等 (2)、输入用户的请求三元组(I,J,K),为进程I申请K个J类资源。 (3)、检查用户的请求是否小于还需求的数量,条件是K<=NEED[I,J]。如果条件不符则提示重新输入,即不允许索取大于需求量 (4)、检查用户的请求是否小于系统中的可利用资源数量,条件是K<=A V ALIABLE[I,J]。 如果条件不符则申请失败,阻塞该进程,重新进行进程动态资源申请(使用goto语句) (5)、进行资源的预分配,语句如下: A V ALIBLE[I][J]= A V ALIBLE[I][J]-K; ALLOCATION[I][J]= ALLOCATION[I][J]+K; NEED[I][J]=NEED[I][J]-K;

银行家算法例子+答案

1、设系统中有3种类型的资源(A , B , C )和5个进程P1、P 2、P3 P4 P5, A 资源的数量为 17, B 资源的数量为5, C 资源的数量为20。在T o 时刻系统状 态见下表(T o 时刻系统状态表)所示。系统米用银行家算法实施死锁避免策 略。(12分) T o 时刻系统状态表 T0时刻系统状态表 (1) T o 时刻是否为安全状态?若是,请给出安全序列。 (2) 在T o 时刻若进程P2请求资源(0, 3, 4),是否能实施资源分配?为 什么? 满足P5的运行,在P5运行后,系统的状态为: 2 1 2 3 4 7 4 o 2 1 3 4 A 4 o 5 C A o o 6 V' 5 4 7 2 o 4 2 2 1 o o o o o o 同样的, 在 P5运行后,V ' (5, 4, 7)也大于等于 C-A 中P4所在的行(2, 2, 1),则能满 足P4的运行。P4运行后,系统的状态为: ⑷ 在(3) 的基; 础上, 若进程 P1 请求资源(o , 2, o ),是否能实施资源 分配?为什么 ,? 答: 当前 的系 统状态描述为: 5 5 9 2 1 2 3 4 7 5 3 6 4 o 2 1 3 4 C 4 o 11 A 4 o 5 C A o o 6 4 2 5 2 o 4 2 2 1 4 2 4 3 1 4 1 1 o R 17 5 2o V 2 3 3 (3)在(2)的基础上,若进程 分配?为什么? P4请求资源(2, o , 1),是否能实施资源 (1) 在To 时刻,由于V (2, 3, 3)大于等于(C-A )中P5所在行的向量(1 , 1 ,。),因此V 能

银行家算法-实验报告

淮海工学院计算机工程学院实验报告书 课程名:《操作系统原理》 题目:银行家算法 班级: 学号: 姓名:

一、实验目的 银行家算法是操作系统中避免死锁的典型算法,本实验可以加深对银行家算法的步骤和相关数据结构用法的更好理解。 实验环境 Turbo C 2.0/3.0或VC++6.0 实验学时 4学时,必做实验。 二、实验内容 用C语言编写一个简单的银行家算法模拟程序,用银行家算法实现资源分配。程序能模拟多个进程共享多种资源的情形。进程可动态地申请资源,系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列;显示和打印各进程依次要求申请的资源数量以及为某进程分配资源后的有关资源数据的情况。 三、实验说明 实验中进程的数量、资源的种类以及每种资源的总量Total[j]最好允许动态指定。初始时每个进程运行过程中的最大资源需求量Max[i,j]和系统已分配给该进程的资源量Allocation[i,j]均为已知(这些数值可以在程序运行时动态输入),而算法中其他数据结构的值(包括Need[i,j]、Available[j])则需要由程序根据已知量的值计算产生。 四、实验步骤 1、理解本实验中关于两种调度算法的说明。 2、根据调度算法的说明,画出相应的程序流程图。 3、按照程序流程图,用C语言编程并实现。 五、分析与思考 1.要找出某一状态下所有可能的安全序列,程序该如何实现? 答:要找出这个状态下的所有可能的安全序列,前提是要是使这个系统先处于安全状态,而系统的状态可通过以下来描述: 进程剩余申请数=最大申请数-占有数;可分配资源数=总数-占有数之和; 通过这个描述来算出系统是否安全,从而找出所有的安全序列。 2.银行家算法的局限性有哪些?

操作系统实验四-银行家算法

银行家算法 xxx 711103xx 2012年5月21日一、实验目的 通过实验,加深对多实例资源分配系统中死锁避免方法——银行家算法的理解,掌握Windows环境下银行家算法的实现方法,同时巩固利用Windows API进行共享数据互斥访问和多线程编程的方法。 二、实验内容 1. 在Windows操作系统上,利用Win32 API编写多线程应用程序实现银行家算法。 2. 创建n个线程来申请或释放资源,只有保证系统安全,才会批准资源申请。 3. 通过Win32 API提供的信号量机制,实现共享数据的并发访问。 三、实验步骤(设计思路和流程图) 最主要的用以实现系统功能的应该有两个部分,一是用银行家算法来判断,二是用安全性算法来检测系统的安全性。 1、银行家算法 设Requesti是进程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) 设置两个向量:①Work∶=Available; ②Finish (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都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

银行家算法问题

银行家算法问题 1、银行家算法中的数据结构 (1)可利用资源向量Available : []Availabel j k = 式中:j 01j m ≤≤- 一个含有m 个(类)元素的数组,每个元素代表一类可利用的资源数目。上式表示系统中现有的第j 类资源可用数目为k 个。 (2)最大需求矩阵Max : [,]Max i j k = 式中: i 01i n ≤≤- j 01j m ≤≤- n 个进程中的每一个进程对m 类资源的最大需求量,上式表示进程i 需求第j 类资源的最大数目为k 。 (3)分配矩阵Allocation : [,]Allocation i j k = 式中: i 01i n ≤≤- j 01j m ≤≤- n 个进程中的每一个进程对m 类资源的分配量,上式表示进程i 已分配到第j 类资源的数目为k 。 (4)需求矩阵Need :[,]Need i j k = 式中: i 01i n ≤≤- j 01j m ≤≤- n 个进程中的每一个进程对m 类资源的需求量,上式表示进程i 对第j 类资源的需求量为k 个。 (5)三个矩阵间的关系 [,][,][,]Need i j Max i j Allocation i j =-

2、银行家算法 设Re i quest 是进程i P 的请求向量,如果Re []i quest j k =,当i P 发出资源请求后,系统按下述步骤进行检查。 (1)如果Re [][,]i quest j Need i j ≤,便转向步骤(2),否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。 (2)如果Re [][]i quest j Available j ≤便转向步骤(3),否则表示尚无足够资源, i P 须等待。 (3)系统试探着把资源分配给进程i P ,并修改下面的数据结构中的值: [][]Re []i Availabel j Availabel j quest j =- [,][,]R e [ i A l l o c a t i o n i j A l l o c a t i o n i j q u e s t j =+ [,][,]Re []i Need i j Need i j quest j =- (4)系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。 若安全,则分配给进程i P 资源,完成本次分配;若不安全,试探分配作废,恢复原来的资源分配状态,让进程i P 等待。 3、安全性算法 (1)设置两个向量: 工作向量Work ,它表示系统可提供给进程继续运行所需的各类资源数目,它含有m 个元素,在执行安全算法开始时,Work Available =。 Finish ,它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做 []:Finish i false =;当有足够资源分配给进程时,再令[]:Finish i true =。 (2)从进程集合中找一个能满足下述条件的进程: [ ]:F i n i s h i f a l s e = [,][]Need i j Work j ≤,若找到,执行步骤(3),否则,执行步骤(4)。 (3)当进程i P 获得资源后,可顺利执行直至完成,并释放出分配给它的资源,

操作系统之调度算法和死锁中的银行家算法习题答案

1.有三个批处理作业,第一个作业10:00 到达,需要执行2 小时;第二个作业在10:10 到达,需要执行1 小时;第三个作业在10:25 到达,需要执行25 分钟。分别采用先来先服务,短作业优先和最高响应比优先三种调度算法,各自的平均周转时间是多少? 解: 先来先服务: (结束时间=上一个作业的结束时间+执行时间 周转时间=结束时间-到达时间=等待时间+执行时间) 短作业优先: 1)初始只有作业1,所以先执行作业1,结束时间是12:00,此时有作业2和3; 2)作业3需要时间短,所以先执行; 最高响应比优先: 高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间,综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达,所以先执行作业1; 2)12:00时有作业2和3, 作业2:等待时间=12:00-10:10=110m;响应比=1+110/60=2.8; 作业3:等待时间=12:00-10:25=95m,响应比=1+95/25=4.8; 所以先执行作业3 2.在一单道批处理系统中,一组作业的提交时刻和运行时间如下表所示。试计算一下三种作业调度算法的平均周转时间T 和平均带权周转时间W。 (1)先来先服务;(2)短作业优先(3)高响应比优先

解: 先来先服务: 短作业优先: 作业顺序: 1)8:00只有作业1,所以执行作业1; 2)9:00有作业2和3,作业3短,所以先执行3; 3)9:12有作业2和4,作业4短,所以先执行4; 高响应比优先: 作业顺序: 1)8:00只有作业1,所以执行作业1; 2)9:00有作业2和3 作业2等待时间=9:00-8:30=30m,响应比=1+30/30=2; 作业3等待时间=9:00-9:00=0m,响应比=1+0/12=1; 所以执行作业2; 3)9:30有作业3和4 作业3等待时间=9:30-9:00=30m,响应比=1+30/12=3.5; 作业4等待时间=9:30-9:06=24m,响应比=1+24/6=5;

操作系统课程设计(银行家算法的模拟实现)

操作系统课程设计 (银行家算法的模拟实现) 一、设计目的 1、进一步了解进程的并发执行。 2、加强对进程死锁的理解。 3、用银行家算法完成死锁检测。 二、设计内容 给出进程需求矩阵C、资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝(银行家算法)模拟该进程组的执行情况。 三、设计要求 1、初始状态没有进程启动。 2、计算每次进程申请是否分配,如:计算出预分配后的状态情况(安全状态、不安全状态),如果是安全状态,输出安全序列。 3、每次进程申请被允许后,输出资源分配矩阵A和可用资源向量V。 4、每次申请情况应可单步查看,如:输入一个空格,继续下个申请。 四、算法原理 1、银行家算法中的数据结构

(1)、可利用资源向量Available,这是一个含有m个元素的数组,其中的每个元素代表一类可利用资源的数目,其初始值是系统中所配置的该类全部资源的数目,其数值随该类资源的分配和回收而动态改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。 (2)、最大需求矩阵Max,这是一个n*m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果 Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。 (3)、分配矩阵Allocation。这也是一个n*m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=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、银行家算法应用 模拟实现Dijkstra的银行家算法以避免死锁的出现,分两部分组成:一是银行家算法(扫描);二是安全性算法。 (1)银行家算法(扫描) 设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Ri类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查: ①如果Requesti[j]<=Need[i,j],便转向步骤②;否则认为出错,

操作系统作业第三章1,第四章的答案

第三章操作系统的答案 1. 高级调度与低级调度的主要任务是什么为什么要引入中级调度 a. 作业调度又称宏观调度或高级调度,其主要任务是按一定的原则对外存上处于后备状态的作业进行选择,给选中的作业分配内存,输入输出设备等必要的资源,并建立相应的进程,以使该作业的进程获得竞争处理机的权利. b. 进程调度又称微观调度或低级调度,其主要任务是按照某种策略和方法选取一个处于就绪状态的进程,将处理机分配给它. c. 为了提高内存利用 6.在抢占调度方式中,抢占的原则是什么 a. 优先权原则 b. 短作业(进程)优先原则 c.时间片原则 7. 选择调度方式和调度算法时,应遵循的准则是什么 a. 面向用户的准则有周转时间短,响应时间快,截止时间的保证,以及优先权准则. b. 面向系统的准则有系统吞吐量高,处理机利用率好,各类资源的平衡利用. 18.何谓死锁产生死锁的原因和必要条件是什么 a. 死锁是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程都将永远不能再向前推进; b. 产生死锁的原因有二,一是竞争资源,二是进程推进顺序非法; c. 必要条件是: 互斥条件,请求和保持条件,不剥夺条件和环路等待条件. 19.在解决死锁问题的几个方法中,哪种方法最容易实现哪种方法使资源的利用率最高 a. 解决死锁可归纳为四种方法: 预防死锁,避免死锁,检测死锁和解除死锁; b. 其中,预防死锁是最容易实现的; c. 避免死锁使资源的利用率最高. 21.在银行家算法的例子中,如果P0发出的请求向量由Request0(0,2,0)改为Request0(0,1,0),问系统可否将资源分配给它

操作系统课程设计银行家算法的模拟实现

操作系统课程设计银行家算法的模拟 实现

操作系统课程设计 (银行家算法的模拟实现) 一、设计目的 1、进一步了解进程的并发执行。 2、加强对进程死锁的理解。 3、用银行家算法完成死锁检测。 二、设计内容 给出进程需求矩阵C、资源向量R以及一个进程的申请序列。使用进程启动拒绝和资源分配拒绝(银行家算法)模拟该进程组的执行情况。 三、设计要求 1、初始状态没有进程启动。 2、计算每次进程申请是否分配,如:计算出预分配后的状态情况(安全状态、不安全状态),如果是安全状态,输出安全序列。 3、每次进程申请被允许后,输出资源分配矩阵A和可用资源向量V。 4、每次申请情况应可单步查看,如:输入一个空格,继续下个申请。 四、算法原理 1、银行家算法中的数据结构

(1)、可利用资源向量Available,这是一个含有m个元素的数组,其中的每个元素代表一类可利用资源的数目,其初始值是系统中所配置的该类全部资源的数目,其数值随该类资源的分配和回收而动态改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。 (2)、最大需求矩阵Max,这是一个n*m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。 (3)、分配矩阵Allocation。这也是一个n*m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=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、银行家算法应用 模拟实现Dijkstra的银行家算法以避免死锁的出现,分两部分组成:一是银行家算法(扫描);二是安全性算法。 (1)银行家算法(扫描) 设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示

银行家算法的java编程实现

/*死锁避免和死锁检测模拟程序【银行家算 法】网络工程06-3班学号:310609040308*/ import java.util.*; public class TestTheBanker { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); TheBanker tb = new TheBanker(); tb.deadlockAvoidance();//死锁避免 int gate = 1; while(gate!=0){ tb.deadlockDetection();//死锁检测 System.out.println("如果您要继续分配资源请输入\"1\",退出请输入\"0\""); System.out.print("您输入的值为:"); gate = scanner.nextInt(); System.out.println(); } System.out.println("使用愉快!期待您下次使用!"); } } class TheBanker{ int m; int n; int[][] max; int[][] maxbak;//备份用 int[][] allocation; int[][] allocationbak;//备份用 int[][] need; int[][] needbak;//备份用 int[] available; int[] availablebak;//备份用 public TheBanker(){ Scanner s = new Scanner(System.in); System.out.println("初始化=============="); System.out.print("请依次输入系统中的【进程数】和【资源类型数】:"); m = s.nextInt(); n = s.nextInt(); max =new int[m][n];

编程序模拟银行家算法

武汉理工大学华夏学院课程设计报告书 课程名称:操作系统原理 题目:编程序模拟银行家算法 系名:信息工程系 专业班级:软件1121 姓名:钟伟 学号:10212812120 指导教师:苏永红 2014年 6 月13 日

武汉理工大学华夏学院信息工程系 课程设计任务书 课程名称:操作系统原理课程设计指导教师:苏永红 班级名称:软件1121 开课系、教研室:软件与信息安全 一、课程设计目的与任务 操作系统课程设计是《操作系统原理》课程的后续实践课程,旨在通过一周的实践训练,加深学生对理论课程中操作系统概念,原理和方法的理解,加强学生综合运用操作系统原理、Linux系统、C语言程序设计技术进行实际问题处理的能力,进一步提高学生进行分析问题 和解决问题的能力,包含系统分析、系统设计、系统实现和系统测试的能力。 学生将在指导老师的指导下,完成从需求分析,系统设计,编码到测试的全过程。 二、课程设计的内容与基本要求 1、课程设计题目 编程序模拟银行家算法 2、课程设计内容 本课程设计要求在Linux操作系统,GCC编译环境下开发。 银行家算法是避免死锁的一种重要方法,本实验要求用用c/c++语言在Linux操作系统 环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。 思想:将一定数量的资金供多个用户周转使用,当用户对资金的最大申请量不超过现存 资金时可接纳一个新客户,客户可以分期借款,但借款总数不能超过最大的申请量。银行家 对客户的借款可以推迟支付,但是能够使客户在有限的时间内得到借款,客户得到所有的借 款后能在有限的时间内归还。用银行家算法分配资源时,测试进程对资源的最大需求量,若 现存资源能满足最大需求就满足当前进程的申请,否则推迟分配,这样能够保证至少有一个 进程可以得到所需的全部资源而执行到结束,然后归还资源,若OS能保证所有进程在有限 的时间内得到所需资源则称系统处于安全状态。 3、设计报告撰写格式要求: 1设计题目与要求 2 设计思想 3系统结构 4 数据结构的说明和模块的算法流程图 5 使用说明书(即用户手册):内容包含如何登录、退出、读、写等操作说明 6 运行结果和结果分析(其中包括实验的检查结果、程序的运行情况) 7 自我评价与总结 8 附录:程序清单,注意加注释(包括关键字、方法、变量等),在每个模块前加注释;

银行家算法的设计与实现(JAVA语言).doc

银行家算法的设计与实现(JAVA语言).doc 淘豆网网友近日为您收集整理了关于操作系统课程设计报告-银行家算法的设计与实现(java语言)的文档,希望对您的工作和学习 有所帮助.以下是文档介绍:操作系统课程设计报告题目:银行家算法的设计与实现院(系):计算机科学与工程学院专业:信息对抗专业班级:学生:学号:指导教师:2011年12月1基于计算机操作系统银行 家算法实现摘要此次课程设计的主要内容是模拟实现资源分配.同时要求编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生的条件,并使用适当的算法,有效的防止和避免死锁的发生具体用 银行家算法实现资源分配.要求如下:(1)设计一个3个并发进程共享3类不同资源的系统,进程可动态地申请资源和释放资源,系统按各 进程的申请动态地分配资源.(2)设计用银行家算法和随机分配算法,实现资源分配的两个资源分配程序,应具有显示或打印各进程依次要求申请的资源数以及依次分配资源的情况.(3)确定一组各进程依次 申请资源数的序列,在相同的情况下分别运行上述两种资源分配程序,观察运行结果.银行家算法是避免死锁的一种重要方法,本实验要求 用高级语言编写和调试一个简单的银行家算法程序.加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法.死锁的产生,必须同时满足四个条件,即一个资源每次只能由一个进程占用:第二个为等待条件,即一个进程请求资源不能满足时,它必须等待,但它仍继续保持已得到的所有其他资源:第四个为循环等 待条件,系统中存在若干个循环等待的进程,即其中每一个进程分别 等待它前一个进程所持有的资源.防止死锁的机构只能确保上述四个条件之一不出现,则系统就不会发生死锁.通过这个算法可用解决生 活中的实际问题,如银行贷款等.通过对这个算法的设计,让学生能够对书本知识有更深的理解,在操作和其它方面有更高的提升.关键词:死锁;安全状态;安全序列;银行家算法;安全性检查2目录1概述..................................................(3)1.1 设计目的....................................................(3)1.

银行家算法

操作系统课程设计报告题目:银行家算法 院(系):计算机科学与工程学院 专业: 班级: 学生: 学号: 指导教师: 2011年12月

目录 摘要 (1) 绪论 (1) 1、需求分析 (1) 1.1银行家算法的提出 (1) 1.2 银行家算法设计思想 (1) 1.3银行家算法设计分析 (2) 2、概要设计 (3) 2.1主要的常量变量 (4) 2.2算法中用到的数据结构的说明 (8) 2. 3算法中用到的函数.......................................................................( 8) 2.4 银行家算法 (8) 2.5流程图.................................... . (9) 3、详细设计 (13) 4. 调试与测试 (8) 4.1测试数据 (8) 4.2.测试的结果: (9) 5、结论 (10) 参考文献 (10) 附录 (11)

摘要 在多道操作系统中,可以利用多个进程并发执行来改善系统资源利用率,提高系统的吞吐量,但也可能发生人们不想看到的危险——死锁。为了解决这个问题,人们引入了多种机制处理死锁问题。本文主要介绍了操作系统如何运用银行家算法和安全性算法避免死锁的产生。同时运用Java编程语言模拟计算机内部资源分配的过程。让读者对银行家算法有更深刻的认识。 关键字:死锁银行家算法安全性算法资源分配 1.需求分析. 1.1银行家算法的提出 本次课程设计主要解决的问题是死锁的避免。 死锁:是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程将永远不能再向前推进。 避免死锁是在不破坏死锁产生的四个必要条件,在资源的动态分配中,防止进程进入可能发生死锁的不安全状态。 根据此原理,Dijkstra 于1965年提出了一个经典的避免死锁的算法----银行家算法(banker’s algorithm)。 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。为实现银行家算法,系统必须设置若干数据结构。所以通过编写一个模拟动态资源分配的银行家算法程序,进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念,并掌握避免死锁的具体实施方法. 1.2 银行家算法设计思.想 我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全,银行家规定: (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2)顾客可以分歧贷款,但贷款的总数不能超过最大需求量; (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可

相关主题
相关文档 最新文档