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

《操作系统课程设计-银行家算法》由会员分享，可在线阅读，更多相关《操作系统课程设计-银行家算法（38页珍藏版）》请在金锄头文库上搜索。

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

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

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

4、性分配作废，系统恢复 原状，进程等待。课题 2：模拟操作系统中进程调度过程。 要求设计一个程序，该程序可模拟对 10个以上的进程进行 FCFS、SJF、HRP 的方式进 行调度。( 1) 设计进程控制块 PCB ，进程控制块至少包括进程号、到达时间和要求服务时间；(2) 动态或静态创建多个(N10)进程；(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官网https:/www.kernel.org/上载LINUX源代码，将其解压后，分析其中includelinux sched.h 和 kernel/sched/core.c 及相关源文件，了解其进程控制块结构，分 析 LINUX 进程调度策略及过程。课题7：分析LINUX中信号量实现部分源代码从LINUX官网https:/www.kernel.o

9、rg/上载LINUX源代码，将其解压后，分析其中 includelinuxsemaphore.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. 课题涉及的数据结构和数据库结构；即要存储什么数

10、据，这些数据是什么样 的结构，它们之间有什么关系等。( 3)详细设计a. 采用C语言定义相关的数据类型。b. 写出各模块的类C码算法。c. 画出各函数的调用关系图、主要函数的流程图。(4) 调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和 含有错误的输入及输出结果。b. 程序调试中遇到的问题以及解决问题的方法。c. 课程设计过程经验教训、心得体会。(5) 使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。(6) 书写格式a. 设计报告要求用A4纸打印成册：b. 级标题用3号黑体，二级标题用四号宋体加粗，正文用小四号宋体;行距为

11、22。7）附录源程序清单（带注释）3.2 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新 精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出 每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤 （占 10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占 40%）（4）设计报告（占 30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占 10%）。3.3 课程验收要求1）运行所设计的系

12、统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。二、 进度安排第 19 周：星期一8：0012：00上机星期二8：0012：00上机星期三14：3018：30上机、课题的主要功能1. 程序的功能编写银行家算法通用程序，并检测所给状态的系统安全性，可利用资源向量 Available 。这是一个含有 N 个元素的数组，其中的每一个元素代表一类可利用 的资源数 ,其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类 资源的分配和回收而动态地改变。最大需求矩阵 Max 这是一个 M*N 的矩阵，它

13、定义了系统中 M 个进程中的每一 个进程对N类资源的最大需求。如果Maxij=K，则表示进程i需要Rj类资源 的最大数目为 K。分配矩阵 Allocation 。这也是一个 n*m 的矩阵，它定义了系统中每一类资 源 当前已分配给没一进程的资源数。如果 Allocationij=K ，则表示 进程 i 当前已分得 Rj 类资源的数目为 K。需求矩阵Need。这也是一个M*N的矩阵，用以表示每一个进程尚需的各类 资源数。如果 Needij= Maxij- Allocationij ，则表示 i 个进程对 j 类资源需求量，方能完成其任务。设 Requesti 是进程 Pi 的请求向量，如果 Re

14、questij=K, 表示进程 Pi 需要 K 个 Rj 类型的资源。当 Pi 发出资源请求后，系统按下述步骤进行检查：如果 Requestij= Needij ，便转向步骤 2；否则认为出错，因为它 所需要的资源数已超过它所宣布的最大值，不能进行资源分配。2. 输入输出的要求(1) 以键盘输入的方式输入进程的数量，资源种类数，各种资源可利用的数量Available，各进程已分配的资源数量Allocation和各进程对各类资源的最大需求 Max;(2) 输出显示当前系统的状态；(3) 如果预分配后，系统处于安全状态，则修改系统的资源分配情况，并予以显 示；(4) 如果预分配后，系统处于不安全状

15、态，则提示不能满足请求，并恢复预分配 前的数据。二、课题的功能模块的划分1. 各功能模块(1) 字符判断模块：由数字判断函数( int shuzi(int sz); )实现。判断输入 的字符是否为数字，如果不是则提示出错并重新输入，主要处理输入为非数字时程序出 现运行错误现象。(2) 程序初始化模块：由初始化函数( void chushihua(); )实现，用于程序开 始进行初始化输入数据：进程数量、资源种类、各种资源可利用数量Available、各进 程的各种资源已分配数量Allocation、各进程对各类资源最大需求数Max等。(3) 安全算法模块：由安全算法函数(voidsafe();)实现，用于判断当前状态 安全性，根据不同地方的调用提示不同处理。(4) 银行家算法模块：由银行家算法函数(void bank();)实现，进行银行家算