文档介绍：操作系统
课程设计报告
专业
计算机科学与技术
学生姓名
周凯强
班级
B计算机112
学号
1110704227
指导教师
李先锋
完成日期
2013年6月21日
信息工程学院
题目:银行家算法的模拟实现
概述
用C或C++语言编制银行家算法通用程序,并检测所给状态的系统安全性。
算法介绍:数据结构:
可利用资源向量 Available;
最大需求矩阵Max;
分配矩阵Allocation;
需求矩阵Need。
功能介绍
模拟实现Dijkstra的银行家算法以避免死锁的出现,分两部分组成:
第一部分:银行家算法(扫描);
第二部分:安全性算法。
设计原理
1、死锁概念
在多道程序系统中,虽可借助于多个进程的并发执行,来改善系统的资源利用率,提高系统的吞吐量,但可能发生一种危险━━死锁。所谓死锁(Deadlock),是指多个进程在运行中因争夺资源而造成的一种僵局(Deadly_Embrace),当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程。
2、关于死锁的一些结论:
Ø 参与死锁的进程最少是两个
Ø (两个以上进程才会出现死锁)
Ø 参与死锁的进程至少有两个已经占有资源
Ø 参与死锁的所有进程都在等待资源
Ø 参与死锁的进程是当前系统中所有进程的子集
注:如果死锁发生,会浪费大量系统资源,甚至导致系统崩溃。
3、资源分类。
永久性资源:
可以被多个进程多次使用(可再用资源)
可抢占资源;
不可抢占资源;
临时性资源:
只可使用一次的资源;如信号量,中断信号,同步信号等(可消耗性资源)
“申请--分配--使用--释放”模式
4、产生死锁的四个必要条件:互斥使用(资源独占)、不可强占(不可剥夺)、请求和保持(部分分配,占有申请)、循环等待。
(1) 互斥使用(资源独占)
一个资源每次只能给一个进程使用。
(2) 不可强占(不可剥夺)
资源申请者不能强行的从资源占有者手中夺取资源,资源只能由占有者自愿释放。
(3) 请求和保持(部分分配,占有申请)
一个进程在申请新的资源的同时保持对原有资源的占有(只有这样才是动态申请,动态分配)。
(4) 循环等待
存在一个进程等待队列
{P1 , P2 , …, Pn},
其中P1等待P2占有的资源,P2等待P3占有的资源,…,Pn等待P1占有的资源,形成一个进程等待环路。
5、死锁预防:
定义:在系统设计时确定资源分配算法,保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。
破坏“不可剥夺”条件:
在允许进程动态申请资源前提下规定,一个进程在申请新的资源不能立即得到满足而变为等待状态之前,必须释放已占有的全部资源,若需要再重新申请
破坏“请求和保持”条件:
要求每个进程在运行前必须一次性申请它所要求的所有资源,且仅当该进程所要资源均可满足时才给予一次性分配。
破坏“循环等待”条件:
采用资源有序分配法:
把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配。
安全状态:
如果存在一个由系统中所有进程构成的安全序列P1,…Pn,则系统处于安全状态。一个进程序列{P1,…,Pn}是安全的,如果对于每一个进程Pi(1≤i≤n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j <i )当前占有资源量之和,系统处于安全状态(安全状态一定是没有死锁发生的)
不安全状态:不存在一个安全序列,不安全状态一定导致死锁。
银行家算法
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的矩阵,用以表示每一个进程