操作系统课程设计：银行家算法算法的模拟实现.doc

枣 庄 学 院信息科学与工程学院课程设计任务书 题目： 银行家算法算法的模拟实现 学 生1： 学 生2： 专 业： 计算机应用技术 课 程： 操作系统 指导教师： 职称： 完成时间： 2014年 12月-2015 年 1月枣庄学院信息科学与工程学院制2014年12月10日课程设计任务书及成绩评定课程设计的任务和具体要求操作系统课程设计是操作系统课程学习的延续。主要目的是配合操作系统课程的学习，对Linux操作系统有一定掌握，能够熟练操作，并能在Linux系统下模拟实现操作系统的功能，有助于对操作系统的理解。本次课程设计共分两部分，其中第一部分为操作题，同学们需要对Linux的基本的命令（常用的几个，讲课的时候强调的），这部分，任课教师实时检查，让学生用命令完成一定的功能，然后，根据完成情况评定成绩。第二部分为编程设计题，每组同学必须独立完成，可以选择进程调度，也可以根据自己的兴趣，选择模拟实现磁盘调度、银行家算法、页面置换算法等。指导教师签字： 日期： 指导教师评语成绩： 指导教师签字： 日期： 课程设计所需软件、硬件等系统：Windows XP上的虚拟机上运行的Centos语言：C语言课程设计进度计划起至日期工作内容备注12：1112：11课程设计选题选题12：21：12：25机房调试12：25打印参考文献、资料索引序号文献、资料名称编著者出版单位1 鞠文飞 Linux操作系统实用教程科学出版社，20122 陈向群/ 陈渝操作系统精髓与设计原理机械工业出版社， 20103 汤子瀛计算机操作系统(修订版)西安电子科技大学出版社, 2012 4吕雪峰嵌入式Linux软件开发从入门到精通清华大学出版社, 2014目 录1 引言 1.1 linux及其特点 .4 1.1.1 Linux的概述 4 1.2 Linux的结构 .41.3 Linux的版本 .52常用命令基本介绍 2.1 Linux目录命令 .52.2 Linux文件命令 .53 银行家算法 3.1 实验目的 .63.2 实验内容 .63.3 实验方法 .73.3.1 算法流程图 .73.3.2 算法数据结构 .73.4 实验代码 .83.5 运行示例 .174 实验小结.17摘要在计算机网络高速发展的今天，计算机技术不断地更新与完善，无论是硬件还是软件的变更都会在计算机操作系统的设计技术与使用风格上得到体现操作系统是计算机系统配置的所有软件中使用最广泛的基础软件，它在整个计算机系统软件中处于中心地位，也是计算机专业课教学中做重要的环节之一。从操作系统自身角度讲，它不仅很好地体现了计算机日益发展中的软件研究成果，而且也较好地体现了计算机的硬件技术发展及计算机系统结构的用户界面环境。本实验主要根据是按动态优先数设计五个进程的调度算法。即在它们调度的过程中，其优先数是不断变化的。引言1.1 Linux及其特点1.11Linux的概述 Linux是一种免费的、开放源代码的、交互式、多用户和多任务的、类Unix的网络操作系统一，它包括系统内核、系统工具、应用程序以及一个完整的的开发环境。实际上，准确点说，Linux指的是：一个类似UNIX的开放的操作系统内核。1.1.2Linux的特点（1）自由和开放性（2）类UNIX （3）交互性强 （4）多用户和多任务 （5）出色的速度性能 （6）丰富的网络功能 （7）可靠的系统安全 （8）良好的可移植性 （9）具有标准兼容性 1.2 linux的结构内核：Linux操作系统的主要部分，是运行程序和管理像磁盘和打印机等硬件设备的核心程序 Shell:是系统的用户界面，提供了用户与内核进行交互操作的一种接口 ,实际上Shell是一个命令解释器，它解释由用户输入的命令并且把它们送到内核 .而且，Shell有自己的编程语言用于对命令的编辑。当然也提供图形界面实用程序：的Linux标准系统都有一套称为应用程序的程序集，它们是专门的程序，包括文本编辑器，编程语言，X Window，办公套件，Internet工具，数据库等 1.3 Linux的版本：内核版本：根据约定，次版本号为奇数时，表示该版本加入新内容，但不一定很稳定，相当于测试版；次版本号为偶数时，表示这是一个可以使用的稳定版本。由于Linux内核开发工作的连续性,因此内核的稳定版本与在此基础上进一步开发的不稳定版本总是同时存在的。对于一般用户，建议采用稳定的内核版本发行版本：（1）Slackware Linux  （2）Red Hat Linux  （3）Turbo Linux （4）Debian Linux （5）红旗Linux 2 常用基本命的基本介绍：2.1 Linux目录命令1.pwd -显示当前工作目录的绝对路径格式: pwd 2. cd -改变当前工作目录命令格式：cd 目录名 3Ls- 列出文件目录的信息命令格式：ls 可选项 子目录名 文件名4mkdir - 建立目录命令格式：mkdir 可选项 目录名 5rmdir -删除目录本命令用于删除指定的一个或多个目录，必须保证要删除的目录中没有任何文件。命令格式：rmdir 可选项 目录名 2.2 linux 文件命令1. ls l 文件名2. chmod -改变文件或目录的访问权限 命令格式：chmod 可选项 权限 目录或文件名 3chgrp命令 -改变文件或目录所属的组。 命令格式：chgrp 选项 group filename选项： -R：递归式地改变指定目录及其下的所 有子目录和文件的属组 4. chown -更改某个文件或目录的属主和属组 命令格式：chown 选项 文件或目录的新属主.文件或目录所在的新组 文件名|目录 5. cat -显示，新建，连接文件6. cp -功能：文件或目录的拷贝 ，如同dos的copy 命令格式： cp 选项 源文件或目录 目标文件或目录 7. mv -功能：为文件或目录改名或将文件由一个目录移入另一 个目录中 命令格式： mv 选项 源文件或目录 目标文件或目录 8. rm -功能：删除一个目录中的一个或多个文件或目录，它也可以将某个目录及其下的所有文件及子目录均删除 命令格式： rm 选项 文件 3 银行家算法3.1 实验目的银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法。3.2 实验内容根据银行家算法的基本思想，编写和调试一个实现动态资源分配的模拟程序，并能够有效地防止和避免死锁的发生。3.3 实验方法开 始输入资源数m, 及各类资源总数，初始化Available向量输入进程数n，i=1输入进程i的最大需求向量max。inmax资源总数提示错误重新输入i加1任选一个进程作为当前进程输入该进程的资源请求量Request 调用银行家算法，及安全性算法，完成分配，或并给出提示Need向量为0该进程已运行结束Need矩阵为0所有进程运行都结束结 束NYYNNY初始化need 矩阵NY3.3.1算法流程图3.3.2算法数据结构1) 可利用资源向量Available ，它是一个最多含有100个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available（j）=k，标是系统中现有j类资源k个。2) 最大需求矩阵Max，这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max（i，j）=k，表示进程i需要j类资源的最大数目为k。3) 分配矩阵Allocation，这也是一个n×m的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation（i，j）=k，表示进程i当前已经分到j类资源的数目为k。Allocation i表示进程i的分配向量，有矩阵Allocation的第i行构成。4) 需求矩阵Need，这还是一个n×m的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need（i，j）=k，表示进程i还需要j类资源k个，才能完成其任务。Need i表示进程i的需求向量，由矩阵Need的第i行构成。5) 上述三个矩阵间存在关系：Need（i，j）=Max（i，j）-Allocation（i，j）；1. 银行家算法设Requesti 是进程i的请求向量，如果Requesti，j=K,表示进程i需要K个j类型的资源。当i发出资源请求后，系统按下述步骤进行检查：1) 如果Request i Need，则转向步骤2；否则，认为出错，因为它所请求的资源数已超过它当前的最大需求量。2) 如果Request i Available，则转向步骤3；否则，表示系统中尚无足够的资源满足i的申请，i必须等待。3) 系统试探性地把资源分配给进程i，并修改下面数据结构中的数值：Available = Available - Request iAllocation i= Allocation i+ Request iNeed i= Need i - Request i4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程i，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程i等待。3.4实验代码源代码：#include<iostream>#include<string.h>#include<stdio.h>#define False 0#define True 1using namespace std;int Max100100=0;/各进程所需各类资源的最大需求int Avaliable100=0;/系统可用资源char name100=0;/资源的名称int Allocation100100=0;/系统已分配资源int Need100100=0;/还需要资源int Request100=0;/请求资源向量int temp100=0;/存放安全序列int Work100=0;/存放系统可提供资源int M=100;/进程的最大数为int N=100;/资源的最大数为void showdata()/显示资源矩阵int i,j;cout<<"系统目前可用的资源Avaliable:"<<endl;for(i=0;i<N;i+) cout<<namei<<" "cout<<endl;for (j=0;j<N;j+) cout<<Avaliablej<<" "/输出分配资源cout<<endl;cout<<" Max Allocation Need"<<endl;cout<<"进程名 "for(j=0;j<3;j+)for(i=0;i<N;i+)cout<<namei<<" "cout<<" "cout<<endl;for(i=0;i<M;i+)cout<<" "<<i<<" "for(j=0;j<N;j+)cout<<Maxij<<" "cout<<" "for(j=0;j<N;j+)cout<<Allocationij<<" "cout<<" "for(j=0;j<N;j+)cout<<Needij<<" "cout<<endl;int changdata(int i)/进行资源分配 int j;for (j=0;j<M;j+) Avaliablej=Avaliablej-Requestj;Allocationij=Allocationij+Requestj;Needij=Needij-Requestj;return 1;int safe()/安全性算法int i,k=0,m,apply,Finish100=0;int j;int flag=0;Work0=Avaliable0;Work1=Avaliable1;Work2=Avaliable2;for(i=0;i<M;i+) apply=0;for(j=0;j<N;j+)if (Finishi=False&&Needij<=Workj) apply+;if(apply=N)for(m=0;m<N;m+)Workm=Workm+Allocationim;/变分配数Finishi=True;tempk=i;i=-1; k+;flag+;for(i=0;i<M;i+)if(Finishi=False)cout<<"系统不安全"<<endl;/不成功系统不安全return -1; cout<<"系统是安全的!"<<endl;/如果安全，输出成功 cout<<"分配的序列:"for(i=0;i<M;i+)/输出运行进程数组cout<<tempi;if(i<M-1) cout<<"->"cout<<endl;return 0;void share()/利用银行家算法对申请资源对进行判定char ch;int i=0,j=0;ch='y'cout<<"请输入要求分配的资源进程号(0-"<<M-1<<"):" cin>>i;/输入须申请的资源号cout<<"请输入进程"<<i<<" 申请的资源:"<<endl;for(j=0;j<N;j+)cout<<namej<<":"cin>>Requestj;/输入需要申请的资源 for (j=0;j<N;j+)if(Requestj>Needij)/判断申请是否大于需求，若大于则出错 cout<<"进程"<<i<<"申请的资源大于它需要的资源"cout<<" 分配不合理，不予分配！"<<endl;ch='n'break;else if(Requestj>Avaliablej)/判断申请是否大于当前资源，若大于则 /出错cout<<"进程"<<i<<"申请的资源大于系统现在可利用的资源"cout<<" 分配出错，不予分配!"<<endl;ch='n'break; if(ch='y') changdata(i);/根据进程需求量变换资源showdata();/根据进程需求量显示变换后的资源safe();/根据进程需求量进行银行家算法判断 void addresources()/添加资源 int n,flag;cout<<"请输入需要添加资源种类的数量:"cin>>n;flag=N;N=N+n;for(int i=0;i<n;i+)cout<<"名称:"cin>>nameflag;cout<<"数量:"cin>>Avaliableflag+;showdata();safe();void delresources()/删除资源char ming;int i,flag=1;cout<<"请输入需要删除的资源名称："docin>>ming;for(i=0;i<N;i+)if(ming=namei)flag=0;break;if(i=N)cout<<"该资源名称不存在，请重新输入："while(flag);for(int j=i;j<N-1;j+)namej=namej+1;Avaliablej=Avaliablej+1;N=N-1;showdata();safe();void changeresources()/修改资源函数cout<<"系统目前可用的资源Avaliable:"<<endl; for(int i=0;i<N;i+) cout<<namei<<":"<<Avaliablei<<endl;cout<<"输入系统可用资源Avaliable:"<<endl;cin>>Avaliable0>>Avaliable1>>Avaliable2;cout<<"经修改后的系统可用资源为"<<endl;for (int k=0;k<N;k+)cout<<namek<<":"<<Avaliablek<<endl;showdata();safe();void addprocess()/添加作业 int flag=M;M=M+1;cout<<"请输入该作业的最大需求量Max"<<endl;for(int i=0;i<N;i+)cout<<namei<<":"cin>>Maxflagi;Needflagi=Maxflagi-Allocationflagi;showdata();safe();int main()/主函数 int i,j,number,choice,m,n,flag; char ming;cout<<"t-"<<endl;cout<<"t| |"<<endl;cout<<"t| 银行家算法的实现 |"<<endl;cout<<"t| |"<<endl;cout<<"t| |"<<endl;cout<<"t| |"<<endl;cout<<"t| |"<<endl;cout<<"t-"<<endl;cout<<"请首先输入系统可供资源种类的数量:"cin>>n;N=n;for(i=0;i<n;i+)cout<<"资源"<<i+1<<"的名称:"cin>>ming;namei=ming;cout<<"资源的数量:"cin>>number;Avaliablei=number;cout<<endl;cout<<"请输入作业的数量:"cin>>m;M=m;cout<<"请输入各进程的最大需求量("<<m<<"*"<<n<<"矩阵)Max:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Maxij;doflag=0;cout<<"请输入各进程已经申请的资源量("<<m<<"*"<<n<<"矩阵)Allocation:"<<endl;for(i=0;i<m;i+)for(j=0;j<n;j+)cin>>Allocationij;if(Allocationij>Maxij) flag=1;Needij=Maxij-Allocationij;if(flag)cout<<"申请的资源大于最大需求量，请重新输入!n"while(flag); showdata();/显示各种资源 safe();/用银行家算法判定系统是否安全 while(choice)cout<<"t-银行家算法演示-"<<endl;cout<<" 1:增加资源 "<<endl;cout<<" 2:删除资源 "<<endl;cout<<" 3:修改资源 "<<endl;cout<<" 4:分配资源 "<<endl;cout<<" 5:增加作业 "<<endl;cout<<" 0:离开 "<<endl;cout<<"t-"<<endl;cout<<"请选择功能号："cin>>choice;switch(choice)case 1: addresources();break;case 2: delresources();break;case 3: changeresources();break;case 4: share();break;case 5: addprocess();break;case 0: choice=0;break;default: cout<<"请正确选择功能号(0-5)!"<<endl;break; return 1;3.5 运行结果：1) 初始化状态：2) 为进程0分配资源：3) 为进程4分配资源：五、实验总结本程序的设计实现主要是用C+语言。程序设计过程中开始遇到的最大的问题是算法的结构设计问题，课本上只给了设计要求及简单的算法，要真正实现还需要考虑很多方面。在程序设计中先后参考了很多网络资料，也参考了一些别人写的的程序，让我彻底认识到自己的不足，也同时从中学到了更多。在这次项目测试中，我也从中得到了许许多多的求知、为人处世的道理第一，团结就是力量，我们应该在今后的学习中更加团结，更加努力；第二，要有一颗相互理解的心。在今后无论是学习还是生活中，与同学朋友相处应该要懂得相互理解，理解万岁；第三，做事要细心，不可马虎，在以后的处事方面，应该要保持小心，谨慎的态度，特别是我们做建筑的，我们的处事态度关系到许多人的生命安全，万万不可马虎；第四，学无止境，人无完人。经过这次的实习让我更加明白学无止境的道理，在今后的学习上，要活到老学到老的精神；第五，温故而知新。孔子曾在几千多年就说过：“温故而知新，可以为师矣。”，所以我们在以后的学习上要时常复习，相信会在其中得到更多的知识；第六，人各有所长。每个人都有自己的长处，我们应该多虚心学习他人的长处，不断完善自己。第七，学会了吃苦耐劳，学会了艰苦奋斗的作风。这次实习中得到的这些求知、为人处世方面的道理，将伴随我整个学生活，甚至一生，它们将是我人生道路上的一笔极其宝贵的财富，我一定会好好珍惜和利用它们。相信它们对我今后的学习将会有很大的帮助，也相信一切的一切，明天会更好。在这次的测试过程中，还有一群和我们一起努力，一起吃苦的人，他们都是最可爱的人我们的指导老师。在实训过程中，老师不辞辛苦给我们指导，为我们测试做出很大努力，给我们提供很多帮助和指导，在这里也真心地向老师们说声：老师，您辛苦了！谢谢您多日来的指导。