武汉理工大学华夏学院

课程设计报告书

课程名称：操作系统原理    

题    目：    编程序模拟银行家算法 

      系    名：        信息工程系        

专业班级：        软件 1111         

姓    名：        张安格                                       

学    号：       10212811105        

指导教师:           苏永红           

 2013年 12 月 13 日

武汉理工大学华夏学院信息工程系

课程设计任务书

课程名称： 操作系统原理课程设计   指导教师：    苏永红              

班级名称： 软件1111    开课系、教研室：  软件与信息安全   

一、课程设计目的与任务

操作系统课程设计是《操作系统原理》课程的后续实践课程，旨在通过一周的实践训练，加深学生对理论课程中操作系统概念，原理和方法的理解，加强学生综合运用操作系统原理、Linux系统、C语言程序设计技术进行实际问题处理的能力，进一步提高学生进行分析问题和解决问题的能力，包含系统分析、系统设计、系统实现和系统测试的能力。

学生将在指导老师的指导下，完成从需求分析，系统设计，编码到测试的全过程。

二、课程设计的内容与基本要求

1、课程设计题目

  编程序模拟银行家算法

2、课程设计内容

本课程设计要求在Linux操作系统，GCC编译环境下开发。

银行家算法是避免死锁的一种重要方法，本实验要求用用c/c++语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

思想：将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。

   3、设计报告撰写格式要求：

1设计题目与要求    2 设计思想

    3系统结构    4 数据结构的说明和模块的算法流程图

    5 使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明

6 运行结果和结果分析（其中包括实验的检查结果、程序的运行情况）

7 自我评价与总结

    8 附录：程序清单，注意加注释（包括关键字、方法、变量等），在每个模块前加注释；

三、课程设计步骤及时间进度和场地安排

本课程设计将安排在第15周, 教育技术中心。具体安排如下：

第一天       下发任务书，学生查阅资料

第二天       系统设计和原型开发

第三，四天 系统功能实现

第五天 系统调试 测试 打包和验收

四、课程设计考核及评分标准

课程设计考核将综合考虑学生考勤和参与度，系统设计方案正确性，系统设计和开发效果以及课程设计报告书的质量。具体评分标准如下：

设置六个评分点

（1）设计方案正确，具有可行性、创新性；              25分

（2）系统开发效果较好；                              25分

（3）态度认真、刻苦钻研、遵守纪律；                  10分

（4）设计报告规范、课程设计报告质量高、参考文献充分    20分

（5）课程设计答辩概念清晰，内容正确                   10分

（6）课程设计期间的课堂考勤、答疑与统筹考虑。        10分

   按上述六项分别记分后求和，总分按五级记分法记载最后成绩。

优秀（100～90分），良好（80～89分），中等（70～79分），及格（60～69分），

不及格（0～59分）

1.题目要求与实验目的

1.1 实验目的：

1.1.1进一步理解利用银行家算法避免死锁的问题；

1.1.2在了解和掌握银行家算法。

1.1.3理解和掌握安全序列、安全性算法

1.2 设计题目:

编程序模拟银行家算法

1.3 要求 ：

本实验要求用用 c/c语言在 Linux 操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

1.4 实验内容 ：

1.4.1编写安全性算法；

1.4.2编写银行家算法，并编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。

2 设计思想

将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。

用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。

3.需求分析

 3.1问题描述：利用银行家算法模拟计算机系统分配资源的过程。

 3.2要求：

3.2.11、以课本例题中数据为例，模拟资源分配过程。

 3.2.2、系统中资源种类，各类资源数目，进程申请资源数目可任意输入，模拟资源分配过程。 

4. 系统结构

图 1

5.数据结构的说明和模块的算法流程图

5.1 数据结构：

①可利用资源向量 Available 是个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果 AvailablejK，则表示系统中现有 Rj 类资源 K 个。

②最大需求矩阵 Max 这是一个 n×m 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果 MaxijK，则表示进程 i 需要 Rj 类资源的最大数目为 K。 ③分配矩阵 Allocation 这也是一个 n×m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 AllocationijK，则表示进程 i 当前已分得 Rj 类资源的 数目为 K。

④需求矩阵 Need。 这也是一个 n×m 的矩阵，用以表示每一个进程尚需的各类资源数。如果NeedijK，则表示进程 i 还需要 Rj 类资源 K 个，才可以完成其任务。

5．2 程序流程图：

①、系统主要过程流程

②、安全性算法流程图

6 用户手册

6.1 首先在终端中使用 vi 编辑器建立 c 的源文件

6.2 然后使用 gcc 编辑器编译生成可执行文件

6.3 使用命令./当前名字，来执行

7. 运行结果和结果分析

7．1 运行结果：

申请成功如图 2，申请失败如图 3：

 图 2 申请金额在需求范围之内同意

图 3 申请金额在需求范围之外拒绝

7.2 结果分析

首先是自己定义 5 个用户所需的金额数，银行可以给用户贷款的总金额数是100，用户 Id 号的范围是在 0 到 4，超过 4 之后的 id 请求贷款，会显示拒绝提示信息，每个客户的贷款数量必须是在之前定义的范围之内，如果超出，也会出现错误提示，只有在规定的用户 id 和在客户所要求金额的范围之内请求，才会给予贷款，并且输出安全序列号。

8. 自我评价与总结

     一周的课程设计结束了。在这一周里，我收获很多，以前都是在自己的教室由我们自己的老师进行讲课，这次学校没有这样做，而是请的校外的老师给我们做课程设计，让我们体会一下真正的公司是怎样做业务的。在这一周里我做一个模拟银行家算法。我觉得在着手设计前设计的思路是很重要的。只有思路清晰才能进行下一阶段的设计。这样才能完成整个程序的设计，完成整个文报告的书写。

课程设计这几天学到的东西还真不少。以前不清楚的现在都暴露出来了。以前认为学了没用的东西现在也用到了。这次的课程设计使我进一步了解了调度与死锁的问题。以及有关资源申请的问题、避免死锁的具体实施方法。深入了解了银行家算法的资源申请和资源分配的过程及原则。保证系统处于安全状态。

经过本周的课程设计，我对操作系统的掌握又进了一步，收获了很多知识。 ，终于我了由于对 c 语言不够熟练，在试验过程中，进行了反复的修改和调试，解银行家算法的基本原理，并且在此次的课程设计中我又复习了一下 c 语言，加深了对它的了解，而且在课程设计的过程中我们同样学会了如何简单的操作与使用 Linux 操作系统，学习到了许多 Linux 操作系统中常用的一些密令。 这次的设计数据是通过一道实际的题目来体现银行家算法避免死锁的问题，先用银行家算法给其中一个进程分配资源，看它所请求的资源是否大于它的需求量，才和系统所能给的资源相比较.让进程形成一个安全队列看系统是否安全.再利用安全性算法检查此时系统是否安全。

操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起“死锁”。而我本次课程设计就是得用银行家算法来避免“死锁”。银行家算法就是一个分配资源的过程，使分配的序列不会产生死锁。此算法的中心思想是：按该法分配资源时，每次分配后总存在着一个进程，如果让它单独运行下去，必然可以获得它所需要的全部资源，也就是说，它能结束，而它结束后可以归还这类资源以满足其他申请者的需要。  通过这次实验，我体会到银行家算法的重要性，银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我来学习借鉴。  

附录：

主要源程序

 

 

 

参考文献

[1] 张尧学主编．计算机操作系统教程（第三版）．北京:清华大学出版社，2006

[2] 张尧学编．计算机操作系统教程（第三版）习题解答与实验指导．北京:清华大学出版社，2006

[3] 汤子瀛主编．计算机操作系统（第三版）．西安:西安电子科技大学出版社，2001 

[4] 张坤等编．操作系统实验教程．北京:清华大学出版社，2008

[5] 张丽芬等编．操作系统实验教程．北京:清华大学出版社，2006

[6] 屠祁等编.操作系统基础（第三版）．北京:清华大学出版社，2000

[7] 冯耀霖等编.操作系统.西安:西安电子科技大学出版社，2001

[8] 左万历．计算机操作系统教程（第二版）．北京：高等教育出版社，2004

[9]谭浩强.《C语言程序设计》. 北京：清华大学出版社2003

[8] 庞丽华.《操作系统原理》（第四版）.北京. 华中科技大学出版社 2002

第二篇：操作系统题目

操作系统课程设计题目与要求

一、课程设计要求：

1．根据每道题的人数选定题目。 

2．分析设计要求，给出解决方案，建立必要的数据结构，然后设计总体流程（包括界面）、详细设计必要的算法，并最终显示结果。基于WINDOWS或LINUX操作系统都可以，用何种编程语言都有可以。 

3．提交设计报告，包括设计要求、设计思想流程、设计所涉及的主要数据结构、程序清单、运行结果、设计心得、参考资料等。 

4．严禁抄袭，复制设计内容，查出后相关同学设计成绩以零分处理。 

5．所提交源程序应是能够运行通过的完整程序。 

6．课程设计参考评分标准：

设计思想说明（10分）。

数据结构的说明（6分）。

各模块的算法流程图（10分）。

程序清单：注意加注释（包含关键字、方法、变量等），在每个模块前加注释；（共70分，其中书面源程序占35分，实验的检查结果、程序的运行情况占35分）。

体会，总结（4分）。

 二、设计题目

1． Windows多线程控制台程序（2人）

目的：学习和掌握如何编写Windows多线程控制台程序。通过编写程序，加深对进程和线程关系的理解，掌握多线程程序的执行和编写技巧。 

设计要求：写一个单进程多线程的Windows控制台程序，该程序在一个进程内建立N个线程来执行指定的任务。N由命令行传递给系统。 

Win32控制台程序中，主函数的格式如：

Void main(int argc,char *argv[])，可以获取命令行参数。

通过VC++“工程/设置”的C/C++属性页设置应用程序为“MTD”多线程。 

利用win32 API  CreateThread()来生成线程。 

2．睡眠理发师问题（2人）

目的：了解信号量机制，了解并掌握进程同步和互斥机制，熟悉信号量的操作函数，利用信号量实现对共享资源的控制。

设计要求：

（1）编写程序实现理发师与顾客进程的同步。

问题描述：这是一种经典的IPC问题，理发店有一位理发师，一把理发椅和n把用来等候理发的椅子。如果没有顾客，则理发师在理发椅上睡觉，顾客理来时，如理发师闲则理发，否则如有空椅则坐等，没有空椅则离开，编写程序实现理发师和顾客程序，实现进程控制，要求不能出现竞争。

（2）将（1）题中问题修改为有两位理发师，设计程序实现同步控制。 

问题提示：可以用一个变量waitting来记录等候理发的顾客数，另使用三个信号量：用来记录等候理发的顾客数customers；用来记录理发师是否空闲的信号量barbers，一个用于互斥访问waitting变量的mutex.。

3．进程调度模拟程序1（2人）

目的：深入掌握进程调度的概念原理和实现方法。 

设计要求：编写一个进程调度程序，允许多个进程并行执行。 

进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）、先来先服务算法、按时间片轮转调度算法，最终总结该算法的优缺点，写出设计体会。

每个进程有一个进程控制块（PCB）表示，进程控制块可以包含如下信息： 

进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。 

进程的优先数及需要的运行时间可以事先人为指定（也可以由随机数产生）。进程的到达时间为输入进程的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪W（wait）、运行R（run）或完成F（finish）三种状态之一。 

4．进程调度模拟程序2（1人） 
目的：深入掌握进程调度的概念原理和实现方法。 

设计要求：编写一个进程调度程序，允许多个进程并行执行。

进程调度算法：采用最高优先数优先与按时间片轮转调度结合算法，最终总结该算法的优缺点，写出设计体会。

如果运行下个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进行已占用CPU时间还未达到所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1(即降低一级)，然后把它插入就绪队列等待CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。重复以上过程，直到所有进程都完成为止。 

5．读者与写者问题（进程同步问题）（2人）

目的：了解进程同步的概念，理解信号量机制的原理，掌握运用信号量解决进程同步问题的方法，进而学会运用进程的同步与互斥。

设计要求：编程模拟读者与写者问题，要求显示结果。

问题描述：

（1）多个进程共享一个文件，其中只读文件的称之为读者，其余只写文件称为写者。读者可以同时读，但是写者只能独立写。 

（2）对（1）修改，使得它对写者优先，即一旦有写者到，后续的读者都必须等待，而无论是否有读者在读文件。 

6．模拟文件管理系统（3人） 

目的：深入了解文件管理系统，初步掌握文件管理系统的实现方法。

设计要求：编写一程序，模拟一个简单的文件管理系统。树型结构，目录下可以是目录，也可以是文件。 

在此文件管理系统，可实现的操作有：

改变目录：格式：cd <目录名> 

显示目录：格式：dir[<目录名>] 

创建目录：格式：md <目录名> 

删除目录：格式：rd<目录名> 

新建文件：格式：edit<文件名> 

删除文件：格式：del<文件名> 
退出文件系统：exit 

实现参考： 
（1） 文件系统采用二叉树型存储结构，结点结构如下： 

Struct FileNode 

{ 
Char filename[FILENAME_LEN];//文件名/目录名 

Int isdir ;//目录、文件的识别标志 

Int i_nlink;//文件链接数 

Int adr;//文件的地址 

Struct FileNode *parent,*child;//指向父亲的指针和左孩子的指针 

Struct FileNode *sibling_prev,*sibling_next;//指向前一个兄弟的指针和后一个兄弟的指针。 

} 
（2） 目录名和文件名支持全路径名和相对路径名，路径名各分量间用“/”隔开 
（3） 功能具体描述： 
改变目录：改变当前工作目录，目录不存在是给出出错信息 

显示目录：显示指定目录下或当前目录下所有文件和一级目录（选做：带/s参数的dir命令，显示所有子目录） 

创建目录：在指定路径或当前路径下创建指定目录。重名时给出出错信息。 

删除目录：删除指定目录下所有文件和子目录。要删目录不空时，要给出提示是否要删除。 

创建文件：创建指定名字的文件，只要创建表示文件的节点即可，内容及大小不考虑。 

删除文件：删除指定文件，不存在时给出出错信息。 

退出文件系统：exit 

（4） 总体流程： 

初始化文件目录 

输出提示符，等待接受命令，分析键入的命令；

对合法的命令，执行相应的处理程序，否则输出错误信息，继续等待新命令。直到键入exit退出为止。 
7．内存的申请与释放（2人） 

目的：了解操作系统内存分配的算法。 

设计要求： 

（1） 定义一个自由存储块链表，按块地址排序，表中记录块的大小。当请求分配内存时，扫描自由存储块链表，址到找到一个足够大的可供分配的内存块，若找到的块大小正好等于所请求的大小时，就把这一块从自由链表中取下来，返回给申请者。若找到的块太大，即对其分割，并从该块的高地址部分往低地址部分分割，取出大小合适的块返回给申请者，余下的低地址部分留在链表中。若找不到足够大的块，就从操作系统中请求另外一块足够大的内存区域，并把它链接到自由块链表中，然后再继续搜索。

释放存储块也要搜索自由链表，目的是找到适当的位置将要释放的块插进去，如果被释放的块的任何一边与链表中的某一块临接，即对其进行合并操作，直到没有合并的临接块为止，这样可以防止存储空间变得过于零碎。

（2） 空闲区采用分区说明表的方法实现（1）中的功能。要求同上。 

8． Windows磁盘直接读写实验（2人）

目的：了解磁盘设备编程的特点。

设计要求：通过本实验了解在windows系统中如何直接使用磁盘的读写功能；所编应用程序能够响应用户指定的读写磁盘扇区的请求，也能提供查看磁盘相关参数的功能。技术的关键是使用了windows提供的API（应用程序接口）来实现所要求的功能。用户可以利用API进行底层的磁盘操作。

相关知识：（下列函数的详细使用方法参看VC++的MSDN文档）

（1） CreateFile:用来创建或者打开一个文件、管道、磁盘设备等，它返回一个句柄用于以后对这信对象的访问。

（2） DeviceControl:本API直接向相应设备的驱动程序发出指令，以完成在函数参数中所指定的动作。

（3） WriteFile：本API用于向文件中写入数据，写入操作可以采用同步方式或者异步方式，写入操作从文件指针处开始，写操作后会被相应调整。磁盘设备被当作文件看待。

（4） ReadFile:本API用于文件中读出数据，读出操作从文件指针处开始，文件指针在读操作后会被相应调整。用法同写文件函数相似。

（5） SetFilePointer:用于移动一个打开的文件中的读写指针。

9．处理机调度（2人） 

目的：加深作业概念的理解，深入了解多道程序设计系统中如何组织作业、管理作业和调度作业，加深对作业调度算法的理解。 

设计要求：采用短作业优先调度算法、先来先服务调度算法和最高响应比调度算法实现处理机对作业的调度。

作业调度算法的关键是在已有的作业后备队列上按照一定的规则选择一个作业，如何在已有的数据结构上进行操作的问题。

10．页面置换算法（2人）

目的：深入掌握内存调度算法的概念原理和实现方法。 

设计要求：编写程序实现：

（1） 先进先出页面置换算法（FIFO） 

（2） 最近最久未使用页面置换算法（LRU） 

（3） 最佳置换页面置换算法（OPT） 
专题：设计一个虚拟存储区和内存工作区，编程序演示以上三种算法的具体实现过程，并计算访问命中率。演示页面置换的三种算法。通过随机数产生一个指令序列，将指令序列转换成为页地址流。计算并输出各种算法在不同内存容量下的命中率。

11．售票员与乘客（信号量操作）（2人）

目的：了解进程同步的概念，理解信号量机制的原理，掌握运用信号量解决进程同步问题的方法，进而学会运用进程的同步与互斥。

设计要求：编程序模拟车站售票厅内进程同步问题，售票厅任何时刻最多可容纳20名购票者进入，否则需要在外面等待。每个购票者可看成一个进程。 

12．苹果问题（2人） 

目的：了解信号量机制，了解并掌握进程同步和互斥机制，熟悉信号量的操作函数，利用信号量实现对共享资源的控制。

设计要求：编程模拟实现这一问题的程序控制，分析处理过程，

问题描述：桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子放苹果（apple），妈妈专向盘子中放桔子（orange）；两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。

13．模拟实现动态分区内存分配与回收算法（2人）

目的：了解动态分区的管理管理，掌握动态分区的最先适应算法、最佳适应算法、最坏适应算法和分区的回收与合并。

设计要求：编程模拟动态分区的最先适应算法、最佳适应算法、最坏适应算法的分配过程，同时实现在回收过程中能对相邻区进行合并。

14．存储器管理系统设计（2人） 

目的：熟悉存储器管理系统的设计方法；加深对所学各种存储器管理方案的了解；要求采用一些常用的存储器分配算法，设计一个存储器管理模拟系统并调试运行。

设计要求：

⑴设计一个模拟内存分配的系统；

⑵采用分页内存管理策略； 

⑶输入数据为进程号，需要的内存量，并根据这些信息进行内存分配； 

⑷输入数据为进程号，则将该进程占用的内存释放；

⑸动态显示分配结果，用位示图来表示内存的使用情况。 

15、基于消息的通讯系统设计（2人）

目的：通过设计和调试一个基于消息的通讯系统，来实现进程之间的间接通讯，对进程间的通讯机制、进程间的同步机制有一个深入的理解。 

设计要求： 

⑴设计一个消息传递系统，使两进程以消息为单位进行数据交换；

⑵以间接方式进行这种传递，发送进程把消息发送到中间实体，接收进程从中取得消息； 

⑶中间实体应能保留一定数量的消息（如，保留10条消息）； 

⑷两进程应保证同步与互斥。 

16、模拟磁盘操作

课程设计内容与要求

一、设计内容：

模拟磁盘空闲空间的表示方法，以及模拟实现磁盘空间的分配和回收。

主要是单用户的磁盘文件管理部分，包括文件的逻辑结构、物理结构、目录、磁盘分配回收的实现。

二、设计要求：

1、磁盘的分配采用链接结构（显式链接）的分配。

2、文件的逻辑结构、目录采用树型目录结构。

3、磁盘空闲存储空间管理采用位视图方法。

4、位示图和显示链接的指针合在一起组成文件分配表。

按照各题中给出的初值，把程序运行的结果按各题的要求打印出来，为了检测程序的正确性，可自己再假设一组初值，运行设计的程序，检验运行结果。

17、猴子攀绳问题

猴子攀绳问题：峡谷上面有一条绳子，猴子可以攀在绳子上面越过峡谷。绳子上可以同时攀上多只猴子，但这些猴子的方向必须一样才能同时过去；否则，这些猴子就卡住了（死锁）。用信号量来避免死锁，给出猴子的越过峡谷的过程。

 

18、银行家算法实现

目的：了解死锁及死锁预防的方法，掌握银行家算法的实现。银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

设计要求：通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用银行家算法，有效地防止和避免死锁地发生。