操作系统应用设计实验指导.doc

1、操作系统应用设计实验指导前 言操作系统是计算机系统的核心，操作系统课程是计算机科学与技术专业的重要必修课。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。操作系统应用设计是操作系统课程的重要组成部分，属于学科基础实验范畴。作为与相关教学内容配合的实践性教学环节，应在操作系统理论课教学过程中开设。操作系统是计算机科学与技术专业、软件工程等专业必修的专业基础课程，其配套实验课操作系统应用设计的作用是：理解操作系统的设计和实现思路，掌握典型算法。学生应具有高级语言编程能力、具有数据结构等基础知识。操作系统应用设计实

2、验指导共有六个实验项目。其中，实验一是处理器调度实验；实验二是银行家算法模拟；实验三是分区存储管理算法模拟；实验四是分页存储管理算法模拟；实验五是请求页式存储管理算法模拟；实验六是磁盘存储空间的分配和回收。这本操作系统应用设计实验指导书是在近几年来的教学实验基础上编写的。参考了有关操作系统实验的实验指导，在此向有关编者表示感谢，同时本指导书仅供内部学生学习使用。由于时间仓促，编者水平有限，不足之处在所难免，恳请读者批评指正。 编 者 张莉 二0一三年四月目 录实验一 处理器调度实验1实验二 银行家算法模拟5实验三 分区存储管理算法模拟8实验四 分页存储管理算法模拟12实验五 请求页式存储管理算

3、法模拟14实验六 磁盘存储空间的分配和回收16附 录22一 参考实例22二 实验报告格式42操作系统应用设计实验指导实验一 处理器调度实验实验内容：选择一个调度算法，实现处理器调度。实验目的：在采用多道程序设计的系统中，往往若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定那些进程优先占有处理器。本实习模拟在单处理器情况下的处理器调度，加深了解处理器调度的工作。实验题目：本实验有两题，可任选一题。第一题：设计一个按优先数调度算法实现处理器调度的程序。提示：(1) 假定系统有5个进程，每个进程用一个PCB来代表。PCB的格式为：进程名、指针、要求运行时间、优先数、

4、状态。进程名P1P5。指针按优先数的大小把5个进程连成队列，用指针指出下一个进程PCB的首地址。要求运行时间假设进程需要运行的单位时间数。优先数赋予进程的优先数，调度时总是选取优先数大的进程先执行。状态假设两种状态，就绪，用R表示，和结束，用E表示。初始状态都为就绪状态。如图1.1所示。进程名指针要求运行时间优先数状态图1.1 进程控制块结构(2) 每次运行之前，为每个进程任意确定它的“优先数”和“要求运行时间”。(3) 为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。例如，当前轮到P2执行，则如下图1.2所示。 队首标志 K2 K1P1

5、 K2P2 K3P3 K4P4 K5P50K4K5K3K12312415342RRRRRPCB1PCB2PCB3PCB4PCB5图1.2 PCB队列(4) 处理器总是选队首进程运行。采用动态改变优先数的办法，进程每运行1次，优先数减1，要求运行时间减1。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：优先数-1要求运行时间-1来模拟进程的一次运行。提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。(5) 进程运行一次后，若要求运行时间不等于0，则将它加入队列（按优先数大小

6、插入，且置队首标志）；否则，将状态改为“结束” （E），退出队列。(6) 若就绪队列为空，结束，否则，重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。(8) 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。第二题：设计一个按时间片轮转法实现处理器调度的程序。提示：(1)假定系统有5个进程，每个进程用一个PCB来代表。PCB的格式为：进程名、指针、要求运行时间、已运行时间、状态。进程

7、名Q1Q5。指针按创建时间把5个进程连成队列，用指针指出下一个进程PCB的首地址。要求运行时间假设进程需要运行的单位时间数。已运行时间假设进程已运行的单位时间，初始值为0。状态假设两种状态，就绪，用R表示，和结束，用E表示。初始状态都为就绪状态。如图1.3所示。进程名指针要求运行时间已运行时间状态图1.3 进程控制块结构(2) 每次运行之前，为每个进程任意确定它的“要求运行时间”。(3) 把五个进程按顺序排成循环队列，用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。例如，当前轮到Q2执行，则如下图1.4所示。标志单元 K2 K1Q1 K2Q2 K3Q3 K4Q4 K5Q5K2K3K4

8、K5K12312410000RRRRRPCB1PCB2PCB3PCB4PCB5图1.4 PCB队列(4) 处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。请同学注意：在实际的系统中，当一个进程被选中运行时，必须置上该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片。在这时省去了这些工作，仅用“已运行时间+1”来表示进程已经运行满一个时间片。(5) 进程运行一次后，应把该进程的进程控制块中的指针值送到

9、标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（E）且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。(6) 若“就绪”状态的进程队列不为空，则重复上面的（4）和（5）的步骤，直到所有的进程都成为“结束”状态。(7) 在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化。(8) 为五个进程任意确定一组“要求运行时间”，启动所

10、设计的处理器调度程序，显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。实验环境：不限制编程语言及环境，建议采用C语言。实验预习要求、实验条件、方法及步骤 ：1理解本实验中调度算法的说明。2根据调度算法的说明，画出相应的程序流程图。3按照程序流程图，编程并实现。思考题 ：1逻辑时间片该如何实现？2如果不使用指针操作，是否也可以使用数组实现进程就绪队列的组织？实验二 银行家算法模拟实验内容：编写和调试一个简单的银行家算法程序。实验目的：银行家算法是避免死锁的一种重要方法，要求编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，理解和掌握安全序列、安全性算法，并体会和

11、了解死锁和避免死锁的具体实施方法。实验题目：1数据结构假设有M个进程N类资源，则有如下数据结构：MAXM*NM个进程对N类资源的最大需求量AVAILABLEN系统可用资源数ALLOCATIONM*NM个进程已经得到N类资源的资源量NEEDM*NM个进程还需要N类资源的资源量2银行家算法设进程I提出请求RequestN，则银行家算法按如下规则进行判断。(1)如果RequestN=NEEDI，N，则转(2)；否则，出错。(2)如果RequestN=AVAILABLE，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：AVAILABLE=AVAILABLE-REQUESTALLOCATI

12、ON=ALLOCATION+REQUESTNEED=NEED-REQUEST(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。3安全性检查(1)设置两个工作向量WORK=AVAILABLE；FINISHM=FALSE(2)从进程集合中找到一个满足下述条件的进程，FINISHi=FALSENEED=WORK如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。WORK=WORK+ALLOCATIONFINISH=TRUEGOTO2(4)如所有的进程FinishM=true，则表示安全；否则系统不安全。实验环境：不限

13、制编程语言及环境，建议采用C语言。实验预习要求、实验条件、方法及步骤 ：1理解本实验中关于银行家算法的说明。2参考图2.1所示流程图编写安全性算法。Y所有finish都为true？输出安全序列NYN存在Finishi =false&Needij Needij出错返回：return(error)Requestij Availablej出错返回：(进程阻塞)return(error)Availablej = Availablej RequestijAllocationij= Allocationij + RequestijNeedij = Needij Requestij假定分配：输入初始参数（资

14、源分配及请求情况）开始 假定分配之后，系统安全吗？申请成功。输出各种数据的变化图2.2 银行家算法流程图实验三 分区存储管理算法模拟实验内容：在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。也可选用循环首次适应算法或最佳适应算法或最坏适应算法其中一种进行替换。实验目的：一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部

15、分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验帮助学生理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。实验题目：1. 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。如下图3.1所示。 图3.1主存分区分配示意图为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下表3.1所示。其中，起址指出一个空闲区的主存起始地

16、址。长度指出从起始地址开始的一个连续空闲的长度。状态有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。表3.1空闲区说明表起 址长 度状 态第一栏14 K12 K未 分 配第二栏32 K96 K未 分 配MM空 表 目空 表 目MM上述的这张说明表的登记情况是按图3.1中的例子所

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

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

19、程序。然后按图3.1中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存；然后作业3撤离；再作业2撤离。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。图3.2 最先适应分配模拟算法图3.3 主存回收算法实验环境：不限制编程语言及环境，建议采用C语言。实验预习要求、实验条件、方法及步骤 ：1理解本实验的说明。2画出相应的程序流程图。3按照程序流程图，编程并实现。思考题 ：1可变分区管理方式与分页管理方式有何区别？实验四 分页存储管理算法模拟实验内容：在分页式管理方式下采用位示图来表示主

20、存分配情况，实现主存空间的分配和回收。实验目的：通过本实验帮助理解在分页式存储管理方式下应怎样贮存空间的分配和回收。实验题目：1分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。2假设某系统的主存被分成大小相等的64块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31，共10个主存块被占

21、用了，那么位示图情况如下图4.1所示。图4.1 位示图示意图3当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。按找到的计算出对应的块号，其计算公式为：块号= j8+i其中，j表示找到的是第n个字节，I表示对应的是第n位。根据分配给作业的块号，为作业建立一张页表，页表格式如下图4.1所示。表4.1 页表页 号块 号012MM 4当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对

22、应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：字节号 j=块号/8 （ 表示取整）位数 i=块号/8 （ 表示取余）5设计实现主存分配和回收的程序。假定位示图的初始状态如图4.1所述，现有一信息量为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（格式如表4.1所述）。然后假定有另一作业执行结束，它占用的块号为第4，5，6和31块，运行你所设计的回收程序，收回作业归还的主存块。要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。实验环境：不限制编程语言

23、及环境，建议采用C语言。实验预习要求、实验条件、方法及步骤 ：1理解本实验的说明。2画出相应的程序流程图。3按照程序流程图，编程并实现。思考题 ：1在编程中遇到了哪些问题？你是如何解决的？实验五 请求页式存储管理算法模拟实验内容：采用请求页式分配存储方案，选择OPT 算法 (最优置换算法)、LRU 算法 (Least Recently)、 FIFO 算法其中一种算法进行模拟实现。实验目的：通过本实验学习掌握调页策略和一般常用的调度算法，学会各种存储分配算法的实现方法，了解页面大小和内存实际容量对命中率的影响。实验题目：分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面。在进程运

24、行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。一、最佳置换算法OPT(Optimal)它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺

25、页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 二、先进先出(FIFO)页面置换算法 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。三、最近最久未使用置换算法 1、LRU(Least Recently Used)置换算法的描述FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调

26、入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 2、LRU置换算法的硬件支持 LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最

27、久未使用的页面，须有以下两类硬件之一的支持： 1）寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如表5.1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为18。由下表5.1可以看出，第7个内存页面的R值最小，

28、当发生缺页时首先将它置换出去。 表5.1 计数器R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 2)栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。实验环境：不

29、限制编程语言及环境，建议采用C语言。实验预习要求、实验条件、方法及步骤 ：1理解本实验的说明，并画出相应的程序流程图。2按照程序流程图，编程并实现。思考题 ：1为什么在实际的系统中不用LRU置换算法，而用它的近似算法？2OPT算法为什么难以实现？实验六 磁盘存储空间的分配和回收实验内容：模拟磁盘空闲空间的表示方法，以及模拟实现磁盘空间的分配和回收.实验目的：磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去，这就涉及到磁盘存储空间的分配和回收。一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、链接

30、文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过本实习使学生掌握磁盘存储空间的分配和回收算法。实验题目：本实验模拟三种磁盘存储空间的管理方法。可任选一题。第一题：连续的磁盘存储空间的分配和回收。提示：(1) 要在磁盘上建立顺序文件时，必须把按序排列的逻辑记录依次存放在磁盘的连续存储空间中。可假定磁盘初始化时，已把磁盘存储空间划分成若干等长的块（扇区），按柱面号和盘面号的顺序给每一块确定一个编号。随着文件的建立、删除、磁盘存储空间被分成许多区（每一区包含若干

31、块），有的区存放着文件，而有的区是空闲的。当要建立顺序文件时必须找到一个合适的空闲区来存放文件记录，当一个文件被删除时，则该文件占用的区应成为空闲区。为此可用一张空闲区表来记录磁盘存储空间中尚未占用的部分，格式如下表6.1所示。表6.1 空闲区表序 号起始空闲块号空闲块个数状 态156未 分 配2143未 分 配32130未 分 配4空 表 目MMMMMMMM(2) 要建立文件时，先查找空闲区表，从状态为“未分配”的登记栏目中找出一个块数能满足要求的区，由起始空闲块号能依次推得可使用的其它块号。若不需要占用该区的所有块时，则剩余的块仍应为未分配的空闲块，这时要修改起始空闲块号和空闲块数。若占用

32、了该区的所有块，则相应登记栏中的状态修改成“空表目”。删除一个文件时，从空闲区表中找一个状态为“空表目”的登记栏目，把归还的起始块号和块数填入对应的位置。磁盘存储空间的分配和回收算法类似于主存储器的可变分区方式的分配和回收。同学们可参考实验三的第一题。(3) 当找到空闲块后，必须启动磁盘把信息存放到指定的块中，启动磁盘必须给出由三个参数组成的物理地址：柱面号、磁道号和物理记录号。故必须把找到的空闲块号换算成磁盘的物理地址。为了减少移臂次数，磁盘上的信息按柱面上各磁道顺序存放。现假定一个盘组共有200个柱面，（编号0-199）每个柱面有20个磁道（编号0-19，同一柱面上的各磁道分布在各盘面上，

33、故磁道号即盘面号。），每个磁道被分成等长的6个物理记录（编号0-5，每个盘面被分成若干个扇区，故每个磁道上的物理记录号即为对应的扇区号。）。那么，空闲块号与磁盘物理地址的对应关系如下：空闲块号6空闲块号6假设M= ， m= M20则 物理记录号 = m磁道号= M20柱面号= (4) 删除一个文件时，从文件目录表中可得到该文件在磁盘上的起始地址和逻辑记录个数，假定每个逻辑记录占磁盘上的一块，则可推算出归还后的起始空闲块号和块数，登记到空闲区表中。换算关系如下：起始空闲块号=（柱面号20+磁道号）6+物理记录号空闲块数=逻辑记录数(5) 请设计磁盘存储空间的分配和回收程序，要求把分配到的空闲块转

34、换成磁盘物理地址，把归还的磁盘空间转换成空闲块号。假定空闲区表的初值如提示（1）中指出，现有一文件要占用10块，运行你所设计的分配程序，显示或打印分配后的空闲区表以及分配到的磁盘空间的起始物理地址。然后，有一文件被删除，它占用的磁盘空间为：1号柱面2号磁道，0号物理记录开始的4块，运行你所设计的回收程序，显示或打印回收后的空闲区表。第二题：用位示图管理磁盘存储空间提示：(1) 为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。位示图由若干字节构成，每一位与磁盘上的

35、一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。位示图的形式与实习二中的位示图一样，但要注意，对于主存储空间和磁盘存储空间应该用不同的位示图来管理，绝不可混用。(2) 申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。假设现在有一个盘组共80个柱面，每个柱面有两个磁道，每个磁道分成4个物理记录。那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：柱面号=字节号位数4磁道号= 位数4物理记录号= (3) 归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中

36、的对应位，把该位置成“0”。按照（2）中假设的盘组，归还块在位示图中的位置计算如下：字节号=柱面号位数=磁道号4+物理记录号(4) 设计申请一块磁盘空间和归还一块磁盘空间的程序。要求能显示或打印程序运行前和运行后的位示图；分配时把分配到的磁盘空间的物理地址显示或打印出来，归还时把归还块对应于位示图的字节号和位数显示或打印出来。(5) 假定已有如表6.1的磁盘空间被占用了，现在要申请五块磁盘空间，运行分配程序，按（4）中要求显示或打印运行的结果。然后再归还如表6.2的空间，运行回收程序，按（4）中的要求显示或打印运行结果。表6.1 初始分配柱面号磁道号物理记录号00100201001310011

37、2表6.2 回收空间柱面号磁道号物理记录号002010101第三题：模拟UNIX系统的空闲块成组链接法，实现磁盘存储空间的管理。提示：(1) 假定磁盘存储空间已被划分成长度为n的等长块，共有M块可供使用。UNIX系统中采用空闲块成组链接的方法 来管理磁盘存储空间，将磁盘中的每N个空闲块（NM）分成一组，最后一组可以不足N块，每组的第一块中登记了下一组空闲块的块数和块号，第一组的块数和块号登记在专用块中，登记的格式如下图6.1所示。0空闲块数k1空闲块号12空闲块号2MMMMK空闲块号kMMMM图6.1 空闲块登记格式当第一项内容为“0”时，则第二项起指出的空闲块是最后一组。(2) 现模拟UNI

38、X系统的空闲块成组链接，假定共有8块可供使用，每3块为一组，则空闲块成组链接的初始状态如下图所示。图6.2 空闲块成组链接的初始状态开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，空闲块的链接就未必按序排列了。用二维数组A：array 0M-1 of array 0n-1来模拟管理磁盘空间，用Ai表示第I块，第0块A0作为专用块。(3) 成组链接的分组情况记录在磁盘物理块中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复制到主存中。定义一个数组MA存放专用块内容，即MA: =A0。申请一块磁盘空间时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时

39、，则应把该块中指出的下一组的空闲块数和块号复制到专用块中，然后把该块分配给申请者。当一组的空闲块分配完后则把专用块内容（下一组链接情况）复制到主存，再为申请者分配。分配算法如下图6.3所示。 图6.3 采用成组链接的分配算法(4) 归还一块时给出归还的块号，叵当前组不满规定块数时，将归还块登记入该组；若当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把主存中登记的一组链接情况MA复制到归还块中，然后在MA重新登记一个新组。归还一块的算法如下图6.4所示。(5) 设计分配和归还磁盘空间的程序，能显示或打印分配的磁盘空间的块号，在完成一次分配或归还后能显示或打印各空闲块组的情况（各组的空

40、闲块数和块号）。本实习省去了块号与物理地址之间的转换工作，而在实际的系统中必须进行块号与物理地址的转换工作。(6) 运行你所设计的程序，假定空闲块链接的初始状态如提示（2），现先分配4块，再依次归还第2块和第6块。把执行后分配到的块号依次显示或打印出来，且显示或打印空闲块组的情况。在上次执行的基础上继续分配3块，然后归还第1块，再申请5块，显示或打印依次分配到的块号及空闲块组情况。图6.4采用成组链接的回收算法实验环境：不限制编程语言及环境，建议采用C语言。实验预习要求、实验条件、方法及步骤 ：1理解本实验的说明。2画出相应的程序流程图。3按照程序流程图，编程并实现。思考题 ：1在编程中遇到了哪些问题？你是如何解决的？附 录一 参考实例二 实验报告格式武汉大学珞珈学院计算机科学系 实验报告实验课程：专 业： 年 级： 学 号： 姓 名： 指导教师： 201 -201 学年 第 学期 实验项目名称实验日期实验成绩实验类型(验证型、设计型、综合设计型、创新性实验)实验目的与要求（给出本次实验所涉及并要求掌握的知识点）实验原理实验环境（列出本次实验所使用的平台和相关软件）实验方案设计实验内容（给出实验内容具体描述）