银行家算法通用演示程序.doc

青岛理工大学操作系统课程设计报告院（系）： 专业： 学生姓名: 班级： 学号: 题目： 银行家算法通用演示程序 起迄日期: 设计地点: 指 导 教 师: 20102011年度 第 2 学期完成日期: 2011 年 7月 2日目录一、课程设计目的2二、课程设计内容2三、系统分析与设计31、系统分析32、系统设计：42.1、模块设计：42.2、数据结构说明：62.3、算法流程图：7四、模块调试与系统测试121、模块调试122、系统测试123、调试分析：14五、用户手册15六、程序清单17七、体会与自我评价26八、参考文献27九、课程设计评价27一、 课程设计目的操作系统是一门重要的专业基础课，是涉及较多硬件知识的计算机系统软件课程。操作系统是计算机系统的核心软件，它负责控制和管理整个系统的资源，并组织用户协调使用这些资源，提高计算机的工作效率。在计算机软硬件课程的设置上，它起着承上启下的作用。进行操作系统课程设计主要是在学习操作系统课程的基础上，在完成操作系统各部分实验的基础上，对操作系统的整体进行一个模拟，通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、创新能力及团队组织、协作开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。银行家算法主要用于解决多种资源被多个独立执行的程序使用的安全算法。银行家算法采用矩阵存储资源的数据，通过对系统资源预分配后检查系统状态，以避免死锁的产生。Dijkstra (1965)提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。二、课程设计内容本次课程设计是编写一个银行家算法通用演示程序。银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。 要解释银行家算法，必须先解释操作系统安全状态和不安全状态。 安全序列是指一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和。 安全状态：如果存在一个由系统中所有进程构成的安全序列P1，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。 不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。银行家算法：我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。银行家算法通用演示程序要求： 1) 资源种类与数目可在界面进行设置，在资源分配过程中可以随时增加进程及其对资源的需求 2) 可读取样例数据（要求存放在外部文件中）进行资源种类、数目与进程数的初始化 3) 在资源分配过程中可以随时进行系统安全状态检测 4) 如果能够通过系统安全状态检测，则系统对该进程进行资源分配；当进程满足所有资源分配后能够自行释放所有资源，退出资源竞争 5) 具有一定的数据容错性 三、系统分析与设计1、系统分析银行家算法通用演示程序是对操作系统中“银行家算法”的模拟，银行家算法是操作系统中一种最具代表性的避免死锁的算法。为了读取样例数据进行资源种类、数目与进程数的初始化，本程序可以打开预先写好txt文件，文件中包含操作系统中的资源信息和进程信息，也可以通过对信息的编辑，来实现自行输入这两种信息。资源种类与数目可在界面进行设置，在资源分配过程中可以随时增加进程及其对资源的需求。在编辑信息时，可以修改资源和进程的各种信息，包括添加、修改和删除。确定信息后，可以通过检查系统安全性，来显示系统的安全序列或者显示系统处于不安全状态。请求资源功能实现了进程请求系统中资源的模拟。如果能够通过系统安全状态检测，则系统对该进程进行资源分配；当进程满足所有资源分配后能够自行释放所有资源，退出资源竞争。本系统利用Visual Studio 2010 .NET平台进行设计。银行家算法步骤(1)如果Requestij=Needi,j,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果Requestij=Availablej,则转向步骤(3)；否则，表示系统中尚无足够的资源，进程Pi必须等待。(3)系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Availablej=Availablej-Requestij; AllocationI,j=AllocationI,j+ Requestij; NeedI,j=NeedI,j- Requestij ;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，本次分配作废，恢复原来的资源状态，让进程Pi等待。安全性算法步骤(1)设置两个向量工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finishi=false，当有足够资源分配给进程时，令Finishi=true。(2)从进程集合中找到一个能满足下述条件的进程：Finishi=falseNeedor=Work如找到，执行步骤(3)；否则，执行步骤(4)。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Workj+Allocationi,j;Finishi=true; 转向步骤(2)。(4)如果所有进程的Finishi=true,则表示系统处于安全状态；否则，系统处于不安全状态。考虑到程序中要求添加资源，添加进程等，以上使用数组用.NE中的ArrayList 实现，可以实现动态的添加和删除。2、系统设计：系统总体设计方案：系统主界面：菜单栏，导航到该程序的各个功能，包括编辑，检查及帮助信息；快捷菜单栏，实现该程序的各个功能，包括打开文件，保存文件，安全序 列检查，请求资源；显示当前系统的信息，显示对各种资源的最大需求（max），已分配资源（allocation），需求资源（need），系统可用资源（available）。文件选项： 包含打开文件、保存文件和退出功能。编辑选项： 包含对资源信息和进程信息的编辑，有添加、修改、删除功能。检查选项： 包含显示当前安全序列和请求资源的功能。关于选项： 显示该程序的相关版本信息。2.1、模块设计：主界面模块：该模块的功能是显示进程信息，是其他模块的入口，通过主界面模块能调用其他模块。资源信息模块：该模块的功能是显示资源信息，和对资源信息进行添加、删除和修改。该模块中的数据类型：ArrayList r_name 资源名称的集合ArrayList r_available 资源数量的集合其中：r_namei对应r_availablei该模块的主要函数： LoadResource() 用于实现加载资源信息AddResource() 用于实现增加资源信息DelResource() 用于实现删除资源信息EditResource() 用于实现修改资源信息 进程信息模块： 该模块的功能是显示进程信息，和对进程信息进行添加、删除和修改。 该模块的数据类型： CProcess p 进程类 ArrayList r_max 进程对资源的最大需求 ArrayList r_allocation进程已分配的资源数量 ArrayList r_need 进程还需要的资源数量 其中：r_maxi r_allocationi r_needi对应系统中的第i类资源 该模块的主要函数： LoadProcess() 用于实现加载进程信息 AddProcess() 用于实现增加进程 DelProcess() 用于实现删除进程 EditResource() 用于修改当前进程的资源信息 安全序列模块： 该模块的功能是检查系统是否处于安全状态，并显示所有安全序列。 该模块的数据类型： SystemInfo current 符合条件的进程信息int rq_pcount 符合条件的进程数目ArrayList rq_able 保存符合条件的进程 ArrayList work 当前系统的可用资源 ArrayList rq_finish 系统中是否有足够资源分配 int security_count 当前安全序列数目 string security_string 保存当前安全序列 ArrayList resultClo 保存符合条件的进程信息的集合 其中：worki=r_allocationi+r_availablei Rq_finish中元素的类型为bool型 该模块的主要函数： CheckSecurity() 找出当前有足够资源分配的进程 compare() 判断当前资源是否满足当前进程的需求 ExistSecurity () 检查并查找安全序列请求资源模块： 该模块对进程请求资源进行计算，能判断请求资源是否合法，并计算出安全序列 该模块的数据类型： ArrayList rq 提出请求资源的进程的请求资源信息 int pIndex 提出请求的进程index ArrayList p_bak 进程副本 ArrayList r_bak 资源副本 其中：r_needi=r_needi-rqi 该模块的主要函数： CheckRequest() 检查请求资源是否合法，合法则找出安全序列程序的模块层次关系：主模块文件打开保存模块进程资源编辑模块安全性检查模块2.2、数据结构说明：程序中的类： public class CProcess /进程类 public string p_name; /进程名称 public ArrayList r_max; /进程最大需求的资源数量 public ArrayList r_allocation; /进程已分配的资源数量 public ArrayList r_need; /进程还需要的资源数量 public CProcess(string name, int count)/构造方法，初始化进程信息 public void CopyFrom(CProcess p) /复制进程信息 public bool AddResource(int max, int alloc)/增加进程资源 public bool EditResource(int index, int max, int alloc)/编辑index位置的进程的资源息 public bool DelResource(int index) /删除index位置的进程的资源 public class SystemInfo /系统当前信息类int p_count;/系统进程数 int r_count;/系统的资源种类数 public int rq_pcount; /满足条件的进程数 public ArrayList rq_able; /满足条件的进程 public ArrayList rq_finish; /进程状态 public ArrayList work; /系统中可用的资源数 public SystemInfo(int pCount, int rcout)/构造方法,初始化 public void CopyFrom(SystemInfo sysInfo)/复制当前系统信息 public class MainBanker /主类，银行家算法 public ArrayList plist = new ArrayList(); /进程集合 public ArrayList r_name; /各类资源名称集合 public ArrayList r_available; /各类资源数量集合 public int pIndex; /提出请求的进程index public ArrayList rq = new ArrayList(); /提出请求的进程请求资源数目 public ArrayList p_bak = new ArrayList(); /进程副本集合 public ArrayList r_bak; /资源副本集合 public ArrayList resultClo; /符合条件的进程集合，SystemInfo类型 SystemInfo current; /保存当前系统的进程信息 public int security_count;/当前安全序列进程数目 public string security_string; /安全序列 public MainBanker() /构造方法 public bool LoadFile(string filename)/读取文本内容函数，初始化进程和资源信息 public bool SaveFile(string filename)/保存进程和资源信息public bool AddResource(string name, int max)/增加资源 public bool DelResource( int index)/删除资源信息 public bool EditResource(int index, int available)/编辑资源信息 public CProcess GetProcess(string pname)/改进进程名查找匹配的进程 public CProcess AddProcess(string pname)/增加进程 public bool DelProcess(string pname)/删除进程 public bool CheckSecurity()/检查系统是否安全 public bool compare(ArrayList a, ArrayList b)/判断该进程是否满足条件 public bool ExistSecurity () /查找安全序列 public void Add(ArrayList a, ArrayList b)/释放的资源和当前资源总和 public void Sub(ArrayList a, ArrayList b)/请求资源后的资源信息 public bool EditRequestResource(int index, int count)/编辑请求资息public bool CheckRequest(bool AllocIfCan)/检查请求资源 2.3、算法流程图： 主模块流程图：否是是否否是开始显示程序主界面读取文本内容添加信息编辑资源信息编辑进程信息读取文件? 安全序列请求资源结束检查请求是否安全？保存保存系统当前信息？ 编辑信息模块流程图：否否开始编辑资源信息编辑进程信息删除资源修改资源添加进程删除进程是否合法？是否合法？结束添加资源是是修改进程检查模块流程图：是否否开始请求资源是否合法？是存在安全序列？显示安全序列结束检查并显示安全序列的流程图：否是是否是开始满足条件的进程数目为0？提示进程信息调用函数CheckSecurity（判断当前系统资源满足进程需求）needi =worki?调用函数ExistSecurity（判断是否有安全序列）存在安全序列？显示所有安全序列否提示不存在安全序列提示不存在安全序列结束四、模块调试与系统测试1、模块调试l 输入的形式和输入值的范围银行家算法通用演示程序是可视化程序，输入形式有两种，一是通过打开文件方式，二是自行输入。进行输入时输入的信息必须是字符或整形数据，字符数据的取值范围是（AZ，az），整形数据的取值范围是（065535），当输入数据错误时，系统会显示提示信息。l 输出的形式程序的输出是以对话框的形式输出，包括提示信息，程序运行结果等。l 程序所能达到的功能打开文件：实现从文本文档中读取资源信息和进程信息，可读取样例数据进行资源种类、数目与进程数的初始化；保存文件：实现将当前的资源信息和进程信息保存到文本文档中；资源信息：编辑资源信息，包含对资源的添加、修改、删除的功能；进程信息：编辑进程信息，包含对进程的添加、修改、删除的功能；安全序列：若系统处于安全状态，则显示所有安全序列，若系统处于不安全状态，则弹出提示信息对话框；请求资源：实现对进程请求资源的分析，若符合条件，则可以显示安全序列，若不符合条件，则弹出提示信息对话框；关于：显示银行家算法通用演示程序的相关信息。2、系统测试测试方法：黑盒、白盒等 测试技术：单元测试、功能测试、场景测试 单元测试应用背景：它是从开发者的角度来编写的，用于确保类的每个特定方法成功执行一系列特定的任务。每一个测试都要保证对于给定的一个已知的输入应该得到所期望的输出。手工测试方法，输入相应的数据查看相应的操作结果，并进行分析判断。功能测试应用背景：它是从使用者的角度来编写的，它关注系统提供的功能特征及其不同的处理条件；测试功能的不同处理流程（包括正常处理的和异常处理）；一个功能测试用例仅用于测试一个功能，一个功能可能需要多个功能测试用例来覆盖。场景测试应用背景：它是从用户对系统进行最终确认的角度来编写的，关注于不同场景、事务、业务流程等；跨功能；仅用到各个功能的一部分处理流程；一个场景测试用例仅测试一个场景、事务或业务流程。测试数据： 测试说明测试名称银行家算法通用演示程序测试目的验证银行家算法通用演示程序是否满足本次课程设计的要求测试技术单元测试测试方法黑盒测试测试用例测试内容银行家算法通用演示程序安全性检查测试步骤输入进程的资源请求检查系统的安全性测试数据课本案例预期结果能够随时的检查系统的安全性测试结果与预期相符课本数据分析：资源进程MaxAllocationNeedAvailableR1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3P07 5 30 1 0 7 4 33 3 2(2 3 0)P13 2 2 2 0 0 1 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 3 0 0 24 3 1T0时刻的存在的一个安全序列是P1，P3，P4,P2,P0当P1发出请求向量Request11,0,2，系统按银行家算法进行检查：Request11,0,2=Need11,2,2Request11,0,2=Available3,3,2先试分配资源并修改Available,Allocation1和Need1再利用安全性算法检查此时系统是否安全：资源进程WorkNeed AllocationWork+AllocationFinishR1 R2 R3R1 R2 R3 R1 R2 R3R1 R2 R3P13 3 21 2 2 2 0 05 3 2trueP35 3 20 1 1 2 1 17 4 3trueP47 4 34 3 10 1 07 4 5trueP27 4 56 0 03 0 210 4 7trueP010 4 77 4 30 1 010 5 7true存在一个安全序列：P1,P3,P4,P2,P0;可以将资源分配给P1此时P4发出资源请求Request43,3,0Request43,3,0=Available2,3,0 让P4等待其它测试用例：测试项目测试数据预期结果实际结果结论打开文件错误的例子.txt提示：读取文件错误，请检查提示：读取文件错误，请检查符合打开文件课本案例.txt打开文件成功，显示出读取文件中的信息打开文件成功，显示出读取文件中的信息符合修改资源空提示：请选择一个项目提示：请选择一个项目符合修改资源输入a提示：输入信息有误，请检查提示：输入信息有误，请检查符合修改资源输入8将资源数量修改成输入的数值将资源数量修改成输入的数值符合添加资源资源名称（aa）和资源数目（a）提示：输入信息有误，请检查提示：输入信息有误，请检查符合添加资源资源名称（aa）和资源数目（10）提示：添加成功！显示添加资源的名称和资源的数量提示：添加成功！显示添加资源的名称和资源的数量符合添加进程输入进程名称pp提示：添加进程成功！提示：添加进程成功！符合添加进程输入进程名称pp重复输入进程pp提示：添加进程失败！/n此进程已存在或进程名称有误！提示：添加进程失败！/n此进程已存在或进程名称有误！符合修改进程最大需求（aa）已分配（8）提示：输入信息有误，请检查！提示：输入信息有误，请检查！符合修改进程最大需求（4）已分配（4）显示出修改的进程的最大需求和已分配数量显示出修改的进程的最大需求和已分配数量符合3、调试分析：在设计本程序时，遇到的问题：(1). 问题：打开文件，当执行打开文件操作时，如何从文本文档载入数据，并将数据填充到主界面的ListView控件中。 解决：通过在文本设置两个数字m和n，分别代表资源数和进程数，通过for循环m和n次来实现对资源和进程的读取，通过创建ListViewItem的实例将数据填入主界面的ListView控件中。(2). 问题：计算安全序列时，如何判断系统资源满足进程的需要，如何实现查找所有的安全序列，以及代码优化。 解决：程序中定义了一个compare函数，用来比较系统资源和进程所需资源之间的关系。CheckSecurity函数用来判断系统中，是否有满足进程需要的资源，若无，则返回false，若有，则将满足需求的进程放到集合rq_able中，ExistSecurity函数实现了判断是否存在安全序列，并找出所有安全序列的功能，若程序中无安全序列，则返回false，有安全序列，则将所有安全序列信息保存到security_string字符串中。在此函数中用到类SystemInfo，该类用来保存当前系统的信息，包括满足需求的资源，当前系统可用资源，进程i是否满足，用finishi保存。集合resultClo中存放SystemInfo类的实例，为查找后续的查找安全序列用，这样做能做到优化代码的作用。(3). 问题：删除操作（添加操作雷同），当执行删除操作时，如何删除当前选定的资源，以及删除用到了本资源的进程中的资源。 解决： 因为本程序中的资源信息都是放在ArrayList集合中的，当选定一个资源时，通过选定的行数index，用RemoveAt()方法删除第index个的资源信息，然后依次删除每个进程的第index个资源。 (4). 问题：当一个进程满足所有资源分配后释放所有资源时，发现available中的数值没变。解决：在frmMain中加载进程loodProcess()信息时，进行判断，当进程的Max和Allocation相等时应删除此进程，同时要将其所分配的资源加入到available中。五、用户手册1、本程序是在Windows7操作系统下，用Visual Studio 2010 .NET平台开发平台下开发的软件。2、运行程序，将进入程序的主界面，弹出对话框，如下图所示：用户可以自己添加进程信息和资源信息，也可以通过打开已存在的文本来实现载入进程和资源信息，打开文件“课本案例”，程序加载后，运行结果如下打开资源信息对话框，如下图所示：点击添加资源按钮，弹出添加资源对话框，如下图所示：打开进程信息对话框，弹出对话框，如下图所示：打开检查中的安全序列，程序弹出显示出全部安全序列的对话框，如下图所示：打开请求资源对话框，程序如下图所示：六、程序清单系统中的关键算法有：CProcess类：public bool AddResource(int max, int alloc)/增加资源 if (max 0 | alloc 0 | max - alloc 0) return false; r_max.Add(max); r_allocation.Add(alloc); r_need.Add(max - alloc); return true; public bool EditResource(int index, int max, int alloc)/编辑资源信息 if (alloc 0 | index 0 | max - alloc 0) return false; r_maxindex = max; r_allocationindex = alloc; r_needindex = max - alloc; return true; public bool DelResource(int index)/删除进程中的该资源 if (index 0) return false; r_max.RemoveAt(index); r_allocation.RemoveAt(index); r_need.RemoveAt(index); return true; MainBanker类：public bool LoadFile(string filename)/读取文本内容 FileStream f1; f1 = System.IO.File.OpenRead(filename); if (f1 = null) return false; this.r_name.Clear(); this.r_available.Clear(); this.plist.Clear(); StreamReader sr = new StreamReader(f1); try /读取资源信息 string s1 = sr.ReadLine(); int count = Convert.ToInt32(sr.ReadLine();/该数为系统资源数目 for (int i = 0; i count; i+) string sa = new string2; string s = sr.ReadLine(); sa = s.Split( ); /以空格将读到的字符串分割 r_name.Add(sa0); /资源名称 r_available.Add(Convert.ToInt32(sa1);/资源数量 /读取进城信息 s1 = sr.ReadLine(); int pCount = Convert.ToInt32(sr.ReadLine();/该数为进城的数目 for (int i = 0; i pCount; i+) string sa = new string9; string s = sr.ReadLine(); sa = s.Split( ); CProcess p = new CProcess(sa0, 0); for (int j = 0; j 2 * count - 1; j = j + 2) int n1 = Convert.ToInt32(Convert.ToInt32(saj + 1);/进程所需最大资源数目 int n2 = Convert.ToInt32(Convert.ToInt32(saj + 2);/进程已分配资源数目 p.AddResource(n1, n2); plist.Add(p);/将进程添加到进程列表中 catch (Exception) MessageBox.Show(读取文件数据错误，请检查文件信息！ , 提示信息, MessageBoxButtons.OK, MessageBoxIcon.Information); sr.Close(); f1.Close(); return true; public bool CheckRequest(bool IsExist)/检查请求资源 bool ret; current = new SystemInfo(this.plist.Count, this.r_name.Count); current.rq_pcount = -1; current.work = (ArrayList)r_available.Clone(); CProcess p = (CProcess)plistthis.pIndex;/进程p为当前选择的进程pIndex /若请求资源大于系统资源，或者请求资源大于需求数量，返回false if (!compare(this.rq, current.work) | !compare(this.rq, p.r_need) return false; if (!IsExist)/假设不存在安全序列时用于保存现场 this.p_bak = (ArrayList)this.plist.Clone();/进程副本 for (int i = 0; i plist.Count; i+) CProcess tmp = new CProcess(, 1); tmp.CopyFrom(CProcess)plisti); this.p_baki = tmp; this.r_bak = (ArrayList)this.r_available.Clone(); Add(p.r_allocation, this.rq);/进程pIndex已获得的资源 Sub(p.r_need, this.rq);/进程pIndex还需要的资源 Sub(this.r_available, this.rq);/系统当前资源/初始化系统可分配资源 current.work = (ArrayList)r_available.Clone(); for (int i = 0; i plist.Count; i+)/查找满足需求的进程 p = (CProcess)plisti; if (compare(p.r_need, current.work) current.rq_pcount+; current.rq_ablecurrent.rq_pcount = i; if (current.rq_pcount = -1)