操作系统

1. 系统概述

#

ref

1.1 基本特征和功能

#

特征:

1. 最基本特征
   1. 并发(同一时间段内发生, 并行时同一时刻发生)
   2. 共享(资源共享, 系统资源可供多个进程共同使用)
      1. 互斥共享 - 一个时间段内只允许一个进程访问该资源
      2. 同时共享 - 如磁盘
2. 其它重要特征
   1. 虚拟
      1. 虚拟处理器 - 时分复用
      2. 虚拟存储器 - 空分复用
   2. 异步(进程的执行可能会中断/继续)

功能:

1. 进程管理
2. 存储器管理
3. 文件管理
4. 设备管理

1.2 接口

#

1. 命令接口 - Shell 命令行解释器
   1. 联机
   2. 脱机
2. 程序接口 - 系统调用(避免用户直接访问操作外部设备)
3. 图形接口(GUI) - windows 图形化操作界面

1.3 运行环境

#

1.3.1 两种状态(内核态/用户态)

#

1. 内核态 - 内核程序运行所处状态
   1. 写时钟, I/O, 关中断, 进程调度
2. 用户态 - 用户程序运行所处状态
   1. 读时钟, 寄存器清零, 压栈, 跳转, trap 指令
3. 微内核 - 将内核中基本功能保留, 其余功能移动到用户态
   1. 优点: 添加新任务不必修改内核, 系统可靠性更高
   2. 缺点: 频繁切换内核态和用户态, 效率降低, 开销大

与之对应的还有两种指令(特权/非特权指令), 以及两类程序
状态存储在 CPU 的 PSW 寄存器中

1.3.2 中断(重点-选择题)

#

中断/异常 - 用户态 => 核心态 的唯一途径, OS 必须提供功能, 通过硬件实现

1. 异常 - 内中断(来自CPU内部)
   1. 自愿中断 - 指令中断(如 trap 陷入指令)
   2. 强迫中断
      1. 硬件故障
      2. 软件中断
2. 中断 - 外中断(来自CPU外部)
   1. 外设请求
   2. 人为干预

中断和程序调用对比:

1.3.3 系统调用(重点-选择题)

#

系统调用 - 操作系统提供给应用程序的唯一接口
系统调用过程(用户态发生, 核心态处理执行):

1. 传递系统调用参数
2. 执行 trap 指令(陷入/访管指令, 在用户态使用)
3. 执行系统调用(内核态)
4. 访问用户态

常见的用户态 => 核心态例子:

1. 系统调用
2. 中断
3. 用户企图执行特权命令

2. 进程和线程(重点)

#

2.1 进程与线程

#

进程是资源分配和拥有的基本单位(线程是独立运行的基本单位)
PCB(进程控制块)是进程存在的唯一标志

2.1.1 进程的状态与转换(重点)

#

进程5种状态(创建/就绪/运行/阻塞/终止)的转换:

2.1.2 进程的控制

#

原语: 操作系统中调用核心层子程序的指令, 原子操作, 不可中断

创建

#

引发事件:

1. 终端用户登录系统
2. 作业调度
3. 系统提供服务
4. 用户程序的应用请求。

过程:

1. 申请PCB(进程标识符PID, 用户标识符UID…)
2. 分配内存
3. 初始化
4. 插入就绪队列

终止

#

引发事件:

1. 正常结束
2. 异常结束,由于发生异常(如存储区越界)而 终止进程

过程:

1. 终止进程
2. 终止子进程
3. 释放资源
4. 删除PCB

阻塞

#

引发事件:

1. 请求系统服务
2. 外界干预,进程应外界请求而终止运行
3. 启动某种操作
4. 新数据尚未到达
5. 无新工作可做

过程:

1. 找到PCB
2. 保护现场
3. 阻塞
4. 插入阻塞队列

唤醒

#

引发事件: 引发阻塞的时间完成

过程:

1. 找到PCB
2. 就绪
3. 插入就绪队列

切换

#

引发事件: 一个进程的阻塞 + 另一个进程的唤醒(切换在调度之后立即进行)

过程:

1. 保存现场
2. 更新PCB
3. 插入相应队列
4. 更新另一个PCB
5. 更新数据结构

2.1.3 进程的通信(重点)

#

进程是分配系统资源的单位(包括内存地址空间), 因此各进程内存地址空间相互独立

共享存储

#

通过增加页表项/段表项即可将共享内存区映射到各个进程的地址空间中

消息传递

#

通过操作系统提供的"发送消息"和"接收消息"原语进行数据交换,分为:

1. 直接通信方式 - 进程之间根据进程ID直接通信
2. 间接通信方式 - 以"信箱"作为中转站进行消息传递

管道通信

#

各进程要互斥地访问管道, 即同一时间只能单向传输
类似缓冲区的设计

2.1.4 进程与线程

#

线程:

1. 用户级线程 - 管理由应用程序完成, OS 意识不到其存在
2. 内核级线程 - 管理由 OS 完成, 应用程序只能看到其接口
   1. 内核级线程才是处理机分配的单位
   2. 并发能力强, 适配多核CPU
   3. 切成切换需要由内核完成, 核心/用户态切换开销大

多内核模型(n个用户级线程对n个内核级线程):

1. 多对一
   1. 优点: 线程管理在用户空间进行, 效率较高
   2. 一个线程使用内核服务时被阻塞, 整个进程都被阻塞
2. 一对一
   1. 优点: 互不影响, 并发能力强
   2. 开销大
3. 多对多

2.2 处理机调度

#

2.2.1 三级调度(重点)

#

1. 高级调度(作业调度) - 外存队列挑选作业放入就绪队列
2. 中级调度(内存调度) - 就绪队列暂不能运行调进程挂起; 可运行时送入就绪队列
3. 低级调度(进程调度) - 将进程从就绪队列送入 cpu
   

   

2.2.3 调度过程

#

调度时机

#

不能调度的时机:

1. 处理中断的过程
2. 进程在 OS 内核临界区
3. 需要屏蔽中断的操作(加锁, 中断现场保护/恢复)

需要调度的时机:

1. 发生引起调度条件切当前进程无法运行
2. 中断处理结束, trap(自陷)指令结束

调度方式

#

1. 抢占式 - 高优进程可以暂停当前执行的进程
2. 非抢占式 - 只能主动放弃资源

进程切换与过程

#

1. 对原来运行进程各种数据的保存
2. 对新的进程各种数据的恢复
   切换开销较大, 因此需要高效的调度算法

2.2.4 调度基本准则(重点-小计算题)

#

也是调度算法评价指标:

1. CPU 利用率 = CPU运行时间/所有作业完成时间
2. 系统吞吐量 = 单位时间CPU完成的工作数
3. 周转时间 = 完成时间-提交时间
4. 带权周转时间 = 周转时间/实际运行时间
5. 等待时间
6. 响应时间

2.2.5 调度算法(重点)

#

1. 先来先服务 FCFS
   1. 长作业有利, 短作业不利
   2. CPU繁忙型有利, I/O 繁忙型不利
2. 短作业优先 SJF
   1. 长作业不利, 饥饿现象
   2. 平均等待时间, 平均周转时间最少
3. 高响应比优先 HRRN
   1. 响应比=(等待时间+要求执行时间)/要求执行时间
   2. 短作业优先基础上,避免长时间等待兼顾了长作业
4. 时间片轮转 RR
   1. 交互型算法,用户可及时干预
5. 优先级调度算法
   1. 具体实现分类:
      1. 抢占式
      2. 非抢占式 - 必须等当前任务执行完毕
   2. 优先级分类:
      1. 静态(nice值)
      2. 动态 - 避免高优先级长时间占用
   3. 一般优先级(与作业长短无关):
      1. 系统进程>用户进程
      2. 交互型>非交互型
      3. I/O>计算
      4. 资源要求低>资源要求高
6. 多级反馈队列调度算法
   1. 是时间片轮转和优先级调度的综合

2.3 进程同步(与互斥)

#

2.3.1 基本概念

#

同步

#

同步 - 直接制约关系, 让各并发进程按要求有序地推进
例如进程 B 依赖进程 A 的处理结果

互斥

#

互斥 - 间接制约关系。临界区的临界资源在同一时刻只能被一个进程访问

互斥的四个部分

#

1. 进入区 - 检查是否可进入临界区
   1. 若可应上锁, 防止其它进程同时进入
2. 临界区 - 访问临界资源
3. 退出区 - 解锁
4. 剩余区 - 其它处理

同步互斥准则

#

为禁止两个进程同时进入临界区, 同步机制准则(常结合软件方法考察):

1. 空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区
2. 忙则等待。当已有进程进入临界区时,其他试图进入临界区的进程必须等待
3. 有限等待。对请求访问的进程,应保证能在有限时间内进入临界区
4. 让权等待。当进程不能进入临界区时, 应立即释放处理器,防止进程忙等待

2.3.2 进程互斥的实现方法

#

软件方式

#

单标志法

#

turn 变量表示允许进入临界区的进程号

设 p1 结束时又有新任务, 即使 P0 空闲也需要等待 P0 执行完才可进入
违背空闲让进

双标志先检查法

#

按图中1234执行, 同时进入临界区, 违背忙则等待

双标志后检查法

#

同上, 可能都无法进入临界区, 违背空闲让进, 有限等待

Peterson 算法

#

最佳

硬件方式

#

中断屏蔽

#

不允许被中断, 自然也不能发生进程切换(危险操作, 只适用于内核)

TestAndSet 指令

#

Swap 指令

#

2.3.3 信号量机制

#

信号量是一个整数计数器, 通常用于表示可用资源数量或许可证的数量
信号量机制: 同步机制
信号量的两个主要操作(PV):

1. P - Wait, 用于请求资源
2. V - Signal, 用于释放资源

程序设计流程:

1. 进入区(申请临界资源), P操作、wait()
2. 临界区(访问临界资源)
3. 退出区(释放临界资源), V操作、signal()
4. 剩余区

整形信号量

#

表示资源数目的整形量
存在"忙等"现象, 违背让权等待原则

记录型信号量(核心重点-大题)

#

除了记录资源数量的整形外, 添加了一个进程链表, 用于链接所有需要等待资源的进程
因此, 进程申请资源失败时会自我阻塞, 不占用 CPU, 符合"让权等待"

后续默认用 semaphore 表示信号量数据类型

信号量的应用(重点)

#

利用信号量机制实现进程互斥

#

利用信号量机制实现同步

#

利用信号是实现前驱关系

#

ref

2.3.4 管程

#

管程: 进程的同步工具, 封装上述复杂的同步操作, 确保每次只有一个进程访问共享资源

管程条件变量的两种操作(以A进程执行时为例):

1. wait() - 阻塞 A 进程
2. signal()
   1. 阻塞队列为空, A 进程继续执行
   2. 阻塞队列非空, 唤醒阻塞队列队头进程, 将 A 放入队尾

2.3.5 经典同步问题(重点)

#

生产者=消费者问题

#

基础 PV 问题

实现互斥的P操作一定要在实现同步的P操作之后
V操作不会导致进程阻塞，因此两个V操作顺序可以交换

读者-写者问题

#

不同之处: 读者进程不会像消费者进程一样将数据清空

每个需要互斥的资源, 其检查赋值必须一气呵成, 此处的 count 也是

解决写线程饥饿的问题, 新增一个 w 互斥信号量, 保证先来先服务

吸烟者问题

#

不同之处: 可生产多种产品的单生产者-多消费者

哲学家进餐问题

#

不同之处: 每个进程需要两个临界资源, 可能出现死锁

避免死锁的策略:

1. 限制最多四人同时进餐
2. 奇数号先拿左边筷子, 偶数号相反; 避免占有一支后等待另一支
3. 左右两只筷子都可以使用才允许抓起筷子(一次锁定两份临界资源)
   

   

2.4 死锁

#

死锁: 多个进程因竞争资源而相互等待

2.4.1 死锁概念

#

死锁的四个必要条件(缺一不可):

1. 互斥条件
   1. 进程要求对所分配的资源(如打印机)进行排他性控制
   2. 此时若有其他进程请求该资源,则请求进程只能等待
2. 不剥夺条件
   1. 进程所获得的资源在未使用完前,不能被其他进程强行夺走
   2. 即只能由获得该资源的进程主动释放
3. 请求并保持条件
   1. 进程已经保持了至少一个资源,但又提出了新的资源请求
   2. 该资源已被其他进程占有,此时请求进程被阻塞
   3. 进程对自己已获得的资源保持不放
4. 循环等待条件
   1. 存在一种进程资源的循环等待链,链中每个进程已获得的资源同时被链中下一个进程所请求
   2. 即存在一个处于等待态的进程集合{P1,P2,…, P},其中$P_i$等待的资源被P1(i= 0,1,…,n-1)占有,P,等待的资源被$P_0$占有

2.4.2 死锁的处理策略(重点)

#

预防

#

即针对四个必要条件进行预防:

1. 破坏互斥 - 不可行
2. 破坏不剥夺 - 请求得不到满足时,必须释放占有资源
3. 破坏请求并保持 - 进程在运行前确保分配到所需所有资源
4. 破坏循环等待 - 顺序分配法

可以确保不死锁, 但会限制用户申请资源的顺序
资源分配策略保守, 宁可资源限制

避免(银行家算法)

#

寻找可能的安全允许顺序, 但需要知道将来的资源需求

检测

#

资源分配策略宽松, 只要允许就分配资源
常考察不发生死锁的最小资源数计算问题

解除

#

1. 资源剥夺法 - 挂起某些死锁进程, 将其资源分配给其他死锁进程
2. 撤销进程法 - 撤销部分甚至全部死锁进程并剥夺其资源
3. 进程回退法 - 进程回退到足以回避死锁的还原点, 进程主动释放资源

3 内存管理(重点)

#

3.1 内存管理概念

#

3.1.1 内存管理的四大任务

#

内存管理: 操作系统对内存的划分和动态分配

内存空间的分配与回收

#

参照内存空间的分配与回收

内存空间的扩充

#

扩充方式: 覆盖/交换/虚拟内存

地址转换

#

进程装入内存:

1. 编译
2. 链接 - 形成逻辑地址
   1. 静态链接 - 提前将模块和库链接成完整的执行程序
   2. 装入时动态链接 - 装入内存时, 边装入边链接
   3. 运行时动态链接 - 程序执行时才链接, 易于修改和共享
3. 装入
   1. 绝对装入 - 编译时产生绝对地址
   2. 静态重定位 - 装入时将逻辑地址转换为物理地址
   3. 动态重定位 - 运行时将逻辑地址转换为物理地址

装入环节实现了地址转换, 即逻辑地址到物理地址的转换(重定位)

存储保护

#

保证逻辑地址不会发生越界错误, 方法:

1. 在CPU中设置一对上/下限寄存器用以检查是否越界
2. 采用重定位寄存器和界地址寄存器进行越界检查
   1. 重定位寄存器(基址寄存器) - 存放进程的起始物理地址
   2. 界地址寄存器(限长寄存器) - 存放进程的最大逻辑地址

3.1.2 覆盖与交换

#

用于在多道程序环境下用来扩充内存
覆盖与交换区别:

1. 覆盖是在同一个程序/进程中发生的
2. 交换在不同的进程中发生的

覆盖

#

由于程序运行时不会一直需要访问所有数据
将内存分为固定区和覆盖区, 活跃的部分常驻在固定区
其余部分按调用关系分段, 即将访问的段放入覆盖区, 其它放在外存
需要调用前, 再将其调入覆盖区, 替换之前的段
打破了一个进程的全部信息装入主存后才能运行的限制

交换

#

换出: 将等待状态的程序从内存移到磁盘(进程在I/O时不能被换出)
换入: 将准备竞争CPU的程序从磁盘移到内存
中级(内存)调度采用的就是交换

3.1.3 内存空间的分配与回收(核心重点)

#

内部碎片 作业内部不能被利用的空间(作业阻塞等导致未充分使用)

外部碎片 系统中未分配给作业的空间(由于太小而无法分配和利用)

3.1.3.1 连续分配管理方式

#

即为用户程序分配一个连续的内存空间

单一连续分配

#

内存被分为系统区和用户区
系统区通常位于内存的低地址部分, 用于存放操作系统
系统区外均为用户区, 用于存放用户进程相关数据
内存中只能有一道用户程序，用户程序独占整个用户区空间

优点：

1. 实现简单；无外部碎片
2. 可以采用覆盖技术扩充内存
3. 不需要采取内存保护
   缺点:
4. 只适用于单用户、单任务的操作系统中
5. 有内部碎片
6. 内存利用率极低

固定分区分配

#

将整个用户空间划分为若干个固定大小的分区
每个分区中只装入一道作业
分区大小可相等(适用多道相同作业)或不等(灵活)
用分区说明表记录分区状态, 包括: 地址, 大小, 是否被分配
是最简单的多道程序存储方法
同单一连续分配: 无外部碎片, 有内部碎片

动态分区分配(重点)

#

也叫可变分区分配, 进程装入内存时, 根据其大小动态建立分区
当很多个空闲分区都能满足需求时, 有以下分配算法:

1. 首次适应 - 选择第一个满足大小的分区
   1. 空闲分区以地址递增的次序链接, 从低地址开始查找
   2. 最简单, 最快, 最好
2. 最佳适应 - 选择容量大小最接近的分区
   1. 空闲分区以容量递增的次序链接, 从小容量分区开始查找
   2. 最容易产生内存碎片
3. 最坏适应(最大适应) - 选择容量最大的分区
   1. 空闲分区以容量递减的次序链接, 直接使用最大的分区
   2. 容易导致后续"大进程"没有足够大的连续空间可用
4. 临近适应(循环首次适应) - 从上次查找结果的位置开始查找的首次适应

采用空闲分区表或者空闲分区链记录内存使用情况
并根据分配算法, 回收内存后对空闲分区链重新排序

3.1.3.2 非连续分配管理方式

#

将应用程序所需内存空间分散分配在内存的各个区域
避免了连续大内存不足的问题, 但需额外空间存储分散区域的索引

根据分区大小是否固定分为:

1. 分页存储管理
   1. 内存分为大小相等的分区, 每个分区是一个页框(块/物理页面)
   2. 进程逻辑地址空间也按页框大小划分, 每个分区为一个页/页面
   3. 操作系统以页框为单位给进程分配内存空间
   4. 进程的每个页面分别放入一个页框中, 即页面页框一一对应
2. 分段存储管理

分页存储管理中, 根据是否要把作业的所有页面装入内存才能运行分为:

1. 基本分页存储管理
2. 请求分页存储管理

基本分页存储管理(核心重点)

#

OS 用页表记录进程中每个(逻辑)页面在(物理)内存中的位置(块号):

1. 页表通常存在 PCB 中
2. 进程的每个页面对应一个页表项
3. 页表字段: 页号 + 块号(页框号)
4. 每个页表项的长度是相同的(重点-计算题)
   1. 页表项占用字节数计算, 以 4GB 内存, 页面大小 4KB 为例
   2. 4GB的内存总共会被分为 $2^{32} / 2^{12} = 2^{20}$ 个内存块
   3. 内存块号的范围应该是 $0 \sim 2^{20} -1$, 即需 20 b(bit)
   4. 即单个页表项最少需要 3B(3 个字节)
   5. 注: 由于逻辑地址是连续的, 页号可以是隐含的(基址+下标)

由逻辑地址得到物理地址(重点):

1. 确定逻辑地址对应的页号
2. 根据页号查页表, 得到物理块号和页内偏移量
3. 物理地址 = 块号 * 块大小 + 页内偏移量
   因此分页逻辑地址结构为: 页号 + 页内偏移量(页内地址)
4. 注意页面偏移量的位数 = 单个页面的长度

基本地址变换结构 - 实现逻辑地址到物理地址的硬件:

1. 系统中设置页表寄存器(PTR)，存放页表在内存中的始址和页表长度
   1. 结合逻辑地址转物理地址的第一步, 还需要判断页号是否越界
2. 进程未执行时，页表的始址和页表长度放在进程控制块(PCB)中
3. 进程被调度时，操作系统内核会把它们放到页表寄存器中

具有快表的地址变换机构(重点)

快表(TLB) 又称联想寄存器(属于cache层级, 不在内存), 用来存放最近访问的页表项的副本，可以加速地址变换的速度(对应内存中的页表常称为慢表)

引入有快表后, 地址的转换过程:

1. 根据逻辑地址查快表, 若命中, 直接访问对应物理地址, 一次访存
2. 若命中, 查找页表(内存), 后续同之前, 两次访存
   1. 注意, 查到页表项后, 应将副本其存入快表(若满需替换)
   2. 基于局部性原理, 快表命中率通常可达到 90% 以上
      

      

单级页表存在的问题:

1. 页表必须连续存放，页表很大时，需要占用很多个连续的页框
   1. 页表项指向的块是离散的, 但页表本身是连续的
2. 整个页表常驻内存，但可能一段时间内只用到几个特定的页面

可参照覆盖和内存空间的离散分配:

1. 将页表进行分组, 每个组正好放入一各物理块(即页大小)
2. 再建立一张页目录表记录页表各分组
   

   

两级页表的两个细节:

基本分段存储管理

#

与"分页"最大区别: 离散分配时所分配地址的基本单位不同(段/块)

段的特征:

1. 按照程序逻辑划分段(例如一个函数为一个段), 每段大小可不一
2. 每个段都有一个段名(短号), 每段从0开始编址
3. 每个段在内存中占据连续空间，但各段之间可以不相邻

因此分段逻辑地址: 段号 + 段内地址(段内偏移量)

• 段号的位数决定了每个进程最多可以分几个段
• 段内地址位数决定了每个段的最大长度是多少

同理也有段表, 段表字段: 段号 + 段长 + 基址

1. 每个段对应一个段表项, 记录其在内存中的起始位置和长度
2. 各个段表项长度相同, 因此段号可以是隐含的，不占存储空间

分段分页的区别:

1. 页是信息的物理单位, 用户不可见; 段是逻辑单位, 用户可见
2. 页长由系统固定统一; 段长由用户影响不一
3. 分段容易产生外部碎片(单个段内要求连续存放)

段页存储管理

#

先分段, 再分页
段表字段: 短号 + 页表长度 + 页表存放块号
页表结构与分页式相同

3.2 虚拟内存管理

#

3.2.1 基本概念

#

传统存储管理方式特征及缺点

#

1. 一次性 - 作业必须一次性全部装入内存后才能开始运行
   1. 大作业无法运行
   2. 多道程序并发度下降
2. 驻留性 - 作业被装入内存后会一直驻留在内存中，直至作业运行结束
   1. 一个时间段内，只需要访问作业的一小部分数据即可正常运行

局部性原理:

#

1. 时间局部性: 当前执行的指令, 不久后可能再次执行
2. 空间局部性: 当前访问的存储单元, 不久后其附近的存储单元可能被访问

虚拟内存定义与特征

#

程序装入时, 即将访问的部分装入内存, 其他部分留在外存, 先执行
序执行过程中访问信息不在内存时, 再将其调入内存
若内存空间不够，将内存中暂时用不到的信息换出到外存

特征:

1. 多次性：作业无需一次性全部装入内存，允许分多次调入内存
2. 对换性：作业运行时无需常驻内存，允许在运行过程中换入换出
3. 虚拟性：逻辑上扩充内存容量，使用户感知内存容量远大于实际容量

虚拟内存的最大容量: 计算机的地址结构(CPU寻址范围)确定, 如32位字节编址最大容量为 $2^{32}B$

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

虚拟内存实现途径

#

由于多次装入的特性(避免空间一直空闲)
虚拟内存的实现需要建立在离散分配的内存管理方式基础上, 分为:

1. 请求分页存储管理
2. 请求分段存储管理
3. 请求段页式存储管理

3.2.2 请求分页管理方式

#

页表机制

#

组成:

1. 基本分页
2. 请求调页
   1. 操作系统需要知道每个页面是否已经调入内存
   2. 如果还没调入，那么也需要知道该页面在外存中存放的位置
3. 页面置换
   1. 当内存空间不够时，要实现页面置换
   2. OS 根据某些指标决定到底换出哪个页面
   3. 若页面修改过, 需要覆盖外存旧数据

因此页表项需要增加字段:

1. 状态位: 标识是否已调入内存
2. 访问字段: 记录最近被访问过几次/上次访问的时间, 供置换算法参考
3. 修改位: 页面调入内存后是否被修改过
4. 外存地址: 页面在外存中的存放位置

缺页中断机构

#

请求分页系统中，要访问页面不在内存时，便产生一个缺页中断
此时缺页的进程阻塞，放入阻塞队列
调页完成后再将其唤醒，放回就绪队列

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项
如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存

属于内部中断, 一条指令期间可以产生多次中断

地址变换机构

#

与基本分页中主要区别:

1. 访问的信息不在内存时，OS 将所需信息从外存调入内存
2. 内存空间不够时，OS 将内存中暂时用不到的信息换出到外存

3.2.3 页面置换算法(重点)

#

内存不够需要进行页面置换时, 决定应该换出哪个页面

最佳置换算法-OPT

#

选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面
保证最低的缺页率, 但无法实现(无法预判页面访问次序)

先进先出置换算法-FIFO

#

淘汰最早进入内存的页面
不考虑使用频率，即使增加了实页数, 多贮存的部分接下来常访问可能性也不一定大
会产生 Belady 异常(进程分配的内存块数增大，缺页次数不减反增)

最近最久未使用-LRU

#

每次淘汰最近最久未使用的页面
每个页面对应的页表项中, 访问字段记录该页面自上次被访问以来所经历的时间

时钟置换算法-CLOCK

#

也称最近未用算法 - NRU
简单的时钟置换算法实现:

1. 每个页面设置一个访问位，内存页面都通过链接指针链接成循环队列
2. 当某页被访问时，其访问位置为1
3. 淘汰页面时，检查页访问位, 0则换出, 1则将其置0继续检查下一个
4. 最多两轮扫描, 一定会有访问位为0的页面

改进型时钟置换算法

#

新增修改位, 如 (1, 1) 代表 (访问过, 修改过):

1. 从当前位置开始扫描到第一个（0, 0）的帧用于替换。本轮扫描 不修改任何标志位
2. 若第一轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。本轮将所有扫描过的帧访问位设为0
3. 若第二轮扫描失败，则重新扫描，查找第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位
4. 若第三轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换

即按照 “访问 < 修改” 的优先级换出

3.2.4 页面分配策略

#

驻留集

#

程序开始执行时读多少页, 太大浪费, 太小频繁缺页

三种策略:

1. 固定分配局部置换
   1. 初始为进程分配一定数量的物理块, 整个运行期间都不改变
   2. 若进程发生缺页, 只允许在自己的内存页面中换出再调入
   3. 很难提前确定分配多少个物理块才算合理
2. 可变分配全局置换
   1. 初始为进程分配一定数量的物理块, OS 维护一个空闲物理块队列
   2. 若进程发生缺页, 从空闲队列取一块分配给进程
      1. 若已无空闲物理块，则可选择一个未锁定的页面换出外存并分配
   3. 存在盲目给进程增加物理块的风险
3. 可变分配局部置换：
   1. 初始为进程分配一定数量的物理块
   2. 若进程发生缺页, 只允许在自己的内存页面中换出再调入
   3. 若进程频繁/很少缺页, 系统适当增加/减少分配
   4. 资源利用率高, 实现复杂

工作集

#

工作集窗口为 n, t 时刻的工作集为该时刻之前访问的 n 个页面

调入页面的时机

#

1. 预调页策略 - 一次调入若干个相邻的页面, 适用于运行前首次调入
2. 请求调页策略 - 运行时缺页调入, (磁盘)I/O开销大

调入页面的出处

#

请求分页系统中, 外存(磁盘)分为:

1. 文件区 - 存放文件, 采用离散分配方式, 读写较慢
2. 对换区 - 存放对换页面, 采用连续分配, 读写较快

从何处调入页面分三种情况:

1. 若对换区足够:
   1. 始终从对换区调入即可
   2. 进程运行前, 将进程相关的数据从文件区复制到对换区
2. 若对换区不足:
   1. 对于不会被修改的数据
      1. 从文件区调入
      2. 换出时不必写回磁盘
   2. 对于可能被修改的部分
      1. 从对换区调入
      2. 换出时需写回磁盘对换区
3. UNIX 方式:
   1. 首次从文件区调入
   2. 换出写回对换区, 下次需要时从对换区调入

抖动

#

抖动指频繁的页面调度(刚刚换出的页面马上又要调入, 刚调入又要调出)
主要原因: 进程频繁访问的页面数量大于其被分配的可用块

地址翻译

#

P191例题讲解

4 文件管理

#

4.1 基础概念

#

文件的组成:

1. 存放的数据
2. 分类和索引信息
3. 访问权限信息

目录也是一种特殊的有结构文件(由记录组成)

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

1. 文件信息保存在目录结构中, 目录结构保存在外存

文件的操作

文件系统的层级结构

#

建议将本章内容都了解后再来以整体视角了解文件系统的层次结构:

4.2 文件的逻辑结构

#

4.2.1 无结构文件(流式文件)

#

文件内部的数据就是一系列二进制流或字符流组成, 如 .txt

4.2.2 有结构文件(重点)

#

由一组相似的记录组成，又称“记录式文件”
根据各条记录记录在逻辑上如何组织, 有以下分类:

顺序文件

#

逻辑上: 文件中的记录一个接一个地顺序排列
物理上:

1. 顺序存储
   1. 定长记录 - 可实现随机存取(位置无需遍历可计算得出)
      1. 串结构
      2. 顺序结构 - 可快速找到关键字对应记录
   2. 可变长记录 - 无法实现随机存取, 只能从第一个记录往后查找
2. 链式存储 - 无法实现随机存取(逻辑上相邻物理上不一定相邻)

按照记录之间顺序的规则, 可分为两种结构:

1. 串结构 - 关键字无关, 通常按存入时间决定顺序
2. 顺序结构 - 按关键字顺序

索引文件

#

针对可变长记录文件顺序查找低效的问题, 提出索引文件
建立一张索引表以加快文件检索速度(因此索引表本身是定长记录的顺序文件)

索引表每条记录对应一个索引项, 索引项字段组成:

1. 索引号 - 唯一标识(如关键字)
2. 长度
3. 指针 - 指向文件地址

索引顺序文件

#

针对索引表过大和空间浪费(如文件8B, 索引表一项32B)的问题 不再逐个索引, 一组记录对应一个索引表项(例如按首字母分组)

索引项字段组成:

1. 键 - 分组特征值
2. 逻辑地址 - 指向每个组中第一个文件的地址

直接文件/散列文件(Hash File)

#

记录的键值通过hash函数转换后直接生成物理地址
专为搜索优化的结构, 存在hash冲突问题

4.3 文件目录

#

4.3.1 目录实现

#

目录结构包含文件的各属性, 便于管理, 每条记录即文件控制块(FCB)
FCB 文件控制块包含:

1. 文件控制块
   1. 基本信息 - 如文件名, 物理位置/结构, 逻辑结构等
   2. 存取控制信息 - 如文件存取权限
   3. 使用信息 - 如创建/修改时间
2. 索引节点(i节点) - 由于FCB过大, 将文件名和其它描述信息分开
   1. 易于检索(按文件名查找)

由此, 目录项组成:

1. 文件名
2. 指向文件 i 节点的指针

4.3.2 文件目录结构(重点)

#

单级目录

#

整个文件系统一个目录表, 一个列表项(FCB)对应一个文件
因此不支持重名, 不适合多用户系统

两级目录

#

分为主目录和用户文件目录两级
主目录记录记录用户名及相应用户文件目录的位置
实现用户级隔离, 但仍不够灵活

多级目录

#

也称为树形目录, 各级目录之间用 / 分隔, 如 C/Users/xx

无环图目录结构

#

为了解决树形目录不利于共享的问题
在其基础上增加了指向同一节点的有向边, 是整个目录构成有向无环图
即一个文件可以被多个目录多引用:

1. 其中一个目录删除该文件, 实则将共享计数器 -1
2. 计数器为 0 时, 才删除该文件

4.4 文件实现-文件的物理结构(非空闲块管理)

#

即实际上在外存(磁盘)的文件存储结构

4.4.1 连续文件(连续分配)

#

文件目录结构: 文件名, 长度l, 起始块号n
那么即在磁盘中第n块开始到 n+l-1 块为文件的内容
支持顺序访问(遍历)和随机访问, 不利于文件长度动态增加, 容易产生碎片

4.4.1 索引文件(索引分配)

#

离散分配, 消除外部碎片且易于动态调整大小

隐式链接

#

每个块都有指向下个块的指针, 通过起始块号遍历即可读取文件

只能顺序访问, 指针页会消耗存储空间, 有内部碎片

显式连接

#

将存放在块中的指针提取出来组成文件分配表(FAT), 存放于内存中

支持随机访问, 提升速度, 且显著减少了访问磁盘次数

4.4.1 索引顺序文件(索引顺序分配)

#

把每个文件所有块号集中存放, 构成了索引块(索引块又可以继续嵌套)
文件目录只需存储文件名和根索引块的地址
由于索引块大小与文件大小相关, 索引块的大小就成了一个问题:

1. 链接方案 - 即索引块离散存放, 块之间指针链接
2. 多层索引 - 索引块内条目继续指向索引
3. 混合索引(重点) - 既有直接索引, 也有多层索引

4.5 文件实现-文件存储空间管理(空闲块管理)

#

即对空闲块的组织、分配、回收

4.5.1 空闲表法

#

适用于连续分配的物理结构, 用表格记录哪些块是空闲块
其中每一项包括: 序号, 第一个空闲块号, 空闲块数
块的分配与回收方式与内存管理中的动态分区分配类似

4.5.2 空闲链表法

#

适用于离散分配的物理结构, 将所有空闲盘块拉成一条空闲链
根据空闲链基本单位的不同, 可分为:

1. 空闲盘块链 - 以块为基本单位
2. 空闲盘区链 - 一个盘区可包含若干块

分配: 从链头依次摘下指定数量块, 并修改空闲链链头指针
回收: 回收的块依次挂到链尾, 并修改空闲链链尾指针

4.5.3 位视图法(重点)

#

表格中每个单元格代表一个块, 其中的值表示块的状态(0-空闲;1-已分配)
若未特殊指明, 位视图行列号从 1 开始编号

4.5.4 成组链接法

#

类似索引顺序文件的思路?
Todo: Unix知识, 了解即可

4.6 其他操作系统对于文件提供的功能

#

4.6.1 基本操作

#

1. 创建 - 先分配空间, 目录中创建条目
2. 读 - 读文件的内容
3. 写
4. 重定位
5. 删除
6. 截断
7. 打开 - 读写之前, 需要先打开文件, 读的FCB(文件控制块)
8. 关闭 - 读写之后, 需要关闭文件

4.6.2 共享

#

基于索引节点的共享方式-硬链接

#

引用文件先指向同一个索引节点
索引节点内维护了共享计数器和文件地址

基于符号链的共享方式-软链接

#

引用文件为链接文件(类似windows快捷方式), 其中包含源文件的路径

例题(答案见alt):

解析1:

1. 建立符号链接时, 引用计数值直接复制
   1. 删除文件时删除操作对于符号链接是不可见的
   2. 后续再通过符号链接访问时, 发现文件不存在, 直接删除符号链接
2. 建立硬链接时， 引用计数值加1
   1. 硬链接则不可以直接删除，引用计数值减1
   2. 若值不为O, 则不能删除此文件, 因为还有其他硬链接指向此文件
3. 当建立F2时，F1和F2的引用计数值都为 1
4. 当再建立F3时，F1和F3的引用计数值就都变成了 2
5. 当后来删除F1时，F3的引用计数值为2-1 = 1, F2的引用计数值一直不变

4.6.3 保护

#

4.6.3.1 文件备份

#

4.6.3.2 访问备份

#

口令

#

口令存在文件系统内部(FCB或索引节点), 不够安全

加密

#

对文件系统加密, 访问时需要密钥, 但加/解密会增加读写时间

访问控制(ACL)

#

用表格记录各个用户对各个文件可以做的各类操作(读写删)的权限

4.7 磁盘管理

#

4.7.1 基础概念

#

磁盘结构:

磁盘地址: 柱面号(投影即磁道)-盘面号-扇区号
簇: 即最小分配单位, 一个文件只能占有整数个簇

磁盘读写时间(重点) = 寻道时间 + 旋转延迟时间 + 传输时间

1. 寻道时间 - 磁头移动到指定磁道
   1. 寻道时磁头移动, 此后为磁盘转动
2. 旋转延迟时间 - 定位本磁道特定扇区的时间
   1. 平均旋转半圈能定位到扇区, 因此所花时间为转速(rpm)的 1/2
3. 传输时间 = $\frac{传输字节数}{转速 * 单个磁道的字节数}$

例题:

4.7.2 磁盘调度算法

#

多个请求同时访问磁盘时如何调度

先来先服务-FCFS

#

根据访问磁盘先后顺序调度
简单公平, 但特定场景下仍需优化(如1-99-2-98的块顺序访问)

最短寻道时间算法-SSTF

#

优先处理距离当前所在磁道距离最近的磁道, 使每次寻找时间最短
可能产生饥饿现象, 距离较远处请求长时间得不到响应

扫描(电梯调度)-SCAN

#

在最短寻道时间优先的基础上, 规定了磁头运动方向
只在本次扫描方向选择最近的磁道, 类似电梯的调度
对最近扫描过的磁道不公平, 局部性访问不如 FCFS 和 SSTF

循环扫描-C-SCAN

#

扫描的基础上, 扫描至首部后, 不立即回扫
直接回到尾部, 始终按同一方向扫描

还可以更进一步优化: 以请求的范围为起点终点, 缩小不必要的扫描区间
采用这种范围的 (C-)SCAN 算法称为 (C-)Look 算法
无特别说明时, 也默认采用此种范围

例题:

4.7.3 读写时间优化

#

减少延迟时间

#

1. 扇区错位交替编号
   1. 以连续读 0-1-2 扇区为例
   2. 磁盘旋转定位到0扇区后, 耗时 0.1ms 读取完该扇区
   3. 此时磁盘已经转了 n 圈, 磁头位于第 3 扇区
   4. 此时需要重新旋转定位到 1 扇区
   5. 若交替错位编号, 理想时读取完0扇区后, 磁头正好位于1扇区
2. 盘面错位命名(原理同上)

改善磁盘I/O性能

#

1. 重排 I/O 请求次序
2. 预读和滞留写
3. 优化文件物理分布

4.7.4 磁盘管理

#

磁盘初始化

#

1. 低级格式化 - 物理分区, 将磁盘划分为若干扇区
2. 逻辑格式化 - 逻辑分区, 将磁盘划分为若干柱面组成的分区(如C盘)

引导块

#

即 BIOS 所在磁盘块
仅小部分引导程序位于 ROM, 完整的初始化程序保存在磁盘的启动块上
它位于磁盘的固定位置, 拥有启动分区的磁盘也成为系统磁盘

坏块

#

磁盘属精密部件容易损坏, 对于损坏的扇区:

1. 简单磁盘场景下, FAT 表中标明, 程序不去使用即可
2. 复杂磁盘场景, 会维护一个磁盘坏块链表, 避免使用
   1. 低级格式化过程中还会保留一些备用块, 用于逻辑替代坏块

5 I/O 管理

#

5.1 概述

#

5.1.1 I/O 设备

#

按使用特性分类:

1. 人机交互类外部设备(键盘鼠标)
2. 存储设备(磁盘)
3. 网络通信设备(网卡)

按速度分类:

1. 低速(键盘鼠标)
2. 中速(打印机)
3. 高速(磁盘)

按信息交换单位分类:

1. 块设备(磁盘)
2. 字符设备(打印机)

5.1.2 I/O 控制方式(重点)

#

主要在计算机组成原理中考察, 这里仅简单介绍

程序直接控制方式(程序查询)

#

中断驱动方式

#

DMA方式

#

通道控制方式

#

5.1.3 I/O 子系统的层次结构

#

从上到下依次为(每一层利用其下层封装的某些功能):

1. 用户层软件 - 通过系统调用请求内核服务
2. I/O 核心子系统(内核部分)
   1. 设备独立性软件(设备硬件无关部分, 也叫设备无关软件)
      1. 统一接口
      2. 设备保护(如权限)
      3. 容错处理
      4. 设备的分配与回收
      5. 数据缓冲区管理 - 屏蔽交换单位和传输速率差异
      6. 维护逻辑设备名到物理设备名映射, 选择对应驱动
   2. 设备驱动程序(设备硬件部分)
   3. 中断处理程序
3. 硬件

5.2 I/O 核心子系统

#

对不同功能/速度的 I/O 设备进行控制的方法

5.2.1 I/O 调度

#

为设备维护一个请求队列实现调度
如磁盘调度算法就是 I/O 调度的一种

5.2.2 高速缓存与缓冲区

#

高速缓存

#

类似于 CPU 的 Cache, 不过位于内存和磁盘之间
逻辑上属于磁盘, 物理上为内存中的盘块, 内存中可分两种情况:

1. 开辟单独空间, 大小固定
2. 利用未使用的内存空间作为缓冲池, 供请求分页系统和磁盘I/O共享

缓冲区(重点)

#

作用: 缓和速率/数据粒度不匹配的矛盾; 降低中断频率; 主要利用内存作为缓冲区(硬件缓冲区如快表成本高, 仅高速场景适用)

读/写(传出/冲入)特点:

1. 缓冲区非空时, 不能写入, 只能读出
2. 缓冲区为空, 可以写入, 但必须写满后, 才能读出

单缓冲(重点-计算题)

#

周期计算: 假定一个初始状态, 下次到达同样状态需要的时间
没有特别说明时, 一个缓冲区的大小就是一个块
T-外部设备输入时间, M-传送时间, C-CPU处理时间

双缓冲(重点-计算题)

#

相比于单缓冲, 还可实现双向传输

循环缓冲

#

缓冲池

#

将多个缓冲区封装

5.2.3 设备分配与回收

#

设备分配时应考虑的因素

#

1. 设备的固有属性
   1. 独占设备 - 一个时段只能分配给一个进程(如打印机)
   2. 共享设备 - 如磁盘(宏观上共享, 微观上交替使用)
   3. 虚拟设备 - 将独占设备虚拟化为虚拟共享设备
2. 设备分配算法(先来先/优先级高优先/短任务优先..)
3. 设备分配中的安全性(关联死锁)
   1. 安全分配
      1. 为进程分配一个设备后就将进程阻塞
      2. 本次I/O完成后才将进程唤醒
   2. 不安全分配
      1. 进程发出I/O请求后, 系统为其分配I/O设备
      2. 进程可继续执行，之后还可以发出新的I/O请求
      3. 只有某个I/O请求得不到满足时才将进程阻塞
4. 分配方式:
   1. 静态分配 - 进程运行前为其分配全部所需资源
   2. 动态分配 - 进程运行过程中动态申请设备资源

分配中的数据结构(重点)

#

“设备、控制器、通道”之间的关系:

其中每个层级都有自己的控制表, 从底层往上依次有:

设备控制表-DCT

#

设备层级表，用于记录设备情况, 包括字段:

1. 设备类型 - 打印机/键盘
2. 设备标识符 - 唯一标识
3. 设备状态 - 忙碌/空闲/故障
4. 指向控制器表的指针 - 指向控制该设备的控制器
5. 重复执行次数或时间 - 重复执行多次I/O操作后仍不成功, 才判定失败
6. 设备队列的队首指针 - 指向正在等待该设备的进程(PCB)队列

控制器控制表-COCT

#

控制器层级表, 操作系统根据其对控制器进行操作和管理

1. 控制器标识符
2. 控制器状态
3. 指向通道表的指针 - 指向控制该控制器的通道
4. 控制器队列的队首指针
5. 控制器队列的队尾指针

通道控制表-CHCT

#

通道级控制表, 操作系统根据其对控制器进行操作和管理

1. 通道标识符
2. 通道状态
3. 与通道连接的控制器表首址 - 关联其管理的所有控制器
4. 通道队列的队首指针
5. 通道队列的队尾指针

系统设备表-SDT

#

系统级总表, 记录了系统中全部设备的情况，每个设备对应一个条记录
包括其基础信息, 对应的控制表DCT, 驱动程序入口等

设备分配的步骤

#

1. 根据物理设备名(设备标识符)在 SDT 查找对应项
2. 根据 SDT 记录找到 DCT
   1. 若设备忙碌则将进程PCB挂到设备等待队列中
   2. 不忙碌则将设备分配给进程
3. 根据DCT找到COCT
   1. 若控制器忙碌则将进程PCB挂到控制器等待队列中
   2. 不忙碌则将控制器分配给进程
4. 根据COCT找到CHCT, 同上

改进思路: 新增逻辑设备表(LUT), 建立了逻辑设备名与物理设备名之间的 映射关系

5.2.4 SPOOLing - 假脱机(重点)

#

脱机 脱离主机控制进行的输入/输出操作

输入:

1. 输入设备 => 输入缓冲 => 输入井
2. CPU 需要数据时, 输入井 => 内存
   输出:
3. 内存 => 输入井
4. 输出设备空闲时, 输出井 => 输出缓冲 => 输出设备

通过软件方式, 把一台物理设备虚拟成逻辑上的多台(多个输入输出井)
每个用户进程都觉得自己在独占一台设备

5.2.5 设备保护与差错处理

#