操作系统

（一）操作系统概述

1、操作系统的概念、特征、功能和提供的服务

【操作系统的概念】

用户观点：根据用户所使用计算机的不同而设计不同类型的操作系统

系统观点：操作系统是计算机系统的资源管理程序

进程观点：操作系统由若干个可以独立运行的程序和一个对这些程序进行协调的核心所组成

虚拟机观点：也称机器扩充，操作系统为用户使用计算机提供了许多服务功能和良好的工作环境

【操作系统的特征】

并发性：两个或多个事件在在同一时间间隔内发生（而并行性是指两个或多个事件在同一时刻发生）

共享性：系统中的硬件和软件资源不再为某个程序所独占，而是供多个用户共同使用（包括互斥共享（如打印机，某些变量，队列等一段时间只能供一个作业使用的资源）和同时访问（如可重入代码，磁盘等），后者作业访问资源的顺序不会影响访问的结果）

虚拟性：把一个物理上的实体变为若干个逻辑上的对应物

异步性：在多道程序环境中，由于资源等因素的限制，程序走走停停，以不可预知的速度向前推进

【操作系统的功能】

处理器管理：对处理器的分配和和运行（以进程为单位）实施有效的管理，包括进程控制（负责进程的创建，撤销以及状态转换），进程同步（对并发执行的进程进行协调），进程通信（负责进程间的信息交流），进程调度（按一定算法进行处理器分配）

存储器管理：对内存进行分配，保护和扩充，包括内存分配（按一定策略为每道程序分配内存），内存保护（保证各程序在自己的内存区域内运行而不相互干扰），内存扩充（为允许大型最作业或多作业的运行，必须借助虚拟存储技术去获得增加内存的效果）

设备管理：对计算机系统内的所有设备进行管理。包括设备分配（根据一定的设备分配原则对设备进行分配），设备传输控制（实现物理的输入输出操作），设备独立性（用户程序中的设备与实际使用的物理设备无关)

文件管理：操作系统中负责信息管理的部分称为文件系统，文件管理的主要任务包括文件存储空间的管理（存储空间的分配与回收），目录管理（提供按名存取的功能），文件操作管理（负责完成数据的读写），文件保护

用户接口：方便用户使用操作系统，包括命令接口（包括联机命令接口和脱机命令接口），程序接口（也称系统调用），图形接口

【操作系统提供的服务】

程序执行，I/O操作，文件操作，资源分配与保护，错误检测与排除

2、操作系统的发展与分类

【操作系统的发展】

无操作系统阶段：用户独占资源，资源利用率低，CPU等待人工操作，手工操作的慢速CPU运算的高速矛盾（引入了脱机输入/输出技术）
单道批处理系统：自动性，顺序性，单道性
多道批处理系统：多道，宏观上并行，微观上串行

【操作系统的分类】

批处理操作系统：运行过程无需用户干预，大大提高了系统资源利用率和系统吞吐量，但无交互性，使用不便

分时操作系统：在操作系统中采用分时技术（把处理器的运行时间分成很短的时间片，按时间片轮流把处理器为分配给各联机作业使用）而得,特征是多路性，交互性，独占性，及时性

实时操作系统：提供及时响应和高可靠性

嵌入式操作系统

集群系统：将两个或多个独立的系统耦合起来，共同完成一项任务

网络操作系统

分布式操作系统

（二）进程管理

1、进程与线程的基本概念

【进程的定义】

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

【进程的组成】

程序段：进程中能被进程调度程序调度到CPU上执行的代码段

数据段：进程对应的程序加工处理的原始数据或者程序执行时产生的中间或结果数据

PCB：既能标识进程存在，又能刻画执行瞬间的数据结构

【进程的特征】

动态性：进程是程序的一次执行过程，是动态地产生，变化和消亡的

并发性：内存中有多个进程实体，各进程可并发执行

独立性：进程是能独立运行，独立获得资源，独立接受调度的基本单位
-

异步性：各进程按各自独立的，不可预知的速度向前推进

结构性：每个进程都会配置一个PCB，结构上看，进程由数据段，程序段，PCB组成

【进程与程序的关系】

进程是动态的，程序是静态的

进程是暂时的，进程是永久的

进程与程序的组成不同

通过多次执行，一个程序可以产生多个不同的进程；通过调用关系，一个进程可以执行多个程序。进程可以创建其他进程，而程序不能形成新的程序

进程具有并行特性，而程序没有

【进程与作业的关系】

作业是用户向计算机提交任务的任务实体，而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位

一个作业可由一个或多个进程组成，但一个进程不能构成多个作业

作业的概念主要用在批处理系统中，而进程的概念则几乎用在所有的多道程序系统中

【为什么PCB是进程存在的唯一标志？】

在系统调度到某进程后，要根据其PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存地址，找到其程序和数据

进程在执行过程中，当需要和与之合作的进程实现同步，通信或访问文件时，也都需要访问PCB

当程序由于某种原因暂停执行时，又需要将其断点的处理机环境保存在PCB中

【导致进程创建的事件有哪些？】

用户登录。在分时系统中，用户在终端输入登录信息，系统检测通过后就为该终端用户建立新进程并插入到就绪队列

作业调度。在批处理系统中，当作业调度程序按照一定的算法调度到某个作业时，将该作业装入内存，并为其分配资源并创建进程，并插入到就绪队列

请求服务。基于进程的需要，由其自身创建一个新进程并完成特定任务

-
【创建进程时，操作系统需要完成的主要工作是什么？】

先向系统申请一个空闲PCB，并指定唯一的进程标识符（PID）

为新进程分配必要的资源

将新进程的PCB初始化。为新进程的PCB填入进程名，家族信息，程序数据地址，优先级等信息

将新进程的PCB插入到就绪队列

【导致进程撤销的事件有哪些？】

进程正常结束，进程异常结束以及外界干预等

【撤销一个进程时，操作系统主要完成的工作是什么？】

先从PCB集合中找到被撤销进程的PCB

若被撤销进程正处于执行状态，则应立即停止该进程的执行，设置重新调度标识，以便进程重新后将处理器分配给其他进程

对后一种撤销策略，若被撤销进程有子孙进程，还应将该进程的子孙进程撤销

回收被撤销进程所占有的资源，或者归还给父进程，或者归还给系统。最后，回收其PCB

【阻塞一个进程时，操作系统主要完成的工作是什么？】

首先停止当前进程的运行。因该进程正处于执行状态，故应中断处理器

保存该进程的CPU现场以便之后可以重新调用该进程并从中断点开始执行

停止运行该进程，将进程状态由执行状态改为阻塞状态，然后将该进程插入到相应事件的等待队列中

转到进程调度程序，从就绪队列中选择一个新的进程投入运行

【唤醒一个进程时，操作系统主要完成的工作是什么？】

将被唤醒进程从相应的等待队列中移出

将状态改为就绪并插入相应的就绪队列

【简述进程上下文切换的过程】==【切换进程时，操作系统主要完成的工作是什么？】

保存处理及上下文，包括程序计数器和其他寄存器

更新PCB信息

把进程的PCB移入相应队列，如就绪，某事件的阻塞队列

选择另一个进程执行，更新其PCB

更新内存管理的数据结构

恢复处理器上下文

【线程的定义】

线程是进程内一个相对独立的，可调度的执行单元

【线程的实现】

内核级线程：依赖于内核，由操作系统内核完成创建和撤销工作的线程

用户级线程：不依赖于操作系统核心，由应用进程利用线程库提供创建，同步，调度和管理线程的函数来控制的线程

组合方式：同时提供内核线程控制机制和用户线程库

【多线程模型】

【线程与进程的比较】

调度。引入线程后，线程是独立调度的基本单位，进程是拥有资源的基本单位；在同一进程中，线程的切换不会引起进程切换；在不同进程中进行线程切换，将引起进程切换

拥有资源。进程始终是拥有资源的基本单位，线程可以访问其隶属进程的系统资源

并发性。引入进程的操作系统中，不仅进程之间可以并发执行，而且同一进程内的多个线程之间也可以并发执行，这使得操作系统具有更好的并发性，大大提高了系统的资源吞吐量

系统开销。引入线程后，线程之间的切换开销很小，而且由于同一进程内的多个线程共享进程的地址空间，因此多线程之间的同步与通信容易实现

2、进程调度的基本概念、调度方式、调度算法

【操作系统中的3级调度】

高级调度，又称作业调度，按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程，发生频率最低

中级调度，又称内存调度，按照某种规则，从挂起队列中选择合适的进程将其数据调回内存，发生频率中等

低级调度，又称进程调度，按照某种规则，从就绪队列中选择一个进程为其分配处理机，发生频率最高

【进程调度的概念】

系统按照一定的策略动态地把处理器分配给就绪队列中的某个进程，以便使之执行

【进程调度的功能】

用PCB记录系统中所有进程的有关情况以及状态特征

选择获得处理器的进程

处理器分配

【引起进程调度的原因】

当前进程运行结束，包括任务完成而正常结束或者因出现错误而异常结束

当前运行进程因某种原因，如I/O请求，P操作，阻塞原语等从运行态变为阻塞态

执行完系统调用等系统程序后返回用户进程，这时可以看作系统进程执行完毕，从而可以调度一个新的用户进程

在采用抢占式调度方式的系统中，更高优先级的进程要求使用处理器，则使当前运行进程进入就绪队列

在分时系统中，分配给该进程的时间片已用完

【不能进行进程调度的情况】

处理中断的过程中。处理中断过程复杂，很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理器资源

在操作系统内核程序临界区中。进程进入临界区后，需要独占式地访问共享数据，理论上必须加锁，以防止其他并行程序进入，在解锁前不应切换到其他进程运行，以加快该共享数据的释放

在其他需要完全屏蔽中断的原子操作过程中。原子操作不可再分，不能进行进程切换

【进程调度的方式】==【CPU调度算法中抢占式调度和非抢占式调度有何区别？】

抢占方式，当一个进程正在处理器上运行时，若有更高优先级的进程进入就绪队列，则立即暂停执行当前进程，将处理器分配给新进程。可优先处理紧急进程，也可实现让各进程按时间片轮流执行，适用于分时操作系统，实时操作系统

非抢占方式，当一个进程正在处理器上运行时，即使有更高优先级的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或者因发生某种事件而进入完成或者阻塞状态时，才把处理器分配个新进程。实现简单，开销小，但无法处理紧急任务，适用于早期批处理系统

【调度算法】

先来先服务

短作业优先

优先级调度，分为抢占式和非抢占式，优先级相同时，通常按照先来先服务或者短作业优先的顺序执行

时间片轮转

高响应比优先，响应比=（等待时间+运行时间）/运行时间

多级反馈队列调度

3、进程同步的基本概念、临界区、信号量、经典同步问题

【两种形式的制约关系】

间接相互制约关系（互斥）

直接相互制约关系（同步）

【临界资源与临界区】

临界资源：同时仅允许一个进程使用的资源

临界区：进程中用于访问临界资源的代码，又称临界段

【互斥的要求】

空闲让进：当没有进程处于临界区时，可以允许一个请求进入临界区的进程立即进入临界区

忙则等待：当已有进程进入临界区时，其他师徒进入的进程必须等待

有限等待：对要求访问临界区的进程，应在有限的时间内进入自己的临界区

让权等待：当一个进程因为某些已有无法进入自己的临界区时，应释放处理器给其他进程

【信号量】

(1)整型信号量：未遵循让权等待

(2)记录型信号量（资源信号量），P&V 操作主要用这个

【经典同步问题】

生产者-消费者

读者写者问题（读优先，读写公平，写优先）

哲学家进餐

理发师

【PV操作的框架细节】

根据实际进程类型来判断是否添加while循环代码

用cobegin和coend表示进程之间的并发执行

4、死锁的基本概念、处理策略、死锁预防和死锁避免的算法、死锁检测

【死锁的定义】

当多个进程因竞争系统资源或相互通信而处于永久阻塞状态时，若无外力作用，这些进程都将无法向前推进，均无限期地等待此组进程中某个其他进程占有的，自己永远无法得到的资源，这种现象称之为死锁

【可剥夺资源与不可剥夺资源的区别】

可剥夺资源是指虽然资源占有者进程需要使用该资源，但另一个进程可以强行把该资源剥夺来归自己使用

不可剥夺资源是指除占有者进程不再需要使用该资源而主动释放资源，其他进程不可在资源占有者使用资源过程中强行剥夺

【死锁产生的原因】

系统资源不足（根本原因）

进程推进顺序不当

信号量的使用不当

简而言之，对不可剥夺资源的不合理分配，可能导致死锁

【死锁产生的必要条件】

互斥条件：进程要求对所分配的资源进行排他性控制，即在一段时间内某种资源仅为一个进程所占有

不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，只能由获得该资源的进程主动释放

请求和保持条件：也成部分分配条件，是指进程已经保持了至少一个资源，但又提出了新的资源请求，而在等待新的资源被分配的同时，又对已有资源保持占有

循环等待条件：存在一种资源的循环等待链，而链中每一个进程已获得的资源同时被链中的下一个进程所请求

【处理死锁的基本方法】

鸵鸟算法：视死锁不见

预防死锁：破坏死锁产生的4个必要条件中的一个或多个

避免死锁：在资源的动态分配过程中

检测及解除死锁

【死锁的预防】

破坏互斥条件：允许多个进程同时访问资源，可行性不高

破坏不剥夺条件：对于一个已经获得了某些资源的进程，若新的资源请求不能立即得到满足，则它必须释放所拥有的全部资源，以后需要时再重新申请，实现复杂，可能导致部分工作失效，导致系统开销增大，导致饥饿

破坏请求和保持条件：运行之前一次行分配好所需要的全部资源，简单安全，但资源利用率低，可能导致饥饿

破坏循环等待条件：给资源编号，必须按照编号从小到大的顺序申请资源，不方便增加新设备，会造成资源浪费，用户编程麻烦

【死锁的避免】

银行家算法

【死锁定理】

系统状态为死锁的条件是：当且仅当g该状态下的资源分配图是不可完全简化的

【死锁的检测】

死锁检测算法

【死锁的解除】

资源剥夺法：从其他进程中抢占足够的资源给死锁的进程以解除其死锁状态

撤销进程法：撤销一些进程，直到有足够的资源分配给其他进程，进程死锁状态

进程回退法：让一个或多个进程回退到足以避免死锁的地步，进程回退时资源释放资源而不是被剥夺，要求系统保持进程的历史信息，设置还原点

（三）内存管理

1、内存管理基本概念

【内存管理的功能】

内存的分配与回收

地址变换

内存扩充

存储保护

【链接的3种方式】

静态链接：在程序运行之前，先把各个目标模块及所需库链接为一个完整的可执行程序，以后不再拆开

动态链接：将应用程序编译后所得到一组目标模块装入内存时采用边装入边链接的动态链接方式

运行时动态链接：在程序执行中需要该目标模块时，才对这些模块进行链接，便于修改和更新，便于实现对目标模块的共享

【程序装入的3种方式】

绝对装入：编译时就知道程序将要驻留在内存中的物理地址，编译程序产生含有物理地址的目标代码，不适合多道程序设计

可重定位装入：又称静态重定位，根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变，适用于早期的多道批处理操作系统，容易实现，无需增加硬件地址变换机构，但要求为每个程序分配一个连续的存储区，而且在程序执行期间不能移动，不能再申请内存空间，难以做到程序和数据的共享

动态运行时装入：又称动态重定位，允许程序运行时在内存中移动位置，把地址变换推迟到程序真正要执行时才进行，需要一个重定位寄存器的支持：物理地址=基址寄存器内容+逻辑地址

【内存保护的方法】

界限寄存器方法，包括上、下界寄存器方法和基址和限长寄存器方法

存储保护键方法,给每个存储块分配一个单独的保护键

2、内存交换及分页、分段、段页式内存分配管理

【内存空间的扩充】

覆盖

交换

【连续分配管理方式】

单一连续分配

固定分区分配

动态分区分配

【动态分区分配算法】

首次适应算法

最佳适应算法

最坏适应算法

邻近适应算法

【基本分页存储管理方式的优缺点】

优点：内存利用率高，实现了离散分配，便于存储访问控制，无外部碎片

缺点：需要硬件支持（尤其是快表），内存访问效率下降，共享困难，有内部碎片

【基本分段存储管理方式的优缺点】

优点：便于程序模块化处理和处理变换的数据结构，便于动态链接和共享，无内部碎片

缺点：与分页类似，需要硬件支持；为满足分段的动态增长和减少外部碎片，要采用拼接技术；分段的最大尺寸受到主存可用空间的限制；有外部碎片

【分段与分页的区别】

页是信息的物理单位，段是信息的逻辑单位；

分页的目的是系统管理所需，为了提高内存利用率；分段的目的是为了更好的满足用户的需要

页的大小固定且由系统决定；段的长度不固定，段长由用户编写的程序决定

分页的地址空间是一维的，而分段的地址空间是二维的；

分页有内部碎片，无外部碎片；分段有外部碎片，无内部碎片

【页式存储管理方式中设置快表的作用】

快表，又称联想寄存器(TLB)，时一种访问速度比内存快很多的高速缓存，用来存放最近访问过的页表项的副本，若快表命中，则只要访问一次高速缓存以及一次主存即可，这样就可以加速地址变换的速度，从而提高了查找的速度和指令执行效率

3、虚拟内存

（1）虚拟内存的基本概念

【虚拟内存的特征】

离散性：程序在内存中离散存储

多次性：一个作业可以分成多次调入内存

对换性：又称交换性，指作业在运行过程中可以换入换出

虚拟性：从逻辑上扩充内存容量，用户可以使用的空间远大于实际内存容量

【局部性原理】

时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问，都集中在一个较短的时期内

空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据，都集中在一个较小的区域内

【请求分页存储管理原理】

在分页存储管理系统的基础上，通过增加请求调页功能，页面置换功能所形成的一种虚拟存储系统;在资源运行之前，装入部分页面便可投入运行，运行时若缺页则调页，同时还可以通过页面置换功能将暂时用不到的页面调出到外存

【请求分页管理方式的优缺点】

优点：可以离散存储程序，降低了碎片数量；提供虚拟存储器，提高了主存利用率，有利于多道程序运行，方便用户

缺点：必须有硬件支持；有些情况下会产生抖动现象；程序最后一页仍存在未被利用的部分空间

（2）页面置换算法

【页面置换算法】

最佳置换算法（OPT)

先进先出算法(FIFO)

最近最少使用算法(LRU)

时钟置换算法（CLOCK）

改进型时钟置换算法

【抖动现象】

刚刚换出的页面，过后不久又要访问，并且调入不久后又被调出，如此反复，使得系统把大部分的时间用在了页面的调入调出上，而几乎不能有效的工作

（3）页面分配策略

【工作集】

定义：最近n次内存访问的页面集合，数字n被称作工作集窗口，也就是工作集的大小

【页面分配策略】

固定分配全局置换

可变分配全局置换

可变分配局部置换

【页面调入策略】==【何时调入页面】

请求调页策略，实现简单，但容易产生缺页中断，时间开销大，容易产生抖动现象

预调页策略，将之后可能用到的页面一次全部调入内存

【从何处调入页面】

系统拥有足够的对换区空间，则全部从对换区调入所需页面，以提高调页速度

系统缺少足够的对换区空间，凡是不会被修改的文件都从文件区调入，置换出这些页面时，由于他们没有被修改而不必再将它们换出，右后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，就应调换到对换区，以后需要时再从对换区调入

UNIX方式：进程运行前，相关数据全放在文件区，故未使用过的页面都可以从文件区调入；若被使用过的页面需要换出时，则写回对换区，下次需要时从调换区调入

（四）文件管理

1、文件系统基础

（1）文件概念

【文件的定义】

文件是具有文件名的一组相关元素的集合，在文件系统中是一个最大的数据单位，它描述了一个对象集，每个文件都有一个文件名，用户通过文件名来访问文件

【文件的组成结构】

数据项，文件系统中最低级的数据组织形式，包括基本数据项(用于描述一个对象是的某种特性的一个值)和组合数据项(由多个数据项组合而成)

记录，是指一组相关的数据项的集合，用于描述一个对象在某一方面的属性

文件，是指由创建者所定义的一组相关数据的集合，逻辑上可分为有结构文件和无结构文件

【文件的属性】

名称。文件名唯一，以容易读取的形式保存

标识符。系统内文件的唯一标签，对用户透明

文件类型。被支持不同类型的文件系统使用

文件位置。指向文件的指针

文件的大小，建立时间，用户标识

（2）文件的逻辑结构：顺序文件、索引文件和索引顺序文件

【3种有结构文件】

顺序文件：定长记录的顺序文件，若物理上采用顺序存储则可以实现随机存取，若再能保证记录的顺序结构，则可实现快速检索，但因为文件存储要求连续的存储空间，所以会产生碎片，同时也不利于文件的动态扩充

索引文件：可以进行随机访问，易于文件的增删，但索引表的使用增加了存储空间的开销，并且索引表的查找策略对文件系统的影响很大

索引顺序文件：大大提高了了顺序存取速度，但仍需配置一个索引表，增加了存储开销

（3）目录结构

【目录的功能】

实现按名存取

提高检索速度

允许文件同名

允许文件共享

文件目录：FCB的有序集合，一个FCB称为一个文件目录项

目录文件：为了实现文件目录的管理，通常将文件目录以文件的形式保存在外存空间，这个文件就称为目录文件（它是长度固定的记录式文件)

【文件控制块FCB】

文件控制块是用于保存文件属性信息的数据结构，至少包含以下信息：文件名，文件的结构（有结构的记录式文件or无格式的流式文件），文件的物理位置，存取控制信息，管理信息

【索引结点】

FCB的改进，把除了文件名之外的其他文件描述信息都放到索引结点（i结点），文件目录中的每个目录项仅由文件名和指向该文件i节点的指针构成；

存放在磁盘上的使用节点称为磁盘索引节点，每个文件都有唯一的磁盘索引节点，主要包括以下内容：文件主标识符，文件类型，文件存取权限，文件物理地址，文件长度，文件链接计数，文件存取时间；

存放在内存中的索引节点称为内存索引节点，主要包括以下内容：索引节点编号，状态，访问计数，逻辑设备号，链接指针

【文件的目录结构】

单级目录结构，在整个文件系统中只建立一张目录表，每个文件占据其中的一个表目，易于实现，管理简单，但不允许文件重名，文件查找速度慢

二级目录结构，将文件目录分为主文件目录和用户文件目录，允许文件重名，可获得较高的查找速度，但缺乏灵活性，用户不能对自己的文件进行分类

多级目录结构，又称树形目录结构，，使用路径名来唯一标识文件，便于对文件分类，层次结构清晰，能更有效的进行文件的管理与保护，但查找文件时需按照路径名逐级访问中间节点，增加了磁盘访问次数，进而影响了查询速度

无环图目录结构，实现了文件的共享，但使得系统的管理变得复杂

（4）文件的访问类型及访问控制

【访问类型】

读，写，执行，添加，删除，列表清单

【访问控制】

对不同的用户访问同一个文件采取不同的访问类型，访问控制通常有四种方法：

访问控制矩阵，访问控制表和用户权限表都是采用某种数据结构来记录用户或用户组对每个文件的操作权限，而口令和密码是另一种访问控制方法，口令直接存储在系统内部，不够安全，密码方法的保密性强，节省存储空间，但编码和译码要花费一定时间

2、文件系统实现

（1）文件系统层次结构

【文件的层次结构】

用户接口

文件目录系统

存取控制验证

逻辑文件系统与文件信息缓冲区

物理文件系统

（2）目录实现

【目录的实现】

线性表

散列表

（3）文件实现

【外存分配方式】

静态分配：在文件建立时一次性分配所需的全部空间

动态分配：根据动态增长的文件长度进行分配

【连续分配】

最简单的磁盘空间分配策略，为文件分配连续的磁盘区域，保证了逻辑文件中的记录顺序与存储器中文件占用盘块顺序一致；优点是查找速度快（只需起始块号和文件大小），目录中关于文件物理存储位置的信息也比较简单，缺点是不方便文件拓展，容易产生碎片，需要定期进行存储空间的紧缩

【链接分配】

分为隐式链接和显式链接。

隐式链接（默认）：目录项中有指向索引顺序文件的第一块盘块和最后一块盘块的指针，此外每个盘块中都含有指向下一个盘块的指针；缺点是不支持随机访问，访问效率低下，并且由于其中任何一个盘块的指针错误都会导致后面的盘块的位置丢失；另外，指向下一个盘块的指针也需要耗费少量的存储空间；优点是方便文件拓展，不会有碎片问题，外存利用率高

显式链接：把用于链接文件各物理块的指针显式地存放在一张表中，称为文件分配表(FAT)，一个磁盘仅设置一张FAT并且在开机时就将其读入内存且常驻内存；优点是既支持顺序访问，又支持随机访问，块号转换过程无需访问磁盘，因此访问速度较快；缺点是FAT需要占用一定的存储空间

【索引分配】

系统为每个文件分配一个索引块，索引块中存放索引表，索引表的每个表项对应分配给该文件的一个物理块；优点是支持随机访问，无外部碎片，便于文件拓展，缺点是访存次数增加导致文件的存取速度降低（可以通过提前将索引表调入内存来解决），索引表本身需占用一定的存储空间

【文件的存储空间管理】

空闲文件表

空闲块链表

位示图，保存在主存中

成组链接法(UNIX的文件存储空间管理方法)，适用于大型文件系统

3、磁盘组织与管理

（1）磁盘的结构

引导控制块

分区控制块

目录结构

文件控制块

（2）磁盘的调度算法

先来先服务(FCFS)

最短寻道时间优先(SSTF)

扫描算法（电梯调度算法）(SCAN)

循环扫描算法(C-SCAN)

（五）输入输出（I/O）管理

1、I/O管理概述

【I/O设备的分类】

（1）按照使用特性：存储设备，人机交互设备，网络通信设备

（2）按照信息交换单位：字符设备（如键盘，打印机和显示器），块设备（如磁盘）

（3）按照传输速率：低速设备，中速设备，高速设备

（4）按照设备的共享属性：独占设备，共享设备，虚拟设备

【I/O管理的任务】

完成用户提出的I/O请求，为用户分配I/O设备，提高I/O设备的利用率，方便用户使用I/O设备

【I/O管理的功能】

设备分配，按照设备类型和相应的分配算法决定将I/O设备分配给哪一个进程

设备处理，设备处理程序用以实现CPU和设备控制器之间的通信

缓冲管理，设置缓冲区的目的是为了缓和CPU与I/O设备速度不匹配的矛盾

设备独立性，又称设备无关性，是指应用程序独立于物理设备

【I/O应用接口】

【I/O控制方式】

程序直接控制方式，优点是工作过程非常简单，缺点是CPU利用率相当低，I/O设备的慢速跟不上CPU的高速，致使CPU的绝大部分时间都在测试I/O设备是否已完成数据传输，从而造成CPU的极大浪费

中断控制方式，优点是CPU和I/O设备间可以并行工作，缺点是每次输入/输出一个数据都要求中断CPU，导致一次数据传送的过程中的中断次数较多，从而耗费了大量CPU时间

DMA控方式，在外设和内设之间开辟直接的数据交换通路，优点是设备和CPU可以并行工作，同时设备与内存的数据交换速度加快，并且不需要CPU干预，缺点是DMA控制方式具有一定的局限性，CPU每发出一条指令，只能读/写一个或多个连续的数据块，若要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成，并且每台设备都需要一个DMA控制器，当设备增加时不经济

通道控制方式，所需CPU干预更少，而且可以做到一个通道控制多台设备，优点是解决了I/O操作的独立性和各部件工作的并行性，CPU，通道，I/O设备可并行工作，资源利用率较高，缺点是由于需要更多硬件（通道处理器），因此其成本较高

2、I/O调度

【I/O调度基本概念】

确定一个好的顺序来执行I/O请求

【缓冲的分类】

单缓冲，双缓冲，循环缓冲，缓冲池(由多个缓冲区组成）

【高速缓存与缓冲区】

高速缓存是可以保存数据备份的高速存储器，但不等价于缓冲区,因为：

(1)两者存放的数据不同。高度缓存上存放的是低速设备上的某些数据的一个备份，而缓冲区中存放的则是低速设备传送给高速设备的数据，，这些数据从低速设备传送到缓冲区，再从缓冲区传送到高速设备，而在低速设备中却不一定有备份

(2)两者的目的不同。引入高度缓存主要是为了存放低速设备上的经常要被访问到的数据的备份，这样高速设备就不需要每次都访问低速设备，但如果要访问的数据不在高速缓存中，那么高速设备还是需要访问低速设备；而缓冲区是为了缓和高速设备和低速设备间速度不匹配的矛盾，高速设备和低速设备间每次通信都要经过缓冲区，高速设备不会直接去访问低速设备

【设备分配与回收】

【假脱机技术】