操作系统综合课程设计——银行家算法模拟
操作系统综合课程设计——银行家算法模拟综 合 课 程 设 计
银行家算法模拟
院 系：
班 级：
小组成员：
时 间：
指导老师：
目 录
一、题目 1
二、设计目的 1
三、问题分析 1
四、设计要求 2
五、设计方案 2
5.1 问题分析 2
5.2 安全和不安全的状态分析 3
5.3 银行家算法伪代码(Pseudo-code) 4
六、说明 5
七、程序流图 5
八、运行结果 7
九、总结 9
十、参考文献 10
附件：源程序 10
一、题目
银行家算法模拟。
二、设计目的
操作系统是计算机系统的核心系统软件，它负责控制和管理整个系统的资源并组织用户协调使用这些资源，使计算机高效的工作。《操作系统课程设计》是《操作系统》理论课的必要补充，是复习和检验所学课程的重要手段，本课程设计的目的是综合应用学生所学知识，通过实验环节，加深学生对操作系统基本原理和工作过程的理解，提高学生独立分析问题、解决问题的能力，增强学生的动手能力。
通过此课程设计，进行的一次全面的综合训练，使之更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。
三、问题分析
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格•迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
银行家算法是避免死锁的一个很优秀的算法。当进程申请一组资源时，需要检查申请者对资源的最大需求量，如果系统现存的各类资源的数量满足当前它对各类资源的最大需求量时，则满足其申请；否则，进程必须等待，直到其他进程释放足够的资源为止。即：仅当申请者可以在一定时间内无条件的归还它所申请的全部资源时，才进行资源分配。
银行家算法使安全状态下系统不会进入死锁，不安全状态可能进入死锁。因而在进行资源分配之前，先要计算分配的安全性，判断是否为安全状态。
四、设计要求
银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。设计完成后，要求写出一份详细的设计报告。
五、设计方案
编制银行家算法通用程序，并检测所给状态的系统安全性。
5.1 问题分析
假定有一个如下的处理程序：
Allocation Max Available
ＡＢＣＤ ＡＢＣＤ ＡＢＣＤ
P1 ００１４ ０６５６ １５２０
P2 １４３２ １９４２
P3 １３５４ １３５６
P4 １０００ １７５０
则会看到一个资源分配表，要判断是否为安全状态，首先先找出它的Need，Need即Max(最多需要多少资源)减去Allocation(原本已经分配出去的资源)，计算结果如下：
NEED
ＡＢＣＤ
０６４２
０５１０
０００２
０７５０
然后加一个全都为false的字段，得到如下的结果：
FINISH
false
false
false
false
接下来找出need比available小的(千万不能把它当成4位数 他是4个不同的数)：
NEED Available
ＡＢＣＤ ＡＢＣＤ
０６４２ １５２０
０５１０
０００２
０７５０
P2的需求小于能用的，所以配置给他再回收，如下所示：
NEED Available
ＡＢＣＤ ＡＢＣＤ
０６４２ １５２０
００００ １４３２
０００２－－－－－－－
０７５０ ２９５２
此时P2 FINISH的false要改成true(己完成)：
FINISH
false
true
false
false
接下来继续往下找，发现P3的需求为0002，小于能用的2952，所以资源配置给他再回收：
NEED Available
ＡＢＣＤ Ａ Ｂ Ｃ Ｄ
０６４２ ２ ９ ５ ２
００００ ＋１ ３ ５ ４
０００２－－－－－－－－－－
０７５０ ３ 12 10 6
同样的将P3的false改成true：
FINISH
false
true
true
false
依此类推，做完P4→P1，当全部的FINISH都变成true时，就是安全状态。
5.2 安全和不安全的状态分析
在上述的处理程序中，如果所有过程有可能完成执行（终止），则一个状态（如上述范例）被认为是安全的。由于系统无法知道什么时候一个过程将终止，或者之后它需要多少资源，系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。在大多数情况下，这是一个合理的假设，因为系统不是特别关注每个进程运行了多久（至少不是从避免死锁的角度）。此外，如果一个进程终止前没有获取其它能获取的最多的资源，它只是让系统更容易处理。
基于这一假设，该算法通过尝试寻找允许每个进程获得的最大资源并结束（把资源返还给系统）的进程请求的一个理想集合，来决定一个状态是否是安全的。不存在这个集合的状态都是不安全的。
5.3 银行家算法伪代码(Pseudo-code)
算法伪码
输入：总进程数，总资源数，各个进程对各类资源最大资源需求量，各个进程已经得到各类资源的资源量以及进程还需要各类资源的资源量
输出：进程的安全序列
main()
{
输出没有进程需要申请资源时的安全序列
while(输入需申请资源的进程号不合理)
{
重新输入
}
输入某进程申请的资源数
for (j=0;j<N;j++)
{
输入申请的资源数
if(输入申请的资源数大于还需要该类资源的资源量或者输入申请的资源数大于系统可用资源量)
{
申请不合理!请重新选择
}
if(输入符合要求)
{
changdata(int k) //尝试分配资源
chkerr(int s) //安全性检查
显示数据
}
}
}
尝试分配资源
changdata(int k)
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]-Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];
NEED[k][j]=NEED[k][j]-Request[j];
}
};
安全性检查
chkerr(int s)
{
设置两个工作向量Work=AVAILABLE;FINISH
if(FINISH==false&&NEED<=Work)
{
进程获得资源，可顺利执行，直至完成，从而释放资源
Work+=ALLOCATION;
Finish=true;
}
else
{
所有的进程Finish= true，则表示安全；否则系统不安全
}
}
六、说明
通过程序实现定义的进程，为各进程分配资源，具体过程是：首先在程序中定义了4类资源，数量分别为1,11,7,6。然后定义进程P1，P2，P3，P4，接着为各进程申请各资源，然后在程序执行并比较申请的资源数量与各资源所剩数量，若前者大于后者则申请失败，反之则成功。同时该程序可以撤消新建进程，也可以查看资源分配情况。
七、程序流图
八、运行结果
图 8-1 程序运行界面
程序运行时，有四个资源，数量分别为1、5、2、0，同时有四个进程，为各个进程分配一定的资源，程序根据设计的要求，为用户计算出各个进程还需要的资源量，同时输出没有进程需要申请资源时的安全序列。
图 8-2 错误的输入
根据程序的要求，输入还需要申请资源的进程号（从0到3，否则重新输入），由于输入错误，则进行提示，要求用户重新输入。
图 8-3 申请资源出错
输入还需要申请资源的进程号（从0到3，否则重新输入），输入需要申请资源的进程号在0到3这个范围内，则进入下一步，提示用户输入所需要的资源数量，如若申请的资源数量大于该进程还需要本类资源的资源量，则高数用户申请不合理，提示用户重新选择。
用户在选择过程中，可以参考程序中各进程还需要的资源量进行申请，如此不会在亲身过程中提示用户申请不合理的问题。
用户申请不合理后，提示用户申请的资源不合理，并进一步提示用户是否继续银行家算法演示，否则退出演示。
图 8-4 申请得到资源出错
根据各个进程已经得到的资源量以及还需要的资源量要求，进行合理的申请。如图，对进程2进行合理的资源申请，将申请的资源进行安全性检查，如若安全性检查通过，则表明可以分配。
分配之后提示用户是否继续演示银行家算法。此后的操作与上一步的操作基本相同，不同的是各个进程还需要的资源、各个进程已经得到的资源量以及各个资源的剩余资源量不同。
九、总结
此次试验研究的是银行家算法模拟问题。
实验按照课程实验设计的要求设计并编写出实验程序代码，完成了银行家算法模拟的问题。
实验过程中，对银行家算法模拟有一个更深层次的理解与认识。通过此次课程设计，并结合课堂知识的学习，对银行家的产生背景、用于解决哪一类问题，有了清晰地了解。
在此次课程实验中，设计前的设计思路很重要，只有思路清晰才能进行下一阶段的设计，这样才能完成整个程序的设计，完成整个文报告的书写。
课程设计这几天学到的东西将以前不清楚的现在都暴露了出来。
此次的课程设计深入了解了调度与死锁的问题，以及有关资源申请的问题、避免死锁的具体实施方法。深入了解了银行家算法的资源申请和资源分配的过程及原则。保证系统处于安全状态。
十、参考文献
《操作系统原理》，华中科技大学出版社，庞丽萍编著，第四版
《C程序设计 (第三版)》，清华大学出版社，谭浩强著
附件：源程序
银行家算法模拟
院 系：
班 级：
小组成员：
时 间：
指导老师：
目 录
一、题目 1
二、设计目的 1
三、问题分析 1
四、设计要求 2
五、设计方案 2
5.1 问题分析 2
5.2 安全和不安全的状态分析 3
5.3 银行家算法伪代码(Pseudo-code) 4
六、说明 5
七、程序流图 5
八、运行结果 7
九、总结 9
十、参考文献 10
附件：源程序 10
一、题目
银行家算法模拟。
二、设计目的
操作系统是计算机系统的核心系统软件，它负责控制和管理整个系统的资源并组织用户协调使用这些资源，使计算机高效的工作。《操作系统课程设计》是《操作系统》理论课的必要补充，是复习和检验所学课程的重要手段，本课程设计的目的是综合应用学生所学知识，通过实验环节，加深学生对操作系统基本原理和工作过程的理解，提高学生独立分析问题、解决问题的能力，增强学生的动手能力。
通过此课程设计，进行的一次全面的综合训练，使之更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。
三、问题分析
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格•迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
银行家算法是避免死锁的一个很优秀的算法。当进程申请一组资源时，需要检查申请者对资源的最大需求量，如果系统现存的各类资源的数量满足当前它对各类资源的最大需求量时，则满足其申请；否则，进程必须等待，直到其他进程释放足够的资源为止。即：仅当申请者可以在一定时间内无条件的归还它所申请的全部资源时，才进行资源分配。
银行家算法使安全状态下系统不会进入死锁，不安全状态可能进入死锁。因而在进行资源分配之前，先要计算分配的安全性，判断是否为安全状态。
四、设计要求
银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。设计完成后，要求写出一份详细的设计报告。
五、设计方案
编制银行家算法通用程序，并检测所给状态的系统安全性。
5.1 问题分析
假定有一个如下的处理程序：
Allocation Max Available
ＡＢＣＤ ＡＢＣＤ ＡＢＣＤ
P1 ００１４ ０６５６ １５２０
P2 １４３２ １９４２
P3 １３５４ １３５６
P4 １０００ １７５０
则会看到一个资源分配表，要判断是否为安全状态，首先先找出它的Need，Need即Max(最多需要多少资源)减去Allocation(原本已经分配出去的资源)，计算结果如下：
NEED
ＡＢＣＤ
０６４２
０５１０
０００２
０７５０
然后加一个全都为false的字段，得到如下的结果：
FINISH
false
false
false
false
接下来找出need比available小的(千万不能把它当成4位数 他是4个不同的数)：
NEED Available
ＡＢＣＤ ＡＢＣＤ
０６４２ １５２０
０５１０
０００２
０７５０
P2的需求小于能用的，所以配置给他再回收，如下所示：
NEED Available
ＡＢＣＤ ＡＢＣＤ
０６４２ １５２０
００００ １４３２
０００２－－－－－－－
０７５０ ２９５２
此时P2 FINISH的false要改成true(己完成)：
FINISH
false
true
false
false
接下来继续往下找，发现P3的需求为0002，小于能用的2952，所以资源配置给他再回收：
NEED Available
ＡＢＣＤ Ａ Ｂ Ｃ Ｄ
０６４２ ２ ９ ５ ２
００００ ＋１ ３ ５ ４
０００２－－－－－－－－－－
０７５０ ３ 12 10 6
同样的将P3的false改成true：
FINISH
false
true
true
false
依此类推，做完P4→P1，当全部的FINISH都变成true时，就是安全状态。
5.2 安全和不安全的状态分析
在上述的处理程序中，如果所有过程有可能完成执行（终止），则一个状态（如上述范例）被认为是安全的。由于系统无法知道什么时候一个过程将终止，或者之后它需要多少资源，系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。在大多数情况下，这是一个合理的假设，因为系统不是特别关注每个进程运行了多久（至少不是从避免死锁的角度）。此外，如果一个进程终止前没有获取其它能获取的最多的资源，它只是让系统更容易处理。
基于这一假设，该算法通过尝试寻找允许每个进程获得的最大资源并结束（把资源返还给系统）的进程请求的一个理想集合，来决定一个状态是否是安全的。不存在这个集合的状态都是不安全的。
5.3 银行家算法伪代码(Pseudo-code)
算法伪码
输入：总进程数，总资源数，各个进程对各类资源最大资源需求量，各个进程已经得到各类资源的资源量以及进程还需要各类资源的资源量
输出：进程的安全序列
main()
{
输出没有进程需要申请资源时的安全序列
while(输入需申请资源的进程号不合理)
{
重新输入
}
输入某进程申请的资源数
for (j=0;j<N;j++)
{
输入申请的资源数
if(输入申请的资源数大于还需要该类资源的资源量或者输入申请的资源数大于系统可用资源量)
{
申请不合理!请重新选择
}
if(输入符合要求)
{
changdata(int k) //尝试分配资源
chkerr(int s) //安全性检查
显示数据
}
}
}
尝试分配资源
changdata(int k)
{
int j;
for (j=0;j<N;j++)
{
AVAILABLE[j]=AVAILABLE[j]-Request[j];
ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];
NEED[k][j]=NEED[k][j]-Request[j];
}
};
安全性检查
chkerr(int s)
{
设置两个工作向量Work=AVAILABLE;FINISH
if(FINISH==false&&NEED<=Work)
{
进程获得资源，可顺利执行，直至完成，从而释放资源
Work+=ALLOCATION;
Finish=true;
}
else
{
所有的进程Finish= true，则表示安全；否则系统不安全
}
}
六、说明
通过程序实现定义的进程，为各进程分配资源，具体过程是：首先在程序中定义了4类资源，数量分别为1,11,7,6。然后定义进程P1，P2，P3，P4，接着为各进程申请各资源，然后在程序执行并比较申请的资源数量与各资源所剩数量，若前者大于后者则申请失败，反之则成功。同时该程序可以撤消新建进程，也可以查看资源分配情况。
七、程序流图
八、运行结果
图 8-1 程序运行界面
程序运行时，有四个资源，数量分别为1、5、2、0，同时有四个进程，为各个进程分配一定的资源，程序根据设计的要求，为用户计算出各个进程还需要的资源量，同时输出没有进程需要申请资源时的安全序列。
图 8-2 错误的输入
根据程序的要求，输入还需要申请资源的进程号（从0到3，否则重新输入），由于输入错误，则进行提示，要求用户重新输入。
图 8-3 申请资源出错
输入还需要申请资源的进程号（从0到3，否则重新输入），输入需要申请资源的进程号在0到3这个范围内，则进入下一步，提示用户输入所需要的资源数量，如若申请的资源数量大于该进程还需要本类资源的资源量，则高数用户申请不合理，提示用户重新选择。
用户在选择过程中，可以参考程序中各进程还需要的资源量进行申请，如此不会在亲身过程中提示用户申请不合理的问题。
用户申请不合理后，提示用户申请的资源不合理，并进一步提示用户是否继续银行家算法演示，否则退出演示。
图 8-4 申请得到资源出错
根据各个进程已经得到的资源量以及还需要的资源量要求，进行合理的申请。如图，对进程2进行合理的资源申请，将申请的资源进行安全性检查，如若安全性检查通过，则表明可以分配。
分配之后提示用户是否继续演示银行家算法。此后的操作与上一步的操作基本相同，不同的是各个进程还需要的资源、各个进程已经得到的资源量以及各个资源的剩余资源量不同。
九、总结
此次试验研究的是银行家算法模拟问题。
实验按照课程实验设计的要求设计并编写出实验程序代码，完成了银行家算法模拟的问题。
实验过程中，对银行家算法模拟有一个更深层次的理解与认识。通过此次课程设计，并结合课堂知识的学习，对银行家的产生背景、用于解决哪一类问题，有了清晰地了解。
在此次课程实验中，设计前的设计思路很重要，只有思路清晰才能进行下一阶段的设计，这样才能完成整个程序的设计，完成整个文报告的书写。
课程设计这几天学到的东西将以前不清楚的现在都暴露了出来。
此次的课程设计深入了解了调度与死锁的问题，以及有关资源申请的问题、避免死锁的具体实施方法。深入了解了银行家算法的资源申请和资源分配的过程及原则。保证系统处于安全状态。
十、参考文献
《操作系统原理》，华中科技大学出版社，庞丽萍编著，第四版
《C程序设计 (第三版)》，清华大学出版社，谭浩强著
附件：源程序
程序代码：
课程设计_银行家算法.rar
