操作系统课程设计指导书

1、操作系统原理课 程 设 计 指 导 书何静媛 编 写适用专业：计算机科学与技术网络安全信息工程重庆大学计算机学院2009年4月目 录课程设计1：存储管理子系统的设计与实现3课程设计2：模拟文件系统的设计与实现9课程设计3：设备管理功能的设计与实现14课程设计1：存储管理子系统的设计与实现一、课程设计目的通过本次课程设计所要达到的目的是：1、 加深学生对操作系统存储管理子系统基本原理的理解和掌握。2、 培养学生理论联系实际的设计思想，训练学生利用课程中的理论知识，结合程序开发技术，提高知识的综合应用能力。3、 强化面向对象的程序设计思想，加强学生的编码实现能力。二、课程设计内容本次课程设计要求学

2、生编程模拟实现操作系统的存储管理功能。具体要求包括：1、包括模拟演示分页管理和段页式管理的基本思想和功能；2、模拟动态地址重定位过程；3、实现存储空间的分配和回收算法。三、课程设计原理、方法和手段课程设计原理:（一）、在进行分页存储管理功能设计时，可以设定每个进程在执行之前，只能装入m个页面，其余的页面需要的时候发出请求调页的缺页中断，进行动态调入。说明 a)、页表为了装入一个页面而必须调出一页时，如果被选中调出的页面在执行过程中没有修改，则不必把该页重新写回到磁盘上，因此页表中需要增加修改标志属性，若该页已经被修改，则访问标记置为“1”；否则该标记置为“0”。 假定主存的每块长度为1024个

3、字节。现有一个共7页的作业，其副本已经在磁盘上。系统为该作业分配了4个主存块，且该作业的第0页第3页已经装入主存。该作业的某时刻的页表如表1.1所示：表1.1 页表页号内/外存标志主存块号修改标志在磁盘上的位置0151011118101221900133110021400225002360121b)、指令序列为了测试程序执行的正确性，可自行假定作业依次执行的指令序列（仅模拟执行，不必考虑每个指令的具体操作）。这些指令序列组织可见表1.2所示：表1.2 指令序列表操作页号页内地址操作页号页内地址+0070移位4053+1050+5023*2015存1037-3021取2078存0056+4001

4、取6040存6084c)、地址转换与缺页中断设计一个地址转换程序来模拟硬件的地址转换和缺页中断。如果访问的页在主存，则形成绝对地址，但不去模拟指令的执行，可用输出转换后的绝对地址来表示一条指令已经完成。如果访问的页不在主存，则产生一次缺页中断。d)、模拟页面淘汰调度算法本设计要求实现FIFO调度算法或LRU调度算法。对于FIFO算法，总是先调出最先进入主存的那一页，因此可以用一个数组来构成页号队列。数组的元素是已经在主存中的页面号。根据上例中的假定，允许使用的主存块为4，且开始的4页已经装入主存，则数组可由4个元素组成：P0, P1, P2, P3.它们的初值为: P0:=0, P1:=1,

5、P2:=2, P3:=3用一指针k指示：当要装入新页时，应调出的页再数组中的位置，k的初始值为0。当产生缺页中断后，操作系统总是选择Pk所指出的页面调出，然后执行： Pk:=要装入的新页页号 k:=(k+1) mod 4在实验中，不必真正启动磁盘去执行调出一页和装入一页的工作，而只需要输出一行字串来表示一次调出和装入的过程。如果要使用LRU调度算法，可以考虑将其进行简化，如选择最少使用的页面进行淘汰，可以考虑在页表中增加一个“访问计数”属性，该属性记录进程对该页的访问次数。当进程访问某页时，需要将访问计数的数值加1。在选择淘汰页面，则选择访问计数数值最小的页面淘汰。（二）模拟实现段页式存储管理

6、功能，对于每个进程，规定需要将虚空间的一个段的m个虚页调入到内存中。其余的虚页按照缺页中断请求的方式调入。说明a)、段表与页表段页式存储管理中的页表与页式存储管理机制中的页表可做相同的设置。二者不同之处在于前者每个段都需要一张页表，而后者每一个进程需要一张页表即可。段页式存储管理机制中，每个进程需要一张段表。其段表的设置见表1.3：表1.3 段表段号页表长度页表起始地址内/外存标志修改标志b)、地址转换段页式存储管理方法的地址变换机构比单纯的页式管理要复杂。在设计地址转换的程序时，需要将逻辑地址表示成三维的结构，如段号，页号，页内地址，如果访问的页在主存，则计算出绝对地址，并输出转换后的绝对地

7、址来表示一条指令已经完成。如果访问的页不在主存，则产生一次缺页中断。c)、其它关于测试指令的设计与页面淘汰调度算法的实现请参照页式存储管理中的说明。关于段的淘汰，我们可假设每个进程只能调入一个段在内存中，故若需要调入新段，则置换当前段即可。（3）设计流程图I、页式存储管理中的地址转换、缺页中断及页面调度可参考流程图1.1：是是j:=Pk输出“页面j写回交换区”Pk:=X;k:=(k+1)mod 4修改页表该页的修改标志=1？结束形成绝对地址是否“存”指令？置该页的修改标志为1输出绝对地址有后继指令吗？开始取一条指令指令中访问的页号保存到X中中查页表该页标志=1？取下一条指令否（产生缺页中断）

8、是否否否是模拟硬件地址转换模拟FIFO页面调度图1.1 页式存储管理流程图II、段页式存储管理中的地址转换、缺页中断及页面调度可参考流程图1.2：否j:=Pk输出“页面j写回交换区”Pk:=X;k:=(k+1)mod 4修改页表该页的修改标志=1？模拟硬件地址转换否（缺页中断） 否是否取下一条指令结束是开始取一条指令段号存入X中；页号存入Y中中查段表De 该段是否在内存？根据段号X，读出对应的页表查页表De 根据页号Y查页表De 该页是否在内存？有后继指令吗？是置该段与该页的修改标志为1输出绝对地址是否“存”指令？形成绝对地址是否（产生缺段中断） 调入段X输出“当前内存段写回交换区”修改段表该

9、段的修改标志=1？是否图1.2 段页式存储管理流程图四、设计组织运行要求设计采取集中授课与集中上机的形式。五、课程设计条件上机环境要求安静，一人一机。操作系统平台为windows2000及以上版本，安装java编译器及相关运行环境；安装C+运行环境（Visual C+）等。课程设计主要参考文献资料有：1计算机操作系统教程（第3版），张尧学，史美林，张高编著，清华大学出版社。2Linux操作系统教程，刘胤杰，岳浩等编著，机械工业出版社。3UNIX操作系统教程，张红光，李福才等编著，机械工业出版社。4操作系统，谭耀铭主编，中国人民大学出版社。六、课程设计步骤 （1）、复习巩固所需要使用的编程语言的

10、语法规则以及相关知识。 （2）、理解操作系统页式存储管理、段页式存储管理机制的思想。 （3）、编写程序实现存储管理的功能。对于步骤（3）需要学生自行设计方案并加以实现。七、思考题 暂无。八、课程设计报告设计完成后，需要书写课程设计报告，报告格式参见重庆大学课程设计报告册。九、其它说明课程设计分小组进行，学生可自由组合，2-3人为一个小组，分工合作完成课程设计任务。课程设计2：模拟文件系统的设计与实现一、课程设计目的通过本次课程设计所要达到的目的是：1、 加深学生对操作系统文件系统理论知识的理解和掌握。培养学生理论联系实际的设计思想和独立思考、解决问题的能力。2、 强化面向对象的程序设计思想，加

11、强学生的编码实现能力。3、 设计所需知识涉及操作系统原理、软件开发工程、语言编程技术、数据结构等课程，通过本次设计可促进学生对知识的融会贯通，极大地提高学生对所学知识的综合应用能力。4、 由于本次设计需要学生按照2-3人自由组合成小组，因此可以促进学生的团体意识和协作开发的能力。二、课程设计内容本次设计要求学生编程模拟实现操作系统的文件管理系统的如下基本功能：1、实现文件的创建、查询、删除、修改、更名、拷贝等基本功能；2、文件系统采用多级目录机制，实现目录的创建、删除、显示、目录之间的切换。3、采用位示图来管理文件系统空间的分配和回收、提供位示图的查看功能。4、实现文件的有关权限管理。三、课程

12、设计原理、方法和手段 说明：（1） 文件的逻辑结构 在模拟文件系统功能时，为了简化，可以假设所有文件均为字符流的无结构文件，因此无须建立专门的逻辑结构管理机制。若文件较大，如果一个物理块不能全部存储，则可存入多个物理块，此时，需要将其按照字节数目平均划分成多个逻辑块。每个块的大小可以自由设定。（2）文件的物理结构文件的物理结构是对硬盘空间上文件存放的描述，它对一般用户是透明的，这样方便了用户的操作。文件的物理结构有三种常见的三种方式：连续结构、串联（链接结构）与索引结构。每种物理结构都有一定的适用范围，若文件本身是字符流式的无结构文件，可以限制文件的大小，采取连续结构的方式进行存储。在这里有一

13、点需要强调：该设计是在内存中模拟文件系统的功能，所有的文件都是建立在内存中，不与硬盘发生任何联系（即程序结束后，所有在程序运行过程中创建的文件及目录全部消失）。（3）模拟文件系统磁盘空间的管理可使用位示图法来模拟磁盘空间的管理，具体实现可根据喜好设计，下面举例说明位示图的设计思想：若要模拟windows操作系统多磁盘空间的管理，可在内存中申请了256128Bytes的空间作为该文件系统的硬盘，整个硬盘共划分为256个物理块，每块大小为128Bytes。整个模拟的硬盘空间可平均分为四个区，即磁盘C、磁盘D、磁盘E、磁盘F，每个分区有64个物理块。所有文件的操作都是在这块内存空间中进行的。对于这块

14、内存空间，可以使用一个16行16列的位示图来表示空闲块的分配和回收。如图2.1所示，图中的每位表示一个物理块，其值为“1”表示该块已经分配，否则表示该块未分配。15201C盘D盘E盘F盘 图2.1 磁盘空间位示图通常可以用一个字符类型的二维数组bitmapi,j来描述位示图。可假设位示图的第(ij)位为”Y”则代表没有分配，如果为”N”则代表已经分配。在文件建立与写入的时候，又文件系统自动地去查找位示图，与给文件分配空间。删除文件时，将对应的位重新置为”Y”，以便下次再分配给其它文件。(4)关于文件系统中基本数据结构的说明可以使用索引节点来记录文件信息，文件系统中的每个文件对应着一个索引节点。

15、索引节点中包含了文件的基本说明信息，如：文件的长度、创建及修改时间、权限、所属关系、磁盘中的位置等信息。文件系统中的所有文件（或目录）可以通过索引节点表来维护。每个文件或目录都与索引节点数组中的唯一一个元素对应。关于索引节点，可使用下面的结构来描述：typedef struct char NodeType;/索引节点类型，标识该节点为普通节点还是目录节点。 char FileName10; /文件名或目录名 INODE *Parent; /父节点索引节点号INODE *child_IndexNumber;/子接点的索引节点号数组int blockid;/文件内容所在物理块的 int size;

16、/文件大小 char timestamp10/文件创建时间 char owner10/文件所有者 ；INODE; 普通文件与目录都可以用一个INODE结构来表示；当该节点为普通文件时，child_IndexNumber域为空；当节点是目录时，blockid域可为空；文件系统中的索引节点通过自身的指针链接形成了一棵树形结构。通过对树形结构的搜索，可以按照文件名实现高效率的存取。（5）总体设计文件系统功能的总体结构图可大致描述如下：主控模块目录管理文件管理磁盘空间管理创建文件夹删除文件夹创建文件删除文件修改文件打开文件位示图查询文件拷贝图2.2系统功能结构图在图2.2的结构图中展示的功能是根据实验

17、基本要求设定的，学生可以在此基础上进行功能的拓展。 四、设计组织运行要求设计采取集中授课与集中上机的形式。五、课程设计条件上机环境要求安静，一人一机。操作系统平台为windows2000及以上版本，安装java编译器及相关运行环境；安装C+运行环境（Visual C+）等。课程设计主要参考文献资料有：1计算机操作系统教程（第3版），张尧学，史美林，张高编著，清华大学出版社。2Linux操作系统教程，刘胤杰，岳浩等编著，机械工业出版社。3UNIX操作系统教程，张红光，李福才等编著，机械工业出版社。4操作系统，谭耀铭主编，中国人民大学出版社。六、课程设计步骤 （1）、复习巩固所需要使用的编程语言的

18、语法规则以及相关知识。 （2）、理解操作系统中文件管理子系统的基本思想。 （3）、编写程序实现文件系统的功能。对于步骤（3）需要学生自行设计方案并加以实现。七、思考题 暂无。八、课程设计报告设计完成后，需要书写课程设计报告，报告格式参见重庆大学课程设计报告册。九、其它说明课程设计分小组进行，学生可自由组合，2-3人为一个小组，分工合作完成课程设计任务。课程设计3：设备管理功能的设计与实现一、课程设计目的通过本次课程设计教学所要达到的目的是：1、通过课程设计，加深我们对了解有关设备申请、避免死锁等概念，并加深我们对银行家算法理解。提高了我们分析、解决问题的能力。2、 强化面向对象的程序设计思想，

19、加强学生的编码实现能力。3、设计所需知识涉及操作系统原理、软件开发工程、语言编程技术、数据结构等课程，通过本次设计可促进学生对知识的融会贯通，极大地提高学生对所学知识的综合应用能力。4、由于本次设计需要学生按照2-3人自由组合成小组，因此可以促进学生的团体意识和协作开发的能力。二、课程设计内容本次课程设计要求学生编程模拟实现操作系统的设备管理模块的如下基本功能：1、实现设备的添加、删除和修改等功能。2、实现设备独立性,即设备内部的管理（对设备的命名、分配等）对用户透明。3、使用银行家算法模拟设备分配的过程。三、课程设计原理、方法和手段课程设计原理:说明：1、银行家算法思想为了避免死锁方法中允许

20、进程动态地申请设备，系统在进行设备分配之前，应先计算此次分配设备的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。银行家算法是避免死锁的一种重要方法，为实现银行家算法，系统必须设置若干数据结构。这些数据结构包括： 1）可利用设备向量Available这是个含有m个元素的数组，其中的每一个元素代表一类可利用的设备数目。如果Availablej=K，则表示系统中现有Rj类设备K个。 2）最大需求矩阵Max这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类设备的最大需求。如果Maxi,j=K，则表示进程i需要Rj类设备的最大数目为K。3）分配矩阵Allocation这也是一个

21、nm的矩阵，它定义了系统中每一类设备当前已分配给每一进程的设备数。如果Allocationi,j=K，则表示进程i当前已分得Rj类设备的数目为K。4）需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类设备数。如果Needi,j=K，则表示进程i还需要Rj类设备K个，方能完成其任务。 Needi,j=Maxi,j-Allocationi,j 设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的设备。当Pi发出设备请求后，系统按下述步骤进行检查：a、如果RequestijNeedi,j，便转向步骤b；否则认为出错，因为它所需要的设备数

22、已超过它所宣布最大值。b、如果RequestijAvailablej，便转向步骤c；否则，表示尚无足够设备，Pi须等待。 c、系统试探着把设备分配给进程Pi，并修改下面数据结构中的数值：Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;d、系统执行安全性算法，检查此次设备分配后，系统是否处于安全状态。若安全，才正式将设备分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的设备分配状态，让进程Pi等待。2、安全性算法简介1）设置两个向

23、量：工作向量Work: 它表示系统可提供给进程继续运行所需的各类设备数目，它含有m个元素，在执行安全算法开始时，Work=Available; 工作向量Finish: 它表示系统是否有足够的设备分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够设备分配给进程时， 再令Finishi=true。 2）从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj；若找到，执行 3)，否则，执行 4)3）当进程Pi获得设备后，可顺利执行，直至完成，并释放出分配给它的设备，故应执行：Workj=Worki+Allocationi,j;Fin

24、ishi=true;go to step 2); 4）如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态3、设备独立性的实现现代计算机系统常常配置许多类型的外围设备，同类设备又有多台，尤其是多台磁盘机，磁带机的情况很普遍。作业在执行前，应对静态分配的外围设备提出申请要求，如果申请时指定某一台具体的物理设备，那么分配工作就很简单，但当指定的某台设备有故障时，就不能满足申请，该作业也就不能投入运行。例如系统拥有A、B两台卡片输入机，现有作业J2申请一台卡片输入机，如果它指定使用A，那么作业J1已经占用A或者设备A坏了，虽然系统还有同类设备B是好的且未被

25、占用，但也不能接受作业J2，显然这样做很不合理。为了解决这一问题，通常用户不指定特定的设备，而指定逻辑设备（即：），使得用户作业和物理设备独立开来，再通过其它途径建立逻辑设备和物理设备之间的对应关系，我们称这种特性为“设备独立性”。具有设备独立性的系统中，用户编写程序时使用的设备与实际使用的设备无关，亦即逻辑设备名是用户命名的，是可以更改的；物理设备号是系统规定的，是不可更改的。在本次实验中，设计者可以使用设备类表与设备表来实现设备独立性机制，如表3.1与表3.2所示：表3.1 设备类表 表3.2 设备表设备类拥有的总台数现存台数设备表始地址打印机11输入机21绝对号是否分配占用作业名相对号001否002是J1001003否 表3.2中的相对号是用户在使用设备时给出的逻辑设备名的一部分，这个值在设备真正分配给请求的进程时才动态地添加到设备表中，这样就构成逻辑设备名与物理设备之间的对应关系。在具体编程