2010-10操作系统原理实验指导.doc

操作系统原理实验指导（学生试用讲义）信息科学与技术学院2010年9月操作系统实验说明操作系统课程教学的主要目的，是学习计算机操作系统中资源管理的方法和技术，这些方法和技术，在以后的实际应用开发中加以借鉴，可以提高所开发的应用程序质量。为了加深对操作系统教材中所讲述的一些主要管理策略和算法的理解、掌握这些算法的思想、并能用已学习的程序设计语言实现之，根据教学大纲的要求，在进行操作系统课程教学过程中必须安排若干实验。要完成这些实验，需要学生具有一定的C语言或其他编程语言的编程能力。根据我校学生的实际情况，也为了学生易于完成本课程的实验，我们在本实验指导中，对大多数实验给出了其C语言程序的实现框架，这些程序是可以直接运行的；并且，对于实验中的一些主要算法，我们也给出其相应的程序段（需要学生完善后才能运行的），其目的是对学生完成本讲义要求的实验提供帮助。很显然，要能较好的达到本课程实验之目的，不能完全依赖本指导，还需要学生的劳动和配合。操作系统实验的要求：（1） 积极认真地做好实验前的准备，在每个实验前，必须写出需要上机调试的源程序，并通过静态分析方法调试和修改，不能等到上机时再编写程序。尽管本指导给出了完整的示例，但要完成要求的实验，可能需要从数据结构定义开始。（2） 上机时，要积极调试程序，只有通过调试和改错，才能积累经验、提高能力、正确完成实验。（3） 仔细观察程序运行情况，做好记录，作好分析。（4） 按要求认真书写实验报告。（5） 遵守机房实验用机规定和纪律，服从管理。实验1 模拟进程管理一、 实验目的1 加深对进程概念的理解，明确进程和程序的区别。2 深入了解系统如何组织进程、创建进程。3 进一步认识如何实现处理器调度。二、 实验预备知识1 进程的概念。2 进程的组织方式。3 进程的创建。4 进程的调度。三、 实验内容编写程序完成单处理机系统中的进程调度，要求采用先来先服务算法、最短CPU运行期优先调度算法、优先级调度算法、多级反馈队列轮转算法。实验具体包括：首先确定进程控制块的内容和进程控制块的组织方式；然后完成进程创建原语和进程调度原语；最后编写主函数对所做工作进行测试。 四、提示与讲解这个实验主要需要考虑三个问题：如何组织进程、如何创建进程和如何实现处理器调度。考虑如何组织进程，首先就要设定进程控制块的内容。进程控制块PCB记录各个进程执行时的情况。不同的操作系统，进程控制块记录的信息内容不一样。操作系统功能越强，软件也越庞大，进程控制块记录的内容也就越多。这里的实验只是用了必不可少的信息。一般操作系统中，无论进程控制块中信息量多少，信息都可以大致分为以下四类：（1） 标识信息每个进程都要有一个唯一的标识符，用来标识进程的存在和区别于其他进程。这个标识符是必不可少的，可以用符号或编号实现，它必须是操作系统分配的。在后面给出的参考程序中，采用编号方式，也就是为每个进程依次分配一个不相同的正整数。（2） 说明信息用于记录进程的基本情况，例如进程的状态、等待原因、进程程序存放的位置、进程数据存放位置等等。实验中，因为进程没有数据和程序，仅使用进程控制块模拟进程，所以这部分内容仅包括进程状态。（3） 现场信息现场信息记录各个寄存器的内容。当进程由于某种原因让出处理器时，需要将现场信息记录在进程控制块中，当进行进程调度时，从选中进程的进程控制块中读取现场信息进行现场恢复。现场信息就是处理器的相关寄存器内容，包括通用寄存器、程序计数器和程序状态字等。在实验中，可选取几个寄存器作为代表。用大写的全局变量AX、BX、CX、DX模拟通用寄存器、大写的全局变量PC模拟程序计数器、大写的全局变量PSW模拟程序状态字。（4） 管理信息管理信息记录进程管理和调度的信息。例如进程优先数、进程队列指针等。实验中，仅包括队列指针。因此，可将进程控制块结构定义如下：struct pcb int name; /进程标识符 int status; /进程状态 int AX,BX,CX,DX; /进程现场信息，通用寄存器内容 int PC; /进程现场信息，程序计数器内容 int PSW; /进程现场信息，程序状态字内容 int next; /下一个进程控制块的位置 确定进程控制块内容后，要考虑的就是如何将进程控制块组织在一起。多道程序设计系统中，往往同时创建多个进程。在单处理器的情况下，每次只能有一个进程处于运行态、其他的进程处于就绪状态或等待状态。为了便于管理，通常把处于相同状态的进程的进程控制块链接在一起。单处理器系统中，正在运行的进程只有一个。因此，单处理器系统中进程控制块分成一个正在运行进程的进程控制块、就绪进程的进程控制块组织成的就绪队列和等待进程的进程控制块组成的等待队列。由于实验模拟的是进程调度，没有对等待队列的操作，所以实验中只有一个指向正在运行进程的进程控制块指针和一个就绪进程的进程控制块队列指针。操作系统的实现中，系统往往在主存中划分出一个连续的专门区域存放系统的进程控制块，实验中应该用数组模拟这个专门的进程控制块区域，定义如下：#define n 10 /假定系统允许进程个数为10struct pcb pcbarean; /模拟进程控制块区域的数组这样，进程控制块的链表实际上是数据结构中使用的静态链表。进程控制块的链接方式可以采用单向和双向链表，实验中，进程控制块队列采用单向不循环静态链表。为了管理空闲进程控制块，还应该将空闲进程控制块链接成一个队列。实验示例程序中采用时间片轮转调度算法，这种算法是将进程控制块按照进入就绪队列的先后次序排成队列。关于就绪队列的操作就是从队头摘下一个进程控制块和从队尾挂入一个进程控制块。因此为就绪队列定义两个指针，一个头指针，指向就绪队列的第一个进程控制块；一个尾指针，指向就绪队列的最后一个进程控制块。实验中指向运行进程的进程控制块指针、就绪队列指针和空闲进程控制块队列指针定义如下：int run; /定义指向正在运行进程的进程控制块的指针struct int head; int tail； ready; /定义指向就绪队列的头指针head和尾指针tailint pfree; /定义指向空闲进程控制块队列的指针以上是如何组织进程，下面考虑如何创建进程。进程创建是一个原语，因此在实验中应该用一个函数实现，进程创建的过程应该包括：（1） 申请进程控制块：进程控制块的数量是有限的，如果没有空闲进程控制块，则进程不能创建，如果申请成功才可以执行第二步；（2） 申请资源：除了进程控制块外，还需要有必要的资源才能创建进程，如果申请资源不成功，则不能创建进程，并且归还已申请的进程控制块；如果申请成功，则执行第三步，实验无法申请资源，所以模拟程序忽略了申请资源这一步；（3） 填写进程控制块：将该进程信息写入进程控制块内，实验中只有进程标识符、进程状态可以填写（模拟进程创建时，需输入进程标识符，进程标识符本应系统建立，并且是唯一的，输入时注意不要冲突），刚创建的进程应该为就绪态，然后转去执行第四步；（4） 挂入就绪队列：如果原来的就绪队列不为空，则将该进程控制块挂入就绪队列尾部，并修改就绪队列尾部指针；如果原来就绪队列为空，则将就绪队列的头指针、尾指针均指向该进程控制块，进程创建完成。 进程创建流程图如图1所示。NYYN开始空闲进程控制块队列为空？取空闲进程控制块队列的第一个i=pfreepfree后移：pfree=pcbareapfree.next填写该进程控制块的内容：=name;pcbareai.status=aready;初始化进程控制块内的现场信息；就绪队列为空？挂入就绪队列：pcbareaready.tail.next=i;ready.tail=i;pcbareaready.tail.next=-1;结束进程创建失败挂入就绪队列：ready.head=i;ready.tail=i;pcbareaready.tail.next=-1;图1 进程创建流程图多道程序设计的系统中，处于就绪状态的进程往往有多个，它们都要求占用处理器，可是单处理器系统的处理器只有一个，进程调度就是解决这个处理器竞争问题的。进程调度的任务就是按照某种算法从就绪进程队列中选择一个进程，让它占有处理器。因此，进程调度程序就应该包括两部分，一部分是在进程就绪队列中选择一个进程，并将其进程控制块从进程就绪队列中摘下来，另一部分工作就是分配处理器给选中的进程，也就是将指向正在运行进程的进程控制块指针指向该进程的进程控制块，并将该进程的进程控制块信息写入处理器的各个寄存器中。实验参考程序中采用时间片轮转调度算法，这种算法让就绪进程按就绪的先后次序排成队列，每次总是选择就绪队列中的第一个进程占有处理器，但是规定只能使用一个“时间片”。采用时间片轮转调度算法的进程调度流程图如图2所示。NYYN开始就绪队列为空？就绪队列头指针赋给i：i= ready.head就绪队列头指针后移：ready.head =pcbareaready.head.next就绪队列队尾指针置为空：ready.tail=-1就绪队列为空？设置相对时钟寄存器：TIME=时间片无进程可以调度修改进程控制块状态：pcbareai.status=running图2 进程调度流程图恢复该进程现场信息：AX=ax;BX=bx;CX=cx;DX=dx;PC=pc;PSW=psw;修改指向运行进程的指针：run=i完成上述功能后，编写主函数进行测试：首先建立一个就绪队列，手工输入信息建立几个进程；然后进行进程调度；最后将指向正在运行进程的指针指向的进程控制块内容输出，察看结果。四、 参考程序#include “stdio.h”#define running 1 / 用running表示进程处于运行态#define aready 2 / 用aready表示进程处于就绪态#define blocking 3 / 用blocking表示进程处于阻塞态#define sometime 5 / 用sometime表示时间片大小#define n 10 /假定系统允许进程个数为nstruct int name; /进程标识符 int status; /进程状态 int ax,bx,cx,dx; /进程现场信息，通用寄存器内容 int pc; /进程现场信息，程序计数器内容 int psw; /进程现场信息，程序状态字内容 int next; /下一个进程控制块的位置pcbarean; /模拟进程控制块区域的数组int PSW, AX,BX,CX,DX, PC,TIME; /模拟寄存器int run; /定义指向正在运行进程的进程控制块的指针struct int head; int tail;ready; /定义就绪队列的头指针head和尾指针tailint pfree; /定义指向空闲进程控制块队列的指针scheduling( ) /进程调度函数 int i; if (ready.head=-1) /空闲进程控制块队列为空，退出 printf(“无就绪进程n”);return;i=ready.head; /就绪队列头指针赋给iready.head=pcbareaready.head.next; /就绪队列头指针后移if(ready.head=-1) ready.tail=-1; /就绪队列为空，修正尾指针ready.tailpcbareai.status=running; /修改进程控制块状态TIME=sometime; /设置相对时钟寄存器/恢复该进程现场信息AX=pcbarearun.ax;BX=pcbarearun.bx;CX=pcbarearun.cx;DX=pcbarearun.dx;PC=pcbarearun.pc;PSW=pcbarearun.psw;run=i;/进程调度函数结束create(int x) /进程创建函数 int i; if(pfree=-1) /空闲进程控制块队列为空 printf(“无空闲进程控制块，进程创建失败n”);return;i=pfree; /取空闲进程控制块队列的第一个pfree=pcbareapfree.next; / pfree后移/填写该进程控制块的内容=x;pcbareai.status=aready;pcbareai.ax=x;pcbareai.bx=x;pcbareai.cx=x;pcbareai.dx=x;pcbareai.pc=x;pcbareai.psw=x;if (ready.head!=-1) /就绪队列不为空时，挂入就绪队列的方式 pcbareaready.tail.next=i; ready.tail=i;pcbareaready.tail.next=-1;else /就绪队列为空时，挂入就绪队列的方式 ready.head=i; ready.tail=i; pcbareaready.tail.next=-1;/进程创建函数结束main() /系统初始化 int num,i,j; run=ready.head=ready.tail =-1; pfree=0; for(j=0;j=0) create(num);scanf(“%d”,&num);scheduling(); /进程调度if(run!=-1) printf(“进程标识符 进程状态 寄存器内容：ax bx cx dx pc psw:n”); printf(“%8d%10d%3d%3d%3d%3d%3d%3dn”, , pcbarearun.status, pcbarearun.ax, pcbarearun.bx, pcbarearun.cx, pcbarearun.dx, pcbarearun.pc, pcbarearun.psw);/main()结束实验2 模拟内存管理一、 实验目的深入了解可变分区存储管理方式主存分配回收的实现。二、 实验预备知识存储管理中的可变分区存储管理方式。三、 实验内容编写程序完成可变分区存储管理方式的主存分配回收的实现。实验具体包括：首先确定主存空间分配表；然后采用首次适应算法、循环首次适应算法、最差适应算法完成主存空间的分配和回收；最后编写主函数对所做工作进行测试。 四、 提示与讲解可变分区存储管理方式不预先将主存划分成几个区域，而把主存除操作系统占用区域外的空间看作一个大的空闲区。当作业要求装入主存时，根据作业需要主存空间的大小查询主存内各个空闲区，当从主存空间找到一个大于或等于该作业大小要求的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。作业执行完后，它所占的主存分区被回收，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。这个实验主要需要考虑三个问题：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。首先，考虑第一个问题：设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域。由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收而变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收主存分区时，可能会合并空闲分区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分分区表，主要操作在空闲区；某个作业执行完成后，将该分区变成空闲区，并将其与相邻空闲区合并，主要操作也在空闲区。由此可见，主存分配和回收主要是对空闲区的操作。这样为了便于对主存空间的分配和回收，就建立两张分区表记录主存使用情况，一张表格记录作业占用分区的“已分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种，一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因而在多数情况下，无论是“已分分区表”还是“空闲区表”都有空闲栏目。已分分区表中除了分区起始地址、长度外，也至少还要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；空闲区表中除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个空闲区的登记项，内容为“未分配”。在实际系统中，这两个表格的内容可能还要更多，实验中仅仅使用上述必须的数据。为此，“已分分区表”和“空闲区表”在实验中有如下的结构定义：已分分区表的定义：#define n 10 /假定系统允许的作业数量最多为nstruct float address; /已分分区起始地址 float length; /已分分区长度，单位为字节 int flag; /已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名 used_tablen; /已分分区表空闲区表的定义：#define m 10 /假定系统允许的空闲区数量最多为mstruct float address; /空闲区起始地址 float length; /空闲区长度，单位为字节 int flag; /空闲区表登记栏标志，“0”表示空栏目，用“1”表示未分配 free_tablem; /空闲区表其中分区起始地址和长度数值太大，超出了整型的表达范围，所以采用了float类型。然后，就要考虑如何在设计的数据表格上进行主存的分配。当要装入一个作业时，从空闲区表中查找标志为“未分配”的空闲区，从中找到一个能容纳该作业的空闲区。如果找到的空闲区正好等于该作业的长度，则把该分区全部分配给作业。这时应该把该空闲区登记栏中的标志改为“空”，同时在已分分区表中找到一个标志为“空”的栏目登记新装入作业所占用分区的起始地址、长度和作业名。如果找到的空闲区大于作业长度，则把空闲区分成两部分，一部分用来装入作业，另外一部分仍为空闲区。这时只要修改元空闲区的长度，且把新装入的作业登记到已分分区表中。实验示例程序中主存分配算法采用最佳适应算法。最佳适应算法是按作业要求挑选一个能满足作业要求的最小空闲区，这样保证可以不去分割一个大的区域，使装入大作业时比较容易得到满足。但是最佳适应算法容易出现找到的一个分区可能只比作业所要求的长度略大一点的情况，这时，空闲区分割后剩下的空闲区就很小，这种很小的空闲区往往无法使用，影响了主存的使用。为了一定程度上解决这个问题，如果空闲区的大小比作业要求的长度略大一点，不再将空闲区分成空闲区和已分分区两部分，而是将整个空闲区分配给作业。在实现最佳适应算法时，可把空闲区按长度以递增方式登记在空闲区中。分配时顺序查找空闲表，查找到的第一个空闲区就是满足作业要求的最小分区。这样查找速度快，但是为使空闲区按长度以递增顺序登记在空闲分区表中，就必须在分配回收时进行空闲区表的调整。空闲区表调整时移动表目的代价要高于查询整张表的代价，所以实验中不采用空闲区有序登记在空闲表中的方法。动态分区方式的主存分配流程图如图3所示。YNNYNYNYYNNYNYN作业J申请xk大小的主存空间i=0; k=-1;i是空闲区表中一栏（i=m）？第i栏标志为“未分配”且满足作业需求xk？i = i+1第i栏空闲区为第一个满足需求的或第i栏空闲区长度小于第k栏空闲区长度？k = i是否找到满足需求的分区k？主存分配失败结束第k栏长度作业需求=minsize？分配整个分区：第k栏状态为“空”；ad=第k栏起始地址；xk=第k栏长度；切割空闲区：第k栏长度减去xk；ad=第k栏起始地址第k栏长度；i=0第i栏是已分配区表中一栏且第i栏状态不为空？i=i+1第i栏是已分配表中的一栏？空闲分区表第k栏状态为空？填写已分配空闲区：第j栏起始地址=ad；第j栏长度=xk；第j栏状态=作业名J；空闲区表状态未分配空闲区表第k栏长度加xk已分配分区表长度不足，分配失败结束图3 动态分区最佳分配算法流程图最后是可变分区方式下的主存回收问题。可变分区方式下回收主存空间时，应该检查是否有与归还区相邻的空闲区。若有，则应该合并成一个空闲区。一个归还区可能有上邻空闲区，也可能有下邻空闲区，或者既有上邻空闲区又有下邻空闲区，或者既无上邻空闲区又无下邻空闲区。在实现回收时，首先将作业归还的区域在已分分区表中找到，将该栏目的状态变为“空”，然后检查空闲区表中标志为“未分配”的栏目，查找是否有相邻空闲区；最后，合并空闲区，修改空闲区表。假定作业归还得分区起始地址为S，长度为L，则：（5） 归还区有下邻空闲区 如果S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，则表明归还区有一个下邻空闲区。这时只要修改第j栏登记项的内容： 起始地址=S； 第j栏长度=第j栏长度+L； 则第j栏指示的空闲区是归还区和下邻空闲区合并后的大空闲区。（6） 归还区有上邻空闲区 如果空闲区表中某个登记栏目（假定为第k栏）的“起始地址+长度” 正好等于S，则表明归还区有一个上邻空闲区。这时要修改第k栏登记项的内容（起始地址不变）： 第k栏长度=第k栏长度+L； 则第k栏指示的空闲区是归还区和上邻空闲区合并后的大空闲区。（7） 归还区既有上邻空闲区又有下邻空闲区 如果S+L正好等于空闲区表中某个登记栏目（假定为第j栏）的起始地址，同时还有某个登记栏目（假定为第k栏）的“起始地址+长度” 正好等于S，这表明归还区既有一个上邻空闲区，又有一个下邻空闲区。这时对空闲区表的修改如下： 第k栏长度=第k栏长度+第j栏长度+L；（第k栏起始地址不变）第j栏状态=“空”；（将第j栏登记项删除） 则第k栏指示的空闲区是归还区和上、下邻空闲区合并后的大空闲区；原来的下邻空闲区登记项（第j栏）被删除，置为“空”。（8） 归还区既无上邻空闲区又无下邻空闲区如果在检查空闲区表时，无上述三种情况出现，则表明归还区既无上邻空闲区又无下邻空闲区。这时，应该在空闲区表中查找一个状态为“空”的栏目（假定查到的是第t栏），则第t栏的内容修改如下：第t栏起始地址=S；第t栏长度=L；第t栏状态=“未分配”这样，第t栏指示的空闲区是归还区。按上述方法归还主存区域的流程图如图4所示。由于是模拟实验，没有真正的主存要分配，所以在实验中，首先应建立一张空闲区表，初始状态只有一个空闲登记项（假定的主存空闲区）和一张所有状态都为“空”的已分分区表，假定主存空间为110KB，操作系统占用10KB，其余为空闲区；然后，可以选择进行主存分配或主存回收，如果是分配，要求输入作业名和所需主存空间大小，如果是回收，输入回收作业的作业名，循环进行主存分配和回收后，如果需要，则显示两张表的内容，以检查主存的分配和回收是否正确。NYYYYYYYYYYNNNNNNNNNN已分配区表第s栏状态为作业J(s=n)？S=已分配区表第s栏起始地址L=已分配区表第s栏长度已分配区表第s栏状态为空假设下邻空闲区在第j栏j=-1;假设上邻空闲区在第k栏k=-1;作业J归还空间s=0s=s+1s为已分配区表中一栏？i=0第i栏不是空闲区表中一栏或回收分区的上下邻空闲区均找到？第i栏状态为“未分配”？第i栏为回收分区的上邻？第i栏为回收分区的下邻？i=i+1j=ij=i回收分区有上邻？回收分区有下邻？回收分区有下邻？和上下邻三项合并：第k栏长度=第k栏长度+第j栏长度+L；第j栏状态=“空”和上邻合并：第k栏长度=第k栏长度+L和下邻合并：第j栏长度=第j栏长度+L；第j栏起始地址=St=0第t栏是空闲表中非空栏？空闲区表满？t=t+1归还分区填入空闲区表：第t栏起始地址=S；第t栏长度=L；第t栏状态=“未分配”；已分配区表第s栏状态为J；空闲表长度不足，回收失败结 束未找到作业，回收失败结 束Y图4 动态分区回收流程图五、 参考程序#define n 10 /假定系统允许的作业数量最多为n#define m 10 /假定系统允许的空闲区数量最多为m#define minisize 100struct float address; /已分分区起始地址 float length; /已分分区长度，单位为字节int flag; /已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名 used_tablen; /已分分区表struct float address; /空闲区起始地址 float length; /空闲区长度，单位为字节 int flag; /空闲区表登记栏标志，“0”表示空栏目，用“1”表示未分配 free_tablem; /空闲区表allocate(char J , float xk) /采用最佳适应算法为作业J分配xk大小的主存空间 int i, k; float ad; k= -1; for(i=0; i=xk & free_tablei.flag=1) if(k= -1 | free_tablei.lengthfree_tablek.length) k=i;if(k= -1) /未找到可用空闲区，返回printf(“无可用空闲区n”);return;/找到可用空闲区，开始分配：若空闲区大小与要求分配的空间差小于或等于minisize，则空闲区全部分配；若空闲区大小与要求分配的空间差大于minisize，则从空闲区划出一部分分配if(free_tablek.length-xk=minisize)free_tablek.flag=0;ad=free_tablek.address;xk= free_tablek.length;else free_tablek.length= free_tablek.length-xk; ad= free_tablek.address+ free_tablek.length;/修改已分分区表i=0;while(used_tablei.flag!=0 & i=n) /无表目填写已分分区 printf(“无表目填写已分分区，错误！n”); /修正空闲区表 if(free_tablek.flag=0) /前面找到的是整个空闲区 free_tablek.flag=1; else /前面找到的是某个空闲区的一部分 free_tablek.length= free_tablek.length+xk; return;else /修改已分分区表 used_tablei. address=ad; used_tablei. length=xk; used_tablei.flag=J;return;/主存分配函数结束reclaim(char J) /回收作业名为J的作业所占的主存空间 int i,k,j,s,t; float S,L; /寻找已分分区表中对应登记项 s=0; while(used_tables.flag!=J | used_tables.flag=0) & s=n) /已分分区表中找不到名为J的作业，返回 printf(“找不到该作业n”);return;/修改已分分区表used_tables.flag=0;/取得归还分区的起始地址S和长度LS= used_tables. address;L= used_tables. length;j=-1;k=-1;i=0;/寻找归还分区的上下邻空闲区，上邻表目k，下邻表目jwhile(im & (j=-1 | k=-1) if(free_tablei.flag=0) if(free_tablei.address+ free_tablei.length=S) /找到上邻 k=i; if(free_tablei.address=S+L) /找到下邻 j=i; i+;if(k!=-1) if(j!=-1) /与上下邻空闲区三项合并 free_tablek.length= free_tablej.length+ free_tablek.length+L; free_tablei.flag=0;else /上邻空闲区，下邻非空闲区，与上邻合并 free_tablek.length= free_tablek.length+L;else if(j!=-1) free_tablej. address=S; free_tablej.length= free_tablej.length+L;else t=0; while(free_tablet.flag=1 & tm) printf(“空闲区表没有空间，回收空间失败！n”); used_tables.flag=J; return;free_tablet. address=S;free_tablet.flag=1;free_tablet.length=L;return(true);/主存归还函数结束实验3 模拟文件管理一、实验目的 文件系统的主要功能就是方便用户对外存上的文件进行管理和操作，合理而有效地管理外存空间。本实验的目的是模拟文件系统常用的多级目录结构和外存空间离散分配（采用盘图管理外存）的策略，实现文件系统对文件的部分管理功能。二、实验内容 1、基本原理现代操作系统大多采用多级目录结构对外存中的文件进行管理，一个外存设备通常都有一个根目录，根目录下用户可根据需要创建子目录；任何一个文件可以属于某一个目录，也就是说，在相应的目录中记录了其所属文件的目录项；目录项中记录了该文件的必要信息。子目录也是作为文件保存的（称为目录文件）。用户通过文件名访问指定文件，文件系统则根据文件名查看目录信息，以确定文件在外存空间的位置，以便进一步的操作。文件系统的另一个重要任务是进行外存空间的管理，现在的操作系统对磁盘存储器大多不再采用连续分配的方法，而采用离散分配的策略。外存空间管理包括为文件分配所需的存储空间和用户删除文件时回收存储空间。常用的做法是，确定外存分配单位，并采用盘图等对外存进行分配和回收管理。2、本实验的内容设计目录结构（采用多级目录）以及文件目录项的结构、外存空间的盘图，并编程实现如下要求（本实验未考虑实现文件操作功能）：（1） 初始化目录和盘图；（2） 为用户创建文件、增加文件长度分配外存空间和更新目录信息；（3） 允许用户删除文件，更新目录和回收外存空间；（4） 提供文件复制和移动并进行管理；（5） 允许更改存在文件的文件名；（6） 可以创建和删除子目录。（7） 实验提示：假定外存空间为1.0M，文件系统为文件分配存储空间的分配单位是物理块（扇区）；根目录允许的目录项总数为100。三、实验要求对各种操作的结果，要能打印（显示）出目录信息和盘图结果。四、思路参照教材介绍的文件目录信息构成设计目录的数据结构，盘图的设计也参照教材所介绍的内容。有关算法可参照本实验提供的源程序。五、参考程序（以下提供的是一个简单的文件管理程序，供参考后完成实验题）#include #include typedef struct FDT char fname8,exfname3,property; int size; struct FDT *sibling,*son;FDT,*FP;FP Root=NULL;FP chdir(FDT *t) char ch,pname81,tn9= , , , , , , , ,0; /*假定路径名长不超过80*/ int i,k; FP r; printf(请输入新选择的目录所在的路径名及目录名（如：abcttt）n); scanf(%s,pname);printf(所选目录是:%sn,pname);i=0;r=t;while(pnamei!=0) k=0; while(pnamei=) i+; while(pnamei!=&pnamei!=0) tnk+=pnamei+; if(r) r=r-son; while(r &(!eqn(tn,8,r-fname)|(r-property!=d)&(r-property!=D) r=r-sibling;if(!r) printf(指定的路径或目录错误！按一键返回n); while(bioskey!=0) getchar(); getchar();return t; printf(你所选当前目录是:%sn,tn);return r;int eqn(char x,int c,char y) int i; if(!c) return 0; for(i=0;ic;i+) if(xi=0&(yi= ) break; else if(xi!=yi) return 0; return 1;void displist(FP q) int i; i=0; while(ifnamei+); printf( ); i=0;while(iexfnamei+); printf( %c ,q-property); if(q-property!=D&q-property!=d) printf(%dn,q-size);else printf(n);void dlist(FDT *ptr)int i; FP r; char fn9,exfn4,c1,c2; c1=c2= ; r=ptr-son; printf(输入要查看的当前目录下的文件/子目录名(*代表全体):); scanf(%s,fn); printf(n输入文件的扩展名(*代表全体或子目录):); scanf(%s,exfn); if(!r) printf(当前目录为空！按一键返回.:n);