操作系统实验指导书06586

1、操作系统实验指导书20-12-23前言操作系统是计算机系统中一个重要的组成部分，是最重要的一门系统软件，同时也是最活跃的学科之一，其发展极为迅速。其出现在50年代末，至今已有四十余年的历史了，在计算机系统中，已是一个发展较成熟的分支。但是随着计算机科学技术的迅速发展，计算机应用领域的不断扩展，现有的操作系统仍然不能满足需要，因此迫切需要新的操作系统来替换旧的操作系统。这一工作毫无疑问应落到从事计算机专业的设计人员身上，因此作为计算机专业的学生，操作系统是一门重要的专业、必修、基础课程之一，掌握其理论和工作原理是至关重要的，当然了解其设计方法和思想也是不可缺少的。实验环节是计算机专业学生学习的必

2、要途径，特别是对操作系统原理这门课程更为重要了，众所周知操作系统原理内容深刻、概念抽象，难以理解。操作系统的开发是一个大型的工作，且开发的时间也是漫长的。作为教学，在有限的时间内开发一个完整的操作系统是不现实的，因此只能按照操作系统的功能，让学生做一些模拟小实验，来了解操作系统的开发方法和设计思路，了解其开发难度，为今后从事这一方面工作打下基础。本指导书是在配合课堂教学的同时，使得学生正确掌握概念、在了解操作系统的一般工作原理基础上使之有效地学好操作系统原理这门课。同时也是为锻炼学生的软件设计能力的一个好机会，进一步掌握软件开发方法的一个好途径，本实验是在WINDOWS环境下，用C语言编程。要

3、求操作系统实验是在计算机专业机房、单机运行、WINDOWS操作系统环境下，用C语言或其它高级语言实现的，因此实验的总要求如下：1、 遵守机房纪律，服从机房管理；2、 努力准备上机内容，并预先作一些情况分析3、 认真编码、测试、观察上机现象，记录测试中出现的问题及今后可能出现的问题，并记录一些主要情况。4、 认真书写实验报告。实验报告应包括实验目的、要求、程序框图、程序清单、运行情况、运行结果、分析意见。在程序清单中主要部分必须加以注释。实验一、进程管理设计一、 实验目的：通过进程的创建和控制的设计来达到如下目的：1、 加深对进程概念的理解，明确进程和程序的区别；2、 进一步认识并发执行的概念，

4、区别顺序执行和并发执行；3、 分析进程争用临界资源的现象，学习解决进程互斥的方法；二、 实验内容：（一）在UNIX环境下实验：1、 进程的创建编写一段程序，创建两个子进程，当此程序运行时，在系统中有一个父进程和两个子进程活动。让每一个进程在屏幕上显示一个字符：父进程显示字符“a”；子进程分别显示字符“b”和“c”。试观察显示在屏幕上的结果，并分析原因。 2、 修改已编写的程序，将每个进程输出一个字符改为每个进程输出一句话，再观察程序执行时屏幕上出现的现象，并分析原因。如果在程序中使用系统调用Lockf（）来给每一个进程加锁，可以实现进程之间的互斥，观察并试分析出现的现象。（二）在WINDOWS

5、环境下模拟实验：1、 用C语言编写一程序，来模拟进程的创建和撤消，要求通过终端键盘输入三、四作业的名称、大小、优先级等。系统为它创建进程，并把进程控制块PCB的内容送到终端显示器上输出。2、 同时模拟内存空间为作业分配内存空间，并把结果用图形形象地表示出来，同样通过终端输出。3、 按进程的优先级的顺序撤消进程，同时通过终端显示PCB的撤消过程和内存的释放过程。实验二、进程调度一、实验目的：在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的进程调度，帮助学生加深了解处理器调度的工

6、作。二、 实验内容：从下面两个调度算法中，选择一个调度算法来实现进程调度：1、 优先数调度算法；2、 时间片轮法调度算法三、 提示：1、 按优先数调度算法：（1）假定系统中有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：进程名指针要求运行时间优先数状态其中：进程名作为进程的标识，假设五个进程的进程名分别为P1，P2，P3，P4，P5。指针按优先数的大小把五个进程；连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“NULL”。要求运行时间假设进程需要运行的单位时间数优先数赋予进程的优先数，调度时总是选取优先数大的进程先执行。状态可假设有两种状态，

7、“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“R”表示；当一个进程运行结束后，它的状态为“结束”状态，用“E”表示。（2）在每次运行你所设计的处理器高度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。（3）为了高度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。例：队首标志K2 K1K2K3K4K5P1P2P3P4P50K4K5K3K12312415342RRRRR PCB1 PCB2 PCB3 PCB4 PCB5（4）处理器高度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实

8、习是模拟处理器高度，所以，对被选中的进程并不实际的启动运行，而是执行：优先数-1要求运行时间-1 来模拟进程的一次运行。提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。（5）进程运行一次后，若要求运行时间0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间=0，则把它状态修改成“结束”（E），且退出队列。 （6）若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。 （7）在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程

9、名以及运行一次后进程队列的变化。 （8）为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器高度程序，显示或打印逐次被选中的进程的进程名以及进程控制块的动态变化过程。2、 按时间片轮转法高度算法：（1） 系统有五个进程，每一个进程用一个进程控制块PCB来代表。进程控制块的格式为： 进程名指针要求运行时间已运行时间状态其中：进程名作为进程的标识，假设五个进程名分别为Q1，Q2，Q3，Q4，Q5。 指针进程按顺序排成循环队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。要求运行时间假设进程需要运行的单位时间数已运行时间假设进程已经

10、运行的单位时间数，初始值为“0”。 状态有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示；当一个进程运行结束后，它的状态为“结束”，用“E”表示。（2） 次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。（3） 把五个进程按顺序排成循环队列，用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。例如：当前轮到P2执行，则有：标志单元K2 K1K2K3K4K5Q1Q2Q3Q4Q5K2K3K4K5K12312410000RRRRR PCB1 PCB2 PCB3 PCB4 PCB5（4） 处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器（进

11、程）调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行： 已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位时间。请同学们注意：在实际的系统中，当一个进程被选中时，必须置该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片。这些工作在这里省去。（5） 进程运行完一个时间片，已运行时间+1，改标志单元的数据，若要求运行时间，则把它的状态改成“结束”（E），且退出队列。（6） 若“就绪”队列不为空，则重复上面（4）、（5），直到所有进程都处在“结束”状态，“就绪”队列为空。（7） 在所设计的程序中应有显示或打印语句，能显示或打印

12、每次被选中的进程名以及运行一次后进程队列的变化。（8） 为五个进程任意确定一组“要求运行时间”，启动所设计的进程调度程序，显示逐次被选中的进程名及进程控制块的动态变化过程。实验三、存储器管理一、 实验目的：一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生

13、理解在不同的存储管理方式下怎样实现主存的分配和回收。二、 实验内容：从下两种存储管理方式的主存分配和回收中，选择一种管理方式来实现本次实验任务：1、在可变分区管理方式下，采用最先适应算法。2、在分页式管理方式下，采用位示图来表示主存的分配情况和回收情况。三、 提示：1、 在可变分区管理方式下，采用最先适应算法实现主存的分配与回收。（1） 可变分区方式是按作业管理的主存空间大小来分割分区。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入，撤离，主存空间被分成许多个分区，有的分区被作业占用，而的分区是空

14、闲的。例如：操作系统作业1作业3空闲区作业2空闲区为了说明哪些区是空闲的，可以用来装入新的作业，必须要有一张空闲区说明表，格式如下：起址长度状态14K12K未分配32K96K未分配空表目空表目其中：起址指出一个空闲区的主存起始地址。长度指出从起始地址开始的一个连续空闲区的长度。状态有两种状态，一种是“未分配”状态，指出对应的、由起址指出的某个长度区是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤后，它占的区域就成了空闲区，应找一个“空表目”栏登记归还的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目

15、”的登记栏目，否则造成表格“溢出”无法登记。上述的这张说明表的登记情况是按提示（1）中的例所装入的三个作业占用的主存区域后填写的。（2） 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲可能大于作业需要量，这应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存在高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其他地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。（

16、3） 采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。 由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图41。（4） 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示（1）中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲

17、区登记在空闲区说明表中。归还主存时的回收算法如图42。（5） 请按最先适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存，然后作业3撤离；再作业2撤离。请你为它们进行主存分配和回收，把空闲说明表的初值以及每次分配或回收后的变化显示出来或打印出来。2、 在分页式管理方式下，采用位示图来表示主存的分配情况和回收情况。（1）分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未

18、分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。（2）假设某系统的主存被分成大小相等的64块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31共10个主存块被占用了，那么位示图情况如下：位数字节号01234567011004440101010100200000000310000001400000000500000000600000000700000000 开始j：=0j：=j+1查看空闲区说明表的第j个登记栏状态为“未分配”吗？申请xk主存区输出分配情

19、况长度：=长度-xk；起址：=起址+xk；置状态为“空表目”长度xk吗？j为空闲区说明表的最末一栏吗？结束输出作业不能装入 否 否 是 是 图41最先适应分配模拟算法开始结束L：=归还区长度S：=归还区起址查空闲区说明表把下邻空闲区登记栏中状态置成“空表目”找一“空表目”栏登记始址：=S，长度：=L状态：=“未分配 ”L：=L+下邻空闲区长度把下邻空闲区登记栏中始址：=S，长度：=L按地址顺序调整和紧缩空闲区说明表上邻空闲区登记栏中长度增加L有与归还区下邻的空闲区？有与归还区上邻空闲区？有与归还区上邻空闲区？ 无 有无 有 有 无图42主存回收算法（1） 当要装入一个作业时，根据作业对主存的需

20、要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功；若能满足则查位图，找出“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。按找到的计算出对应的块号，其计算公式为：块号=j*8+i其中：j表示找到的是第j个字节，i表示对应的是第i位根据分配给作业的块号，为作业建立一张页表，页表格式：页号块号012（2） 当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块，归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：字节号j=块号/8（

21、表示取整）位数i=块号/8（表示取余）（3） 设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（格式如（3）所述）。然后假定有另一作业执行结束，它占用的块号为第4、5、6、31块，运行你所设计的回收程序，收回作一归还的主存块。要求能显示或打印分配和回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。实验四、设备管理一、 实验目的：磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或已经建立在磁盘上的文件删去，这

22、就涉及到磁盘存储空间的分配和回收。一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、链接文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过本实验使学生掌握磁盘存储空间的分配和收回算法。二、 实验内容：模拟磁盘空闲空间的表示方法，以及模拟实现磁盘空间的分配和回收。从下题目中选择一题来实现设备的管理：（1） 连续的磁盘存储空间的分配和回收。（2） 用位示图管理磁盘存储空间。（3）模拟UNIX系统的空闲块组链接法，实现磁盘存储空间的管理。三、 提示：1、 连续

23、的磁盘存储空间的分配和回收：（1） 要在磁盘上建立顺序文时，必须把按序排列的逻辑记录依次存放在磁盘的连续存储空间中。可假定磁盘初始化时，已把磁盘 存储空间划分成若干个等长的块（扇区），按柱面号和盘面号的顺序给每一块确定一个编号。随着文件的建立、删除、磁盘存储空间被分成许多区（每一区包含若干块），有的区存放着文件，而有的区的空闲的。当要建立顺序文件时必须找到一个合适的空闲区来存放文件记录，当一个文件被删除时，则该文件占用的区应成为空闲区。为此可用一张空闲区表不记录磁盘存储空间中尚未占用的部分，格式如下：序列起始空闲块号空闲块个数状态156未分配2143未分配32130未分配4空表目（2） 要建立

24、文件时，先查找空闲区表，从状态为“未分配”的登记栏目中找出一个块数能满足要求的区，由起始空闲块号能依次推得可使用的其它块号。若不需要占用该区的所有块时，则剩余的块仍应为未分配的空闲块，这时要修改起空闲块号和空闲块数。若占用了该区的所有块，则相应登记栏中的状态修改成“空表目”，删除一个文件时，从空闲区表中找一个状态为“空表目”的登记栏目，把归还的起始块号和块数填入对应的位置。磁盘存储空间的分配和回收算法类似于主存储器的可变分区方式的分配和回收。同学们可参考上一实验的第一题。（3） 当找到空块后，必须启动磁盘把信息存放到指定的块中，启动磁盘必须给出由三个参数组成的物理地址：柱面号、磁道号和物理记录

25、号。故必须把找到的空闲块号换算成磁盘的物理地址。为了减少移臂次数，磁盘上的信息按柱面上各磁道顺序存放。现假定一个盘组共有200个柱面，（编号0199）每个柱面有20个磁道（019，同一柱面上的各磁道分布在各盘面上，故磁道号即盘面号。），每个磁道被分成等长的6个物理记录（编号05，每个盘面被分成若干个扇区，故每个磁道上的物理记录号即为对应的扇区号。）。那么，空闲块号与磁盘物理地址的对应关系如下： 假设M=空闲块号/6，m=空闲块号/6 则物理记录号=m 磁道号=M/20，柱面号=M/20（4） 删除一个文件时，从文件目录表中可得到该文件在磁盘上的起始地址和逻辑记录个数，假定每个逻辑记录占磁盘上的

26、一块，则可推算出归还后的起始空闲块号和块数，登记到空闲区表中。换算关系如下：起始空闲块号=（柱面号*20+磁道号）*6+物理记录号空闲块数=逻辑记录数（5） 请设计磁盘存储空间的分配和回收程序，要求把分配到空闲块转换成磁盘物理地址，把归还的磁盘空间转换成空闲块号 假定空闲区表的初值如提示（1）中指出，现有一文件要占用10块，运行你所设计的分配程序，显示或打印分配后的空闲区表以及分配到的磁盘空间的起始物理地址。然后，有一文件被删除，它占用的磁盘空间为：1号柱面2号磁道，0号物理记录开始的4块，运行你所设计划的回收程序，显示或打印回收后的空闲区表。2、用位示图管理磁盘存储空间的分配和回收：（1）为

27、了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。位示图的形式与上一实验中的位示图一样，但要注意，对于主存储空间和磁盘存储空间应该用不同的位示图来管理，绝不可混用。（2）申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。假设现在有一个盘组共80个柱面，每个柱面有两个磁道，每个磁道分成4个物理记

28、录。那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为： 柱面号=字节号 磁道号=位数/4 物理记录号=位数/4（3）归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位，把该位置成“0”。按照（2）中假设的盘组，归还块在位示图中的位置计算如下： 字节号=柱面号 位数=磁道号*4+物理记录号（4）设计申请一块磁盘空间和归还一块磁盘空间的程序。要求能显示或打印程序运行前和运行后的位示图；分配时把分配到的磁盘空间物理地址显示或打印出来，归还时把归还块对应于位示图的字节号和位数显示或打印出来。（5）假定已有如表61磁盘空间被占用了，现在要申

29、请五块磁盘空间，运行分配程序，按（4）中要求显示或打印运行的结果。然后再归还如表62的空间，运行回收程序，按（4）中的要求显示或打印运行结果。柱面号磁道号物理记录号001002010013100112表61柱面号磁道号物理记录号002010101表623、模拟UNIX系统的空闲块成组链接法，实现磁盘存储空间的管理：（1）假定磁盘存储空间已被划分成长度n的等长块，共有M块可供使用。UNIX系统中采用空闲块成组链接的方法来管理磁盘存储空间，将磁盘中的每N个空闲块（NM）分成一组，最后一组可以不足N块，每组的第一块登记了下一组空闲块的块数和块号，第一组的块数和块号登记在专用块中，登记的格式如下：空闲

30、块数K空闲块号1空闲块号2空闲块号K当第一项内容为“0”时，则第二项起指出的空闲块是最后一组。（2）现模拟UNIX系统的空闲块成组链接，假定共有8块可供使用，每3块为一组，则空闲块成组链接的初始状态为： A0 A1 A43456 308713 32专用块 A2 A5 A7 A3 A6 A8 开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，空闲块的链接就未必按序排列了。 用二维数组AMN来模拟管理磁盘空间，用Ai表示第i块，第0块A0作为专用块。（3）成组链接的分组情况记录在磁盘物理块中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复到主存中，定义一个数组MA存放专用块内容，即MA=A0。申请一块磁盘空间时，查MA，从中找出空闲块号，当一组空闲块只剩第一块时，则应把该块中指出的下一组的空闲块数和块号复制