操作系统原理期末复习.docx

1、 操作系统的目标和作用 方便性，有效性，可扩充性，开放性 OS作为用户与计算机硬件系统之间的接口 OS作为计算机系统资源的管理者 OS实现了对计算机资源的抽象2、 多道程序设计的目的 为了进一步提高资源的利用率和系统吞吐量3、 操作系统的定义、功能、类型、特征 OS是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。a.处理机管理功能 进程控制 进程同步 进程通信 调度b.存储器管理功能 内存分配 内存保护 地址映射 内存扩充c.设备管理功能 缓冲管理 设备分配 设备处理d.文件管理功能 文件存储空间的管理 目录管理 文件的读/写管理和保护类型：1)未配置操作系统的计算机系统 人工操作方式 脱机输入输出方式2)单道批处理系统3)多道批处理系统4)分时系统5)实时系统6)微操作系统 单用户单任务操作系统(CP/M，MS-DOS) 单用户多任务(win95，win Vista，win7) 多用户多任务(UNIX ，solaris，Linux)特征：a.并发 并行与并发 引入进程b.共享 互斥共享方式 同时访问方式c.虚拟 时分复用技术 空分复用技术d.异步4、 进程的定义、特征 定义：由程序段、相关的数据段和PCB三部分便构成了进程实体。 特征： a.结构特征：PCB控制块，FCB文件控制块 b.动态性，并发性，独立性，异步性5、 进程控制块（概念、作用、内容） 概念：为了描述系统描述和管理进程的运行，在OS的核心为每个进程专门定义了一个数据结构进程控制块。PCB作为进程实体的一部分，记录了操作系统所需的，用于描述进程的当前情况以及管理进程运行的全部信息，是操作系统中最重要的纪录型数据结构。 作用：PCB使一个在多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其他进程并发执行进程。 a.作为独立运行的基本单位的标志。 b.能实现间断性运行方式。 c.提供进程管理所需要的信息。 d.提供进程调度所需要的信息。 e.实现与其它进程的同步和通信。 内容：进程标识符：外部标识符，内部标识符。 处理机状态：处理机上下文，通用寄存器， 进程调度信息：进程状态，进程优先级，进程调度所的其他信息，事件进程控制信息：程序和数据的地址，进程同步和通信机制，资源清单，链接指针。6、 进程基本状态及其转换原因（1）就绪状态：指进程已处于准备好运行的状态，即进程已分配到除了CPU以外的所有必要资源。（2）执行状态：进程已获得CPU，程序正在执行的状态。（3）阻塞状态：指正在执行的进程由于发生某事件暂时无法继续执行时的状态。（4）创建状态：申请PCB填写信息-分配资源-就绪队列（5）终止状态：等待操作系统进行善后处理-PCB清零，空间返回系统 许可就绪创建 时间片完 I/O完成 进程调度 释放 I/O完成终止执行阻塞 7、 临界资源、临界区、进程两种制约关系 两种形式的制约关系：间接制约关系（互斥），直接制约关系（合作共赢） 临界资源：许多硬件资源，打印机，磁带机等 临界区：在每个进程中访问临界资源的那段代码成为临界区。8、 进程同步机制 进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则共享系统资源，并相互合作。1） 空闲让进：临界区无进程，允许请求进入临界区。2） 忙则等待：正在被访问，请求应该等待。3） 有限等待：对每个请求都给它们一些承诺，避免死等。4） 让权等待：进程进不去时，释放掉处理机，不能占着茅坑不拉屎。 硬件同步机制：关中断，利用Test-and-Set指令实现互斥，利用Swap指令实现进程互斥 信号量机制：整型信号量，记录型信号量，AND信号量，信号量集 管程机制：数据结构和对数据结构实施的一组操作。进程私有数据结构顺序程序执行的操作为了实现系统的并发性主动工作可并发执行由创建诞生，由撤销消亡。管程公共数据结构同步操作和初始化操作解决共享资源的互斥使用被动工作不能与其调用者并发OS中的资源管理模块，供进程调用，不生不死不老不灭9、 进程高级通信机制的分类共享存储器系统基于共享数据结构的通信方式基于共享存储区的通信方式管道通信系统用于连接一个读进程和一个写进程，利用管道通信互斥，同步，确定对方是否存在消息传递系统格式化的消息（报文）将通信的数据封装在消息里传输直接通信（发送原语）间接通信（邮箱）客户机-服务器系统套接字（文件型-像管道，网络型-连接后通信），远程过程调用，远程方法调用10、 用信号量和p、v操作机制实现进程的同步和互斥11、 线程与进程的比较A. 作为调度的基本单位：线程的切换代价远低于进程B. 并发性：不同进程中的线程课并发执行，有效的提高系统资源利用率和系统吞吐量，例如文字处理器。C. 拥有资源：进程是系统中拥有资源的一个基本单位，线程没有系统资源，而是仅有一点能保证独立运行的资源。多个线程可以共享进程拥有的资源（地址空间）D. 独立性：线程不如进程。每个进程之间有独立的地址空间和其他资源，而同一进程中的线程可以共享该进程的地址空间，独立性较差。E. 系统开销：进程开销大F. 支持多处理机系统：多线程进程可以将一个进程中的多个线程分配到多个处理机上，使并行执行。12、 处理机调度的三级调度主要任务是什么（作业调度）（1）高级调度：调度对象是作业，根据某种算法，决定将外存上处于后备队列的哪几个作业调入内存，创建进程，分配资源。高级调度主要用于多道批处理系统中。（2）低级调度：调度对象是进程（或内核级线程），根据某种算法，决定就绪队列中的哪个进程应获得处理机，最基本调度，三种类型OS都配置。（3）中级调度：内存调度，控制暂时不能运行的进程调入调出内存外存。13、 常用的调度算法（先来先服务、短进程优先、高优先权优先、高响应比、时间片轮转等）（1） 先来先服务调度算法（2） 短作业优先调度算法（3） 优先级调度算法（动态和静态） a.非抢占式优先权算法 在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成,不会被中断 b. 抢占式优先权调度算法 在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。（4） 高响应比优先调度算法 增加动态优先级 由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： （5）时间片轮转法 让就绪队列上每个进程每次仅运行一个时间片，时间片耗尽后，中断。（6） 多队列调度算法 设置不同的多个就绪队列，对每个就绪队列实施不同的调度算法。（7） 多级反馈队列调度算法 多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。 a.应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍。 b.当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。c.仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。（8） 基于公平原则的调度算法a.保证调度算法：比较各进程获得处理机时间的比率，选择比率小的B.公平分享调度算法 ：用户获得相同的处理机时间或所要求的时间比率14、 死锁（定义、原因、必要条件、和解决死锁的方法） 死锁：如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程就是死锁的。 原因：竞争不可抢占性资源引起死锁 竞争可消耗资源引起死锁 进程推进顺序不当引起死锁 必要条件： （1）互斥条件：一个资源被占用时，其他进程只能等待 （2）请求和保持条件：请求的资源被占用时，阻塞，以获得的资源保持不放 （3）不可抢占条件：进程获得的资源不能被抢占，只能自己释放 （4）循环等待条件：P0等待P1占用的资源，P1等待P2 解决死锁的办法： 预防死锁 避免死锁 检测死锁 解除死锁15、 程序的装入和链接方法 程序的装入：绝对装入方式（单道程序环境） 可重定位装入方式（重定位后不能在内存中移动，且必须放在连续区域） 动态运行时的装入方式（装入内存的地址仍是逻辑地址，转换要等到程序执行时进行） 程序的链接： 静态连接方式：对相对地址进行修改后变换外部调用符号 装入时动态链接：便于修改和更新 便于实现对目标模块的共享 运行时动态链接：将对某些模块的链接推迟到程序执行时才进行16、 连续分配（固定分区存储管理器、动态分区存储管理）的原理和特点 连续分配方式是最早出现的一种存储器分配方式，该分配方式为一个用户程序分配一个连续的内存空间。 单一连续分配 MS-DOS CP/M RT11 仅装有一道用户程序 固定分区分配 每个分区装入一道作业。分区大小相等 不灵活，程序太小时会造成内存空间浪费分区大小不等 增加分配的灵活性内存分配：为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，当有程序装入时，就会查分区表，可用于多道程序系统。动态分区分配为了实现动态分区分配，系统中必须配置相应的数据结构，用以描述空闲分区和已分配分区的情况，为分配提供依据。分区号分区大小（KB）分区始址（K）状态 1 50 85空闲 2 32 155空闲 3 70 275空闲 4 60 53空闲 5 . . 空闲分区表 前向指针后向指针N个字节可用N+2N+200空闲分区链 17、 分区分配算法（首次适应、最佳适应、最坏适应） 首次适应法为作业选择分区时总是从链首（低地址）开始搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。要求：空闲分区按地址递增的顺序排列。 循环首次适应算法 在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。 最佳适应法接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配。为作业选择分区时总是寻找其大小最接近于所要求的存储区域。特点：用最小空间满足要求。要求：空闲分区按其容量大小的顺序排列。 最坏适应算法接到内存申请时，在空闲表中找到一个不小于请求的最大空快进行分配，与最佳适应法相反，在作业选择存储块时，总是寻找最大的空白区。特点：当分割后空闲块仍为较大空块。要求：空闲分区按其容量从小到大的顺序排列。18、 页式、段式存储管理原理和特点 根据分配时所采用的基本单位不同，可将离散分配的管理方式分为以下三种段式存储管理和段页式存储管理。其中段页式存储管理是前两种结合的产物。 页式存储原理 A、划分实页：将物理内存划分成位置固定、大小相同的块（实页 面）。 B、划分虚页：将用户逻辑地址空间也分成同样大小的页面，成为虚 拟空间的虚页面。 C、建立页表：有时称为页面表或页面映射表（PMT）。每个作业一 张，按虚页号进行登记，其基本的内容有特征位（表示该页是否 在内存、实页号以及对应外存的地址。 D、地址变换：将虚页面的逻辑地址转化为实页面的物理地址，在程 序执行时改变为物理地址，属于作业的动态重定位，一般由地址 转换机构（硬件）完成。 特点： 允许一个作业存放在不连续的内存块中而又能保证作业连续得以运行，既不需要移动内存中的信息，又可较好地解决零头。段式存储管理的原理： A、采用二维地址空间，如段号（S）、页号（P）和页内单元号（D）； B、系统建两张表格每一作业一张段表，每一段建立一张页表，段表 指出该段的页表在内存中的位置； C、地址变换机构类似页式机制，只是前面增加一项段号。 特点： a、每一段分成若干页，再按页式管理，页间不要求连续； b、用分段方法分配管理作业，用分页方法分配管理内存； 段页式存储先分段，在段内进行分页，为每一个段赋予一个段名。以下展示出了一个作业地址空间的结构。该作业有三个段，页面大小4KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成。 19、 变换机构 段页式系统中，为了获得一条指令或数据，须三次访问内存：访问内存中的段表，从中取得页表始址访问内存中的页表，从中取出该页所在的物理块号，并与页内地址形成物理地址访问真正从第二次访问所得的地址中，取出指令或者数据20、分页和分段的主要区别 分页和分段有许多相似之处,比如两者都不要求作业连续存放.但在概念上两者完全不同,主要表现在以下几个方面:(1)页是信息的物理单位,分页是为了实现非连续分配,以便解决内存碎片问题,或者说分页是由于系统管理的需要.段是信息的逻辑单位,它含有一组意义相对完整的信息,分段的目的是为了更好地实现共享,满足用户的需要.(2)页的大小固定,由系统确定,将逻辑地址划分为页号和页内地址是由机器硬件实现的.而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时根据信息的性质来划分.(3)分页的作业地址空间是一维的.分段的地址空间是二维的.21、虚拟存储器（定义、理论基础、特征） 定义：虚拟存储技术是在主存和辅存之间，增加部分软件及必要的硬件支持，使主、辅之间的信息交换、程序的重定位、地址转换都能自动进行，从而主、辅存形成一个有机的整体，这种存储器的概念成为虚拟存储器。 特征：- 多次性多次性是指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只需将当前要运行的那部分程序和数据装入内存即可。以后每当要运行到尚未调入的那部分程序时，再将它调入。多次性是虚拟存储器最重要的特征。- 对换性对换性是指允许在作业的运行过程中进行换进、换出。即在进程运行期间，允许将那些暂不使用的程序和数据，从内存调至外存的对换区（换出）等到以后需要时再将它们从外存调至内存（换进）。甚至还允许将暂不运行的进程调至外存，待它们重又具备运行条件时再调入内存。- 虚拟性虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。虚拟性是以多次性和对换性为基础的。或者说仅当系统允许将作业分多次调入内存，并能将内存中暂时不运行的程序和数据换至外存时，才有可能实现虚拟存储器，而多次性和对换性又必须建立在离散分配的基础上。理论基础：程序在运行时，如果它所要访问的页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（缺页/缺段），此时程序应利用OS所提供的请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。- 如果此时内存已满，无法再装入新的页（段），则还需再利用页（段）的置换功能，将内存中暂时不用的页（段）调至外存上，腾出足够的内存空间后，再将要访问的页（段）调入内存，使程序继续执行下去。这样，便可使一个大的用户程序能在较小的内存空间中运行，也可在内存中同时装入更多的进程使它们并发执行。22、 页面淘汰率算法（FIFO OPT LRU） 1、最佳置换算法（Optimal）- 最佳置换算法是一种理想化的算法，具有最好的性能，但实际上却难于实现。该算法是由Belady于1996年提出的一种理论上的算法。该算法所选择的被淘汰的页面，将是以后不再使用的，或是未来最长时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于我们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。2、先进先出（FIFO）页面置换算法- 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个替换指针，总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。3、最近最久未使用（LRU）置换算法- FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。- 最近最久未使用（LRU Least Recently Used）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自从上次被访问以来（到现在）所经历的时间t，当需淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。- LRU置换算法的硬件支持:LRU置换算法虽然是一种比较好的算法，但要求系统有较多的硬件支持。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有两类硬件的支持：寄存器或栈。23、 内存管理的碎片（零头）问题及解决办法 24、设备的分类25、I/O传输控制的方式26、 独占设备分配的方法 分配设备 分配控制器 分配通道27、虚拟设备、Spooling的组成28、 引入缓冲技术的原因，缓存区的类型 （1）缓和CPU与I/O设备间速度不匹配的矛盾 （2）减少对CPU的中断频率，放宽对CPU中断响应时间的限制 （3）解决数据粒度不匹配的问题 （4）提高CPU和I/O设备之间的并行性类型：单缓冲区，双缓冲区，环形缓冲区，缓冲池29、 活动头磁盘的访问时间 活动头磁盘的访问时间包括寻道时间、旋转延迟时间和传送时间。 寻道时间指磁头移动到数据所在磁道需要的时间。在不同的磁头调度算法中，有不同的寻道时间。 旋转延迟时间是指从磁盘寻道结束开始，直到磁头旋转到I/O请求所请求的起始数据块位置止，这之间的时间间隔称为旋转延迟。 传送时间是指由磁头把扇区中的信息读到内存或内存中信息写到扇区中所需的时间。30、磁盘的调度算法31、文件的逻辑结构和存取方法有哪些 1. 按文件是否有结构分类分为有结构文件（记录式文件）、无结构文件（流式文件）。 1） 有结构文件分为： 定长记录，修改和检索比较方便； 变长记录，节省空间。 2）无结构文件：以字节为单位。如：源程序、可执行程序、库函数等。利用读、写指针来指出下一个要访问的字符。流式文件可以看做是单记录式。 2. 按文件的组织方式分类根据文件的组织方式，可把有结构文件分为三类：(1) 顺序文件：记录按某种顺序排序。(2) 索引文件：为每个变长记录建索引表项。(3) 索引顺序文件：为每组变长建索引表项。存取方法：单级文件目录，两级文件目录，树形结构目录32、 文件的共享方法有哪些？特点是什么？ 1、利用索引结点共享 特点：对文件的修改，只改动索引结点。用户都可见。 2. 利用符号链接实现文件共享 允许一个文件或子目录有多个父目录，但其中仅有一个作为主(属主)父目录，其它的几个父目录都是通过符号链接方式与之相链接的(简称链接父目录)。33、 文件的物理结构（顺序结构、链接（串联）结构（隐式、显示）、索引结构（单级、多级）顺序结构主要优点：(1) 顺序访问容易。(2) 顺序访问速度快，磁头移动距离最少。 主要缺点：(1) 要求为一个文件分配连续的存储空间。(2) 必须事先知道文件的长度。(3) 不能灵活地删除和插入记录。(4) 对于那些动态增长的文件，按最终的文件长度进行预分配。 隐式链接文件目录的外存地址有两部分组成：指向链接文件第一个盘块和最后一个盘块的指针。 每个数据盘块中含有指向文件下一盘块 的指针（如最后）。 特点：适合顺序访问； 随机访问效率低，如访问第i块时，需启动i次磁盘。（i-1次寻找下一盘块号， 1次访问数据）； 可靠性差。显式链接把用于链接文件各物理块的指针显式地存放在内存的一张链接表中，该表称为文件分配表（file allocation table ，FAT）。该表在整个磁盘中仅设置一张。 表的序号是物理盘块号； 每个表项存放该文件下一盘块的指针（下一盘块的盘块号）； 文件目录的外存地址只存放指向该文件的第一个盘块指针。单级索引组织方式为每个文件建立索引块（表），把分配给文件的所有盘块依文件的顺序记录在索引块中 。 在文件目录的物理地址中填写索引块所在的盘块号（指向索引块的指针）。 索引块和文件的数据块都需放在磁盘的盘块内。因此读写文件需先启动磁盘将索引 块读入内存。 多级索引组织方式文件太大时，需用多个索引块，这时需建立高级索引表。特点：查找速度块；启动磁盘次数增加。 34、 Unix系统混合（增量式）索引结构 UNIX System V的组织方式设有13个地址项。盘块（簇）大小为4KB，盘块号占4B(1) 直接地址：前09项。 文件最大=10 212=40KB。 (2) 一次间接地址：第10项。 文件最大= 210 212=4MB(3) 二次间接地址：第11项。 文件最大= 210210 212=4GB (4) 三次间接地址：第12项。 文件最大= 210210210 212=4TB 35、文件存储空间的管理方法（位示图、成组连接） 1) 空闲表（类似内存的动态分区算法）空闲表法用于连续分配方式，它为每个文件分配一块连续的存储空间。系统为外存上所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，形成空闲盘块表。 2. 空闲链表法1) 空闲盘块链这是将磁盘上的所有空闲空间以盘块为单位拉成一条链，其中的每一个盘块都有指向后继盘块的指针。用离散分配，如链接文件或索引文件。但需一个一个的摘下盘块进行分配，效率低。（回收一样）2) 空闲盘区链这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。与空闲表一样，用于连续分配。分配和回收与内存的分区(动态)分配类似，可采用相似算法，只是分配单位是盘块。1. 位示图位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。有的系统把“0”作为盘块已分配的标志，把“1”作为空闲标志。磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。 2. 盘块的分配(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2) 将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按下式计算：b=n(i-1)+j式中，n代表每行的位数。(3) 修改位示图，令mapi, j=1。3. 盘块的回收(1) 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：i=(b-1)DIV n+1j=(b-1)MOD n+1(2) 修改位示图。令mapi, j =0。 注：前面的几种管理方法，在空闲空间的分配和回收时需将空闲表或链或位示图全部调入内存。成组链接法1. 空闲盘块的组织 (1) 空闲盘块号栈，用来存放当前可用的一组空闲盘块的盘块号(最多含100个号)，以及栈中尚有的空闲盘块(号)数N。顺便指出，N还兼作栈顶指针用。 S.free(0)是栈底，栈满时S.free(99)是栈顶。(2) 文件区中的所有空闲盘块被分成若干个组，比如，将每100个盘块作为一组。假定盘上共有10000个盘块，每块大小为1 KB，其中第2017999号盘块用于存放文件，即作为文件区，这样，该区的最末一组盘块号应为79017999；次末组为78017900，倒数第二组的盘块号为301400；第一组为201300。 (3) 将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块的S.free(0) 中。这样，由各组的第一个盘块可链成一条链。 (4) 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。(5) 最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)S.free(99)中，而在S.free(0)中则存放“0