《操作系统课程设计任务书.doc》由会员分享,可在线阅读,更多相关《操作系统课程设计任务书.doc(15页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、操作系统课程实验指导书一、 设计题目题目一:模拟实现页式虚拟存储管理页面置换算法题目二:模拟实现虚拟存储管理(请求分页存储管理)题目三:模拟实现可变分区存储管理题目四:模拟实现算法多级反馈队列进程调度算法题目五:模拟银行家算法二、 设计目的 操作系统课程实验是计算机类专业的集中实践性环节之一,是学习完操作系统课程后进行的一次全面的综合练习。其目的在于加深对操作系统课程的理解,使学生更好地掌握操作系统的基本概念、基本原理、及基本功能,理解操作系统在计算机系统中的作用、地位和特点,具有分析实际操作系统,设计、构造和开发现代操作系统的基本能力,为今后从事的各种实际工作,如设计、分析和改进各种系统软件
2、和应用软件提供必要的软件理论基础。、 设计内容设计内容一 页式虚拟存储管理页面置换算法1目的和要求在熟练掌握计算机虚拟存储技术的原理的基础上,利用一种程序设计语言模拟实现几种置换算法,一方面加深对原理的理解,另一方面提高学生通过编程根据已有原理解决实际问题的能力,为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。2设计内容阅读教材计算机操作系统第四章,掌握存储器管理相关概念和原理。模拟实现页式虚拟存储管理的三种页面置换算法(OPT、FIFO和LRU),并通过比较性能得出结论。前提:(1)页面分配采用固定分配局部置换。(2)作业的页面走向和分得的物理块数预先指定。可以从键盘
3、输入也可以从文件读入。(3)置换算法的置换过程输出可以在显示器上也可以存放在文件中,但必须清晰可读,便于检验。 3设计环境Windows操作系统、VC+6.0C语言4设计提示(1)基础知识 存储管理是操作系统进行资源管理的一个重要功能。现代操作系统广泛采用虚拟存储的技术对内存进行扩充。实现虚拟存储的一个主要技术手段就是将辅存和主存统一管理,在二者之间进行对换,从而形成物理上两级而逻辑上一级的存储管理系统。一个置换算法的好坏对这个逻辑上的单级虚存的性能起着极其重要的作用,而且会影响处理机的调度性能。 对于本任务规定的前提:页面分配采用固定分配局部置换,则置换发生的时机是作业已经将操作系统分配的固
4、定数目的物理块全部用完且发生缺页的时候。此时必须要将已经装入内存的部分逻辑页面换出以便将所缺的页面调入内存。置换算法就是一个决定将内存中“哪一个”页面换出的算法。(2)数据结构要模拟实现某一个置换算法,有如下一些对象需要用相关的数据结构来描述:l 作业的页面走向(执行过程中对页面的访问顺序)。可以用数组也可以用字符串。如果用数组,则页面走向的长度受数组长度限制,如果用字符串,则需要将字符串进行解析,将字符串经过解析处理后变成一个页面的排列顺序。考虑最佳置换算法(“向前看”)和其他置换算法(“向后看“)的特点。l 页框(作业分得的物理块)。由于作业分得的物理块数在置换算法执行之前已经确定,可以用
5、一些比较简单的数据结构实现。在综合置换算法的原理,可以灵活采用相应的数据结构,尽可能使程序的时间复杂度最低。如对于FIFO,队列最合适,对于LRU,则数组和堆栈都比较合适,采用不同的数据结构还要配合在数据结构上的相应操作才行。 (2)功能模块划分 大体上可以将整个程序的模块划分成如下几个部分:1)主模块:主要是初始化、界面和模块调用。2)页面走向输入模块。(从键盘读入数据结构或将页面走向写入文件)3)置换算法模块。 * 判断模块。决定换出哪一块。每一种置换算法对应一种判断算法。* 调整模块。根据判断模块的结果,调整作业分得物理块集合中逻辑页面的情况。 * 置换过程输出模块(在显示器上显示或写入
6、文件)。该模块每发生一次置换,由置换算法模块调用一次。*.除此之外,有些反复执行的操作考虑用过程或函数实现。总而言之,整个程序应该结构清晰,界面友好,可读性好,易调试,易扩充,易维护。 设计内容二 虚拟存储管理(请求分页存储管理)1目的和要求存储管理的主要功能之一是合理的分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是:通过编写和调试请求页式存储管理中页面置换算法的模拟程序以加深对存储管理方案的理解,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换方法;通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。2设计内容阅读教材计算机操作系统第四章,掌握存储器管理
7、相关概念和原理。(1)用C语言实现对分页式存储管理中的硬件的地址转换和产生缺页中断。(2)设计页表。分页式虚拟存储系统是把作业的副本存放在磁盘上,当作业被选中时,可把作业的开始几页先装入主存且启动执行。为此,在为作业建立页表时,应说明哪些页已在主存,哪些页尚未装入主存,页表的格式为:页 号 标 志 主存块号 在磁盘上的位置可根据页面置换算法的不同,页表构的内容可以作适当的增删。 (3)地址计算。作业执行时,指令中的逻辑地址指出了参加运算的操作数存放的页号和单元号,硬件的地址转换机构按页号查页表,若该页对应标志为“1”,则表示该页已在主存,这时根据关系式: 绝对地址=块号*块长+单元号计算出欲访
8、问的主存单元地址。按计算出的绝对地址可以取到操作数,完成一条指令的执行。若访问的页标志为“0”,则表示该页不在主存,这时硬件发“缺页中断”信号,由OS按该页在磁盘上的位置,把该页信息从磁盘读出装入主存后再重新执行这条指令。(4)设计“地址转换”程序模拟硬件的地址转换工作。当访问的页在主存时,则形成绝对地址,但不去模拟指令的执行,而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时,则输出“*该页页号”,表示产生了一次缺页中断,执行缺页中断程序。该模拟程序的算法如图1.2所示。开始是取一条指令取指令中访问的页号查页表该页标志=1?转缺页中断子程序形成绝对地址输出绝对地址有后继指令?结束
9、取一条指令否是否图 1.2 地址转换模拟流程图(5) 缺页中断模拟。如果访问页不在主存且页表未满,则调入一页并打印页表情况;如果该页不在主存且页表已满,则产生缺页中断,模拟算法如图1.3所示。输出:页号lnumber输出:*lnumber页号为lnumber淘汰页的页号j=phead将页lnumber装入队尾输出:页号j修改页表:第j页存在标志改为“0”第lnumber页存在标记改为“1”第lnumber页修改标记改为“0”第lnumber页主存块号为第j页原主存块号图 1.3 缺页中断算法流程图实验中采用FIFO算法进行页面淘汰。把在主存的页的页号按进入主存的先后次序排成队列,每次总是调出队
10、首页。用数组存放页号的队列。若分配给该作业的物理块数为m,则数组由m个元素组成,p0,p1pm-1,队首指针head,队尾指针tail。当装入新页时,将其页号装入数组。3设计环境Windows操作系统、VC+6.0C语言4设计主要步骤:1. 启动C语言环境,新建文件。2. 假定主存的每块长度为128个字节;现有一个共七页的作业,其中的第0页至第3页已经装入主存,其余三页未装入主存;该作业的页表为:015011118012219013311021400225002360121如果作业依次执行的指令序列(操作,页号,单元号)为:(+, 0, 070)、(+, 1, 050)、(*, 2, 015)
11、 、(存, 3, 021)、(取, 0, 056)、(, 6, 040)、(移位, 4, 053)、(+, 5, 023)、(存, 1, 037)、(取, 2, 078)、(+, 0, 070)、(+, 4, 001)、(存, 6, 084)。运行设计的地址转换程序,显示或打印运行结果。因仅模拟地址转换,并不模拟指令的执行,故可不考虑上述指令序列中的操作。3. 编写程序运行。设计内容三 模拟实现可变分区存储管理1目的和要求在熟练掌握计算机分区存储管理方式的原理的基础上,利用一种程序设计语言模拟实现操作系统的可变分区存储管理的功能,一方面加深对原理的理解,另一方面提高学生通过编程根据已有原理解决
12、实际问题的能力,为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。2设计内容设计合理的数据结构来描述存储空间:对于未分配出去的部分,可以用空闲分区队列或空闲分区链表来描述,对于已经分配出去的部分,由装入内存的作业占据,可以将作业组织成链表或数组。实现分区存储管理的内存分配功能,要求选择至少两种适应算法(首次适应算法和循环首次适应算法至少选一,最佳适应算法和最坏适应算法至少选一)。实现分区存储管理的内存回收算法:要求能够正确处理回收分区与空闲分区的四种邻接关系。当碎片产生时,能够进行碎片的拼接。3设计环境Windows操作系统、VC+6.0C语言4设计提示(1)基础知识 分
13、区存储管理是操作系统进行内存管理的一种方式。现代操作系统广泛采用多道程序设计的技术来提高系统吞吐量和内存的利用率。由于可变分区存储管理将一个连续的作业装入一片大小与作业恰好相等的内存中,因而地址变换的算法简单,需要的硬件支持少,变换效率高。但是最大的缺点是随着作业不断地进出内存,会将内存逐渐分割成一些大小很小而数目较多的小块,而且一块中仅能容纳一道作业,导致内存利用率较低。分区存储管理的另一个缺点是由于必须将整个作业的逻辑地址空间全部装入内存作业才可以开始运行,因而这种存储管理的方式无法实现内存的扩充。(2)数据结构要模拟实现可变分区存储管理,有如下一些对象需要用相关的数据结构来描述:l 内存
14、中没有被存储管理程序分配给作业的部分,属于空闲内存,要求以分区为单位进行统一管理以合理分配。包括对分区的描述(结构体)和对多个分区的组织(表格或链表)。l 对于内存中已经分配给作业的那部分内存,当作业完成后应该将占据的内存归还给系统,以便进行再分配。因此必须对已分配分区进行描述和组织,以便进行内存的回收。(2)功能模块划分 大体上可以将整个程序的模块划分成如下几个部分:1)主模块:主要是初始化(设置物理内存的用户区的大小,选取适应算法)和界面,界面参考如下:1-初始化2-作业进入内存(内存分配算法1)3-作业进入内存(内存分配算法2)4-作业完成(内存回收,相对于内存分配算法1)5-作业完成(
15、内存回收,相对于内存分配算法2)6-显示当前自由分区链7-显示当前内存中的作业占据的分区8-碎片拼接9-退出2)内存分配算法(实现两种适应算法)3)内存回收算法(考虑四种邻接情况,尤其是采用最佳(坏)适应算法时的分区合并)4)碎片拼接算法5)空闲分区队列显示6)作业队列显示除此之外,有些反复执行的操作考虑用过程或函数实现。总而言之,整个程序应该结构清晰,界面友好,可读性好,易调试,易扩充,易维护。设计内容四 模拟实现算法多级反馈队列进程调度算法1目的和要求在熟练掌握计算机处理机调度原理的基础上,利用一种程序设计语言模拟实现多级反馈队列进程调度算法,一方面加深对原理的理解,另一方面提高学生通过编
16、程根据已有原理解决实际问题的能力,为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。2设计内容模拟实现算法多级反馈队列进程调度算法,并分析其调度效果。前提: 调度算法中采用至少4级队列,每级队列的时间片大小预先指定。 由于只是模拟实现,调度的对象进程实际上并不包括程序和数据,而仅仅包括一个PCB数据结构,用PCB来代表一个进程,调度算法调度的对象只包括进程的PCB.处理机的切换通过将PCB在运行指针和就绪队列之间进行移动来实现。又因为进程的组成只有PCB,没有程序和数据,因而进程只有运行和就绪两种状态,没有等待状态。 为避免显示结果超过一屏,调度结果要求写入文件中以方便检
17、验。3设计环境Windows操作系统、VC+6.0C语言4设计提示(1)基础知识 由于处理机是计算机系统中最宝贵和稀有的资源,因而处理机调度是操作系统进行资源管理的一个重要功能。现代操作系统广泛采用多道程序设计的技术来提高系统吞吐量,提高程序的并发度和资源利用率。特别是进程调度程序,由于其运行频率高,更加要求调度算法简单,高效,系统开销小,进程切换快,可以说,调度算法的好坏直接影响整个计算机系统的性能。多级队列调度算法是一种动态优先数调度算法。对于普通的优先调度算法,如何确定进程优先级以真实地反映进程运行的紧迫程度是一个难题,但在多级队列调度算法中,可以预先规定优先级一样可以获得好的性能。该算
18、法实际上综合了两种调度算法:队列内部是FCFS,队列之间是优先调度。(2)数据结构最核心的数据结构就是进程的逻辑结构。进程中必须包括的内容很多(参见教材PCB部分的定义),为了简化起见,可以略去一些与本模拟调度算法关系不大的一些信息。请同学们自行设计,要求能够实现本调度算法即可。(2)功能模块划分 大体上可以将整个程序的模块划分成如下几个部分:多级队列调度算法模拟实现1-初始化2-创建进程3-调度4-显示各级就绪队列的进程5-退出1)主模块:主要是初始化(队列的级数和每级队列的时间片大小)和界面,可参考如下:2)进程创建3)调度算法实现4)显示多级队列中的就绪进程.除此之外,有些反复执行的操作
19、考虑用过程或函数实现。总而言之,整个程序应该结构清晰,界面友好,可读性好,易调试,易扩充,易维护。设计内容五 模拟实现银行家算法实现死锁避免1目的和要求在熟练掌握死锁发生原理和解决死锁问题的基础上,利用一种程序设计语言模拟实现利用银行家算法实现死锁避免,一方面加深对原理的理解,另一方面提高学生通过编程根据已有原理解决实际问题的能力,为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。2设计内容模拟实现银行家算法实现死锁避免。3设计环境Windows操作系统、VC+6.0C语言4设计提示模拟实现银行家算法对系统资源进行分配,以防止死锁的出现。本课题肯定不可能实现对实际操作系统
20、的资源管理,而是通过对模拟资源数据的处理,检测银行家算法在防止死锁出现的作用。l 银行家算法描述:第一部分:银行家算法(扫描)1如果Request=Need,则转向2;否则,出错2如果Request=Available,则转向3,否则等待3系统试探分配请求的资源给进程4系统执行安全性算法第二部分:安全性算法1.设置两个向量(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False2.若Finishi=False&Need=Work,则执行3;否则执
21、行4(i为资源类别)3.进程P获得第i类资源,则顺利执行直至完成,并释放资源:Work=Work+Allocation;Finishi=true;转2请充分理解以上银行家算法描述的核心思想。(详细银行家算法描述见p95)l 本课题的设计思路:l 需根据教材上银行家算法的描述定义一些模拟数据:系统中资源的种数(假设:n);每类资源的数量(假设:m1,m2,mn);当前系统中资源的使用情况等。l 设计方法:通过静态数据,人工输入来完成银行家算法的工作流程。此方法只需给出一个当前系统资源的使用情况的模拟数据矩阵(该数据可事先保存于磁盘文件,程序执行后从该磁盘文件读入矩阵数据),然后通过用户手工输入下
22、一个进程的资源申请要求的一维向量(控制台输入,此方式可以输入各种资源请求的可能情况,以检测当前的资源申请后是否系统处于安全状态)。六、 工作要求1. 上机前认真使用C语言编写好程序,采用Visual C+6.0作为编译环境;2. 上机时独立调试程序;3. 任务完成时报告老师,上机验收运行结果,现场提问;4. 根据具体任务要求,提交源程序电子档和纸质课程设计说明书。说明书中除了在封面应有题目、班级、姓名、学号和课程设计日期以外,其正文一般应包括: 1) 课程设计目的2) 课程设计内容3) 课程设计基本原理和解决方案4) 数据结构、模块划分5) 画出程序的基本结构框图和流程图(包括主程序流程图、模
23、块详细设计流程图等),对程序的每一部分要有详细的设计分析说明,说明设计实现所用的原理。6) 源代码,要求格式规范,必须有相关注释,以有助于说明问题为宜,注释不少于三分之一。7) 运行的结果,要求有对结果的分析。8) 设计中遇到的问题,设计的心得体会。9) 参考资料。七、成绩评定标准由指导教师根据学生完成任务的情况、课程设计说明书的质量和课程设计过程中的态度等综合打分。1. 课程设计说明书:30%包括设计说明书内容的全面性、正确性,文字表述的准确性和条理性,以及书写的工整程度等。2平时:30%平时主要包括考勤和操作练习的实际情况。3. 设计末考核:40%包括上机验收结果和现场提问结果。成绩评定标
24、准: 优(90100):能很好地完成实验所要求的任务,达到任务书中规定的全部要求,设计说明书能对整个任务进行全面、系统的总结,并能运用学过的理论知识对某些问题加以分析,在考核时能很圆满地回答问题,并有某些独到见解。学习态度很端正。 良(8089):能较好地完成实验所要求的任务,达到任务书中规定的全部要求,设计说明书能对整个系统内容进行比较全面、系统的总结。考核时能较圆满地回答问题,学习态度较端正。 中(7079):达到实验任务书中规定的主要要求,设计说明书能对整个系统内容进行比较全面的总结,在考核时能正确地回答主要问题,学习态度端正。 差(6069):完成了实验任务书的主要任务,达到任务书中规
25、定的基本要求,能够完成设计说明书,内容基本正确但不够完整、系统,考核中能回答主要问题。学习态度基本端正。 不及格(60):未达到实验任务书中规定的基本要求,设计说明书马虎潦草或内容有明显错位;考核时不能回答主要问题或有原则性错误。学习态度不端正。附:凡是上机未到者,每次扣除5分。上机时间内,做与本课程设计无关事情者,予以警告。屡教不改者当次上机视为旷课。处理办法见第条。上机时间内,无正当理由离开实验室长达半小时者,当次上机视为旷课。处理办法见第条。课程设计整个过程中,如果请假超过5次,即5次上机未能前来者,请速去系办公室办理缓考事宜。七、主要参考资料 1 汤子瀛等. 计算机操作系统(第四版). 西安:西安电子科技大学出版社2014 2 美William Stallings. 操作系统内核与设计原理. 北京:电子工业出版社 2001 3 美Abraham Silberschatz等. 操作系统概念(第六版) 北京:高等教育出版社 2004 4 荷Andrews Tanenbaum. 现代操作系统(第2版)北京:机械工业出版社 2005 5 谭浩强. C程序设计(第四版). 北京:清华大学出版社2010附:操作系统课程设计说明书封面武汉轻工大学数学与计算机学院操作系统课程设计说明书题 目: 专 业: 班 级: 学 号: 姓 名: 指导老师: 年月日
限制150内