第5章 设备管理与文件管理

第5章设备管理与文件管理在计算机系统中，除了需要有处理机和存储器外，还需要有用于实现信息输入、输出和存储的设备。设备管理程序便是用于对这类设备进行控制和管理的一组程序。设备管理是操作系统中最繁杂且与硬件紧密相关的部分。这里只讨论在计算机系统中，除CPU、主存储器外的设备的管理。学习目标:掌握设备的分类。掌握设备管理的主要功能。掌握常见的数据I/O控制方式。掌握文件的分类。掌握文件管理的主要功能。了解文件的逻辑结构方式及文件在外存上的分配存储方式。了解Linux系统中的设备管理。5.1设备管理概述5.2数据输入/输出控制方式5.3文件管理概述5.4文件的逻辑结构5.5外存分配方式5.6Linux中的设备管理5.1设备管理概述5.1.1设备的分类5.1.2设备管理的任务和功能5.1.3缓冲技术5.1.4设备驱动5.1.1设备的分类

可以从不同的角度对I/O设备进行分类。按其使用方式可分为： 输入型设备(例如光电输入机、键盘、鼠标器等)

输出型设备(例如打印机、绘图仪、显示器等)

输入/输出型设备(例如磁盘、磁带等)按设备的所属关系分类。(1)系统设备。系统设备是在系统生成时已登记于系统中的标准设备，属于系统的基本配置。如磁盘、打印机等。(2)用户设备。用户设备是在系统生成时未登记在系统中的非标准设备，通常这类设备是由用户提供的，并以适当的方式介绍给系统，以便操作系统对其实施统一的管理。按设备的信息交换的单位分类：(1)字符设备字符设备是以字符为单位进行输入和输出的设备。也就是说，这类设备每输入/输出一个字符就要请求CPU中断一次以处理，所以也叫做低速字符设备。卡片阅读机、纸带机、打印机、穿孔机等都属于低速字符设备。(2)块设备块设备的输入和输出是以数据块为单位的。数据块也叫物理块，在不同的系统中，数据块的大小不同，例如可在8~1024B的范围内变化。磁盘、磁带等都属于块设备。

按设备的共享属性分类。(1)独占设备所有的字符设备都是独占设备。独占设备是指一段时间内只允许一个用户(进程)访问的设备，即临界资源。(2)共享设备块设备都是共享设备。共享设备是指一段时间内允许多个进程同时访问的设备。当然，对于某一时刻而言，该类设备仍然只允许一个进程访问。(3)虚拟设备通过虚拟设备技术把一台独占设备变换为若干台逻辑设备，供若干个用户(进程)同时使用，以提高设备的利用率。5.1.2设备管理的任务和功能设备管理的主要任务如下：(1)选择和分配I/O设备以便进行数据传输操作。(2)控制I/O设备和CPU(或内存)之间交换数据。(3)为用户提供一个友好的透明接口，把用户和设备硬件特性分开，使得用户在编制应用程序时不必涉及具体设备，由系统按用户的要求来对设备的工作进行控制。另外，这个接口还为新增加的用户设备提供一个和系统核心相连接的入口，以便用户开发新的设备管理程序。(4)提高设备和设备之间、CPU和设备之间以及进程和进程之间的并行操作程度，以使操作系统获得最佳效率。设备管理程序的功能(1)提供进程管理系统的接口当进程要求设备时，该接口将进程的要求转达给设备管理程序。(2)进行设备分配选择某种调度策略，从设备等待队列中选择一个等待进程投入运行，将I/O设备及相应的设备控制器、通道分配给提出设备请求的进程，并将未获得分配的进程排入设备等待队列。当一个进程使用完一个设备后，系统应将此设备及时回收。对多个进程争用同一设备的情况，则要按照某种分配策略进行设备的分配。(3)实现设备和设备、设备和CPU等之间的并行操作这项功能需要系统中相应的硬件地支持。除了设备控制器之外，对应于不同的I/O控制方式，还需要有DMA控制器、I/O通道等硬件。在设备分配程序根据进程要求分配了设备、控制器和通道(或DMA控制器)等配件之后，通道(或DMA控制器)将自动完成设备和内存之间的数据传送工作，从而实现CPU和I/O设备的并行工作。在没有通道(或DMA控制器)的系统中，则由设备管理程序利用中断技术来完成上述并行操作。

(4)进行缓冲管理一般来说，CPU的执行速度和内存的访问速度都较高，而I/O设备的数据流通速度则低得多。为了缓解I/O设备和内存与CPU之间的速度不匹配的问题，系统中一般设有缓冲区来暂存数据。设备管理程序负责进行缓冲区分配、释放及有关的管理工作。(5)设备控制与驱动按照I/O控制方式，对不同的设备完成相应的I/O中断、设备控制、读写等I/O操作。并针对不同的设备请求，通过设备驱动程序完成对设备的直接控制。5.1.3缓冲技术在现代OS中，几乎所有的I/O设备在与处理机（内存）交换数据时，都使用了缓冲区。因为提高I/O速度和设备的利用率，在很大程度上都需要借助于缓冲技术来实现。缓冲管理的主要功能是组织好这些缓冲区，并提供获得和释放缓冲区的手段。

引入缓冲区的主要原因:缓和CPU与I/O设备间速度不匹配的矛盾。减少CPU的中断频率，放宽对CPU中断响应时间的限制。提高CPU和I/O设备之间的并行性。例如，在CPU和打印机之间设置了缓冲区后，便可使CPU和打印机并行工作。缓冲的分类 根据系统设置缓冲区的个数，可把缓冲分为单缓冲，多缓冲和缓冲池。单缓冲是在设备和处理机之间设置一个缓冲区。多缓冲是把多个缓冲区连接起来，这些缓冲区被分为两个部分：一部分专门用于输入，另一部分专门用于输出。缓冲池则是把多个缓冲区连接起来统一管理，缓冲池中的缓冲区既可用于输入又可用于输出。单缓冲：最简单。每当用户进程发出一I/O请求时，操作系统便在主存中为之分配一缓冲区，如图（a）。块设备：缓冲区用于暂存块设备输入的一块数据。数据块处理时间：Max(C,T)+M字符设备：缓冲区用于暂存用户输入的一行数据，或者输出一行数据到缓冲区。

双缓冲：也称为缓冲对换方式。在设备输入时，先将数据输入第一缓冲区，装满后便转入第二缓冲区；然后操作系统从第一缓冲区中取数据，等待CPU对数据进行计算。如图（b）。数据块处理时间：Max(C,T)

循环缓冲：当输入、输出或生产者--消费者的速度相差甚远时，双缓冲的效果则不够理想，但可以增加缓冲区数量而使情况有所改善。因此，引入了多缓冲，并将多缓冲组织成循环缓冲形式。如图（c）：缓冲池循环缓冲只适用于特定的I/O进程和计算进程，属于专用缓冲，显然若系统中进程数目很多，则需要很多这样的循环缓冲，这是不合理的，引入缓冲池（公用）。组成：三个队列：空缓冲队列emq、输入队列inq、输出队列outq。四种工作缓冲区：用于收容输入/出数据的工作缓冲区；用于提取输入/出数据的工作缓冲区。工作方式：先看示意图，在看下页文字说明收容输入工作方式：在输入进程需要输入数据时，便调用Getbuf(emq)过程，从emq队列的队首摘下一空缓冲区，把它作为收容输入工作缓冲区hin。然后，把数据输入其中，装满后再调用Putbuf(inq,hin)过程，将该缓冲区挂在输入队列inq的队尾。提取输入工作方式：当计算进程需要输入数据时，调用Getbuf(inq)过程，从输入队列取得一缓冲区作为提取输入工作缓冲区，计算进程从中提取数据。计算进程用完该数据后，再调用Putbuf(emq,sin)过程，将该缓冲挂到空缓冲队列emq上。

收容输出工作方式：当计算进程需要输出时调用Getbuf(emq)过程，从空缓冲队列emq的队首取得一空缓冲区，作为收容输出工作缓冲区hout。当其中装满输出数据后，又调用Putbuf(outq,hout)过程，将该缓冲区挂在outq末尾。提取输出工作方式：当要输出时，由输出进程调用Getbuf(outq)过程，从输出队列的队首取得一装满输出数据的缓冲区，作为提取输出工作缓冲区sout。在数据提取完后，再调用Putbuf(emq,sout)过程，将它挂在空缓冲队列的末尾。5.1.4设备驱动设备驱动程序又称为设备处理程序，它是I/O进程与设备控制器之间的通信程序，是一种低级的系统例程。设备驱动程序的主要任务是接受上层软件发来的抽象要求，如read或write命令，再把它转换为具体要求，发送给设备控制器。此外，它也将由设备控制器发来的信号传送给上层软件，从而完成两者间的相互通信。设备驱动程序的处理过程(1)将抽象要求转换为具体要求通常在每个设备控制器中都含有若干个寄存器，它们分别用于暂存命令、数据和参数等。用户及上层软件对设备控制器的具体情况毫不了解，因而只能向它发出抽象的要求(命令)，但这些命令无法传送给设备控制器。因此，就需要设备驱动程序将这些抽象要求转换为具体要求。(2)检查I/O请求的合法性对于任何输入设备，都是只能完成一组特定的功能，若该设备不支持这次的I/O请求，则认为这次I/O请求非法。(3)读出和检查设备的状态在启动某个独占设备进行I/O操作时，其前提条件应是该设备正处于空闲状态。因此在启动设备之前，要从设备控制器的状态寄存器中，读出设备的状态。只有设备处于就绪状态时，才能启动其设备控制器，否则只能等待。(4)传送必要的参数对于许多设备，除必须向设备控制器发出启动命令外，还需传送必要的参数。例如，在启动磁盘进行写之前，应将本次要传送的字节和数据要传送的内存始址，送入控制器的相应寄存器中。(5)工作方式的设置有些设备可具有多种工作方式，典型情况是利用RS-232接口进行异步通信。在启动该接口之间，应先按通信规程设定下述参数：波特率、奇偶校验方式、停止位数目及数据字节长度等。(6)启动I/O设备在完成上述各项准备工作后，驱动程序可以向控制器中的命令寄存器传送相应的控制命令。对于字符设备，若发出的是写命令，驱动程序将把一个数据传送给控制器；若发出的是读命令，则驱动程序等待接收数据，并通过从控制器中的状态寄存器读入状态字的方法，来确定数据是否到达。驱动程序发出I/O命令后，基本的I/O操作是在设备控制器的控制下进行的。通常，I/O操作所要完成的工作较多，需要一定的时间，如读/写一个盘块中的数据，此时驱动(程序)进程把自己阻塞起来，直到中断到来才被唤醒。5.2数据输入输出控制方式5.2.1程序直接控制方式5.2.2中断控制方式5.2.3DMA方式5.2.4通道控制方式5.2.1程序直接控制方式在处理机向设备控制器发出一条I/O指令启动输入设备输入数据时，要同时把状态寄存器中的忙/闲标志busy置1，然后便不断的循环测试busy。当busy=1时，表示输入机尚未输完一个字（符），处理机应继续对该标志进行测试，直至busy=0，表明输入机已将输入数据送入控制器的数据寄存器中，于是处理机将数据寄存器中的数据取出，送入内存指定单元中，接着，再启动去读下一个数据，并置busy=1。5.2.2中断控制方式

当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务。设备控制器按照该命令的要求去控制指定的I/O设备，此时，CPU和I/O设备并行操作。数据进入数据寄存器之后，控制器通过控制线向CPU发送中断信号，由CPU检查输入是否出错，若无错，便向控制器发送取走数据的信号，然后再通过控制器及数据线将数据写入指定的内存单元。5.2.3DMA方式特点：数据传输的基本单位是数据块；所传送的数据是从设备直接送入内存的；仅在传送下一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成的。

控制/状态寄存器CR

内存地址寄存器MAR

数据缓冲寄存器DR

数据计数器DC

DMA控制器中设置四类寄存器：以磁盘读入数据为例。当CPU要从磁盘读入数据块时，便向磁盘控制器发送一条读命令，该命令被送入其中的命令寄存器CR中。同时，还需将本次要将数据读入的内存起始目标地址送入内存地址寄存器MAR中；本次要读的数据的字（节）数则送至数据计数器DC中，还需将要从中读取数据的磁盘源地址，直接送至DMA控制器的I/O控制逻辑上。然后启动DMA控制器进行数据传送，以后，CPU便可去处理其它任务，整个的数据传送便由DMA控制器进行控制。5.2.4通道控制方式是DMA方式的延伸。引入：把对一个数据块的读（或写）为单位的干预，减少为对一组数据块的读（或写）及有关的控制和管理为单位的干预，可实现CPU、通道和I/O设备三者的并行工作，从而有效的提高了整个系统的资源利用率；通道程序： 通道是通过执行通道程序，并与设备控制器来共同实现对I/O设备的控制的。通道程序是由一系列的通道指令所构成。通道控制方式的数据输入处理过程：当进程要求设备输入数据时，CPU发start指令指明I/O操作、设备号和对应通道。对应通道接收到CPU发来的启动指令start之后，把存放在内存中的通道指令程序读出，并设置对应设备的I/O控制器中的控制状态寄存器。设备根据通道指令的要求，把数据送往内存中指定区域。若数据传送结束，I/O控制器通过中断请求线发出一个中断信号，请求CPU做中断处理。中断处理结束后CPU返回被中断进程处继续执行。

补充：磁盘设备的特性及其调度只有内存才可以被CPU直接访问，而磁盘存储器是作为一种设备，由CPU通过访问磁盘控制器来实现对它的访问。一、磁盘简介

1、磁盘系统的组成：磁盘+驱动机构+磁盘控制器

格式化后盘片的俯视示意图，可以清楚的看到盘片被化分成等分的扇区（实际扇区当然比这密得多）中心圆孔扇区间隙最外缘的磁道为0磁道，向中心靠近的第二条磁道为1磁道，依次类推扇区界限标志，存放标识扇区的编号地址等信息。存储数据2、磁盘盘面的基本构造固定头磁盘：固定头磁盘是每个磁道都有一个磁头，这种磁盘的磁道转速快，但价格较贵主要用于大容量磁盘上。移动头磁盘：每个盘面只有一个磁头，此磁头在径向移动以存取不同磁道上的信息，需要磁头控制部件支持，造价较低，广泛应用于中小型磁盘设备。温彻斯特盘，移动头磁盘，简称温盘。其它划分：软盘+硬盘单片盘+多片盘（如A盘分单面和双面）3、磁盘分类磁头移动到指定柱面的机械运动时间m—常数n—磁道数。因为磁头移过每一条磁道的时间是相同的，所以可以用磁道数来模拟s—磁臂启动时间1、磁头定位时间（寻道时间、柱面定位时间）二、温盘的磁盘访问时间Ta构成磁盘旋转到指定扇区的机械运动时间；它与磁盘转速相关，如：软盘转速可为600rpm(每分钟转速)，硬盘可为7200—15000rpm2、扇区定位时间（即旋转延迟时间）3、实际信息传输时间从指定扇区读写数据的时间。由于柱面定位时间在访问时间中占主要部分，合理组成磁盘数据的存储位置可提高磁盘I/O性能。4、例题精选：读一个128KB大小的文件：例1设文件由8个连续磁道(每个磁道32个扇区)上的256个扇区构成：若柱面定位时间为20ms，旋转延迟时间为8.3ms，32个扇区数据传送时间为16.7ms。则总时间为：20ms+(8.3ms+16.7ms)*8=220ms例2文件由256个随机分布的扇区构成，每个扇区数据传送时间为0.5ms。则总时间为：（20ms+8.3ms+0.5ms)*256=7373ms;★随机分布时的访问时间为连续分布时的33.5倍。可见，适当地集中数据存放，将有利于提高传输效率。（例如，系统工具提供的磁盘碎片整理工具）三、硬盘的调度

应采用一种合适的调度算法来使各进程对磁盘的访问时间最小，考虑到在访问磁盘的过程中，主要是磁头的移动，即寻道时间，所以：磁盘调度的目标：就是使磁盘的平均寻道时间最少；寻道时间的衡量指标：磁头移动的磁道数来衡量。FCFS算法：根据进程请求访问磁盘的先后次序来进行调度；最短寻道时间优先算法SSTF（ShortestSeekTimeFirst）：其要求访问的磁道与当前所在的磁道距离最短；扫描算法（SCAN）：与当前磁道距离最近，并且是在当前扫描方向上的；循环扫描算法（CSCAN）：规定磁头单向扫描，然后立即返回重新开始。磁盘调度算法四、硬盘高速缓存

磁盘I/O速度远低于内存的访问速度，通常低4-6个数量级。提高磁盘I/O速度的最主要的技术便是采用磁盘高速缓存：利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。逻辑上属于磁盘，物理上驻留在内存。5.3文件管理概述计算机系统中所使用的数据要以文件的形式存放到外存，所以对数据的使用需要涉及到文件的逻辑组织（面向用户）以及文件在外存上的组织形式（物理组织，面向系统），因此操作系统给我们提供了文件管理功能。5.3.1文件类型和文件属性5.3.2文件系统的功能5.3.1文件类型和文件属性1.文件的类型(1)按用途分类①系统文件：是指系统软件构成的文件。②库文件：是指由系统提供给用户使用的各种标准过程、函数和应用程序文件。这类文件允许用户调用执行，但不允许用户修改。③用户文件：是指用户委托文件系统保存的文件。如源程序、目标程序、原始数据等。这类文件只能由文件所有者或所有者授权用户使用。(2)按保护级别分类①只读文件：允许所有者或授权用户对文件进行读，但不允许改写。②读写文件：允许所有者或授权用户对文件进行读写，但但禁止未核准用户读写。③执行文件：允许核准用户调用执行，但不允许对它进行读写。④不保护文件：不加任何访问限制的文件。(3)按数据形式分类①源文件：是指由源程序和数据构成的文件。通常由终端或输入设备输入的源程序和数据所形成的文件都属于源文件。源文件一般由ASCII码或汉字组成。②目标文件：指源文件经过编译以后，但尚未链接的目标代码形成的文件。目标文件属于二进制文件。③可执行文件：编译后的目标代码经链接程序链接后形成的可以运行的文件。(4)按文件性质分类①普通文件：一般的系统文件及用户文件。②目录文件：文件目录组成的文件。③特殊文件：将设备看成是特殊文件。2.文件的属性①文件类型：表示文件的所属类型。如文本类型、图像类型、应用程序类型等。②文件长度：记录文件的大小。③文件的位置：表示在哪个设备或设备的什么位置可以找到它或存放它。④文件的存取控制：表示对文件的读、写或执行等的控制。⑤文件的建立时间：记录文件最后一次的修改时间。5.3.2文件系统的功能1.文件存储空间的管理，即磁盘的管理；2.目录管理：允许用户用符号名访问文件，并实现文件共享；3.文件的读／写管理；4.提供有效的存取控制功能。5.4文件的逻辑结构可以用两种不同的观点去进行研究文件结构：用户观点是研究用户“思维”中的抽象文件，或称逻辑文件，其研究的侧重点在于为用户提供一种逻辑结构清晰、使用简便的逻辑文件形式。用户将按照这种形式去存储、检索和加工有关文件中的信息。实现观点是研究驻留在设备“介质”中的实际文件，或称物理文件。它研究的侧重点是选择一些工作性能良好、设备利用率高的物理文件形式。系统将按照这种形式同外部设备打交道并控制信息的传输。文件的逻辑结构可以分为两种形式：一种是无结构的流式文件一种是有结构的记录式文件流式文件是由一系列字符组成的无结构文件，其内部信息不再划分结构，整个文件就是一个不可分割的整体，每次读写访问流式文件可以指定任意数据长度，是当前操作系统中常用的文件组织形式。如源程序文件、可执行文件常采用这种结构形式。

记录式文件是一种有结构的文件，它由一组相关记录组成。记录式文件记录的是若干个对象的具体描述，每个对象的具体描述占用一条记录，而记录是一个具有特定意义的信息单位。记录式文件又可分为等长记录文件和变长记录文件，等长记录文件记录的长度相等，变长记录文件中记录的长度可以不相等。

定长记录文件示例例如:学生登记表文件xsdjb.dbf姓名学号籍贯通信地址邮政编码李铭925678武昌武昌关山街125号430074马乐925679北京北京海军路88号100034记录式文件的分类顺序文件。文件体中的记录长度大小相同，并按某个关键字项排序了的等长记录文件叫顺序文件。索引文件。索引文件的每个索引项指向一条记录，记录大小不必相同，记录按输入次序排列，不必排序，索引项按照记录中的某个关键字项排序。对同一个文件，可以针对不同的关键字项建立多个索引。索引文件的记录项通常较小，查找速度快，便于随机访问。索引顺序文件。在顺序文件的基础上，另外建立索引文件，此即索引顺序文件5.5外存分配方式一个文件存储介质，格式化后就分成许多大小相等的单位－－存储块（物理盘块），在现代计算机系统中，一般来说，每个物理块是一个磁盘的扇区，512字节。并给每个存储块有个编号，称为物理块号。文件的物理结构指文件在存储介质上的结构，目前有三种基本结构，即连续文件结构链接文件结构索引文件结构1、连续文件 连续分配是最简单的磁盘空间分配策略，该方法要求为文件分配连续的磁盘区域。 连续分配的优点是，知道文件物理存储位置的起始块号和文件的长度后就能快速存取，文件存取的速度比其他方法要快。其主要缺点是容易产生碎片问题，需要定期进行存储空间的紧缩。2.链接分配对于文件长度需要动态增减及用户不知道文件有多大的情况，往往采用链接分配法。文件的连接分配是用非连续的物理块来存放信息，物理块之间没有物理块号的顺序要求，其中每个物理块中有一个指针指向下一个连接的物理块，从而使存放该文件的物理块连接成一个链接队列，文件的最后一个物理块的指针标记为“∧”，表示文件至本块结束。(1)以扇区为单位的链接分配按文件的要求分配若干个磁盘扇区，这些扇区在磁盘上可以不相邻，属于同一个文件的各扇区按文件记录的逻辑次序用链接指针连接出来。链接分配的优点是消除了碎片问题，能提高效率地利用外存空间，易于对文件进行扩充，调整指针可实现删除或插入物理快的操作。链接分配的缺点是只能按队列中的指针顺序搜索，效率较低，同时链接指针的维护有一些开销，且链接指针也要占用存储空间。链接分配只能采用顺序存取方式，不宜随机存取。链接分配有以下两种实现方案：(2)以区段为单位的链接分配

这是一种广为使用的分配策略，其实质是连续分配和非连续分配的结合。在每个区段内采用连续分配，区段间则采用链接分配或后面介绍的索引分配。区段是由若干个(在一个特定系统中其数目是固定的)连续扇区组成的存储块。这种分配策略集中了连续分配与非连续分配的优点，所以广为使用。

3.索引分配在索引分配方式中，系统为每个文件分配一个索引块，索引块中存放索引列表，索引表中存放的是分配该文件的物理号。文件目录中只需要记录索引块的块号即可。如果需要访问文件中的某一个记录时，则不需从第一个物理块开始按链接指针依次进行查找，从而提高了查找速度。索引分配方式不仅支持直接访问，而且不会产生碎片现象，文件长度受限的问题也得到了解决。其缺点是由于索引块的分配增加了系统存储空间的开销。索引块的大小选择是个很重要的问题，为了节约磁盘空间，希望索引块越小越好，但索引块太小又无法支持大文件。该分配方式存取文件需要两次访问外存。首先要读取索引块内容，然后再访问存放文件的物理块，因而降低了文件的存取速度。为了提高速度，可以在访问文件时将索引表调入内存中，这样文件的存取就只需要访问外存一次。当文件很大时，索引表也会很大，如果索引表大到一个索引块装不下时，可以将索引表本身作为一个文件，再为它建立一个“索引表”，从而构成了二级索引。（UNIX系统文件映射）补充：文件存储空间的管理无论是程序还是数据，所有信息都是以文件形式存放在外存上。外存上文件存放的空间也叫作“文件存储空间”。文件存储空间是系统与多个用户共享的资源，用户只要给出文件名就可以实现按名存取。系统将外存空间分成若干大小相等的物理块，以块为单位来交换信息。因此，需要对外存的物理块进行管理。比如，建立空闲管理表，标出哪些块正在使用，以便建立文件时能迅速、合理、方便地找出空白存储块进行分配。将文件释放出来的存储块回收，归还给系统。文件存储空间的管理，实际上就是一个空闲块的组织和管理问题。三种常用的管理方法：空闲块表或空闲块链，位示图，空闲块成组链接法与可变分区存储管理方式中的空闲块表和空闲块链是完全相似的。空闲块表表目的内容至少包括：第一空白块地址（物理块号）、空白块个数。一、空闲块表和空闲块链

1、空闲块表

空闲块表适合于连续组织的文件，因为在分配文件时按文件尺寸申请一组连续的空闲块，撤消文件时归还这组连续的空闲块区。与可变分区分配算法相似，可采用最先适应、最坏适应、最佳适应算法。由于空闲块区的个数是动态改变的，导致空闲块表目个数不能预先确定，因此可能会产生表目溢出(表较小时)或表目浪费(表较大时)。分配：当请求的块数正好等于表目中的块数时，就把这些块全部分配给该文件并把该项标记为空项。如果该项中的块数多余请求的块数，则把多余的块号留在表中，并修改该表中的各项。回收：如果被释放的物理块号与某一目录项中的物理块号相邻，还要进行合并空白文件。空闲块链把文件存储设备上的所有空闲块连接在一起，这是非连续结构。适用于各种物理组织的文件。注意，对空闲块链操作时应互斥。当需要分配空白块时从链首进行，所以在主存中要保存一个链首指针，它指向第一个空白块，当回收时，把回收块挂在空白块链尾上。

2、空闲块链位示图是外存空间的存储映射图。位示图是系统在内存中划分出的若干字节的集合，用来指示磁盘存储情况。位示图中的每一位（bit）对应外存空间的一个物理块。若该位为“1”，表示对应块被占用；若该位为“0”，表示对应物理块空闲。设整个文件空间有n块，那么可用n位构成位示图二、位示图（bitmap）例：设想一个磁盘组共有16个柱面，每个柱面有16个磁头寻道，每个磁道分为16个扇区，那么整个磁盘空间的扇区数为：

16*16*16=4096（个）如果一个扇区被定义为一个存储块，那么，用字长位16位的存储单元来构造位示图，共需要256个字。0位1位15位4095位0/10/10/1………分配：顺序扫描位示图，找到一组为０的盘块，将其转换成对应的盘块号，并置状态为1。回收：将盘块号转换成行号和列号，修改状态为０。注意：系统工作时位示图应驻留主存，但必须定时地把主存中的位示图复制到外存保存。这样，万一文件系统发生故障，可以依据外存的位示图副本修复文件系统。三、成组链接法1、UNIX系统采用空闲块成组链接法对磁盘空间的空闲块加以组织2、思路：100个空闲块划归1组，将各组中的盘块号存放在其前组中的第1个空闲块中，第1组的空闲盘块号放入系统专用的超级块(superblock)中。

最后组99块，第1组不足100块，其他各组均为100块。文件存储空间不会恰好为100的整数倍，所以第1组小于100。各组(最后组除外?)第1块和超级块内设置一个容量为100