2024 操作系统期末复习
#

Tongji University. 2024/12/28
Author: Hyoung Yan

本文框架
#

外设管理
#

外设管理，文件管理 Unix V6++源代码不用看。操作流程方面，特别细节的地方不用看。比如，要掌握核心数据结构，磁盘高速缓存池。借助缓存的读写操作，缓存块互斥使用的过程，缓存队列的变化。

外设基础概念
#

CPU 访问内存和访问外设是不一样的
- 内存中的信息每个字节有物理地址。以字节为单位随机访问。访问方式：CPU 将物理地址放在地址总线上，直接访问。
- 外设中的信息没有地址，不能直接访问，需要使用特殊的方式（in、out 指令或内存映射），先将外设中的数据取入内存或寄存器，再进行访问。外设中的字节 不能随机访问
  - 键盘、网络输入信息是流式的，读完一个字节才能读下个字节
  - 硬盘中的信息按扇区组织，扇区 512 字节，全读出来或者被新数据块覆盖。

计算机与外设的交互
外设一次执行一条 IO 命令，完成或失败后，CPU 才能发下条命令。
- 读操作 I：外设转换好的数据放在数据缓存中，供计算机读取
- 写操作 O：计算机将数据放在数据缓存中，外设将其中的数据转化成物理信号向外界输出

外设控制器的寄存器（端口），以磁盘为例
CPU 写命令端口向外设发 IO 命令
- 读命令 out 0x00000003, comPort
- 写命令 out 0x00000001, comPort
CPU 读状态端口（in 指令）获取外设状态
- busy 标志为 1，IO 命令执行中，CPU 暂停指令发送，直到 busy 位为 0
- done 标志为 1，IO 命令执行完毕，CPU 可以读取数据
- error 标志为 1，IO 命令执行出错，CPU 可以读取错误信息
CPU 读数据端口取数据缓存中的数据（外设的输入数据）；写数据端口向数据缓存中写数据（外设的输出数据）

三种外设控制方式
- 程序直接控制 IO 方式 1（忙等，读）
  - CPU 承担全部 IO 事务：忙等外设空闲、IO 完成，计算和 IO 无法并行。
  - CPU 只能忙等一个外设，整个系统 IO 效率低下，多个外设无法并行工作。
- 程序直接控制 IO 方式 2（轮询 polling）程序在合适的时间点主动查看外设状态（发出请求时，设备忙，离开；IO 未完成，离开），计算和 IO 能够并行，多个外设可以并行，但 CPU 仍然需要承担所有的外设事务。
- 中断驱动的 IO 方式
  - 中断是 IO 完成信号。CPU 无需忙等或轮询 IO 操作。计算和 IO 可以并行。不同的外设，IO 也可以并行。
  - 数据块从外设数据缓存复制到内存的工作由 CPU 完成。所以，中断驱动的 IO 方式只适合键盘、鼠标等数据缓存很小的外设
  - 在中断驱动的 I/O 方式中，外设的操作（如数据输入输出）不会像轮询（Polling）那样周期性地检查外设的状态，而是 由外设主动发出中断信号，通知操作系统有需要处理的任务。
- DMA 方式（磁盘、网络、GPU…）
  数据就绪于外设数据缓存后，外设控制器向 DMA 控制器发中断信号 DMA 控制器循环，盗取主存周期，把数据缓存中的数据送入内存，一次传送一个字。这一步会循环直至内存得到数据缓存中的所有数据所有数据传送完毕后，DMA 控制器向 CPU 发中断信号。 终端处理程序不复制数据，CPU 完全不参与数据传输

缓存
#

只考磁盘的块设备缓存，字符设备不考，把复习题中的状态图看懂，识别出 IO 请求队列，自由缓存队列磁臂调度算法，磁盘访问时间，计算所在磁道

内存中为每个外设配缓存，暂存外设 IO 数据；缓存在 核心空间，Unix v6++中，缓存在内核数据段。

块设备（存储设备）用于信息存储，例如硬盘、软盘、光盘等，数据存储以数据块为单位，缓存是磁盘高速缓存池，可重用的字符块集合。
UNIX V6++，缓存块 512 字节，同步磁盘上的 1 个扇区。缓存块中存放的那个数据块所有 进程共享，互斥访问。用前上锁，用后解锁。

借助缓存的读写操作
- 写入数据量不足一个数据块，先读后写 buffer[offset] = a
- 写入一整块，无需先读 buffer = 数组a
- 内核会在合适时机，将缓存中的数据块写回磁盘（持久化操作）；什么时候？最晚，关机时，需要把新数据写回磁盘。装新数据的是 脏缓存块。写回磁盘前，如果断电，磁盘会丢数据。

性能分析

用户空间 IO 的使用场合

Unix V6++的磁盘高速缓冲池
缓存控制块：m_Buf [i] 是 Buffer [i] 的控制块
- b_dev：磁盘号
- b_blkno：扇区号
- b_wcount：IO 参数，传送字节数
- b_addr：缓存块首地址
- b_flags：缓存块状态
- b_error：错误码
- b_resid：IO 错误时剩余字节数
缓存管理：进程 随机读写 缓存池中的数据（任意数据块，从任意偏移量开始的任意字节）
- 新请求放队尾，前一个 IO 请求完成的时候启动下一个 IO 请求
- 如果仅考虑读操作，IO 子系统 FIFS 地为系统提供缓存不命中的数据块。
- 读是同步请求，影响 IO 系统响应速度，优先级高。
- 脏缓存块需要写回磁盘，防止数据丢失。写操作是异步的，优先级低。
- Unix V6 写操作执行时机：
  - 脏缓存块分配用来装新数据块时写回磁盘。
  - 每 30s 执行一次 update 程序，将所有脏缓存块写回磁盘。

LRU 的自由缓存队列

Unix 的外设和缓存管理所有磁盘共用磁盘高速缓冲池，每张磁盘有自己私有的设备缓存队列和 IO 请求队列。

外设管理和块设备管理

块设备开关表 bdevsw 管理所有块设备，每一个元素管理一种块设备
字符设备开关表 cdevsw 管理所有终端。每个元素管理一种终端

class BlockDevice
{
public:
    // 设备驱动
    virtual int Open(short dev, int mode);
    virtual int Close(short dev, int mode);
    virtual int Strategy(Buf* bp); // 执行IO操作
    virtual void Start(); // 向磁盘发IO命令
public:// n，同类磁盘的数量
    Devtab* d_tab[n]; // 块设备表
};

class Devtab // 块设备表
{
public:
    int d_active;// 磁盘忙，IO请求队列非空
    int d_errcnt;// 队首IO操作，出错次数
    Buf* b_forw; // 设备缓存队列队首
    Buf* b_back;
    Buf* d_actf; // IO请求队列队首
    Buf* d_actl;
};

主硬盘。设备号 0，0。管理硬盘的内核对象：g_ATADevice

ATA 硬盘驱动程序
1. 编程 DMA 控制器：设置内存物理地址，数据传输量
  写 PRD 表。PRD 表，最多 10 项。每一项是一个 PRD（Physical Region Descriptor，物理内存区描述符），管理 DMA 操作访问的一块连续内存区域。
2. 编程磁盘控制器：设置需要 IO 的磁盘扇区号，扇区数
  - 字节分解：bp-> b_blkno 是一个 32 位的整数，需要拆解为 4 个字节。每个字节包含 8 位，因此通过移位操作可以提取每个字节的具体值。
  - 控制端口：IOPort:: OutByte 函数每次只能发送一个字节（8 位数据）。为了将 32 位的数据分解为多个字节，并通过多个端口传输，需要使用移位操作获取每个字节。
3. 向磁盘控制器和 DMA 控制器发 IO 命令
4. 磁盘中断处理程序 ATADriver::ATAHandler

同步读
- bp = Getblk(dev,blkno) 申请使用缓存池中的数据块
- Brelse(Buf* bp) 释放数据块的使用权

异步写
数据写入缓存池后，解锁缓存块，写操作完毕。数据块可供其它进程使用。需要注意的技术细节：
- 如果写入磁盘数据块的数据量不足 512 字节。先读后写，保护磁盘数据块中新数据覆盖不到的旧数据。
- 数据块写满时刷回磁盘。这是假定进程会顺序写磁盘数据，数据块写至底部不再有重用价值，异步写回磁盘。
  - 若写不满，打脏标识、解锁缓存块，写操作完毕。

总结 Unix V6++外设管理模块和缓存管理模块

IO 性能优化（机械硬盘）
#

机械硬盘（等速圆周运转的设备）
- 每个盘面上有许多同心磁道，用于存储信息，从外至内编号为 0，1，2，3 等。
- 所有盘面上 相同编号的磁道组成一个柱面，柱面号即为磁道号。
- 每个磁道被划分为多个等圆心角的圆弧，每个圆弧为一个扇区，编号为 0，1，2，3 等。
- 每个磁盘有上下两个盘面，每个盘面配有一个读写磁头，磁头号，磁头编号为 0，1，2，3 等。
磁盘的信息存储和访问单位为扇区，目前的技术标准是每个扇区存放 512 字节。扇区的物理地址由柱面号、磁头号和扇区号组成。通过序列化可以得到扇区的逻辑地址。

硬盘访问耗时：从 CPU 写命令寄存器至 → 数据块（512 字节）进硬盘控制器数据缓存
- 寻道时间（seek time）：磁头从当前柱面移动到目标柱面的时间。平均寻道时间小于 10ms。
- 旋转延时（Rotational delay）：磁头到达目标柱面（磁道）后，等待欲访问扇区转到磁头之下。平均旋转延时为磁盘旋转一周所需时间 T 的 1/2。
- 数据传输时间（Data transfer）：磁头走过目标扇区，期间读扇区内容至硬盘数据缓存。若每个磁道包含 N 个扇区。数据传输时间为：T/N。

磁盘 IO 性能优化
1. 磁臂调度算法优化寻道时间
  - FIFO（FIFS）
  - SSTF（Shortest Service Time First）
  - SCAN（电梯调度算法）
    算法性能比较
    - SSTF 性能较好，但可能出现 被饿死的 IO 请求。
    - SCAN 和 C-SCAN 理论上不会饿死 IO 请求，但是会出现“磁臂粘着”（Arm stickiness）现象。指：一个或几个进程对某个柱面密集访问，反复读写其中的磁道，导致磁臂停留此处不动，其余进程针对其它柱面的 IO 请求会长期得不到处理。
    - 解决方法：设置多个磁盘 IO 请求集合
2. 优化旋转延迟（硬件）
3. 考虑数据定位开销，优化文件访问速度：文件在磁盘上尽量连续存放。swap 分区上的进程图像一定要连续存放。
4. 预读技术

复习重点
#

说明操作系统进程设备管理的初衷？因为很麻烦，所以访问外设特别慢。计算机系统在设计时需要有效解决 CPU 访问内存和外设信息不一致的问题，提高系统的整体性能和响应速度。

设备管理中，I/O 软件的组成？什么是设备驱动程序？其主要完成什么功能？介绍 I/O 管理的流程。

I/O 硬件技术中，数据传输技术有那些？分别介绍？并说明中断技术和 DMA 技术的区别与联系？

进程通信
#

（1）读者、写者公平的解，不要求掌握（2）复习资料里，明确写明不要求掌握的，考前肯定不需要看。（3）银行家算法，资源释放算法不要求能够写出来。银行家算法，Dijstra 1965 年提出。算法的缺点（1）每次资源分配时实施，比较耗时（2）保守。进程提出的资源需求量很可能大于需要量。并且算法假定任何进程均可能随时提出资源申请（3）必需事先知道每个进程的最大资源需求量，工程上很难办到，所以这是一个理论上的算法。数据库系统写操作日志、不预防死锁。发现死锁之后（1）重启（2）恢复最近检查点，回放其后所有日志。嗜眠理发师，PPT part 5 进程通信 2 个
银行家算法是死锁避免算法预读不考

可执行存储器是用来存放进程图像的存储单元，包括内存和 盘交换区。
- 内存中的进程图像可以执行，因为每个单元都有物理地址
- 盘交换区中的图像不可执行，运行前必须要为其分配内存
- 内存中的进程 SLOAD = 1，盘交换区中的进程 SLOAD = 0
可执行存储器的使用状态
- 可执行存储器的使用状态 RunIn，内存无法容纳，RunOut，内存可以容纳
- 进程在内存或盘交换区的驻留时长 Process 结构中设置 p_time 字段
- 设置 0#进程负责进程换入任务

互斥、同步、信号量
#

并发访问时，共享变量的值为什么会出错?(单核)
现运行的应用程序 PA 执行完每条指令后，可能因为响应中断放弃 CPU。
- 下台时，保存所有用户态寄存器。
- 被调度、再次运行时，恢复上次保存的用户态寄存器。
- 若某寄存器存有共享变量的更新，放弃 CPU 时，其它进程看不到更新，会读到过时的旧值。再者，若放弃 CPU 时段，其它进程 PB 有更新该变量，待 PA 再次上台，恢复寄存器时会覆盖 PB 对共享变量的更新。变量的值就会出错。

怎样保证共享变量的值不出错？
- 上锁，保证更新共享变量是 原子操作。上例：counter++，一次完成。
- 并发进程互斥访问共享变量。用前上锁，用后解锁。访问期间，禁止其它进程的并发访问请求。

互斥、临界资源、临界区
- 互斥：一次只允许一个进程使用。
- 需要互斥保护的叫做临界资源，包括共享变量（数据结构）和计算机系统中所有的外部设备。
- 临界区是访问共享变量的那段代码。

锁的实现
互斥机制应遵循的原则（假设，进程 PA 需要访问共享资源 R）
- 空闲让进：R 空闲，可以使用
- 忙则等待：R 有进程用，等
- 有限等待：不可以等太久
- 让权等待：若要等待，入睡放弃 CPU
- （睡眠锁，适用于临界区很长或临界区内进程有可能入睡的情况）
1. 软件实现的锁
2. 关中断
  - 没有中断，就没有调度。
  - 内核可以用关中断的方法实现原子操作。
3. 应用程序可以使用的锁（硬件）

信号量 semaphore
现代操作系统为应用程序提供的同步和互斥工具
信号量的用法：
- 为共享资源 R 配一个信号量，用来描述资源使用状态 semaphore semphoreR;
- 进程访问共享资源前，执行 P 操作，同步等待资源访问权限。
- 访问结束后，执行 V 操作，释放资源访问权限、唤醒等待使用资源的另一个进程

用信号量实现的互斥锁

互斥信号量初值为 1，又叫 互斥锁。

int count = 0 ;
semaphore mutex ； //保护共享变量 count
mutex.value = 1 ;

同步同步表现为并发系统中，经常需要：
- 观察系统状态，确定自己是不是可以继续前进
- 修正系统状态，维护系统咋混给他一致性实施同步的位置叫做 同步点
用信号量实施同步：设置同步信号量，维护系统状态，在同步点上：
- 进程检测、更新系统状态，识别共享资源使用状态，必要时入睡、同步等待访问权限。核心是原子操作 P。
- 资源访问结束后，进程修正系统状态，释放资源访问权限、唤醒等待使用资源的其它进程。核心是原子操作 V。

经典 IPC 问题 1 (InterProcess Communication)
#

引例一：吃水果

引例二：消息队列（多客户机、单服务器、无界缓存）

生产者、消费者问题
死锁：并发系统中，因资源管理不当导致的进程彼此等待，均无法前进的现象。
产生死锁的情形

读者/写者问题
- 共享变量需要互斥访问，但是读操作是可以并发的，允许读操作并发可以提高并发系统的效率。
- 读操作，不会改变共享变量的值
- 写操作，改变共享变量的值，两种写操作：更新和赋值
1. 状态分析
  - 写操作必须互斥，不能与其他操作并发，用一个互斥信号量就能搞定
  - 读操作可以和读操作并发，不能与写操作并发，实现上，我们需要一个读者计数器
    - 读者数量非 0 时，新的读操作可以并发，否则必需与写操作互斥
    - 细节：读者计数器是一个共享变量，需要一个互斥信号量予以保护
2. 读者有优先权的解决方案
  存在的问题：饿死写进程
3. 写进程优先的解决方案
4. 例子

经典 IPC 问题 2 & 死锁
#

嗜眠理发师
#

信号量的局限性，快餐店问题
嗜眠理发师问题

信号量的局限性
原始设计问题 seat 信号量的值表示空座位的数量，消费者每次进入时都会调用 p(seat)，如果座位满了（信号量为 0），进程会被阻塞。然后，进程执行完 eating 后释放信号量（v(seat)）。
问题：
1. 信号量的值反映的是空座位数，而信号量本身并没有明确控制座位的数量，而只是作为一个计数信号量来管理等待队列。信号量的计数只适用于“占用资源”或“允许访问资源”，但它不能存储座位数。
2. 没有互斥机制：多个消费者进程可能会在“取座位”和“释放座位”这两个操作之间发生竞态条件。假设两个顾客同时到达并试图访问座位时，他们可能同时看到座位满了（seat == 0），但这时两者的 seat 数可能已经被错误地更新或冲突，从而导致座位的数量被错误管理。
```
   semaphore mutex = 1;  // 用于保护共享资源seat的互斥
   int seat = n;  // 座位数量

   customer进程：
   p(mutex);  // 获取锁
   if (seat == 0)  // 如果没有空座位
   {
      v(mutex);  // 释放锁
      goto out;  // 跳转到退出
   }
   else {
      seat--;  // 减少空座位数量
      v(mutex);  // 释放锁
   }

   eating;  // 顾客吃饭

   p(mutex);  // 重新获取锁
   seat++;  // 增加空座位数量
   v(mutex);  // 释放锁

   out:
   exit;  // 退出
```
理发店

失眠理发师

死锁
#

在一个进程集合中, 每个进程都因等待永远不会发生的事件而阻塞，称这种系统状态为死锁。
死锁产生的原因：资源竞争，资源分配策略导致进程推进顺序不当。

死锁的必要条件
- 系统的固有属性，不可破坏：
  - 互斥条件：资源不可共享（软件：锁；硬件：所有外设）
  - 不可剥夺条件：指进程已获得的资源在未使用完之前，不能被剥夺，只能使用完自己释放
- 破坏其中之一，就可以避免死锁：
  - 请求和保持条件：进程先申请一部分资源，再申请另一部分资源。在无法获得新的资源的时候，不放弃已有资源
  - 循环等待条件：资源分配图里有环路

处理死锁的方法

复习重点
#

为什么要引入进程？为什么要引入线程？从调度性、并发性、拥有的资源以及系统开销等方面，区别和比较进程和线程？

进程状态迁移图，引起状态迁移的原因和事件？

进程组成？PCB 的含义？

进程之间的关系？什么是临界区？如何实现临界区的互斥访问？

P/V 操作的含义？信号量的含义？如何定义信号量的初值？如何利用 P/V 操作实现多个进程之间的同步和互斥？如利用其实现单缓冲区的读写问题？如何实现生产者消费者等问题？

高级通信方式中，理解 send()和 receive（）的工作过程。

有哪些常用调度算法？引起进程调度的事件有那些？多级反馈队列调度算法的分析？

引起死锁的四个特征是什么？如何针对这是个特征克服死锁？资源分配图的方法判定死锁？

内存管理
#

思考题，考前不看段式，段页式不考! md

基本概念
#

多级存储器结构
存储管理终极目标：统一管理不同层次的存储介质。为系统提供容量近似于磁盘，访问速度近似于 cache 的物理存储器

存储管理的任务
- 存储资源管理：空闲资源管理、存储空间分配和释放
- 提供地址重定位机制：将指令和数据的逻辑地址转化为内存单元的物理地址
- 提供内存保护机制：防止现运行进程破坏内核或分配给其它进程的内存单元，以非法方式访问进程图像
- 内存扩充：借助大容量辅存扩充物理内存容量，存放暂时不用的进程图像。为系统提供一个容量比物理内存大许多的可执行存储器，以容纳更多的进程图像。

存储管理方式
#

为进程图像分配连续物理空间
所有图像均在内存的进程才能够执行
移动时搬迁的是整个进程图像。包括内存中的移动和换入、换出操作

可变分区

每个分区放一个进程。分区不固定。
用 空闲分区表（map 数组） 登记所有空闲分区的首地址和长度。

地址重定位和内存保护

内存扩充

优缺点

概念
- 逻辑地址：程序中指令和数据的地址。编译、链接过程确定的。
- 物理地址：指令和数据在物理内存中的地址。操作系统内核决定的。
- 虚空间（地址空间），逻辑地址集合。
- 线性地址空间：进程可以访问的所有逻辑地址 = 应用程序的虚空间 ∪ 内核的虚空间。
- 物理地址空间，物理地址集合。
- 重定位（Relocate）：将可执行程序中，指令和数据的逻辑地址转换成物理地址。
  - 静态重定位：由软件实施，程序加载时
  - 动态重定位：动态重定位由 CPU 硬件，每次访存时实施：MMU 将逻辑地址转换成物理地址。

内存分配方式
- 连续内存分配方式
- 段式内存管理 为每个逻辑段独立分配物理内存空间，每个进程一张段表，登记所有逻辑段的 首地址，长度和 保护位。
  - 段是自然的共享、保护单位
  - 段式内存管理的内存分配：内存分配，以自然段为单位，自然段长度可变，内存分配麻烦，存在外部碎片问题，物理内存利用率低。
- 页式存储管理方式
  - 虚空间等分为若干个逻辑页面，逻辑页面(2^n)字节
  - 实空间（物理内存），按相同尺寸分为若干个页框
  - 允许为逻辑页面分配任意空闲的物理页框。
  - 每个进程一张页表（Page Table），登记所有逻辑页面的 物理页框号 和 保护位。
  - 每个逻辑页面一个页表项（Page Table Entry，PTE）
  - base 是分配给它的物理页框号
  - prot 是保护位：
    - U/S：1 (U) 表示应用程序的逻辑页，CPU 用户态运行时有权访问；0 (S) 表示内核的逻辑页，CPU 用户态运行时无权访问。
    - RW/RO：1 (RW) 表示可读、可写；0 (RO) 表示只读。
    - X：1 表示代码页，可执行；0 表示数据页，不可执行。
  - 逻辑地址和页表
  - 地址映射和内存保护
  - 页式存储管理的优点
    - 页式最显著的优点，提高物理内存的利用率。每一个物理页框可以用来存放任何进程的任意逻辑页面。不存在 外部碎片 问题。但是存在页内碎片问题。
    - 扩展进程图象极其容易，已有进程不必移动。（栈从高地址向低地址增长，堆从低地址向高地址增长）
    - 以页为单位共享和保护物理内存
  - 页式存储管理的缺点
    - 页表太大，页表项太多，页表占用内存空间太大。
    - 页表查找时间太长，页表查找时间太长，页式地址映射，访存耗时加倍，CPU 运算速度减半。

CPU 的 Cache
指令缓存和数据缓存
- 命中：
- 不命中：
  物理地址访存耗时：指令/数据缓存访问时间 + 缓存不命中的概率 * 主存访问时间
TLB（装 PTE 的缓存）
EAT（Effective Access Time，内存有效访问时间）

空闲分区管理

虚拟存储器
#

程序运行的局部性原理：时间局部性和空间局部性

虚拟存储器改善性能的思路

传统存储管理方式，一次性为进程图像分配所需的所有内存
仅为当前需要访问的代码和数据分配内存。现在主流的方法：在基本的分页机制的基础上，加上 调页机制 和 页面置换机制
- 调页机制：为即将访问的页面分配存储空间、并且进行初始化。
  - 请求调页：内存分配（调页操作），延迟至页面访问时刻。一次调入一页。
  - 预调页：一次调入多个页面。当前需要的页面 + 虚空间中附近的多个页面。
- 页面置换机制：淘汰暂时不用的页面。将其换至磁盘，释放内存。
基于此技术打造的虚拟存储器，时间 & 空间局部性变现良好的程序，执行速度不会比运行在物理内存慢许多。

虚拟内存器：虚拟存储器用 硬盘中的 swap 分区（或者 swap 文件） 作为主存的辅助存储器，存放所有进程的图像；主存中只存放 CPU 最近需要使用的逻辑页面。
- 有了虚拟存储器，只需要装入少量逻辑页面进程就可以运行，访问到其它逻辑页面时，MMU 会抛出异常，缺页异常处理程序调入所缺页面。
- 虚拟存储器的优点：
  - 启动前不必装入全部进程图像，应用程序装载（exec）速度快
  - 程序员编程不必受物理内存的限制，计算机可以运行虚空间大于内存总容量的应用程序
  - 最后，除非内存抖动，系统不再需要执行 swap in 和 swap out 操作，系统性能提升。

请求调页
任何应用程序，只需为初始栈分配主存页框，装入 main 函数栈帧后便可以开始运行。其余进程图像，一次一页，访问时，缺页中断处理程序负责调入。
请求调页是指如果 CPU 访问的数据或指令不在主存，引发缺页异常，异常处理程序调入所缺逻辑页面。
缺页（Page Fault） CPU 所访问的信息内存中不存在。以 i386 芯片为例，present bit 是 0。缺页异常处理过程：
- MMU 硬件
  - (1)当前指令执行时操作数不在内存
  - (2)取指时下条指令不在内存，抛出缺页异常。
- 随后，CPU 中断处理元件
  - (1)压栈引发异常的当前指令的地址.
  - (2)cr2 记录引发缺页的那个逻辑地址。
- 操作系统介入：缺页异常处理程序
  - (1)找 1 个空闲的 物理页框
  - (2)修改页表，目标逻辑页对应的 PTE
  - (3)初始化物理页框。从磁盘读入包含 CPU 想要访问的数据或指令的整张逻辑页面（1 张页面，4096 字节，要读 8 个连续磁盘扇区）。
- 异常返回，进程重新执行引发异常的指令。所缺数据在内存，不会引发缺页异常，程序得以继续运行。
页面置换
- 缺页时，异常处理程序会为现运行进程分配一个可用的主存页框。如果内存没了，就要 覆盖一个逻辑页面，用分配给它的物理页框装所缺逻辑页。这个操作就是页面置换。
- 页面置换方式
  - 固定分配局部置换
    - 为每个进程分配固定数目的物理页框，如果缺页只能覆盖自己的逻辑页面
    - 典型算法：FIFO \ LRU \ CLOCK
  - 可变分配局部置换
    - 为每个进程分配一定数目的物理页框，如果缺页，仍然只能覆盖自己的逻辑页面
    - 跟踪进程的执行情况
      - 频繁缺页，为进程追加物理页框
      - 缺页率长期维持较低水平，可以收回部分页框
  - 可变分配全局置换
    - 为每个进程分配一定数目的物理块（物理页框）
    - 系统维护一个空闲物理块队列
    - 当某进程发生缺页时，由系统从 空闲物理块队列 中取出一个分配给该进程
    - 空闲队列分配完时，OS 才会覆盖内存中的逻辑页面
    - 被覆盖的可能是其他进程的逻辑页面，所以叫 全局置换

请求调页系统使用的页表项（PTE）及请求调页操作
例题

页面置换算法（使用固定分配局部置换）缺页时，若内存已无空闲空间，淘汰一页。用新逻辑页面覆盖被淘汰页面占用的物理页框。若被淘汰页面脏（修改过），写回磁盘。页面置换算法决定淘汰哪一页。优化目标：降低缺页率。
- OPT 未来访问时刻最远的（最优）
- FIFO 最先进入内存的
- LRU 最近最久未访问的
- CLOCK（NRU，Not Recently Used）淘汰最近没用过的（不一定是最久）
- 随机算法

请求调页虚拟存储器相关的理论

工作集和驻留集
抖动

复习重点
#

程序装入内存有几种方式？什么是可重定位的装入技术？

在动态分区分配中，有那些分区分配算法？各个是如何实现的？

什么是虚拟存储器？其特征是什么？虚拟存储器容量是如何确定的？

请求分页技术中，图示 windows 下的两级分页机制？

请求分页机制中，页面置换算法有那些，具体实施页面置换过程？

在交换技术中，进程置换策略是什么？

什么是快表？其中内容是什么样子的？什么是页表？其结构是如何？

文件系统
#

预读的代码考试不考。知道 read 系统调用什么时候用它就行到这个程度《文件系统例题和习题 2 完整的文件读写过程》

Unix 文件系统
#

文件系统存放很多文件，文件是 可重复访问的字节序列，支持 随机访问、所有字节可 重复读写。

用户存放的文件，是文件系统的用户数据
- 可执行文件供进程管理系统使用
- 普通数据文件供应用程序使用

用来管理文件的数据结构，是文件系统的 元数据（metadata）
- 每个文件一个文件控制块，登记文件访问权限、文件数据块存放的位置
- 读写文件，需要使用文件控制块
- 文件树，挂所有文件，目录搜索就是在文件树上查找文件
- 用户数据和元数据存放在同一张磁盘

文件基础概念
- 文件按磁盘数据块大小切块，离散存放在磁盘上，每一块是一个逻辑块
- 为文件分配的磁盘存储空间，是 整数个 磁盘数据块
- 文件系统使用 离散存储管理方式。相邻的文件逻辑块在磁盘上 不必连续存放。但尽量连续存放一定能提升文件顺序读写效率。

文件控制块（FCB，File Control Block）
每个文件有一个文件控制块 FCB，包括如下信息：
- 地址映射表，用来计算分配给逻辑块 bn 的物理块号 dn
- dn = f(bn) /* bn = offset/512; offset是数据在文件中的偏移量 */
- 数据存放在物理块 dn，块内偏移量是 offset % 512
- 文件主 uid，创建该文件的进程的 uid
- 文件访问权限，登记各类用户对该文件的读、写、执行权限
- Unix 是 RWXRWXRWX，标识 文件主，文件所在的用户组 和 nobody 对文件的读、写、执行权限。
- Windows 是 ACL（Access Control List）
- 进程 uid 和 gid 标识使用文件的用户和用户组
- 创建时刻，最后一次访问时刻，最后一次修改时刻。
FCB 的使用：
- 创建文件时，进程执行系统调用 create("文件名", mode) 创建 FCB。mode 是文件的访问权限 rwxrwxrwx。
  - 新建 FCB，填入文件名，uid=进程 uid，访问权限=mode。文件尺寸=0，创建时刻=time。
- 访问已有文件，进程需要使用 FCB。
  - 使用文件前，执行 open 系统调用打开文件。
    - open ("文件名", mode) 。mode 是进程希望对文件执行的操作：读、写还是既读又写。
    - 需要将 FCB 读入内存，使用访问权限字段，判断进程（p_uid 用户）有没有文件的访问权限。
  - 读写文件时，进程执行 read/write 系统调用。
    - 需要使用 FCB 中的地址映射表确定需要读写的磁盘数据块
    - 执行 bread/bwrite/breada……合适的函数，进行字符块读写
- 文件访问结束，执行 close 系统调用关闭文件。内存中的 FCB，如果发生变化，写回磁盘。 - 写文件会导致文件长度和地址映射表发生变化

文件树，目录项和目录文件
1. 文件树
2. 绝对路径、相对路径

DiskInode DiskInode 是 Unix 的文件控制块。DiskInode 号是文件 ID，文件的内部标识，每个文件，磁盘上有一个 DiskInode。

class DiskInode {
    unsigned int d_mode;  // 文件模式
    int d_nlink;          // 硬链接数
    short d_uid;          // 文件主的 uid
    short d_gid;          // 文件所在的组
    int d_size;           // 文件尺寸，字节数
    int d_addr[10];       // 混合索引表根节点
    int d_atime;          // 最后访问时刻
    int d_mtime;          // 最后修改时刻
};

d_mode，DiskInode 的使用状态、文件类型和访问权限

d_addr，用来进行地址映射

文件卷
- 每个 文件系统 有自己的 文件卷，存有运行所需的全部内核数据结构和它所管理的数据文件。
- 卷格式取决于具体的文件系统。Unix 文件卷和 Windows 文件卷格式完全不同。
  - 超级块，存放文件卷 info 和文件系统的使用状态
  - inode 区，存放 DiskInode（64 字节）。
    - 空闲标识，d_mode 中 IALLOC 为 0，不在内存打开 inode 池中
    - DiskInode 编号由存储位置决定，n# DiskInode，扇区号 n/8+2，扇区内偏移量 n%8
  - 数据区，存放普通数据文件和目录文件（数据块、索引块）。数据区的资源是物理块，Unix V6 中为 1 个扇区、512 字节没有空闲标识

Unix V6++系统中文件
1. 磁盘上的普通数据文件
  - 混合索引树
    - DiskInode 中的 d_addr 数组是混合索引树的根节点。
    - d_addr [0] ~ d_addr [5]，可以登记 6 个物理块号，存放文件的 0#~5#逻辑块。
    - d_addr [6]，第 1 个索引块，可以登记 128 个物理块号。
    - d_addr [7]，第 2 个索引盘块，可以登记 128 个物理块号。
    - d_addr [8] 和 d_addr [9] 是 2 次索引块。每个 2 次索引盘块可以挂 128 个一次索引盘块，用来支持很大的文件。
2. 磁盘上的目录文件
  John 的目录项，存放在目录文件 home
3. 特殊文件（外设硬件）

磁盘空闲资源管理

主硬盘

文件系统的使用
#

文件系统的使用过程
- 使用前装载 mount
  - 将超级块读入内存。分配、释放存储资源需要使用空闲盘块号栈和空闲 Inode 栈。
  - 将根目录 Inode 读入内存。搜索文件时要用文件树。
- 使用阶段
  - 搜索、维护文件树
    - （1）打开已有文件、目录
    - （2）新建文件/子目录时，增加节点和边
    - （3）删除文件/子目录时，去除节点和边。
  - 访问普通数据文件。read、write 系统调用。写文件会更新 DiskInode。
- 使用完毕卸载 unmount
  - 超级块和所有脏数据写回磁盘
文件系统的元数据 metadata
- 文件系统的元数据 metadata 是文件系统持久化在磁盘上的内核数据结构
- Unix V6++：超级块、DiskInode 和 DirectoryEntry
- 磁盘上的数据结构，使用前，复制进内存。用完，更新后的数据结构写回磁盘。

支持文件系统运行的数据结构（系统层面）
文件系统会话

支持文件系统运行的数据结构（进程层面）
- 外部标识：文件路径名；
- 内部标识：文件描述符，打开文件表的下标 fd

进程访问数据文件，需要使用打开文件结构
1. read 系统调用
2. write 系统调用
3. seek 系统调用

文件树使用和维护

打开文件结构的使用和维护
1. fd=open() 建立打开文件结构
2. close(fd) 拆除打开文件结构，释放资源
3. fork 创建的子进程集成父进程打开的文件
  - 进程的标准输入、输出文件这三个文件无需打开。它们，用户登录（login）时打开，fork 时继承自 shell 进程（V6++没有登录过程，系统初始化时 main0 打开这 3 个文件）所以进程打开文件表中 0,1,2 项要空出来，从 3 开始分配 File 结构。
    - 0，STDIN, 标准输入
    - 1，STDOUT，标准输出
    - 2，STDERR，标准错误输出(Unix V6++没有)
  - 标准输入输出文件的使用