操作系统OS笔记2
调度和死锁
调度简介
1. 调度的基本概念
2. 调度原则
调度算法
平均周转时间：
平均带权周转时间：周转时间/服务时间
1. 先来先服务调度算法（FCFS）
当在高级调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。
该算法比较有利于长作业(进程)，而不利于短作业(进程)。
只考虑作业等待时间，忽视作业计算时间
2. 短作业（进程）优先调度算法（SJF）
按照进入系统的作业所要求的CPU运行时间的长短为挑选依据，优先选取预计计算时间最短的作业。可以分别用于高级调度和低级调度。
短作业优先的调度算法从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它。
SJF调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。
不足之处是长作业的运行得不到保证，不能保证紧迫性作业(进程)会被及时处理…
考虑作业预计的计算时间，忽视作业的等待时间。
3. 优先级算法
根据事先设定好的进程的优先级来选取就绪队列中优先级最高的进程投入运行。
（出现两种系统策略：抢占式和非抢占式调度）
（优先级划分的两种方法：静态优先级、动态优先级）
4. 时间片轮转算法
将CPU分配给就绪队列中的第一个进程，每次分配一个时间片。但时间片耗尽时，如果进程未完成，则让出处理机，转到就绪队列的队尾，等待下一轮的时间片的分配。
在时间片轮转算法中，时间片的大小对系统性能有很大的影响
一个较为可取的大小是时间片略大于一次典型的交互时间，这样可使大多数进程在一个时间片内完成
5. 最高响应比优先调度算法
兼顾作业的等待时间和处理时间，做有效的协调和折中，既能照顾短作业的调度，同时也不会让长作业等待的时间超出合理的范围。
缺点：计算每个作业的响应比需要耗费一定的时间，性能比短作业优先算法略差。
最高响应比优先算法性能介于先来先服务算法和短作业优先算法之间。
6. 多级反馈队列
(1) 设置多个就绪队列。为每个队列设置不同的优先级，第一个队列优先级最高，第二个次之，其余队列优先级逐个降低。
(2) 每个队列都采用FCFS算法。
(3) 按队列优先级调度，先调度第一个就绪队列，为空时，再调度第二个，依次类推。每个进程执行一次时间片之后加入下一个就绪队列，如到达最后第n个就绪队列还没结束，则按照时间片轮转调度算法进行调度。
7. 实时调度算法
根据实时任务性质，可将实时调度的算法分为硬实时调度算法和软实时调度算法
根据调度方式，则可分为非抢占调度算法和抢占调度算法。
死锁简介
1. 资源
2. 死锁产生的原因和必要条件
（1）定义
所谓死锁 (Deadlock)，是指多个进程因竞争资源而造成的一种僵局(Deadly-Embrace)，若无外力作用，这些进程将永远不能再向前推进。
（2）产生原因
①资源竞争：当系统中供多个进程共享的资源如打印机，其数目不足以满足诸进程的需要时，会引起诸多进程对资源的竞争而产生死锁；
②进程推进顺序不当：进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。
（3）必要条件
①互斥: 进程对所分配到的资源必须独立使用，即在一段时间内某资源只由一个进程占用，不能共享。
②请求和保持：进程已经持有了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已获得的其它资源保持继续持有。
③不可剥夺: 在未使用完之前，不能剥夺进程已获得的资源，只能在使用完时由自己释放。
④循环等待：在发生死锁时，必然存在一个进程和进程之间等待相互资源的环形链。使得链中每个进程的资源需求都得不到满足。
3. 死锁的表示方法和判定
处理机调度与死锁
死锁预防
死锁避免
死锁避免通过合理的资源分配确保不会出现循环等待的条件，除了能够避免死锁，还能够支持进程的并发及资源的合理使用。且过程动态，无强制和预先设置的规则。
1.安全状态
安全状态是指系统能按某种顺序如<P1,P2,…PN>（称为安全序列）为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。
若系统不存在这样一个安全序列，则称系统处于不安全状态。
避免死锁的实质是：如何使系统不进入不安全状态。
2.银行家算法数据结构、流程
（1）数据结构
① 可利用资源向量Available。该向量为一个数组，含有m个元素，每一个元素代表一类可利用的资源数目。将系统中所配置的该类全部可用资源的数目设置为初始值，随着该类资源的分配和回收，其数值会动态的发生改变。系统中第j类资源有K个，能用以下式子表示：Available[j]=K。
② 最大需求矩阵Max。该矩阵大小为n×m，表示系统中n个进程中的每一个进程对m类资源的最大需求。进程i需要第j类资源的最大数目为K，能用以下式子表示：Max[i,j]=K。
③分配矩阵Allocation。该矩阵大小为n×m的矩阵，表示系统中每一类资源当前已分配给每一个进程的资源数。进程i当前已分得第j类资源的数目为K，可以表示成 Allocation[i,j]=K。
④需求矩阵Need。该矩阵大小依然为n×m，表示每一个进程还需要的各类资源数。进程i还需要第j类资源K个，可以表示为：Need[i,j]=K。
其中后三者之间存在如下关系：
Need[i, j] = Max[i,j] - Allocation[i, j]
（2）流程
设Request i是进程Pi的请求向量，如果Request i[j]=K，表示进程Pi需要K个R j类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
① 如果Request i[j] ≤ Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
②如果Requesti[j] ≤ Available[j]，转向步骤(3)；否则表示尚无足够资源，Pi等待。
③ 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available[j] := Available[j] - Request i[j]；
Allocation[i,j] := Allocation[i,j] +Request i[j]；
Need[i,j] := Need[i,j] - Request i[j]；
④ 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。
安全，正式将资源分配给进程Pi，完成本次分配；否则，本次试探分配作废，恢复原来的资源分配状态，进程Pi等待。
3.安全性算法
死锁检测和恢复
内存管理
概述
1. 存储层次结构
2. 存储管理的目的和任务
地址重定位
1. 重定位的基本概念
2.补充：程序的装入、程序的链接
分区存储管理
1. 单一连续、固定分区、可变分区分配
2. 分区分配算法
（1）首次适应算法
内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲区为止。
该算法倾向于优先利用内存中低址部分的空闲区，高址部分的很少利用，从而保留了高址部分的大空闲区，为以后到达的大作业分配大的内存空间创造了条件。但低址部分留下许多难以利用的很小的空闲区 ，每次查找又都从低址部分开始，增加了查找开销。
（2）最优（佳）适应算法
指每次为作业分配内存时，总是把既能满足要求又是最小的空闲分区分配给作业，避免“大材小用”。为加速查询，该算法要求将所有的空闲区按其大小以递增的顺序链接成一空闲区链。这样第一次找到的满足条件空闲区必为最优。
每次分配后所切割下的剩余部分总是最小的，存储器中会留下许多难以利用的小空闲区。
（3）最差适应算法
在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。
该算法要求将所有空闲分区，按容量从大到小的顺序，形成一空闲分区链，查找时，只要看第一个分区能否满足作业要求即可。
（4）循环首次适应算法（由首次适应算法演变而来）
分配内存时，不再每次从链首开始查找，而是从上次找到的空闲分区的下一空闲分区开始查找，直到找到第一个能满足要求的空闲分区，从中划出一块所请求大小的内存空间。
该算法能使内存中的空闲分区分布得更均匀，减少查找空闲分区的开销，但这会缺乏大的空闲分区。
（5）快速适应算法（基于索引）
该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表的表头指针。
3. 补充：哈希算法、伙伴系统
存储器管理
存储器的层次结构在一定程度上解决了主存和CPU速度不匹配的矛盾，提高了系统的工作效率。同时，在对主存的管理过程中，用到了分区存储管s理、页式存储管理、段式存储管理等管理手段，来提高对主存的访问速度。
页式存储管理
1. 页、块、页表、地址结构、分页地址变换、快表
（1）页（页面）：分页存储管理方式的基本单位
将用户程序的地址空间划分成的若干个固定大小的区域称作页。
（2）块：相应地，内存空间也被划分成若干个物理块。
页和块的大小相等，典型大小为1KB。这样，用户程序的任意页可放在内存的任一块。
（3）地址结构
页号P：表示属于哪一页。
页内地址W：在页内的地址，其长度表示每一页的大小。
（4）页表：存储分配时，允许将进程的各个页离散地存储在内存中不同的物理块中，但系统应能保证进程的正确运行。
页表包括 ①页号：进程各页序号 ②物理块号：进程各页对应存放内存中的物理块块号
（4）地址变换过程：基本任务是实现逻辑地址到物理地址的转换。
实际上是将逻辑地址中的页号，转换为内存中的物理块号。
地址变换任务是借助于页表来完成的。
物理地址 = 物理块号页面大小 + 页内地址
（5）快表：地址变换机构中增设的一个称为快表的高速缓冲存储器，用以存放当前访问的页表项。能提高地址变换速度，
2. 两级页表、多级页表
段式与段页式存储管理
1. 段、段表、地址结构、分段地址变换
（1）段：分段存储管理方式的基本单位
把用户程序的地址空间分成若干个大小不等的段，每段可定义一组相对完整的逻辑信息。
（2）段表：段页式存储管理中段表内容是 页表始址 和 页表长度 ，与分段式系统不同。
（3）地址结构：段页式地址结构包括 ①段号 ②段内页号 ③页内地址
2. 分页和分段的区别
（1）如果离散分配的基本单位是页，则称为分页存储管理方式；
如果离散分配的基本单位是段，则称为分段存储管理方式。
3. 段页式存储管理
（1）定义：分页和分段两种存储管理方式相结合的产物。
（上图展示为利用段表和页表实现地址映射）
内存扩充技术
1.覆盖、交换
内存管理
虚拟存储管理
1. 基本原理：局部性原理、虚拟存储器
2. 请求分页存储管理
3. 页面置换算法
（1）进程逻辑空间为n页，系统为其分配的内存物理块数为m，运行过程中访问页面成功次数为S , 失败次数为F
该进程总页面访问次数： A = S + F
缺页率： f = F / A
（2）最佳置换算法 （OPT）
实际应用中无法实现
（3）先进先出置换算法 （FIFO）
（4）最近最久未使用置换算法 （LRU）
（5）第二次机会置换算法 （SC）
检查最老页面的R位。如果R位是0，那么这个页面既老又没有被使用过，可以立刻置换掉；如果是1，就将R位清0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续搜索。（对FIFO算法的修改）
（6）时钟页面置换算法 （Clock）
把所有的页面都保存在一个类似钟面的环形链表中，用一个表针指向最老的页面。
当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。
4. 请求分页存储管理系统性能分析：缺页率、抖动、页面大小
5. 请求分段存储管理
设备管理
概述
1. 设备管理的目标和任务
2. I/O系统结构
3. I/O设备分类
I/O系统控制方式
尽量减少CPU对I/O控制的干预，把CPU从繁杂的I/O控制事务中解脱出来，以便更多地去完成其它数据处理任务
1. 程序直接控制方式
主机和I/O设备交换信息
由CPU通过程序来直接控制处理器和外围设备之间的信息传送
准备就绪时，CPU将从I/O接口中把数据取出，送入内存指定单元，一个字一个字地传送，直至整个数据块的数据全部传送结束，CPU又重新返回到当前程序
用户程序需要启动I/O设备工作时，CPU向I/O设备发送一条指令，不断地循环测试I/O设备是否准备就绪
CPU和I/O设备处于串行工作状态，导致CPU工作效率不高
2. 中断控制方式
处理机和设备交换信息。
（在程序直接控制的基础上添加中断，实现了CPU与I/O的设备并行操作）
CPU与I/O设备并行操作，只有当输入完一个数据才需要CPU花费时间去处理中断请求
当用户程序需要启动某个I/O设备工作时，CPU向I/O设备发送一条指令，然后立即返回继续执行原来的任务
缺点：容易发生多次中断，这将消耗大量CPU处理时间；可能导致CPU无法响应中断和出现数据丢失的现象
3. DMA控制方式
内部和外部I/O设备交换信息
（1）DMA控制方式的特点
①数据传输的基本单位是数据块，而不是字。
②所传输的数据是从I/O设备直接读入主存，或者从主存直接传输到I/O设备。
③只有在一次传输操作的开始或者结束时，才需要CPU干预，在传输的过程中，无需CPU的干预，都是在DMA控制器的控制下完成的。
（2）DMA控制器
组成：①处理器与DMA控制器的接口 ②DMA控制器与块设备的接口 ③I/O控制逻辑
（3）缺点
CPU每发出一条I/O指令，也只能去读（写）一个连续的数据块，当系统需要一次读多个数据块且将它们分别传送到不同内存区域，或者相反时，则需由CPU分别发出多条I/O指令及进行多次中断处理才能完成
（4）DMA的配置方法
①单总线、分离的DMA ： CPU、DMA控制器和所有的外部I/O模块共享一个系统总线，DMA模块代替CPU来处理内存与I/O模块之间的数据交换。额外开销较小，但是效率较低。
②单总线、集成的DMA-I/O ： 通过把DMA和I／O功能集中起来，很大程度上减少数据传送所需的总线周期数。
③I／O总线的DMA配置 ： 使用一个I/O总线连接I/O模块和DMA模块，从而使DMA模块中I/O接口的数目减少到一个。
4. 通道控制方式
内存和I／O设备交换信息
（1）通道控制方式是一种以内存为中心，实现设备和内存直接交换数据的控制方式
（2）与DMA方式不同，通道直接控制数据传送的方向、存放数据的内存起始地址以及传送的数据长度
（3） 通道控制方式能够控制多台I/O设备与内存进行数据交换，能够进一步减轻CPU的工作负担，增加了计算机系统的并行工作程度
（4）实现CPU、通道和I/O设备三者的并行操作
输入输出系统
I/O软件的组成
1. I/O软件设计目标和原则
2. I/O软件结构
3. 设备驱动程序
4. I/O设备控制方式
5. 设备无关软件
6. 用户层软件：SPOOLing技术的引入、组成和特点
具有通道的设备管理
1. 通道类型
（I/O通道：又称作I/O处理器，它是一种特殊的处理器，具有自己的指令系统）
（1）字节多路通道（Byte multiplexor channel）
一种按字节交叉方式工作的通道。它通常都含有许多非分配型子通道。每个子通道都连接一台I/O设备，并控制该设备的I/O操作；另外还存在一个主通道，采用时间片轮转法轮流为各子通道服务，（即当某个子通道控制其I/O设备完成一个字节的交换后，便立即让出主通道，以供下一个子通道使用）。多个子通道之间轮流共享主通道。
子通道通常连接的都是低速I/O设备，如行式打印机等。
（2）数组选择通道（Block selector channel）
该通道传输速率高，可以连接多台高速设备。
但通道利用率较低，一段时间内只能执行一道通道程序，控制一台设备进行数据传送。
（3）数组多路通道（Block multiplexor channel）
数组多路通道是将数组选择通道传输速率高和字节多路通道能使各子通道分时并行操作的优点相结合而形成的一种新通道。
数组多路通道数据传输按数组方式进行，含有多个非分配型子通道，因而这种通道不但具有很高的数据传输速率，而且能获得令人满意的通道利用率。
数据多路通道适用于连接高、中速的I/O设备。
设备管理相关技术
1. DMA
2. 缓冲技术：单缓冲、双缓冲、循环缓冲区和缓冲池
磁盘存储管理
1. 磁盘简述：磁盘的定义、组成、磁盘访问时间
（1）磁盘：一种直接存取存储设备，又叫随机存取存储设备
柱面号、磁头号、扇区号可表示磁盘上每一磁盘块的唯一地址
（2）组成：在一个盘片上的读写磁头的轨迹称磁道，在磁头位置下的所有磁道组成地圆柱体称柱面，一个磁道又可被划分成一个或多个物理块，物理块又称为扇区。
磁盘存储容量 = 磁头数 x 磁道（柱面）数 x 每道扇区数 x 每扇区字节数
（3）磁盘访问时间
①寻道时间（Seek time）：磁头定位到磁道所需的时间。
启动磁头的时间s与磁头移动n条磁道所花费的时间之和。 m是一常数，与磁盘驱动器的速度有关。
T = m x n + s
②旋转延迟（Rotational delay）时间：磁头到达扇区开始位置的时间。
③存取时间（Access time）：寻道时间和旋转延迟时间的总和，这是达到读或写位置所需的时间。
④传送时间（Transfer time）：一旦磁头定位完成，磁头就通过下面旋转的扇区，开始执行读操作或写操作，这正是操作的数据传送部分。传输所需的时间即传送时间。
T = b / r N
b：传送的字节数 N：一个磁道中的字节数 r：旋转速度
2. 磁盘调度C-SCAN、N步扫描、F-SCAN
（1）先来先服务（First come first served, FCFS）
根据进程请求访问磁盘的先后次序进行调度，不会出现某一进程请求长期得不到满足的情况
算法未对寻道进行优化，平均寻道时间较长。
该算法适用于请求磁盘I/O的进程数目较少的情况
（2）最短寻道时间优先（Shortest seek time first, SSTF）
要求访问的磁道与当前磁头所在的磁道距离最近，以便每次的寻道时间最短
但这种算法不能保证平均寻道时间最短，且会导致某个进程发生饥饿现象
（3）扫描（SCAN）算法 （又称电梯调度算法。）
不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向
所考虑的下一个访问的磁道满足既在当前磁道之外，又是距离最近的
自里向外访问，直至再无更外的磁道需要访问，或者它到达这个方向上的最后一个磁道时，才将磁头转换方向，变为自外向里移动
（4）循环扫描（C-SCAN）算法
SCAN算法既能获得较好的寻道性能，又能防止饥饿现象，但存在如下问题：当磁头从里向外移动刚刚越过了某一磁道时，恰好又有一进程请求访问该磁道，此时进程只能等待。磁头继续从里向到达最后一个访问的磁道，转向后从外向里扫描完所有要访问的磁道后，才能处理该进程的请求。
C-SCAN算法规定磁头单向移动。
当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问的磁道。
将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。
（5）N-step-SCAN算法
磁盘请求队列被分成多个段，每次只有一个段被完全处理
把磁盘请求队列分成长度为N的子队列，每一次用SCAN处理一个子队列
较大的N值，N-step-SCAN的性能与SCAN接近
N = 1时，就是FCFS
（6）F-SCAN算法
实质上是N步SCAN算法的简化
F-SCAN只将磁盘请求队列分成两个子队列，一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理
新到达的的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列
所有的新请求都将被推迟到下一次扫描时处理
文件管理
概述
1. 文件、文件系统的定义
（1）文件管理系统 （文件系统）
文件系统：操作系统中负责管理和存储文件信息的软件模块
文件系统由三部分组成：与文件管理有关软件、被管理文件以及实施文件管理所需数据结构。
（2）文件
文件：具有文件名的若干相关元素的集合。
（3）文件类型
①按用途分类
A. 系统文件，这是指由系统软件构成的文件。大多数的系统文件只允许用户调用，但不允许用户去读，更不允许修改；有的系统文件不直接对用户开放。
B. 用户文件，指由用户的源代码、目标文件、可执行文件或数据等所构成的文件。用户将这些文件委托给系统保管。
C. 库函数文件，这是由标准子例程及常用的例程等所构成的文件。这类文件允许用户调用，但不允许修改。
②按组织形式分类
A. 普通文件。普通文件主要是指文件的组织格式为文件系统所规定的最一般格式的文件，例如由字符流组成的文件。
B. 目录文件。目录文件是由文件的目录构成的特殊文件，是用来管理和实现文件系统功能的系统文件。
C. 特殊文件。特指系统中的各类I/O设备。这些特殊文件的使用是和设备驱动程序紧密相连的。操作系统会把对特殊文件的操作转成为对应设备的操作。
③按数据类型分类
A. 源文件，这是指由源程序和数据构成的文件。通常，由终端或输入设备输入的源程序和数据所形成的文件都属于源文件。它通常是由ASCII码或汉字所组成的。 B. 目标文件，这是指把源程序经过编译程序编译过，但尚未经过链接程序链接的目标代码所构成的文件。目标文件所使用的后缀名是“.obj”。
C. 可执行文件，这是指把编译后所产生的目标代码经过链接程序链接后所形成的文件。其后缀名是 .exe。
④按存取控制属性分类
A. 只执行文件，该类文件只允许被核准的用户调用执行，不允许读和写。
B. 只读文件，该类文件只允许文件主及被核准的用户去读，不允许写。
C. 读写文件，这是指允许文件主和被核准的用户去读或写的文件。
文件结构
1. 逻辑结构
（1）定义
逻辑结构是指一个文件在用户面前所呈现的形式，它主要为用户提供一种逻辑结构清晰、使用简便的逻辑文件，用户将按这种形式去存取、检索和加工文件。
（2）分类
①无结构的字符流式文件：这是一种无结构文件，构成文件的基本单位是字符，文件是有逻辑意义的、无结构的一串字符的集合，其内部不再划分结构。
优点是节省存储空间，给用户提供了最大的灵活性。
②有结构的记录式文件：一种结构文件。由若干记录组成，用户以记录为单位组织信息。每个记录都用于描述实体集中的一个实体，各记录着相同或不同数目的数据项。记录长度可分为定长（文件中所有记录的长度相同）和不定长（文件中所有记录的长度不同）两类
2. 物理结构：顺序结构、链接结构、索引结构；直接文件、哈希文件
（1）物理结构（存储结构）
文件的物理结构是指文件在文件存储介质上的存储形式。
文件的物理结构和组织是指逻辑文件在物理存储空间中的存放方法和组织关系。
（2）顺序结构（连续结构）
如果一个逻辑文件的信息顺序存放在文件存储器上的相邻物理块，则称该文件为顺序文件或连续文件，这样的结构称为顺序结构或连续结构。
最佳应用场合是在对文件中的记录进行批量存取时(即每次要读或写一大批记录)。
若用户要求查找或修改单个记录，这时顺序文件表现出来的性能可能很差。其另一缺点是，若想要增加或修改一个记录，都比较困难。
（3）链接结构（串联结构）
一种物理上非连续的结构，它将逻辑上连续的文件信息存放在外存的不连续物理块中。
链接结构不要求所分配的各物理块是连续的，也不必按顺序排列。
为了使系统能方便地找到逻辑上连续的下一块的物理位置，在每个物理块中设置一个指针，指向该文件的下一个物理块号。
优点：文件可以方便的动态增加或删除，新建文件时，不必预留出文件的最大长度。
缺点：是只适合顺序存取，不便于直接存取；在每个物理块中部设置了链接字，破坏了物理信息的完整性。
（4）索引结构
将一个文件的信息存放在若干不连续的物理块中，并为每个文件建立专用数据结构—索引表，其每一表目指出文件逻辑记录所在的物理块号，并将这些物理块号存放在索引表中。
优点：既能顺序存取，又能随机存取，满足了文件动态增长、插入、删除的要求，能充分地利用存储空间，避免存储设备资源的浪费。
缺点：在于索引表本身带来了系统开销，例如为了存储索引表导致内存储空间开销增加。