

首页  思维导图  详情



408-操作系统

2026-03-31 09:57:28   0  举报





仅支持查看

AI智能生成

这个具体内容的笔记我是写在我的A4纸上了。408本质还是看你的理解深度，你的理解深度到了，后面的题就容易处理。全国统考408的环境下，就不搞那么多冷门题，我觉得可以吃透题目，可以把考研卷的题想考什么(把这题你觉得考的方向，且没考到的补充一些，写到题目旁，方便以后回来翻阅)，怎么得出答案也要理解原理(很多题，解答都很抽象，但是你可以结合讲解和图像真正理解了，就觉得，这才是脱离课本该有的样子，哈哈)。上面说的是做题方面的。评论区可以发"不负韶华，不负热望。我们终将上岸，加油！"

考研-408

考研-操作系统

王道-操作系统

模版推荐

作者其他创作

大纲/内容

操作系统基础

操作系统的概念（定义） 功能和目标

负责管理协调硬件，软件等计算机资源的工作

 为上层用户、应用程序提供简单易用的服务

是一种系统软件

图

子主题

功能和目标

资源的管理者

处理机管理

存储器管理

文件管理

设备管理

补充知识

执行一个程序前需要将该程序放到内存中，才能被CPU处理

图

子主题

向上层提供服务

给普通用户用的

命令接口

联机命令接口

小黑框

写一句回一句

脱机命令接口

批处理命令接口

写好多条语句放到文件，进行批量处理

图形接口

GUI用户图形界面

是调用了系统调用而实现的功能

给软件/程序员用的

程序接口

即系统调用

系统调用类似于函数调用，是应用程序请求操作系统服务的唯一方式

图

子主题

对硬件机器的扩展

扩充机器

虚拟机   

操作系统对硬件的扩展：将硬件合理的组合起来实现功能

操作系统的特征

并发

并发的实现需要具有中断功能的支持

共享

互斥共享方式(如对摄像头设备的共享使用)

同时共享方式(如对硬盘资源的共享使用)

虚拟

虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体(前者)是实际存在的，而逻辑上 对应物(后者)是用户感受到的

时分复用技术(如虚拟处理器技术)

核心

交替共享：资源按时间片轮流使用

资源状态

整个物理资源在每个时间点只被一个任务使用

空分复用技术(如虚拟存储技术)

核心

分割独占：资源被静态划分，部分独占

资源状态

整个物理资源在同一时间点被多个任务使用（的不同部分）

复用(和虚拟好像一样)

是将一种物理资源虚拟成多个逻辑上的副本，供多个用户或任务使用，从而提高资源利用率和系统效率。

异步

异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

重要考点

理解并发和并行的区别

并发

宏观是同时发生，微观是交替发生

单核CPU同一时刻只能执行一个程序，各个程序只能并发地执行

多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行

并行

两个或多个任务同时发生

并发和共享互为存在条件

子主题

没有并发和共享，就谈不上虚拟和异步，因此并发和共享是操作系统的两个最基本的特征

操作系统的发展和分类

手工操作阶段

缺：人机速度矛盾

子主题

批处理系统

批处理

事先编制作业控制

作业执行时，用户无法干预其运行

单道批处理系统（引入脱机输入输出技术）

优:缓解人机速度矛盾

缺:资源利用率依然很低

主要缺点:内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。 CPU有大量的时间是在空闲等待I/0完成。资源利用率依然很低。

图

子主题

多道批处理系统（操作系统开始出现）

把多个程序同时装入内存，并应许他们在CPU交替运行

当一道程序因为I/O程序中断，CPU便去运行另一道程序，即I/O设备可与cpu并行工作，在多批道处理系统

优点:  多道程序并发执行，资源利用率高和吞吐量，还没包括可靠性

缺点: 主要是缺乏人机交互功能，需要大量内存不是主要

图

子主题

分时操作系统

主要用于交互式作业而非批处理作业

优:提供人机交互功能

计算机以时间片为单位轮流为各个用户/作业服务

系统的响应时间好，

是一种多用户操作系统

缺:不能优先处理紧急任务

实时操作系统

硬实时系统

必须在绝对严格的规定时间内完成处理

软实时系统

能接受偶尔违反时间规定

主要优点:能够优先响应一些紧急任务，某些紧急任务不需时间片排队。

资源利用率不是主要追求目标

实时性

可靠性

安全可靠

网络操作系统

分布式操作系统

个人计算机操作系统

运行机制

两种指令

特权指令

如内存清零指令，这类指令权限高，不允许用户程序使用。

输入/输出指令属于特权指令

直接管理系统资源的指令(如设置时钟、启动/关闭硬件设备、切换进程、设置中断等

系统状态修改指令(如修改中断向量表、切换 CPU 的运行模式等)

系统控制指令(如停机指令，重启指令等)

非特权指令

如普通的运算指令，权限低，对其他用户没有影响。

区别用户态发生和用户态执行

用户态执行

普通的数据处理指令、流程控制指令、读操作指令都不会影响系统的安全和整体状态，可以在用户态执行。

用户态发生

系统调用是操作系统提供给用户程序的接口，系统调用发生在用户态，被调用程序在内核态下执行。

外部中断是用户态到内核态的“门”，也发生在用户态，在内核态完成中断处理过程。

缺页产生后，在用户态发生缺页中断，然后进入内核态执行缺页中断服务程序。

补充

“指令”就是处理器(CPU)能识别、执行的最基本命令

注:很多人习惯把 Linux、Windows、Macos 的“小黑框”中使用的命令也称为“指令”，其实这是“交互式命令接口”，注意与本节的“指令”区别开。本节中的“指令”指二进制机器指令

子主题

两种处理器状态

核心态

特权指令和非特权指令都可以执行。

内核态 --> 用户态  一条修改PSW(程序状态字) 的特权指令

用户态

此时CPU只能执行非特权指令。

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

两种程序

内核程序

是系统的管理者，即可以执行特权指令又可以执行非特权指令，运行在核心态。

应用程序

为了保证系统的安全运行，普通应用程序只能执行非特权指令，运行在用户态。

 图

子主题

操作系统内核在让出CPU之前，会用一条特权指令把 PSW 的标志位 设置为“用户态"

先硬件负责保存断点和程序状态字，并将CPU模型改为内核态

CPU检测到中断信号后，会立即变为“核心态”， 并停止运行当前的应用程序，转而运行处理中断信号的内核程序

操作系统内核

图

子主题

时钟管理

实现计时功能

中断处理

负责实现中断机制

原语

是一种特殊的程序，其执行具有原子性

处于操作系统最底层，是最接近硬件的部分

这种程序的运行具有原子性--其运行只能一气呵成，不可中断

运行时间较短、调用频繁

子主题

对系统资源进行管理的功能

进程管理

存储器管理

设备管理

中断与异常

中断的作用

让操作系统内核强行夺回CPU的控制权

使CPU从用户态变为内核态

中断的分类

内中断(也称异常、例外)

陷阱、陷入(trap)

是应用程序故意引发的

故障(fault)

如：缺页故障

终止(abort)

如：整数除0，非法使用特权指令

外中断(也称"中断”)

时钟中断

I/0中断请求

中断机制的基本实现原理

检查中断信号

内中断:CPU 在执行指令时会检查是否有异常发生

外中断:每个指令周期末尾，CPU都会检查是否有外中断信号请求需要处理

找到相应的中断处理程序

通过"中断向量表"实现

图

子主题

显然，中断处理程序一定是内核程序， 需要运行在“内核态"

适合用数组

系统调用

什么是系统调用？

操作系统对应用程序/程序员提供的接口

操作系统不同，为应用程序提供的系统调用接口也不同

是由用户进程发起的，请求操作系统的服务

系统调用与库函数的区别

图

子主题

有的库函数是对系统调用的进一步封装

有的库函数没有使用系统调用

小例子：为什么系统调用是必须的

Word 和 WPS 同时打印

两个进程并发运行，打印机设备交替地收到WPS 和 Word 两个进程发来的打印请求，结果两篇论文的内容混杂在一起了….

用户进程想要使用打印机这种共享资源，只能通过系统调用向操作系统内核发出请求。内核会对各个请求进行协调处理。

什么功能要用系统调用实现

设备管理

完成设备的请求/释放/启动等功能

文件管理

完成文件的读/写/创建/删除等功能

进程控制

完成进程的创建/撤销/阻塞/唤醒等功能

内存管理

完成内存的分配/回收等功能

系统调用的过程

传参

陷入指令=trap 指令=访管指令

该中断由陷入指令引发，因此转入相应的中断处理程序--即系统调用 的入口程序

由操作系统内核程序处理系统调用请求

根据寄存器中的参 数判断用户需要那 种系统调用服务

返回应用程序

系统调用和一般过程调用

系统调用

系统调用需要保存 PSW 和 PC 的值

系统调用的被调用过程是操作系统中的程序，是系统级程序，必须运行在内核态

一般过程调用(用普通函数调用)

一般过程调用只需保存 PC的值

一般过程调用的被调用程序与调用程序运行在同一个状态，可能是系统态，也可能是用户态

完成

系统调用的完成

一次请求交互过程的结束

依赖于操作系统的完成

如

创建新进程  像上面写的那些

操作系统的完成

一个具体任务的结束

是系统调用过程中的核心执行阶段

如

 页置换

当内存中的空闲页框不够时，操作系统会将某些页面调出，并将要访问的页面调入， 这个过程完全由操作系统完成，不涉及系统调用

进程调度

进程调度完全由操作系统完成，无法通过系统调用完成

保存寄存器的内容

执行系统调用服务例程

是连接用户程序请求和操作系统内核实际操作的桥梁和具体执行者。 它隐藏在软中断之后， 是操作系统实现其功能并保证安全、稳定和隔离的关键组成部分。

操作系统内核中真正执行系统调用所请求操作的具体函数

操作系统体系结构

图

子主题

大内核

将操作系统的主要功能模块都作为系统内核，运行在核心态

优点: 高性能

缺点: 内核代码庞大，结构混乱，难以维护

微内核

只把最基本的功能保留在内核

优点: 内核功能少，结构清晰，方便维护

可靠性

安全性

可扩展性

缺点: 需要频繁地在核心态和用户态之间切换，性能低

如下服务放在微内核中

进程间通信机制

低级I/O

低级进程管理和调度

这个属于调度

中断和陷入处理

 分层结构

子主题

结构清晰且便于调试

便于系统的调试和验证，若在调试某层时发现错误，则错误应在这层上，这是因为其低层都已调试好。

模块化

子主题

某个功能模块出问题,也是会导致系统奔溃的

外核

子主题

优缺点比较

子主题

操作系统引号(Boot)

图

子主题

初始化过程中创建中断向量表

虚拟机

子主题

VMM的代码量小于操作系统的代码量

第二类运行在用户态没有最高特权级,第一类有

可用软件实现,不可以硬件实现

进程管理

进程的控制

进程的基本概念，组成，特征

概念

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

线程是CPU 调度的基本单位,线程几乎不拥有系统资源

由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预

切换同进程内的线程，系统开销很小

切换进程，系统开销较大

图

子主题

进程和程序的根本区别是静态和动态特点

组成

PCB

图

子主题

一个进程实体(进程映像)由PCB、程序段、数据段组成。 进程是动态的，进程实体(进程映像)是静态的。 进程实体反应了进程在某一时刻的状态(如:x++后，x=2)

子主题

概念

操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中

中文是进程控制块

进程描述信息

进程标识符PID

用户标识符UID

进程控制和管理信息

CPU、磁盘、网络流量使用情况统计

进程当前状态:就绪态/阻塞态/运行态..

资源分配清单

正在使用哪些文件

正在使用哪些内存区域

正在使用哪些I/0设备

处理机相关信息

如PSW、PC等等各种寄存器的值(用于实现进程切换)

程序段

程序的代码（指令序列）

数据段

运行过程中产生的各种数据（如:程序中定义的变量）

补充

PCB 是给操作系统用的，程序段、数据段是给进程自己用的。

程序段、数据段、PCB三部分组成了进程实体(进程映像，

同时挂三个QQ号，会对应三个QQ进程，它们的PCB、数据段各不相同， 但程序段的内容都是相同的(都是运行着相同的QQ程序)

父进程与子进程

父进程与子进程可以并发执行

父进程可与子进程共享一部分资源，但不能共享虚拟地址空间， 在创建子进程时，会为子进程分配资源，如虚拟地址空间等

临界资源一次只能为一个进程所用

进程控制块(PCB)是进程存在的唯一标志，每个进程都有自己的 PCB

特征

动态性

进程的最基本特性

并发性

独立性

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

异步性

各进程以不可预知的速度向前推进，可能导致运行结果的不确定性

结构性

进程的状态与转换

状态

运行状态

CPU

其他所需资源

就绪状态

CPU

其他所需资源

阻塞状态

CPU

其他所需资源

创建状态

操作系统为新进程分配资源、创建PCB

终止状态

操作系统回收进程的资源、撤销PCB

图

子主题

父进程可能还需要用到子进程的某些 信息，因此子进程还不能完全杀掉

补充

单CPU情况下，同一时刻只会有一个进程处于运行态，多核CPU情况下，可能有多个进程处于运行态

进程状态间的转换

就绪态->运行态

进程被调度

运行态一>就绪态

时间片到，或CPU被其他高优先级的进程抢占

运行态->阻塞态

等待系统资源分配，或等待某事件发生(主动行为) 类似协作的进程

这个是由进程自身决定的

阻塞态->就绪态

资源分配到位，等待的事件发生(被动行为)

创建态->就绪态

系统完成创建进程相关的工作

运行态一>终止态

进程运行结束，或运行过程中遇到不可修复的错误

进程的组织方式

链接方式

图

子主题

按照进程状态将PCB分为多个队列

操作系统持有指向各个队列的指针

很多操作系统还会根据阻塞原因不同，再分为多个阻塞队列

索引方式

图

子主题

根据进程状态的不同，建立几张索引表

操作系统持有指向各个索引表的指针

进程控制

基本概念

什么是进程控制?

反正进程控制就是要实现进程状态转换

子主题

如何实现进程控制?

用“原语“实现

原语是一种特殊的程序，它的执行具有原子性也就是说，这段程序的运行必须一气呵成，不 可中断

可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性

原因

CPU执行了关中断指令之后，就不再例行检查中断信号， 直到执行开中断指令之后才会恢复检查。

图

子主题

进程控制相关的原语

进程的创建

创建原语 (操作系统创建一个进程时使用的原语)

申请空白PCB

为新进程分配所需资源

初始化PCB

将PCB插入就绪队列

创建态->就绪态

引进进程创建的事件

用户登录

分时系统中，用户登录成功，系统会建立为其建立一个新的进程

作业调度 (高级调度)

多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程

提供服务

用户向操作系统提出某些请求时，会新建一个进程处理该请求

应用请求

由用户进程主动请求创建一个子进程

进程的终止

撤销原语

从PCB集合中找到终止进程的PCB

若进程正在运行，立即剥夺CPU，将CPU分配给其他进程

终止其所有子进程

进程间的关系是树形结构

将该进程拥有的所有资源归还给父进程或操作系统

删除PCB

引起进程终止的事件

正常结束

进程自己请求终止(exit系统调用)

异常结束

整数除以0、非法使用特权指令然后被操作系统强行杀掉

外界干预

Ctrl+Alt+delete，用户选择杀掉进程

进程的阻塞

阻塞原语 (运行态->阻塞态)

找到要阻塞的进程对应的PCB

保护进程运行现场将PCB状态信息设置为“阻塞态"，暂时停止进程运行

将PCB插入相应事件的等待队列

引起进程阻塞的事件

需要等待系统分配某种资源

需要等待相互合作的其他进程完成工作

进程的唤醒

唤醒原语 (阻塞态->就绪态)

在事件等待队列中找到PCB

将PCB从等待队列移除，设置进程为就绪态

将PCB插入就绪队列，等待被调度

引起进程唤醒的事件

要等待的事件发生完成了

因何事阻塞，就应由何事唤醒

一次I/O操作的完成

进程的切换

切换原语 (运行态->就绪态) (就绪态->运行态)

将运行环境信息存入PCB

PCB移入相应队列

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

根据PCB恢复新进程所需的运行环境

引起进程切换的事件

当前进程时间片到

有更高优先级的进程到达

当前进程主动阻塞

当前进程终止

程序是如何运行的？

子主题

注意: 另一个进程在运行过程中也会使用各个寄存器

解决办法: 在进程切换时先在PCB中保存这个进程的运行环境

PC: 程序计数器，存放下一条指令的地址

IR:  指令寄存器存放当前止在执行的指令

子主题

学习技巧

进程控制会导致进程状态的转换。无论哪个进程控制原语，要做的无非三类事情

1.更新PCB中的信息

a.所有的进程控制原语一定都会修改进程状态标志

b.剥夺当前运行进程的CPU使用权必然需要保存其运行环境

c.某进程开始运行前必然要恢复期运行环境

2.将PCB插入合适的队列

3.分配/回收资源

进程通信

共享存储

设置一个共享内存区域，并映射到进程的虚拟地址空间

要互斥地访问共享空间(由通信进程自己负责实现互斥)

共享内存是进程通信方式中速度最快的

消息传递

Socket(套接字)

共享内存

管道

两种方式

基于数据结构(低级)

比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式

子主题

基于存储区的共享(高级)

子主题

操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。

消息传递

传递结构化的消息(消息头/消息体)

系统提供"发送/接收原语"

两种方式

直接通信方式

消息直接挂到接收进程的消息队列里

子主题

间接(信箱)通信方式

消息先发到中间体(信箱)

子主题

可以多个进程往同一个信箱send消息，也可以多个进程从同一个信箱中receive消息

管道通信

图

子主题

文件系统

设置一个特殊的共享文件(管道)，:其实就是一个内存缓冲区

一个管道只能实现半双工通信

生成者,消费者问题

实现双向同时通信要建立两个管道

各进程要互斥访问管道(由操作系统负责实现互斥)

管道写满时，写进程阻塞。管道读空时，读进程阻塞

管道中的数据一但被读出，就彻底消失。因此， 当多个进程读同一个管道时，可能会错乱。 对此通常有两种解决方案

①一个管道允许多个写进程，一个读进程

2. 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据

补充

信号的处理

信号的处理时机只会在进程从内核态转为用户态时

当进程从用户态转为内核态时，不会检查是否有待处理的信号

线程，多线程模型

概念

有的一个进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。

子主题

线程的属性

线程是处理机调度的单位

CPU调度的单位

多CPU计算机中，各个线程可占用不同的CPU

每个线程都有一个线程ID、线程控制块(TCB)

线程也有就绪、阻塞、运行三种基本状态

线程几乎不拥有系统资源

同一进程的不同线程间共享进程的资源

由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预

同一进程中的线程切换，不会引起进程切换

不同进程中的线程切换，会引起进程切换

切换同进程内的线程，系统开销很小

切换进程，系统开销较大

线程的优点

提高系统并发性

节约系统资源

便于进程通信

线程的引入减少时空开销

没有增强安全性

线程

线程的实现

用户级线程

从用户视角能看到的线程，由线程库实现

图

子主题

同一个进程内的多个线程不可以同时调度到多个处理机上执行

因为操作系统只能看到进程

用户级线程的切换是由应用程序自己控制的， 不需要操作系统的干预，操作系统感受不到用户级线程的存在。

系统调用、IO请求和异常处理这些涉及内核态的事件 都不会导致用户级线程切换，但会导致内核级线程切换。

线程同步是指多个线程之间协调执行顺序的机制， 如互斥锁、信号量、条件变量等。 当一个线程在等待同步条件时，应用程序可以选择切换到另一个就绪的用户级线程，以提高 CPU 的利用率。

内核线程

从操作系统视角看到的线程，由操作系统实现内核级线程才是处理机分配的单位

图

子主题

组合方式

上述两种方式的结合

调度

用户级线程

管理者和实现位置

应用程序或用户空间的线程库（如pthread库)

内核感知度

不可见。内核只知道进程的存在

调度单位  什么视角什么说法

以进程为单位。内核将CPU时间片分配给整个进程

操作系统内核完全不知道用户级线程的存在。它只看到进程，并把CPU时间分配给进程。 至于这个进程内部有多少个线程、如何轮转，则由进程内部的线程库自己管理

模式切换开销

无需模式切换。线程切换在用户空间完成，开销极小

阻塞的影响

整个进程阻塞。一个线程发起系统调用被阻塞，会导致整个进程的所有线程都被阻塞

多处理器利用

难以利用多核。内核一次只分配给一个进程一个CPU

内核级线程

管理者和实现位置

操作系统内核

内核感知度

可见。内核知道并管理每一个线程

调度单位

以线程为单位。内核直接调度可运行的线程

模式切换开销

需要模式切换。线程切换必须进入内核，开销较大

阻塞的影响

单个线程阻塞。一个线程被阻塞，内核可调度该进程内或其他进程的其他线程运行

多处理器利用

可以利用多核。内核可以将一个进程的多个线程调度到不同CPU上并行执行

多线程模型

一对一模型

图

子主题

一个用户级线程映射到一个内核级线程

优: 各个线程可分配到多核处理机并行执行，并发度高

缺: 线程管理都需要操作系统支持，开销大

多对一模型

图

子主题

多个用户级线程映射到一个内核级线程

优: 线程管理开销小效率高

缺: 一个线程阻塞(认为是内核线程记忆)会导致整个进程都被阻塞(并发度低)

多对多模型

图

子主题

n个用户级线程映射到m个内核级线程(n>=m)

集二者之所长

状态与转换

子主题

组织与控制

子主题

TCB(线程控制块)

线程切换时要保存/恢复,同时以下的也是线程独有的

程序计数器PC

其他寄存器

堆栈指针

多个线程共享所属进程所拥有的资源，进程P的线程可以访问进程P的全部地址空间和资源 (如已打开的文件、定时器、信号量机构等)以及它申请到的 I/O 设备等

同一个进程中的线程共享进程的虚拟地址空间，因此不需要更新页基址寄存器的值

页基址寄存器

存储当前进程的页表起始物理地址

作用：在虚拟地址→物理地址转换时，告诉MMU从哪里开始查找页表

线程表(thread table)

可将多个TCB组织成一张线程表

 栈

联想函数调用。凡是与函数执行过程密切相关的临时数据（局部变量、参数、返回地址），都在栈里。它的管理是自动的。

堆

联想malloc。凡是需要程序员手动申请和释放的内存空间，都在堆里。它的管理是手动的。

PCB

联想操作系统。凡是进程的管理信息（身份、状态、资源清单），都在PCB里

正文/数据段

联想编译后就确定的东西。程序代码、全局变量、静态变量这些在程序运行前就基本确定存在哪里的数据。

CPU调度于上下文切换

处理机调度

基本概念

按某种算法选择一个进程将处理机分配给它

图

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。

子主题

三个层次

图

子主题

高级调度(作业调度)

按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程

中级调度(内存调度)

按照某种规则，从挂起队列中选择合适的进程将其数据调回内存

低级调度(进程调度)

按照某种规则，从就绪队列中选择一个进程为其分配处理机

三层调度的联系，对比

高级调度

外存->内存 (面向作业)

发生频率:最低

中级调度

外存一>内存 (面向进程)

发生频率:中等

低级调度

内存->CPU

发生频率:最高

补充知识

为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为“挂起态

七状态模型:在五状态模型的基础上加入了"就绪挂起"和“阻塞挂起"两种状态

图

子主题

有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列， 甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

进程调度(低级调度)的时机切换与过程调度方式

时机

什么时候需要进程调度？

主动放弃

进程正常终止

运行过程中发生异常而终止

主动阻塞(如等待I/O)

被动放弃

分给进程的时间片用完

有更紧急的事情需要处理(如 I/O中断)

有更高优先级的进程进入就绪队列

什么时候不能进行进程调度？

在处理中断的过程中

进程在操作系统内核程序临界区中

原子操作过程中(原语)

补充

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

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

处于临界区的进程也可能因中断或抢占而导致调度。 此外，若进程在临界区内请求的是一个需要等待的资源， 比如打印机，则它主动放弃 CPU，让其他进程运行。

进程在操作系统内核程序临界区中不能进行调度与切换

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列(由各就绪进程的PCB组成)

 图

子主题

切换与过程

狭义的“调度"和“切换”的区别

狭义的“调度"

从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程, 也可能是另一个进程，后一种情况就需要进程切换)

“切换”

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程

广义的进程调度包含了选择一个进程和进程切换两个步骤

切换过程

对原来运行进程各种数据的保存

对新的进程各种数据的恢复

重要结论:进程调度、切换是有代价的， 并不是调度越频繁，并发度就越高

方式

非剥夺调度方式(非抢占式)

只能由当前运行的进程主动放弃CPU

剥夺调度方式(抢占式)

可由操作系统剥夺当前进程的CPU使用权

调度器，闲逛进程

调度器/调度程序

图

子主题

图

闲逛进程

概念

调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程(idle)

特性

优先级最低

可以是0地址指令，占一个完整的指令周期(指令周期末尾例行检查中断)

能耗低

调度算法的评价指标

CPU利用率

也有题目会让我们计算某设备的利用率

利用率 =忙碌的时间/总时间

图

子主题

系统吞吐量

系统吞吐量=总共完成了多少道作业/总共花了多少时间

子主题

周转时间

周转时间= 作业完成时间-作业提交时间

平均周转时间= 各作业周转时间之和/作业数

带权周转时间= 作业周转时间/作业实际运行的时间

平均带权周转时间= 各作业带权周转时间之和/作业数

等待时间

进程/作业 等待被服务的时间之和

平均等待时间即各个进程/作业等待时间的平均值

图

子主题

响应时间

从用户提交请求到首次产生响应所用的时间

设计调度算法时应考虑

公平性

资源利用率

平均周转时间

平均等待时间

平均响应时间

互斥性不是考虑指标

调度算法 (先来先服务) (最短作业优先) (最高响应比优先)

各种调度算法的学习思路

1. 算法思路

2.算法规则

3.这种调度算法是用于作业调度还是进程调度

4.抢占式？非抢占式？

5.优点和缺点

6.是否会导致饥饿

某进程/作业长期得不到服务

先来先服务 （FCFS）

图

子主题

1. 算法思路

主要从“公平”的角度考虑(类似于我们生活中排队买东西的例子)

2.算法规则

按照作业/进程到达的先后顺序进行服务

3. 用于作业/进程调度

用于作业调度时，考虑的是哪个作业先到达后备队列;用于进程调度时，考虑的是哪个进程先到达就绪队列

4.是否可抢占

非抢占式的算法

5.优缺点

优点: 公平、算法实现简单

缺点: 排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大， 对短作业来说用户体验不好。即FCFS算法对 长作业有利，对短作业不利(Eg:排队买奶茶..)

6.是否会导致饥饿

不会

最短作业优先 （SJF）

图

非抢占式

子主题

抢占式

子主题

 小细节

如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的

如果选择题中遇到“SJF 算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项

1. 算法思路

追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间

2.算法规则

最短的作业/进程优先得到服务(所谓“最短”，是指要求服务时间最短)

3. 用于作业/进程调度

即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先(SPF,Shortest Process First)算法”

4.是否可抢占

SJF和SPF是非抢占式的算法。但是也有抢占式的版本--最短剩余时间优先算法(SRTN,Shortest Remaining Time Next)

5.优缺点

优点:“最短的”平均等待时间、平均周转时间

缺点: 不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

6.是否会导致饥饿

会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死”

最高响应比优先 （HRRN）

图

子主题

1. 算法思路

要综合考虑作业/进程的等待时间和要求服务的时间

2.算法规则

在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务

响应比=(等待时间+要求服务时间)/要求服务时间

响应比 ≥1

3. 用于作业/进程调度

即可用于作业调度，也可用于进程调度

4.是否可抢占

非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比

5.优缺点

综合考虑了等待时间和运行时间(要求服务时间) 等待时间相同时，要求服务时间短的优先(SIF的优点) 要求服务时间相同时，等待时间长的优先(FCFS的优点) 对于长作业来说，随着等待时间越来越久，其响应比也会 越来越大，从而避免了长作业饥饿的问题

6.是否会导致饥饿

不会

回顾

子主题

调度算法 (时间片轮转) (优先级调度) (多级反馈队列)

学习思路（同上）

时间片轮转调度算法

图

子主题

1. 算法思路

公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

2.算法规则

按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

3. 用于作业/进程调度

用于进程调度(只有作业放入内存建立了相应的进程后，才能被分配处理机时间片)

4.是否可抢占

若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到

5.优缺点

优点: 公平;响应快，适用于分时操作系统:

时间片轮转的主要目的是，使得多个交互的用户能够得到及时响应，使得每个用户以为“独占"计算机的使用

缺点: 由于高频率的进程切换，因此有一定开销;不区分任务的紧急程度。

6.是否会导致饥饿

不会

时间片太大或太小分别有什么影响?

优先级调度算法

图

非抢占式

子主题

抢占式

子主题

补充

子主题

1. 算法思路

随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序

2.算法规则

调度时选择优先级最高的作业/进程

3. 用于作业/进程调度

既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中

4.是否可抢占

抢占式、非抢占式都有。做题时的区别在于:非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占

5.优缺点

优点: 用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。

缺点:若源源不断地有高优先级进程到来，则可能导致饥饿

6.是否会导致饥饿

会

多级反馈队列调度算法

图

子主题

1. 算法思路

对其他调度算法的折中权衡

2.算法规则

1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

2.新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片， 若用完时间片进程还未结束，则进程进入下一级队列队尾， 如果此时已经是在最下级的队列，则重新放回该队列队尾

3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片

3. 用于作业/进程调度

用于进程调度

4.是否可抢占

抢占式的算法。在k级队列的进程运行过程中，若更上级的队列(1~k-1级)中进入了一个新进程， 则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。

5.优缺点

对各类型进程相对公平(FCFS的优点);每个新到达的进程都可以很快就得到响应(RR的优点):短进程只用较少的时间就可完成(SPF的优点);不必实现估计进程的运行时间(避免用户作假)可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/0密集型进程(拓展:可以将因I/0而阻塞的进程重新放回原队列，这样O型进程就可以保持较高优先级)

6.是否会导致饥饿

会

回顾

子主题

调度算法 (多级队列调度)

子主题

补充

CPU 繁忙型作业

该类作业需要占用很长的 CPU 时间，而很少请求 I/O 操作

FCFS

I/O 繁忙型作业

指作业执行时需频繁请求 IO 操作，即可能频繁放弃 CPU，所以占用 CPU 的时间不会太长

SIF 比较适合

优先级调度算法分静态和动态两种。静态优先级在进程创建时确定，之后不再改变。

什么叫抢占

时间片轮转就是绝对抢占

同步与互斥

进程同步，进程互斥

进程同步

异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

并发性带来了异步性，有时需要通过进程同步解决这种异步问题。 有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序。

进程互斥

对临界资源的访问，需要互斥的进行。即同一时间段内只能允许一个进程访问该资源

四个部分

图

子主题

进入区

检查是否可进入临界区，若可进入，需要"上锁"

临界区

访问临界资源的那段代码

退出区

负责"解锁"

剩余区

其余代码部分

需要遵循的原则

空闲让进

临界区空闲时，应允许一个进程访问

忙则等待

临界区正在被访问时，其他试图访问的进程需要等待

有限等待

要在有限时间内进入临界区，保证不会饥饿

让权等待

进不了临界区的进程，要释放处理机，防止忙等

进程互斥的软件实现方法

如果没有注意进程互斥

子主题

需要进行互斥的操作是对临界资源的访问，也就是说，不同线程对同一个进程内部的共享变量的访问才有可能需要进行互斥，不同进程的线程、代码段或变量不存在互斥访问的问题，同一个线程内部的局部变量也不存在互斥访问的问题。

单标志法

图

子主题

在进入区只做“检查"，     不“上锁”

在退出区把临界区的使用权转交给另一个进程(相当于在退出区既给另一进程“解锁"，又给自己“上锁”)

主要问题: 不遵循“空闲让进"原则

到小札他没进入临界区就卡在哪老扎就没得用

turn 表示谦让

双标志先检查

图

子主题

在进入区先“检查" 对方的意愿    对方无后“上锁"，退出区“解锁”

主要问题: 不遵循“忙则等待"原则

两个过了检测都可以访问了

双标志后检查

图

子主题

在进入区先“加锁“后“检查”，退出区“解锁”

主要问题:不遵循“空闲让进、有限等待"原则，可能导致“饥饿”

Peterson算法

图

子主题

在进入区"主动争取一主动谦让-检查对方是否想进、已方是否谦让"

主要问题: 不遵循“让权等待"原则，会发生“忙等"

进程互斥的硬件实现方法

中断屏蔽方法

图

子主题

使用“开/关中断"指令实现

优点:简单高效

缺点: 只适用于单处理机;  只适用于操作系统内核进程 , 不适用于用户进程 (因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)

TestAndSet(TS指令/TSL指令)

 图

子主题

old 记录是否已被上锁;再将 lock 设为 true;检查临界区是否已被上锁(若已上锁，则循环重复前几步)

优点: 实现简单;适用于多处理机环境;

缺点: 不满足“让权等待"

一直锁着得别的用完

TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作

Swap指令(XCHG指令)

图

子主题

互斥锁

子主题

重在理解

需忙等，进程时间片用完才下处理机，违反“让权等待

优点: 等待期间不用切换进程上下文，多处理器系统中， 若上锁的时间短，则等待代价很低常用于多处理器系统， 一个核忙等，其他核照常工作，并快速释放临界区

缺点: 不太适用于单处理机系统，忙等的过程中不可能解锁

信号量机制

相关概念

信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作， 从而很方便的实现了进程互斥, 进程同步。

信号量

信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)， 可以用一个信号量来表示系统中某种资源的数量，比如:系统中只有一台打印机，就可以设置一个初值为1的信号量。

一对原语

一对原语:wait(S) 原语和 signal(s) 原语，可以把原语理解为我们自己写的函数， 函数名分别为 wait和 signal，括号里的信号量S其实就是函数调用时传入的一个参数。

wait(s)、signal(s)原语常简称为 P、V操作(来自荷兰语 proberen 和 verhogen)。因此，做题的时候常把 wait(S)、signal(S)两个操作分别写为 P(S)、V(S)

原语(Primitive/Atomic Action)，顾名思义，就是原子性的、不可分割的操作。其严格定义为:由若干机器指令构成的完成某种特定功能的一段程序，其执行必须是连续的，在执行过程中不允许被中断。

整型信号量

图

子主题

用一个整数型变量作为信号量，数值表示某种资源数

整型信号量与普通整型变量的区别:对信号量只能执行 初始化、P、V 三种操作

整型信号量存在的问题:不满足让权等待原则

记录型信号量

图

S.value 表示某种资源数，S.L指向等待该资源的队列

P 操作中，一定是先 S.value--，之后可能需要执行 block 原语

V 操作中，一定是先 S.value++，之后可能需要执行 wakeup 原语

处理的是里面的等待队列

要唤醒 说明有负的  加一也就 小于等于0

注意: 要能够自己推断在什么条件下需要执行 block 或 wakeup

可以用记录型信号量实现系统资源的“申请"和“释放'

可以用记录型信号量实现进程互斥、进程同步

不存在"让权等待"

注意

注:若考试中出现 P(S)、V(S)的操作，除非特别说明，否则默认S为记录型信号量。

实现进程互斥

图

子主题

分析问题，确定临界区

设置互斥信号量，初值为1

临界区之前对信号量执行 P 操作

临界区之后时信号量执行 V 操作

必须成对出现

这里的临界区是指访问临界资源A的那段代码(临界区的定义)。 那么5个并发进程共有5个操作共享变量 A 的代码段。就是5个临界区

实现进程同步

图

子主题

分析问题，找出哪里需要实现“一前一后"的同步关系

设置同步信号量，初始值为0

“前操作"之后执行 V 操作

在“后操作"之前执行 P 操作

前V后P

实现进程的前驱关系

图

子主题

分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题

为每一对前驱关系设置同步信号量，初值为0

在每个“前操作"之后执行 V操作

在每个“后操作"之前执行 P操作

生产者-消费者问题

同步

前V后P

互斥

前P后V (绑定在以一起的)

以什么作为中转

缓存区

问题描述

子主题

如何处理

子主题

例题

在9个生产者、6 个消费者共享容量为8的缓冲区的生产者-消费者问题中， 互斥使用缓冲区的信号量初始值为 "1"

多生产者-多消费者问题

以什么作为中转

盘子(plate)

问题描述

子主题

如何实现

一个盘子

子主题

二个盘子

子主题

理解为什么要中转点

子主题

吸烟者问题

以什么作为中转

供应者

问题描述

子主题

问题分析

子主题

如何实现

子主题

读者写者问题

没有涉及什么中转，就是关于互斥问题

问题描述

子主题

如何实现

子主题

回顾

子主题

哲学家进餐问题

问题描述

子主题

问题分析

子主题

如何实现

子主题

管程

图

子主题

为什么要引入管程

解决信号量机制编程麻烦、易出错的问题

让程序员写程序时不需要再关注复杂的PV操作

组成

共享数据结构

对数据结构初始化的语句

一组用来访问数据结构的过程(函数)

基本特征

各外部进程/线程 只能通过管程提供的特定“入口"才能访问 共享数据

每次仅允许 一个进程 在管程内执行某个内部过程

补充

各进程必须互斥访问管程的特性是由编译器实现的

可在管程中设置条件变量及等待/唤醒操作以解决同步问题

管程就是一个自带“自动锁”和“等待室”的类。它保证了同一时间只有一个客户（线程）能进入办理业务（执行方法），如果业务暂时办不了（条件不满足），客户就去指定的等待室（条件变量）休息并把锁交给下一个人，等条件满足时再由工作人员（signal）叫回来。

管程的 signal 操作与信号量机制中的 V操作不同,信号量机制中的V操作一定会改变信号量的值 S=S+1。 而管程中的 signal 操作是针对某个条件变量的，若不存在因该条件而阻塞的进程,则 signal 不会产生任何影响。

管程是由一组数据及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。管程不仅能实现进程间的互斥，还能实现进程间的同步，

“条件变量”是管程内部说明和使用的一种特殊变量，其作用类似于信号量机制中的“信号量”，都用于实现进程同步。 需要注意的是，在同一时刻，管程中只能有一个进程在执行。若进程 A 执行了 x.wait()操作，则该进程会阻塞， 并挂到条件变量x对应的阻塞队列上。这样，管程的使用权被释放，就可以有另一个进程进入管程。 若进程B执行了x.signal()操作，则会唤醒x对应的阻塞队列的队首进程。只有一个进程要离开管程时才能调用 signal()操作。

死锁

死锁的概念

什么是死锁

各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进

死锁，饥饿，死循环的区别

死锁: 至少是两个进程一起死锁，死锁进程处于阻塞态

饥饿: 可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪

死循环: 可能只有一个进程发生死循环，死循环的进程可上处理机 while()

死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的

死锁产生的必要条件

互斥条件

对必须互斥使用的资源的争抢才会导致死锁

不剥夺条件

进程保持的资源只能主动释放，不可强行剥夺

请求和保持条件

保持着某些资源不放的同时，请求别的资源

既要又要

循环等待条件

存在一种进程资源的循环等待链

有顺序

等待形成了一个环

循环等待未必死锁，死锁一定有循环等待

什么时候会发生死锁

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

死锁的处理策略

预防死锁

破坏死锁产生的四个必要条件

避免死锁

避免系统进入不安全状态(银行家算法)

死锁的检测和解除

允许死锁发生，系统负责检测出死锁并解除

死锁定理是用来检测死锁的方法

预防死锁

破坏互斥条件

将临界资源改造为可共享使用的资源(如SPOOLing技术)

缺点: 可行性不高，很多时候无法破坏互斥条件

破坏不剥夺条件

方案一，申请的资源得不到满足时，立即释放拥有的所有资源

方案二，申请的资源被其他进程占用时，由操作系统协助剥夺(考虑优先级)

缺点: 实现复杂;剥夺资源可能导致部分工作失效;反复申请和释放导致系统开销大;可能导致饥饿

破坏请求和保持条件

运行前分配好所有需要的资源，之后一直保持

预先分配好

缺点:资源利用率低;可能导致饥饿

破坏循环等待条件

给资源编号，必须按编号从小到大的顺序申请资源

缺点: 不方便增加新设备;会导致资源浪费;用户编程麻烦

避免死锁

什么是安全序列

子主题

什么是系统的不安全状态，与死锁有何联系

如果系统处于安全状态，就一定不会发生死锁。 如果系统进入不安全状态，未必就是发生了死锁，但发生死锁时一定是在不安全状态)

多维向量表示

不发生死锁

子主题

发生死锁

子主题

如何避免系统进入不安全状态-银行家算法

子主题

补充

按照银行家算法，只要保证系统中进程申请的最大资源数小于或等于 m，就一定存在一个安全序列。考虑最极端的情况，假如有n-1个进程都申请了1个资源，剩下一个进程申请了m个资源，则各进程的最大需求量之和为m+n-1，此时能保证一定不会发生死锁。

此外，银行家算法虽然会通过检测是否存在安全序列来判断申请资源的请求是否合法，但安全序列并不是唯一的，也不是固定的，它只是一种可能的分配方案，而不是种必须遵循的规则，银行家算法更没有给出固定的申请资源的顺序

死锁的检测和解除

如何检测

数据结构：资源分配图

图

子主题

两种结点

进程结点

资源结点

两种边

进程结点-->资源结点(请求边)

资源节点-->进程结点(分配边)

死锁检测算法

依次消除与不阻塞进程相连的边，直到无边可消，就没有死锁(相当于找到一个安全序列)

注: 所谓不阻塞进程是指其申请的资源数还足够的进程

死锁定理: 若资源分配图是不可完全简化的，说明发生了死锁

图

子主题

不能消除所有的边说明发生了死锁

 例题

子主题

出现了环路，只是满足了循环等待的必要条件，而满足必要条件不一定会导致死锁，选项1对

没有环路，破坏了循环等待条件，一定不会发生死锁，选项Ⅱ错

每种资源只有一个，又出现了环路，这是死锁的充分条件，可以确定是否有死锁，选项3 错

使每个进程至少有一条请求边，若资源足够，则不会发生死锁，但若资源不充足，则有发生死锁的可能，选项4对

死锁定理是用来检测死锁的方法

如何解除

图

子主题

资源剥夺法

撤销进程法(终止进程法)

进程回退法

例题

子主题

子主题

内存管理

内存管理基础

内存管理概念

逻辑地址与物理地址空间

地址变换

内存共享

内存保护

内存分配与回收

连续分配管理方式

页式管理

段式管理

段页式管理

虚拟内存管理

虚拟内存基本概念

请求页式管理

页框分配与回收

页置换算法

内存映射文件(Memory-MappedFiles)

虚拟存储器性能的影响因素及改进方式

内存管理基础

内存的基本概念

内存的基本知识

什么是内存，有何作用

图

子主题

存储单元、内存地址的概念和联系

按字节编址 vs 按字编址

内存的作用

内存可存放数据。程序执行前需要先放到内存中才能被CPU处理 --缓和CPU与硬盘之间的速度矛盾(学内存的本质)

进程运行的基本原理

指令的工作原理

操作码+若干参数(可能包含地址参数)

逻辑地址(相对地址)vs物理地址(绝对地址)

从写程序到程序运行

编辑源代码文件

编辑

由源代码文件生成目标模块(高级语言“翻译"为机器语言)

链接

由目标模块生成装入模块，链接后形成完整的逻辑地址

由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起， 形成一个完整的装入模块

装入

将装入模块装入内存，装入后形成物理地址

图

子主题

三种链接方式

静态链接

装入前链接成一个完整装入模块,之后不会拆开

装入时动态链接

运行前边装入边链接

运行时动态链接

运行时需要目标模块(可能各个目标模块已经放到内存了)才装入并链接

 图

子主题

三种装入方式

绝对装入

编译时产生绝对地址

图

子主题

静态重定位: 又称可重定位装入。

静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间， 如果没有足够的内存，就不能装入该作业。 作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。

动态运行时装入

装入时将逻辑地址转换为物理地址

图

子主题

动态重定位: 又称动态运行时装入

编译、链接后的装入模块的地址都是从0开始的。 装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址(可能是内部指令的指向)， 而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。 这种方式需要一个重定位寄存器的支持。

可重定位装入

运行时将逻辑地址转换为物理地址，需设置重定位寄存器

图

子主题

采用动态重定位时允许程序在内存中发生移动。

内存管理的概念 (操作系统作为系统资源的管理者， 当然也需要对内存进行管理，要管些什么呢?)

子主题

子主题

内存空间的分配与回收

问题

多个进程同时运行，每个都需要内存。 如何分配物理内存给它们？如何回收进程结束后占用的内存？

管理策略

操作系统需要跟踪哪些内存是空闲的，哪些已被占用。 早期有连续分配（如可变分区），现代普遍采用非连续分配（分页、分段）， 极大地提高了内存利用率和灵活性。

早期有连续分配

现代普遍采用非连续分配（分页、分段）

内存空间的扩充(实现虚拟性)

问题

物理内存大小有限，如何运行一个比物理内存还大的进程？如何让用户感觉内存“无限大”？ 创造一个每个进程都独占整个内存的“假象”（虚拟地址空间）。

覆盖技术

交换技术

虚拟存储技术

地址转换

操作系统负责实现逻辑地址到物理地址的转换

三种方式

绝对装入：编译器负责地址转换(单道程序阶段，无操作系统)

可重定位装入：装入程序负责地址转换(早期多道批处理阶段)

动态运行时装入：运行时才进行地址转换(现代操作系统)

存储保护

问题

如何确保一个进程不会越界访问或修改另一个进程的内存空间？ 如何防止用户进程破坏操作系统的内存？

保证各进程在自己的内存空间运行，不会越界访问

两种方式

设置上下限寄存器

子主题

利用重定位寄存器，界地址寄存器进行判断

子主题

方法二:采用重定位寄存器(又称基址寄存器)和界地址寄存器(又称限长寄存器)进行越界检查。 重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

进程的内存映射

不同于存放在硬盘上的可执行程序文件，当一个程序调入内存运行时，就构成了进程的内存映像。

内存映射就是将进程虚拟地址空间中的页（Page）映射到物理内存的页帧（Page Frame）或者磁盘上的文件/交换空间的过程

子主题

进程的地址空间

操作系统为每个进程创建一个独立的、统一的、连续的虚拟地址空间

空间通常被划分为几个标准段

代码段

存放程序的二进制机器指令。只读，可共享

数据段

存放已初始化的全局变量和静态变量

BSS段

存放未初始化的全局变量和静态变量

堆(Heap)

动态内存分配区。当进程调用 malloc()或 new时，从这里分配内存， 需要程序员手动释放或由垃圾回收器管理。向高地址增长。

栈(Stack)

存放局部变量、函数参数、返回地址等。由编译器自动管理。向低地址增长

程序访问内存时使用的是虚拟地址，操作系统负责将其转换为物理地址

内存空间的扩充(实现虚拟性)

覆盖与交换

覆盖技术

概念

将程序分为多个段(多个模块)常用的段常驻内存，不常用的段在需要时调入内存。

图

子主题

一个固定区

存放最活跃的程序段

固定区中的程序段在运行过程中不会调入调出

若干覆盖区

不可能同时被访问的程序段可共享一个覆盖区

覆盖区中的程序段在运行过程中会根据需要调入调出

必须由程序员声明覆盖结构，操作系统完成自动覆盖

缺点: 对用户不透明，增加了用户编程负担(程序员必须看见、理解并亲自管理这一切。 系统并没有向程序员隐藏这个艰难的细节)

不透明

用户看得见

透明

用户看不见

交换技术

内存紧张时，换出某些进程以腾出内存空间，再换入某些进程

磁盘分为文件区和对换区，换出的进程放在对换区

覆盖与交换的区别

覆盖是在同一个程序或进程中的

交换是在不同进程(或作业)之间的

连续分配管理方式

连续分配方式是指为一个用户程序分配一个连续的内存空间，譬如某用户需要 100MB 的内 存空间，连续分配方式就在内存空间中为用户分配一块连续的 100MB 空间。 连续分配方式主要包括单一连续分配、固定分区分配和动态分区分配。

补充

连续分配

指为用户进程分配的必须是一个连续的内存空间

先预先给出一片连续的内存空间给它

单一连续分配

图

子主题

只支持单道程序，内存分为系统区(存放操作系统相关的数据)和用户区，用户程序放在用户区

无外部碎片，有内部碎片

固定分区分配

图

子主题

支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业

无外部碎片，有内部碎片

两种分区方式

分区大小相等

分区大小不等

也是预先分好的

操作系统需要建立一个数据结构--分区说明表

用数据结构的数组(或链表)即可表示这个表

这种方式存在两个问题:①程序太大而放不进任何一个分区: ②)当程序小于固定分区大小时也要占用一个完整的内存分区，这样分区内部就存在空间浪费，这种现象称为内部碎片。 固定分区方式无外部碎片，但不能实现多进程共享一个主存区，所以内存的利用率低。

动态分区分配

 图

子主题

支持多道程序，在进程装入内存时，根据进程的大小动态地建立分区

无内部碎片，有外部碎片

内部碎片就是非空闲的内部有没用的

外部碎片就是空闲的

外部碎片可用"紧凑"技术来解决

两种常见的数据结构

空闲分区表

每个空闲分区对应一个表项。 表项中包含分区号、分区大小、分区起始地址等信息

空闲分区链

每个分区的起始部分和末尾部分分别设置前向指针和后向指针。 起始部分处还可记录分区大小等信息

回收内存分区时，可能遇到四种情况

回收区之后有相邻的空闲分区

回收区之前有相邻的空闲分区

回收区前、后都有相邻的空闲分区

回收区前、后都没有相邻的空闲分区

动态分区分配算法

将作业装入主存时，需要按照一定的分配算法从空闲分区链(表)中选出一个分区，以分配给该作业。 按分区检索方式，可分为顺序分配算法和索引分配算法。 顺序分配算法是指依次搜索空闲分区链上的空闲分区，以寻找一个大小满足要求的分区，顺序分配算法有以下四种。

基于顺序搜索的分配算法

首次适应算法（First Fit）

算法思想

每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

如何实现

空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)， 找到大小能满足要求的第一个空闲分区。

图

子主题

综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序

最佳适应算法（Best Fit）

算法思想

可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区

如何实现

空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区 表)，找到大小能满足要求的第一个空闲分区。

图

子主题

缺点

每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。 因此这种方法会产生很多的外部碎片。

最佳适应算法总是匹配与当前大小要求最接近的空闲分区，但是大多数情况下空闲分区的大小不可能完全和当前要求的大小相等， 几乎每次分配内存都会产生很小的难以利用的内存块，所以最佳适应算法最容易产生最多的内存碎片。(不是内部碎片)

最坏适应算法（Worst Fit） 又称最大适应算法:(Largest Fit)

算法思想

可以在每次分配时优先使用最大的连续空闲区

如何实现

空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区 表)，找到大小能满足要求的第一个空闲分区。

图

子主题

缺点

每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用， 但是这种方式会导致较大的连续空闲区被迅速用完。 如果之后有“大进程”到达，就没有内存分区可用了

邻近适应算法（Next Fit）

算法思想

首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现

空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

图

子主题

会使高地址的大分区也被用完

区别

子主题

基于索引搜索的分配算法

当系统很大时，空闲分区链可能很长，此时采用顺序分配算法可能很慢。 因此，在大、中型系统中往往采用索引分配算法。 索引分配算法的思想是，根据其大小对空闲分区分类，对于每类(大小相同)空闲分区，单独设立一个空闲分区链，并设置一张索引表来管理这些空闲分区链。 当为进程分配空间时，在索引表中查找所需空间大小对应的表项，并从中得到对应的空闲分区链的头指针，从而获得一个空闲分区。索引分配算法有以下三种。

补充

伙伴算法

将空闲内存块不断对半分割，直到得到能满足请求大小的最小块； 回收时，将相邻的“伙伴”块合并成更大的块

1)快速适应算法

空闲分区的分类根据进程常用的空间大小进行划分。分配过程分为两步: 1)①首先根据进程的长度，在索引表中找到能容纳它的最小空闲分区链表; ②然后从链表中取下第一块进行分配。 优点是查找效率高、不会产生内存碎片: 缺点是回收分区时需要有效地合并分区，算法比较复杂，系统开销较大。

2)伙伴系统

规定所有分区的大小均为2的k次幂(k为正整数)。当需要为进程分配大小为n的分区时(2^(i-1)< n<2^i )，在大小为2^i 的空闲分区链中查找。 若找到，则将该空闲分区分配给进程。 否则，表示大小为2^i 的空闲分区已耗尽，需要在大小为2^(i+1)的空闲分区链中继续查找。 若存在大小为2^(i+1)的空闲分区，则将其等分为两个分区，这两个分区称为一对伙伴，其中一个用于分配，而将另一个加入大小为2^i  的空闲分区链。若不存在，则继续查找，直至找到为止。回收时，需要要将相邻的空闲伙伴分区合并成更大的分区。

3)哈希算法

根据空闲分区链表的分布规律，建立哈希函数，构建一张以空闲分区大小为关键字的哈希表， 每个表项记录一个对应空闲分区链的头指针。 分配时，根据所需分区大小，通过哈希函数计算得到哈希表中的位置，从中得到相应的空闲分区链表。

图

子主题

非连续分配管理方式

段和页的区别

页均分

原因：固定分区会产生内部碎片,动态分区会产生外部碎片,这两种技术对内存的利用率都比较低。 我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想: 处理办法： 1. 将内存空间分为若干固定大小(如4KB)的分区，称为页框、页帧或物理块。 2. 进程的逻辑地址空间也分为与块大小相等的若干区域，称为页或页面。 3. 操作系统以页框为单位为各个进程分配内存空间。 从形式上看： 分页的方法像是分区相等的固定分区技术，分页管理不产生外部碎片。 但它又有本质的不同点: 块的大小相对分区要小很多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行。 这样，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，所以尽管会产生内部碎片， 但这种碎片相对进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片(也称页内碎片)。

段不均分在内存中不相邻

原因： 分页管理方式是从计算机的角度考虑设计的，目的是提高内存的利用率,提升计算机的性能。 分页通过硬件机制实现，对用户完全透明。 提出：分段管理方式的提出则考虑了用户和程序员， 以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。

段页

原因： 1. 分页存储管理能有效地提高内存利用率， 2. 而分段存储管理能反映程序的逻辑结构并有利于段的共享和保护。 将这两种存储管理方法结合起来，便形成了段页式存储管理方式。

基本分页存储管理的概念

图

子主题

基本分页存储管理的思想:把进程分页，各个页面可离散地放到各个的内存块中

易混概念

图

子主题

“页框、页帧、内存块、物理块、物理页"(内存这边的表示)VS"页、页面"(进程这边的表示)

“页框号、页帧号、内存块号、物理块号、物理页号"VS"页号、页面号"

页表

页表记录了页面和实际存放的内存块之间的映射关系

一个进程对应一张页表， 进程的每一页对应一个页表项， 每个页表项由"页号"和“块号"组成

本质是页面里的页和内存里的内存块大小是一样的, 页表只是记录对应关系的表而已

每个页表项的大小是相同的，页号是“隐含“的

内存块的数量推出 ->页表项的最大数字 -> 页表项的可能大小

i号页表项存放地址 =页表始址 +i*页表项大小

图

子主题

逻辑地址结构--可拆分为 【页号P，页内偏移量W】

页号=逻辑地址/页面大小; 页内偏移量=逻辑地址%页面大小(这也看出页内偏移量与页表无关)

如果页面大小刚好是2的整数次幂呢?

逻辑地址的拆分更加迅速

物理地址的计算更加迅速

图

子主题

子主题

如何实现地址转换

1.计算出逻辑地址对应的【页号，页内偏移量】

2.找到对应页面在内存中的存放位置(查页表)

3.物理地址= 页面始址 +页内偏移量

图

子主题

基本地址变换机构

 图

子主题

页表寄存器的作用

存放页表起始地址

存放页表长度

地址变换过程

1. 根据逻辑地址算出页号、页内偏移量

2. 页号的合法性检查(与页表长度对比)

3. 若页号合法，再根据页表起始地址、页号找到对应页表项

第一次访问内存:查页表

4. 根据页表项中记录的内存块号、页内偏移量得到最终的物理地址

5. 访问物理内存对应的内存单元

第二次访问内存: 访问目标内存单元

其他小细节

页内偏移量位数与页面大小之间的关系(要能用其中一个条件推出另一个条件)

页式管理中地址是一维的

实际应用中，通常使一个页框恰好能放入整数个页表项

为了方便找到页表项，页表一般是放在连续的内存块中的

在页式存储管理中，CPU 将虚拟地址分解为页号和页内偏移量，然后通过硬件中的页表寄存器和内存管理单元(MMU)，将页号转换为物理地址，再拼接上页内偏移量，得到最终的内存物理地址。这一过程是由硬件自动完成的，不需要操作系统或其他软件的干预。

例题

子主题

具有快表的地址变换机构 (基本地址变换机构的改进版本)

什么是快表（TLB）

快表，又称联想寄存器 (TLB，translation lookaside buffer)，是一种访问速度比内存快很多的高速缓存(TLB不是内存!)，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。

图

子主题

引入快表后，地址的变换过程

 图

子主题

例题

子主题

局部性原理

两级页表

单级页表存在什么问题？

图

子主题

所有页表项必须连续存放，页表过大时需要很大的连续空间

在一段时间内并非所有页面都用得到，因此没必要让整个页表常驻内存

说明单级页表驻留在内存中

补充

页表和段表同样存储在内存中，系统提供给用户的物理地址空间为总空间大小减去页表或段表的长度。 因为页表和段表的长度不能确定，所以提供给用户的物理地址空间大小也不能确定。

两级页表

将长长的页表再分页

逻辑地址结构:(一级页号，二级页号，页内偏移量)

注意几个术语:页目录表/外层页表/顶级页表

图

子主题

在多级页表中，页表基址寄存器存放的是顶级页表的起始物理地址，所以存放的是一级页表的起始物理地址。

如何实现地址变换？

1.按照地址结构将逻辑地址拆分成三部分

2.从PCB 中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置

3.根据二级页号查表，找到最终想访问的内存块号

4.结合页内偏移量得到物理地址

几个细节

多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级

子主题

多级页表的访存次数(假设没有快表机构)--N 级页表访问一个逻辑地址需要 N+1次访存

段式管理

分段

将地址空间按照程序自身的逻辑关系划分为若干个段，每段从0开始编址

每个段在内存中占据连续空间，但各段之间可以不相邻

逻辑地址结构:(段号，段内地址)

图

子主题

段表

记录逻辑段到实际存储地址的映射关系

每个段对应一个段表项。各段表项长度相同，由段号(隐含)、段长，基址组成

图

子主题

地址变换

1. 由逻辑地址得到段号、段内地址

2. 段号与段表寄存器中的段长度比较，检查是否越界

3.由段表始址、段号找到对应段表项

4.根据段表中记录的段长，检查段内地址是否越界

5.由段表中的"基址+段内地址"得到最终的物理地址

6.访问目标单元

图

子主题

分段vs分页

分页对用户不可见(透明)，分段对用户可见(不透明)

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

分段更容易实现信息的共享和保护(纯代码/可重入代码可以共享)

分页(单级页表)、分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构

引入分段的主要目的是更好地满足用户的需求，实现程序的模块化和保护

实现离散分配并提高内存利用率是引入分页的主要目的

图

子主题

如果允许不同页表的页表项指向同一个页帧

实现内存“复制”操作时，不需要将页面的内容逐字节复制， 而只需将页表中指向该页面的指针复制到目的地址的页表项中

共享段表

定义

在段式存储管理中,若有些段可被多个进程共享,则可用一个单独的共享段表来描述这些段, 而不需要在每个进程的段表中都保存一份。

共享段表的作用是实现多个进程共享同一段代码或数据

多个进程共享同一段物理内存空间并不需要用到共享段表，只需在各自的段表中指向相同的物理地址即可。

多个进程共享同一段逻辑地址空间是不可能的，因为每个进程的逻辑地址空间都是相互独立

在段式存储管理中，并不要求各个进程中相同功能的段必须有相同的段号

段页式管理

分段+分页

图

子主题

将地址空间按照程序自身的逻辑关系划分为若干个段，在将各段分为大小相等的页面

将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存

逻辑地址结构:(段号，页号，页内偏移量)

段表，页表

每个段对应一个段表项。各段表项长度相同，由段号(含)页表长度、页表存放地址组成

每个页对应一个页表项。各页表项长度相同，由页号(隐含)、页面存放的内存块号组成

图

子主题

地址变换

图

子主题

1.由逻辑地址得到段号、页号、页内偏移量

2.段号与段表寄存器中的段长度比较，检查是否越界

3.由段表始址、段号找到对应段表项

4.根据段表中记录的页表长度，检查页号是否越界

5.由段表中的页表地址、页号得到查询页表，找到相应页表项

6.由页面存放的内存块号、页内偏移量得到最终的物理地址

7.访问目标单元

访问一个逻辑地址所需访存次数

第一次--查段表、第二次--查页表、第三次--访问目标单元

可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存

虚拟内存管理

虚拟内存的基本概念

原因： 传统存储管理方式的特征，缺点 (就是上面的弊端）

一次性: 作业数据必须一次全部调入内存

驻留性: 作业数据在整个运行期间都会常驻内存

局部性原理

时间局部性: 现在访问的指令、数据在不久后很可能会被再次访问(for 循环)

空间局部性: 现在访问的内存单元周围的内存空间，很可能在不久后会被访问 (数据也一般是以向量、数组、表等形式聚存储的)

高速缓存技术: 使用频繁的数据放到更高速的存储器中

方法： 1. 时间局部性通过将近来使用的指令和数据保存到高速缓存中，并使用高速缓存的层次结构实现。 2. 空间局部性通常使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。 3. 虚拟内存技术实际上建立了“内存-外存”的两级存储器结构，利用局部性原理实现高速缓存。

虚拟内存的定义和特征

程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需换出一些数据

图

子主题

虚拟内存的最大容量是由计算机的地址结构(CPU寻址范围)确定的

虚拟内存的实际容量=min(内存和外存容量之和，CPU寻址范围)

特征 (内存)

多次性: 无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。

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

虚拟性: 从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

如何实现虚拟内存技术

访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存(请求调页功能)

内存空间不够时，将内存中暂时用不到的信息换出到外存(页面置换功能)

虚拟内存的实现

请求分页存储管理

请求分段存储管理

请求段页式存储管理

不管哪种方式，都需要有一定的硬件支持。 一般需要的支持有以下几个方面:

<ul><li>一定容量的内存和外存。</li><li>页表机制(或段表机制)，作为主要的数据结构。</li><li>中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断。</li><li>地址变换机构，逻辑地址到物理地址的变换。</li></ul>

补充

虚拟存储技术基于程序的局部性原理。 局部性越好(本质就是不要使用全部) ，虚拟存储系统越能更好地发挥作用

请求分页管理方式

触发条件

进程访问的页面不在物理内存(触发缺页中断)

作用

按需将磁盘中的页面加载到物理内存，避免一次性加载全部页面

页表机制

图

子主题

在基本分页的基础上增加了几个表项

<ul><li>状态位: 表示页面是否已在内存中</li><li>访问字段: 记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考</li><li>修改位: 表示页面调入内存后是否被修改过，只有修改过的页面才需在置换时写回外存</li><li>外存地址:页面在外存中存放的位置</li></ul>

缺页中断机构

<ul><li>在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，请求操作系统的缺页中断处理程序处理。</li><li>此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。</li><li>若内存中有空闲页框，则为进程分配一个页框，将所缺页面从外存装入该页框，并修改页表中相应的表项。</li><li>若内存中没有空闲页框，则由页面置换算法选择一个页面淘汰，若该页在内存期间被修改过，则还要将其写回外存(写回法)。</li><li>未被修改过的页面不用写回外存。</li></ul>

缺页中断作为中断，同样要经历诸 如保护 CPU 环境、分析中断原因、转入缺页中断处理程序、恢复 CPU 环境等几个步骤。 但与一般的中断相比，它有以下两个明显的区别:

在指令执行期间而非一条指令执行完后产生和处理中断，属于内部异常。

一条指令在执行期间，可能产生多次缺页中断。

缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面

缺页中断属于内中断，属于内中断中的“故障”，即可能被系统修复的异常

中断的分类

内中断 (内部异常)

陷阱，陷入（trap）断点

故障（fault）缺页

终止（abort）分母是0

外中断

I/O中断请求

人工干预

一条指令在执行过程中可能产生多次缺页中断

缺页率

顺序执行的情况下进程访问缺页中断的次数等于进程访问的页帧数

正常情况, 页帧数少会导致缺页次数多

正常情况, 页面增大会导致缺页次数减少

进程的数量越多，对内存资源的竞争越激烈，每个进程被分配的物理块数越少，缺页率也就越高

工作集的大小决定了分配给进程的物理块数，分配给进程的物理块数越多，缺页率就越低

补充

操作系统执行的操作

修改页表

磁盘I/O

分配页框

地址变换机构 (重点关注与基本分页不同的地方)

图

子主题

找到页表项是需要检查页面是否在内存中

若页面不再内存中，需要请求调页

若内存空间不够，还需换出页面

页面调入内存后，需要修改相应页表项

提高TLB命中率

增大TLB容量

提高页面大小减速缺页率

页面置换算法

进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页，换出到外存。 选择调出哪个页面的算法就称为页面置换算法。 页面的换入、换出需要磁盘 IO，开销较大，因此好的页面置换算法应该追求更低的缺页率。

触发条件

物理内存已满，需加载新页面时

作用

选择牺牲页,换出到磁盘，腾出空间给新页面a

最佳置换算法（opt）

概念

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面(要预先知道内容)，这样可以保证最低的缺页率。

图

子主题

缺页率最小，性能最好,但无法实现,

先进先出置换算法（FIFO）

概念

每次选择淘汰的页面是最早进入内存的页面

图

子主题

但该算法没有利用局部性原理，与进程实际运行的规律不相适应， 最早进入内存的页面也可能经常被访问，因此性能较差。

可能产生当驻留集增大时页故障数不减反增的 Belady 异常

实现简单;但性能很差可能出现Belady异常

只有 FIFO 算法可能出现 Belady 异常， LRU 和 OPT 算法永远不会出现 Belady 异常。

最近最久未使用置换算法(LRU)

 概念

每次淘汰的页面是最近最久未使用的页面

 图

子主题

性能很好;但需要硬件支持(本质是查找时间最久的进行替换这涉及排序 ) ，算法开销大

时钟置换算法（CLOCK）

概念

循环扫描各页面第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。 若第一轮没选中，则进行第二轮扫描

在选择淘汰一页时，只需检查页面的访问位: 若为0，就选择该页换出; 若为1，则将它置为 0，暂不换出，给予该页第二次驻留内存的机会，再依次顺序检査下一个页面。 当检查到队列中的最后一个页面时，若其访问位仍为1，则返回到队首去循环检查。 因为该算法是循环地检查各个页面的使用情况，所以称为CLOCK 算法。 但是，因为该算法只有一位访问位，而置换时将未使用过的页面换出，所以也称最近未用(NRU)算法。

 图

子主题

LRU 算法的性能接近 OPT 算法，但实现起来的开销大。 因此，操作系统的设计者尝试了很多算法， 试图用比较小的开销接近LRU 算法的性能，这类算法都是 CLOCK 算法的变体。

改进型的时钟置换算法

原因： 将一个页面换出时，若该页已被修改过，则要将该页写回磁盘，若该页未被修改过，则不必将它写回磁盘。 可见，对于修改过的页面，替换代价更大。 在改进型 CLOCK 算法中，除考虑页面使用情况外，还增加了置换代价--修改位。 在选择页面换出时，优先考虑既未使用过又未修改过的页面。 由访问位4和修改位M可以组合成下面四种类型的页面:

<ul><li>1类A=0.M=0:最近未被访问，且未被修改，是最佳的淘汰页。</li><li>2类A=0,M=1:最近未被访问，但已被修改，是次佳的淘汰页.</li><li>3类A=1,M=0:最近已被访问，但未被修改，可能再被访问。</li><li>4类A=1,M=1:最近已被访问，且已被修改，可能再被访问 基于的是最近未使用的算法所以未访问优先</li></ul>

概念

子主题

改进型 CLOCK 算法优于简单 CLOCK 算法的地方在于，可减少磁盘的 I/0 操作次数。 但为了找到一个可置换的页，可能要经过几轮扫描，即实现算法本身的开销将有所增加。

例题

子主题

区别

子主题

页面分配策略

触发条件

进程创建或初始化时

作用

为进程分配初始物理页帧(如代码段、数据段)，并设定内存配额(如固定分配或按需增长)

驻留集

指请求分页存储管理中给进程分配的内存块的集合

对于分页式的虚拟内存，在进程准备执行时，不需要也不可能将一个进程的所有页都读入主存。 因此，操作系统必须决定读取多少页，即决定给特定的进程分配几个页框。 给一个进程分配的页框的集合就是这个进程的驻留集。需要考虑以下两点:

驻留集越小， 驻留在内存中的进程就越多，可以提高多道程序的并发度，但分配给每个 进程的页框太少，会导致缺页率较高，CPU 需耗费大量时间来处理缺页。

驻留集越大， 当分配给进程的页框超过某个数量时，再为进程增加页框对缺页率的改善是不明显的， 反而只能是浪费内存空间，还会导致多道程序并发度的下降。

页面分配，置换策略组合

在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。 在进行置换时，也可采取两种策略，即全局和局部置换。 于是可组合出下面三种适用的策略。

固定分配 VS 可变分配: 区别在于进程运行期间驻留集大小是否可变

为每个进程分配固定数量的物理块，在进程运行期间都不改变

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

局部置换 VS 全局置换: 区别在于发生缺页时是否只能从进程自己的页面中选择一个换出

所谓局部置换，是指若进程在运行中发生缺页， 则只能从分配给该进程在内存的页面中选出一页换出， 然后再将所缺页面调入，以保证分配给该进程的内存空间不变。

全局置换，是指若进程在运行中发生缺页， 则系统从空闲物理块队列中取出一块分配给该进程， 并将所缺页面调入。

固定分配,局部置换: 进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页(出一页进一页数量没变) 实现这种策略时，难以确定应为每个进程分配的物理块数量:太少会频繁出现缺页中断，太多又会降低 CPU 和其他资源的利用率

可变分配,全局置换: 只要缺页就分配新物理块，可能来自空闲物理块，也可能需换出别的进程页面 存在弊端，如它会盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降。

可变分配,局部置换: 频繁缺页的进程，多分配一些物理块;缺页率很低的进程，回收一些物理块。直到缺页率合适 这种方法在保证进程不会过多地调页的同时，也保持了系统的多道程序并发能力。 当然它需要更复杂的实现，也需要更大的开销，但对比频繁地换入/换出所浪费的计算机资源，这种牺牲是值得的。

固定分配不能出现全局置换 (全局置换意味着一个进程拥有的物理块数量必然会变，因此不可能与固定分配组合)

因为固定分配不是只一个进程用这个方法  其他进程也用这个方法，为满足这调用其他固定分配的不合适

物理块调入算法

采用固定分配策略时，将系统中的空闲物理块分配给各个进程，可采用下述几种算法。 1)平均分配算法，将系统中所有可供分配的物理块平均分配给各个进程。 2)按比例分配算法，根据进程的大小按比例分配物理块。 3)优先权分配算法，为重要和紧迫的进程分配较多的物理块。 通常采取的方法是将所有可分配的物理块分成两部分:一部分按比例分配给各个进程::一部分则根据优先权分配。

何时调入页面

预调页策略: 一般用于进程运行前

请求调页策略: 进程运行时，发现缺页再调页

从何处调页

请求分页系统中的外存分为两部分: 用于存放文件的文件区和用于存放对换页面的对换区，也称交换区。 对换区采用连续分配方式，而文件区采用离散分配方式，因此对换区的磁盘I0速度比文件区的更快。 这样，当发生缺页请求时，系统从何处将缺页调入内存就分为三种情况:

对换区--采用连续存储方式，速度更快; 文件区--采用离散存储方式，速度更慢。

对换区足够大: 运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行

对换区不够大: 不会修改的数据每次都从文件区调入(读); 会修改的数据调出到对换区(写)，需要时再从对换区调入 (读比写的速度快）

UNIX方式: 第一次使用的页面都从文件区调入;调出的页面都写回对换区，再次使用时从对换区调入 UNIX方式:运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。 若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。

图

子主题

抖动（颠簸）现象

页面频繁换入换出的现象。主要原因是分配给进程的物理块不够

如何调入页面

<ul><li>当进程所访问的页面不在内存中时(存在位为 0)，便向 CPU 发出缺页中断，中断响应后便转入缺页中断处理程序。</li><li>该程序通过查找页表得到该页的物理块，此时，若内存未满，则启动磁盘 I/0，将所缺页调入内存，并修改页表。</li><li>若内存已满，则先按某种置换算法从内存中选出一页准备换出(置换算法);若该页未被修改过(修改位为0)，则不需要将该页写回磁盘(写回法);</li><li>但是，若该页已被修改(修改位为 1)，则必须将该页写回磁盘，然后将所缺页调入内存，并修改页表中的相应表项，置其存在位为1。</li><li>调入完成后，进程就可利用修改后的页表形成所要访问数据的内存地址。</li></ul>

工作集

在某段时间间隔里，进程实际访问页面的集合驻留集大小一般不能小于工作集大小

 图

子主题

驻留集是指分配给进程的物理页面的集合

工作集是指在某段时间内，进程实际要访问的页面的集合。

工作集不一定是驻留集的子集，因为有些工作集中的页面可能还未被调入内存，或已被换出内存。 只有当工作集完全包含在驻留集中时，才能保证进程不发生缺页中断。

子主题

内存映射文件

内存映射文件(Memory-MappedFiles)是操作系统向应用程序提供的一个系统调用，它与虚拟内存有些相似，在磁盘文件与进程的虚拟地址空间之间建立映射关系。

特性

进程可使用系统调用，请求操作系统将文件映射到进程的虚拟地址空间

以访问内存的方式读写文件

进程关闭文件时，操作系统负责将文件数据写回磁盘，并解除内存映射

多个进程可以映射同一个文件，方便共享

优点

程序员编程更简单，已建立映射的文件，只需按访问内存的方式读写即可

文件数据的读入/写出完全由操作系统负责，I/0效率可以由操作系统负责优化

 图

子主题

多个进程可以映射同一个文件，实现共享在物理内存中，一个文件对应同一份数据，当一个进程修改文件数据时，另一个进程可以立马“看到'

虚拟存储器性能影响因素

缺页率是影响虚拟存储器性能的主要因素，而缺页率又受到页面大小、分配给进程的物理块数、页面置换算法以及程序的编制方法的影响。 根据局部性原理，页面较大则缺页率较低，页面较小则缺页率较高。 页面较小时，一方面减少了内存碎片，有利于提高内存利用率;另一方面，也会使每个进程要求较多的页面，导致页表过长，占用大量内存。 页面较大时，虽然可以减少页表长度，但会使页内碎片增大。 分配给进程的物理块数越多，缺页率就越低，但是当物理块超过某个数量时，再为进程增加一个物理块对缺页率的改善是不明显的。 可见，此时已没有必要再为它分配更多的物理块，否则也只能是浪费内存空间。 只要保证活跃页面在内存中，保持缺页率在一个很低的范围即可。 好的页面置换算法可使进程在运行过程中具有较低的缺页率。选择LRU、CLOCK 等置换算法，将未来有可能访问的页面尽量保留在内存中，从而提高页面的访问速度，写回磁盘的频率。 换出已修改过的页面时，应当写回磁盘，若每当一个页面被换出就将它写回磁盘，则每换出一个页面就需要启动一次磁盘，效率极低。 为此在系统中建立一个已修改换出页面的链表，对每个要被换出的页面(已修改)，可以暂不将它们写回磁盘，而将它们挂在该链表上，仅当被换出页面数达到给定值时，才将它们一起写回磁盘，这样就可显著减少磁盘IO 的次数，即减少已修改页面换出的开销。 此外，若有进程在这批数据还未写回磁盘时需要再次访问这些页面，则不需从外存调入，而直接从已修改换出页面链表上获取，这样也可以减少页面从磁盘读入内存的频率，减少页面换进的开销。 编写程序的局部化程度越高，执行时的缺页率就越低。 若存储采用的是按行存储，则访问时就要尽量采用相同的访问方式，避免按列访问造成缺页率过高的现象。

地址翻译

结合王道强化 

文件管理

文件

文件的基本概念

文件元数据和索引节点(inode)

文件的操作

建立， 删除， 打开， 关闭， 读， 写文件的保护; 文件的逻辑结构; 文件的物理结构目录

目录的基本概念; 树形目录; 目录的操作; 硬链接和软链接

文件系统

文件系统的全局结构(layout): 文件系统在外存中的结构，文件系统在内存中的结构外存空闲空间管理办法; 虚拟文件系统; 文件系统挂载(mounting)

文件

文件的基本概念

文件(File)是以硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档、图片、程序等。在系统运行时，计算机以进程为基本单位进行资源的调度和分配;而在用户进行的输入、输出中，则以文件为基本单位。大多数应用程序的输入都是通过文件来实现的，其输出也都保存在文件中，以便信息的长期存储及将来的访问。当用户将文件用于程序的输入、输出时，还希望可以访问、修改和保存文件等，实现对文件的维护管理，这就需要系统提供一个文件管理系统操作系统中的文件系统(File System)就是用于实现用户的这些管理要求的。要清晰地理解文件的概念，就要了解文件究竟由哪些东西组成。

文件的定义:一组有意义的信息的集合

文件的属性: 文件名、标识符、类型、位置、大小、保护信息..

文件内部应该如何被组织起来(文件的逻辑结构)

图

子主题

无结构文件 (如文本文件)

由一些二进制或字符流组成，又称“流式文件”

有结构文件 (如数据库表)

由一组相似的记录组成，又称"记录式文件”

一条记录是一组相关数据项的集合

数据项是文件系统中最基本的数据单位

文件之间应该如何被组织起来(目录结构)

 图

子主题

根目录(如: C,D,E盘)

用户可以自己创建一层一层的目录，各层目录中存放相应的文件。 系统中的各个文件就通过一层一层的目录合理有序的组织起来了

目录其实也是一种特殊的有结构文件【由记录组成 如何实现文件目录是之后会重点探讨的问题

所谓的“目录"其实就是我们熟悉的"文件夹"

操作系统应向上提供哪些功能(create、delete、open、close、read、write 系统调用)

文件应如何存放在外存中(文件的物理结构)

图

子主题

操作系统以“块”为单位为文件分配存储空间，因此即使一个文件大小只有10B,， 但它依然需要占用 1KB 的磁盘块。外存中的数据读入内存时同样以块为单位

类似于内存分为一个个“内存块”外存会分为一个个“块/磁盘块/物理块”。 每个磁盘块的大小是相等的，每块一般包含2的整数幂个地址 (如本例中,一块包含 2^10 个地址，即 1KB) 同样类似的是,文件的逻辑地址也可以分为(逻辑块号，块内地址)， 操作系统同样需要将逻辑地址转换为外存的物理地址(物理块号，块内地址)的形式 块内地址的位数取决于磁盘块的大小

与内存一样，外存也是由一个个存储单元组成的， 每个存储单元可以存储一定量的数据(如 1B)。每个存储单元对应一个物理地址

操作系统如何管理外存中的空闲块(存储空间的管理)

 图

子主题

文件数据放在连续的几个磁盘块中

文件数据放在离散的几个磁盘块中此时， 应该如何记录各个磁盘块之间的先后顺序呢?

操作系统需要提供的其他文件管理功能

文件共享

文件保护

文件系统工作的完整链条

系统调用 - 唯一的访问桥梁

用户程序与文件系统交互的唯一接口

用户通过目录找到文件，

用于组织和定位文件的一种数据结构， 实现了文件名到文件实体(如文件控制块FCB或Inode编号)的映射

单级目录

两级目录

树形目录

图形目录

索引节点

文件逻辑结构定义了用户视图，(用户视角)

从用户角度看到的文件的组织形式， 是应用程序直接处理的数据结构

无结构文件(流式文件)(如.txt, .exe)

有结构文件(记录式文件)(如数据库文件、.csv文件)

顺序文件

串结构

顺序结构

索引文件

索引顺序文件

物理结构将用户请求映射到硬件地址,(系统视角)

文件在物理磁盘上是如何实际存储的， 即如何为文件分配磁盘块

连续分配

链接分配

隐式链接

显式链接

索引分配

而空闲空间管理则为物理结构提供存储资源支持

跟踪磁盘上哪些块是空闲的， 以便在创建文件时进行分配

空闲表法/空闲链表法

位示图法 (Bit Map)

成组链接法

文件共享-协作功能

让多个用户或进程访问同一文件

目录项创建硬链接(共享Inode)

软链接(共享路径名)

文件保护-安全屏障

文件的逻辑结构

无结构文件

无结构文件:文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件 。如: Windows 操作系统中的 .txt 文件。

 图

有结构文件

 概念

 图

子主题

有结构文件: 由一组相似的记录组成，又称“记录式文件”，每条记录又若干个数据项组成。

如:数据库表文件。一般来说，每条记录有一个数据项可作为关键字(作为识别不同记录的ID)

根据各条记录的长度(占用的存储空间)是否相等，又可分为定长记录和可变长记录两种

顺序文件

图

子主题

串结构: 记录顺序与关键字无关

顺序结构: 记录按关键字顺序排列

可变长记录的顺序文件无法实现随机存取(i*L) ，定长记录可以

定长记录、顺序结构的顺序文件可以快速检索(根据关键字快速找到记录)

最大缺点: 不方便增加/删除 记录

索引文件

图

子主题

建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录

索引表本身就是定长记录的顺序文件、一个索引表项就是一条定长记录，因此索引文件可支持随机存取

若索引表按关键字顺序排列，则可支持快速检索

解决了顺序文件不方便增/删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间

索引顺序文件

 图

子主题

Tips: 要为N个记录的文件建立K级索引，| 则最优的分组是每组 NV(K+1)个记录

检索一个记录的平均查找次数是((N1/(K+1) )/2)*(K+1)

如:本例中，建立2级索引，则最优分组为每组100000^1/3=100个记录 平均查找次数是(100/2)*3=150 次

50+50+50

求出每组的记录数也可以算出来"每组的记录数*(K+1)"

例题

子主题

将记录分组，每组对应一个索引表项,一个组就是(一个顺序文件)

检索记录时先顺序查索引表，找到分组，再顺序查找分组

当记录过多时，可建立多级索引表

文件目录的实现

 图

子主题

一个文件对应一个FCB,一个FCB就是一个目录项，多个FCB组成文件目录

对目录的操作:搜索、创建文件、删除文件、显示文件、修改文件

FCB是文件控制块的一个目录项

目录结构

单级目录结构

 图

子主题

一个系统只有一张目录表不允许文件重名

两级目录结构

 图

子主题

不同用户的文件可以重名，但不能对文件进行分类

多级(树形)目录结构

 图

子主题

不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享

系统根据“文件路径"找到目标文件

从根目录出发的路径是“绝对路径"/照片/2015-08/自拍.jpg")

从"当前目录"出发的路径是“相对路径"("/照片/2015-08/自拍.jpg")

无环图目录结构

图

子主题

在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图 可以更方便地实现多个用户间的文件共享。

为共享结点设置一个共享计数器 计数器为0时才真正删除该结点

支持通过链接(硬链接、软链接)实现一个文件有多个路径名，形成有向无环图(DAG)

索引结点

 图

子主题

除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点

目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅减小

由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘I/0的次数就少了很多

文件的物理结构

文件块，磁盘块

子主题

在内存管理中，进程的逻辑地址空间被分为一个一个页面同样的， 在外存管理中为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个个的文件“块” 于是:文件的逻辑地址也可以表示为(逻辑块号，块内地址)的形式。

操作系统为文件分配存储空间都是以块为单位的

用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地 址的映射

若块的大小是1KB，则1MB大小的文件可以被分为1K个块

子主题

 连续分配

概念

连续分配方式要求每个文件在磁盘上占有一组连续的块。

 图

子主题

结论:物理上采用连续分配存储空间利用率低，会产生难以利用的磁盘碎片 |可以用紧凑来处理碎片，但是需要耗费很大的时间代价

读取某个磁盘块时，需要移动磁头。 访问的两个磁盘块相隔越远，移动磁头所需时间就越长。

结论: 连续分配的文件在顺序读/写时速度最快

因为其他方法是离散分配

(逻辑块号，块内地址)→(物理块号，块内地址)需转换块号就行，块内地址保 持不变

物理块号 = 起始块号+逻辑块号 当然， 还需要检查用户提供的逻辑块号是否合法(逻辑块号>长度就不合法)

文件目录中记录存放 的起始块号和长度(总共占用几个块)一个文件可以有多个逻辑块

可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问(即随机访问可以算出来就是;)

优点

支持顺序访问和直接访问(即随机访问); 连续分配的文件在顺序访问时速度最快

缺点

不方便文件拓展;存储空间利用率低，会产生磁盘碎片

链接分配

 概念

链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。 分为隐式链接和显式链接两种。

隐式链接

 概念

目录中记录了文件存放的起始块号和结束块号。 当然，也可以增加一个字段来表示文件的长度

采用链式分配(隐式链接)方式的文件，只支持顺序访问，不支持随机访问，查找效率低。 另外，指向下一个盘块的指针也需要耗费少量的存储空间。

除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。 文件目录包括文件第一块的指针和最后一块的指针。(这些指针对用户是透明的)

 图

子主题

 优点

很方便文件拓展，不会有碎片问题，外存利用率高。

缺点

只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

显式链接

概念

把用于链接文件各物理块的指针显式地存放在一张表中，即 文件分配表(FAT，FileAlocation Table)。 一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。

 图

子主题

优点

很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。 相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高

缺点

文件分配表的需要占用一定的存储空间。

索引分配

概念

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表， 索引表中记录了文件的各个逻辑块对应的物理块 (索引表的功能类似于内存管理中的页表--建立逻辑页面到物理页之间的映射关系)。

索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

在显式链接的链式分配方式中，文件分配表FAT 是一个磁盘对应一张。 而索引分配方式中，索引表是一个文件对应一张。

 图

子主题

可以用固定的长度表示物理块号(如:假设磁盘总容量为1TB=240B， 磁盘块大小为1KB，则共有 2^30个磁盘块， 则可用4B (是32位 11111111111111来表示数字)表示磁盘块号)， 因此，索引表中的“逻辑块号”可以是隐含的。

子主题

链接方案

 概念

如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

若想要访问文件的最后一个逻辑块，就必须找到最后一个索引块(第256个索引块)， 而各个索引块之间是用指针链接起来的，因此必须先顺序地读入前 255 个索引块。

 图

子主题

 多层索引

概念

建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据 文件大小的要求再建立第三层、第四层索引块。

若采用多层索引，则各层索引表大小不能超过一个磁盘块

采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作

 图

子主题

混合索引

概念

多种索引分配方式的结合。 例如，一个文件的顶级索引表中， 既包含直接地址索引(直接指向数据块)， 又包含一级间接索引(指向单层索引表)、 还包含两级间接索引(指向两层索引表)。

图

子主题

 Linux 的 inode（索引节点）

子主题

一个索引节点就是一个文件,索引节点的总数即文件的总数

子主题

使用close操作回收索引节点时他是在内存中的

重点考点

①要会根据多层索引、混合索引的结构计算出文件的最大长度(Key:各级索引表最大不能超过一个块); ②要能自己分析访问某个数据块所需要的读磁盘次数(Key:FCB中会存有指向顶级索引块的指针， 因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。 另外，要注意题目条件--顶级索引块是否已调入内存)

 总结

子主题

连续存储因为是连续的所以顺序存储速度是最快的

补充

簇

子主题

易混淆点 支持随机访问

子主题

逻辑块里存的就是文件的记录

如果没有给出块内地址n=(i%64)*16 (记得乘位数/长度)

子主题

连续分配是可以算出来的所以只有链接分配(默认是隐式分配)不能随机分配, 但是在要移动位置的块中连续分配就要重点考虑了

子主题

 逻辑结构vs物理结构

逻辑结构

 图

子主题

索引文件: 从用户视角来看，整个文件依然是连续存放的。 如:前1MB存放索引项，后续部分存放记录

顺序文件: 各个记录可以顺序存储或链式存储

用户(文件创建者)的视角看到的亚子

在用户看来，整个文件占用连续的逻辑地址空间

文件内部的信息组织完全由用户自己决定，操作系统并不关心

物理结构

 图

子主题

索引文件的索引表:用户自己建立的，映射:关键字→记录存放的逻辑地址

索引分配的索引表:操作系统建立的，映射:逻辑块号→物理块号

文件内部各条记录链式存储:由创建文件的用户自己设计的 文件整体用链接分配:由操作系统决定

由操作系统决定文件采用什么物理结构存储

操作系统负责将逻辑地址转变为(逻辑块号，块内偏移量)的形式，并负责实现逻辑块号到物理块号的映射

外存空闲空间管理方法

 存储空间的划分与初始化

文件卷(逻辑卷)，目录区、文件区的概念

目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据

 图

目录区主要存放文件目录信息(FCB)、用于磁盘存储空间管理的信息

子主题

 几种管理方法

空闲表法

图

子主题

空闲表中记录每个连续空闲区的起始盘块号、盘块数

分配时可采用首次适应、最佳适应等策略;  回收时注意表项的合并问题

如何回收磁盘块:与内存管理中的动态分区分配很类似， 当回收某个存储区时需要有四种情况-- ①回收区的前后都没有相邻空闲区; ②回收区的前后都是空闲区; ③回收区前面是空闲区; ④回收区后面是空闲区。 总之，回收时需要注意表项的合并问题

空闲链表法

空闲盘块链

以盘块单位组成一条空闲链

分配时从链头依次取出空闲块，回收时将空闲块插到链尾

 图

子主题

空闲盘块中存储着下一个空闲盘块的指针

空闲盘区中的第一个盘块内记录了盘区的长度下一个盘区的指针

空闲盘区链

以盘区单位组成一条空闲链

分配时可采用首次适应、最佳适应等策略;回收时注意相邻空闲盘区合并的问题

位示图法

一个二进制位对应一个盘块。(字号，位号)或(行号，列号)与盘块号--对应

重要考点: 要能够自己推出盘块号→(字号，位号)之间的相互转换公式

需要注意的题目条件

二进制位 0/1 到底哪个代表空闲，哪个代表不空闲

字号、位号、盘块号到底是从0开始还是从1开始

 图

子主题

位示图一般用连续的“字”来表示

例题

子主题

成组链接法

UNIX 采用的策略，适合大型文件系统。理解即可，不方便用文字描述的知识点也很难作为考题

例题

子主题

子主题

文件的操作

 创建文件

分配外存空间，创建目录项

删除文件

回收外存空间，删除目录项

打开文件

 图

子主题

将目录项中的信息复制到内存中的打开文件表中， 并将打开文件表的索引号返回给用户

打开文件之后，对文件的操作不再需要每次都查询目录， 可以根据内存中的打开文件表进行操作

每个进程有自己的打开文件表，系统中也有一张总的打开文件表

进程打开文件表中特有的属性: 读写指针、访问权限(只读?读写?)

系统打开文件表中特有的属性:打开计数器(有多少个进程打开了该文件)

关闭文件

将进程打开文件表中的相应表项删除

系统打开文件表的打开计数器减1，若打开计数器为0，则删除系统表的表项

 图

子主题

操作系统在处理 Close 系统调用时

1.将进程的打开文件表相应表项删除

2.回收分配给该文件的内存空间等资源

3.系统打开文件表的打开计数器count减1，若count=0， 则删除对应表项。

并不意味着将文件数据写回磁盘(什么都没做)

读文件

根据读指针、读入数据量、内存位置将文件数据从外存读入内存

写文件

根据写指针、写出数据量、内存位置将文件数据从内存写出外存

区分用户的访问权限和用户优先级

用户访问权限是指用户有没有权限访问该文件

用户优先级是指在多个用户同时请求该文件时应该先满足谁

文件共享

 硬链接

各个用户的目录项指向同一个索引结点

索引结点中需要有链接计数 count

某用户想删除文件时，只是删除该用户的目录项，且count--

只有 count ==0 时才能真正删除文件数据和索引结点， 否则会导致指针悬空

 图

子主题

软链接 (符文链接)

在一个 Link 型的文件中记录共享文件的存放路径(Windows 快捷方式)

操作系统根据路径一层层查找目录，最终找到共享文件

即使软链接指向的共享文件已被删除，Link型文件依然存在， 只是通过 Link 型文件中的路径去查找共享文件会失败(找不到对应目录项)

由于用软链接的方式访问共享文件时要查询多级目录， 会有多次磁盘I0因此用软链接访问共享文件的速度要比硬链接更慢

图

子主题

例题

子主题

文件的保护

口令保护

为文件设置一个“口令"，用户想要访问文件时需要提供口令，由系统验证口令是否正确

实现开销小，但“口令"一般存放在FCB或索引结点中(也就是存放在系统中)因此不太安全

加密保护

 图

子主题

用一个“密码”对文件加密，用户想要访问文件时，需要提供相同的“密码"才能正确的解密

安全性高，但加密/解密需要耗费一定的时间(Eg:异或加密)

访问控制

用一个访问控制表(ACL)记录各个用户(或各组用户)对文件的访问权限

对文件的访问类型可以分为:读/写/执行/删除等

实现灵活，可以实现复杂的文件保护功能

 图

子主题

文件系统

文件系统的层次结构

例子

假设某用户请求删除文件“D:/工作目录/学生信息.xlsx”的最后100条记录。

用户接口

1. 用户需要通过操作系统提供的接口发出上述请求

文件目录系统

2.用户接口由于用户提供的是文件的存放路径， 因此需要操作系统一层一层地查找目录，找到对应的目录项

存取控制模块(存取控制验证层)

3.不同的用户对文件有不同的操作权限， 因此为了保证安全，需要检査用户是否有访问权限

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

4.验证了用户的访问权限之后， 需要把用户提供的“记录号”转变为对应的逻辑地址

物理文件系统

5.知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址

设备管理程序模块

6.要删除这条记录，必定要对磁盘设备发出请求

辅助分配模块

7.删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收

 图

子主题

逻辑文件存放到存储介质上  意思就是 将用户视角的连续文件(逻辑结构)，映射到磁盘的离散物理块

不同的存储介质有不同的存储特性， 如磁带只能顺序存取， 磁盘可以随机存取， 因此文件的组织形式与存储介质特性有关。

文件系统的全局结构（layout）

 图

子主题

open系统调用打开文件的背后过程

子主题

文件描述符（fd）是进程访问文件/I/O资源的通行证（整数句柄 windows叫文件句柄）

例题

子主题

子主题

①文件描述符 fd: 

②buf 缓冲区首址

③传送的字节数 n

read 的功能是试图从fd指示的文件中读入n字节的数据， 并将它们送至由指针 buf所指示的缓冲区中。

文件系统挂载

子主题

虚拟文件系统

 普通的文件系统

子主题

输入输出(I/O)管理

I/O管理基础

I/O设备的基本概念与分类

什么是I/0设备

将数据 Input/0utput(输入/输出)计算机的外部设备

按使用特性分类

 图

子主题

人机交互类外部设备

存储设备

网络通信设备

按传输速率分类

 图

子主题

低速设备

中速设备

高速设备

按信息交换的单位分类

 图

子主题

块设备(传输快，可寻址)

块设备:如磁盘等--数据传输的基本单位是"块"

字符设备(传输慢，不可寻址，常采用中断驱动方式(一种I/O控制方式)

字符设备:鼠标、键盘等--数据传输的基本单位是"字符"

I/O控制器

I/O设备

用于实现对I/0设备的控制

机械部件

显示屏，鼠标等

电子部件(I/O控制器，设备控制器)

通常是一块插入主板扩充槽的印刷电路板

概念

CPU可控制I/O控制器，又由I/0控制器来控制设备

主要功能

接受和识别CPU发出的命令(要有控制寄存器)

向CPU报告设备的状态(要有状态寄存器)

数据交换(要有数据寄存器，暂存输入/输出的数据)

地址识别(由I/0逻辑实现)

组成

 图

子主题

CPU与控制器之间的接口(实现控制器与CPU之间的通信） |用于实现CPU与控制器之间的通信。CPU通过控制线发出命令; 通过地址线指明要操作的设备;通过数据线来取出(输入)数据，或放入(输出)数据

I/0逻辑(负责识别CPU发出的命令，并向设备发出命令) 负责接收和识别CPU的各种命令(如地址译码)， 对设备发出命令并负责

控制器与设备之间的接口(实现控制器与设备之间的通信)

两种寄存器编址方式

内存映射I/0

控制器中的寄存器与内存统一编制

可以采用对内存进行操作的指令来对控制器进行操作

寄存器独立编制

控制器中的寄存器独立编制

需要设置专门的指令来操作控制器

 图

子主题

I/O控制方式

程序直接控制方式

图

子主题

1.完成一次读/写操作的流程(见右图，Key word:轮询)

2.CPU干预的频率 很频繁，I/0操作开始之前、 完成之后需要CPU介入并且在等待I/0完成的过程中CPU需要不断地轮询检查，

3.数据传送的单位 每次读/写一个字

4.数据的流向 读和写都相对于cpu来说的 读操作(数据输入): I/0设备→CPU→内存 写操作(数据输出): 内存→CPU→I/0设备 每个字的读/写都需要CPU(指的是CPU的寄存器)的帮助

5.主要缺点和主要优点 : 优点: 实现简单。在读/写指令之后，加上实现循环检查的 一系列指令即可(因此才称为“程序直接控制方式” 缺点: CPU和I/O设备只能串行工作， CPU需要一直轮询检查长期处于“忙等”状态，CPU利用率低。

中断驱动方式

图

子主题

2.CPU干预的频率每次I/0操作开始之前、完成之后需要CPU介入。 等待I/0完成的过程中CPU可以切换到别的进程执行

5.主要缺点和主要优点 :与“程序直接控制方式”相比， 优点: 在“中断驱动方式”中， I/O控制器会通过中断信号主动报告I/O已完成， CPU不再需要不停地轮询. CPU和I/O设备可并行工作，CPU利用率得到明显提升。 缺点: 每个字在I/0设备与内存之间的传输，都需要经过CPU。 而频繁的中断处理会消耗较多的CPU时间。

DMA方式

 图

子主题

与“中断驱动方式”相比，DMA方式 (DirectMemoryAccess，直接存储器存取。 主要用于块设备的I/0控制)有这样几个改进

1.数据的传送单位是“块”。不再是一个字、一个字的传送

②数据的流向是从设备直接放入内存，或者从内存直接到设备。 不再需要CPU作为“快递小哥”

③仅在传送一个或多个数据块的开始和结束时，才需要CPU干预

CPU指明此次要进行的操作(如:读操作)，并说明要读入多少数据、 数据要存放在内存的什么位置 数据在外部设备上的地址(如:在磁盘上的地址)

控制器会根据CPU提出的要求完成数据的读/写工作， 整块数据的传输完成后，才向CPU发出中断信号

1.完成一次读/写操作的流程

2.CPU干预的频率仅在传送一个或多个数据块的开始和结束时， 才需要CPU干预

3.数据传送的单位每次读/写一个或多个块 (注意:每次读写的只能是连续的多个块且这些块读入内存后在内存中也必须是连续的)

4.数据的流向(不再需要经过CPU) 读操作(数据输入): I/0设备→内存 写操作(数据输出): 内存→I/0设备

5.主要缺点和主要优点 优点:数据传输以“块”为单位，CPU介入频率进一步降低。 数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。 CPU和IO设备的并行性得到提升。 缺点:CPU每发出一条I/0指令，只能读/写一个或多个连续的数据块。 如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时， CPU要分别发出多条I/0指令，进行多次中断处理才能完成。

通道控制方式

图

子主题

通道: 一种硬件，可以理解为是“弱鸡版的CPU”。 通道可以识别并执行一系列通道指令

与CPU相比，通道可以执行的指令很单一， 并且通道程序是放在主机内存中的，也就是说通道与CPU共享内存

1.完成一次读/写操作的流程

2. CPU干预的频率极低，通道会根据CPU的指示执行相应的通道程序， 只有完成一组数据的读/写后才需要发出中断信号，请求CPU干预

3.数据传送的单位 每次读/写一组数据块

4.数据的流向(在通道的控制下进行) 读操作(数据输入):I/0设备→内存 写操作(数据输出):内存→I/0设备

5.主要缺点和主要优点 缺点: 实现复杂，需要专门的通道硬件支持 优点: CPU、通道、I/0设备可并行工作，资源利用率很高。

区别

子主题

难点理解: 通道=弱鸡版CPU 通道程序=任务清单

例题

子主题

I/O软件层次结构

图

子主题

每一层会利用其下层提供的服务

用户层软件

设备独立性软件

设备驱动程序

中断处理程序

硬件

用户层软件

实现与用户交互的接口，向上提供方便易用的库函数

设备独立性软件

概念

又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现。

①向上层提供统一的调用接口(如 read/write 系统调用);

②设备的保护

③差错处理

④设备的分配与回收

5.数据缓冲区管理

⑥建立逻辑设备名到物理设备名的映射关系;根据设备类型选择调用相应的驱动程序.

设备独立性软件 设备驱动程序 中断处理程序 属于操作系统内核部分

逻辑设备表(LUT，Logical Unit Table)

子主题

I/0设备被当做 一种特殊的文件

可以用文件名访问设备

操作系统系统可以采用 两种方式管理逻辑设备表(LUT)

第一种方式，整个系统只设置一张LUT这就意味着 所有用户不能使用相同的逻辑设备名， 因此这种方式只适用于单用户操作系统。

第二种方式，为每个用户设置一张LUT， 各个用户使用的逻辑设备名可以重复，适用于多用户操作系统。 系统会在用户登录时为其建立一个用户管理进程， 而LUT就存放在用户管理进程的PCB中。

不同类型(厂商)的I/0设备需要有不同的驱动程序处理

子主题

设备驱动程序

1. 主要负责对硬件设备的具体控制，将上层发出的一系列命令 (如read/write)转化成特定设备“能听得懂”的一系列操作。

2. 设置设备寄存器

3. 检查设备状态

例题

设备寄存器的写命令是在I/O软件什么中完成

设备驱动程序

子主题

中断服务例程(实际上是驱动程序)

中断处理程序

进行中断处理

例题

子主题

 硬件

执行I/0操作，有机械部件、电子部件组成(参考“I/0控制器”小节的视频)

 输入输出应用程序接口

输入/输出应用程序接口

 图

子主题

字符设备接口

get/put 系统调用: 向字符设备读/写一个字符

如:键盘、打印机， 不可“寻址"每次读1个字符

块设备接口

read/write 系统调用: 向块设备的读写指针位置读/写多个字符;

seek 系统调用:修改读写指针位置

如:磁盘，可“寻址” 每次读/写1个块

网络设备接口

网络设备接口，又称“网络套接字(socket)接口

1.socket 系统调用:创建一个网络套接字，需指明网络协议(TCP?UDP?)

2. bind:将套接字绑定到某个本地“端口"

3. connect:将套接字连接到远程地址

4. read/write:从套接字读/写数据

如:网络控制器(网卡)，数据该给谁?

图

子主题

概念:什么是阻塞/非阻塞 I/O?

阻塞I/0

应用程序发出I/0系统调用，进程需转为阻塞态等待 eg:字符设备接口--从键盘读一个字符 get

非阻塞I/0

应用程序发出I/0系统调用，系统调用可迅速返回，进程无需阻塞等待 eg:块设备接口--往磁盘写数据 write

设备驱动程序接口

 图

子主题

操作系统规定好设备驱动程序的接口标准，各厂商必须按要求开发设 备驱动程序

设备独立软件

I/O核心子系统

图

子主题

I/O 调度

子主题

I/0调度:用某种算法确定一个好的顺序来处理各个I/0请求

如:磁盘调度(先来先服务算法、最短寻道优先算法、 SCAN算法、C-SCAN算法、LOOK算法、C-LOOK算法)。 当多个磁盘I/0请求到来时，用某种调度算法确定满足I/0请求的顺序。

同理，打印机等设备也可以用先来先服务算法、 优先级算法、短作业优先等算法来确定I/0调度顺序。

设备保护

子主题

操作系统需要实现文件保护功能，不同的用户对各个文件有不同的访问权限(如:只读、读和写等) 在UNIX系统中，设备被看做是一种特殊的文件，每个设备也会有对应的FCB。 当用户请求访问某个设备时，系统根据FCB中记录的信息来判断该用户是否有相应的访问权限， 以此实现“设备保护”的功能。(参考“文件保护”小节)

 假脱机技术(SPOOLing)

 脱机技术

 图

子主题

外围控制机+更高速的设备--磁带

作用: 缓解设备与CPU的速度矛盾，实现预输入、缓输出

假脱机技术

又叫SPOOLing技术，用软件的方式模拟脱机技术

输入井和输出井--模拟脱机输入/输出时的磁带

输入进程和输出进程--模拟脱机输入/输出时的外围控制机

输入缓冲区和输出缓冲区--内存中的缓冲区，输入、输出时的“中转站"

 图

子主题

共享打印技术

用SPO0Ling技术将独占式的打印机“虚拟“成共享打印机

图

子主题

SPOOLing技术的主要目的

SPOOLing 技术将一台物理设备虚拟为多台逻辑设备， 以减少设备的闲置时间，提高设备的并发度和吞吐量， 因此 SPOOLing 技术的主要目的是提高独占设备的利用率

以空间换时间

SPOOLing 技术需有高速大容量 且可随机存取的外存支持， 通过预输入和缓输出来减少 CPU等待慢速设备的时间， 将独享设备改造成共享设备

 设备分配回收

应考虑的因素

固有属性

独占设备、共享设备、虚拟设备(SPOOLing)

独占设备

 指在一段时间内只允许一个用户（进程）访问的设备

静态分配方式

打印机、磁带机

共享设备

一段时间内允许多个进程同时访问的设备

磁盘

可寻址，可随机

访问保证数据的完整性和一致性

动态分配方式

虚拟设备

虚拟设备（Virtual Device）是指通过软件技术（具体是SPOOLing技术） 将一台物理的独占设备模拟成为多台逻辑上的共享设备， 供多个用户进程同时、高效地使用

分配算法

先来先服务、优先级高者优先、短任务优先等

安全性

安全分配方式

为进程分配一个设备后就将进程阻塞，本次I/0完成后才将进程唤醒，

不安全分配方式

进程发出I/0请求后，系统为其分配I/0设备，进程可继续执行， 之后还可以发出新的I/0请求。只有某个I/0请求得不到满足时才将进程阻塞。

不考虑及时性

静态分配与动态分配

静态分配

进程运行前为其分配全部所需资源，运行结束后归还资源

独占设备

动态分配

进程运行过程中动态申请设备资源

共享设备

设备分配管理中的数据结构

图

子主题

一个通道可控制多个设备控制器， 每个设备控制器可控制多个设备

设备控制表(DCT)

每个设备对应一张DCT，关键字段: 类型/标识符/状态/指向COCT的指针/等待队列指针

 图

子主题

控制器控制表(COCT)

每个控制器对应一张COCT，关键字段:状态/指向CHCT的指针/等待队列指针

 图

子主题

通道控制表(CHCT)channel

每个通道对应一张CHCT，关键字段:状态/等待队列指针

 图

子主题

系统设备表(SDT)

记录整个系统中所有设备的情况，每个设备对应一个表目，关键字段:设备类型/标识符/DCT/驱动程序入口

 图

子主题

设备分配的步骤

1. 根据进程请求的物理设备名查找SDT; 2. 根据SDT找到DCT并分配设备; 3. 根据DCT找到COCT并分配控制器; 4. 根据COCT找到CHCT并分配通道

注:只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/0设备进行数据传送

缺点:用户编程时必须使用“物理设备名"，若换了一个物理设备，则程序无法运行。 若进程请求的物理设备正在使用则即使系统中还有同类型的设备，进程也必须阻塞等待

设备分配步骤的改进

用户编程时使用逻辑设备名申请设备 操作系统负责实现从逻辑设备名到物理设备名的映射(通过LUT)

逻辑设备表的设置问题

整个系统只有一张LUT:各用户所用的逻辑设备名不允许重复

每个用户一张LUT:各个用户的逻辑设备名可重复

图

子主题

①根据进程请求的逻辑设备名査找SDT (注:用户编程时提供的逻辑设备名其实就是“设备类型”

②)查找SDT，找到用户进程指定类型的、并且空闲的设备， 将其分配给该进程。操作系统在逻辑设备表(LUT)中新增一个表项。

例题

子主题

系统为每台设备确定一个编号以便区分和识别设备， 这个确定的编号称为设备的绝对号

缓冲区管理

缓冲区的概念

一般利用内存作为缓冲区

1. 缓解CPU与设备的速度矛盾、 2. 减少对CPU的中断频率、 3. 解决数据粒度不匹配的问题、 4. 提高CPU与I/0设备之间的并行性

1. 缓冲区主要解决输入/输出速度比 CPU 处理的速度慢而造成数据积压的矛盾(缓冲区作用大) 2. 所以当 I/O 花费的时间比 CPU 处理时间短很多时，缓冲区没有必要设置

磁盘缓冲区的主要目的

减少磁盘I/O次数

缓冲区结合预读和滞后写技术 对于具有重复性及阵发性的 I/O 进程改善磁盘 I0 性能很有帮助

单缓冲

 图

子主题

设备一(T)-缓冲区-(M)-工作区-(C)-处理

处理一块数据平均耗时 Max(C, T)+M

分析问题的初始状态:工作区满，缓冲区空

双缓冲

 图

子主题

处理一块数据平均耗时 Max(T,C+M)

分析问题的初始状态:工作区空，一个缓冲区满，另一个缓冲区空

例题

子主题

循环缓冲

 图

子主题

多个缓冲区链接成循环队列，in指针指向第一个空缓冲区，out指针指向第一个满缓冲区

缓冲池

三个队列:空缓冲队列、输入队列、输出队列

四种工作缓冲区

用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区

用于收容输出数据的工作缓冲区、用于提取输出数据的工作缓冲区

图

子主题

缓冲池和SPOOLing假脱机技术

输入/输出缓冲区是在内存中开辟的，因为IO 设备高很多，缓冲池通常在主存中建立U速度比

输入井和输出井是在磁盘上开辟的存储空间

设备驱动程序接口

单位

图

子主题

外存设置

磁盘

磁盘的结构

磁盘、磁道、扇区的概念

磁盘由表面涂有磁性物质的圆形盘片组成

每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区

 图

子主题

如何在磁盘中读/写数据

磁头移动到目标位置，盘片旋转，对应扇区划过磁道才能完成读/写

盘面、柱面的概念

 图

子主题

磁盘有多个盘片“摞”起来，每个盘片有两个盘面

所有盘面中相对位置相同的磁道组成柱面

磁盘的物理地址

(柱面号，盘面号，扇区号)

磁盘的分类

根据磁头是否可移动

图

子主题

固定头磁盘(每个磁道有一个磁头)

移动头磁盘(每个盘面只有一个磁头)

根据盘片是否可更换

 图

子主题

固定盘磁盘

可换盘磁盘

磁盘调度算法

一次磁盘读/写操作需要的时间

寻找时间(寻道时间):启动磁臂移动磁头所花的时间

但是操作系统的磁盘调度算法 会直接影响寻道时间

延迟时间:将目标扇区转到磁头下面所花的时间

传输时间:读/写数据花费的时间

 图

子主题

延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬 件的固有属性，因此操作系统也无法优化延迟时间和传输时间

对磁盘影响最大也是寻道时间，寻道过程为机械运动，时间较长，影响较大。

磁盘调度算法

先来先服务(FCFS)

图

子主题

按访问请求到达的先后顺序进行处理

优点: 公平;如果请求访问的磁道比较集中的话， 算法性能还算过的去

缺点:如果有大量进程竞争使用磁盘， 请求访问的磁道很分散， 则FCFS在性能上很差，寻道时间长

最短寻找时间优先(SSTF)

图

子主题

每次都优先响应距离磁头最近的磁道访问请求

贪心算法的思想，能保证眼前最优，但无法保证总的寻道时间最短

优点: 性能较好，平均寻道时间短

缺点: 可能导致饥饿

扫描算法(电梯算法、SCAN)

 图

子主题

只有磁头移动到最边缘的磁道时才可以改变磁头移动方向

优点:性能较好，平均寻道时间较短，不会产生饥饿现象

缺点:对各个位置磁道的响应频率不平均

上面的图到终点的磁道就停了 没有到0

循环扫描算法(C-SCAN)

 图

子主题

只有磁头朝某个方向移动时才会响应请求， 移动到边缘后立即让磁头返回起点，返回途中不响应任何请求

优点: 比起SCAN 来，对于各个位置磁道的响应频率很平均

缺点: 只有到达最边上的磁道时才能改变磁头移动方向， 事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了: 并且，磁头返回时其实只需要返回到18号磁道即可，不需要返回到最边缘的磁道。 另外，比起SCAN算法来，平均寻道时间更长

低频考点

LOOK 算法

SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即改变磁头方向

 图

子主题

优点: 比起SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向， 使寻道时间进一步缩短

C-LOOK 算法

C-SCAN 算法的改进，只要在磁头移动方向上不再有请求，就立即让磁头返回

 图

子主题

减少延迟时间的方法

原因

磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻， 则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”

交替编号

具体做法: 让编号相邻的扇区在物理上不相邻

原理: 读取完一个扇区后刚读完的扇区需要一段时间处理才可以继续读入下一个扇区

 图

子主题

错位命名

具体做法: 让相邻盘面的扇区编号“错位"

原理: 与"交替编号"的原理相同。“错位命名法"可降低延迟时间

图

子主题

磁盘地址结构的设计

理解为什么要用(柱面号，盘面号，扇区号)的结构

理解为什么不用(盘面号，柱面号，扇区号)的结构

原因:在读取地址连续的磁盘块时，前者更不需要移动磁头

 例题

子主题

磁盘的管理

磁盘初始化

低级格式化/物理格式化: 划分扇区

磁盘分区(C盘、D盘、E盘)

逻辑格式化: 1. 建立文件系统(建立根目录文件、 2. 建立用于存储空间管理的数据结构)。

子主题

子主题

时间顺序

低级格式化 (出厂时) → 分区 → 高级格式化 (每个分区) → 安装操作系统/引导程序 → 系统引导 (每次开机)

逻辑关系

低级格式化也称为物理格式化。它是在硬盘盘片上划分磁道和扇区

分区定义了磁盘的逻辑布局，并创建了系统引导的基石（MBR/GPT）

高级格式化为分区提供了文件存储系统

系统引导是一个过程，它依赖于分区时创建的引导扇区（MBR/PBR） 和高级格式化后安装的操作系统文件

引导块

计算机启动时需要运行初始化程序(自举程序)来完成初始化

ROM中存放很小的自举装入程序(不放完整的是有原因的)

完整的自举程序存放在启动块(即引导块/启动分区)上，启动块位于磁盘的固定位置。 拥有启动分区的磁盘称为启动磁盘或系统磁盘(C:盘)

图

子主题

坏块的管理

简单的磁盘: 逻辑格式化时将坏块标记出来

复杂的磁盘: 磁盘控制器维护一个坏块链，并管理备用扇区

 图

子主题

坏了、无法正常使用的扇区就是“坏块”。 这属于硬件故障，操作系统是无法修复的。 应该将坏块标记出来，以免错误地使用到它

对于简单的磁盘，可以在逻辑格式化时(建立文件系统时)对整个磁盘进行坏块检查， 标明哪些扇区是坏扇区比如:在 FAT表上标明。(在这种方式中，坏块对操作系统不透明)操作系统可见

对于复杂的磁盘，磁盘控制器(磁盘设备内部的一个硬件部件) 会维护一个坏块链表在磁盘出厂前进行低级格式化(物理格式化)时就将坏块链进行初始化。 会保留一些“备用扇区”，用于替换坏块。 这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明

固态硬盘SSD

原理

基于闪存技术 Flash Memory，属于电可擦除ROM，即EEPROM

组成

闪存翻译层

负责翻译逻辑块号，找到对应页(Page)

存储介质：多个闪存芯片(Flash Chip)

每个芯片包含多个块(block)

每个块包含多个页(page)

读写性能特性

闪存是以页(page)为单位读/写

相当于磁盘的“扇区"

以块(block)为单位“擦除"，擦干净的块，其中的每页都可以写一次，读无限次

支持随机访问，系统给定一个逻辑地址，闪存翻译层可通过电路迅速定位到对应的物理地址

读快、写慢。要写的页如果有数据，则不能写入，需要将块内其他页全部复制到一个新的(擦除过的)块中，再写入新的页(包含复制过来的数据)

与机械硬盘相比的特点

SSD读写速度快，随机访问性能高，用电路控制访问位置; 机械硬盘通过移动磁臂旋转磁盘控制访问位置，有寻道时间和旋转延迟

SSD 安静无噪音、耐摔抗震、能耗低、造价更贵

SSD的一个“块"被擦除次数过多(重复写同一个块)可能会坏掉,而机械硬盘的扇区不会因为写的次数太多而坏掉

磨损均衡技术

思想:将“擦除"平均分布在各个块上，以提升使用寿命

动态磨损均衡

写入数据时，优先选择累计擦除次数少的新闪存块

静态磨损均衡

SSD监测并自动进行数据分配、迁移，让老旧的闪存块承担以读 为主的储存任务，让较新的闪存块承担更多的写任务

 图

子主题

核心协作链路

应用程序调用

系统调用接口

设备独立软件

I/O核心系统

设备分配

设备分配 + I/O控制方式

确保设备访问的有序性和效率

缓冲管理

SPOOLing + 缓冲区管理

共同解决速度匹配问题

设备驱动

I/O控制器

物理设备

例题

子主题

 Collect

Get Started

操作系统导论

 Collect

Get Started

现代操作系统

 Collect

Get Started

操作系统

 Collect

Get Started

操作系统





0 条评论

下一页