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

1、枣庄学院信息科学与工程学院课程设计任务书题目银行家算法算法的模拟实现学 生1: 学 生2: 专 业：计算机应用技术课 程：操作系统指导教师： 职称： 完成时间： 2014年12月-2015年1月枣庄学院信息科学与工程学院制2014年12月10日课程设计任务书及成绩评定课程设计的任务和具体要求操作系统课程设计是操作系统课程学习的延续。主要目的是配合操作系统课程的学习， 对Linux操作系统有一定掌握， 能够熟练操作，并能在Linux系统下模拟实现操作系统的功 能，有助于对操作系统的理解。本次课程设计共分两部分，其中第一部分为操作题，同学们需要对Linux的基本的命令 （常用的几个，讲课的时候强调

2、的），这部分，任课教师实时检查，让学生用命令完成一定 的功能，然后，根据完成情况评定成绩。第二部分为编程设计题，每组同学必须独立完成， 可以选择进程调度，也可以根据自己的兴趣，选择模拟实现磁盘调度、银行家算法、页面 置换算法等。指导教师签字： 日期： 指导教师评语成绩： 指导教师签字： 日期： 课程设计所需软件、硬件等系统：Windows XP上的虚拟机上运行的 Centos语言：C语言课程设计进度计划起至日期工作内容备注12： 11 12： 11课程设计选题选题12： 21：12： 25机房调试12： 25打印参考文献、资料索引序号文献、资料名称编著者出版单位1 鞠文飞.Linux操作系统实

3、用教程.科学出版社，20122 陈向群/陈渝.操作系统精髓与设计原理.机械工业出版社，20103 汤子瀛计算机操作系统 （修订版）西安电子科技大学出版社 ，20124 吕雪峰嵌入式 Linux软件开发从入门到精通清华大学出版社，2014目录1引言1.1 linux 及其特点 41.1.1 Linux 的概述 41.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实验代码 3.5运行示例

4、 174实验小结 .1720摘要在计算机网络高速发展的今天，计算机技术不断地更新与完善，无论是硬 件还是软件的变更都会在计算机操作系统的设计技术与使用风格上得到体现操作系统是计算机系统配置的所有软件中使用最广泛的基础软件，它在整 个计算机系统软件中处于中心地位，也是计算机专业课教学中做重要的环节之 一。从操作系统自身角度讲，它不仅很好地体现了计算机日益发展中的软件研 究成果，而且也较好地体现了计算机的硬件技术发展及计算机系统结构的用户 界面环境。本实验主要根据是按动态优先数设计五个进程的调度算法。即在它 们调度的过程中，其优先数是不断变化的。引言1.1 Linux及其特点1.11Linux的概

5、述Linux是一种免费的、开放源代码的、交互式、多用户和多任务的、类Unix的网络操作系统一，它包括系统内核、系统工具、应用程序以及一个完整的的开 发环境。实际上，准确点说，Linux指的是：一个类似UNIX的开放的操作系统内核。1.1.2Li nux 的特点（1）自由和开放性（2）类 UNIX（3）交互性强（4）多用户和多任务（5）出色的速度性能（6）丰富的网络功能（7）可靠的系统安全（8）良好的可移植性（9）具有标准兼容性1.2 lin ux 的结构内核：Linux操作系统的主要部分，是运行程序和管理像磁盘和打印机等硬件 设备的核心程序Shell:是系统的用户界面，提供了用户与内核进行交互

6、操作的一种接口，实际上Shell是一个命令解释器，它解释由用户输入的命令并且把它们送到内核.而 且，Shell有自己的编程语言用于对命令的编辑。当然也提供图形界面实用程序：的Linux标准系统都有一套称为应用程序的程序集，它们是专门的程序，包括 文本编辑器，编程语言，X Win dow,办公套件，In ternet工具，数据库等1.3 Lin ux 的版本：内核版本：根据约定，次版本号为奇数时，表示该版本加入新内容，但不一定很稳定，相 当于测试版；次版本号为偶数时，表示这是一个可以使用的稳定版本。由于 Linux内核开发工作的连续性，因此内核的稳定版本与在此基础上进一步开发 的不稳定版本总是同

7、时存在的。对于一般用户，建议采用稳定的内核版本 发行版本：（1）Slackware Linux（ 2） RedHat Linux（ 3）Turbo Linux（4）Debian Linux（ 5）红旗 Linux2常用基本命的基本介绍：2.1 Lin ux 目录命令1. pwd -显示当前工作目录的绝对路径格式：pwd2. cd -改变当前工作目录命令格式：cd 目录名3. Ls-列出文件目录的信息命令格式：Is 可选项子目录名文件名4. mkdir -建立目录命令格式：mkdir 可选项目录名5. rmdir - 删除目录本命令用于删除指定的一个或多个目录，必须保证要删除的目录中没有任何文

8、件。命令格式：rmdir 可选项目录名2.2 linux文件命令1. ls -1文件名2. chmod -改变文件或目录的访问权限命令格式：chmod 可选项权限目录或文件名3. chgrp命令-改变文件或目录所属的组。命令格式： chgrp 选项group file name选项：-R :递归式地改变指定目录及其下的所有子目录和文件的属组4. chown - 更改某个文件或目录的属主和属组命令格式：chown 选项文件或目录的新属主.文件或目录所在的新组文 件名|目录5. cat -显示，新建，连接文件6. cp - 功能：文件或目录的拷贝 ，如同dos的copy命令格式：cp 选项源文件或

9、目录 目标文件或目录7. mv -功能：为文件或目录改名或将文件由一个目录移入另一个目录中命令格式：mv 选项源文件或目录 目标文件或目录8. rm - 功能：删除一个目录中的一个或多个文件或目录，它也可以将某个 目录及其下的所有文件及子目录均删除命令格式：rm 选项文件 3银行家算法3.1实验目的银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配 的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等 重要概念，并掌握避免死锁的具体实施方法。3.2实验内容根据银行家算法的基本思想，编写和调试一个实现动态资源分配的模拟程 序，并能够有效地防止和避免死锁的发生。3.3

10、实验方法3.3.1算法流程图3.3.2算法数据结构1）可利用资源向量Available，它是一个最多含有100个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的 该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。 如果Available（j）=k，标是系统中现有j类资源k个。2）最大需求矩阵Max这是一个nxm的矩阵，它定义了系统中n个进程中的 每一个进程对m类资源的最大需求。如果 Max（i，j ） =k，表示进程i需要 i类资源的最大数目为k。3) 分配矩阵Allocation ,这也是一个nXm的矩阵，它定义了系统中的每类资源当前一分配到每一

11、个进程的资源数。如果Allocation(i , j ) =k，表示进程i当前已经分到j类资源的数目为k。Allocationi表示进程i的分配向量，有矩阵Allocation 的第i行构成。4) 需求矩阵Need这还是一个nXm的矩阵，用以表示每个进程还需要的各类 资源的数目。如果Need (i , j ) =k,表示进程i还需要j类资源k个，才 能完成其任务。Needi表示进程i的需求向量，由矩阵Need的第i行构成。5) 上述三个矩阵间存在关系：Need( i , j ) =Max(i , j ) -Allocation(i , j)；1.银行家算法设Requesti 是进程i的请求向量

12、，如果 Requesti , j=K,表示进程i 需要K个j类型的资源。当i发出资源请求后，系统按下述步骤进行检查：1) 如果Request i Need,则转向步骤2；否则，认为出错，因为它所请求的 资源数已超过它当前的最大需求量。2) 如果Request i Available，则转向步骤3;否则，表示系统中尚无足够 的资源满足i的申请，i必须等待。3) 系统试探性地把资源分配给进程i，并修改下面数据结构中的数值：Available = Available - Request iAllocationi = Allocation i+ Request iNeed i = Need i - R

13、equest i4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如 果安全才正式将资源分配给进程i，以完成本次分配；否则，将试探分配作 废，恢复原来的资源分配状态，让进程i等待。3.4实验代码源代码：#include #include #include #define False 0#define True 1using namespacestd;int Max100100=0;/各进程所需各类资源的最大需求int Avaliable100=0;/ 系统可用资源char name100=0; / 资源的名称int Allocation100100=0;/ 系统已分配资源in

14、t 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;iN;i+)coutnamei;coute ndl;for (j=0;jN;j+)coutAvaliablej ;/ 输出分配资源 coute ndl;e ndl;coutMaxAllocati onNeedc

15、outvv进程名 ;for (j=0;j3;j+)for (i=0;iN;i+)coutnamei ; cout; coute ndl;for (i=0;iM;i+)cout i;for (j=0;jN;j+)coutMaxijvv;cout;for (j=0;jN;j+)coutAllocationij;cout;for (j=0;jN;j+) coutNeedij ; coute ndl;int changdata( int i) / 进行资源分配int j;for (j=0;jM;j+) Avaliablej=Avaliablej-Requestj;Allocatio n ij=Allo

16、catio nij+Requestj; Needij=Needij-Requestj;return 1;int safe() /安全性算法int i,k=0,m,apply,Finish100=0;int i;int flag=O;Work0=Avaliable0;Work1=Avaliable1;Work2=Avaliable2;for (i=0;iM;i+)apply=0;for (j=0;jN;j+)if (Finishi=False&Needij=Workj) apply+;if (apply=N)for (m=0;mN;m+)Workm=Workm+Allocationim;/ 变分

17、配数Fini shi=True; tempk=i; i=-1; k+; flag+;for (i=0;iM;i+)if (Finishi=False) coutvv系统不安全endl; /不成功系统不安全 return -1;cout 系统是安全的! endl; /如果安全，输出成功 cout分配的序列：;for (i=0;iM;i+)/输出运行进程数组couttempi;if (iM-1) cout;coute ndl;return 0;void share() /利用银行家算法对申请资源对进行判定char ch;int i=0,j=0;ch=y;coutvv请输入要求分配的资源进程号(0-

18、 M-1):;cini;/输入须申请的资源号coutvv请输入进程vvivv 申请的资源:endl;for (j=O；jN;j+)coutvnamejRequestj; /输入需要申请的资源for (j=O;jNeedij) /判断申请是否大于需求，若大于则出错 coutvv进程vvivv申请的资源大于它需要的资源; coutvv分配不合理，不予分配！ Avaliablej) /判断申请是否大于当前资源，若 大于则/出错coutvv进程vvivv申请的资源大于系统现在可利用的资源;coutvv分配出错，不予分配! vvendl;ch=n;break;if (ch=y ) changdata(i

19、); /根据进程需求量变换资源showdata(); /根据进程需求量显示变换后的资源 safe(); /根据进程需求量进行银行家算法判断void addresources() / 添加资源int n,flag;coutvv请输入需要添加资源种类的数量：；cinn;flag=N;N=N+n;for (int i=0;ivn;i+)coutvv名称:;cinn ameflag;coutvv数量:;cin Avaliableflag+;showdata();safe();void delresources() / 删除资源 char ming;int i,flag=1; coutvv请输入需要删除

20、的资源名称：;docinming;for (i=0;iN;i+)if (ming=namei) flag=0; break;if (i=N) coutvv该资源名称不存在，请重新输入：;while (flag);for (int j=i；jN-1;j+)n amej=n amej+1; Avaliablej=Avaliablej+1; N=N-1; showdata(); safe();void changeresources() / 修改资源函数 coutvv系统目前可用的资源Avaliable:endl;for (int i=0;iN;i+)coutnamei: vAvaliableive

21、ndl;coutvv 输入系统可用资源Avaliable:Avaliable0Avaliable1Avaliable2; coutvv经修改后的系统可用资源为vvendl; for ( int k=0;kvN;k+)coutvvnamekvv : vvAvaliablekvvendl; showdata();safe();void addprocess() / 添加作业int flag=M;M=M+1;coutvv请输入该作业的最大需求量Max vvendl; for (int i=0;ivN;i+)coutvvnameivv :;cin Maxflagi;Needflagi=Maxflagi

22、-Allocatio nflagi; showdata(); safe();int main() / 主函数int i,j,number,choice,m,n,flag; char ming;cout tndl;coutt| endl;coutvv t|银行家算法的实现II endl;cout t| endl;cout t| endl;cout t| endl; cout t| n;N=n;for (i=0;im;M=m;coutvv请输入各进程的最大需求量(vvmvv* vv*v，矩 阵)Max: vvendl;vvevvefor (i=0;ivm;i+)for (j=0;jn;j+)ci

23、nMaxij;doflag=0;cout请输入各进程已经申请的资源量(m* *矩 阵)Allocatio n:e ndl;for (i=0;im;i+)for (j=0;j Allocatio nij;if (AllocationijMaxij) flag=1; Needij=Maxij-Allocatio nij;if (flag) coutvv申请的资源大于最大需求量，请重新输入!n;while (flag);showdata(); /显示各种资源safe(); /用银行家算法判定系统是否安全while (choice)cout t-IIe ndl;银仃豕算法演示cout1:增加资源e n

24、dl;cout2:删除资源e ndl;cout3:修改资源e ndl;cout4:分配资源e ndl;cout5:增加作业e ndl;cout0:离开e ndl;ecout tndl;cout choice;switch (choice)case 1: addresources();break;case 2: delresources();break;case 3: cha ngeresources();break;case 4: share(); break;case 5: addprocess(); break;case 0: choice=0; break;default : cout

25、请正确选择功能号(0-5)! filloCationJ：11S 累统目前叮用的资源EfiualiableJzB C5700212A lluca ABC I 1毎1I毎Max fi B C 1 5 32 2珏22 23 3进程名&123:统是安全的？分配的序?I：0-1-2-3-4S0212Need fi B C 1 42野1332S11m C:Wi ndow 5syst e m 3 2cm d. ex e银行家算法的实现需求量z矩阵ms请输入各进程已经申请的资源量估旧矩阵Ifi I loc ationJ： ! 1 00 U:9 21 10 2系统目前可用的资源CHustliablel?.0 C

26、0 S 7进程名012A c? 5 23 2 29 & 22 2 24 3 2ABC1 S0 00 21 10 2Need 口 R C 7 4 3 12 2 6 0 0 ait 4 3 1系统星安全的甲分配的序列：0-1-2-3-4 半三2）为进程0分配资源:C:Wi n dowssyste m 3 2cmd. exe请选择功能号：4幘藏入墨衣存配的茨源进程号：0请1A程0申请的资源：7：4分配岀错，不予分配?易為申请的资源大于系统现在可利用的资为进程4分配资源:iJ程名I4 3 3Max ABC 7 5 3ftlluctit iun ABC请谨摄功毎号i 4请求分配的系源讲#： tWAji 4申请笊资痹r.：43 24 4 陈瓠是爰全的FKi酉己的声列：2-3-1 - M-0Need A