计算机操作系统课程设计指导书.doc

计算机操作系统课程设计指导书湖南工业大学计算机与通信学院二O一三年 九月计算机操作系统课程设计说明计算机操作系统是计算机科学与技术专业的主要专业基础课程，其实践性、应用性很强。实践教学环节是必不可少的一个重要环节。计算机操作系统课程设计目的是加深对理论教学内容的理解和掌握，使学生较系统地掌握操作系统的基本原理，加深对操作系统基本方法的理解，加深对课堂知识的理解，为学生综合运用所学知识，在Linux环境下编写功能较简单的程序来实现操作系统的基本方法、并在实践应用方面打下一定基础。要求学生在指导教师的帮助下自行完成各个操作环节，并能实现且达到举一反三的目的，完成一个实验解决一类问题。要求学生能够全面、深入理解和熟练掌握所学内容，并能够用其分析、设计和解答类似问题；对此能够较好地理解和掌握，并且能够进行简单分析和判断；能够熟练使用Linux用户界面；掌握操作系统中进程管理概念和控制方法；了解进程的并发，进程之间的通信方式，了解虚拟存储管理的基本思想，了解设备管理的功能，了解文件系统的功能。同时培养学生进行分析问题、解决问题的能力；培养学生完成实验分析、实验方法、实验操作与测试、实验过程的观察、理解和归纳能力。为了收到良好的实验效果，编写了这本课程设计指导书。在指导书中，每一个课程设计任务按照该课程设计大纲的要求编写，力求紧扣理论知识点、突出设计方法、明确设计思路，通过多种形式引导学生有目的、有方向地完成课程设计任务，得出实验结果。任课教师在课程设计前对课程设计的任务进行一定的分析和讲解，要求学生按照课程设计任务的具体要求提前做准备工作，如：查找资料等，做到有准备地上机。进行课程设计时，指导教师应检查学生的预习情况，并对设计过程给予积极指导。课程设计完毕后，学生应根据课程设计情况，实验数据及结果，完成课程设计报告，由学习委员统一收齐后交指导教师审阅评定。任务1 进程管理演示一、课程设计目的加深对进程概念及进程管理各部分内容的理解；熟悉进程管理中主要数据结构的设计及进程调度算法、进程控制机构、同步机构及通讯机构的实施。二、课程设计内容设计一个允许n个进程并发运行的进程管理模拟系统。该系统包括有简单的进程控制、同步与通讯机构，其进程调度算法可任意选择（优先级调度，时间片轮转，短进程优先中的一种）。每个进程用一个PCB表示，其内容根据具体情况设置。各进程之间有一定的同步关系（可选）。系统在运行过程中应能显示或打印各进程的状态及有关参数的变化情况，以便观察诸进程的运行过程及系统的管理过程。三、课程设计指导 1）实验中使用的数据结构：1）PCB进程控制块其中包括参数进程名name；要求运行时间 runtime；优先级 prior；状态 state；已运行时间runedtime等。2）为简单起见，只设运行队列，就绪链表，阻塞队列三种数据结构，进程的调度在这两个队列中切换，如图1.1所示运行队列PCBi就绪队列PCBjPCBj1PCBj1阻塞队列PCBkPCBk1PCBk1图1.1PCB链表2）进程管理的流程图进程管理的流程图如图1.2所示，采取时间片原则来进行调度。图1.2 进程管理流程图2）运行结果，包括各个进程的运行顺序，每次占用处理机的运行时间，可以参考下列输出如图1.3图1.3 输出结果示意图3）每个进程运行时间随机产生，为120之间的整数。4）时间片的大小由实验者自己定义，可为3或5，优先级也可以随机产生。5）各进程之间有一定的同步关系（可选），注意进程状态转换的时机。任务2 存储管理系统设计一、课程设计目的使学生熟悉存储器管理系统的设计方法；加深对所学各种存储器管理方案的了解。二、课程设计内容采用一些常用的存储器分配算法，设计一个请求页式存储管理模拟系统并调试运行。三、课程设计指导（1） 通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成（可选，也可随机产生）： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；具体的实施方法是： 在0，319的指令地址之间随机选取一起点m； 顺序执行一条指令，即执行地址为m+1的指令； 在前地址0，m+1中随机选取一条指令并执行，该指令地址为m； 顺序执行一条指令，其地址为m+1; 在后地址m+2，319中随机选取一条指令并执行； 重复上述步骤，直到执行320次指令。（2） 将指令序列变成为页地址流 设： 页面大小为1k； 用户内存容量为4页到32页；用户虚量容量为32k。在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页（对应虚存地址为0，9）；第10条第19条指令为第1页（对应许存地址为10，19）； 第310条第319条指令为第31页（对应许存地址为310，319）；按以上方式，用户指令可组成32页。（3） 计算并输出下述各种算法在不同内存容量下的命中率 。先进先出的算法（FIFO）； 页面失效次数 命中率= 1 页地址流长度 在本次实验中，页地址长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不内存的次数。3随机数产生办法 关于随机数产生法，系统提供函数srand（）和rand（），分别进行初始化和产生随机数。例如： srand（）； 语句可初始化一个随机数； a0=10*rand（）/32767*320； a0=10*rand（）/32767*a0； 语句可用来产生a0与a1中的随机数。（4）请求页式管理的程序流程图如图2.1图2.1请求页式管理的程序流程图任务3 编程序模拟银行家算法一、课程设计目的通过设计和调试银行家算法通用程序，加深对死锁概念和死锁避免方法的了解。二、课程设计内容编制银行家算法程序，并检测所给状态的系统安全性。三、课程设计指导1）对用银行家算法来避免死锁的方法有较深入的了解，给出系统的初始状态，模拟避免死锁的动态过程。2）银行家算法中的数据结构（1）可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。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的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi，j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵存在如下关系： Needi,j= Maxi，j- Allocationi，j3）银行家算法设Requesti 是进程Pi的请求向量，如果Requesti，j=K,表示进程需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：（1）如果Requesti，j= Needi，j，便转向步骤（2）；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。（2）如果Requesti，j= Availablej，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej= Availablej- Requesti，j； Allocationi，j= Allocationi，j+ Requesti，j； Needi，j= Needi，j- Requesti，j；（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。4）安全性算法系统所执行的安全性算法可描述如下：（1）设置两个向量：工作向量Work：它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，在执行安全算发开始时，Work=Available；Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false；当有足够资源分配给进程时，再令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程：Finishi=false；Needi，j = Workj；若找到，执行步骤（3），否则，执行步骤（4）。（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj= Worki+ Allocationi，j； Finishi=true； go to step 2；（4）如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。5）银行家算法程序流程图如图3.1所示，银行家算法所用数据可参考ppt上的例子。图3.1银行家算法程序流程图任务4 磁盘调度算法的实现与分析一、课程设计目的使学生熟悉磁盘管理系统的设计方法；加深对所学各种磁盘调度算法的了解及其算法的特点。二、课程设计内容编程序实现下述磁盘调度算法，并求出每种算法的平均移动磁道数，并分析结果：先来先服务算法（FCFS）最短寻道时间优先算法（SSTF）扫描算法（SCAN）循环扫描算法（C-SCAN）三、课程设计指导1）进程请求访问磁盘的磁道数按时间随机产生，可假设磁盘总共有200个磁道，计算每种算法的平均移动磁道数。2）具体调度策略见参考文献（2）的161163页，产生不同的随机磁道数，计算平均寻道时间，再比较其性能的优劣。任务5 文件系统演示一、课程设计目的使学生熟悉文件管理系统的设计方法；加深对所学各种文件操作的了解及其操作方法的特点。二、课程设计内容设计一个简单的多用户文件系统。即在系统中用一个文件来模拟一个磁盘；此系统至少有：Create、delete、open、close、read、write等和部分文件属性的功能。实现这个文件系统。 能实际演示这个文件系统。基本上是进入一个界面（此界面就是该文件系统的界面）后，可以实现设计的操作要求。三、课程设计指导1）设计一个10个用户的文件系统，每次用户可保存10个文件，一次运行用户可以打开5个文件。2）程序采用二级文件目录（即设置主目录MFD）和用户文件目录（UFD）。另外，为打开文件设置了运行文件目录（AFD）。3）为了便于实现，对文件的读写作了简化，在执行读写命令时，只需改读写指针，并不进行实际的读写操作。4）因系统小，文件目录的检索使用了简单的线性搜索。5）文件保护简单使用了三位保护码：允许读写执行、对应位为 1，对应位为0，则表示不允许读写、执行。6）程序中使用的主要设计结构如下：主文件目录和用户文件目录（MFD、UFD），打开文件目录（AFD）即运行文件目录，如图5.1所示。AFD打开文件名打开保护码读写指针MDF用户名文件目录指针用户名文件目录指针UFD保护码文件长度文件名图5.1目录结构的设计参考的数据结构设计如下struct TYPE_UFD/用户文件目录string File_Name;/文件名boolRead;/读保护码，true为可读boolWrite;/写保护码，true为可写boolExecute;/执行保护码，true为可执行intLength_File;/文件长度;struct TYPE_MFD/主文件目录string User_Name;/用户名TYPE_UFD*Pointer;/用户文件目录指针;struct TYPE_AFD/打开文件目录intFile_ID;/打开的文件号boolRead;/读保护码，true为可读boolWrite;/写保护码，true为可写boolExecute;/执行保护码，true为可执行intPointer;/读写指针;7）文件系统结构如图5.2所示 wzq MFDUFDcattest图5.2文件系统总体数据结构图8）文件系统算法的流程图如图5.3所示。图5.3文件系统算法的流程图9）注意对于物理块的访问（包括访问指针，空闲位）需要经过输入输出，相当于通过定位对文件进行读写。打开文件目录（AFD）是在内存中，由打开文件时创建。教材及参考书目（1） 胡志刚，谭长庚等. 计算机操作系统.中南大学出版社. 2005（2） 罗宇，邹鹏等.操作系统(第2版). 电子工业出版社. 2007.4（3） 汤子瀛、哲凤屏、汤小丹. 计算机操作系统.西安电子科技大学出