操作系统

什么是操作系统？

Def.操作系统是指控制和管理整个计算机系统的硬件和软件资源，并合理的组织调度计算机的调度工作和资源的分配；已提供给用户和其他软件方便的接口环境；它是计算机系统当中最基本的系统软件

1. 操作系统是资源的管理者（处理机、存储器、文件、I/O设备）
2. 向上层提供方便易用的服务（GUI、命令接口、程序接口（通过系统调用））
3. 是最接近硬件的一层软件--实现对硬件机器的扩展

操作系统的功能是什么？有哪些模块？

内存管理、进程管理、文件系统管理、输入输出设备管理

1. 内存管理：内存的分配与回收、地址重定位、地址的共享与保护、地址扩充
2. 进程管理：负责进程的创建、销毁、切换、调度以及进程的通信
3. 文件系统管理：负责文件在内存与磁盘之间的读写，文件的创建删除、磁盘空间的分配回收
4. 输入输出设备管理：实现驱动设备，进行设备的访问。处理设备的中断

操作系统的特征

四个特征：并发、共享、虚拟、异步（并发、共享是最基本的特征）

并发性：计算机系统中存在同时运行着的程序

并发：两个或者多个事件在同一时间间隔内发生（单核cpu）

并行：两个或者多个事件在同一时刻发生（多核cpu）

共享：资源共享，指系统中的资源可供内存中多个并发执行的进程共同使用

互斥共享方式：一个时间段内只允许一个进程访问该资源

同时共享方式：允许一个时间段内有多个进程“同时”对他们进行访问

虚拟： 把物理上的实体变为若干个逻辑上的对应物（时分复用技术、空分复用技术）

异步：也称不确定性，指进程的执行顺序和执行时间的不确定性

同步：一个进程在进行某个请求时，若该请求需要一段时间才能返回信息，那么该进程一直等待

异步：进程不需要一直等待下去，而是执行下面的操作，不管其他进程的状态

操作系统的分类

1. 单道批处理系统：引入脱机技术，有监督程序负责控制作业输入输出
2. 多道批处理系统：（内存中同时存放若干道程序，在系统内并发执行，共享资源）

优点：多道程序并发执行，共享计算机资源，资源利用率大幅度提升，系统吞吐量增大

缺点：没有人机交互功能

1. 分时操作系统：计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互

优点：解决了人机交互问题，允许多个用户同时使用一台计算机，用户对计算机的操作相对独立

1. 实时操作系统（及时性&可靠性）：及时相应外部事件，在规定时间内完成该事件的处理

什么是内核？什么是用户态（目态）和内核态？★★★★★

内核：一个计算机程序，是操作系统的核心，提供了操作系统最核心的能力可以控制操作系统中的所有内容

微内核功能：时钟管理、中断处理、原语（设备驱动、CPU切换等进程切换、线程调度等）

内存分为用户态和内核态

内核态：操作系统内核代码及其运行时数据结构所在的内存区域，拥有对资源的完全访问权限

用户态：为应用程序分配的内存区域，用户空间中的进程不能直接访问硬件或内核数据结构，只能通过系统调用与内核通信

内核态-》用户态：一条修改psw的特权指令

用户态-》内核态：由中断引起，硬件自动完成   

中断和系统调用的区别

（1）中断：是CPU对例如I/O设备发送的中断信号的响应，此时CPU应该检测当权是否有正在处理的程序，有的话保存上下文信息，从用户态转向内核态进行处理，完成后返回断点继续执行

（2）中断分为软中断和硬中断。硬中断：从硬件发出的中断信号，例如I/O请求。软中断是由指令执行过程中发出的中断。

（3）系统调用是一种软中断，应用程序通过OS间接的调用I/O过程。以实现用户态向内核态的转换

什么是原语

原语是一种特殊的程序，处于操作系统最底层，运行具有原子性--只能一气呵成不能中断

用关中断和开中断两个特权指令（只能让内核程序使用）实现原子性

进程

1. Def.进程：是程序的一次执行过程，是系统进行资源分配和调度的基本单位
2. 进程=PCB(进程控制块)+程序段+数据段（运行过程中产生的各种数据）
3. 特征：动态性、并发性、独立性、异步性
4. 进程vs程序

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

并发性：多个进程可以并发执行；没有并发性

生命周期：进程有创见执行阻塞终止等生命周期；程序就是一段代码

独立性：进程可以独立运行，独立分配资源和接受调度；程序不占用系统资源

线程

减少进程并发执行时所付出的时空开销，增加并发度，并发所带来的系统开销减少

线程是CPU的调度单位

线程共享进程的资源，因为共享内存空间，线程之间的通信无需系统干预

进程和线程的区别★★★★★★

（1）进程是资源分配的基本单位，线程是CPU的基本单位

（2）同一个进程中的不同线程共享进程中的资源（--》会导致一个问题--》数据错乱、恶意修改--》用信号量机制来解决）

1. 调度性：进程是操作系统进行资源分配和调度的基本单位，进程切换需要保存和恢复更多上下文信息；线程在进程内部独立执行的任务，切换开销小
2. 并发性：进程间独立运行，拥有自己的地址空间和资源，进程间通信需要操作系统提
3. 通信机制；线程在统一进程内共享地址和资源，可直接访问
4. 拥有资源：进程独立拥有资源；线程共享进程资源
5. 系统开销：进程较大

PCB（进程控制块）是什么

PCB是进程存在的唯一标志，操作系统对进程进行管理的工作都存在PCB中

PCB要记录：

1. 进程的描述信息（进程名称、标识符等）
2. 处理机的状态信息，程序中断时保留此时的信息，一遍CPU返回时从断点执行
3. 进程控制和管理信息
4. 资源分配清单

进程的状态及转换

1. 进程的基本状态：创建状态、就绪状态、运行状态、阻塞状态、结束状态
2. 进程状态的转换：**不能由阻塞态直接转化为运行态，也不能由就绪态直接转化为阻塞态

进程控制

Def.创建新进程、撤销已有进程、实现进程之间的状态转换（用原语实现）

创建&结束

1. 创建一个子进程：申请PCB，为进程分配所需资源，初始化进程描述信息，插入就绪队列中

引起创建的事件：用户登录，作业调度，提供服务，应用请求

1. 撤销一个子进程：查找需要撤销进程的PCB，如果处于运行状态终止进程并进行调度，终止孙进程归还资源，从所在队列中删除

引起进程终止的事件：正常结束、异常结束、外界干预

进程的切换：切换原语：将运行环境信息存入PCB，PCB移入相应队列，选择另一个进程执行并更新其PCB，根据PCB恢复新进程所需的运行环境

进程通信★★★★★

1.共享存储：两个进程分别拿出一块虚拟地址空间来，映射到相同的物理内存中，速度最快

2.消息传递

进程之间的数据交换以格式化的消息为单位，通过原语进行数据交换

直接通信方式

间接通信方式（信箱）

3.管道通信

各进程要互斥访问管道

一个管道允许多个写进程，只能1个读进程

允许多个写进程、读进程，但是系统会让各个读进程轮流读（Linux）1.1-0.4=0.7

4.信号量机制 ：通过信号量控制多个进程对有限个共享资源的访问权限。

5.Socket：用于跨网络的两个进程之间的通信

线程实现方式

线程控制块TCB，线程切换时要保存：程序计数器、其他寄存器、堆栈指针

用户级线程：由应用程序通过线程库实现，线程管理工作由应用程序负责（包括线程切换），在用户态下完成

优点：用户级线程切换在用户空间即可完成，不需要切换到核心态，系统开销小、效率高

缺点：一个线程被阻塞所有都被阻塞，并发度不高。多个线程不可在多核处理及上并行运行

内核级线程：线程管理工作由操作系统内核完成，线程切换需在核心态下完成

优点：一个线程被阻塞后，别的线程仍然可以继续执行，并发能力强

多线程模型（一对一、多对一、多对多）

处理机调度

调度：确定某种规则来确定这些任务的顺序

1.调度的三个层次

高级调度（作业调度）

低级调度（进程调度/处理机调度）

中级调度（内存调度）：按照某种策略决定将哪个处于挂起状态的进程重新调入内存

（挂起：在内存不够时，将某些进程的数据调出外存，等内存空间空闲或者进程需要运行时再调入）

2.进程调度的时机

需要进行进程调度与切换的情况：当前运行的进程主动放弃处理机（进程正常终止、运行过程中发生异常而终止、进程主动请求阻塞）；被动放弃处理及（时间片用完、I/O中断、更高优先级进入队列）

不能进行进程调度与切换的情况：（1）处理中断过程中（2）在操作系统内核程序临界区（3）原子操作过程中

3.进程调度的方式

非剥夺调度方式（非抢占方式）：只允许进程主动放弃处理机

剥夺调度方式（抢占方式）

调度算法

	先来先服务	短作业优先SPJ	高相应比优先
算法规则	按照作业/进程到达的先后顺序进行服务	最短的作业/进程优先得到服务	相应比=（等待时间+要求服务时间）/要求服务时间
用于作业/进程调度？	都可以	都可以	都可以
是否可抢占	否	非抢占式 (抢占式-最短时间剩余算法SJF)	非抢占式
优点	公平算法实现简单	“最短的”平均等待/周转时间	综合考虑了等待时间和运行时间 对于长作业来说，等待时间越大，相应比越大，从而避免长作业饥饿问题
缺点	长作业（进程）后面的短作业等待时间长，带权周转时间大，对长作业有利，对短作业不利	不公平，对短作业有利，对长作业不利，可能产生饥饿现象	无
是否会导致饥饿	不会	会	否

	时间片轮转（分时操作系统）	优先级调度算法
算法规则	按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。若进程没有在一个时间片内执行完，重新放到就绪队列队尾	每个作业/进程都有各自优先级，调度时先选优先级高的
用于作业/进程调度？	只用于进程调度	都可以
是否可抢占	是	都有
优点	公平，响应快，适合分时操作系统	用优先级区分紧急程度、虫咬成都，用于实时操作系统
缺点	由于高频率的进程切换，有一定开销，不区分任务的紧急程度	如果源源不断的有高优先级进程来，则导致饥饿
是否会导致饥饿	不会	会

临界区和临界资源

临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥访问临界资源

临界区：访问临界资源的那段代码

进程同步与互斥

进程同步：协调各进程间的运行，以实现各进程互斥的访问临界资源

进程互斥：当一个进程访问临界资源时，另一个要访问该临界资源的进程必须等待

四个部分：进入区-》临界区-》退出区-》剩余区

实现对临界资源互斥访问的原则：

1. 空闲让进
2. 忙则等待
3. 有限等待（保证不会饥饿）
4. 让权等待

进程互斥的实现方法

软件实现

单标志法---违反了空闲让进原则

双标志先检查---违反了忙则等待

双标志后检查---解决了忙则等待原则，违反了空闲让进和有限等待原则

Peterson算法---违反让权等待原则

硬件实现

中断屏蔽方法：只适用于操作系统内核进程，不适用于用户进程

TSL指令（用硬件实现）

Swap指令（用硬件实现）

信号量机制

信号量：一个变量，来表示系统中某种资源的数量

两个原子操作的系统调用函数来控制信号量

1. P 操作：当线程想要进入临界区时，会尝试执行 P 操作。如果信号量的值大于 0，信号量值减 1，线程可以进入临界区；否则，线程会被阻塞，直到信号量大于 0。
2. V 操作：当线程退出临界区时，执行 V 操作，信号量的值加 1，释放一个被阻塞的线程。

管程

引入管程的原因：信号量机制存在编写程序难，易出错的问题

管程：（1）局部与管程的共享数据结构（2）一组过程（3）初始话语句（4）名字

死锁★★★★★★

Def.在并发环境下，各进程因竞争资源而导致的一种相互等待对方手里的资源，导致个进程都阻塞，无法向前推进的现象（死锁现象：>=2个进程同时发生死锁）

死锁产生的必要条件

1. 互斥条件：互斥访问资源
2. 不可剥夺条件
3. 请求和保持条件：进程已经保持了一个资源，但是此时又提出了新的资源请求
4. 循环等待条件：发生死锁时，必然存在一个进程--资源循环等待链

什么时候发生死锁现象：对系统资源的竞争、进程推进顺序非法、信号量的使用不当

死锁的处理策略★★★★★★

1.预防死锁：破坏死锁产生的四个必要条件

互斥条件无法被破坏（Spooling技术）

破坏不剥夺条件 ：占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源，这样不可剥夺这个条件就破坏掉了。

破坏请求和保持条件--》静态分配方法（一次性申请完所需全部资源）/动态资源分配

破坏循环等待条件--》采用顺序资源分配法，每个进程按编号递增顺序请求资源

2.避免死锁--银行家算法

安全序列：系统按这个序列分配资源，每个进程都能顺利完成

通过动态地检查系统资源的状态，来判断是否分配资源会导致死锁，并只允许安全的分配。它基于资源的最大需求量和当前已分配资源的情况，对进程提出资源请求进行评估。

3.死锁的检测和解除

死锁的检测：在资源分配图中，先找出：不阻塞（请求边可以分配给他）&非独立（有请求边）的进程节点，消去请求边和分配边，使其成为独立节点。依次简化，如果可以消除所有边，那么是可简化的---》不死锁

死锁的解除：抢占资源/终止进程

存储器管理

内存管理的主要功能：

(1)内存的分配与回收

(2)地址重定位（逻辑地址--》物理地址）

逻辑地址：用户控件中使用的相对地址

物理地址：存储单元中使用的实际的物理单元地址

(3)地址共享与保护

内存保护：上下寄存器/重定位寄存器和界地址寄存器

(4)地址扩充

覆盖、交换、虚拟内存

覆盖：将程序分为多个段，常用的段常驻内存（固定区），不常用的段在需要时调入内存

交换：内存空间紧张时，系统将内存中的某些进程暂时换出外存，把外存中的某些已具备条件的进程换入内存

简述一下内存空间的分配★★★★★

传统操作系统：包括连续分配和非连续分配

1. 连续分配就是一个进程是连续存储的，不会拆分成若干个块。连续分配包括单一连续分配、固定分区分配、动态分区分配。
2. 非连续分配可以将进程拆分成若干个块，离散存放在内存中。非连续分配包括页式存储、段式存储、段页式存储。

现代操作系统：虚拟内存技术

连续分配方式

单一连续分配：分为系统区（os使用）和用户区

• 优点：无外部碎片，可采用覆盖技术扩充内存
• 缺点：适用于单用户、单任务的操作系统；有内部碎片

固定分区分配：将内存用户去划分为多个固定大小的区域，每个分区只装入一道作业

• 内存分配管理：MAT表（分区使用表）;分区大小相等、分区大小不等
• 优点：实现简单，无外部碎片
• 缺点：当用户程序太大时，可能所有的分区无法解决，要用覆盖技术来解决；有内碎片

动态分区分配：不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态建立分区

• 数据结构：空闲分区表/空闲分区链
• 优点：没有内部碎片
• 缺点：有外部碎片

动态分区分配算法★★★★★

首次适应算法：每次都从低地址开始寻找，找到第一个满足大小的空闲分区（碎片多出现于低地址空间）

循环首次适应算法（CFF）:空闲分区以地址递增的顺序排列。每次分配内存时从上次查找结束的位置开始查找空闲分区链

最佳适应算法：空闲分区按照容量依次递增排列，每次分配内存时顺序查找空闲分区链，找到大小等满足要求的第一个空闲分区（会留下很多碎片）

最坏适应算法：空闲分区按照容量依次递减排列，每次分配内存时顺序查找空闲分区链，找到大小等满足要求的第一个空闲分区

简述一下动态回收算法

1. 上邻空闲区，与上空闲区合并，修改长度
2. 下邻空闲区，与下空闲区合并，修改长度与首地址
3. 上、下邻空闲区。与上下空闲区合并，修改其长度/首地址从空闲区表中或空闲链表中删除下接的空闲区表项。
4. 上下都不相邻空闲区时，在空闲区表中或空闲链表中添加新项，添上被回收分区长度和首址。

非连续内存分配中，分页的好处是什么？分页和分段的区别？★★★★

分页的好处：

1. 实现了虚拟内存：分页将进程的逻辑地址空间划分为固定大小的页，并将物理内存也划分为相同大小的页框。这样，每个进程只需要将所需的页加载到物理内存中，而不需要一次性加载整个进程。
2. 内存利用率高。分页可以更灵活的分配内存
3. 页表简单：页的大小是固定的，页表可以简单有效的实现

分页和分段的区别

1. 分页是以固定大小的页作为单位进行管理，而分段是以逻辑段为单位进行管理。分页的大小是固定的，由OS确定；分段的大小是可变的，由用户确定
2. 由于分页使用固定大小的页，会产生内碎片，而分段可以更好的适应变长的逻辑段，避免内碎片。

非连续分配方式

基本分页存储管理

Def.

• 页框：将内存空间分为一个个大小相等的分区，这个分区就叫页框=内存块=物理块
• 页/页面：将进程的逻辑空间分为与页框大小相等的部分，每一个叫做页
• Os以页框为单位为每个进程分配内存空间

数据结构：页表（反应进程的每个页面在内存中存放的位置，每个进程都有一张页表）

页表记录的只是内存块号，而不是内存块的起始地址

地址转换：页号=逻辑地址/页面长度;页内偏移量=逻辑地址%页面长度

快表（TLB）：访问速度比内存快很多的高速缓存

基本分段存储管理段表（段长，基址）

分页、分段的对比

分页	分段
仅仅是系统管理的需要，对用户不可见	更好的满足用户需求，一个段通常包含着一组属于属于一个逻辑模块的信息。对用户是可见的
用户进程地址空间为1维	用户进程地址空间为2维
	更容易实现信息的共享与保护

段页式管理方式

什么是虚拟内存？虚拟内存的工作模式是怎样的？虚拟内存有什么好处？★★★★★★

虚拟内存：从逻辑上扩充内存容量。基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当要访问的信息不在内存中，由操作系统将所需要的部分调入内存，然后继续执行。操作系统将暂时不用的内容换出到外存上，从而腾出空间来放调入内存的信息。

工作模式

地址映射、按需加载、缺页中断、页面置换

好处：

1. 保证了进程与进程是相互隔离的，提升了系统的安全性
2. 引入了虚拟内存，可以减少内存碎片，充分利用内存
3. 加载更多进程

虚拟存储技术

传统存储管理的特征

1. 一次性：作业必须一次性全部装入内存后才能开始运行（如果作业很大不能全部装入内存，导致大作业无法运行；当大作业运行时，内存无法容纳所有作业，导致多道程序并发下降）
2. 驻留性：一旦作业被装入内存，就会一直驻留在内存中

局部性原理

1. 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问
2. 空间局部性：一旦程序访问了某个存储单元，在不久之后其附近的存储单元也很有可能被访问
3. 虚拟内存（基于局部性原理）

在程序装入时，可以将程序中很快用到的部分装入内存，暂时用不到的部分留在外存；

在程序执行过程中，所访问的信息不在内存时，由os负责将所需信息从外存调入内存；

若空间不够，由os负责将内存中暂时用不到的信息调出

特征：

多次性：不用在作业运行时一次性调入内存，而是允许被分成多次调入内存

对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出

虚拟性：从逻辑上扩充了内存容量

虚拟内存技术的实现：请求调页+页面置换

请求分页管理方法

与基本分页管理方法的区别：

在程序执行过程中，当所访问的信息不在内存时，由os负责将所需信息从外存调入内存，然后继续执行程序；若内存空间不够，由os负责将内存中暂时用不到的信息换出到外存

缺页中断机制：

有快表机制的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是：

查快表-》未命中-》查慢表-》调页-》查快表（命中）-》访问目标内存单元

4.页面置换算法★★★★

若内存空间不够，要选择页面换出到外存，页面置换算法就是解决到底要换哪一个

最佳置换算法（OPT）：选择在之后最长时间内不会被使用到的页面

缺点：理想化的算法，需要知道序列，但是实际无法实现

先进先出置换算法（FIFO）：每次选择淘汰的页面是最早进入内存的页面

缺点：会产生Belady异常（当为进程分配的物理块数增大时，缺页次数不减反增）；算法性能比较差

最近最久未使用置换算法（LRU）：淘汰的页面是最近最久没有使用的页面（逆向扫描检查最后出现的一个页号即使要淘汰的）

缺点：性能好，但是难实现

时钟置换算法（CLOCK）：为每个页面设置一个访问位，将内存中的页面链接成循环队列。当某页被访问时，其访问位被置为1。

当淘汰一个页面时，只需检查页的访问位；如果是0，就选择该页换出；如果是1，则将它置0，暂不换出，继续检查下一个页面；若第一轮扫描所有页面都是1，则这些页面的访问位依次置0后，在进行第二次扫描（淘汰一个页面最多会进行两次扫描）

改进型的时钟置换算法：在其他条件都相同时，应优先淘汰没有修改过的页面

页面分配策略

驻留集：请求分页存储管路中给进程分配的物理块集合

（驻留集过小：导致频繁缺页；驻留集过大：多道程序并发程度下降，资源利用率降低）

固定分配：os为每个进程分配一组固定数目的物理块，在进程运行期间不会再改变

可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。

局部置换：发生缺页时智能选自己进程的物理块进行置换

全局置换:可以将操作系统保留的空闲物理块分配给缺页进程,也可以将别的进程持有的物理块置换到外存,再分配给缺页进程。

1. 固定分区局部置换：系统为每个进程分配一定数量的物理块，整个运行期间都不改变，若进程发生缺页，则可以在内存中页面选择一页换出。
2. 动态分区局部置换：进程缺页时，从空闲物理块中取出一块分配给该进程
3. 动态分区全局置换：根据缺页率动态的增加/减少物理块数

何时调入页面：

预调页策略：进程运行前调入

请求调页策略：运行时调入（I/O开销比较大）

预防抖动的策略：

1. 采用局部置换策略
2. 将工作集算法融入处理机调度中
3. 用L=S准则
4. 挂起部分进程

文件管理

文件的逻辑结构vs物理结构★★★

逻辑结构（面向用户）： 用户视角下文件是怎么组织的。

1. 无结构文件（流式文件）： 如文本文件、源代码。以字节为单位，最常用。
2. 有结构文件（记录式文件）： 由一组相似的记录组成（如数据库表、定长/变长记录）。

物理结构（面向系统）： 文件在磁盘上实际是怎么存储和组织的。

1. 连续分配：文件占用磁盘上一组连续的块。优点：访问速度快、支持随机访问；缺点：产生外部碎片、文件扩展难
2. 链式分配（隐式）：文件但用的磁盘块通过指针链接，无需连续。优点：无外部碎片、文件容易扩展；缺点：只支持顺序访问、指针占用空间、可靠性低
3. 链式分配（显式）：用于连接文件个盘块的指针显式的存放在外存的一张链接表中，用 FAT 表集中管理指针；优点：管理简单，存取速度快，适合顺序存储也适合随机访问；缺点：FAT表占大量存储空间和内存，扩大了系统开销。
4. 索引分配：为每个文件建立索引块，在索引块中记录各逻辑块与外村物理块的对应关系。优点：支持随机访问、无外部碎片、易实现对记录的增删；缺点：索引块占用空间，大文件需多级索引。

目录管理与FCB

FCB（文件控制块）： 包含文件名、物理地址、访问权限、创建时间等元数据。目录项就是由 FCB 组成的。

索引节点（Inode）： * 痛点： 传统的 FCB 很大，在查找文件时需要将大量包含元数据的目录项调入内存，导致磁盘 I/O 次数过多。

优化： 把文件名和文件描述信息分开。目录项只保留“文件名”和“指向 Inode 的指针”。查找时只读文件名，找到后再通过 Inode 指针去读文件的详细元数据。极大减少了磁盘 I/O 次数。

磁盘空闲区的管理：操作系统如何知道磁盘哪些块是空的？

1. 空闲表法： 记录连续空闲区的起始块号和块数。适合连续分配。
2. 空闲链表法： 把空闲块链成队列（或把空闲区链成队列）。
3. 位示图法（Bitmap）： 极其重要。

• 用每一位（bit）表示一个块的状态（0空闲，1已分配）。
• 优点： 扫描快，占用内存极小，易于在内存中维护。
• 面试常考计算： 给出磁盘大小和块大小，求位示图需要多少字节，或者给出字长求某个块在第几字第几位。

1. 成组链接法（Unix/Linux 采用）： 结合了链表和表格，将空闲块分组，每组的第一块记录下一组的信息。适合大型文件系统。

虚拟文件系统vs文件共享

虚拟文件系统

作用： VFS 屏蔽了底层具体文件系统的实现差异，为上层应用提供了一组统一的、抽象的系统调用接口（如 open, read, write）。屏蔽底层具体文件系统的实现差异。

文件共享：硬链接 vs 软链接（符号链接）

(1)硬链接（基于索引节点的共享方式）：

原理：多个目录项中的文件名指向同一个索引节点。

特点：共享同一个文件内容和属性；删除一个文件名，只要索引节点的引用计数不为0，文件就不会被真正删除；不能跨文件系统，不能对目录创建。

(2)软链接（基于符号链的共享方式）：

原理：创建一个新的快捷方式文件，这个文件的内容是目标文件的路径名。

特点：有自己独立的索引节点；如果源文件被删了，软链接会“断开”（变成死链接）；可以跨文件系统，可以对目录创建。

I/O设备管理

I/O设备控制方式

程序直接控制方式（轮询）

CPU向控制器发出I/O命令，然后进入死循环，不断检查寄存器的状态位

缺点：CPU极大浪费，CPU速度远快于I/O设备，绝大多数实践都在忙等

中断驱动方式

原理：CPU发出I/O命令后可以切换去执行其他进程。当I/O设备准备好后，向CPU发出中断信号，CPU暂停当前工作，转去执行中断处理程序。

优点： 实现了 CPU 与 I/O 设备的并行，提高了 CPU 利用率。

缺点： 每个字节/字的传输都需要中断一次 CPU。高频的中断会消耗大量 CPU 时间（上下文切换开销大）。

DMA方式（直接内存存取）

原理： 在外设和内存之间开辟一条直接数据通路。CPU 只需在传输开始前（设置传输参数）和传输结束后（处理中断）介入。数据的传输由专门的 DMA 控制器 完成。

特点：

传输的基本单位是数据块（而不再是字节）。

数据直接在外设和内存之间传输，不再经过 CPU。

缺点：每次只能读写连续的数据块；如果是不连续的块，仍需 CPU 多次干预。

通道控制方式

原理： 通道是一种“弱鸡版”的专用处理器。CPU 只需发出一条 I/O 指令指明通道程序的位置，通道就会自动执行通道程序，完成一组复杂的数据传输。

优点： 传输的基本单位是一组数据块。CPU、通道、I/O 设备三者实现全面并行，CPU 干预极少。

I/O软件的层次结构

设备独立性：作用是让用户不需要关心具体硬件

实现机制：通过逻辑设备表将用户的逻辑设备名映射到物理设备名

缓冲管理

为什么要引入缓冲区？

1. 缓和CPU与I/O设备之间速度不匹配的矛盾
2. 减少CPU的中断频率
3. 提高CPU与I/O设备之间的并行性

缓冲区技术

单缓冲vs双缓冲：

单缓冲时，设备向缓冲区灌数据和 CPU 从缓冲区读数据不能同时进行。

双缓冲实现了“输入”和“传送/处理”的并行。

循环缓冲与缓冲池： 现代 OS 采用结构更灵活的缓冲池，包含空缓冲队列、输入队列、输出队列，动态分配收发。

设备分类

独占设备： 一段时间内只允许一个进程访问（如打印机）。容易导致死锁。

共享设备： 一段时间内允许多个进程同时访问（如磁盘）。

虚拟设备： 通过某种技术把独占设备改造成共享设备。

假脱机技术（SPOLing技术）：把一台独占设备虚拟化为共享设备

在磁盘上开辟两个物理区域：输入井和输出井。

当进程请求独占设备（如打印机）输出时，系统并不直接把打印机分配给它。

系统将打印数据先快速写入磁盘的输出井。

由系统内的 SPOOLing 输出进程 在打印机空闲时，逐个从输出井读出数据进行打印。

优点： * 将独占设备改造为了共享设备。实现了“伪并行”：进程误以为打印已经完成（因为写磁盘极快），可以继续执行，极大提高了 CPU 利用率。

磁盘的调度算法★★★★

FCFS（先来先服务）：公平，但寻道时间长。

SSTF（最短寻道时间优先）：优先处理离磁头最近的请求。缺点：可能导致处于两端的请求“饥饿”。

SCAN（电梯算法）：磁头按一个方向移动，直到磁盘尽头再反向。解决了饥饿，但对刚走过的区域不公平。

C-SCAN（循环电梯算法）：磁头单向处理请求，到头后直接快速返回起始端，形成循环。消除了两端请求的延迟不均。