操作系统（计算机系）复习笔记 ¶

about 13861 words 27 lines of code reading time 70 minutes

Info

此复习笔记参考 2024 春季学期清华大学计算机系《操作系统》谌卫军老师课程，《操作系统》第二版（编著：谌卫军，清华大学出版社。）

第 1 章操作系统概述 ¶

指令是计算机运行的最小功能单元，是指挥计算机硬件运行的命令算术运算指令、逻辑运算指令、移位操作指令、数据传送指令、输入输出指令、转移指令等。

硬件和应用软件之间，引入一层软件，其功能为：管理系统的各个部件，使之能正常运转；给上层的应用软件提供一个易于理解和编程的接口；这层软件就是操作系统 (Operating System)。

操作系统是计算机系统中的一个系统软件，是一些程序模块的集合。它们能以尽量有效、合理的方式管理和分配计算机的软硬件资源，合理的组织计算机的工作流程，控制程序的执行并向用户提供各种服务功能，使得用户能够灵活、方便、有效的使用计算机，使整个计算机系统能高效地运行。

高级语言源代码 source code --> 编译器 compiler --> 链接器 linker --> 可执行程序 executable program。

单道批处理——通道，中断——多道批处理（现代意义上操作系统）。

考点：多道批处理的时间分配画图和计算。

操作系统类型：批处理操作系统（多道批处理），分时操作系统，实时操作系统，嵌入式操作系统（Linux 为代表），个人计算机操作系统，分布式操作系统。

硬件特性：受保护的指令（特权指令），系统调用，内存保护，中断机制，IO 系统，时钟操作。

CPU 可以直接访问：内存，寄存器，不能直接访问磁盘、网络和 CD-ROM。

处理器状态：管态（内核态，系统态，特权态），目态（普通态，用户态），用一个专门的寄存器指示处理器状态，PSW(Program Status Word)。

内核态——用户态，设置 PSW 实现。用户态——内核态，无法直接修改 PSW。只能通过中断完成。

如何让用户能够做一些带有特权的事？系统调用。用户程序通过特殊的访管指令，来请求操作系统为其提供某种功能的服务。优点：保护了系统，更安全。缺点：跨越了硬件栅栏，开销更大（无系统函数的地址、Cache 和 TLB 项更新等），一次系统调用所花费的时间是一次函数调用的 10－1000 倍。解决方案：把一些系统功能放在用户态下运行，如动态库（DLL）。

系统调用指令的实现过程一般是：

当 CPU 执行访管指令时，即引起访管中断；
处理器保存中断点的程序执行上下文环境（PSW, PC 和其他的一些寄存器），CPU 切换到内核态。
中断处理程序开始工作，调用相应的系统服务；
中断处理结束后，恢复被中断程序的上下文环境，CPU 恢复为用户态，回到中断点继续执行。

系统调用的时候从用户态切换到内核态但不会发生进程切换。

内存保护：防止一个用户程序去访问其他用户程序的数据；保护操作系统免受用户程序的破坏。如何支持？最简单的做法：基址寄存器和边界寄存器。还可以虚拟存储技术：虚实地址映射。

中断对于操作系统非常重要：

同步中断：CPU 控制单元发出，也叫异常。CPU 检测到的异常，包括：错误 Fault、陷阱 Trap 和中止 Abort，例如：算术溢出、被零除、用户态下使用了特权指令等；程序设定的异常，即程序员通过 int、int3 等指令来发出的中断请求，也称为软中断，主要用来实现系统调用服务。
异步中断：由其他的硬件设备在任意的时刻所发出的中断，简称为中断。可屏蔽中断，即 I/O 中断，它是当外部设备或通道操作正常结束或发生错误时所发生的中断。例如：打印机打印完成、缺纸，读磁盘时驱动器中没有磁盘等；不可屏蔽中断，例如：由掉电、存储器校验错等硬件故障引起的硬件中断）。每一个中断或异常都用一个 0－255 之间的整数来标识，称为中断向量，系统根据中断向量，来为每一个中断或异常指定相应的处理程序。

I/O 系统，完成计算机系统中的输入输出。

时钟，在分时系统中，间隔时钟实现进程间按时间片轮转；在实时系统中，按要求的间隔输出正确的时间信号给实时的控制设备；记录用户和系统所需的绝对时间（年、月、日、时、分、秒）。

第 2 章进程管理 ¶

进程 ¶

进程 process，组织和管理程序的运行。

处理器组成：

控制单元（Control Unit），能够正确并且自动地连续执行指令能正确并分步完成每一条指令的功能读取指令 --> 分析指令 --> 控制执行响应并处理中断。
执行单元（Execution Unit），CPU 的“计算器”，分为不同的功能部件，包括算术逻辑单元（ALU）、移位器、乘法器、除法器、分支单元等来自控制单元的信号选择不同的功能部件。
寄存器组。

一个进程包括：进程包含了正在运行的一个程序的所有状态信息。进程不等于程序，还包括动态内容：

程序的代码
程序的数据
CPU 寄存器的值，如 PC，用来指示下一条将运行的指令、通用寄存器等
堆、栈
一组系统资源（如地址空间、打开的文件）

栈的用途：用于暂存功能，在程序运行时保存运行上下文信息。在函数调用发生时，保存被调用函数的局部变量和形参。

堆：内存中的一块空间，用于动态分配；在 C 语言中，通过 malloc 来申请动态内存空间，通过 free 来释放；使用不当可能导致内存泄漏。

进程的特性：

动态性：程序的运行状态在变，PC、寄存器、堆和栈等；
独立性：是一个独立的实体，是计算机系统资源的使用单位。每个进程在一个“虚拟计算机”上运行，每个进程都有“自己”的 PC 和内部状态，运行时独立于其他的进程（虚拟 PC 和物理 PC）；
并发性：从宏观上看各进程是同时独立运行的。

进程的创建：3 个，系统初始化时；在一个正在运行的进程当中，执行了创建进程的系统调用；用户请求创建一个新进程。

进程的状态：3 个，运行，就绪，阻塞（等待某种事件的发生而暂时不能运行的状态，如 I/O 操作或进程同步，此时即使 CPU 空闲该进程也不能运行。）

进程转换：

运行 --> 阻塞，等待 I/O 的结果，等待某一进程提供输入
运行 --> 就绪，运行进程用完了时间片，运行进程被中断，因为一高优先级进程处于就绪状态
就绪 --> 运行，调度程序选择一个新的进程运行
阻塞 --> 就绪，当所等待的事件发生时
没有：阻塞到运行（不会直接到运行，中间要有一步缓冲），就绪到阻塞（准备好了之后就不会阻塞）

系统调用的时候从用户态切换到内核态但不会发生进程切换。

描述进程的数据结构：进程控制块，PCB(Process Control Block)，结构体实现

PCB 中的主要内容：寄存器，PC（程序计数器），PSW，栈指针，进程状态，优先级，进程 ID，调度参数，父进程，信号，进程起始时间，CPU 使用时间，代码段数据段和栈的指针（内存中），工作目录，用户 ID，文件读写指针

系统用 PCB 来描述进程的基本情况以及运行变化的过程，PCB 是进程存在的唯一标志。进程的创建：为该进程生成一个 PCB；进程的终止：回收它的 PCB；进程的组织管理：通过对 PCB 的组织管理来实现；

单核 CPU 的进程运行，切换进程和陷入内核交替进行。

操作系统来维护一组队列，用来表示系统当中所有进程的当前状态；不同的状态分别用不同的队列来表示（运行队列、就绪队列、各种类型的阻塞队列）；每个进程的 PCB 都根据它的状态加入到相应的队列当中，当一个进程的状态发生变化时，它的 PCB 从一个状态队列中脱离出来，加入到另外一个队列。

线程 ¶

线程：可以并发执行，共享相同的地址空间，（线程是进程当中的一条执行流程）

从资源组合的角度：进程把一组相关的资源组合起来，构成了一个资源平台（环境），包括地址空间（代码段、数据段）、打开的文件等各种资源；从运行的角度：代码在这个资源平台上的一条执行流程（线程）。

进程 = 线程 + 资源平台。优点：一个进程中可以同时存在多个线程；各个线程之间可以并发地执行；各个线程之间可以共享地址空间。
线程独享：寄存器，PC，PSW，栈指针。
线程共享：进程 ID，代码段的指针，工作目录。
线程执行时的栈：向下增长，栈中存放局部变量，允许递归调用。
线程三步走：分配栈，传递参数，执行函数。

进程 vs 线程：

进程是资源分配单位和操作系统保护单位，线程是 CPU 调度单位。
进程拥有一个完整的资源平台，如代码、数据和堆，而线程只独享必不可少的资源如寄存器和栈。
线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换关系。
线程能减少并发执行的时间和空间开销。
线程＝轻量级进程 (lightweight process)

线程控制块：TCB，有 CPU 寄存器，栈指针，线程优先级

通常来讲，一个函数名对应一个线程，一个文件名对应一个进程。共享全局变量的是两个不同的线程。

进程间通信与同步 ¶

进程间通信：InterProcess Communication, IPC。

并发进程之间的两种关系：相互独立：进程之间没有任何关联关系，仅有 CPU 竞争关系；相互关联：进程之间存在着某种关联关系（直接或间接），需要相互通信。低级通信：只能传递状态和整数值（控制信息）。高级通信：能够传送任意数量的数据。

当两个或多个进程在访问共享资源时，如何确保它们不会相互妨碍——进程互斥问题；当进程之间存在着某种依存关系时，如何来调整它们运行的先后次序——进程同步问题。

进程互斥的产生原因：进程宏观上并发执行，依靠时钟中断来实现微观上轮流执行；访问共享资源。

竞争状态：两个或多个进程对同一共享数据同时进行读写操作，而最后的结果是不可预测的。在同一时刻，只允许一个进程访问该共享数据，即如果当前已有一个进程正在使用该数据，那么其他进程暂时不能访问。对共享内存或共享文件的访问，可能会导致竞争状态的出现。我们把完成这类事情的那段程序称为临界区，把需要互斥访问的共享资源称为临界资源。

实现互斥访问的四个条件：

任何两个进程都不能同时进入临界区；
不能事先假定 CPU 的个数和运行速度；
当一个进程运行在它的临界区外面时，不能妨碍其他的进程进入临界区；
任何一个进程进入临界区的要求应该在有限时间内得到满足。

基于关闭中断的互斥实现：当一个进程进入临界区后，关闭所有的中断；当它退出临界区时，再打开中断。由于进程的切换是由中断引发的，关闭中断后，CPU 不会被分配给其他进程，其他进程无法执行；操作系统内核经常使用这种方法来更新内部的数据结构（变量、链表等）。

基于繁忙等待的互斥实现：

加锁标志位法：lock 的初始值为 0，当一个进程想进入临界区时，先查看 lock 的值，若为 1，说明已有进程在临界区内，只好循环等待。缺点：可能出现针对 lock 的竞争状态问题。
强制轮流法：每个进程严格地按照轮流的顺序进入临界区。优点：保证在任何时刻最多只有一个进程在临界区。缺点：违反了互斥访问四条件中的第三个条件（当一个进程运行在它的临界区外面时，不能妨碍其他的进程进入临界区）。
Peterson 方法：当一个进程想进入临界区时，先调用 enter_region 函数，判断是否能安全进入，不能的话等待；当它从临界区退出后，需调用 leave_region 函数，允许其它进程进入临界区。两个函数的参数均为进程号。解决了互斥访问的问题，而且不会相互妨碍，可以完全正常地工作。

上面的方法都是基于繁忙等待，缺点：1、浪费 CPU 时间；2、可能导致预料之外的结果（如：一个低优先级进程位于临界区中，这时有一个高优先级的进程也试图进入临界区）解决方法：当一个进程无法进入临界区时，应该被阻塞起来（sleep）；当一个进程离开临界区时，需要去唤醒（wake up）被阻塞的进程；克服了繁忙等待方法的两个缺点（浪费 CPU 时间、可能死锁）。

上面的问题是：任何时刻，只允许一个进程进入临界区。新的问题是：在任何时刻，只允许 N 个进程同时进入临界区（N >= 1）：

信号量与 PV 原语 ¶

信号量 semaphore，正数表示当前空闲资源的数量，负数的绝对值表示正在等待进入临界区的进程个数。是由操作系统来维护的，用户进程只能通过初始化和两个标准原语（P、V 原语）来访问。初始化可指定一个非负整数，即空闲资源总数，也即同时允许几个进程在临界区。

P、V 原语包含有进程的阻塞和唤醒机制，因此在进程等待进入临界区时不会浪费 CPU 时间；

P 原语：申请一个空闲资源（把信号量减 1），若成功，则退出；若失败，则该进程被阻塞；

V 原语：释放一个被占用的资源（把信号量加 1），若发现有被阻塞的进程，则选择一个唤醒之。

结构体实现：

C

typedef struct
{
    int count;         // 计数变量
    struct PCB *queue; // 进程等待队列
} semaphore;

C

P(semaphore S)
{
    --S.count;       // 表示申请一个资源;
    if (S.count < 0) // 表示没有空闲资源;
    {
        // 该进程进入等待队列S.queue末尾;
        // 阻塞该进程;
        // 调用进程调度器；// OSSched( )
    }
}

C

V(semaphore S)
{
    ++S.count;        // 表示释放一个资源;
    if (S.count <= 0) // 表示有进程被阻塞;
    {
        // 从等待队列S.queue中取出一个进程;
        // 把该进程改为就绪状态，插入就绪队列
    }
}

格式：

C

P(mutex);
// 临界区
V(mutex);

经典问题：生产者消费者问题。

进程调度 ¶

在任何时刻，一个进程只可能是以下三种状态之一：

运行状态：该进程正在 CPU 上运行，每个 CPU 上最多只能有一个进程在运行；

就绪状态：进程已经就绪，随时可以运行；

阻塞状态：如在某个信号量上被阻塞，等待 I/O

进程行为：

CPU 执行（CPU 繁忙），大部分时间处于运行和就绪状态。如科学计算，图像处理，视频解码。
等待 I/O 操作（I/O 繁忙），大部分时间处于阻塞状态。如磁盘读写，文件操作，网络通信（爬虫）。

何时调度？：

当一个新的进程被创建时，是执行新进程还是继续执行父进程？
当一个进程运行完毕时；
当一个进程由于 I/O、信号量或其他的某个原因被阻塞时；
当一个 I/O 中断发生时，表明某个 I/O 操作已经完成，而等待该 I/O 操作的进程转入就绪状态；
在分时系统中，当一个时钟中断发生时。

两种调度方式：

不可抢占调度方式：一个进程若被选中，就一直运行下去，直到它被阻塞（I/O，或正在等待其他的进程），或主动地交出 CPU。以上的情形 1－3 均可发生调度；
可抢占调度方式：当一个进程在运行时，调度程序可以打断它。以上的情形 1－5 均可发生调度。

进程切换：

时间片轮转法：

将所有的就绪进程按照 FCFS 原则，排成一个队列；每次调度时将处理器分派给队首进程，让其执行一小段 CPU 时间（时间片）；在一个时间片结束时，如果进程还没有执行完的话，在时钟中断中，进程调度程序将暂停当前进程的执行，并将其送到就绪队列的末尾，然后执行当前的队首进程；如果一个进程在它的时间片用完之前就已结束或被阻塞，那么立即让出 CPU。
优点：公平性：各个就绪进程平均地分配 CPU 的使用时间。假设有 n 个就绪进程，那么每个进程将得到 1/n 的 CPU 时间；活动性：若时间片大小为 q，每个进程最多等待 (n-1)q 时间就能够再次得到 CPU 去运行。
缺点：q 的大小难以确定。q 太大：退化为 FCFS 算法，进程在一个时间片内执行完或被阻塞，响应时间长。如 q=100ms；q 太小：每个进程需要更多时间片才能处理完，进程切换次数增加 (1ms)，增大系统开销；一般在 20－50ms

优先级算法：

给每个进程设置一个优先级，然后在所有就绪进程中选择优先级最高的那个进程去运行；
可以把进程按照不同的优先级别分组，然后在不同级别之间使用优先级算法，而在同一级别的各个进程之间使用时间片轮转法。
可能产生的问题：饥饿。解决：实行动态优先级
可能产出的问题：优先级反转。如 T1 优先级高、T2 优先级低，T2 获得了锁 L，T1 试图去获取 L，失败，被阻塞。T3 进入系统，其优先级高于 T2、低于 T1。 T2 无法运行。解决：优先级继承，临时提升最低的 T2 的优先级，使得与 T1 相同，更快完成并释放锁 L（同步资源），完成后再恢复原来的优先级。

第 3 章存储管理 ¶

存储管理概述 ¶

理想存储器：更大更快更便宜，非易失。

（小快贵）——寄存器——高速缓存 Cache——主存储器 DRAM——外部存储器（硬盘，光盘，U 盘）——（大慢便宜）。

内存也叫主存，存储指令和数据。对各个存储单元的读写操作就是通过它们的地址来进行的。

单道程序存储管理 ¶

内存分为两个区域：系统区，用户区。每次把一个应用程序装入到用户区运行，由它和操作系统来共享内存。当它运行结束后，操作系统再装入一个新的程序把它覆盖。

数据存储方式：

全局变量，固定地址，其他源文件可见。
静态全局变量，固定地址，但只在本文件中可见。
函数参数：位于栈帧当中，动态创建，动态释放。
静态局部变量，固定地址，只在本函数中可见。
普通局部变量，位于栈帧当中，只在本函数可见。
动态申请的内存空间，位于堆当中。

（高地址）——栈——动态堆空间——数据段（放数据）——代码段（放代码）——（低地址）。

优点：简单、开销小，易于管理；适合于单用户、单任务的 OS。

缺点：每次只能运行一个程序；内存资源的使用效率不高，程序较小时，会浪费大量的内存空间；OS 的保护，应用程序的 bug 会破坏 OS 地址；空间有限，即为物理内存的大小。

如何实现多道存储管理？分区管理：又把用户区划分为若干分区 (partition)。一个进程占用一个分区。特点：适合多道程序系统和分时系统，支持多个程序并发执行。

固定分区存储管理 ¶

各个用户分区的个数、位置和大小一旦确定以后，就固定不变。（自助提货柜问题）

分区的大小是否相等？程序大小不同多个小分区、适量的中等分区、少量大分区。

进程个数多于分区个数？输入队列。

数据结构：设置内存分配表。

内存分配：先放入输入队列，然后采用最先匹配法、最佳匹配法等算法。

内存回收：简单。

固定分区的缺点：

内存利用率不高，内碎片造成很大浪费。所谓内碎片，即进程所占用分区之内的未被利用的空间。
分区的总数固定，限制了并发执行的程序个数，不够灵活。
地址空间的大小有限。
如何确定分区的大小？

可变分区存储管理 ¶

可变分区（动态分区）

初始时，操作系统会占用内存的一部分，其余空间为一个完整的大空闲区。
当一个程序要求装入内存运行时，系统从这个空闲区中划一块分配给它。
当程序完成后释放所占用的存储区。
随着一系列的内存分配和回收，原来的一整块大空闲区就形成了若干占用区和空闲区相间的布局。

可变分区特点：

分区的个数、位置和大小都是随进程的进出而动态变化的，非常灵活，避免了在固定分区中因分区大小不当所造成的内碎片，提高了内存利用率。
有外碎片，即各个占用分区之间难以利用的空闲分区。
使得内存的分配、回收和管理更为复杂。

地址映射 ¶

CPU 访问内存的两种模式：

实模式：直接访问内存，8086 CPU 的工作方式，数据总线和寄存器各 16 位，地址总线 20 位，可访问内存空间 1M。现代计算机在刚加电时运行在实模式，单道；
保护模式：需要进行地址映射，286 以后 CPU 采用的工作方式。

物理地址也叫内存地址、绝对地址，实地址；把内存分成很多个大小相等的存储单元，每个单元给一个编号，这个编号称为物理地址；物理地址可以直接寻址；物理地址的集合称为物理地址空间（内存地址空间），它是一个一维的线性空间。

逻辑地址也叫相对地址，虚地址；用户程序经汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为 0，其余指令中的地址都是相对首地址来编址；内存保护：逻辑地址与物理地址分离。

地址映射：为保证 CPU 执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，此过程称为地址映射。

地址映射方式：

静态地址映射（静态重定位）：当用户程序被装入内存时，直接对指令代码进行修改，一次性实现逻辑地址到物理地址的转换。无需额外硬件，适用于嵌入式系统。
动态地址映射（动态重定位）：当用户程序被装入内存时，不对指令代码做任何修改。而是在程序运行过程中，当需要访问内存单元时再来进行地址转换（即在逐条执行指令时完成转换）。由硬件地址映射机制完成，如设置一个基地址寄存器，并装入进程所在分区起始地址；在程序运行时，硬件自动完成地址映射。基地址寄存器只有一个（无论有几个进程）。在一个进程进入时，填入该进程的基地址。

存储保护：为了防止一个用户程序去访问其他用户程序的内存分区，保护操作系统免受用户程序的破坏，须进行存储保护。最简单的做法：在基地址寄存器的基础上再增加一个限长寄存器（大于 0 小于某个长度），记录分区长度。这两者在一起，就定义了进程所在的分区。

MMU：存储管理单元 (Memory Management Unit)，连接 CPU 和总线（MMU 位于处理器内核和连接高速缓存以及物理存储器的总线之间），CPU 发送逻辑地址给 MMU，MMU 发送物理地址给内存。

MMU 作用：内存保护，内存共享。

页式存储管理 ¶

（类比火车车厢运货）

把物理内存划分为许多个固定大小的内存块，称为物理页面，或页框(page frame)；

把逻辑地址空间划分为大小相同的块，称为逻辑页面，或简称页面(page)；

页面大小为 2n，一般在 512 字节到 8K 字节之间；

当一个用户程序装入内存时，以页面为单位进行分配。若要运行一个大小为 n 个页面的程序，需要有 n 个空闲的物理页面把它装入，这些页面不必是连续的。

存储管理的数据结构：数组。

页表：系统为每一个进程都建立了一个页表，页表给出了逻辑页面号和具体内存块号（物理页面号）之间的对应关系。页表是对于某一个进程的。

物理页面表：在系统中设立一张物理页面表，用来描述内存空间当中，各个物理页面的分配使用状况。具体实现：位示图，空闲页面链表。内存中共有 256 个物理页面，可以用字长为 32 位的 8 个字来构成位示图。物理页面表是对于整个内存的，是操作系统的。

如何实现页表？

数组。数组索引是逻辑页面号，数组内容是物理页面号，即存储要放在第几个物理页面。逻辑地址空间是连续的 page0, page1, ... page3，相应的页表索引是 0, 1, 2, 3。然后将这些 page 放在物理内存中，不一定是连续的且顺序的。

如何进行内存的分配与回收？——这里以位示图为例：

内存的分配：计算一个进程所需要的页面数 N，并查看位示图，看是否还有 N 个空闲页面；若有，则申请一个页表，其长度为 N，并把页表的起始地址填入 PCB；分配 N 个空闲物理页面，将其编号填入页表；修改位示图（0-->1，空闲页面数－N）
内存的回收：当一个进程运行结束，释放它所占用的内存空间后，需要对这些物理页面进行回收。对于每一个物理页面，根据它的编号计算出它在位示图当中的相应位置，并将相应位的值从 1 改成 0；修改位示图中的空闲页面数：加上 N。

如何进行地址映射？（输入逻辑地址，输出物理地址）：

对于给定的逻辑地址，找到逻辑页面号和页内偏移地址；
查找页表，找到相应的物理页面号；
计算最终的物理地址。

注意：我们平时程序运行以及调试能看到的全部都是逻辑地址。

将逻辑地址划分为两部分：逻辑页面号（高位） + 页内地址偏移（低位），系统自动而完成，对用户透明。页面大小取决于低位的页内偏移的位数。页内偏移有 10 位即为 1KB，12 位即为 4KB。

如果逻辑地址为十进制：页号＝虚地址 / 页大小，位移量＝虚地址 % 页大小。例如：假设页面大小为 2KB，计算逻辑地址 7145 和 3412 的逻辑页面号和页内偏移地址。页号：7145 / 2048 ＝ 3，页内偏移： 7145 % 2048 ＝ 1001。

页表的具体实现？

保存在内存中。且位于内核空间，用户不能随便访问。本质上是数组，因此在内存中连续。
为了访问页表内容，硬件上增加一对寄存器：页表基地址寄存器 PTBR（指向页表起始地址），页表长度寄存器 PTLR（指示页表大小，也即这个进程有多少个页面）。寄存器位于 MMU。
硬件寄存器在进程切换时更新，由操作系统更新，如何更新？从 PCB 中取出页表起始地址，放入页表基地址寄存器。
地址映射以及物理内存访问都是 CPU 完成的（包括 MMU）。一般来说硬件可实现的都是 CPU 完成，软件指令实现的才是操作系统完成。
具体来说，逻辑地址的分离、查询页表并将逻辑页面号转变为物理页面号是 CPU 完成。页表寄存器起的装值、页表数据的维护都是操作系统完成。
页式地址映射：程序在运行中需要访问某个内存单元，此时指令给出的是逻辑地址，MMU 的页表基地址寄存器中存放了这个进程的页表的起始地址，将逻辑页面号与这个值相加（乘 4）得到相应的页表项，里面记录了物理页面号，取出物理页面号，与页内地址偏移相加得到最终的物理地址。合成物理地址时使用物理页面号与页内偏移叠加的方式。
地址映射的过程中，访问 2 次内存，一次是访问内存中的页表，一次是真正访问内存中的数据。
如何加快页表查询速度？快速查找硬件 TLB（Translation Lookaside Buffer），存放最近一段时间内最常用的页表项。能够直接将逻辑页面号映射为物理页面号，不用访问内存，在 TLB 中没找到再去访问页表。（考虑到绝大多数程序在一小段时间内，倾向于集中访问一小部分页面）。例如：访问一个连续的 1024 的数组内容，使用 TLB 只需 1025 次，不用 TLB 要 2048 次。

页式存储管理的优缺点？

优点：

没有外碎片，内碎片的大小不超过页面的大小；
一个程序不必连续存放，提高了内存的利用率；
进程看到的仍然是连续逻辑地址空间，所有的操作都是 OS 和硬件完成的。

缺点：

程序必须全部装入内存才能运行；内存中必须有足够多空闲的物理页面才行。
OS 为每个进程维护一张页表，切换开销很大。

段式存储管理 ¶

基本原理：

对程序的每个逻辑单元（代码、数据和栈等），设立一个完全独立的地址空间，称为“段”。每个段的内部是一维线性连续地址，大小可不同。
对于物理内存来说，采用可变分区（动态分区）的管理方法。
当一个程序需要装入内存时，以段为单位进行分配，把每一个段装入到一个内存分区当中，这些内存分区不必是连续的。
可以看作是可变分区管理的一种扩展，因为在物理内存上管理方法完全相同。

具体实现：

在段式存储管理中，用户空间地址为二维地址：( 段号，段内偏移 )。实现方式有两种：(1) 地址高位为段号、低位为偏移；(2) 指令中显式地给出段号和段内偏移。
段表：系统为每一个进程都建立了一个段表，它给出了进程当中的每一个段与它所对应的内存分区之间的映射关系。

段表 vs 页表：

功能不同，页表实现逻辑页面号与物理页面号之间映射，页表项存放物理页面号。而段表项存放这个段在相应内存分区的起始地址。
页表长度固定，段表长度不固定，所以要增加段长这个字段。

段表的具体实现？

段表保存在内存当中。
数据结构：结构体数组。
设置一个段表基地址寄存器（Segment-table base register，STBR），用来指向内存当中段表的起始地址。
设置一个段表长度寄存器（Segment-table length register，STLR），用来指示段表的大小，即程序当中的段的个数。
硬件寄存器在进程切换时更新，由操作系统更新，如何更新？从 PCB 中取段表起始地址，放入段表基地址寄存器。

段式地址映射：

给定一个逻辑地址，第一维是段号，第二维是段内偏移（无需分离）。
段表基地址寄存器中存放了段表的起始地址，加上段号（乘 4）得到相应的段表项，这样就 i 能知道这个段存放在哪个分区、分区的起始地址、分区的长度。
合成物理地址时，直接将分区起始地址与段内偏移相加。

一般来说，32 位逻辑地址中，16 位段号，16 位段内偏移，最多 64K 个段，每个段最多 64KB，相乘恰好为 4G（内存大小）。

优点：

程序通过分段来划分多个模块，每个模块可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为单位来进行共享（How？共享的段映射到相同的内存分区）。
一个程序不必连续存放，没有内碎片。
便于改变进程所占空间大小。

缺点：程序必须全部装入内存、有外碎片等。

段页式存储管理 ¶

先把程序划分为段，然后在段内分页。

逻辑地址 = 段号 + 段内地址（段内地址 = 页号 + 页内地址）。

内存划分：按页式存储管理方案。

内存分配：以页面为单位进行分配。

具体实现：

段表：记录了每个段的页表起始地址和页表长度，而不是该段所在内存分区的起始地址。
页表：记录了逻辑页面号与物理页面号之间的对应关系（每一段有一个，一个程序可能有多个页表）。
需要的硬件支持：段表基地址寄存器（STBR）和段表长度寄存器（STLR）。

虚拟存储技术 ¶

局部性原理：程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。具体表现：

程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令；
程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行；
程序中存在很多对一定数据结构的操作，如数组操作，往往局限在较小范围内。

程序的局部性原理表明，从理论上来说，虚拟存储技术是能够实现的，而且在实现了以后应该是能够取得一个满意的效果的。成功案例：TLB、Cache。

虚拟页式存储管理 ¶

基本思路：当一个用户程序要调入内存运行时，不是将该程序的所有页面都装入内存，而是只装入部分的页面（0 个或多个），就可启动程序运行。在运行的过程中，如果发现要执行的指令或要访问数据不在内存，则发出缺页中断请求，系统在处理这个中断时，将外存中相应的页面调入内存，使得该程序能继续运行。

当内存空间不够用时，需要把页面保存在磁盘上（backing store，后备存储）；
内存物理页面称为 page frame，磁盘上的页面称为后备页面（backing frame）；
目的：提供一种错觉，内存的容量好像和磁盘容量一样大，且速度和内存一样快（理想状态）。

页表表项有哪些内容 ?

逻辑页面号，物理页面号。
驻留位（有效位）：表示该页是否在内存。若该位为 1，表示该页位于内存中，即该页表项有效，可以使用；若该位为 0，表示该页当前还在外存中，此时若访问该页表项，将导致缺页中断。
保护位：表示允许对该页做何种类型的访问，如只读、可读写、可执行等。
修改位：表明此页在内存中是否被修改过。当系统回收该物理页面时，根据此位来决定是否把它的内容写回外存。（如果没有修改过，那么磁盘中的与内存中的相同，内存中的可以直接扔掉）
访问位：如果该页面被访问过（包括读操作或写操作），则设置此位。用于页面置换算法。

OS 写 CPU 读：驻留位保护位，CPU 写 OS 读：修改位访问位。

在地址映射过程中，如果所要访问的逻辑页面 p 不在内存，则产生缺页中断 (page fault)。如何处理缺页中断？

如果在内存中有空闲的物理页面，则分配一页，设为 f，然后转第 4 步；否则转第 2 步；
采用某种页面置换算法，选择一个将被替换的物理页面 f，它所对应的逻辑页面为 p'。如果该页在内存期间被修改过，则需把它写回外存 (where?)；
对 p' 所对应的页表项进行修改，把驻留位置为 0；
将需要访问的页面 p 装入到物理页面 f 当中（进程被阻塞），并修改 p 所对应的页表项的内容，把驻留位置为 1，把物理页面号设置为 f；重新运行被中断的指令（PC 不变，该指令从头开始，而不是中断发生的这一时刻）。

PS：用户进程感觉不到缺页中断的发生（就像进程切换一样）。

页面置换算法 ¶

当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。目标：尽可能地减少页面的换进换出次数（即缺页中断的次数）。

最优页面置换算法（OPT，Optimal Replacement）：对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个淘汰
最近最久未使用算法 (LRU，Least Recently Used)，基本思路：当一个缺页中断发生时，选择最近最久未使用的那个页面淘汰。完美的 LRU 算法并不实用：在每次内存访问时，都需要去更新该页面访问时间（时间戳法）或调整各个页面的先后顺序（链表法和栈法），开销很大；缺乏硬件支持。可行的做法：对 LRU 算法的近似；在硬件的支持下，使用某种简单而快速的方法来寻找比较老（而非最老）的页面。
先进先出算法（FIFO，First-In First-Out），基本思路：选择在内存中驻留时间最长的页面并淘汰之。特点：性能较差，调出的页面有可能是经常要访问的页面。可能出现 Belady 现象。
最不常用算法（LFU，Least Frequently Used），基本思路：当一个缺页中断发生时，选择访问次数最少的那个页面淘汰。实现方法：对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加 1。在发生缺页中断时，淘汰计数值最小的那个页面。

缺页率 = 缺页次数 / 内存访问次数。

驻留集是指在当前时刻，进程实际驻留在内存当中的页面集合。（工作集是进程在运行过程中固有的性质，而驻留集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法）

多级页表 ¶

将逻辑地址的逻辑页面号进一步划分：一级索引，二级索引（每一级索引位数应该相同）。

举例：

以二级页表为例：假设逻辑地址为 32 位，页面大小为 4K。把逻辑地址划分为两个部分：逻辑页面号为 20 位，页内偏移地址为 12 位。
把逻辑页面号再进一步地划分为两个部分：10 位的字段 PT1，用来指向第一级页表当中所对应的页表项。10 位的字段 PT2，用来指向第二级页表当中所对应的页表项。

页面大小，决定页内偏移有多少位，2 的幂次关系。

每个页面有多少个页表项，决定每级索引有多少位，2 的幂次关系。

第 4 章 I/O 设备管理 ¶

I/O 硬件 ¶

交互方向分类：

输入设备：键盘，鼠标，扫描仪，麦克风。
输出设备：显示器，打印机。
输出 / 输出设备：磁盘，网卡。

数据组织分类：

块设备：以数据块作为信息的存储和传输单位，每个数据块都有一个地址，数据块之间的读写操作是相互独立的，如硬盘。
字符设备：以字符作为信息存储和传输单位，数据即字符流，无定位无寻址，如鼠标、键盘。

一个 I/O 单元由两部分组成：机械部分和电子部分（设备控制器或适配器）。

适配器可以插入到主板的扩充槽中，设备控制器集成在主板上或 I/O 设备内部。功能相同——设备与主机之间的连接与通信。

每个设备控制器都有一些寄存器用来与 CPU 通信。通过往这些寄存器中写入不同的值，OS 能命令该设备去执行发送数据、接收数据、打开、关闭等操作；OS 也能通过读取这些寄存器的值来了解设备的当前状态。此外，许多控制器还有一个数据缓冲区供 OS 读写。

控制寄存器，状态机寄存器，数据寄存器。

CPU 如何与设备控制器通信？

I/O 独立编址。给控制器中的每一个寄存器分配一个唯一的 I/O 端口（I/O port）编号，称为 I/O 端口地址，然后用专门的 I/O 指令对端口进行操作；这些端口地址所构成的地址空间是完全独立的，与内存的地址空间没有关系。

例如：IN R0 [4] 表示读入 I/O 端口地址为 4 的内容；MOV R0 [4] 表示读入内存地址为 4 的内容；
内存映像编址。

把所有控制器中的每个寄存器都映射为一个物理内存地址，专门用于 I/O 操作（功能上），对这些单元的读写操作即为普通的内存访问操作。端口地址空间与物理内存的地址空间统一编址，前者是物理内存的一部分，一般位于后者的顶端部分。

优点：编程方便；对普通内存单元的操作指令同样适用于 I/O 端口；无需专门的保护机制去防止用户进程执行 I/O 操作。

缺点：不能对控制寄存器的内容进行 cache，必须关闭。每一次都压迫判断访问的是内存还是 I/O。
混合编址。

对于设备控制器中的寄存器，采用独立编址的方法；而对于设备的数据缓冲区，采用内存映像编址的方法。

I/O 控制方式 ¶

程序循环检测方式：

在程序（设备驱动程序）中通过不断地检测 I/O 设备的当前状态，来控制 I/O 操作的完成。具体来说，在进行 I/O 操作之前，要循环地检测设备是否就绪；在 I/O 操作进行之中，要循环地检测设备是否已完成。从硬件来说，控制 I/O 的所有工作均由 CPU 来完成。也称为繁忙等待方式（busy waiting）或轮询方式（polling）。

缺点是进行 I/O 操作时一直占用着 CPU，浪费大量 CPU 时间。CPU 很快，而 I/O 设备很慢。

PS：I/O 控制与 I/O 操作不同，I/O 控制由 CPU 完成，I/O 操作由设备自己完成。

中断驱动方式：

当一个 I/O 设备完成任务时，它的控制器会通过总线向中断控制器发出一个信号，如果中断控制器接受了该信号，就把标明该设备的一个编号放在地址线上，并向 CPU 发出一个中断信号。 CPU 发现后就中断当前工作，并以该编号为索引去访问中断向量表，取出中断处理程序的起始地址，并在该程序运行后向中断控制器发出确认信号。

中断发生时，CPU 会暂停当前执行的程序，保留现场后自动执行相应事件的处理程序，处理完后再返回断点，继续执行被打断的程序。

直接内存访问方式：

直接内存访问 (Direct Memory Access, DMA) 方式：在硬件上需要一个 DMA 控制器。DMA 控制器独立于 CPU，可以直接去访问系统总线，它能代替 CPU 去指挥 I/O 设备与内存之间的数据传送，为 CPU 腾出更多时间。

I/O 软件 ¶

层次结构：

用户空间的 I/O 软件
设备独立的系统软件
设备驱动程序
中断处理程序
硬件

设备驱动程序：与具体的设备类型相关的，用来控制设备运行的程序。一般由设备生产商提供。通常是平台相关（如 Windows/linux），适合于特定的某个设备（如键盘）或某类设备（如 SCSI）。每一个 I/O 设备都需要相应的设备驱动程序，而每一个设备驱动程序一般只能处理一种设备类型。

设备独立的 I/O 软件（I/O 子系统）是系统内核的一部分，其任务是实现所有设备都需要的一些通用的 I/O 功能，并向用户级软件提供一个统一的接口。

为什么需要内核的 I/O 软件？

I/O 设备的种类繁多、功能各异，需要标准化接口
I/O 设备不可靠，如存储介质失效或传输错误
I/O 设备不可预测，且运行速度快慢不一

上层接口：

设备独立性：使得用户在编写程序、访问各种 I/O 设备时，无需事先指定特定的设备类型，各种类型的设备之间的差异由 OS 来处理，对用户是透明的。
统一命名：即用简单的字符串或整数的方式来命名一个文件或设备。例如在 Unix 当中，所有的文件和设备都采用相同的命名规则：路径名。
阻塞与非阻塞 I/O：当进程启动一个系统调用后，是立即返回还是被阻塞起来，直到 I/O 操作完成。

什么是阻塞与非阻塞 I/O？

阻塞：进程被阻塞起来，直到 I/O 操作完成。易于使用和理解。有些情形下不能满足要求
非阻塞：I/O 调用很快返回。异步性：当 I/O 操作进行时进程继续执行，当 I/O 操作完成时，I/O 子系统给进程发信号。调用者具有主动权。不易使用，多线程

下层接口：略。

接口映射：略。

用户空间的 I/O 软件：

库函数：如 C 语言里与 I/O 有关的库函数 write、read 等，它们实质上只是将它们的参数再传递给系统调用函数，并由后者来完成实际的 I/O 操作。
Spooling 技术：在多道系统中，一种处理独占设备的方法。假脱机技术（SPOOLing, Simultaneous Peripheral Operation On Line, 也称虚拟设备技术）可把独占设备转变成具有共享特征的虚拟设备，从而提高设备利用率。

块设备的驱动程序方案：

数据结构：请求队列（request queue）。
块设备驱动程序：上层函数，负责管理请求队列；底层函数，负责与硬件打交道，完成真正的 I/O。
I/O 请求的提交与真正实现是分离的。各个用户进程（通过内核）调用上层函数，提交 I/O 请求 (mak_request)，然后阻塞；底层函数则从队列中取出每个 I/O 请求，并完成之。
能对各 I/O 请求进行优化，如数据块重组。

存储设备 ¶

磁盘：

磁盘的访问过程：以扇区作为最小的寻址和存取单位。首先移动传动装置，通过它来移动磁头，从而定位正确的柱面。然后选中相应的磁头，等我们想要的扇区正好路过这个磁头正下方的时候，就可以对它进行访问了。

如何写一个字节？读－修改－写：读入包含该字节的扇区——修改该字节——把整个扇区写回到磁盘。

磁盘的访问是以扇区作为最小的寻址和存取单位，在访问一个磁盘扇区时，所需的时间主要有：

柱面定位时间：磁头在磁头臂牵引下，移动到指定柱面的机械运动时间；
旋转延迟时间：等待指定的扇区旋转到磁头的正下方所需的机械运动时间；它与磁盘转速有关，如：软盘转速可为 600rpm( 每分钟转速 )，硬盘可为 7,200rpm 至 10,000rpm；
数据传送时间：从指定扇区读写数据的时间。

硬盘的格式化可分为三个步骤，即低级格式化——分区——高级格式化。

低级格式化：标出磁道和扇区，在相邻的扇区之间有狭窄的间隙隔开。一个扇区的格式是：相位编码（preamble）＋数据区＋纠错码（ECC）。

相位编码：以某个特定的位组合模式开始，向硬件表明这是一个新扇区的开始。还包括柱面号、扇区号、扇区大小等类似信息；

数据区：由格式化程序确定其大小，一般 512；

纠错码：包含冗余信息，用来纠正读取错误。
分区：用分区软件把整个硬盘划分为若干个逻辑分区，每个分区可视为一个独立的磁盘。在多数计算机上，用第 0 个扇区来存放一些系统启动代码和一个分区表，记录了每个分区的起始扇区和大小。
高级格式化：对每一个逻辑分区，分别进行一种高级格式化（即通常的格式化操作），生成一个引导块、空闲存储管理结构、根目录和一个空白的文件系统。对不同的分区，可以使用不同的文件系统，如 FAT16、FAT32、NTFS 等。

闪存：

可读 / 可写
基本单元电路（存储细胞）为双层浮空栅 MOS 管，带电表示存入 0，不带电表示存入 1
速度快，无机械装置，无需柱面定位和旋转延迟，可用电气的方法快速地擦写
非易失型，在断电后不丢失信息
经久耐用（压力、温度、水），在嵌入式设备中得到广泛应用

NOR Flash，NAND Flash。

在一个嵌入式系统（如数码相机或摄像机）中，可能会用到哪些不同类型的存储器？

存放 BootLoader 的存储器，必须随机访问，其内容主要是代码，一般不会修改。非易失型。

可用 ROM 或 NOR Flash 实现
内存。程序必须装入内存执行。要求可读写、随机访问，速度要快。

可用 DRAM 实现
系统的固件放哪？可读可写，不需要随机访问，容量要大。

可用 NAND Flash 实现
用户产生的数据文件放哪？

NAND Flash

SSD 硬盘：

SSD（Solid-State Drive）：固态硬盘，一种固态存储设备，使用集成电路部件来永久地存储数据，外部接口与传统硬盘相同
SSD 的存储介质主要是 NAND flash，早期也有用 DRAM 的
优点：可靠、无噪声、读速快（总是快）
缺点：价格贵、写速慢、擦除次数有限

常见问题 :

SSD 硬盘需要碎片整理吗？

不需要，SSD 硬盘不需要机械寻址。
为了提高硬盘的访问速度，操作系统会在内存提供缓存功能，但由于 SSD 硬盘的访问速度比较快，所以可以减少缓存容量

错！要尽量减少 SSD 硬盘的擦写次数。
有了 SSD 硬盘后，可以疯狂地下载电影了

错！SSD 硬盘存放常用、速度慢及以读为主的内容，而不常用、速度快及频繁删除的内容尽量存放在机械硬盘上。

第 5 章文件系统 ¶

略。

操作系统（计算机系） 复习笔记 ¶

第 1 章 操作系统概述 ¶

第 2 章 进程管理 ¶