操作系统银行家算法

实验一进程调度实验学时：2学时实验类型：设计实验要求：必修一、实验目的多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。

因而引起进程调度。

本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。

二、实验内容1．优先权法、轮转法简化假设1）进程为计算型的（无I/O）2）进程状态：ready、running、finish3）进程需要的CPU时间以时间片为单位确定2．算法描述1）优先权法——动态优先权当前运行进程用完时间片后，其优先权减去一个常数。

2）轮转法三、流程图四、实验程序代码package进程调度;/***@author**/public class CPCB {private String name;private int time;private int count;public int getCount() {return count;}public void setCount(int count) { this.count = count;}public String getName() {return name;}public void setName(String name) { = name;}public int getTime() {return time;}public void setTime(int time) {this.time = time;}}package进程调度;/***@author**/class PCB{private String name;private int time ;private int priority ;public int getTime(){return time;}public void setTime(int time){this.time = time;}public int getPriority(){return priority;}public void setPriority(int priority){ this.priority = priority;}public String getName() {return name;}public void setName(String name) { = name;}}package进程调度;import java.util.LinkedList;/***@author**/class process{private final static int nap_time = 500;private LinkedList<PCB> queue = new LinkedList<PCB>();private LinkedList<CPCB> cqueue = new LinkedList<CPCB>();//优先权算法public void go(int p_Num) throws Exception{for(int i = 0;i<p_Num;i++){PCB pcb = new PCB();int time = (int)(Math.random()*20+1);int pri = (int)(Math.random()*20+4);pcb.setName("进程"+i);pcb.setTime(time);pcb.setPriority(pri);queue.add(pcb);}queue = this.sort(queue);int i=0;while(queue.size()!=0){PCB pcb = (PCB)queue.getFirst();System.out.println(i+"\t\t"+pcb.getName()+"运行\t"+"优先级:"+pcb.getPriority()+"---所需时间:"+pcb.getTime());// Thread.sleep(nap_time);int pre = pcb.getPriority() - 3;int time = pcb.getTime() - 1;if(time<=0){System.out.println(pcb.getName()+"\t\t进程运行结束");PCB p = (PCB)queue.removeFirst();System.out.println("移除队列的进程是\t\t"+p.getName()+"\n队列中还有"+queue.size()+"个进程\n");}else{queue.remove();pcb.setPriority(pre);pcb.setTime(time);// System.out.println("运行后:"+i+"----"+pcb.getName()+"---优先级:"+pcb.getPriority()+"---所需时间:"+pcb.getTime());queue.add(pcb);queue = this.sort(queue);}i++;}}//时间片轮转调度算法public void cycle(int p_Num) throws Exception{final int time = 3; //定义轮转时间片数for(int i = 0;i<p_Num;i++){CPCB cpcb = new CPCB();cpcb.setTime((int)(Math.random()*20)+1);cpcb.setName("进程"+i);cpcb.setCount(0);cqueue.add(cpcb);}while(cqueue.size()!=0){CPCB cpcb = (CPCB)cqueue.getFirst();while(cpcb.getCount()!=time){// Thread.sleep(nap_time);cpcb.setTime(cpcb.getTime() - 1);cpcb.setCount(cpcb.getCount()+1);for(int i=0;i<cqueue.size();i++)//输出进程运行情况{CPCB cpcb1 = (CPCB)cqueue.get(i);System.out.println(cpcb1.getName()+"\t\t所需时间片数"+cpcb1.getTime()+"\t\t已占用CPU时间片数"+cpcb1.getCount());}if(cpcb.getTime()==0){System.out.println(cpcb.getName()+"运行结束\n"+"-------------移除队列的是"+cpcb.getName()+"-------------");cqueue.removeFirst();System.out.println("-------------队列中还有"+cqueue.size()+"个进程--------------");break;}if(cpcb.getCount()==time){// cqueue.remove();System.out.println("----因为"+cpcb.getName()+"占用CPU时间片数"+cpcb.getCount()+"="+time);System.out.println(cpcb.getName()+"时间片运行结束"+cpcb.getCount()+cpcb.getTime());CPCB p = (CPCB)cqueue.removeFirst();cqueue.add(p);cpcb.setCount(0);break;}}}}public LinkedList<PCB> sort(LinkedList<PCB> processes){for(int i=0;i<processes.size();i++){PCB thread = new PCB();thread = processes.get(i);for(int j=i+1;j<processes.size();j++){if(thread.getPriority() < processes.get(j).getPriority()){PCB mythread = new PCB();mythread = thread;//thread = processes.get(j);processes.set(i, processes.get(j));processes.set(j, mythread);}}}return processes;}}package 进程调度;import java.io.BufferedReader;import java.io.InputStreamReader;/**** @author 邱福文**/public class MainFun{public void FPF(){}public static void main (String[] args) throws Exception{Integer n2;do{System.out.print("请输入进程数:");BufferedReader sin = new BufferedReader(new InputStreamReader(System.in));String str = sin.readLine();Integer n = Integer.parseInt(str);System.out.print("请输入调度算法:\n"+"1为优先权\n"+"2为轮转法\n"+"0 退出\n");BufferedReader sin2 = new BufferedReader(new InputStreamReader(System.in));String str2 = sin2.readLine();process p = new process();// do{n2 = Integer.parseInt(str2);switch(n2){case 0:break;case 1:p.go(n);break;case 2:p.cycle(n);break;default:System.out.print("输入有误请重新输入");break;}}while(n2!=0);}}五、实验结果请输入进程数:3请输入调度算法:1为优先权2为轮转法0 退出10 进程0运行优先级:19---所需时间:181 进程1运行优先级:19---所需时间:152 进程0运行优先级:16---所需时间:173 进程1运行优先级:16---所需时间:144 进程0运行优先级:13---所需时间:165 进程1运行优先级:13---所需时间:136 进程2运行优先级:10---所需时间:87 进程0运行优先级:10---所需时间:158 进程1运行优先级:10---所需时间:129 进程2运行优先级:7---所需时间:710 进程0运行优先级:7---所需时间:1411 进程1运行优先级:7---所需时间:1112 进程2运行优先级:4---所需时间:613 进程0运行优先级:4---所需时间:1314 进程1运行优先级:4---所需时间:1015 进程2运行优先级:1---所需时间:516 进程0运行优先级:1---所需时间:1217 进程1运行优先级:1---所需时间:918 进程2运行优先级:-2---所需时间:419 进程0运行优先级:-2---所需时间:1120 进程1运行优先级:-2---所需时间:821 进程2运行优先级:-5---所需时间:322 进程0运行优先级:-5---所需时间:1023 进程1运行优先级:-5---所需时间:724 进程2运行优先级:-8---所需时间:225 进程0运行优先级:-8---所需时间:926 进程1运行优先级:-8---所需时间:627 进程2运行优先级:-11---所需时间:1 进程2 进程运行结束移除队列的进程是进程2队列中还有2个进程28 进程0运行优先级:-11---所需时间:829 进程1运行优先级:-11---所需时间:530 进程0运行优先级:-14---所需时间:731 进程1运行优先级:-14---所需时间:432 进程0运行优先级:-17---所需时间:633 进程1运行优先级:-17---所需时间:334 进程0运行优先级:-20---所需时间:535 进程1运行优先级:-20---所需时间:236 进程0运行优先级:-23---所需时间:437 进程1运行优先级:-23---所需时间:1 进程1 进程运行结束移除队列的进程是进程1队列中还有1个进程38 进程0运行优先级:-26---所需时间:339 进程0运行优先级:-29---所需时间:240 进程0运行优先级:-32---所需时间:1进程0 进程运行结束移除队列的进程是进程0队列中还有0个进程请输入进程数:3请输入调度算法:1为优先权2为轮转法0 退出2进程0 所需时间片数8 已占用CPU时间片数1 进程1 所需时间片数6 已占用CPU时间片数0 进程2 所需时间片数13 已占用CPU时间片数0 进程0 所需时间片数7 已占用CPU时间片数2 进程1 所需时间片数6 已占用CPU时间片数0 进程2 所需时间片数13 已占用CPU时间片数0 进程0 所需时间片数6 已占用CPU时间片数3 进程1 所需时间片数6 已占用CPU时间片数0 进程2 所需时间片数13 已占用CPU时间片数0 ----因为进程0占用CPU时间片数3=3进程0时间片运行结束36进程1 所需时间片数5 已占用CPU时间片数1 进程2 所需时间片数13 已占用CPU时间片数0 进程0 所需时间片数6 已占用CPU时间片数0 进程1 所需时间片数4 已占用CPU时间片数2 进程2 所需时间片数13 已占用CPU时间片数0 进程0 所需时间片数6 已占用CPU时间片数0 进程1 所需时间片数3 已占用CPU时间片数3 进程2 所需时间片数13 已占用CPU时间片数0 进程0 所需时间片数6 已占用CPU时间片数0 ----因为进程1占用CPU时间片数3=3进程1时间片运行结束33进程2 所需时间片数12 已占用CPU时间片数1 进程0 所需时间片数6 已占用CPU时间片数0 进程1 所需时间片数3 已占用CPU时间片数0 进程2 所需时间片数11 已占用CPU时间片数2 进程0 所需时间片数6 已占用CPU时间片数0 进程1 所需时间片数3 已占用CPU时间片数0 进程2 所需时间片数10 已占用CPU时间片数3 进程0 所需时间片数6 已占用CPU时间片数0----因为进程2占用CPU时间片数3=3进程2时间片运行结束310进程0 所需时间片数5 已占用CPU时间片数1 进程1 所需时间片数3 已占用CPU时间片数0 进程2 所需时间片数10 已占用CPU时间片数0 进程0 所需时间片数4 已占用CPU时间片数2 进程1 所需时间片数3 已占用CPU时间片数0 进程2 所需时间片数10 已占用CPU时间片数0 进程0 所需时间片数3 已占用CPU时间片数3 进程1 所需时间片数3 已占用CPU时间片数0 进程2 所需时间片数10 已占用CPU时间片数0 ----因为进程0占用CPU时间片数3=3进程0时间片运行结束33进程1 所需时间片数2 已占用CPU时间片数1 进程2 所需时间片数10 已占用CPU时间片数0 进程0 所需时间片数3 已占用CPU时间片数0 进程1 所需时间片数1 已占用CPU时间片数2 进程2 所需时间片数10 已占用CPU时间片数0 进程0 所需时间片数3 已占用CPU时间片数0 进程1 所需时间片数0 已占用CPU时间片数3 进程2 所需时间片数10 已占用CPU时间片数0 进程0 所需时间片数3 已占用CPU时间片数0 进程1运行结束-------------移除队列的是进程1--------------------------队列中还有2个进程--------------进程2 所需时间片数9 已占用CPU时间片数1 进程0 所需时间片数3 已占用CPU时间片数0 进程2 所需时间片数8 已占用CPU时间片数2 进程0 所需时间片数3 已占用CPU时间片数0 进程2 所需时间片数7 已占用CPU时间片数3 进程0 所需时间片数3 已占用CPU时间片数0 ----因为进程2占用CPU时间片数3=3进程2时间片运行结束37进程0 所需时间片数2 已占用CPU时间片数1 进程2 所需时间片数7 已占用CPU时间片数0 进程0 所需时间片数1 已占用CPU时间片数2 进程2 所需时间片数7 已占用CPU时间片数0 进程0 所需时间片数0 已占用CPU时间片数3 进程2 所需时间片数7 已占用CPU时间片数0 进程0运行结束-------------移除队列的是进程0--------------------------队列中还有1个进程--------------进程2 所需时间片数6 已占用CPU时间片数1进程2 所需时间片数4 已占用CPU时间片数3----因为进程2占用CPU时间片数3=3进程2时间片运行结束34进程2 所需时间片数3 已占用CPU时间片数1进程2 所需时间片数2 已占用CPU时间片数2进程2 所需时间片数1 已占用CPU时间片数3----因为进程2占用CPU时间片数3=3进程2时间片运行结束31进程2 所需时间片数0 已占用CPU时间片数1进程2运行结束-------------移除队列的是进程2--------------------------队列中还有0个进程--------------请输入进程数:实验二银行家算法一、实验目的死锁会引起计算机工作僵死，因此操作系统中必须防止。

银行家算法总结银行家算法是一种经典的避免死锁的算法，在操作系统中得到了广泛的应用。

本文将对银行家算法进行总结，介绍其原理和应用。

## 1. 银行家算法简介银行家算法是一种资源分配和安全性检查的算法，用于避免在多个进程竞争有限资源时产生死锁。

它通过预先分配资源，检查每个进程请求资源后是否会导致系统进入不安全状态，从而避免死锁的发生。

## 2. 银行家算法原理银行家算法基于以下前提条件和原理：- 每个进程对资源的最大需求量是固定的，并在程序开始时规定。

- 系统中的资源被分为多类，每类资源的数目也是固定的。

- 每个进程在请求资源时需要指定所需资源的数量。

- 当进程请求资源时，系统会先检查此次请求是否安全，如果安全则分配资源，否则将此次请求置于等待状态。

银行家算法的原理可以归纳为以下几个步骤：1. 初始化阶段：系统初始化可分配资源和进程的最大需求量，并记录当前已分配资源和已请求资源的情况。

2. 请求资源阶段：当进程请求资源时，系统首先判断此次请求是否会导致系统进入不安全状态。

3. 安全检查阶段：系统通过安全性检查算法，判断当前系统状态下是否有足够的资源分配给进程，避免产生死锁。

4. 分配资源阶段：如果系统通过安全检查，则分配资源给进程，并将进程从等待状态转换为运行状态。

5. 进程释放资源：当进程完成任务后，释放已分配的资源。

6. 终止进程阶段：在释放资源后，检查是否有其他进程的请求可以被满足，如果满足则继续分配资源。

## 3. 银行家算法应用场景银行家算法主要应用于多进程共享有限资源的场景，如操作系统、数据库管理系统等。

以下是一些常见的应用场景：1. 操作系统资源管理：在多任务操作系统中，为了确保资源的高效利用，避免死锁的发生，可以使用银行家算法进行资源分配和调度。

2. 分布式系统：在分布式系统中，各个节点之间可能存在资源争用的情况。

使用银行家算法可以保证资源的分配和调度是安全的，避免死锁和资源竞争。

3. 并发编程：在并发编程中，多个线程可能会竞争同一资源。

操作系统银行家算法1. 简介1.1 定义：银行家算法是一种用于避免死锁的资源分配策略，通过判断当前状态是否安全来决定是否为进程提供所需资源。

1.2 目的：保证系统能够按照合理顺序进行并发执行，并防止出现死锁情况。

2. 死锁概述在多道程序环境下，当两个或更多进程因竞争有限数量的资源而无限等待时就会产生死锁。

常见原因包括互斥、占有和不可剥夺性以及循环等待条件。

3. 资源管理模型操作系统中使用了三类数据结构：- 可利用向量(Avlable)：表示每种类型可被分配给各个进程实例数目；- 最大需求矩阵(Maximum)：记录每个进程对某类资源最大需要量；- 分配矩阵(Allocation) ：描述已经成功地将某些单位从总体汇集转移到具体过渡态；4. 进展与请求检查流程（Safety Algorithm）当一个新任务到达后，在满足以下所有条件之前不能接受它: a）如果存在这样一个i使得Request[i] > Need[i]，则拒绝请求；b）如果存在这样一个i使得Request[i] > Avlable，则不接受该进程的资源申请。

5. 安全状态检查流程（Safety Algorithm）当新任务到达后，在满足以下所有条件之前不能接受它:a) 如果有某个j, 且Work[j]<Need_i[j], 则将p加入集合T中;b) 若对于每个p∈ T 都有Allocation[p]+ Work >= Need_p ，将p从T移到Finish，并释放其占用的全部资源。

6. 算法实现步骤1）初始化：定义Avlable、Max和Allocation矩阵以及Need数组；2）判断是否安全：使用银行家算法进行系统当前状态下是否会发生死锁的判断；3）处理用户请求：- 检查用户请求所需资源量与可利用向量(Avlable)比较，如大于可利用向量或者超过最大需求(Maximum)，则拒绝分配给该进程；- 分配成功时更新相关数据结构(如Avlable、Allocation等);4）回收已完成进程所占据的资源并重新计算各项指标值。

操作系统实验⼆：银⾏家算法实验⼆银⾏家算法⼀、实验⽬的1、了解什么是操作系统安全状态和不安全状态；2、了解如何避免系统死锁；3、理解银⾏家算法是⼀种最有代表性的避免死锁的算法，掌握其实现原理及实现过程。

⼆、实验内容根据银⾏家算法的基本思想，编写和调试⼀个实现动态资源分配的模拟程序，并能够有效避免死锁的发⽣。

三、实验原理进程申请资源时，系统通过⼀定的算法判断本次申请是否不可能产⽣死锁（处于安全状态）。

若可能产⽣死锁（处于不安全状态），则暂不进⾏本次资源分配，以避免死锁。

算法有著名的银⾏家算法。

1、什么是系统的安全状态和不安全状态？所谓安全状态，是指如果系统中存在某种进程序列＜P1，P2，…，Pn＞，系统按该序列为每个进程分配其所需要的资源，直⾄最⼤需求，则最终能使每个进程都可顺利完成，称该进程序列＜P1，P2，…，Pn，＞为安全序列。

如果不存在这样的安全序列，则称系统处于不安全状态。

2、银⾏家算法把操作系统看作是银⾏家，操作系统管理的资源相当于银⾏家管理的资⾦，进程向操作系统请求分配资源相当于⽤户向银⾏家贷款。

为保证资⾦的安全，银⾏家规定:(1) 当⼀个顾客对资⾦的最⼤需求量不超过银⾏家现有的资⾦时就可接纳该顾客;(2) 顾客可以分期贷款，但贷款的总数不能超过最⼤需求量;(3) 当银⾏家现有的资⾦不能满⾜顾客尚需的贷款数额时,对顾客的贷款可推迟⽀付,但总能使顾客在有限的时间⾥得到贷款;(4) 当顾客得到所需的全部资⾦后,⼀定能在有限的时间⾥归还所有的资⾦。

操作系统按照银⾏家制定的规则设计的银⾏家算法为：（1）进程⾸次申请资源的分配：如果系统现存资源可以满⾜该进程的最⼤需求量，则按当前的申请量分配资源，否则推迟分配。

（2）进程在执⾏中继续申请资源的分配：若该进程已占⽤的资源与本次申请的资源之和不超过对资源的最⼤需求量，且现存资源能满⾜该进程尚需的最⼤资源量，则按当前申请量分配资源，否则推迟分配。

（3）⾄少⼀个进程能完成：在任何时刻保证⾄少有⼀个进程能得到所需的全部资源⽽执⾏到结束。

简述银行家算法银行家算法，也称为银行家安全算法，是一种用于避免系统资源的死锁现象的算法。

在操作系统中，当多个进程需要同时访问同一组资源并且它们的访问不可分割时，就会产生死锁现象。

在这种情况下，所有的进程都会被阻塞，无法进行任何工作。

银行家算法通过对系统资源的分配和管理，可以避免死锁现象的发生。

它主要包括以下几个步骤：1. 初始化系统：在系统启动时，需要确定每种类型的资源的数量和可用数量，并记录每个进程需要的最大资源数和已经分配的资源数。

2. 进行资源请求：当一个进程需要资源时，会向系统发送一个资源请求。

该请求指定了进程需要的资源类型和数量。

如果系统中有足够的资源可以分配给该进程，那么分配成功并将资源分配给该进程。

3. 检查资源分配是否安全：在分配资源之前，需要检查分配后系统是否处于安全状态。

安全状态是指在分配后，所有进程都能够完成它们的工作并释放所有资源。

如果系统处于安全状态，则分配资源并通知进程可以执行它们的任务。

4. 回收资源：当进程完成任务后，会释放它所占用的所有资源并通知系统。

系统会将这些资源重新分配给其他进程。

在银行家算法中，对于每个进程，都会维护一个资源请求向量和一个安全向量。

资源请求向量包含了进程当前所需要的资源数量，安全向量包含了系统中未分配的资源数量。

当系统收到一个资源请求时，会将该请求向量加入到系统资源向量中，并检查是否存在一个安全序列，该安全序列满足所有进程都可以完成它们的任务并释放它们所占用的所有资源。

如果存在这样的安全序列，则分配资源并通知进程可以执行它们的任务；如果不存在，则拒绝资源请求并等待其他进程的资源释放。

通过使用银行家算法，可以避免系统中的死锁现象，保证所有进程都可以完成它们的任务。

这种算法被广泛应用于操作系统和其他复杂的软件系统中，是保障系统安全性的重要工具。

银行家算法总结一、银行家算法银行家算法（Banker’s Algorithm），又称银行家管理算法，是一种专门用于系统资源管理的算法，用于解决操作系统中多个用户对多类资源的竞争请求，从而保证合理地分配公共资源，解决资源分配问题，其目的是为了保证单个进程的安全运行，同时保证系统的安全运行。

二、银行家算法的定义银行家算法是一种用于解决多个用户对多类资源的竞争请求的算法，也称作资源分配算法或资源管理算法，它可以确定是否有足够的资源可供一个或多个进程安全运行，如果有足够的资源可供运行，则可以分配该资源，否则系统将进入不满足安全状态。

三、银行家算法的特点（1）安全性：银行家算法可以确定是否有足够的资源可以满足所有进程的最大要求，使系统处于安全态；（2）在安全态下，银行家算法能够有效地检查一个进程是否可以获得资源，并且可以确定该状态下的最优解；（3）银行家算法可以有效检查一个系统是否处于安全态，它可以检查任意多个资源种类的一组资源分配是否安全；（4）银行家算法可以防止死锁的发生，可以有效地确保非抢占式多处理机系统的安全运行；（5）银行家算法设计简单，容易实现，并十分快速；（6）银行家算法不是最优的，它只是一种有效的搜索算法，其实现效率较低；四、银行家算法的使用1、资源分配问题银行家算法可以用于操作系统中的多个用户对多类资源的竞争请求，以此保证资源的合理分配，从而解决资源分配问题。

它可以有效地检查一个进程是否可以获得资源，同时可以确定该状态下的最优解。

2、进程安全性银行家算法可以用于检查一个系统是否处于安全态，并检查任意多个资源种类的一组资源分配是否安全，可以保证系统的安全运行，从而保证单个进程的安全性。

3、防止死锁银行家算法可以防止死锁的发生，这是由于它可以确定是否有足够的资源可以满足所有进程的最大要求，使系统处于安全态，从而阻止死锁发生。

操作系统银⾏家算法（C++实现）1. 系统安全状态 系统在进⾏资源分配之前，应先计算此次资源分配的安全性，即判断系统当前拥有的资源数，是否满⾜该进程⽬前所需要的资源数，若满⾜则将该进程运⾏完毕，并将在此之前分配给该进程的资源释放，然后继续推进，该推进顺序为安全序列；若⽆法满⾜，则称当前系统处于不安全状态。

2. 银⾏家算法中的数据结构可⽤资源向量Available。

其中含有 m 个元素（m 即为资源种类），Available[ j ] 的值表⽰，当前资源 j 所拥有的个数。

最⼤需求矩阵Max。

这是⼀个n * m的矩阵（n 即为进程个数），Max[ i ][ j ] 的值表⽰，进程 i 对于资源 j 的最⼤需求值。

分配矩阵Allocation。

这是⼀个n * m的矩阵，Allocation[ i ][ j ] 的值表⽰，当前系统对于进程 i 已分配资源 j 的个数。

需求矩阵Need。

这是⼀个n * m的矩阵，Need[ i ][ j ] 的值表⽰，当前进程 i 对于资源 j 的需求个数。

上述三个矩阵满⾜如下关系： Need[ i ][ j ] = Max[ i ][ j ] - Allocation[ i ][ j ]3. 银⾏家算法 设 Request i 是进程 P i的请求向量，如果 Request i[ j ] = K, 表⽰进程 P i需要K个 R j类的资源。

当 P i 发出资源请求后，系统按下述步骤进⾏检查：1. 如果 Request i[ j ] <= Need[ i ][ j ] ,便转向步骤（2）；否则认为出错，因为它所需要的资源超过所宣布的最⼤值。

2. 如果 Request i[ j ] <= Available[ j ]，便转向步骤（3）；否则，表⽰尚⽆⾜够资源，P i需等待。

3. 系统尝试着把资源分配给进程Pi，并修改下⾯数据结构中的数值： Available[ j ] -= Request i[ j ]; Allocation[ i ][ j ] += Request i[ j ]; Need[ i ][ j ] -= Request i[ j ]; 4. 系统执⾏安全性算法，检查此次资源分配后是否安全。

操作系统实验之银行家算法操作系统实验中的银行家算法复杂难懂，那么我们究竟要怎么去理解呢?下面由店铺为大家整理了操作系统实验银行家算法的相关知识，希望大家喜欢!操作系统实验——银行家算法一、实验目的1、理解银行家算法。

2、掌握进程安全性检查的方法与资源分配的方法。

二、实验内容与基本要求编制模拟银行家算法的程序，并以下面给出的例子验证所编写的程序的正确性。

进程已占资源最大需求数资源种类 A B C D A B C DP0 0 0 1 2 0 0 1 2P1 1 0 0 0 1 7 5 0P2 1 3 5 4 2 3 5 6P3 0 6 3 2 0 6 5 2P4 0 0 1 4 0 6 5 6现在系统中A、B、C、D 4类资源分别还剩1、5、2、0个，请按银行家算法回答：1、现在系统是否处于安全状态?2、如果现在进程P1提出需要(0、4、2、0)个资源的请求，系统能否满足它的请求?三、实验报告内容1、银行家算法和安全性检查算法原理银行家算法：银行家算法最初级原为银行系统设计，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。

在OS设计中，也可以用它来避免死锁。

为实现银行家算法，每个新进程在进入系统时它必须申明在运行过程中，可能需要的每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。

当某一进程请求时，系统会自动判断请求量是否小于进程最大所需，同时判断请求量是否小于当前系统资源剩余量。

若两项均满足，则系统试分配资源并执行安全性检查算法。

安全性检查算法 :安全性检查算法用于检查系统进行资源分配后是否安全，若安全系统才可以执行此次分配;若不安全，则系统不执行此次分配。

安全性检查算法原理为：在系统试分配资源后，算法从现有进程列表寻找出一个可执行的进程进行执行，执行完成后回收进程占用资源;进而寻找下一个可执行进程。

当进程需求量大于系统可分配量时，进程无法执行。

当所有进程均可执行，则产生一个安全执行序列，系统资源分配成功。

操作系统课程设计－银行家算法(流程图+源代码+设计报告)一、实验目的：熟悉银行家算法，理解系统产生死锁的原因及避免死锁的方法,加深记意。

二、实验要求：用高级语言编写和调试一个描述银行家算法的程序。

三、实验内容：1、设计一个结构体，用于描述每个进程对资源的要求分配情况。

包括：进程名--name[5]，要求资源数目--command[m]（m类资源），还需要资源数目--need[m]，已分配资源数目--allo[m]。

2、编写三个算法，分别用以完成：①申请资源；②显示资源；③释放资源。

（动态完成）四、程序流程图五、源程序：最新版本：bk5.c/*bk2.c::可以自定义进程及资源数目,可选择读文件或创建新文件,但不超过10,5*//*可修改# define NP 10*//* # define NS 5 */ /*资源种类*//*bk3.c::可以继续分配资源（〉2）*//*bk4.c::可保存分析结果*//*bk5.c::除以上功能外，对暂时不能分配的可以进行另外一次尝试,并恢复已分配的资源*/ /*四、程序流程图：五、源程序：最新版本：bk5.c/*bk2.c::可以自定义进程及资源数目,可选择读文件或创建新文件,但不超过10,5*//*可修改# define NP 10*//* # define NS 5 */ /*资源种类*//*bk3.c::可以继续分配资源（〉2）*//*bk4.c::可保存分析结果*//*bk5.c::除以上功能外，对暂时不能分配的可以进行另外一次尝试,并恢复已分配的资源*/ #include "string.h"#include "stdio.h"#include "dos.h"#include "conio.h"#define MOVEIN 1#define GUIYUE 2#define ACC 3#define OK 1#define ERROR 0#define MAXSH 7#define MAXSHL 10#define MAXINPUT 50#define maxsize 100int act;int ip=0;int line=0; /*line为要写的行号，全局变量*/int writeok;int right;char wel[30] = {"Welcome To Use An_Li System"};char ente[76]={" 警告：未经作者同意不得随意复制更改！"};char rights[40]={"Copyright (c) 2002"};struct date today;struct time now;typedef struct{int data[maxsize];int top;}stack;int emptystack(stack *S){if(S->top==48&&S->data[S->top]==35)return(1); /*35 is '#'*/ else return(0);}int push(stack *S,int x){if(S->top>=maxsize-1)return(-1);else{S->top++;S->data[S->top]=x;return(0);}}int gettop(stack *S){return S->data[S->top];}int pop(stack *S){if(emptystack(S)){printf("the stack is empty\n");exit(1);}else S->top--;return S->data[S->top+1];}void initstack(stack *S){int i;S->top=0;S->data[S->top]=35;}/*****模拟打字机的效果*********/delay_fun(){int i;void music();for(i=0;;i++){if(wel!='\0'){delay(1000);textcolor(YELLOW);gotoxy(26+i,8);cprintf("%c",wel);printf("谢谢");printf("网络 ");music(1,60);}else break;}delay(500000);for(i=0; ; i++){if(ente!='\0'){delay(1000);textcolor(RED);/*显示警告及版权*/ gotoxy(2+i,11);cprintf("%c",ente);music(1,60);}else break;}delay(40000);for(i=0;;i++){if(rights != '\0'){delay(1000);textcolor(YELLOW);gotoxy(30+i,14);cprintf("%c",rights);music(1,60);}elsebreak;}getch();}/*********登陆后的效果**********/logined(){ int i;clrscr();gotoxy(28,10);textcolor(YELLOW);cprintf("程序正在载入请稍候.....");gotoxy(35,12);for(i=0;i<=50;i++){gotoxy(40,12);delay(8000);cprintf("%02d%已完成",i*2);gotoxy(i+15,13);cprintf("\n");cprintf("|");}main0();}/*********对PC扬声器操作的函数****/void music(int loop,int f) /* f为频率*/{ int i;for(i=0;i<30*loop;i++){sound(f*20);delay(200);}nosound();}int analys(int s,int a){int hh,pos;switch(a){case (int)'i':hh=0;break;case (int)'+':hh=1;break;case (int)'*':hh=2;break;case (int)'(':hh=3;break;case (int)')':hh=4;break;case (int)'#':hh=5;break;case (int)'E':hh=6;break;case (int)'T':hh=7;break;case (int)'F':hh=8;break;default:{printf(" \n analys()分析发现不该有的字符 %c !(位置:%d)",a,ip+1); writeerror('0',"\n............分析出现错误!!!");writeerror(a,"\n 错误类型: 不该有字符 ");printf("谢谢");printf("网 ");return ERROR;}}pos=(s-48)*10+hh;switch(pos){case 3:case 43:case 63:case 73:act=4;return MOVEIN;case 0:case 40:case 60:case 70:act=5;return MOVEIN;case 11:case 81: act=6;return MOVEIN;case 92:case 22:act=7;return MOVEIN;case 84:act=11;return MOVEIN;/*-------------------------------------------*/ case 91:case 94:case 95:act=1;return GUIYUE;case 21:case 24:case 25:act=2;return GUIYUE;case 101:case 102:case 104:case 105:act=3;return GUIYUE;case 31:case 32:case 34:case 35:act=4;return GUIYUE;case 111:case 112:case 114:case 115:act=5;return GUIYUE;case 51:case 52:case 54:case 55:act=6;return GUIYUE;/*+++++++++++++++++*/case 15:return ACC;/*******************************/case 6:return 1;case 7:case 47:return 2;case 8:case 48:case 68:return 3;case 46:return 8;case 67:return 9;case 78:return 10;default:{if(a=='#')printf("");else printf(" \n analys() 分析发现字符%c 不是所期望的!(位置:%d)",a,ip+1);writeerror('0',"\n ...........分析出现错误!!!");writeerror(a,"\n 错误类型: 字符 ");writeerror('0'," 不是所期望的! ");printf("谢谢");printf("网 ");return ERROR;}}}int writefile(int a,char *st){FILE *fp;fp=fopen("an_slr.txt","a");if(fp==0){printf("\nwrite error!!");writeok=0;}else{if(a==-1){fprintf(fp," %s ",st); /*若a==－1则为添加的注释*/}else if(a==-2){getdate(&today);gettime(&now);fprintf(fp,"\n 测试日期： %d-%d-%d",today.da_year,today.da_mon,today.da_day); fprintf(fp," 测试时间：%02d:%02d:%02d",now.ti_hour,now.ti_min,now.ti_sec);}else if(a>=0) fprintf(fp,"\n step: %02d , %s",a,st);writeok=1;fclose(fp);}return writeok;}int writeerror(char a,char *st) /*错误类型文件*/{FILE *fpp;fpp=fopen("an_slr.txt","a");if(fpp==0){printf("\nwrite error!!");writeok=0;}else{if(a=='0') fprintf(fpp," %s ",st); /*若a=='0' 则为添加的注释*/else fprintf(fpp," %s \'%c\'(位置:%d) ",st,a,ip+1);writeok=1;fclose(fpp);}return writeok;}/*^^^^^^^^^^^^^^^^^^^^^^*/main0(){int an,flag=1,action,lenr;char a,w[MAXINPUT];int len,s,ss,aa,ana;stack *st;char r[MAXSH][MAXSHL]; /*初始化产生式*/strcpy(r[0],"S->E");strcpy(r[1],"E->E+T");strcpy(r[2],"E->T");strcpy(r[3],"T->T*F");strcpy(r[4],"T->F");strcpy(r[5],"F->(E)");strcpy(r[6],"F->i");clrscr();printf("\nplease input analyse string:\n");gets(w);len=strlen(w);w[len]='#';w[len+1]='\0';initstack(st);push(st,48); /* (int)0 进栈*/writefile(-1,"\n------------------------SLR(1)词法分析器-------------------------");writefile(-1,"\n 计本003 安完成于2003.01.12 14:04");writefile(-1,"\n谢谢");writefile(-1,"网 ");writefile(-1,"\n 以下为串");writefile(-1,w);writefile(-1,"('#'为系统添加)的分析结果： ");writefile(-2," ");do{s=gettop(st);aa=(int)w[ip];action=analys(s,aa);if(action==MOVEIN){ss=48+act;push(st,aa);push(st,ss); /* if ss=4 int =52 */ip++;}else if(action==GUIYUE){lenr=strlen(r[act])-3;for(an=0;an<=2*lenr-1;an++)pop(st); /* #0 */s=gettop(st); /* s=0 */push(st,(int)r[act][0]);/*将产生式左端 F 进栈 */ana=analys(s,(int)r[act][0])+48;if(ana>59)printf("\分析出错:ana>59!!!");push(st,ana);/*analys(s,aa)即为goto(s',aa) */if((line+1)%20==0){printf("\nThis screen is full,press any key to continue!!!");getche();clrscr();}printf(" step %02d: %s\n",line++,r[act]);writefile(line,r[act]);}else if(action==ACC){flag=0;right=1;}else if(action==ERROR){flag=0;right=0;} /*接受成功*/else{flag=0;right=0;} /* 出错*/}while(flag==1);if(right==1)printf("\nok,输入串 %s 为可接受串!!",w);if(right==0)printf("\nsorry,输入串 %s 分析出错!!",w);if(writeok==1){printf("\nAnWin soft have wrote a file an_slr.txt");if(right==1)writefile(-1,"\n最终结果：输入串为可接受串!"); }}main() /*主函数*/{clrscr();delay_fun();logined();}六、测试报告－操作系统课程设计－银行家算法(流程图+源代码+设计报告)六、测试报告：（测试结果保存于系统生成的an.txt 文件中）以下为课本上的实例：：-------------------------------------------------------------------------------------========================银行家算法测试结果=========================-------------------------------------------------------------------------------------T0 时刻可用资源(Available) A:3, B:3, C:2测试日期： 2003-6-28 请求分配时间： 14:07:29经测试，可为该进程分配资源。

3 课程设计三银行家算法（参考1）1设计目的（1）了解多道程序系统中，多个进程并发执行的资源分配。

（2）掌握死锁产生的原因、产生死锁的必要条件和处理死锁的基本方法。

（3）掌握预防死锁的方法，系统安全状态的基本概念。

（4）掌握银行家算法，了解资源在进程并发执行中的资源分配策略。

（5）理解避免死锁在当前计算机系统不常使用的原因。

2．算法描述Dijkstra(1965年)提出了一种能够避免死锁的调度方法，称为银行家算法，它的模型基于一个小城镇的银行家，现将该算法描述如下：假定一个银行家拥有资金，数量为Σ，被N个客户共享。

银行家对客户提出下列约束条件：（1）每个客户必须预先说明自已所要求的最大资金量；（2）每个客户每次提出部分资金量申请各获得分配；（3）如果银行满足了客户对资金的最大需求量，那么，客户在资金动作后，应在有限时间内全部归还银行。

只要每个客户遵守上述约束，银行家将保证做到：若一个客户所要求的最大资金量不超过Σ，则银行一定接纳该客户，并可处理他的资金需求；银行在收到一个客户的资金申请时，可能因资金不足而让客户等待，但保证在有限时间内让客户获得资金。

在银行家算法中，客户可看做进程，资金可看做资源，银行家可看做操作系统。

3. 环境操作系统Windows XP SP2,开发工具VC++6.0或者BCB6.0。

4 功能模块说明1.银行家所能够提供的资源typedef struct node{int a;int b;int c;int remain_a;int remain_b;int remain_c;}bank;2.进程所占用的资源typedef struct node1{char name[20];int a;int b;int c;int need_a;int need_b;int need_c;}process;main()函数：完成对系统运行环境的初始化，定义了简单的选择菜单，调用各功能函数。