考研操作系统笔记

Through the storm, we will find a way.

---

lpf的考研提示

各位同学：

很多同学下个月要踏入考研的考场，预祝大家能收获好成绩！

批改了几十年的考研卷子，几点建议供大家参考：

1、答案是空白，老师不会给分；

2、字尽量写的大一点，端正一点，行与行要有间距，便于老师阅卷；（老师一天要批改上千道题目）

3、突出答案中的关键部分（如平均等待时间等数字），避免阅卷老师漏掉；

4、代码加注释，避免老师短时间内看不懂你写的代码；

5、先写答案，再写过程。如在银行家算法中问是否处于安全状态，先回答是否处于安全状态，再说明理由（没有理由可能会扣分。另外，即使回答是否处于安全状态你回答错了，如果有计算过程也能得部分分数）。

第一章 导论

1.1 什么是操作系统

定义

操作系统是内核（Kernel）：一直运行在计算机上的程序，内核不运行则计算机无法运行。

目的

• 核心目标：运行程序
• 面向系统：高效使用计算机
• 面向用户：方便使用计算机

功能

操作系统是资源分配器

• 管理所有资源
• 面对冲突的资源请求，决定如何分配资源，以便系统能有效公平运行

操作系统是控制程序

• 管理用户程序运行，以防计算机资源的错误使用或使用不当

操作系统是计算机最底层的软件

现代计算机系统

现代计算机系统通常包含一个或多个CPU和内存、若干通过总线相连的设备控制器及其设备、总线、CPU和设备控制器可以并行工作，并竞争内存。

CPU和设备间的交互

• 每个设备控制器有一个本地缓冲

• CPU在内存和本地缓冲之间传输数据

• I/O控制器从设备到本地缓冲之间传输数据

• 控制器通过中断通知CPU完成操作

  • 中断是指当出现需要时，CPU暂时停止当前进程的执行，转而处理新情况的中断处理程序。

1.2 多道程序设计和分时

简单批处理系统（单道程序设计）

用户将一批作业（批处理作业）提交给操作系统后就不再干预，由操作系统控制它们自动运行。

• 每个时刻只执行一个作业，自动从一个运行完的作业切换到下一个作业
• 实现了自动化作业调度（由常驻监控程序Monitor（简单批处理系统的核心）实现）
  • 控制作业传输
  • 调度作业运行
  • 自动从一个运行完的作业转换到下一个作业
• 可以在无需人工干预的条件下运行作业（不具有交互性）

多道程序系统（多道程序设计）

在内存中同时存在多道作业，在管理程序控制下相互穿插运行。

目的：提高CPU利用率

并行和并发

并行：微观上，两个或多个作业在同一时刻运行

并发：宏观上，两个或多个作业在同时运行；但微观上，同一时刻只有一个作业在运行，不同作业在不同时间段依次运行

分时系统

分时系统是针对交互作业设计出来的，是多道程序设计的延伸。e.g. Unix

• 联机的多用户交互式操作系统

• 采用时间片轮转方式使一台计算机为多个用户服务

• 在单位时间内，每个用户获得一个时间片并运行

• 保证用户获得足够小的响应时间，并提供交互能力

1.3 操作系统类型

1. 大型机系统
   1. 简单批处理系统
   2. 多道程序系统
   3. 分时系统
2. 桌面系统
   • 适用于PC
3. 嵌入式系统
   • 完全嵌入受控器件内部，为特定应用设计的专用计算机系统
4. 手持（移动）系统
   • 适用于手持设备，如手机、平板
5. 分布式系统
   • 又称松耦合系统
   • 通过网络通信：TCP/IP
   • 目前没有真正意义上的分布式操作系统
6. 多处理器系统
   • 有多个紧密通信的处理器的系统。多个处理器共享计算机总线、内存和外设等。紧耦合系统。
   • 优点：节省资金（因为共享其他设备）、增加可靠性、增加吞吐量
   • 对称多处理（SMP）：每个处理器运行操作系统的相同副本
   • 非对称多处理（ASMP）：各个处理器不对等，一个主处理器，若干从处理器（如骁龙820）
7. 集群系统
   • 通过专用网络连接一群计算机，将这些计算机虚拟化为一台有超强算力的计算机。

1.4 操作系统操作和功能

操作

双模式

用户模式和内核模式

用以解决程序运行中出现的问题：除以零、死循环等，允许OS保护自身和其他系统部件

双模式需要CPU的支持，如果CPU有模式位，则可以在操作系统中实现双模式

内核模式的模式位为0，用户模式的模式位为1

在用户模式中，只能运行用户自编的应用程序

在内核模式中，可以运行OS内核程序（特权指令），包括I/O指令、置中断指令等

用户可以通过系统调用和软件中断执行特权指令

I/O保护

I/O指令都是特权指令，防止用户执行非法I/O

内存保护

通过硬件支持（基址寄存器+限长寄存器）的存储保护机制，防止内存非法访问

定时器

如果用户程序死循环或不调用系统调用，那么操作系统就无法获得CPU的控制权并对系统进行管理

所以引入定时器，在一段时间后发生中断，将CPU控制权返回给操作系统

也需要硬件支持

功能

进程管理、内存管理、文件管理、I/O系统管理、其他

---

第二章 操作系统结构

2.1 操作系统服务和接口

操作系统以服务形式向程序和用户提供环境执行程序

三种基本服务形式

提供给程序的服务形式：系统调用

• 系统调用可以供程序通过应用程序接口（API）访问
• 三种常用API：Windows的Win32 API、POSIX系统的POSIX API、Java虚拟机的Java API

提供给用户的服务形式：用户接口、系统程序

• 用户接口：命令行接口（CLI）、图形接口（GUI）

  • 智能手机采用的人机交互接口有：命令行接口、图形接口、声控接口

• 系统程序：用以管理、维护操作系统

  • 文件管理（文件资源管理器）、状态信息（这台电脑->管理）、通信等

2.2 操作系统结构

1. 简单结构（无结构）：MS-DOS、早期Unix
2. 层次结构：每层只能使用相邻低层次的功能和服务（THE、iOS）
3. 微内核（Mach、Windows NT、 Windows 2000）
   • 便于移植、更稳定、更安全（适合服务器）
   • 用户空间和内核空间通信的系统开销增加 ——> 提出了消息传递机制
4. 模块结构：大部分现代操作系统采用（Linux、Solaris）
   • 每个核心部件分开
   • 每个模块在需要时被加载到内核
5. 混合结构：MacOS

2.3 虚拟机

定义：虚拟机是通过软件模拟实现，具有完整硬件系统功能，并运行在一个完全隔离环境中的完整计算机系统

常见的虚拟机有三种

1. 高级语言虚拟机（JVM）
   • 用以模拟代码运行，实现跨平台
   • 运行在操作系统上
2. 工作站虚拟机（VMWare Workstation、Virtual Box）
   • 面向工作站和PC，使得多个操作系统可以在一个计算机上使用
   • 客户操作系统运行在宿主操作系统上
3. 服务器虚拟机（阿里云、腾讯云等）
   • 多用户、多操作系统并存
   • 把服务器的物理资源抽象成逻辑资源，让一个物理计算机虚拟化为多个相互隔离的虚拟服务器
   • 直接运行在硬件上

---

第三章 进程

3.1 进程概念

进程：一个程序在一个数据集上的一次运行

进程和程序的区别

• 进程是程序的一个实例，是程序的一次执行；程序是进程的代码部分

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

• 进程在内存中，程序在外存中

进程的组成

进程包括

• 代码（程序段）
• 当前活动：程序计数器PC、堆栈(包括函数参数、返回地址、局部变量）、数据（包括全局变量）、堆（进程运行时动态分配的内存）

进程的状态

运行态：指令在执行

等待态：等待资源或某些事件发生，满足条件后转化为就绪态

就绪态：等待分配处理器（时间片），满足条件后转化为运行态

新建态：创建进程

终止态：进程执行完毕

进程控制块（PCB）

PCB在内核空间中，是进程在操作系统中的唯一标志

PCB中包含了和进程有关的信息：进程状态、程序计数器、CPU寄存器、CPU调度信息、内存管理信息、记账信息、I/O状态信息

进程的上下文切换需要PCB保护和恢复现场

3.2 进程操作

进程创建

父进程创建子进程，如此轮流创建进程，构成一棵进程树

资源共享的三种方式

• 父进程子进程共享所有资源
• 子进程共享父进程资源的子集
• 父进程和子进程之间无资源共享

执行顺序

• 父进程和子进程并发执行（默认）
• 父进程等待，直到子进程执行完成为止（父进程调用wait系统调用）

地址空间

• 子进程复制父进程的空间（与父进程具有相同的程序和数据）（fork）
• 子进程装入另一个新程序

fork

Linux中用系统调用fork()来创建子进程。fork()创建的子进程和父进程有不同的PID ，但是它们共享相同的代码空间和资源（通过虚拟存储的写时复制技术实现），相当于复制了父进程。

通过fork()的返回值区分父子进程：

• 如果子进程创建失败，fork()返回-1

• 如果创建成功，fork()在父进程中返回新创建的子进程的PID，在子进程中返回0

进程终止

当进程完成执行最后语句并且通过系统调用exit()请求操作系统删除自身时，进程终止。

进程结束的方式

1. 进程执行最后一项并退出（exit）

   • 进程执行完最后一项并退出

   • 操作系统收回进程的资源

2. 父进程终止子进程的执行（abort）

   • 通常使用这种方式结束进程是由于以下几种原因

     • 子进程超量分配资源

     • 赋予子进程的任务不再需要

     • 父进程终止

3. 父进程可等待子进程的结束（abort）

   • 父进程通过调用wait()系统调用来等待子进程结束

   • fork()创建子进程之后，父进程和子进程的运行顺序是不固定的，有可能还没有执行子进程，父进程就先结束了。我们需要让子进程先执行，然后再执行父进程，就要用wait()，让父进程等子进程运行完。

进程通信

独立与协同进程

独立进程：不会影响另一个进程的执行或被另一个进程执行影响

协同进程：可能影响另一个进程的执行或被另一个进程执行影响

进程间通信（IPC）的两种模式

1. 共享内存：一块内存在多个进程间共享

以最快的速度进行方便的通信，一般用于大数据通信

生产者-消费者

2. 消息传递：建立连接后使用send和receive操作交换信息

用以交换较少数量的数据

消息传递分为直接通信和间接通信

• 直接通信：需要通信的每个进程必须明确指定通信的接收者或发送者

• 间接通信：消息导向至信箱并从信箱接收，两个进程只有拥有一个共享信箱时才能通信

  • 进程间采用间接通信方式时，在消息中必须给出信箱名

消息传递分为阻塞（同步）和非阻塞（异步）

• 阻塞send：发送进程阻塞，直到消息被接收
• 阻塞receive：接收者进程阻塞，直到有消息可用
• 非阻塞send：发送进程发送消息并继续操作
• 非阻塞receive：接收者收到一个有效消息或无效消息

其他

Tips

• 进程的创建和终止都是原子操作
• 原子性必须需要硬件的支持
• 进程创建时，进程将被设置为就绪态，不会为其分配CPU
• 单任务操作系统不需要进行进程上下文切换
• 进程创建原语的任务主要是为进程建立PCB表
• 进程操作的原语有：创建原语、唤醒原语、阻塞原语、撤销原语（没有延迟原语）

---

第四章 线程

4.1 什么是线程

线程是在CPU上运行的基本执行单位；进程上的一个代码片段可以被创建为一个线程

进程仍然是资源分配的基本单位；线程本身不拥有系统资源，而是向进程申请资源

每个线程含有一个栈

引入线程的原因

性能角度

• 操作进程对系统而言开销大

应用角度

• 进程代码并行执行的需求

硬件角度

• 充分利用多核处理器的并行特性
• 加速进程运行

线程和进程的联系和区别

代码

• 进程包含线程
• 线程是进程中的一段代码

资源

• 进程是资源分配的基本单位
• 线程不拥有资源，共享使用进程的资源

调度

• 线程是基本的调度单位
• 同一进程中的线程切换不引起进程切换

切换

• 进程：重量级，上下文切换代价大
• 线程：轻量级，切换代价小

生命期

• 进程撤销会导致它的所有线程被撤销
• 线程撤销不影响进程

线程数据结构

线程控制块（TCB）

TCB包含在PCB中

含有：线程ID，程序计数器，寄存器集，栈空间

线程的优点

• 响应度高：线程创建开销小。（e.g. Web服务器）
• 资源共享
• 经济性：线程创建和上下文切换比进程快
• 充分利用多处理（MP）结构

4.2 线程模型

用户线程

定义：由用户线程库进行管理的线程

• 用户线程的创建和调度在用户空间中，不需要内核的干预
• 内核看不见用户线程

内核线程

定义：由内核进行管理的线程

• 需要内核支持，由内核完成调度
• 由内核进行创建和撤销

多线程模型

多对一模型：多个用户线程对应一个内核中的用户进程，用于不支持内核线程的操作系统

• 内核只看到一个进程，多个线程不能并行运行在多个处理器上
• 进程内线程切换不会导致进程切换（减少系统开销）
• 一个线程的系统调用会导致整个进程阻塞

一对一模型：用户线程映射到内核线程（Windows中普遍采用）

• 并发性好：多个线程可以并行运行在多个处理器上
• 内核开销大

多对多模型：多个用户线程映射为相等或更小数目的内核线程

• 并发性和效率兼顾，但增加了复杂度

4.3 线程库

线程库为程序员提供API来创建和管理线程

两种模式

1. 用户库（用户线程）
   • 存在于用户空间
   • 调用线程库不会产生系统调用
2. 内核库（内核线程）
   • 存在于内核
   • 操作系统支持
   • 调用线程库会产生系统调用

常见线程库

PThreads线程库

• 线程的POSIX标准
• 多是用户线程

Java线程库

两种创建方法

1. 扩展java.lang.Thread类
2. 实现Runnable接口

• 由JVM管理
• 用户线程，操作系统不可见

Win32线程库

可能会产生系统调用

Tips

• 同一个进程中的线程，不能共享堆栈
• ‌线程是比进程更小的能独立运行的基本单位
• 一个线程的TCB中不包括打开文件列表
• Java中的线程有六种状态

---

第五章 CPU调度

5.1 CPU调度概述

三种调度

调度	作用	开销	频率
长程/作业调度	将作业由新建态转换到就绪态	大	高（秒）
短程调度	调度程序选择下一个执行进程	小	低（毫秒）
中程调度	将进程在内存和外存换进换出	中	中

处于新建状态的进程一般首先被放到外存的进程池中，经过长程调度放入内存，转换为就绪状态

中程调度又称交换，将进程在内存和外存之间换进换出，目的是节省内存空间

调度过程

调度程序（Scheduler）

根据某种策略（调度算法）选择内存中的一个就绪进程

分派程序（Dispatcher）

负责具体的进程切换工作：

• 负责把CPU的控制权转交CPU调度程序
• 切换上下文
• 切换到用户态
• 跳转到用户程序的适当位置并重新运行

调度方式

非抢占式调度

一旦把CPU分配给某进程之后，系统不可以抢占已分配的CPU并分配给其他进程

特点：易实现、系统开销小、适合批处理系统；响应时间长，不适合交互式系统

发生时机：

1. 从运行转到等待
2. 进程终止运行

抢占式调度

调度程序可根据某种原则暂停某个正在执行的进程，将已分配给它的CPU重新分配给其他进程

特点：可防止单一进程长时间独占CPU；系统开销大

发生时机：

1. 从运行转到就绪
2. 从等待转到就绪

基本指标

• CPU利用率：固定时间内CPU运行时间的比例
• 吞吐量：单位时间内运行完的进程数
• 周转时间：T完成时间 - T到达时间
• 响应时间：T首次运行 - T到达时间
• 等待时间：进程等待调度（不运行）的时间总和

5.2 先来先服务和短作业优先

先来先服务（FCFS）

短作业优先（SJF）

SJF算法的就绪队列是按照进程的下一个CPU脉冲时间排列

非抢占式

抢占式

被称为最短剩余时间优先调度，缩写为SRTF

• SJF调度算法拥有最短的平均等待时间
• 但是存在饥饿问题

5.3 优先级调度和时间片轮转

优先级调度（PR）

目前主流的操作系统调度算法

优先级类型

• 静态优先级
  • 进程创建时确定优先级，运行期间不变
  • 可能产生饥饿问题（解决方法：老化，视进程等待时间的延长提高其优先级）
• 动态优先级
  • 进程的优先级随着进程推进或等待时间增加而改变
  • 高响应比优先调度算法（响应比 = 等待时间/运行时间）

抢占式

非抢占式

时间片轮转（RR）

一般来说时间片轮转调度算法能够获得最短响应时间

5.4 多级队列和多处理器调度

多级队列调度（MLQ）

针对不同的进程使用不同的调度算法：允许系统中存在多个就绪队列，每个就绪队列有自己的调度算法

核心问题

• 队列数
• 每个队列的调度算法（每个队列的调度算法可以相同、可以不同）
• 决定新进程将进入哪个队列的方法

多级反馈队列调度（MLFQ）

进程在其运行过程中，能在不同队列间移动

Unix, Solaris, Windows的调度算法都是MLFQ的变种

核心问题

• MLQ需要考虑的问题
• 决定进程升级（低级队列到高级队列）和降级（高级队列到低级队列）的方法

多处理器调度

适用多核处理器的CPU调度

亲和性：进程在某个给定的CPU上尽量长时间运行而不被迁移到其他处理器的倾向性

软亲和性：操作系统试图保证进程运行在同一处理器上（但不保证一定）

• 进程通常不会在处理器之间频繁迁移

硬亲和性：操作系统提供系统调用支持硬亲和性，使得进程运行在某个处理器子集上

• 进程不会在处理器之间迁移

负载平衡

将负载平均分配到SMP系统的所有处理器

对于有些系统（处理器具有私有的可执行进程的队列），负载平衡是必需的；对于具有公共队列的系统，负载平衡通常没有必要，因为一旦处理器空闲，就可以从公共队列中取出一个可执行进程。

单队列调度方法（SQMP）

系统有一个公共就绪队列；当任意一个CPU空闲时，就从就绪队列中选择一个到该CPU上运行

优点

• 容易从单核调度算法推广到多核/多处理器
• 实现简单，负载均衡

缺点

• 不具有亲和性
• 加锁问题

多队列调度方法（MQMP）

系统有多个队列，每个CPU一个；每个就绪队列有自己的调度算法，并且调度相对独立

优点

• 亲和性好
• 不需要加锁

缺点

• 负载不均衡

Tips

• 为了照顾紧迫型进程，应采用PR调度策略
• 一般来说，能够获得最短响应时间的调度算法是RR算法
• 一般来说，能够获得最短平均等待时间的调度算法是SJF算法
• SJF算法的就绪队列是按照进程的下一个CPU脉冲时间排列
• 对短作业不利的调度算法是FCFS

---

第六章 进程同步

6.1 临界区

同步和互斥

同步：协调进程的执行次序，使并发进程间能够有效地共享资源、相互合作，保证数据一致性

互斥：进程排他性地运行某段代码，任何时候只有一个进程能够运行

临界资源：一次只允许一个进程使用的资源

共享资源：一次允许多个进程使用的资源

临界区：涉及临界资源的代码片段；由程序员确定

• 互斥准则
• 有空让进
• 有限等待

6.2 信号量

整型信号量

信号量 S 是整型变量

原子操作

wait(S) / P(s)

signal(S) / V(s)：V操作唤醒的进程状态可能会变为就绪态

存在忙等问题

记录型信号量

分为计数信号量和二值信号量

在整型信号量的基础上增加了一个等待队列

通过加入了阻塞和唤醒机制，消除了忙等

当一个进程无法获得一个信号量时，马上释放CPU并把自己转换为等待状态，加入该信号量的等待队列，从而消除忙等

信号量S的使用

• S必须置一次初值且只能置一次初值
• S初值不能为负数
• 除了初始化，只能通过执行P、V操作访问S

互斥信号量的使用

Semaphore *S; 
S->value = 1;       // 初始化为1
wait(S);
CriticalSection();  // 临界区
signal(S);

同步信号量使用

// 例如P1和P2需要比C1和C2先运行
Semaphore S;
S->value = 0;  //初始化为0
P1:
	C1;
	signal(S);
P2:
	wait(S);
	C2;

6.3 经典问题

生产者消费者

semaphore *full, *empty, *mutex;
full->value = 0, empty->value = N, mutex->value = 1;

Producer() {
	prodece();
	wait(empty);
	wait(mutex);
	put in;
	signal(mutex);
	signal(full);
}

Consumer() {
	wait(full);
	wait(mutex);
	take out;
	signal(mutex);
	signal(empty);
}

读者写者

• 允许多个读者同时读
• 不允许多个写者同时写
• 不允许读者、写者同时读写

（1）读优先：要求指一个读者试图进行读操作时，如果这时正有其他读者在进行操作，他可直接开始读操作，而不需要等待。

/*
读优先
*/
// rc是读者计数器，当第一个读者开始读时，给临界区加锁，写者无法写，但其他读者依然可以读
// 当最后一个读者读完，rc == 0时，释放临界区，写者可以写
// rc本身也是临界资源，使用互斥信号量rmutex
semaphore rwmutex = 1;  // 用于写者与其他写者/读者互斥访问共享数据
semaphore rmutex = 1;   // 用于读者互斥访问
int rc = 0;

procedure reader_i:
	P(rmutex);
	rc ++;
	if(rc == 1) P(rwmutex);  // 如果是第一个开始读的，就给临界区加锁，不允许写者写
	V(rmutex);
	读数据;
	P(rmutex);
	rc --;
	if(rc == 0) V(rwmutex);  // 如果是最后一个读完的，就给临界区解锁，允许写者写
	V(rmutex);

procedure writer_i:
	P(rwmutex);
	写数据;
	V(rwmutex);

（2）写优先：一个读者试图进行读操作时，如果有其他写者在等待进行写操作或正在进行写操作，他要等待该写者完成写操作后才开始读操作。

/*
写优先
多个读者可以同时进行读
写者必须互斥
写者优先于读者（一旦有写者，后续的读者都必须等待写完）
*/
semaphore rwmutex = 1;  // 用于写者与其他写者/读者互斥访问共享数据
semaphore rmutex = 10;  // 假设有10个读者进程

procedure reader_i:
	P(rwmutex);  // 读写互斥，在写者已经在写时不能读，读者在读时不能写
	P(rmutex);
	V(rwmutex);  // 释放读写互斥
	读数据;
	V(rmutex);

procedure writer_i:
	P(rwmutex);
	for (int i = 0; i < 10; i ++) P(rmutex);  // 禁止新读者，并等待已进入的读者退出
	写数据;
	for (int i = 0; i < 10; i ++) V(rmutex);  // 恢复允许rmutex值为10
	V(rwmutex);

哲学家就餐

防止死锁可采取的措施

• 最多允许（筷子数 - 1）个哲学家同时坐在
• 仅当一个哲学家左右两边筷子都可用时，才允许他拿筷子
• 给所有哲学家编号，奇数哲学家必须先拿左边筷子，偶数哲学家反之
• 增加一根额外的筷子

6.4 管程

由编程语言解决同步和互斥问题；引入管程可以方便程序员在代码中实现同步

---

第七章 死锁

7.1 死锁概念及其资源分配图

死锁：一组等待进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源

死锁的必要条件

互斥：一次只有一个进程可以使用一个资源

占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源

不可抢占：一个资源只有当持有它的进程完成任务后，才会自由地释放

循环等待：等待资源的进程之间存在环

资源分配图

1. 如果资源分配图没有环，那么系统就不处于死锁状态
2. 如果资源分配图有环，那么系统可能处于死锁状态

如果每个资源类型刚好有一个实例，那么有环就意味着已经出现死锁（充分必要）；如果每个资源类型有多个实例，那么有环并不意味着出现了死锁（必要非充分）。

死锁处理方法

一般来说，处理死锁问题有三种方法：

1. 通过协议来预防或避免死锁，确保系统不会进入死锁状态
2. 可以允许系统进入死锁状态，然后检测并恢复
3. 忽略这个问题（被大多数操作系统所采用）

忽略死锁的可能性要比其他方法更便宜。对于许多系统，死锁很少发生（如一年一次），发生之后人工重启系统即可。所以和死锁预防、死锁避免和死锁检测与恢复相比，这种方法更便宜。

7.2 死锁预防

死锁预防是一组方法，确保至少一个上述的必要条件不成立

通过限制资源申请的方法来预防死锁，降低了设备使用率和系统吞吐量

互斥

如系统存在互斥资源，不能改变这个条件来预防死锁

占有并等待

必须保证进程申请资源的时候没有占有其他资源

• 静态分配策略
• 要求进程在执行前一次性申请全部的资源或要求进程只有在没有资源时才可申请资源
• 利用率低，可能出现饥饿

非抢占

当一个进程处于等待时，如果其他进程申请其拥有的资源，那么该进程的部分资源可以被抢占

循环等待

对所有的资源类型进行总排序，并且要求进程按照递增顺序申请资源，先申请数量少的资源，用完并释放后再申请数量多的

7.3 死锁避免

获得以后如何申请资源的附加信息来决定是否分配资源

死锁避免算法动态检查资源分配状态以确保循环等待条件不可能成立

资源分配图算法

适用于每个资源类型只有一个实例的系统

需求边（虚线）、请求边、分配边

请求能满足的前提是：把请求边转换为分配边后不会导致环存在。如果有环存在，那么分配会导致系统处于非安全状态

通过采用环检测算法（$O(n^2)$）检查安全性

银行家算法

适用于每个资源类型有多个实例的系统

安全算法+资源请求算法

7.4 死锁检测和恢复

死锁检测

单个实例 —— 资源等待图

资源等待图是资源分配图的简化，适用于每种资源类型只有单个实例的系统

若等待图中有环，则系统一定产生了死锁

为检测死锁，系统需要维护等待图，并周期调用环检测算法，复杂度为$O(n^2)$

多个实例

类似银行家算法中的安全算法，只不过把Need换成Request，Finish[]中值为false的元素即为发生死锁的进程

死锁恢复

1. 操作员人工恢复
2. 自动恢复
   1. 终止进程
      1. 中断所有的死锁进程
      2. 一次中断一个进程直到死锁消失
   2. 抢占资源

总结

死锁产生的必要条件：

1. 互斥
2. 持有并等待
3. 非抢占
4. 循环等待

死锁处理的方法：

1. 死锁预防：确保至少一个死锁产生的必要条件不发生（其中互斥条件无法改变）
2. 死锁避免：
3. 死锁的检测与恢复

Tips

• 死锁避免方法不会限制用户申请资源的顺序；死锁预防的破坏循环等待条件才会
• 所有进程都被挂起时，系统不一定陷入死锁
• 每个死锁进程必然占据了某类资源 <–错误，因为可能有的资源本身没有占有资源，但是在等待被占有的资源，此时它也处于死锁中。比如汽车过桥问题中，不在桥上但不能过桥的汽车。
• 在为多道程序所提供的系统资源不足时，可能出现死锁。但是，不恰当的进程推进顺序也可能产生死锁
• ‏当检测出发生死锁时，可以通过撤销一个进程解除死锁（错误，可能需要撤销多个进程才能解除死锁）

---

第八章 内存管理

8.1 内存管理背景

内存管理的目的

1. 提高内存利用率
2. 提高内存数据访问的速度
3. 进行存储保护

基本硬件

CPU可以直接访问的通用存储只有内存和处理器内置的寄存器

程序必须装入内存才能被执行

内存保护

保护用户进程不会相互影响

内存保护通过硬件来实现，因为操作系统通常不干预CPU对内存的访问（会导致性能损失）

内存保护的一种可能方案：

动态重定位

• 确保每个进程都有一个单独的内存空间。
• 基址寄存器：含有最小的合法的物理内存地址
• 界限寄存器：指定了范围的大小
• 只有操作系统可以通过特殊的特权指令，才能加载基址寄存器和界限寄存器

地址绑定

程序以二进制可执行文件的形式存储在磁盘上，为了执行，程序被调入内存并放在进程中。

地址绑定通常发生在以下三个时期：

1. 编译时：如果在编译时就已经知道进程将在内存中的驻留地址，那么就可以生成绝对代码
2. 加载时：如果在编译时不知道进程将驻留在何处，那么编译器就生成可重定位代码
3. 执行时：如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定应延迟到执行时才进行（绝大多数操作系统采用）

逻辑地址和物理地址

逻辑地址（虚拟地址）：CPU生成的地址

物理地址（实地址）：内存单元看到的地址

从逻辑地址到物理地址的运行时映射是由内存管理单元（MMU）的硬件设备来完成

动态加载

为了获得更好的内存空间利用率，可以使用动态加载。此时，一个程序只有在调用时才会加载，所有程序都以可重定位加载格式保存在磁盘上。

动态加载不需要操作系统提供特别支持。

动态链接库

动态链接库为系统库，将各种库文件的连接被推迟到执行时期。

与动态加载不同，动态链接通常需要操作系统的帮助。

8.2 连续内存分配

连续内存分配是早期内存分配方式，运用于内存较少的系统

涉及三种类型：单一连续分配、固定分区分配、可变分区分配

单一连续分配

单道程序环境下，仅装有一道用户程序，整个内存的用户空间由该程序独占，这种分配方案称为单一连续分配

固定分区分配

预先把可分配的主存空间分割成若干个连续的区域，称为一个分区

每个分区的大小可以相同也可以不同，但分区大小固定不变，每个分区只能装入一个程序

可变分区分配

可变分区分配是固定分配分区的延伸，主要用于批处理系统

对于可变分区方案，操作系统有一个表，用于记录哪些内存可用和哪些内存已用。开始，所有内存都可用于用户进程，因此可以作为一大块的可用内存，称为孔。最后，内存中会有一个集合，包含各种大小的孔。

存储分配算法

• 首次适应：分配首个足够大的孔
• 最佳适应：分配最小的足够大的孔
• 最差适应：分配最大的孔

在速度和存储空间的利用上，首次适应和最佳适应要好于最差适应（但是会产生外部碎片）

• 减少碎片的方法：紧缩，把小的空闲内存结合成一个大的块（必须得到动态重定位的支持才能采用）

8.3 分页内存管理

由连续分配方式发展为分页存储管理方式的主要动力是：提高内存利用率

每个进程拥有一张页表，且进程的页表驻留在内存中（不是只有执行进程的页表驻留）

允许进程的物理地址空间可能不连续

将物理内存分成大小固定的块，称为帧

将逻辑内存分成同样大小的块，称为页

地址转换机制

CPU生成的每个地址分为两部分：页码和页偏移。页码作为页表的索引，页表包含每页在物理内存的基地址，这个基地址和页偏移的组合就成了物理内存地址，可发送到物理单元。

注意页表项中只有帧号，所以一个32位的页表项可以指向$2^32$个物理帧的任意一个

硬件支持

如果页表比较小，可以将页表存放于寄存器中。但如果页表较大（例如100万个条目），就只能存放于内存中

页表基地址寄存器（PTBR）指向页表，改变页表时只需要改变这一寄存器即可，这大大降低了上下文切换的时间

转换表缓冲区（TLB）中存放页码和帧码

假设寄存器的查找需要时间为a，访问一次内存时间为b，命中率为$\lambda$
$$
有效访问时间EAT=\lambda(a+b)+(1-\lambda)(a+2b)
$$

页共享

如果代码是可重入代码（只读），可以在进程间共享；共享代码出现在所有进程的逻辑空间的相同位置

8.4 页表结构

层次页表

哈希页表

虚拟页号被散列到一个页表中，这种页表的每一个条目都包括了一个链表元素（拉链法处理碰撞），这些元素哈希成同一位置

页表中每个元素有三个域：虚拟页号、所映射的帧号、指向下一个元素的指针

反向页表（倒置页表）

反向页表适用于进程较多的系统

通常来说，每个进程都有一个页表，而每个页表有很多项，需要消耗大量物理内存。为了解决这个问题，可以使用反向页表。反向页表对于每个真正的内存页或帧才有一个条目。每个条目保存真正内存位置的页的虚拟地址，以及拥有这个页的进程的信息。

整个系统只有一个页表，对每个物理内存的页也只有一条对应的条目

8.5 分段内存管理

分段的特点

• 支持用户观点的内存管理机制
• 逻辑地址空间是由一组段组成的，每个段都有名称和长度，地址指明了段名称和段内偏移
• 可以实现有意义的共享
• 方便进行地址转换
• 程序不需要连续的内存
• 在段式存储管理中，一个段是不定长的连续区域
• 会产生外部碎片（两个段中间的空闲区有可能过小而无法分配给其他程序段）

	地址	由谁确定	存储
分页	逻辑地址连续，一维	操作系统	各页可以分散存放在主存
分段	逻辑地址不连续，二维	用户	每段必须采用连续的主存空间

8.6 内存“扩充”技术

为了解决内存空间不足的问题所产生的技术

虚拟内存

覆盖

在程序执行过程中，程序的不同部分相互替换，只在内存中保留那些在任何时间都需要的指令和数据

• 现代操作系统一般不用
• 由程序员声明覆盖结构，不需要操作系统的特别支持

交换

把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上的备份区，再把已具备运行条件的进程或进程所需的程序或数据调入内存

• 交换较为耗时（100MB大约4S）
• 交换时间的主要部分是转移时间，总的转移时间直接同交换的内存数量成正比
• 标准交换技术在现代操作系统中一般很少使用

其他

Tips

1. 采用覆盖和交换技术的目的是减少程序占用的主存空间
2. 采用覆盖技术不需要操作系统的支持
3. 采用交换技术需要I/O支持
4. 每个进程拥有一张页表，且进程的页表驻留在内存中
5. 存在内部碎片的存储管理方式：固定分区分配、单一连续分配、段页式存储管理
6. 存在外部碎片的存储管理方式：可变分区分配、段式存储管理
7. 实现进程间数据共享最方便的存储管理技术是分段
8. 在页式存储管理中，引入快表可以减少每一次的内存访问时间（错误，引入快表只能减少平均的内存访问时间，而不是每次内存访问时间）
9. 对于通用计算机而言，存储层次分为四层：CPU寄存器。 高速缓存、主存和辅存
10. ‏采用动态重定位方式装入的作业，其地址变换工作是在每执行一条指令时完成的。

---

第九章 虚拟内存

内存不够进程运行 -> 虚拟内存技术

虚拟内存使用请求分页技术实现 -> 如何处理缺页、页置换、给进程分配页框数等问题

页置换问题 -> 页置换算法

给进程分配页框 -> 固定分配、优先级分配；颠簸问题

内核内存分配 -> buddy, slab

9.1 虚拟存储技术

局部性原理

虚拟存储技术

当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动将它们从磁盘调入内存执行

虚拟内存大小由：操作系统字长和内外存容量和共同决定

使用虚拟内存的共享库

通过将共享对象映射到虚拟地址空间，系统库可以被多个进程所共享

虚拟内存允许进程共享内存

虚拟内存可允许在创建进程期间共享页，从而加快进程创建（fork）

写时复制(Copy on Write)

允许父进程和子进程在初始化时共享页面

虚拟内存的实现

1. 虚拟页式
   1. 请求分页
   2. 预调页
2. 虚拟段式

9.2 请求分页

进程开始运行之前，不是装入全部页面，而是装入一个或零个页面。运行之后，根据进程需要而动态装入其它页面。当内存空间已满，需要装入新的页面时，则根据某种算法置换内存中的某个页面，以便装入新的页面。

有效-无效位

请求分页的实现需要在页表的表项中增加一个“有效-无效位”，1表示在该页在内存，0表示不在内存。在所有的表项中，这个位被初始化为0

缺页中断

如果访问的页不在内存，系统陷入缺页中断。此时系统决定终止执行指令或将该页从外存中调入内存，再更改页表，然后重启指令

缺页中断属于程序中断

请求分页讨论

极端情况下，进程创建时未被分配内存，导致进程执行第一行代码开始就不断产生缺页中断。这种情况被称为纯请求分页

请求分页性能

缺页率： $0<= p <= 1$

有效访问时间（EAT）：

$$EAT = (1-p) \times 内存访问时间 + p \times 页错误时间$$

页错误时间 = 处理缺页中断 + [页交换出去的时间] + 读入页时间 + 重启进程开销

9.3 页面置换

页置换过程

1. 将待置换的帧换出至磁盘
2. 修改页表，将换出的帧有效位设置为i
3. 将待换入的页换入内存
4. 修改页表，将换入的帧有效位设置为v

页置换讨论

1. 如果发生页置换，则缺页处理时间加倍
2. 通过修改位或脏位来防止页面转移过多（只有修改过的页面才换出到磁盘，否则直接舍弃）

页置换算法

1. 先进先出算法（FIFO）：可能会导致Belady异常（页框更多->缺页更多）。使用FIFO队列来管理内存中所有的页。

2. 最优置换算法（OPT）：置换将来不再需要的页（无法实现）

3. 最近最少使用算法（LRU）：置换最长时间没有使用的页。需要一个计数器或栈来实现（开销大，需要硬件支持）

4. 不经常使用算法（NFU）：将每个页面与一个软件计数器相关联，每次时钟中断时，将每个页面的R位(即访问位，值是0或1)加到它的计数器上，缺页时置换值最小的页。老化算法

5. 二次机会算法：以循环链表的形式存储所有的页，为每个页设置R位，如果将要交换的页访问位是0则直接置换；如果是1则将其置零，然后对后面的页执行相同的操作。实现：时钟置换

9.4 页框分配和颠簸

固定分配

平均分配：100个页框，5个进程，每个进程分配20个页

按比例分配：根据每个进程的大小来分配

优先级分配

按照优先级而不是进程大小来使用比率分配策略

如果进程Pi产生一个缺页：

1. 可能选择替换Pi自己的页框
2. 可能从一个较低优先级的进程中选择一个页面来替换

全局置换和局部置换

全局置换：进程在所有的页框（包括其他进程的）中选择一个替换页面

局部置换：每个进程只从属于自己的页框中选择

颠簸（抖动）

颠簸：一个进程的页面经常换入换出

工作集（Working Set）

假如进程Pi最近的10个引用（称为工作集窗口）是：2 6 1 5 7 7 7 7 5 1，那么在这10个引用中，它的工作集就是${1,2,5,6,7}$

缺页率（PFF）策略

设置一个可接受的缺页率，如果缺页率太低，回收一些进程的页框；如果缺页率太高，就分给进程一些页框

9.5 内核内存分配

内核内存不同于用户内存，通常从空闲内存池中获取，因为：

1. 内核需要为不同大小的数据结构分配内存
2. 一些内核内存需要连续的物理页
3. 占用内存块的时间比较短

伙伴（Buddy）系统

主要思想：内存按2的幂的大小进行划分，组成若干空闲块链表；查找链表找到满足进程要求的最佳匹配块。

当分配需求小于现在可用内存时，当前段就分为两个更小的2的幂段（伙伴），继续上述操作直到合适的段大小。

• 主要用于Linux早期版本中内核底层内存管理

• 从物理上连续的大小固定的段上分配内存

优点：可通过合并而快速形成更大的段

缺点：容易产生碎片

Slab分配

主要思想：

Slab层把不同的对象划分为所谓的Cache组，每个Cache都存放不同类型的对象（例如一个Cache存放task_struct结构体，另一个Cache存放struct_inode结构体）。

Slab是由一个或多个物理上连续的页组成，每个Cache又由一个或多个slab组成。

每个内核数据结构都有一个Cache（如进程描述符、文件对象、信号量等）。

Slab分配：当创建cache时，包括若干个标记为空闲的对象，对象的数量与slab的大小有关。当需要内核对象时，从cache上直接获取，并标记对象为使用。当一个slab充满了已使用的对象时，下一个对象的分配从空的slab开始分配。

优点：

1. 没有因碎片引起的内存浪费
2. 内存请求可以快速满足（因为对象预先创建，需要使用时只需要标记为使用）

9.6 虚拟内存中的其他考虑

预先调页

在纯请求调页中，进程启动初期会有大量的缺页中断

预先调页在引用前，调入进程的所有或一些需要的页面，从而减少缺页

页面尺寸

没有最佳答案，取决于考虑的方面。但总的来说，现代操作系统趋向更大的页

• 页表大小：需要大的页，从而减少页表项

• 碎片：需要小的页

• I/O开销：需要大的页，因为磁盘的寻道时间和延迟时间远超传输时间

• 程序局部：需要小的页，从而精确匹配程序局部

• 缺页次数：需要大的页，因为每次缺页会产生大量的额外开销

TLB的命中率

TLB范围：通过TLB所访问的内存量

$$TLB范围=（TLB大小）\times （页大小）$$

理想情况下，一个进程的工作集应存放在TLB中，否则会有大量的缺页中断

反向页表

I/O互锁

允许某些页在内存中被锁住

为了防止I/O出错，有两种解决方案：

1. 不允许用户内存进行I/O
2. 允许页锁在内部，锁住的页不能被置换

其他

Tips

1. 可以实现虚拟存储的存储管理方法：分页、分段、段页式

2. 缺页中断属于程序中断

3. 程序部分装入技术可带来的好处有：1.更多的进程可以并发执行，提高了CPU的利用率 2.每个进程所需的内存量更小 3.载入或交换每个用户进程到内存所需的I/O会更少 4.进程大小不再受到物理内存大小的限制

4. 请求式分页的优点：1.系统能够快速响应 2.需要很少的物理内存 3.可以支持多用户 4.需要很少的I/O

5. 在采用虚存的系统中，要求程序运行前不必全部装入内存且在运行过程中不必一直驻留在内存

---

第十章 文件系统接口

10.1 文件

文件概念

文件是计算机中信息存储的基本组织形式；是具有文件名的相关信息集合

文件结构

是指文件内信息的组织方式

目的是便于程序理解文件内容。操作系统和应用程序决定了文件的结构

常用文件结构

1. 无结构：字节流等
2. 简单记录结构：线性、固定长度、可变长度等
3. 复杂结构：格式化文档、多媒体文件等

一般可执行文件采用的文件结构是字符流

文件类型

文件类型一般由扩展名决定，如.txt .doc等

文件属性

名称

标识符：文件的唯一标记

类型

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

尺寸：文件的当前大小（以字节、块为单位）

保护：访问控制信息

时间、日期和用户标识

所有文件的信息保存在目录结构中，该目录结构保存在外存上。通常，目录条目由文件的名称及其唯一标识符组成。

文件操作

创建文件、写、读、打开、关闭、截断、删除等

打开文件操作不是一个文件系统中必须具有的操作

• 创建文件：首先要在文件系统中为文件找到空间，其次要在目录中创建新文件的条目
• 写文件：使用一个系统调用指定文件名称和要写入的位置，系统根据给定的文件名搜索目录以查找文件位置。系统保留写指针用于指向需要进行下次写操作的文件位置。
• 读文件：使用一个系统调用，指明文件名称和需要文件的下一个块应该放在哪里。系统搜寻目录找到相关条目，并保留一个读指针。
• 重新定位文件：搜寻目录找到适当的条目，并且将当前文件位置指针重新定位到给定值。
• 删除文件：在目录中搜索给定名称的文件，找到关联的目录条目后，释放所有文件空间，并删除目录条目

以上大多数操作都要搜寻目录找到对应的条目。而操作系统有一个打开文件表，用以维护所有打开文件的信息。当请求文件操作时，可通过该表的索引指定文件，而不需要搜索。

具体操作过程

创建文件：应用程序调用逻辑文件系统，逻辑文件系统分配一个新的FCB，然后将相应的目录读到内存，使用新的文件名和FCB进行更新，并将目录写回磁盘。

打开文件：系统调用open()将文件名传递到逻辑文件系统。open()首先搜索整个系统的打开文件表，以确定这个文件是否已被其他进程使用，若是，则在单个进程的打开文件表中创建一个条目，指向系统的打开文件表；若否，则根据文件名搜索目录结构，找到文件后将其FCB复制到系统的打开文件表中，再在进程的打开文件表中创建一个条目，指向系统的打开文件表。

关闭文件：进程的打开文件表的条目被删除，系统的打开数目减少。当所有打开该文件的用户关闭它时，所有更新过的数据被复制到磁盘中，系统的打开文件表条目被删除。

系统中的数据结构

• 打开文件表：跟踪打开文件，分为系统的和进程的
• 文件指针：指向最后一次读写的位置，每个进程有一个（lseek()）
• 打开文件计数器：打开文件（调用open()）次数
• 访问控制

10.2 逻辑文件及其访问方法

文件访问

文件系统的主要功能是文件访问，也就是检索、读写等操作

逻辑文件

逻辑文件指文件呈现在用户面前的组织结构，又称为文件逻辑结构；和实际在磁盘上的存储方式无关

逻辑文件决定了文件访问方法，不同的逻辑文件有不同的访问方式

顺序访问：按照存放顺序依次访问，如磁带

直接（随机）访问：可以随机访问，如磁盘、光盘

顺序文件

顺序文件是最常用的文件组织形式，由一系列不等长记录按照某种顺序排列形成。只能顺序访问

优点：记录存储紧凑

缺点：访问效率差

直接（随机）文件

采用直接访问方式，直接文件一般组织为记录等长的文件

用户提供给操作系统的块号，通常为相对块号。文件的第一相对块是0。

优点：访问效率高，可直接定位到某条记录

缺点：浪费存储空间（因为记录可能不等长，要使记录等长，就要把每条都扩充到最长记录的大小）

索引文件

为了结合顺序文件和直接文件的优点，为顺序文件建立索引表，表项等长以便随机访问，表中每项中有指针指向文件中的记录

索引文件广泛用于组织需要频繁检索的文件，如数据库文件等

对于大文件，索引文件本身可能变得太大而无法保存在内存中。解决方法是为索引文件创建索引

10.3 文件目录

文件控制块FCB

用以保存文件的各种属性信息（文件名、权限、拥有者、组、大小、修改次数等）

• 必须通过文件控制块来访问文件

目录

目录由目录项有序构成，一个目录中的目录项组成了目录文件，每个目录项存放了一个文件的各类属性

• 在有的操作系统中，目录项 = 文件控制块

• 目录是用户和文件之间的桥梁，负责把文件名转换为文件在存储设备上的位置

inode

为了减小目录项的大小，提升文件访问的效率，产生了inode

Unix为每个文件控制块建立一个索引项，内容为文件名和指向文件控制块的指针，类似于索引文件，称为Inode

inode用于描述保存给定文件的元数据的结构，例如其长度、权限以及其组成块的位置。每个inode都由一个数字（称为inumber）隐式引用。给定一个inumber，以其为偏移量，在inode的bitmap中可以定位到该inode位置

在inode中存放有一个或多个直接指针，指向属于该文件的一个数据块；为了支持更大的文件，inode中又引入了多级索引，即间接指针

10.4 目录结构

目录设计的目标：访问效率、同名文件、文件分组

单层目录

只有一个根目录“/”

结构简单，检索效率差，不允许重名，不能分组

双层目录

为每个用户建立自己的目录

不同用户可有相同命名的文件；每个用户的文件无法分组，同一用户文件无法重名

将不同用户进行隔离，虽然保证了用户文件的独立性，但也使得不同用户难以访问对方的文件

树型目录

把双层目录进行扩展

检索高效、可以分组、允许重名，禁止共享文件或目录

图型目录

无环图目录：有向边无环，不同目录内可以指向同一文件，实现文件共享

通用图（有环图）目录：允许图中有环，会出现目录内的文件又指回目录的情况

文件共享

硬链接：硬链接文件具有相同inode的节点号。硬链接文件是普通文件。

新建一个文件f1，内容为”this is file1”，再ln f1 f2，创建f1的硬链接f2。此时f2中的内容也为”this is f1”。将f1或f2删除（unlink()），不影响另一个文件。f1和f2的inode相同。

符号链接（软链接）：就是快捷方式。软连接文件和源文件是不同的文件，文件类型不同，inode号也不同。

新建一个文件f1，内容为”this is file1”，再ln -s f1 f3，创建f1的符号链接f3。此时f3中的内容也为”this is f1”。将f1删除，f3依然存在，但无法访问。f1和f3的inode不同。

目录实现

线性列表：采用文件名称和数据块指针的线性列表。查找文件需要线性搜索

哈希表：除了采用线性列表存储目录条目外，还采用了哈希数据结构，根据文件名称获得一个值，并返回列表内的一个文件指针

Tips

1. 一般可执行文件采用的文件结构是字符流
2. 打开文件操作不是一个文件系统中必须具有的操作
3. 在文件系统中，打开文件的主要操作是创建一个目录项（错）
4. 可以实现文件共享的目录结构是图型目录
5. 文件的逻辑结构一般可能由应用程序、操作系统、用户决定

---

第十一章 文件系统实现

11.1 文件系统

文件系统是操作系统中负责管理和存储文件信息的模块，提供了在存储设备上组织文件的方法和数据结构

在系统角度上

• 文件系统对存储设备的空间进行组织和分配，负责文件检索、读写等操作
• 目标：存取速度和存储空间效率

在用户角度上：

• 文件系统提供按名存取的文件访问机制、文件的组织管理
• 目标：方便的文件存取机制

文件系统的层次架构

从低到高：设备->I/O控制->基本文件系统->文件组织模块->逻辑文件系统->应用程序

基本文件系统：物理块读写、向设备驱动程序发送控制命令

文件组织模块：管理文件、逻辑块和物理块；把文件的逻辑地址转为物理地址；管理空闲空间；为文件分配物理块

逻辑文件系统：文件按名存取；文件目录组织管理；把文件名转换为文件ID、文件句柄；管理FCB

文件系统实现

磁盘文件系统

• 引导控制块：包含了系统引导操作系统的各种信息，只有安装操作系统的分区才有

• 分区控制块：包含分区信息，UFS称为超级块

• 目录和FCB

• 用户文件

内存文件系统

• 分区表：所有安装分区信息
• 目录缓冲结构：保存最近访问的目录信息
• 进程打开文件表
• 系统打开文件表

文件操作需要用到内存文件系统，目的是通过缓冲提高文件系统性能

虚拟文件系统

把多个文件系统整合成一个目录结构，为用户屏蔽各个文件系统的差异

网络文件系统

通过LAN（或WAN）访问远程文件系统

常用文件系统

Window：FAT, NTFS

Linux：Ext(Ext2, Ext3, Ext4) （Ext：基于扩展的文件系统）

MacOS：HFS

11.2 连续分配

物理块：存储设备的基本分配单位。系统以物理块为单位为文件分配存储空间。物理块的大小和页面大小相对应，从0开始编号

逻辑块：在文件空间中的块。大小和物理块一致，一个逻辑块存储在一个物理块中。块号从0开始

连续分配：每个文件在磁盘上占用一组连续的物理块。访问文件时，FCB只需给出<起始块号，长度>

地址映射：将逻辑地址（一维）映射到物理地址（二维）。

目录格式：<文件名，起始块号，长度>

优点：支持随机访问、存取速度快、适用一次性写入操作

缺点：浪费空间（小空间无法分配，外部碎片）、文件不能动态增长、不利于文件的插入和删除

11.3 链接分配

链接分配：文件信息存放在若干个不连续的物理块中，所有物理块通过指针链接成链表结构

目录格式：<文件名，起始块号，结束块号>

优点：提高磁盘的利用率（没有外部碎片）、可以动态扩充文件大小、便于文件的插入和删除

缺点：无法实现随机/直接访问、可靠性差

分类

1. 隐式链接：链表的指针分散存放在物理块中，每个物理块中的指针指向下一个物理块
   • 为了读入一个指针需要读入整个物理块
2. 显式链接：指针集中存放，把所有指针存放在一张链接表中，每个磁盘块都有一个条目，并可按块号索引
   • 例子：FAT（用于MS-DOS）
   • 链接表一般在文件系统装载时装入内存
   • 改善了随机访问时间：通过读入FAT信息，磁头能找到任何块的位置
   • 不适合大容量磁盘（因为此时链接表会非常大）
   • FAT表存放在磁盘每个卷的开头
   • 目录条目包含文件首块的块号，通过这个块号索引的表条目包含文件的下一块的块号
   • 未使用的块用0作为条目的值来表示。为文件分配新块时，只要找到第一个值为0的FAT条目，用新块的地址替换前面文件结束值，用文件结束值替代0

11.4 索引分配

索引分配：将所有指针放在一起，即索引块

索引块：索引块的第i个条目指向文件的第i个块

目录格式：<文件名，索引块>

访问文件时，先访问该文件的索引块，再从索引块中找到文件所占的物理块，FCB指向索引块

优点：支持随机访问（先访问索引块，再访问具体块）、离散存储，没有碎片

缺点：需要额外空间存放索引表、磁盘访问时间增加（物理块分布在磁盘各地）

如果文件很小，只占1到2块，采用链接分配只会浪费1到2个指针的空间，而如果采用索引分配，即使只有1到2个指针是非空的，也需要分配一个完整的索引块。所以对于小文件尽量不要使用索引分配。

但如果文件太大，一个索引块不能存放所有指针应该怎么办？

多级索引

大文件无法用单级索引实现，于是产生了多级索引

例如，物理块大小4KB，表项大小4B，每个索引块中可以存放4KB/4B=1K个表项，所以单级目录支持的最大文件是1K*4KB=4MB

n级索引文件大小：$(1K)^n\times 4KB$

联合策略

Unix中采用多种索引混合的策略

将索引块的前几个指针（如15）存在文件的inode中，这些指针的前12个指向直接块，即它们包含物理块的地址。接下来的3个指针指向间接块，第一个指向一级间接块，一级间接块为索引块；第二个指向二级间接块，最后一个指针为三级间接块。

11.5 空闲空间管理

空闲表

空闲区：连续的未分配物理块集合

空闲表：<首块块号, 长度>。每个表项对应一个空闲区。适用连续分配

空闲链表

将磁盘上所有空闲块链接在一个链表中

分配：从链表头依次摘下适当数目的空闲块

回收：空闲块加入链表尾部

位示图

利用二进制一位来表示一个块的使用情况，1代表盘块空闲，0代表盘块已分配

所有块都有一个二进制位与之对应

位示图需要额外的空间，存放在物理块中。分配时，将1改成0，回收时，将0改成1

成组链接

结合了空闲表和空闲链表

例如Unix系统中：

• 将空闲块分成若干组，每100块为一组
• 每组第一个空闲块中包括：空闲块总数、下一组空闲块首块的块号、本组其它空闲块的块号列表

一致性检查

将目录结构数据与磁盘空闲块结构相比较，纠正发现的不一致

空闲空间整理

把不连续的空闲块集合在一起

有利于给文件分配连续的物理块

Tips

1. 采用离散分配的磁盘空间分配方法有：链接分配、索引分配、基于扩展的文件系统（Ext）
2. 文件信息隐藏在若干个不连续物理块中的链接分配模式是隐式链接

---

第十二章 大容量存储器结构

12.1 磁盘结构和管理

磁盘结构

盘片、磁头、主轴；接口、磁盘控制器、缓冲区

盘片结构

磁道（从外面开始从“0”编号）、扇区（扇区大小为512B）、柱面

地址映射关系

块号 LBA

磁盘地址（CHS）格式：<柱面Cylinder，磁头/面Head，扇区Sector>

$$柱面号 = 块号 / (每个磁道扇区数 \times 扇面数)$$

$$磁头号 = (块号 / 每个磁道扇区数)\mod 扇面数$$

$$扇区号 = (块号\mod 每个磁道扇区数) + 1$$

磁盘访问时间

$$磁盘访问时间 = 寻道时间 + 旋转延迟时间 + 传输时间 + 系统开销时间$$

例：4KB块，7200 RPM磁盘， 5ms平均寻道时间，1Gb/sec传输率，0 .1ms 控制开销：

5ms + 0.5 * (7200 / 60)s + 4KB / 1Gb/s + 0.1ms = 9.30ms

磁盘管理

低级格式化（物理格式化）：将磁盘分成扇区，以便磁盘控制器读写

分区：将磁盘分成分区，主分区和扩展分区

高级格式化（逻辑格式化：创建文件系统

引导块

12.2 磁盘调度和RAID

磁盘调度

目标是减少磁盘访问时间，使寻道时间最小化

调度算法

先来先服务 FCFS

最短寻道时间优先 SSTF

• 饥饿

扫描算法/电梯算法 SCAN

• 到达另一端时，磁头改变移动方向
• 饥饿：当磁头当前位置前后有大量请求时，另外一段的请求会长期等待；C-SCAN也有这种问题，但由于其单向响应请求，理论上可以缓解一半

循环扫描算法 C-SCAN

从起始位置移动到一端，中间处理请求。然后从一端回到另一端，这个过程不处理请求

• 单向处理请求
  • 磁头从硬盘外道（0道）移动到内道的过程中处理请求
  • 内道移动到外道的过程中不处理请求
  • 具有更加均匀的等待时间

循环LOOK算法 C-LOOK

• C-SCAN的变形，磁头只移动到一个方向上最远请求为止，而不是继续移动到磁盘尽头

实际上，SSTF 较为普遍而且很有吸引力，SCAN和C-SCAN适合磁盘大负荷系统（数据库）

RAID结构

由很多价格较便宜的磁盘，组合成一个大容量的磁盘组，利用个别磁盘提供数据所产生的加成效果提升整个磁盘系统效能和可靠性

可靠性：引入冗余

性能：数据分散在多个磁盘，并行读写

RAID级别

RAID 0

• 条带化，没有冗余

• 数据分散在多个磁盘上

• 提高读写性能（并行）

• 不具有容错功能

RAID 1

• 磁盘镜像
• 提高可靠性

RAID 5

• 分散 + 校验
• 校验信息分散在各个磁盘

RAID 01 / RAID 10

RAID 0 重视性能，RAID 1 重视可靠性

• RAID 01 先做分散，再镜像，性能好
• RAID 10 先镜像，再分散，可靠性好

Tips

1. 不具有容错功能的RAID技术是RAID 0
2. 数据库服务器的磁盘一般采用的磁盘调度算法是SCAN
3. 具有更加均匀的等待时间的磁盘调度算法是C-SCAN
4. 可能存在饥饿现象的磁盘调度算法是SCAN、SSTF
5. 操作系统的引导程序一般存放在ROM中（错误，自举程序存放在ROM中，引导程序在磁盘中）
6. LOOK算法总比SCAN算法优 （错误）
7. ‎磁盘调度的目的是减少磁盘访问时间
8. LOOK算法总比SCAN算法优（错误）

---

第十三章 I/O系统

13.1 I/O基本概念

I/O系统的基本功能

隐藏物理设备的细节、与设备的无关性、提高处理机和I/O设备的利用率、对I/O设备进行控制、确保对设备的正确共享、错误处理

设备独立性

引入逻辑设备和物理设备

• 在应用程序中，使用逻辑设备名来请求使用某类设备，而系统在实际执行时使用物理设备名

内核I/O结构

从低到高：硬件 -> 设备驱动程序 -> I/O驱动结构 -> 内核I/O子系统 -> I/O应用接口 -> 应用程序

I/O硬件

端口

总线

控制器

I/O硬件控制

控制设备方法

• 直接I/O指令
• 内存映射I/O：设备地址和内存统一编址

I/O寄存器

状态寄存器

控制寄存器

数据输入寄存器

数据输出寄存器

I/O设备的类型

按使用特性分类：存储设备、I/O设备

按传输速率分类：低速设备（键盘、鼠标）、中速设备（打印机）、高速设备（磁带、磁盘）

低速设备一般被设置成独占设备

按信息交换的单位分类：块设备、字符设备

按设备的共享属性分类：独占设备、共享设备

独占设备应该采用静态分配策略

13.2 I/O控制方式

I/O的标准协议

1. 操作系统读取状态寄存器，等待设备进入可以接收命令的就绪状态（轮询）
2. 操作系统下发数据到数据寄存器
3. 操作系统将命令写入命令寄存器
4. 操作系统再次轮询设备，等待并判断设备是否执行完命令

轮询

又称“可编程I/O”

由用户程序自己控制的I/O控制方式

流程：由设备定时发出询问，询问设备是否忙，忙则进程进入忙等，不忙则进行I/O

特点：容易实现，但效率偏低；CPU会长期处于忙等状态。实际上基本不用。

中断

CPU硬件有一根中断请求线IRL

流程：

1. CPU执行完每条指令后，检测IRL
2. 如检测到信号，CPU保存当前状态，并跳转到中断处理程序
3. 执行中断处理程序
4. 执行完毕，清除中断，返回

中断（interrupt）和陷入（trap）

• 中断是CPU对I/O设备发来的中断信号的一种响应
• 陷入是指CPU内部事件所引起的中断（除以0等）

中断向量表

中断向量表存放每个设备的中断处理程序的入口地址

中断处理程序

1. 检测是否有未响应的中断信号
2. 保护被终端进程的CPU环境
3. 转入相应的设备处理程序
4. 中断处理
5. 恢复CPU的现场并退出中断

DMA

直接内存访问（Direct Memory Access）

绕过CPU，直接在I/O设备和内存之间传输数据。数据传输完成后，DMA控制器抛出一个中断来告诉操作系统自己已经完成数据传输

13.3 I/O内核子系统

内核提供与I/O相关的许多服务，如调度、缓冲、缓存、假脱机等，建立在硬件和设备驱动程序的基础设施之上，还保护自己免受错误进程和恶意用户的危害

I/O改善计算机效率的一个方法是进行I/O调度，另一个方法是使用主存或磁盘上的存储空间的技术，如缓冲、高速缓存、假脱机等

I/O调度

操作系统开发人员通过为每个设备维护一个请求队列来实现调度

缓冲（Buffering）

缓冲区是一个存储区域，可以由专门的硬件组成；更多的是利用内存

缓冲的用途：

1. 解决设备之间的速度差异
2. 协调传输数据大小不一样的设备
3. 支持应用程序I/O的复制语义

高速缓存（Cache）

假脱机（SPOOLing）

为了缓和CPU的高速性与I/O设备的低速性之间的矛盾而引入了脱机输入、脱机输出技术

原理：程序模拟脱机输入，把低速I/O设备上的数据传送到高速磁盘上；另一程序模拟脱机输出，把数据从磁盘传送到低速输出设备

输入进程模拟脱机输入时的外围控制机，将用户要求的数据从输入设备通过输入缓冲区再送入输入井，当CPU需要输入数据时，直接从输入井读入内存。输出同理。

特点：提高了I/O的速度；将独占设备改造为共享设备，实现了虚拟设备的功能

错误处理

Tips

1. 一个设备控制器可以连接多个设备
2. 需要CPU干预最少的I/O控制方式是SPOOLING
3. 使用SPOOLing系统的目的是为了提高I/O设备的使用效率
4. 操作系统使用的缓冲技术，多数通过使用内存来实现
5. 低速设备一般被设置成独占设备
6. 独占设备应该采用静态分配策略
7. 基于中断机制的I/O方式是一种同步的I/O方式（错误）
8. ‏使用内存映射I/O的设备是显卡
9. 由用户程序自己控制的I/O控制方式是轮询