武汉理工大学华夏学院 课程设计报告书 课程名称： 操作系统原理 题 目： 编程序模拟银行家算法 系 名： 信息工程系 专业班级： 计算机1102班 姓 名： 何利华 学 号： 指导教师: 赵传斌 苏永红 2013 年 1 月 17 日 课程设计任务书 学生姓名： 何利华 专业班级： 计算机1102 指导教师： 苏永红 赵传斌 工作单位： 信息工程系 设计题目：编程序模拟银行家算法 初始条件： Linux操作系统，GCC编译环境 要求完成的主要任务： 主要任务： 银行家算法是避免死锁的一种重要方法，本实验要求用用c/c++语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 思想：将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。 设计报告撰写格式要求： 1设计题目与要求 2 设计思想 3系统结构 4 数据结构的说明和模块的算法流程图 5 使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明 6 运行结果和结果分析（其中包括实验的检查结果、程序的运行情况） 7 自我评价与总结 8 附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释； 时间安排 1月14日 布置课程设计任务；分配题目后，查阅资料、 准备程序； 1月 15～1月17 日上机调试程序、书写课程设计报告； 1月18 日 提交课程设计报告及相关文档。 指 导 教 师 签 字： 2012年 12月 29日 系 主 任 签 字： 2013年 1月 2 1设计题目与要求 设计题目 编程序模拟银行家算法 要求 本实验要求用用c/c++语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 2 设计思想 思想：将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。 3系统结构 图 1 4数据结构的说明和模块的算法流程图 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] 4．2程序流程图： 1、系统主要过程流程图1 图1 图1 2、安全性算法流程图 5

死锁、死锁模型、死锁预防和恢复、银行家算法

死锁：一组阻塞的进程（两个或多个），持有一种资源，等待获取另一个进程所占有的资源，而导致谁都无法执行。
由于进程的并发执行引起了死锁。

每个进程可以怎么使用资源：

• 在一个时间只能一个进程使用，且不能被删除。OS避免杀死拥有资源的进程。
• 进程使用资源后要释放，让其他进程重用
• 有物理资源（cpu， I/O通道，主和副存储器），也有抽象的资源（设备和数据结构，如文件，数据库和信号量）
• 如果每个进程拥有一个资源并请求其他资源，可能导致死锁

创建，销毁—内存管理单元
I/O缓冲区的中断，信号，消息，信息
如果接受信息阻塞可能会发生死锁
少见的组合事件可能会引起死锁

左图没有死锁，右图死锁，死锁会有闭环出现
但有闭环出现不一定会死锁，因为资源是循环的
如果不包含闭环—>没有死锁
如果包括闭环，且每个资源类只有一个实例-→死锁 ；否则，不会。

死锁的特征 : 四个的必要条件

• 无抢占，一个资源只能被进程自愿释放

互斥—占用非共享资源 会增加不确定性 不推荐
占用并等待—保证当一个进程请求资源时，不持有任何其他的资源
all or nothing 需要进程请求并分配其所有资源，资源利用率低，可能饥饿
无抢占—允许抢占占有某些资源的进程
循环等待—对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请，会出现资源利用不够

当进程运行过程中，根据申请资源的情况判断会不会死锁，如果会就不给资源。
需要系统具有一些先验信息。
最简单有效就是要求每个进程声明它需要的每个类型资源的最大数目，资源在分配中根据最大数目限定提供与分配的资源数目，死锁避免算法要动态检查资源的分配状态来避免环形等待。
环形等待不一定会死锁。分为安全状态，不安全状态，死锁状态，不安全状态包括死锁。
当一个进程请求可用资源，系统必须判断分配资源是否能让系统处于安全状态。
安全状态：针对所有进程，存在安全的时间序列。第一个P1结束，第二个P2结束。。。都能得到满足，正常结束。则称序列< P1, P2…Pn >是安全的：针对每一个进程Pi，它要求的资源能够由当前可用的资源+所有i之前的进程所持有的资源来满足。
进程会相继结束，Pi只能用它之前的进程的资源。
如果Pi资源的需求不是立即可用，那么Pi可以等到所有Pj完成。
当Pi完成后Pi+1得到所需要的资源，执行，释放资源，并终止。

如果系统处于安全状态 => 没有死锁
如果处于不安全状态 => 可能死锁
避免死锁： 确保系统永远不会进入不安全状态

银行家算法 DIJ设计的
每个进程必须能最大限度地利用资源
一个进程请求一个资源时，不得不等待
所有资源都必须在一段有效时间释放
找到理想执行时序，找到就认为是安全的

Finish [i] 得到了所有资源，可以执行结束
看哪个未结束的进程的need小于avaliable，就是第一个结束的进程，结束后释放资源，重复。

也是银行家算法，由于开销大，且需要一开始就知道max[i,j]，不一定能得到，所以主要用于开发阶段的调试，不会用于检测，特别是单一OS时

通过杀死所有死锁进程，在一个时间内终止一个进程直到死锁消除等方式完成，都干扰了进程的正常运行，都有强制性。
多数情况下，就是重启。
资源抢占，打破4个条件。
以最小的成本选择一个受害者
进程的优先级，运行时间，还需多少时间，占用的资源，完成需要的资源（max），多少进程需要被终止，进程是交互还是批处理
重启进程，返回到安全状态—回滚
同一进程可能一直被选为受害者，包括回滚的数量—饥饿
确保不会死锁，运行系统进入死锁然后恢复
假装不知道死锁，不占了就重启（死锁恢复）：用于大多数操作系统，包括UNIX，主要是因为开销大，为了避免死锁设定条件会降低OS的性能

如果P和Q想通信，需要：
在它们之间建立通信链路

物理（例如，共享内存，硬件总线）

进程要相互独立，但另一方面也要相互协作
左侧进程A和B是间接的通信，右侧是直接通信

为了实现直接通信，要有发送和接收的ID
进程必须正确地命名对方
一条链路恰好对应一对通信进程
每对进程之间只有一个链接存在
链接可以是单向的，但通常为双向的

为了实现间接通信，要发送到共享区，发送方和接收方都不关注具体的另一方是谁
定向从消息队列接收消息：
每个消息队列都有一个唯一的ID
只有他们共享了一个消息队列，进程才能通信
只有进程共享一个共同的消息队列，才建立链路
链接可以与许多进程相关联
每对进程可以共享多个通信链路
连接可以是单向或者双向
通过消息队列发送和接收消息

队列的消息被附加到链路的3种方式
0容量—0 messages 发送方必须等待接收方
有限容量—n messages 的有限长度，发送方在队列满的时候要等待
无限容量—理想状况，不用等

ipc常用手段：信号，管道，消息队列，共享内存
硬件中断interrupt，信号是软件中断，通知有事件要处理
应用程序会catch，默认，停下来处理信号，特殊处理函数。

第二步，改入口，OS把系统调用返回的堆栈修改到信号处理函数的入口，再把信号处理函数结束后的地址处理成原有进程中断点的入口。

管道：用于数据交换，与信号不同。理解为内存中的一个buffer
UNIX想灵活组合小程序，一个的输出是另一个的输入，用竖线|来表示
把ls的输出stdout重定向，通过一个类似buffer的管道作为stdin传输给more。More以为是从i/o给它的，实际是ls给它的。进程不关心。

完成分页显示目录的功能
buffer是有限的，满了会阻塞，如果ls太慢也会sleep
能协作的基础是有shell，shell会创建一个管道，为ls创建进程，设置stdout为管道写端，对more同理。管道以文件的形式存在。
管道必须有父进程，数据是字节流，没有数据结构。消息队列可以多个不相干的进程来传递数据，而且message作为一个字节序列存储，message quenues是消息数组。是一个有意义的结构化。

直接的方式。不用系统调用send&receive，数据量最大，最快。
开始要创建共享区域。方便，高效，没有多余的拷贝。
每个进程都有私有地址空间，其中明确地设置了共享内存段。同一块物理内存映射到不同的地址空间中去。页表。。。
但必须同步数据访问。写的时候要上锁。同步互斥。