操作系统课程设计-银行家算法

1、课 程 设 计 报 告课程名称 操作系统 课题名称 银行家算法 专 业 班 级 学 号 姓 名 指导教师 2013年7 月 5 日湖南工程学院课 程 设 计 任 务 书课程名称 操作系统 课 题 银行家算法 专业班级 学生姓名 学 号 指导老师 审 批 任务书下达日期 2013 年 6 月 24 日任务完成日期 2013年 7 月5日一、设计内容与设计要求1设计内容：课题1：银行家算法 编制银行家算法通用程序，并检测所给状态的系统安全性。假设有n个进程m类资源，则有如下数据结构：(1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初

2、始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Availablej=K，则表示系统中现有Rj 类资源K个。(2) 最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi，j=K，则表示进程i需要Rj类资源的最大数目为K。(3) 分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi，j=K，则表示进程i当前已分得Rj类资源的数目为K。(4) 需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。

3、如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵存在如下关系：Needi,j= Maxi，j- Allocationi，j。设进程I提出请求RequestN，则银行家算法按如下规则进行判断：(1)如果RequestN=NEEDI，N，则转(2)；否则，出错。 (2)如果RequestN=AVAILABLE，则转(3)；否则，出错。 (3)系统试探分配资源，修改相关数据： AVAILABLE=AVAILABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUEST (4)系统执行安全性检查，如安全，则

4、分配成立；否则试探险性分配作废，系统恢复原状，进程等待。课题2：模拟操作系统中进程调度过程。要求设计一个程序，该程序可模拟对10个以上的进程进行FCFS、SJF、HRP的方式进行调度。( 1) 设计进程控制块PCB，进程控制块至少包括进程号、到达时间和要求服务时间； (2) 动态或静态创建多个(10)进程；(3) 实现FCFS、SJF、HRP调度算法；(4) 调度所创建的进程并显示调度结果。课题3：模拟短进程优先（SJF）调度要求：(1) 每一个进程有一个PCB，PCB的内容可以根据具体情况设定；(2) 可以由用户界面设定互斥资源（包括两种：输入设备和输出设备）的数目；(3) 进程数、进入内存

5、的时间和要求服务时间可以由用户界面设定，程序应检查其合理性；(4) 进程之间存在一定的同步与互斥关系，可以通过界面进行设定，其表示方法如下：进程的服务时间由四段组成：I2C10O5C5（表示进程的服务时间由2个时间片的输入，10个时间片的计算，5个时间片的输出，5个时间片的计算组成）；进程间的同步关系用一个段表示：W2，表示该进程先要等待P2进程执行结束后才可以运行，因此，进程间的同步与互斥关系、服务时间可以统一用五段表示为：I2C10O5C5W2；(5) 可以在运行中显示各进程的状态：就绪、阻塞、执行；(6）采用可视化界面，可以在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队

6、列；(7) 具有一定的数据容错性；(8) 模拟6个以上短进程优先调度的程序。界面用VC中的MFC框架结构写。课题4：利用多线程模拟实现生产者/消费者问题。生产者/消费者问题是一个多线程同步问题的经典案例。该问题描述了两个共享固定大小缓冲区的线程即所谓的“生产者”和“消费者”在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。要解决该问题，就必须让生产者在缓冲区满时休眠，等到下次消费者消耗缓冲区中的数据的时候，生产者才能被唤醒，开

7、始往缓冲区添加数据。同样，也可以让消费者在缓冲区空时进入休眠，等到生产者往缓冲区添加数据之后，再唤醒消费者。通常采用进程间通信的方法解决该问题，如采用信号量方法。如果解决方法不够完善，则容易出现死锁的情况。出现死锁时，两个线程都会陷入休眠，等待对方唤醒自己。课题5：模拟实现读者写者问题读者写者问题是一个经典的并发程序设计问题，是经常出现的一种同步问题。所谓读者写者问题，是指保证一个writer进程必须与其他进程互斥地访问共享对象的同步问题。读者写者问题可以这样的描述，有一群写者和一群读者，写者在写同一本书，读者也在读这本书，多个读者可以同时读这本书，但是，只能有一个写者在写书，并且，读者比写者

8、优先，也就是说，读者和写者同时提出请求时，读者优先。当读者提出请求时需要有一个互斥操作，另外，需要有一个信号量S来当前是否可操作。课题6：分析LINUX内核中进程调度部分源代码从LINUX官网/上载LINUX源代码，将其解压后，分析其中includelinux sched.h 和kernel/sched/core.c及相关源文件，了解其进程控制块结构，分析LINUX进程调度策略及过程。课题7：分析LINUX中信号量实现部分源代码从LINUX官网/上载LINUX源代码，将其解压后，分析其中includelinux

9、semaphore.h和 kernel/sched/ semaphore.c及相关源文件，分析LINUX中信号量的定义及其相应操作的实现。2 选题方案：所选题目根据学号确定，学号模7加1，即（学号%7+1）。如你的学号为9，则所选题目号为：9%7+1（题目3）。3设计要求：3.1 课程设计报告规范（1）需求分析a.程序的功能。b.输入输出的要求。（2）概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。（3）详细设计a.采用C语言定义相关的数据类型。b 写出各

10、模块的类C码算法。c.画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。（6）书写格式a.设计报告要求用A4纸打印成册：b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。（7）附录源程序清单（带注释）3.2 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计

11、报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤 （占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占10%）。3.3 课程验收要求（1）运行所设计的系统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打

12、分。二、 进度安排第 19 周：星期一 8：0012：00 上机 星期二 8：0012：00 上机星期三 14：3018：30 上机 一、课题的主要功能1.程序的功能 编写银行家算法通用程序，并检测所给状态的系统安全性，可利用资源向量Available。这是一个含有N个元素的数组，其中的每一个元素代表一类可利用的资源数,其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。 最大需求矩阵Max这是一个M*N的矩阵，它定义了系统中M个进程中的每一个进程对N类资源的最大需求。如果Maxij=K，则表示进程i需要Rj类资源的最大数目为K。 分配矩阵Allocati

13、on。这也是一个n*m的矩阵，它定义了系统中每一类资源 当前已分配给没一进程的资源数。如果Allocationij=K，则表示 进程i当前已分得Rj类资源的数目为K。 需求矩阵Need。这也是一个M*N的矩阵，用以表示每一个进程尚需的各类资源数。如果Needij= Maxij- Allocationij，则表示i个进程对j类资源需求量，方能完成其任务。 设Requesti 是进程Pi的请求向量，如果Requestij=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果Requestij= Needij，便转向步骤2；否则认为出错，因为它所需要的资源数已超

14、过它所宣布的最大值，不能进行资源分配。2.输入输出的要求(1)以键盘输入的方式输入进程的数量，资源种类数，各种资源可利用的数量 Available，各进程已分配的资源数量Allocation和各进程对各类资源的最大需求Max; (2)输出显示当前系统的状态；(3)如果预分配后，系统处于安全状态，则修改系统的资源分配情况，并予以显示；(4)如果预分配后，系统处于不安全状态，则提示不能满足请求，并恢复预分配前的数据。2、 课题的功能模块的划分1. 各功能模块(1) 字符判断模块：由数字判断函数（ int shuzi(int sz); ）实现。判断输入的字符是否为数字，如果不是则提示出错并重新输入，

15、主要处理输入为非数字时程序出现运行错误现象。（2）程序初始化模块：由初始化函数（void chushihua(); ）实现，用于程序开始进行初始化输入数据：进程数量、资源种类、各种资源可利用数量Available、各进程的各种资源已分配数量Allocation、各进程对各类资源最大需求数Max等。（3）安全算法模块：由安全算法函数（void safe(); ）实现，用于判断当前状态安全性，根据不同地方的调用提示不同处理。（4）银行家算法模块：由银行家算法函数（void bank();）实现，进行银行家算法实现的模块，调用其他各个模块进行银行家算法过程。（5）分配模块：由分配显示函数（void

16、showdata(); ）实现，显示当前资源分配详细情况，包括：各种资源的总数量(all)、系统目前各种资源可用的数量Available、各进程已经得到的资源数量Allocation、各进程还需要的资源量Need。2.数据结构2.1 全局变量const int x=50,y=100; /定义常量，便于修改int Availablex; /各种资源可利用的数量int Allocationyy; /各进程当前已分配的资源数量int Maxyy; /各进程对各类资源的最大需求数量int Needyy; /需求资源矩阵int Requestx; /申请各类资源的数量int Workx; /工作向量，表

17、示系统可提供给进程运行所需各类资源数量int Finishy; /表示系统是否有足够的资源分配给进程，0为否，1为是int py; /存储安全序列int i,j; /全局变量，主要用于循环语句中int n,m; /n为进程的数量,m为资源种类数int l=0,counter=0;2.2 函数声明int shuzi(int sz); /数字判断函数void chushihua(); /系统初始化函数void safe(); /安全性算法函数void bank(); /银行家算法函数void showdata(); /输出显示当前资源分配情况2.3 主函数结构 int main() coutend

18、lendl; chushihua(); /初始化函数调用 coutendl; showdata(); /输出初始化后的状态 safe(); /安全性算法函数调用 if (ln) coutn当前状态不安全，无法申请,程序退出!endl; coutendl; system(pause); return 0; Else int i; l=0; /局部变量 coutn安全的状态!endl; cout安全序列为: ; coutendl进程(p0); /输出安全序列 for (i=1; in; i+) cout进程(pi); for (i=0; in; i+) Finishi=0; /所有进程变为未分配状

19、态 coutendlendl; bank(); /银行家算法函数调用 return 0; / break; 3、 主要功能的实现1.程序流程图 银行家算法bank（） 初始化Init（） 请求资源request i Requesti =needi 错误Request itemp; len=strlen(temp); /取字符长度 for(int i=0;ilen;i+) s= *(temp+i); if(s9) cout 输入的数字有误，请重新输入! nn; cout请重新输入：; break; while(s9); for(int i=0;ilen;i+) /输入字符串转化为整形数字 int

20、 t=1; for(int j=1;jlen-i;j+) t*=10; sz+=(*(temp+i)-48)*t; return sz;3. 程序初始化模块此模块在程序开始时输入相关数据：进程数量、资源种类、各种资源可利用数量Available、各进程的各种资源已分配数量Allocation、各进程对各类资源最大需求数Max等。 void chushihua() /系统初始化函数 cout =欢迎进入银行家算法= endl; cout=endlendl; cout请输入进程的数量: ; /输入相关数据 n=shuzi(n); cout请输入资源种类数: ; m=shuzi(m); couten

21、dl请输入各种资源可利用的数量( m 种): endl; coutendl; for (j=0; jm; j+) cout 输入资源 j 可利用的数量Availablej: ; Availablej=shuzi(Availablej); Workj=Availablej; /初始化Workj coutendl; cout请输入各进程当前已分配的资源数量Allocationnm: endlendl; for (i=0; in; i+) for (j=0; jm; j+) cout 请输入进程 i 当前已分配的资源 j 数量: ; Allocationij=shuzi(Allocationij);

22、 coutendl; Finishi=0;/初始化Finishi coutendl; cout请输入各进程对各类资源的最大需求数Maxnm: endlendl; for (i=0; in; i+) for (j=0; jm; j+) cout 请输入进程 i 对资源 j=Allocationij) / Needij = Maxij-Allocationij; /计算还需求量 else Needij=0; /判断是否还需要分配资源 coutendl; cout% 初始化完成! %endl;4. 安全算法模块 此模块用于判断当前系统安全性，根据不同地方的调用提示不同处理。void safe() l

23、=0; for (i=0; in;)if (Finishi=0) /寻找Finishi=0的进程 counter=0; /记数器 for (j=0; j=Needij); /可用大于等于需求 elsecounter=1; break; if(counter!=1) Workj=Needij /进程的每类资源量都符合条件 pl=i; /存储安全序列 Finishi=1; /标志为可分配 for (j=0; jm;j+) Workj=Workj+Allocationij; /释放资源 l=l+1; /记数,当L=N时说明满足安全序列 i= -1; /从第一个进程开始继续寻找满足条件一二的进程 i+

24、; /for循环继续寻找 5. 银行家算法模块 进行银行家算法实现的模块，调用其他各个模块进行银行家算法过程。void bank() cout% 以下开始为进程进行资源分配申请 %endlendl;/申请资源 int k=0; /用于输入进程编号 bool r=false; / 初值为假，输入Y继续申请则置为真 do cout请输入申请资源的进程编号(输入0-n-1之间): ; /输入请求 k=shuzi(k); coutn-1) coutendl您输入了错误的进程号，请重新输入!endl; /输入异常处理 coutendl请输入申请资源的进程编号(输入0-n-1之间): ; k=shuzi(

25、k); coutendl; coutendl请输入该进程申请各类资源的数量: endl; for (j=0; jm; j+) do cout进程 k 申请资源j的数量:; /循环判断申请输入的情况 Requestj=shuzi(Requestj); coutNeedkj) cout申请大于需要量!endl; /申请大于需求量时出错 cout您申请资源j的数量为Requestj,大于进程k对该资源需求量Needkj。endl; cout请重新输入!Availablej)/申请大于可利用量 coutn没有那么多资源，目前可利用资源j数量为Availablej,本次申请不成功，进程等待!Needkj

26、); /RequestjAvailablej| /改变Avilable、Allocation、Need的值 for (j=0; jm; j+) Availablej = Availablej-Requestj; Allocationkj = Allocationkj+Requestj; Needkj = Needkj-Requestj; Workj = Availablej; /判断当前状态的安全性 safe(); /调用安全性算法函数 if (ln) l=0; coutn当前状态不安全,不予分配!endl; /恢复数据 for (j=0; jm; j+) Availablej = Avail

27、ablej+Requestj; Allocationkj = Allocationkj-Requestj; Needkj = Needkj+Requestj; Workj = Availablej; for (i=0; in; i+) Finishi=0; /进程置为未分配状态 else l=0; coutn申请资源成功!endl; for(j=0;jm;j+) if(Needkj=0); else /有一种资源还没全部申请到，则该进程不可执行，不能释放拥有的资源 l=1; /置l为1，作为判断标志 break; if(l!=1) /进程可以执行，则释放该进程的所有资源 for (j=0;jm

28、;j+) Availablej=Availablej+Allocationkj; Allocationkj=0; cout该进程已得到所有需求资源，执行后将释放其所有拥有资源！endl; l=0; /归零 coutn安全的状态!endl; cout安全序列为: ; coutendl进程(p0); /输出安全序列，考虑显示格式，先输出第一个 Finish0=0; for (i=1; in; i+) cout进程(pi); Finishi=0; /所有进程置为未分配状态 coutendlendl; showdata(); /显示当前状态 ppp: /申请大于可利用量， 应该阻塞等待,结束本次资源申

29、请，GOTO 语句跳转至此 coutendl是否继续申请资源(y/n) ?; char* b=new char; /输入y/n，判断是否继续申请 b; coutendl; cout=endlendl; coutendl; if(*b=y|*b=Y) r=true; else r=false; /输入非 Y 则令 R =false / system(cls); / /在sign() 里调用 while (r=true);6. 分配模块此模块用于显示当前资源分配详细情况，包括：各种资源的总数量(all)、系统目前各种资源可用的数量Available、各进程已经得到的资源数量Allocation、各

30、进程还需要的资源量Need。void showdata() /函数showdata,输出当前资源分配情况 int i,j; /局部变量 int Ally; /各种资源的总数量 int l2; /局部变量 l cout=endl; coutendl% 系统当前状态如下：%endl; cout% 各种资源的总数量(all):endl; for (j=0;jm;j+) cout 资源j: ; Allj=Availablej; /初始化 先赋值加上可利用量 for (i=0;in;i+) Allj+=Allocationij; /再加上每个进程已分配量计算J类资源总量 coutAllj ; if (j

31、+1)%5=0 ) coutendl; /每行显示五个 & j!=0 coutendlendl; cout% 系统目前各种资源可用的数为(available):endl; for (j=0;jm;j+) cout 资源j: Availablej ; if(j+1)%5=0) coutendl; /每行最多显示五个 & j!=0 coutendlendl; cout% 各进程已经得到的资源量(allocation): endl; for(i=0;i=m/5;i+) /设计每行最多显示五种资源 for (j=i*5;ji*5+5 & jm;j+)cout 资源j; coutendl; for(l2

32、=0;l2n;l2+) cout进程l2:; for (j=i*5;ji*5+5 & jm;j+)coutAllocationl2j ; coutendl; coutendl; cout% 各进程还需要的资源量(need):endl; for(i=0;i=m/5;i+) /设计每行显示五种资源 for (j=i*5;ji*5+5 & jm;j+)cout 资源j; coutendl; for(l2=0;l2n;l2+) cout进程l2:; for (j=i*5;ji*5+5 & jm;j+)coutNeedl2j ; coutendl; coutendl; coutendl; system(

33、pause); / 暂停4、 程序调试 图2 各类资源输入 当进入银行家算法界面后，输入进程信息和各类资源，包括：进程数量、资源种类、各种资源可利用数量Available、各进程的各种资源已分配数量Allocation、各进程对各类资源最大需求数Max。图3 当前资源状态及安全序列通过输入相关信息后，利用显示函数予以显示出来，并在此时刻利用安全性算法进行分析，可知存在一个安全序列进程，进程，进程，进程，进程，故此时系统是安全的。 图4 进程1申请资源 当进程1发出请求向量Request（1，0，2）系统按照银行家算法进行检查，再利用安全性算法检查此时系统是否安全。经检查，找到一个安全序列进程，

34、进程，进程，进程，进程，因此，系统安全，可以将进程1所申请资源分配给它。 图5 进程0申请资源当进程1发出请求向量Request（1，0，2）系统按照银行家算法进行检查，再利用安全性算法检查此时系统是否安全。此时，可利用资源Available（2，1，0）已不能满足任何进程的需要，故若实施分配系统将进入不安全状态，此时系统不分配资源。5、 总结 通过本次课程设计，使我基本懂得了操作系统教程的基础理论知识和设计方法，同时在课设时遇到了不少的问题，通过查阅相关书籍或请教老师同学获得了不少的帮助，在此期间也学到了不少的知识，提升了知识层面的容量，扩宽了设计的道路。 由于在课设中也遇到了关于银行家算法

35、的相关问题，但也比较轻松的解决了，同时也学习到了在实践时的不同知识，真的让我获益良多。课程设计中需要自我的耐心和解决问题的勇气，正好让我体验了一把，没有足够的耐心只会感觉到它的枯燥乏味，而没有体会到实践带来的动手能力的提高，这是在以后工作中不可缺少的能力之一，在此感谢辛勤的老师和帮助过我的同学，希望我们一起提高和进步。我们不知道我们接下来的学期里会有多少课程设计，但我们已经有足够面对它的勇气，从中学会的有关做事情的一些态度和方法，将对我们终身受用，以便我们能在社会里创造更好的成就，为社会做出更多的贡献，所以真心的感谢所有老师，是你们让我有了体验的机会，让我懂得了做事不可能一蹴而就，需要有耐心和

36、毅力，当然这也是当前社会追求人才所要求的。六、附件#include #include #include #include #include /=定义全局变量=const int x=50,y=100; /定义常量，便于修改int Availablex; /各种资源可利用的数量int Allocationyy; /各进程当前已分配的资源数量int Maxyy; /各进程对各类资源的最大需求数int Needyy; /还需求矩阵int Requestx; /申请各类资源的数量int Workx; /工作向量，表示系统可提供给进程继续运行所需的各类资源数量int Finishy; /表示系统是否有足

37、够的资源分配给进程，0为否，非0为是int py; /存储安全序列int i,j;int n,m; /n为进程的数量,m为资源种类数int l=0,counter=0;/函数声明int shuzi(int sz); /数字判断函数 或者使用 void shuzi(int& sz); 方式void chushihua(); /系统初始化函数void safe(); /安全性算法函数void bank(); /银行家算法函数void showdata(); /函数showdata,输出当前资源分配情况/=数字判断函数=int shuzi(int sz) /输入数据并判断是否为数字 char *te

38、mp; temp=new char; /临时指针，存放输入字符 int len; /存储取字符的长度 sz=0 ; /清零 char s; / do /输入赌注，只能输入数字 / gets(temp); /getline(cin,temp) cintemp; len=strlen(temp); /取字符长度 for(int i=0;ilen;i+) s= *(temp+i); if(s9) cout 输入的数字有误，请重新输入! nn; cout请重新输入：; break; while(s9); for(int i=0;ilen;i+) /输入字符串转化为整形数字 int t=1; for(i

39、nt j=1;jlen-i;j+) t*=10; sz+=(*(temp+i)-48)*t; return sz;/=系统初始化函数=void chushihua() /=系统初始化输入= cout =欢迎进入银行家算法= endl; cout=endlendl; cout请输入进程的数量: ;/从此开始输入有关数据 n=shuzi(n); cout请输入资源种类数: ; m=shuzi(m); coutendl请输入各种资源可利用的数量( m 种): endl; coutendl; for (j=0; jm; j+) cout 输入资源 j 可利用的数量Availablej: ; Availablej=shuzi(Availablej); Workj=Availablej; /初始化Workj coutendl; cout请输入各进程当前已分配的资源数量Allocationnm: endlendl; for (i=0; in; i+) for (j=0; jm