操作系统复习 重点提纲
操作系统关键部分摘要
引论
操作系统的作用
- 作为用户与计算机硬件系统之间的接口
- 作为计算机系统资源的管理者
- 实现了对计算机资源的抽象
操作系统的种类
- 单道批处理系统：
- 批处理是指计算机系统对一批作业自动进行处理的一种技术。
- 为实现对作业的连续处理,需要先把一批作业以脱机方式输入到磁带上,并在系统中配上监督程序(Monitor) ,在它的控制下,使这批作业能一个接一地连续处理
- 多道批处理系统
- 在多道批处理系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”; 然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。
- 分时系统
- 采用时间片轮转的方法，同时为许多终端用户服务，对每个用户能保证足够快的响应时间，并提供交互会话的功能。
- 时间片：将CPU的时间划分成若干个片段，称为时间片，操作系统以时间片为单位，轮流为每个终端用户服务关键问题
- 微机操作系统
- 微型计算机操作系统 微型计算机操作系统简称微机操作系统，常用的有Windows、Mac OS、Linux。
现代操作系统的特性
并发性、共享性、虚拟性、异步性
操作系统程序接口
由一组系统调用组成,每一个系统调用都是一个能完成特定功能的子程序,每当应用程序要求OS提供某种服务时,便调用具有相应功能的系统调用。
操作系统内核态与用户态
内核态（管态）和用户态（目态）将内核程序和用户程序隔离
特权指令
涉及外部设备的输入/输出指令
存取用于内存保护的寄存器
内存清零
置时钟
允许/禁用中断
中断指令是用户程序发起的调用内核代码的唯一方式
中断机制
提高多道程序环境下CPU利用率
外中断：中断信号来源于外部设备
内中断：中断信号来源于当前指令内
内中断的三种情况
陷阱/陷入：由应用程序主动引发
故障：由错误条件引发
终止：由致命错误引发
系统调用的核心
用户程序中包含一段含有int指令的代码
操作系统写中断处理，获取想调用程序的编号
int指令将使CPL改成0 ，“进入内核”
操作系统根据编号执行相应代码
进程控制
进程的概念
程序段、数据段、PCB三部分构成了进程实体,简称”进程”。
进程的三种状态
- 就绪状态(Ready)
- 进程已获得除CPU之外的所有必需的资源,一旦得到CPU控制权,立即可以运行
- 运行状态(Running)
- 进程已获得运行所必需的资源，它正在处理机上执行。
- 阻塞状态(Blocked)
- 正在执行的进程由于发生某事件而暂时无法执行时,便放弃处理机而处于暂停状态,称该进程处于阻塞状态或等待状态。
PCB的定义
PCB是内存中的一种数据结构，PCB的作用是使一个在多道程序环境下不能独立运行的程序(含数据) ,成为一个能独立运行的基本单位, 一个能与其他进程并发执行的进程
PCB是进程存在的唯一标志
PCB的内容
| 类型 | 内容 | 作用 |
|---|---|---|
| 标识信息 | 1 )外部标识为方便用户 2 )内部标识为方便系统 | 标识一个进程 |
| 处理机状态(现场信息 ) | 1 ) CPU通用/指令寄存器 2 ) CPU程序状态字PSW 3 )用户栈指针 | 记录处理机现场信息,以备恢复之用 |
| 调度信息 | 1 )进程状态 2 )进程优先级 3 )调度所需信息 4)事件 | 用户进程的调度管理 |
| 控制信息 | 1 )程序和数据地址 2 )进程同步和通信机制 3 )资源清单 4 )指向下一个进程的指针 | 用于进程的控制管理 |
进程的创建
引起创建进程的事件
用户登录
作业调度
提供服务
应用请求
创建过程
申请进程标识,即申请空白PCB
为新进程分配内存和其它资源
初始化进程控制块
将创建的进程置于就绪队列
进程控制的原语
进程创建原语
进程撤销原语
阻塞原语
唤醒原语
挂起原语
激活原语
临界区的定义
临界区：进程中访问临界资源的那段代码
信号量
定义:把整型信号量定义为一个用于表示资源数目的整型量S ,除初始化外仅能通过两个原子操作wait(S)，signal(S)（低级原语）来访问
原子操作P :
分配一个单位资源
wait(S)
原子操作V :
- 释放一个单位资源
当信号量sign 大于0时，表示该资源该有sign个。当sign小于0时，表示有sign个进程正在等待
管程
管程是由若干个公共变量和所有访问这些变量的过程所组成的一个特殊的模块或软件包
其他进程同步机制（有各种各样的问题）
- 关中断法(开关中断指令)也称为”硬件锁”,在进入锁测试之前关闭中断,直到完成锁测试并上锁之后才能打开中断。
- 利用Test and Set指令实现互斥：这是一种借助一条硬件指令一“测试并建立”指令TS(Test- and-Set)以实
现互斥的方法。在许多计算机中都提供了这种指令。 - 利用swap指令实现线程互斥
管道的定义
管道:指用于连接一个读进程和一个写进程以实现他们之间通信的一个打开的共享文件,又名pipe文件。
管道只能采取半双工通信,某一时间段内只能实现单向的传输。如果要实现双向同时通信,则需要设置两个管道各个进程要互斥的访问管道
数据以字节流的形式写入管道,当管道写满时,写进程的write()系统调用将会被阻塞,等待读进程将数据取走。当读进程将数据全部取走后,管道变空,此时读进程的read()系统调用将会被阻塞
线程
线程(thread)是一个可执行的实体单元。它代替以往的进程,成为现代操作系统中处理机调度的基本单位。
调度的基本单位
同一进程中的线程切换不会引起进程切换
不同进程中的线程切换必然引起进程切换
用户级线程
用户级线程仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能,都无须利用系统调用来实现。
对于用户级线程的切换,通常是发生在一个应用进程的诸多线程之间,无须内核的支持。
切换的规则远比进程调度和切换的规则简单
内核支持线程KST
在内核的支持下运行的，即无论是用户进程中的线程,还是系统进程中的线程,他,们的创建、撤消和切换等,也是依靠内核实现的。
在内核空间还为每一个内核支持线程设置了一个线程控制块 ,内核是根据该控制块而感知某线程的存在的,并对其加以控制。
线程控制块TCB
线程标识符;
组寄存器，它包括程序计数器PC、状态寄存器和通用寄存器;
线程运行状态,用于描述线程正处于何种运行状态;
优先级，描述线程执行的优先程度;
线程专有存储区，用于线程切换时存放现场保护信息,和相关统计信息;
信号屏蔽，即对某些信号加以屏蔽。
堆栈,用来保存局部变量和返回地址。
- 用户栈和核心栈
调度机制与死锁
作业调度——先来先服务算法（First Come First Serve）
基本原则是按照作业到达系统的先后次序来选择,或者说它是优先考虑在系统中等待时间最长的作业,而不管该作业所需执行时间的长短。
作业调度——短作业优先（Short Job First）调度算法
SJF算法是以作业的长短来计算优先级,作业越短,其优先级越高。
作业调度——高响应比优先调度算法
为每个作业引入一个动态优先级,即优先级是可以改变的，令它随等待时间延长而增加,这将使长作业的优先级在等待期间不断地增加,等到足够的时间后,必然有机会获得处理机。该优先级的变化规律可描述为:
$$
R_p=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}
$$
响应比
(等待时间+执行时间)/执行时间
进程调度算法
考得不大具体，了解即可
死锁的概念
死锁( Deadlock ) 是指多个进程在运行过程中因争夺资源而造成的一种僵局
死锁原因
竞争不可抢占性资源
竞争可消耗资源
进程推进顺序不当
产生死锁的必要条件
互斥条件
请求和保持条件
不可抢占条件
循环等待条件
死锁的预防、避免、检查与解除
这一块内容很多还挺重要的，慢慢看吧
存储器管理
目的
存储器管理的目的：提高内存利用率、方便用户
程序的装入
重定位：
在装入时对目标程序中指令和数据的修改过程称为重定位。
绝对装入方式：
在编译时,如果知道程序驻留在内存的什么位置,那么编译程序将产生绝对地址的目标代码。
可重定位装入方式（Relocation Loading Mode）：
在多道程序环境下,可重定位装入方式,根据内存的当前情况,将装入模块装入到内存的适当位置。
动态重定位：
- 在把装入模块装入内存后,并不立即把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正要执行时(访问内存之前)才进行。
连续分配存储方式
- 单一连续分配：系统区加用户区，连续的分配
- 固定分区分配：将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业,便可以有多道作业并发执行。
- 动态分区分配：动态分区法在作业执行前并不建立分区,分区的建立是在作业的处理过程中进行的,且其大小可随作业或进程对内存的要求而改变。分区分配算法有：
- 首次适应算法：要求按地址递增的次序组织空闲区表(链)。
- 循环首次适应算法（Next Fit）：每次分配不再从空闲分区链(表)的开始找起,而是从上次找到的空闲分区的下一个找起,找到一个能满足要求的空闲区。
- 最佳适应算法（Best Fit)：把能满足要求的最小空闲分区分配给作业,避免“大材小用”
- 最坏适应算法(Worst Fit)：总是挑选最大的空闲分区分割给作业使用
- 快速适应算法：将空闲分区按大小分类,每类具有相同容量，放入一个空闲分区链表
- 伙伴系统：无论已分配分区或空闲分区,分区大小必须是2的k次幂，k为整数, I≤k≤m
- 哈希算法:哈希算法就是利用哈希快速查找优点,以及空闲分区在可利用空间表中的分布规律,建立哈希函数,构造一张以空闲分区大小为关键字的哈希表,该表的每一个表项记录了一个对应的空闲分区链表表头指针。
分页存储
页面
把进程的逻辑地址空间划分成若干大小相等的区域,每个区域称作页面或页。每个页都有一个编号,叫做页号。页号一般从0开始编号,如0 , 1, 2, …等。
把内存空间划分成若干和页大小相同的物理块，这些物理块叫页框(frame)或(物理)块。同样,每个物理块也有一个编号，块号从0开始依次顺序排列。
以页为单位进行内存分配,并按进程的页数多少来分配。逻辑上相邻的页,物理上不一定相邻。
虚拟存储器
虚拟存储器:是指具有请求调入功能和置换功能,能从逻辑.上对内存容量加以扩充的一种存储器系统。
虚拟内存的实际容量 = min（内存与外存之和, CPU寻址范围）
虚拟存储器的实现都是建立在离散分配的存储管理方式的基础上。
请求分页系统
在分页系统的基础上,增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。置换时以页面为单位。
硬件支持:
- 请求分页的页表机制
- 缺页中断机构
- 地址变换机构
物理块分配策略
在请求分页系统中,可采取两种内存分配策略:
固定分配策略:为每个进程分配一定数目的物理块,在整个运行期间不再改变
可变分配策略:先为每个进程分配一定数量的物理块,在整个运行期间可适当增多或减少。
在进行置换时,也可采取两种策略
全局置换:可以将操作系统保留的空闲物理快分配给进程,也可以将别的进程持有的物理块置换到外存,再分配给缺页进程。
局部置换:发生缺页时,只选进程自己的物理块置换
组合出的三种策略：（不能采用固定分配全局置换）
固定分配局部置换(Fixed Allocation , Local Replacement)
为每个进程分配一定数目的物理块,在整个运行期间不再改变。
采用该策略时,如果进程在运行中发现缺页,只能从该进程在内存中的n个页面中选出一页换出,然后再调入一页。
困难:应为每个进程分配多少个物理块难以确定。
可变分配全局置换(Variable Allocation , Global Replacement)
在采用这种策略时,先为系统中的每个进程分配一定数目的物理块,而OS自身也保持一个空闲的物理块队列。
如果某进程发生缺页时,由系统从空闲的物理块队列中,取出一个物理块分配给该进程,并将欲调入的页装入其中。
当空闲物理块队列中的物理块用完后, OS才能从系统中的任一进程中选择一页调出。
可变分配局部置换(Variable Allocation , Local Replacement)
为每个进程分配一定数目的物理块,如果某进程发生缺页时,只允许从该进程在内存的页面中选出一页换出,不会影响其他进程执行。
如果进程在运行中频繁发生缺页中断,则系统再为进程分配若干物理块
如果进程在运行中缺页率特别低,则适当减少分配给该进程的物理块
交换(swap)分区：
Swap分区在系统的物理内存不够用的时候，把硬盘内存中的一部分空间释放出来，以供当前运行的程序使用。那些被释放的空间可能来自一些很长时间没有什么操作的程序，这些被释放的空间被临时保存到Swap分区中，等到那些程序要运行时，再从Swap分区中恢复保存的数据到内存中。
页面置换算法
最佳置换算法
- 算法无法实现，但可评价其他算法。
先入先出页面（FIFO）置换算法
- 算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
- Belady现象
- 采用FIFO算法时,如果对一个进程未分配它所要求的全部页面,有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
最近最久未使用（LeastRecently Used）算法
- 算法根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
- 该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t ,当需淘汰一个页面时,选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
- 需有以下两类硬件之一的支持:
- 寄存器
- 栈
最少使用置换（Least Frequently Used)算法
- 在采用LFU算法时,应为在内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。
简单的Clock置换算法
当采用简单Clock算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列。
当某页被访问时,其访问位被置1。
置换算法在选择一页淘汰时,只需检查页的访问位。如果是0 ,就选择该页换出;若为1 ,则重新将它置0 ,暂不换出,而给该页第二次驻留内存的机会
再按照FIFO算法检查下一个页面。
当检查到队列中的最后一个页面时,若其访问位仍为1 ,则再返回到队首去检查第一个页面。
因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描
改进型CLock算法
在将一个页面换出时,如果该页已被修改过,便须将该页重新写回到磁盘上;但如果该页未被修改过,则不必将它拷回磁盘。
在改进型Clock算法中,除须考虑页面的使用情况外,还须再增加一个因素,即置换代价,这样,选择页面换出时,既要是未使用过的页面,又要是未被修改过的页面。
把同时满足这两个条件的页面作为首选淘汰的页面。
由访问位A和修改位M可以组合成下面四种类型的页面:
1类(A=0 , M=0) :表示该页最近既未被访问,又未被修改,是最佳淘汰页。
2类(A=0 , M=1) :表示该页最近未被访问,但已被修改,并不是很好的淘汰页。
3类(A=1 , M=0) :表示该页最近已被访问,但未被修改,该页有可能再被访问。
4类(A=1 , M=1) :表示该页最近已被访问且被修改,该页可能再被访问。
(1)从指针所指示的当前位置开始,扫描循环队列,寻找A=0且M=0的第一类页面,将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。
(2)如果第一步失败,则开始第二轮扫描,寻找A=0且M= 1的第二类页面,将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间,将所有扫描过的页面的访问位都置0。
(3)如果第二步也失败,则将指针返回到开始的位置,然后回到第一步重新开始,一定能找到被淘汰的页。
该算法与简单Clock算法比较，可减少磁盘的I/O操作次数。但为了找到一个可置换的页，可能须经过几轮扫描。换言之,实现该算法的开销有所增加。
预防抖动
刚被淘汰的页面又马上被调回内存,调回内存不久后又被淘汰出去,如此频繁进行,这种现象称为抖动(或称颠簸)
所谓工作集,是指在某段时间间隔△里,进程实际所要访问页面的集合。
预防抖动的策略
采取局部置换策略
把工作集算法融入到处理机调度中
利用”L=S”准则调节缺页率
选择暂停的进程
当多道程序度偏高时,已影响到处理机的利用率,为了防止发生“抖动”,系统必须减少多道程序的数目,以便腾出内存空间分配给那些缺页率偏高的进程。
输入输出设备
I/O 系统 （四个层级从低到高）
中断处理程序
- 当I/O任务完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。
设备驱动程序
- 驱动程序一般会以一个独立进程的方式存在。
- 主要负责对硬件设备的具体控制，将上层发出的一系列命令(如read/write) 转化成特定设备“能听得懂”的一系列操作。包括设置设备寄存器;检查设备状态等
设备独立性软件
他的主要功能有:
向上层提供统一的调用接口，如read/write系统调用
设备的分配与回收
差错处理
数据缓冲区管理
建立逻辑设备名到物理设备名的映射关系:根据设备类型选择调用相应的驱动程序
用户层软件
- 实现了与用户交互的接口，用户可直接使用该层提供的、与I/O操作相关的库函数对设备进行操作。
设备驱动设备的控制方式
控制方式
宗旨：尽量减少主机对I/O控制的干预，把主机从繁杂的IO控制事务中解脱出来
忙——等待方式
CPU向控制器发出I/O指令,启动输入设备。
状态寄存器忙/闲标志busy置1。
循环测试busy, busy= 1输入未完成。
busy=0输入完成，将数据从控制器的数据寄存器读到内存
由于CPU高速,I/O设备低速致使CPU极大浪费。
使用中断的可编程I/O方式
CPU向控制器发出I/O指令，CPU返回继续原来的工作。
设备控制器控制I/O设备。CPU与I/O并行工作。
数据输入寄存器，控制器向CPU发出中断。
CPU检查数据正确性，数据写入内存。
直接存储器访问(Direct Memory Access)
特点
数据传输的基本单位是数据块。
数据从设备直接送入内存，或者相反。
仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成的。
DMA控制器
三部分
主机与DMA控制器的接口
DMA控制器与块设备的接口
I/O控制逻辑
四类寄存器
数据寄存器DR
命令/状态寄存器CR
内存地址寄存器MAR
数据计数器DC
DMA工作过程
CPU发出指令，存入CR
内存起始目标地址送入MAR。
读取字节数送DC。
源地址送DMA的I/O控制逻辑。
启动DMA控制器，CPU处理其他任务。
DMA控制读入一个字(节)到DR。
将该字(节)送入MAR指向的内存单元。
MAR加1，DC减1。
DC<> 0继续传输，DC=0发出中断。
中断方式是在数据缓冲寄存区满后，发中断请求，CPU进行中断处理。
DMA方式则是在所要求传送的数据块全部传送结束时要求CPU进行中断处理，大大减少了CPU进行中断处理的次数。
中断方式的数据传送是由CPU控制完成的，而DMA方式则是在DMA控制器的控制下不经过CPU控制完成的。
I/O通道控制方式
- 目的：CPU的I/O任务由通道来承担。
- 一种特殊的处理机，属于硬件技术。它具有执行I/O指令的能力，并通过执行通道程序来控制I/O操作。
- 指令类型单一、 即由于通道硬件比较简单，其所能执行的指令，主要为与I/O有关的指令
- 通道没有自己的内存，与CPU共享内存
- CPU一次读(或写)多个数据块。
- 多个数据块送入不同内存区域。
- CPU、通道和I/O设备三者的并行操作。
- 工作过程:
- CPU向通道发送一条I/O指令。
- 给出通道程序首址和要访问的I/O设备。
- 通过执行通道程序完成I/O任务。
- 通道程序由一系列通道指令(通道命令)构成。
- 每条通道指令包含的信息:
- 操作码
- 内存地址
- 计数
- 通道程序结束位P (P= 1表示程序结束)
- 记录结束标志R (R=0表示与下一条指令处理的数据属于同一记录;R= 1表示某记录的最后一条指令)
- 字节多路通道(Byte Multiplexor Channel)
- 字节多路通道以字节为单位传输信息
- 含有许多非分配型子通道
- 子通道按时间片轮转方式共享通道
- 只要扫描每个子通道的速度足够快，而连接到子同上的设备的速率较小的时，不丢数据
- 主要连接以字节为单位的低速I/O设备,如:打印机、终端
设备独立性
用户编程时使用的硬件名称与实际使用的设备名称不同
假脱机系统(spooling)
在多道程序技术下，专门利用一道程序来模拟脱机输入操作，把低速I/O设备上的数据传送到高速磁盘上，
再用另一道程序来模拟脱机输出操作，把数据从磁盘传送到输出设备上。
- 此时I/O设备与CPU并行工作。
缓冲区管理
单缓冲区(Single Buffer)
- 进程发出一个I/O请求时，操作系统便在主存中为之分配一缓冲区。
双缓冲区
在设备输入时，先将数据送入第一缓冲区，装满后便转向第二缓冲区。此时OS可以从第二缓冲区中移出数据，并送入用户进程。接着由CPU对数据进行计算。
为了实现两台机器间的双向数据传输，必须在两台机器中都设置两个缓冲区，一个用作发送缓冲区，另外一个用作接收缓冲区。
文件管理
文件逻辑结构是为了方便用户而设计的
文件的逻辑结构
顺序文件：由一系列记录按某种顺序排列所形成的文件。通常是定长记录
索引文件：当记录可变长时，通常为之建立一张索引表，并为每个记录设置一个表项以加快对记录检索的速度。
索引顺序文件：上述两种方式的结合。为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。
二级索引顺序文件：为了进一步提高检索效率,可以为顺序文件建立多级索引表。
文件控制块
为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为”文件控制块(FCB)
FCB通常含有三类信息:
基本信息类。包括:文件名，文件物理位置，文件逻辑结构，文件的物理结构
存取控制信息类。包括:文件主的存取权限，核准用户的存取权限和一般用户的存取权限
使用信息类。包括:文件的建立日期和时间、文件上次修改的日期和时间及当前使用信息。
文件目录
文件目录通常是存放在磁盘上的，当文件很多时，文件目录要占用大量的盘块。在检索目录文件的时候，需要将目录调入内存后比较文件名，但是只用到文件名，而不需要其它那些对文件的描述信息。所以便把文件名与文件信息分开，使文件描述信息单独形成一个索引结点。
软连接与硬链接
硬链接
- 软链接相当于Windows的快捷方式
- 软链接里面存放的是源文件的路径，指向源文件
- 删除源文件，软链接文件依然存在，但是无法通过软链接访问源文件，已经失效，并且白字红底闪烁
- 软链接和源文件是不通的文件，iNode号不同，文件类型也不同
- 所有连接文件的权限都是777，而实际权限是由链接指向的源文件权限决定的
软连接
- 具有相同iNode节点号的多个文件，互为硬链接文件
- 删除硬链接文件或者源文件任意之一，文件实体并未被删除，只有删除了所有硬链接文件和源文件，文件实体才被删除
- 硬链接文件只是文件的另一个入口
- 链接文件和源文件属性相同
- 不能跨分区，不能对目录使用
硬盘存储器管理
外存组织方式（文件的物理结构）
- 顺序组织方式
- 每个文件在磁盘上占有一组连续的块
- 链接组织方式
- 可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表
- 显式链接：把用于链接文件各物理块的指针显式地存放在一张表中。 即文件分配表(FATFile Allocation Table)
- 索引组织方式
- 索引分配允许文件离散地分配在各个磁盘块中,系统会为每个文件建立一张索引表
- 索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表)。
- 索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
文件存储空间管理
存储空间的管理实际上是对外存未占用空间的管理
- 连续分配方式
- 空闲表法：为每个文件分配一块连续的存储空间。系统为外存上的所有空闲区建立一张空闲表， 每个空闲区对应于一个空闲表项,再将所有空闲区按其起始盘块号递增的次序排列
- 离散分配方式
- 空闲盘块链：磁盘上的所有空闲空间以盘块为单位拉成一条链，其中的每一个盘块都有指向后继盘块的指针。
- 空闲盘区链：将磁盘上的所有空闲盘区拉成一条链。 在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。
- 位示图法（连续离散都适用）
- 利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为0时表示对
应的盘块空闲，为1时表示已分配(Linux)。 有的系统则相反。 - 磁盘上的所有盘块都有一个二进制位与之对应，这样由所有盘块所对应的位构成一个集合，称为位示图。
- 通常可用
m*n个位数来构成位示图，并使m*n等磁盘的总块数。
- 利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为0时表示对