操作系统

边干边学 LINUX 内核指导

Chapter 1: Overview

OS 能干什么？

复用：将一个组件分给多个任务

CPU：时分复用 内存：空分复用

OS 提供最重要的能力是抽象

SQL 声明式语言——高度抽象

计算机系统组成

中断 - H/W　硬中断 - trap: 软中断 - errors (无意识的出错) - system calls

interrupt-Driven I/O Cycle

I/O Method： 同步-异步

Device-Status Table

Direct Memory Access

存储结构、层次

多核系统

OS operations - User Mode & Kernel mode (Supervisor Mode)

做这个区分是为了 Isolation

kernel mode 中运行的不只是 privilege instructions，但是后者只能在前者上运行

user mode -> kernel mode -> user mode

Multiprogrammed 的情况 需要 multiplex 复用

OS Structure

multiprogramming: 多道程序设计（运行）

同时加载入内存，不一定同时运行

multiprogramming 的原因是充分利用内存和 CPU 的能力，提高使用效率

• 批处理

Time Sharing (MultiTask)

将时间分配多个系统 多任务系统

在多个任务上轮流提供 CPU 运行，每个进程在很短时间内都能用到 CPU

多个用户使用同一台计算机的场景，提供非常好的交互性 interactivity

减少 response time

CPU Schedule

更多用在 server 而非移动端

Process Management 进程管理

创建进程——分配资源 进程是一个 active entity

线程——执行的序列

进程可以创建、删除、继承

提供同步、进程间见交互、处理死锁（deadlock）的机制

Storage Management

将物理的存储抽象为逻辑的存储单元—— file 文件

Storage Management 提供文件和文件系统的管理 存在磁盘的分区 partition 上

Mass-Storage Management

对于大量数据（磁盘）的管理

I/O Subsystems

OS Purposes

• Basic requirements for OS
  • sharing
  • isolation
  • interaction
• abstraction
• security
• performance
• range of uses

Chapter 2: Operating System Structure

OS Service

• user interface
• program execution
• I/O Operation
• File-System manipulation

System Calls

OS 服务的程序接口

高层语言

系统调用较为低级

API

可重用代码

Standard C Lib exmpl

kernel 空间搬到 user 空间

system call

pass the parameter in registers

types of system calls

process control, file management, device management,.....

都是 OS kernel 提供的代码

以函数形式被调用

机制和策略相分离

• Modules

loadable module

Other Structures

（Exokernel）定制化 library，作为 Kernel 和 Software 的中间

（Unikernel）将 kernel 静态地链接到 OS code （Application）—— boot 更快

Virtual Machines

本质是一种 abstract

单台主机抽象为多个、隔离的环境

实现了极端的层次化：

• Hardware（Host）
  • Virtual Machine Manager / Hypervisor （对标非虚拟机的 kernel）
    • Virtual Machine 1 （对标非虚拟机的进程，进程中运行了一个 OS）
      • 。。。。。。
    • Virtual Machine 2
      • kernel
        • process 1
        • process 2
        • 。。。。。。

hypervisor——type 1

hosted hypervisor——type 2 （通过硬件上的 OS 的 Application 运行 virtual machine）

Type 1 Hypervisor runs directly on the hardware to manage resources, but Type 2 Hypervisor runs as a software application within host OS.

上面两个 type 显然 type 1 更加高效

另：paravirtuallization——半虚拟化

virt I/O

实验中使用的 QEMU 可以看作 type 2

container 不是严格意义上的虚拟机，但使用了虚拟化的技术

containers 之间使用同一个 kernel，但在文件管理等方面是隔离的

Operating System Generation

• 启动

bootstrap program 鞋拔子程序/引导程序

stored in ROM ，能够定位到 kernel，加载到 Memory，开始运行

磁道 track 0

• OS 生成

bootstrap program 是谁写进去的？

做引导盘的工作（将 bootstrap program 写入 track 0）

Chapter 3: Processes

Section 3.1: Concept

job & process

process include： - code i.e. text field - program counter i.e. PC（跟踪当前运行到哪里了）——实际上是一个 register - stack——存入函数调用的参数、local variables 和返回地址 - data section——存放 global variables - heap——存放动态分配的内存

Process in Memory

![[cs/systems/operating_systems/fig-3-1.png]]

Address Space 地址空间—— max - 0

max： maxVA 最大虚地址

heap 和 stack 之间的区域：hole 空洞（实际上，空洞是非常大的，而不是像上图画的那样小）

真实情况是我们不会这样使用内存 ，因为空洞太大是一种不可接受的浪费

Process State

• new
• running
• waiting（挂起）
• ready
• terminated ---- 进程 已经完成

可以画成状态机的形式

![[fig-3-2.png]]

waiting 和 ready 过程中进程的代码没有在运行

以上是大致上的几个状态，实际上会非常的细分

waiting 无法进入running（只有 ready 可以进入 running）

这样设计的原因在后面给出

Process Control Block

进程相关的信息保存在 PCB 中，实际上可能不是一个 Block，总之在理论上可以用一个抽象的数据结构表示

information associated with processes - process state - prog counter - contents of CPU regs - CPU scheduling information - mem-management information - accounting information - I/O status information

Section 3.2: Process Schedule

Queues

用 queues 进行管理 PCB

• Job Queue ( all processes in the program )
• Ready Queue
• Various I/O Device Queue

进程的“换”本质上是换 PCB 的位置

一个队列代表一系列的 resource

处理器的等待队列：Ready Queue

representation of process scheduling：

![[fig-3-4.png]]

Schedulers

• long-term scheduler

发生在 queueing-diagram 的外部

将进程将外存搬到 ready queue 中（内存中）

• short-term —— 选出一个进程在下一个运行并分配 CPU

现在的计算机不再需要 long-term scheduler，由用户完成这部分的工作（long-term scheduler 成为历史概念）

![[fig-3-5.png]]

long-term 处理上图中从外部到内部的调度， short-term 处理从 ready queue 到 CPU 的调度。

另：medium-term scheduler

可以将进程换出到 swapping disk 中，缓解内存紧张；或者在 memory 空间紧张，高优先级的进程需要先被执行时，可以将低优先级的进程换出。

short-term 使用频率非常高，所以必须非常快；long-term 则频率低，可以不那么快

long-term 控制 degree of multiprogramming

• I/O bound process - 更多时间花在 I/O，many short CPU bursts
• CPU bound process - 更多时间在 computation，few very long CPU busrts

Context Switch

进程切换—— context switch

context-switch time is overhead

![[fig-3-6.png]]

Section 3.3: Operations on Process

Process Creation

(一个图：Process Creation)

fork() 后凭空多出一个 child process，然后作为一个独立的进程运行

parent_process_id

一次 fork() 为当前所有进程都创建一个子进程，总进程数 \(\times\) 2

Process Termination

从 child 到 parent output data (parent 等 child)（如果不等，则子进程变成 zombie）

OS 回收分配给进程的资源

子进程终止后 ，其 PCB 不会立即被释放，相关信息需要反馈给 parent 进程，然后 parent 进程调用 wait() 来获取这些信息，之后 PCB 才会被释放。否则子进程变成 zombie。

Section 3.4: Interprocess Communication

进程之间的合作使得不同进程能够影响对方的执行过程

• information sharing
• computation speedup ( multi-CPU )
• Modularity
• Convenience

一个抽象模型：producer-consumer problem

Todo

待完善：P-C Model

针对上述抽象模型，衍生出两种具体的模型分类：

• unbounded-buffer
• bounded-buffer

这里的 buffer 是指用来存储 producer 发出的信息的缓冲区。Unbounded 指的是这个缓冲区相对于发送的信息相比，不可能被占满（相对足够大）；相对的，bounded 指的是 buffer 可能在某时刻被占满。

进程间通讯：Interprocess Communication (IPC)

两个模型:

• Message Passing
• Shared Memory

Message Passing 需要通过不断的 system call 实现，所以 Shared Memory 效率更高。

Message Passing

对于 Message Passing，需要提供两种 interface: send(message) & receive(message)

直接通信：显式指定 send/receive 的 ID

这样，连接自动建立在恰好一对进程之间。

间接通信：通过 mailbox 进行 direct & receive

well-known mailbox

系统中称为端口 port

间接通信中连接可能建立在多个进程中。

Pipeline 管道

管道：用 | 分隔任意两个命令（进程），建立通信

对于一般的命令，前一个命令的输出提供给下一条命令作为输入。 （联想到 scikit-learn 中的 Pipeline 类）

但是实际上在不影响结果的情况下可以并发执行。

Shared Memory

例子：在一个进程中创建虚拟内存，然后创建子进程，父进程在共享内存中写入一个数据，子进程从中读取。

（上例并没有保证运行结果正确，因为无法保证父进程的写入发生在子进程之前——涉及同步问题）

Chapter 4: Threads

Section 4.1: Overview

异步非常重要

线程是 CPU 利用的基本单元。

同一进程的多个控制线程共享所有的 OS 资源和 code, data, files, 但是有自己的 stack 和 regs。

单一进程如果由多个线程控制，则可以一次执行多个任务。

在线程出现之前，进程是最小的 CPU 使用单元，但是其内部可能由多个子任务组成，无法做到内部的并行，所以将整个进程作为调度的单元是不合适的。线程就是为了解决这个问题而产生的，由 OS 来调度，代替进程作为最小的 CPU 利用单元。但是进程仍然是资源分配的最小单元。

thread_id

benefits: - responsiveness - resource sharing - economy - utilization of MP architecture

并发 concurrentcy：不断切换，但是串行（单核可用）

并行 parallelism：多核同时运行

线程占用内存小，上下文切换快

user thread & kernel thread

Section 4.3: Multithreading Models

many to one

one to one

many to many (A variation: two level)

Section 4.6: Threading Issues

• fork() and exec() System calls

Threads Cancellation: 在线程正常结束之前终止

• Asynchronous cancellation

暴力终止

• deferred cancellation

打上标签，让线程自己运行完剩下的部分后终止

Thread Pool: 一池子的线程，等待工作

分配到任务后开始运行，结束后也不会被 cancel 掉

主要用于需要同时、并发的大量线程的情形，减少为新请求创建线程的时间，增加了空闲的线程（一种空间换时间）。

（Thread 其他不讲了）

Chapter 5: CPU Scheduling

注意这里 Chapter 标题不是 Process Scheduling，也不是别的 Scheduling，而是 CPU 的 Scheduling。

这是因为在讨论 Scheduling 时，既有 Process，也有 Thread。只不过我们在本章大部分情况（且默认）讨论的是 Process 的调度，而 Thread 的调度本质上是类似的。

Section 5.1: Basic Concepts

进程中，CPU burst 和 I/O burst 交替进行。大部分的 CPU burst 的持续时间都非常之短，但是频率极高（周期极短）。这就要求 scheduler 和 context switch 要快。（这里与 short time scheduler 也相关）

CPU Scheduler 的任务就是从 ready queue 中选出一个进程/线程来执行。

调度的时机：

1. running -> waiting (主动放弃 CPU，如 System Call)
2. running -> ready (被动放弃，如 interrupt)
3. waiting -> ready (被动放弃，如 I/O 完成)
4. process terminate

可以基于此将调度分为 preemptive（抢占式，2 和 3） 和 non-preemptive（非抢占式，1 和 4）.

现代的 OS 基本上都是抢占式的。

• Dispatcher 指派程序

dispatch latency（从 P_0 executing，save state to PCB_0, 到 restore state from PCB_1, P_1 executing 的时延）

Secction 5.2: Scheduling Criteria

• CPU Utilitzation（CPU 利用率）
• Throughput（吞吐率）：单位时间完成任务的个数
• Turnaround Time（周转时间）time of execute a particular process，在 ready queue中等待、在 CPU 上执行和执行 I/O 所花费时间的总和
• Waiting Time（等待时间）在 ready queue 中等待的时间 （注意不是 waiting 状态的时间）
• Response Time（响应时间）从请求提交到第一个 response 生成所需的时间

给定 CPU 中待处理的任务，希望利用率越高越好，这样处理的时间最短；反之越低越好，因为希望能够接受更多的任务。

三个 time 也是希望越低越好。

Section 5.3: Scheduling Algorithms

我们可以用 Gantt Chart 展现进程调度的关系

First-Come, First-Serve (FCFS) Scheduling

直观上看，按照进程被分配到 CPU 的顺序依次响应。（FCFS: policy）

实现：FIFO Queue（mechanism）

优点：实现简便 缺点：平均等待时间较长

Example

Burst Time: 24, 3, 3

如果顺序响应，平均等待时间长 \((0+24+27)/3=17\)

如果按照 3, 3, 24 顺序，平均等待时间大大减少 \((0+3+6)/3=3\)

通常 FCFS 的平均等待时间不是最小的，并且当不同进程的 CPU Burst 差异很大时，不同的到达顺序对平均等待时间的影响比较大：当 CPU Burst 较短的进程有较长的 I/O Burst 时，它极有可能在长 CPU Burst 之后进入 Ready Queue，从而被调度的晚，这会增大 Average Waiting Time。也就是说，FCFS 是不够稳定的。

Info

一般衡量调度算法是看 Average Waiting Time，所以上面一直在讨论其长短。

Shortest-Job-First (SJF) Scheduling

这个 policy 是在 FCFS 下自然得出的。

两个版本：抢占的和非抢占的

在非抢占下，如果新到达的进程的 CPU Burst 比正在 CPU Burst 的进程还要小，也不会将其终止，而是等待其完成。

这里除了 Burst Time，还需考虑 Arrival Time （注意 preemptive 和 non-preemptive 的区别）

如果同时存在多个 CPU Burst 相同的进程，退化为 FCFS.

同样的，在计算 Average Waiting Time 也需要考虑 Arrival Time

在 preemptive 下，允许 剩余的 Burst Time 更小的进程打断当前进程，剩余的内容在同样的条件下重新启动运行。

preemptive 和 non-preemptive 的例子（见 Slides）

从效果来看，preemptive 的调度更加公平（防止先到的一个长进程一直占用 CPU）

然而，对于 preemptive，需要考虑的是“抢占”是否会导致原子性问题

回到 SJF 本身，显然从 AWT 的角度看，SJF 是最优的（离线最优）。

SJF 的致命问题是它无法在 CPU Scheduling 的层面实现，因为从 CPU Scheduler 的视角，在一个进程运行结束之前，不可能提前知道它的 Burst Time。

这样我们只能对 Burst Time 猜测，通常从历史推断。

exponential average（见恐龙书）

Priority Scheduling

每个进程有一个 Priority Number

必定优先运行 priority number 更高的进程。

这里也自然的分出 non-preemptive 和 preemptive

SJF 是 Priority Scheduling 的一个特例：

\[ Priority\ Number=Burst\ Time \]

Problem: Starvation

Solution: Aging - priority increases as time progresses

Round-Robin Scheduling

时间片轮转算法

类似 FCFS 加入 preemptive

定义一个小的时间片 time quantum

将 ready queue 看作一个环形队列，每次给当前进程至多一个 time quantum 的时间运行，超过则直接切换到下一个进程（不超过则可以提前结束，不必等待当前 time quantum 结束）。如此循环往复，直到所有进程都完成。

注意：新的进程和时间片结束时还没有运行完的进程，都加入到 ready queue 的末尾 。

新的进程和时间片结束时还没有运行完的进程同时加到 ready queue 的末尾，哪个先运行？

大部分 Burst Time 在 8ms 之下，所以将 time quantum 设置为 8ms 之下即可。

Warning

Time quantum 不能太小，否则 context switch 发生过于频繁，用于 context switch 的开销过大；也不能太大，否则退化为 FCFS.

Multilevel Queue Scheduling

将 Ready Queue 分为多个 Queue，分别使用 Scheduling Algorithm ( Multilevel 的实质 )

根据进程的性质分类，将其分为 foreground 和 background（或可以分的更细），应用不同的 policy，如 foreground 用 RR，background 用 FCFS。

另外，不同队列之间也需要 Scheduling 的机制，如 fixed-priority scheduling 等

对于 foreground，需要更好的交互性，用更合适的 RR；对于 background，不那么注重交互，适用批处理的 FCFS

Multilevel Feedback Queue

允许进程在不同队列中移动，根据 CPU Burst 进行分类，Burst Time 高的被赋予低优先级

Example

• \(Q_1:8 \text{ ms}\)，\(Q_2:16\text{ ms}\)，\(Q_3:FCFS\)

一开始认为一个进程需要足够的交互性，将其放入 \(Q_1\)，如果一个 time quantum 没有运行完，放入 \(Q_2\)；\(Q_2\) 中进程被运行当且仅当 \(Q_1\) 为空，\(Q_1\) 的新进程会抢占 \(Q_2\) 中正在运行的进程；\(Q_2\) 与 \(Q_3\) 的关系类似

Multilevel Queue 的根本动机

无论有没有 Feedback，根据不同的性质对进程进行分类，对于每一类使用不同的调度算法。

Section 5.5: Multi-Processor Scheduling

（略）

Section 5.6: Real Time Scheduling

指定一个 time out 时间，保证给定的任务可以在 time out 时间之内完成。

（后略）

• Soft Real-Time System

不保证关键进程在 Deadline 前完成，只保证其先于非关键（优先级更低）的进程执行

• Hard Real-Time System

严格要求进程必须在 Deadline 之前执行，超出时间的服务等同于没有服务。

Chapter 9: Main Memory

这里采用恐龙书中的章节排布，对应 Slides Chapter 8

讲课的顺序跳过了 Chap. 6, 7, 8，为了与 Lab 的进度相对应；另外这几章难度较大，放在后面讲

Section 9.1: Background

程序必须要存在内存中才能运行 within a process for it。

对于 CPU Register 来说，Main Memory 是很慢的。Cache 介于两者之间，Disk 在最下层。（回顾《组成》《体系机构》Memory Hierachy）

Main Memory 也叫 Primary Memory；相应地， Secondary Memory 指的就是 Disk 了。

一个现象

某一级的 Miss Penalty 往往比下一级的 Hit Time 大：原因是可能在下一级也 Miss，需要访问下下级。

目前，即便有了多核，Memory 的带宽仍然是不够用的（Bottleneck: 内存墙）

Basic Hardware

Memory 也需要 Isolation：通过 base 和 base+limit 两个界（实际上是 reg， 见 Section 9.2）实现分配给进程的内存

Address Binding

• Symbolic Address：符号地址，如函数名，Programmer 使用
• Relocatable Address：可重定位地址（例子：代码的地址全部用 程序起始位置+偏移量 的形式），Compiler 将 Symbolic Addr 绑定到 Relocatable Addr
• Absolute Address：绝对地址，如一个 linker 或 loader，Main Memory 使用

• Compile Time: 如果在编译时，编译器已经知道了进程在内存中驻留的位置，那么可以直接生成 Absolute Code. 当 Starting Location 变更时，需要重新编译。
• Load Time: 若编译时未能得知进程在内存中的位置，编译器生成 Relocatable Code，最终的绑定被推迟到 Load Time。这样，当 Starting Location 变更时，只需要重新加载 user code 并合并。
• Execution Time (Run Time): 如果进程在执行期间需要从一个内存段移动到另一个内存段，则绑定需要被延迟到 Execution Time ( 因为此前无法获知具体的地址 )

Logical Versus Physical Address Space

• Memory Management Unit

由 relocation registers (memory-address registers) 组成。

在运行时动态的进行重定位，将 logical address 映射到 physical address

Dynamic Loading & Dynamic Linking

Dynamic Loading 是一种内存管理技术，使得程序的某个模块只有在被调用时才被加载到内存，而不是程序开始执行时就加载全部的内容（所有模块）。

Dynamic Loading 的好处：提高内存利用率，特别是被加载的程序是大体量但是不频繁使用的情况，如 error 处理

通常通过用户手动加入这种功能。

Example

• loadlibrary()

Dynamic Linking: 当程序的某个模块在 Execution 的过程中被调用时，才被链接。

Dynamic Linking 通常用于 System Libraries，如 Standard C Language Library

目的是让 executable image file 变小，节约内存；当 Library 被更改（如升级换代）尤其是系统整个换掉，则不需要重新做编译、链接的工作（提高 Application 的可移植性）

另外，这样的 Lib 只需要加载一次，就可以在多进程间共享（这样的 Lib 称为 Dynamic Linked Libraries/Shared Libraries），进而节省了大量的内存开销。

Section 9.2: Contiguous Memory Allocation

将系统主存分为两部分，一部分给 OS（low memory），另一部分给 user process（high memory）

使用一对 REG 对一个进程空间进行管理：limit register + relocation register

relocation 包含最小物理地址的值，limit 包含逻辑地址的范围

这里第一步需要将 limit 与 logical address 比较，以区别非法访问。

分配内存的最简单方法之一是将进程分配给内存中大小可变的分区，其中每个分区可能只包含一个进程。操作系统保留一个表，指示哪些内存部分可用以及哪些部分已被占用。

问题是，最终，这个表中可能会出现大量不相连的 holes，即便加起来能容纳新的进程，但由于不相连，实际上是放不下的。这样内存就被 碎片化 了（fragmentation）。

• external fragmentation: 上述情况
• internal fragmentation: OS 分配的内存和实际上需要的内存大小不同（OS 分配的稍大）

填 hole 的三种策略： - First fit: 最先找到的可容纳的洞 - Best fit: 所有可容纳的洞中最小的那个 - Worst fit: 所有可容纳的洞中最大的那个

如何处理 fragmentation?

使用 compaction ( 压缩 ) 解决 external fragmentation: 移动进程，将所有 hole 拼在一起

缺点是正在移动的进程和新的进程无法被运行，代价非常大。

以上就是 contiguous allocation 的局限，进一步解决 fragmentation 的问题只能使用 non-contiguous 的方式

Section 9.3: Paging

Basic Method

Paging 是 non-contiguous allocation 的一种实现，将物理内存分为固定大小的 frame，将逻辑内存相应的分为 page

分配到的 page 所对应的 frame 可以散布在整个内存空间中（ 非连续的实质 ）

Paging 本身是 CPU 提供的机制，OS 只是利用之。

OS 维护一个 page table（每一个进程都有一个） 用于保存 page 和 frame 之间的映射关系。

CPU 生成的地址由 page number 和 page offset 组成，在 page table 中通过 page number 找到对应 frame，frame 加 offset 找到某一块内存。

\[ page\ size = 2^d \]

\[ the \ number \ of \ pages = the \ number \ of \ entries = 2^p \]

一般来说，page size 和 frame size 是相同的，其大小通常由硬件决定。

Paging 解决了 external fragmentation，即便 hole 仍然存在（internal fragmentation）。

p 和 f 的 bit 数量没有限制

Hardware Support

Page table 保存在内存中，通过 page-table base register 和 page-table length register 定位。这两个寄存器需要存在 PCB 中（与进程本身相关）

注意这里 PTBR 存的显然是物理地址，如存虚地址，还需要通过 PT 查找，但这是还没有访问到 PT，逻辑上不自洽（类似循环论证）

这样，一个进程如果需要访问内存，首先需要对 page table 访问，那么任何一次地址访问就会实际上引起两次内存访问，这是非常不经济的。因此可以参考 cache 的设计，添加一个 Translation Look-aside Buffer（转换旁视缓冲，快表，TLB），大概率上降低访问 page table 的开销。

TLB 储存形式：\((p,f)\)

在访问 PT 之前，先在 TLB 中尝试寻找，若 hit 则 OK，miss 则访问 PT。

注意 TLB 是可以 parallel 访问的。

不同进程的 TLB 也不同，因此在进程切换时 TLB 也要切换。这样，TLB 中还需要一个 Address Space Identifier，来区分这个 TLB 是属于哪个进程的。

Associative Lookup: \(\varepsilon\) (TLB 访问的代价) Memory Cycle: 1 Hit Ratio: \(\alpha\)

Effective Access Time:

\[ EAT = (1+\varepsilon)\alpha+(2+\varepsilon)(1-\alpha) = 2+\varepsilon-\alpha \]

有些指令会 flush 掉 TLB 的内容，这样新的页表才能生效。

Protection

Memory Protection 通过在 PT 中设置 Protection bits 实现。

在 PT 中加入一个 valid-invalid bit，来标识这个 entry 是否有效。

OS 通过设置有效位来实现对 page 访问的允许/禁止

除了有效位，还有例如 read-only，write-only，execution-only 等等。

Shared Pages

多个进程之间共同运行的代码（只读），拿来放在共享的 Page 里面，比如调用一个共同的函数：

call func() # 0xdeadbeef logical address

逻辑地址可以一样，物理地址可以不一样。

Section 9.4: Structure of the Page Table

Hierarchical Paging

多级页表

可能出现 PT 过大，查询时间过长的情况，并且占用物理内存过大。

将 PT 看作一个 Page，再加一级页表来管理原 PT 的分布，外层页表的 entry 中存放内层表的物理地址。

这样，地址空间上，就会将 page number 拆分为两个。

Linux 可以支持五级页表。

缺点是页表层级越多，访问内存的可能次数越多。解决方法仍然是使用 TLB

TLB 往往是很有效的，因为内存访问是局部性的，相邻的内存地址很大概率会在不久的将来被访问到。

Hashed Page Tables

考虑 hash 函数将 page number （大空间） 映射到一个 bucket 的序号（小空间），然后在对应的 bucket 中找到 frame number

当然 hash table 和 page-frame 的信息还是存在内存中，还是使用 TLB 来降低开销。

Inverted Page Table

倒排页表

整个系统只有一张页表，在每一个 entry 放入 pid，每有一个 frame 就有一个 entry。查找时直接查找内容（pid + page number）而不是像之前一样找 index.

好处就是只需要一张页表，减少页表的存储量，但是遍历页表的时间变大，典型的时间换空间。

hash 和 inverted 都适用于地址空间较大的情形。

Section 9.5 Swapping

当内存紧张的时候，将一些不太重要的进程换出内存，放到某处（backing store）暂存，之后再换回来。

Standard Swapping: 整个换出到硬盘中

Swapping with Paging: 分页式地换出进程

还有一点讲究：将虚地址连续的页 Page out 到连续的物理内存中。

Section 9.a: Segmentation

将进程 Serialization 后以 Segment 为单位对进程的内容进行传输。

由于进程的成员大小不相同，Segment 也一般是可变长的。

• Segmentation Architecture:
  • Logical Addr Composition: <segment_number, offset>
  • Segment Table: \(\{entry|entry=(base, limit)\}\)(Hardware: STBR, STLR)

• Protection: Validation bit, R/W/E, 存在 Segment Table 中

Code Sharing 发生在 Segment 层。

内存资源是动态分配的。

同样具有 External Fragmentation 的问题，是否存在 Internal Fragmentation 取决于分配的策略（是否留出富余）

能否将 Paging 和 Segmentation 结合一下？

• Segmentation with Paging

一个进程的逻辑地址空间分为两部分，第一部分是进程私有的，第二部分是进程间共有的。第一部分的信息存在 Local Descriptor Table (LDT) 中，第二部分的信息存在 Global Descriptor Tabel (GDT) 中。每一个 entry (descriptor of 8 bytes) 就是 segment 的信息如 base, limit 等。

local addr: \((selector=(s,g,p),offset)\)

• \(s[13]\): segmentation number
• \(g[1]\): segment 在 LDT 还是 GDT
• \(p[2]\): protection

这样得到一个 Linear Addr。

段页式提供更灵活的内存共享和保护机制，原因之一是一个 Segment 中的语义是几乎同一的。

Chapter 10: Virtual Memory

Section 10.1: Background

Virtual Memory 的目的是实现逻辑内存和物理内存之间的 Separation。

一个进程，不需要将其完整的放在物理内存中才能运行，这样就说系统具有 Virtual Memory（只需要全部在虚拟内存中即可），这使得逻辑地址空间可以比物理地址空间更大。

另外，Virtual Memory 还提供了物理内存在进程之间共享（如 System Libs, Shared Memories,fork()）。

Virtual Memory 不是一个物理实体，而是 kernel 提供的一系列抽象和 mechanism，来管理物理内存和虚地址。

通过请求式调页和请求式调段来实现。

如何做到 Virtual Memory 比 Physical Memory 还大？

首先正常访问 Physical Memory，当 miss 时，通过 OS 提供的 mechanism 从 disk 中将其取出，这样从用户的视角来看就跟内存变大了一样。（所以是一种 abstraction 而不是 physical object）

• Sparse Address Space: 逻辑地址空间中有大量的 holes

Section 10.2: Demand Paging

如果程序运行时在内存中找不到对应 page，发生 page fault（一种 trap），通过 Demand Paging 将其调到内存中，然后程序继续运行。

Basic Concepts

• Lazy Swapper: 只有在 page 被用到时才将其换到内存中。

\(\text{valid bit} = 0\) 可能表示 page invalid reference（非法访问），这时直接 abort

一个特例

\(\text{valid bit} =0\) 还可能表示 not in memory，这时如果仍然想访问这个 page，则需要 OS 提供在调页后将 \(\text{valid bit}\) 置为 1 的机制。

为了区分这两种情况，需要额外的标识符。

block size of frames 和 block size in back storage (disk) 必须相等，否则无法正确地将 page 换入内存。

• Page Fault 的原理图（可能是 load 也可能是 store）

步骤 2 在 OS 中完成判断是 page invalid 还是 not in memory.

步骤 4 可能没有 free frame 可用，这时需要通过 page replacement（Sec. 10.4） 选择一个 frame 换出到 disk 上，以腾出一个 free frame.

步骤 5 包括加入 frame number 和 setting the valid bit.

值得一提的是，在 OS 中有一个 Free-Frame List 来管理 free frames.

Performance of Demand Paging

Page Fault 使得 Page 的访问变得缓慢。

• Effective Access Time (EAT)

\[ EAT = (1-p) \times \text{memory access time} + p \times (\text{page fault service time}) \]

其中 \(page\ fault\ service\ time\) 包括处理 page fault 的所有时间：

$$

\begin{aligned} \text{page fault service time} = & \text{ service the page fault interrupt} \ + & \text{ swap out time} \ + & \text{ swap in time} \ + & \text{ restart overhead} \ \end{aligned} $$

\(p\) 是 page fault rate，显然希望其尽可能小。

Section 10.3: Copy-on-Write

fork() 时，parent 和 child 进程共享同一份内存空间，直到其中一个进程对某个 page 进行写操作时，才将该 page 复制一份给该进程使用（copy-on-write, COW）。

                       

• Memory-mapped Files (Sec. 13.5)

通过将文件映射到内存中，使得对文件的访问变得像对内存的访问一样。

Section 10.4: Page Replacement

Basic Page Replacement

Page Replacement 发生在 page fault (not in memory) 且没有 free frame 的情况下，需要选择一个 frame 作为 victim 换出到 disk 上，以腾出一个 free frame.

对于在内存中没有更改的page，由于可以在外存中找到完全相同的副本，因此可以直接丢弃而不需要写回到外存，只有那些在内存中被修改过的 page (dirty page) 作为 victim 时才需要被写回到外存中。这样，很自然地，我们可以使用一个 dirty bit 来标识 page 是否被修改过，从而减少写回外存的开销。

另外，victim 的选择是非常重要的，这关系到 page fault rate 的高低。换言之，我们不希望一个页面在被换出后不久又被换入，这样就白白增加了开销。Page Replacement Algorithm 的目标就是尽可能地减少上述情况的发生，从而减少 page fault rate。

让替换算法在一系列内存访问上，计算 page fault rate，从而衡量其好坏。一般来说，需要给出一个 address sequence。这个序列只需要看 page number 即可（reference string），忽略 offset。这样，对于对相同 page 的连续访问可视为单次访问。

Firstst-In, First-Out (FIFO) Algorithm

FIFO 是最简单的 page replacement algorithm.

维护一个 queue，最先进入内存的 page 最先被替换掉。

Page fault 和 Page Replacement 的区别在于，一开始（冷启动）时，内存中没有 page，此时发生 page fault，但不需要进行 page replacement，因为没有 page 可以被替换掉。

Example

Slides 中展示了一个例子，对于相同的 reference string，4 frames 的 page fault 数量比 3 frames 的还要多。

上例的现象称为 Belady's Anomaly，产生原因是使用了一个特殊的 reference string（在再次被访问之前恰好被替换出内存）

Optimal Page Replacement

选择在未来最长时间内不会被访问的 page 作为 victim.

这是理论上最优的 page replacement algorithm，但实际上无法实现，因为无法预知未来的内存访问情况。

如何证明 Optimal 是最优的？

假设有一个算法 A，比 Optimal 更优。考虑 A 和 Optimal 在某一 reference string 上的第一个不同的选择，假设 Optimal 选择了 page P1，而 A 选择了 page P2。由于 Optimal 选择了未来最长时间内不会被访问的 page，因此 P2 必定会比 P1 更早被访问到，这样 A 就会在未来比 Optimal 产生更多的 page fault，矛盾。

LRU Page Replacement

• Least Recently Used (LRU) Page Replacement

选择内存中在过去最长时间内最少被访问的 page 作为 victim。

这样选择的理由是， 过去没有被访问的 page 很可能在未来也不会被访问。这是对 Optimal 的一种近似。

实现思路之一

在 PTE 中维护一个 counter，每次访问 page 时，将全局的 time stamp 赋值给该 counter。在需要进行 page replacement 时，选择 counter 最小的 page 作为 victim。

实现思路之二

使用一个 stack 来维护 page 的访问顺序。每次访问 page 时，将其从 stack 中移除并压入栈顶。在需要进行 page replacement 时，选择栈底的 page 作为 victim。

LRU-Approximation Page Replacement

由于 LRU 的实现开销较大，通常使用一些近似算法来实现。使用一个 reference bit 来标识 page 是否被访问过。在需要替换 page 时，扫描内存中的 page，选择 reference bit 为 0 的 page 作为 victim. 如果 reference bit 为 1，则将其清零，并继续扫描下一个 page。

问题是，可能存在多个 reference bit 都为 0 的情况。

• Additional-Reference-Bits Algorithm

为每个 page 维护一个 8-bit 的 shift register，每次时钟中断时，将 reference bit 的值右移一位，并将 reference bit 的值放入最高位。这个 shift register 保存了 page 在近 8 个时间段的使用记录。在需要进行 page replacement 时，选择 shift register 值最小的 page 作为 victim。

• Second-Chance Algorithm

也叫 Clock Algorithm

仍然需要 reference bit，将所有的 page 组织成一个环形链表，类似时钟的指针，每次需要进行 page replacement 时，检查当前指针所指向的 page 的 reference bit。如果 reference bit 为 0，则选择该 page 作为 victim，并将指针移动到下一个 page。如果 reference bit 为 1，则将其清零，并将指针移动到下一个 page，继续检查，直到找到 reference bit 为 0 的 page。

• Enhanced Second-Chance Algorithm

结合 reference bit 和 dirty bit，将 page 分为四类：

1. (reference bit = 0, dirty bit = 0)：最优先被替换
2. (reference bit = 0, dirty bit = 1)：次优先被替换
3. (reference bit = 1, dirty bit = 0)：再次优先被替换
4. (reference bit = 1, dirty bit = 1)：最后被替换

在进行 page replacement 时，首先扫描第一类 page，如果存在则选择一个作为 victim. 如果不存在，则扫描第二类 page，以此类推。如果在扫描过程中遇到 reference bit 为 1 的 page，则将其清零，并继续扫描。

Counting-Based Page Replacement

维护一个计数器，记录每个 page 被访问的次数。

• Least-Frequently-Used (LFU) Page Replacement
• Most-Frequently-Used (MFU) Page Replacement

两者都有一定道理。

Section 10.5: Allocation of Frames

讨论在各个进程之间分配固定数量的可用内存问题。

两种主要的 allocation schemes:

• fixed allocation: 每个进程分配固定数量的 frames
• proportional allocation: 按照进程的大小或优先级分配 frames

Minimum Number of Frames

每个进程至少需要有足够的 frames 来存放其所有的指令和数据，否则会导致频繁的 page fault，甚至无法运行。

最小帧数通常由体系结构定义。

Allocation Algorithms

• Equal Allocation

每个进程分配相同数量的 frames，不能整除的部分用作 free-frame buffer pool

• Proportional Allocation

按照进程的优先级来分配 frames，page fault 时，要么选择自己的 frame 当作 victim，要么选择优先级低的进程的 frame

Global versus Local Allocation

对于 Page Replacement，考虑可以跨进程（Global）从 frame 全集中选择 victim，还是只能在本进程内选择（Local）。

Global 的问题是，可能导致难以预测的 page fault rate，并且一个进程控制不了自己的 page fault rate（可能被被其他进程影响）。

Section 10.6: Thrashing

如果一个进程没有充足的 pages，就会频繁地发生 page fault，降低 CPU utilization（进程需要经常进入 I/O device queue 来完成 page fault service 要求的 I/O 操作），但 ready queue 变得很空，这样 OS 就会认为 CPU utilization 低，从而启动更多的进程，进一步加剧了问题。

• 这种现象称为 Thrashing（主要指一个进程一直忙于 pages in & out）

Cause of Thrashing

demand paging 可以工作的原因是：Locality Model

locality 指的是进程在某一小段时间访问到的所有资源的总和。

进程在 locality 之间切换。

locality 之间可能重叠（overlap）

如果所有 locality 的总和大于物理内存大小，则会发生 thrashing。

限制 thrashing 方法之一是使用 local replacement algorithm。 但是根本上，需要确保每个进程有足够的 frames 来容纳其当前的 locality，才能避免 thrashing。

Working-Set Model

定义 working set window \(\Delta\)，即最近 \(\Delta\) 时间内访问过的 page 的集合，称为 working set。

这个 \(\Delta\) 就是 locality 的时间跨度。

Working Set Size (WSS) 是 working set 中 page 的数量。

统计 $$ D = \sum_{i=1}^{N} WSS_i $$ ，如果 \(D >\) total number of frames，则可能发生 thrashing.

追踪 working set 的方法之一是在 page 中维护一些 bits，如果在 working set 中则置为 1；每隔一段时间（clock interrupt）将 reference bit 置为 0。

Page-Fault Frequency

Memory Mapped Files

Section 10.8: Allocating Kernel Memory

kernel memory 要求分配出来的 memory 在物理上也是连续的。

Buddy System

用于管理大块的、连续的内存。

Chapter 6: Process Synchronization - Synchronization Tools

这里仍然采取恐龙书中的章节排布，Slide 将 Chap.6, 7 合并为一章，所以 Chap.7 之后的章节号对不上

Section 6.1: Background

• concurrency & parallelism

两个进程在时间片上确确实实地同时运行，叫做并行（parallelism）；而两者仅仅是可能存在重叠，而不要求完全对齐地同时运行，叫做并发（concurrency）。

并行一定是并发的，但并发不一定是并行的。

Hint

回顾之前在 Sec.3.4 中提到的 Producer-Consumer Model，为了填充所有的 buffer，我们引入了一个 counter

counter 的自增和自减的整个过程中，对于其内部的多条指令，可能存在两个进程同时操作 counter，从而导致 counter 的值不正确，并且执行的结果取决于访问发生的特定顺序，称为竞态条件（race condition）。

恐龙书 Sec.6.1, P259 展示了一个因竞态条件导致 counter 值错误的例子。

竞态条件是指某段内存被多个进程同时访问，并且至少有一个进程在写入该内存时的情况。

Section 6.2: The Critical-Section Problem

设计一种 Protocol，使得在进程访问一段内存之前需要获得某种准入资格，从而保证同一时刻只有一个进程可以访问该内存，从而避免竞态条件。

• Critical Section: 访问共享资源的代码段
• Remainder Section: 与共享资源无关的代码段

From Quiz: 注意 Critical Section 本身不是一种 Synchronization Mechanism！

与之对应的，Critical Resource 就是指这个被共享的数据段

对于不同的进程，其 Critical Section 可能不同。

这也侧面说明了 Critical Section 是一个抽象模型，而不是物理上的一段代码。

另一个 Critical Section Problem: next_pid()

要解决 Critical-Section Problem，需要满足以下三个条件：

1. Mutual Exclusion: 同一时刻只能有一个进程在其 Critical Section 中运行
2. Progress: 如果没有进程在其 Critical Section 中运行，并且有一些进程想要进入其 Critical Section，则只有那些不在其 Remainder Section 中执行的进程才能参与决定下一个将进入其临界区的进程，并且不能无限期地推迟
3. Bounded Waiting: 对于每个进程，必须存在一个上界，限制在该进程进入其 Critical Section 之前，其他进程可以进入其 Critical Section 的次数

Section 6.3: Peterson's Solution

Peterson's Solution 是一个经典的解决 Critical-Section Problem 的软件方案。

一些前提假设：

• 只有两个进程
• load 和 store 是原子的
• 两个进程共享两个变量：
  • bool flag[i]: 进程 i 是否想要进入其 Critical Section
  • int turn: 指示哪个进程的优先级更高（轮到哪一个进程）

// process i
while(true) {
    flag[i] = true; // 想要进入临界区
    turn = j;       // 让另一个进程优先
    while (flag[j] && turn == j); // 等待
    // Critical Section
    flag[i] = false; // 离开临界区
    // Remainder Section
}

• Mutual Extension: 由于 turn 是共享的，所以满足
• Progress: 如果两个进程中只有一个想进入，则想进入的必能进入；若两个进程都想进入，则 turn 决定了谁先进入；
• Bounded Waiting: 由于 turn 的存在，另一个进程最多只能进入一次（如果想要进入，则由于 flag 的存在，必然进入循环，而无法进入 critical section）。

Section 6.4: Hardware Support for Synchronization

Hardware Instructions

原子操作由 disable interrupts 实现，尤其是在 critical section 期间。

• TestAndSet()

bool TestAndSet(bool *target) {
        bool rv = *target;
        *target = true;
        return rv;
}

如果 *target 原本是 false，则将其置为 true 并返回 false；否则返回 true。注意这个函数传入的是地址，所以函数外部 target 的值也会被修改。

如果有多个进程同时调用 TestAndSet()，则只有一个进程会成功地将 *target 置为 true 并返回 false，其他进程都会返回 true。

为了离开 critical section，需要将 *target 重新置为 false，使用简单的 store 即可。

while(true) {
    while(TestAndSet(&lock)); // 等待
    // Critical Section
    lock = false; // 离开临界区
    // Remainder Section
}

逐一验证三个条件：易知 Mutual Exclusion, Progress 满足，但是 Bounded Waiting 不一定满足，因为前面离开临界区的进程可能重新回来与剩下的进程竞争，而 TestAndSet() 并不保证公平性。

• Swap()

void Swap(bool *a, bool *b) {
        bool temp = *a;
        *a = *b;
        *b = temp;
}

Swap() 交换两个变量的值，令其也是一个原子操作。

while(true){
    key = true;
    while(key){
        Swap(&key, &lock);
    }
    // Critical Section
    lock = false; // 离开临界区
    // Remainder Section
}

这个 solution 本质上与 TestAndSet() 相同，都是尝试对一个 lock 变量进行原子操作，从而实现 mutual exclusion。

swap 还是比较实用的。

• compare_and_swap()

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected) {
        *value = new_value;
    }
    return temp;
}

如果 *value 等于 expected，则将其置为 new_value 并返回原值；否则不修改 *value，直接返回原值。

while(true){
    while(compare_and_swap(&lock, 0, 1) != 0); // 等待
    // Critical Section
    lock = 0; // 离开临界区
    // Remainder Section
}

这个 solution 也与 TestAndSet() 相似，也不能保证 bounded waiting。

• bounded waiting with compare_and_swap()

while (true) {
    waiting[i] = true;
    key = 1;
    while (waiting[i] && key == 1) {
        key = compare_and_swap(&lock, 0, 1);
    }

    waiting[i] = false;
    // Critical Section

    j = (i + 1) % n;
    while (j != i && !waiting[j]) {
        j = (j + 1) % n;
    }
    if (j == i) {
        lock = 0;
    } else {
        waiting[j] = false;
    }

    // Remainder Section
}

在实际工程中，往往不对 bounded waiting 过于苛求，而是使用更为简洁的方案来实现 mutual exclusion 和 progress。

Section 6.5: Mutex Locks

Mutex Lock 是一种提供 mutual exclusion 的机制，以解决 Critical-Section Problem。

互斥锁是一个 boolean 变量，来表示锁是否是 available，这个变量就是 lock

两个 原子 操作：aquire(lock) 和 release(lock)（原子性假设）

这种解决机制要求 busy waiting，即进程在等待锁时不断地检查锁的状态，而不释放 CPU 资源，这种现象叫做 spinlock（自旋锁）。

从语义上来说，这两个操作的代码：

void acquire() {
    while(!available)；// busy waiting
    available = false;
}

void release() {
    available = true;

一种 spinlock 的实现：

acquire(struct spinlock * splk) {
    for(;;) {
        if (lk->lock == 0) {
            lk = 1;
            break;
        }
    }
}

原子性的含义是，一旦开始执行 acquire() 或 release()，就不会被中断，直到执行完毕。

release 可以用简单的 store 实现，困难在于这种写法的 acquire 难以保证原子性。

一种自然的想法是利用 Hardware Instructions.

一个利用 TestAndSet() 实现的 mutex lock：

acquire(struct spinlock * splk) {
    pushoff();

    while(__sync_lock_test_and_set(&splk->lock, 1)); // busy waiting
    __sync_synchronize();

    lk->cpu = thiscpu;
}

其中 __sync_lock_test_and_set() 是 RISC-V 中的 amoswap.w.aq 指令的内建函数，能够实现原子性的 TestAndSet() 功能。

这样，就可以使用 acquire() 和 release() 来解决 Critical-Section Problem.

Section 6.6: Semaphores

Semaphore: 信号量，是一个同步工具。

Semaphore \(S\) 是一个整数，支持两个原子操作：wait() 和 signal()

wait(S) {
    while S <= 0; // busy waiting
    S = S - 1;
}

signal(S) {
    S = S + 1;
}

可以理解为，wait 消耗了信号量 \(S\)，而 signal 则增加了信号量 \(S\)。

这两个操作也被要求是原子的。

理论上来说，\(S\) 可能是负的；但实际上，只要不将 \(S\) 初始化为负数，并且只通过 wait 和 signal 来修改 \(S\)，则 \(S\) 永远不会是负数。

以上就是 Semaphore 的基本定义。

细分：

• Binary Semaphore: 取值只能是 0 或 1 的 Semaphore，本质上等同于 Mutex Lock
• Counting Semaphore: 取值可以是任意非负整数的 Semaphore

利用 Semaphore 的机制提供 Mutual Exclusion:

Semaphore S; // initialize S = 1
wait(S);
/// Critical Section
signal(S);

这个互斥的实现是非常简单的。

Semaphore Usage

一种常见的需求：希望语句 \(S_1\) 在语句 \(S_2\) 之前执行。

// initialize S = 0

// Process P1
S1;
Signal(S);

// Process P2
Wait(S);
S2;

注意这里需要将 \(S\) 初始化为 0。这样，只有当 \(S_1\) 执行完毕后，\(S_2\) 才能执行。

这就说明信号量需要有合适的初始值，才能实现同步的功能。

一个有趣的例子（笑）

厕所里有四个坑位，每一个坑位都需要一把钥匙，每人拿一把才能进入对应的坑位，这样就避免了多个人同时进入一个坑位 ((

如果要应用 Semaphore，其值应当表示当前空闲的坑位数量。自然地，初始化为 4。

每个人需要进入时，wait(S)，离开时，signal(S)。

一个进一步的思考是，假设四个坑位的锁是不同的，与某把钥匙对应，这样就需要四个 Semaphore，每个 Semaphore 初始化为 1。同样，每个人需要进去，只能指定一个坑位 wait(S_i)，离开时 signal(S_i)。

然而，Semaphore 的上述实现仍然存在 busy waiting 的问题。

Semaphore Implementation

一个 busy waiting 的例子：

struct semaphore {
    struct spinlock lock;
    int count;
};

void wait(semaphore *s) {
    while(s->count == 0) ;
    acquire(&s->lock);
    s->count--;
    release(&s->lock);
}

void signal(semaphore *s) {
    acquire(&s->lock);
    s->count++;
    release(&s->lock);

对于写操作，使用互斥锁保护；读操作则不影响。

然而，如果执行 signal 很少，大部分进程都在 wait，浪费了 CPU 资源。

希望 wait() 和 signal() 能够阻塞进程，而不是 busy waiting。

将 Semaphore 视为一个设备，加入一个等待队列（wait queue），具体来说是一个指向 PCB 链表的指针。

另外，还需要两个基本的系统调用：

• sleep(): 将当前进程放入等待队列
• wakeup(): 唤醒一个等待队列中的进程

只要系统支持上面两个调用，就可以实现阻塞式的 Semaphore:

typedef struct {
    int value;
    struct process *list;
} semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // add this process to S->list
        sleep();
    }
}

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // remove a process P from S->list
        wakeup(P);
    }
}

一个细节是，如果 value 小于等于 0，则必然引起上下文切换，带来代价。

如果 critical section 很短，则进行上下文切换不经济，可以考虑 busy waiting 的实现；否则，使用阻塞式的实现更好。

另外还有 wait/signal 式的 busy waiting:

void wait(semaphore *s) {
    while(s->count == 0) ;
    sleep(s);
    acquire(&s->lock);
    s->count--;
    release(&s->lock);
}

void signal(semaphore *s) {
    acquire(&s->lock);
    s->count++;
    wakeup(s);
    release(&s->lock);

这种实现的问题是，在 wait() 加锁之前的操作不是原子的。如果将加锁提早至 while 之前，则进入 sleep 时会持有锁，导致死锁。

一种解决是，给 sleep 加上一个 &s->lock 的参数，使得 sleep 在将进程标记为正在 sleep，放入等待队列之后释放锁。同样地，对于 wakeup，也需要一个 &s->lock 参数，使得 wakeup 在唤醒进程时获得锁（加锁）。

Section 6.8: Liveness

Deadlock

一种使用 waiting queue 实现的 semaphore 可能会导致这样的情况：两个或多个进程无限期地等待仅由其中一个等待进程引起的 event，这里指的尤其是 signal() 操作的执行。当达到这种状态时，称这些进程被死锁了。

• 另：Starvation

见 slides

Chapter 7: Process Synchronization - Synchronization Examples

Section 7.1: Classic Problems of Synchronization

• 本节讨论并发控制问题这一大类中的一些经典同步问题

The Bounded-Buffer Problem

考虑 \(N\) 个 Buffer，每一个可以容纳一个 item.

考虑 Producer-Consumer Problem，使用三个 Semaphore 实现同步：

• mutex: binary semaphore, initialized to 1
• empty: counting empty slots, initialized to N
• full: counting full slots, initialized to 0

Producer 检测empty，Consumer 检测 full，并且都使用 mutex 来保护对 buffer 的访问。

• Producer:

while(true) {
    // produce an item

    wait(empty);
    wait(mutex);

    // add the item to the buffer

    signal(mutex);
    signal(full);
}

• Consumer:

while(true) {
    wait(full);
    wait(mutex);

    // remove an item from the buffer

    signal(mutex);
    signal(empty);

    // consume the removed item
}

On-Course Exercise:

三个进程 \(P1\)、\(P2\)、\(P3\)互斥使用一个包含 \(N\)（\(N>0\)）个单元的缓冲区。 \(P1\) 每次用 produce() 生成一个正整数并用 put() 送入缓冲区某一空单元中；\(P2\) 每次用 getodd() 从该缓冲区中取出一个奇数并用 countodd() 统计奇数个数；\(P3\) 每次用 geteven()从该缓冲 区中取出一个偶数并用 counteven() 统计偶数个数。 请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

Semaphore mutex = 1;
Semaphore empty = N;
Semaphore even = 0;
Semaphore odd = 0;

// P1

while(true) {
    int integer = produce();

    wait(empty);
    wait(mutex);

    put();

    signal(mutex);

    if (integer % 2 == 0) {
        signal(even);
    } else {
        signal(odd);
    }
}

// P2

while(true) {
    wait(odd);
    wait(mutex);

    int odd_num = getodd();

    signal(mutex);
    signal(empty);

    int count = countodd();
}

// P3

while(true) {
    wait(even);
    wait(mutex);

    int even_num = geteven();

    signal(mutex);
    signal(empty);

    int count = counteven();
}

The Readers-Writers Problem

• 背景： 有一个共享数据区，允许多个进程同时读取，但写入时必须是独占的。

进程可以分为两类：

• Reader：只读
• Writer：读写

互斥性来源于写操作，因此需要为写操作定义 Semaphore。

Semaphore wrt = 1; // for writers

// writer
while(true) {
    wait(wrt);
    // writing
    signal(wrt);
}

对于 Readers，多个 Reader 可以同时读取，与一个 Reader 等效。可以将这个等效的单个 Reader 与 Writer 竞争，这个竞争显然是互斥的。这个等效 Reader 从若干 Reader 中选举而出，一个简单的实现是将第一个 Reader 作为等效 Reader，最后一个 Reader 离开时释放互斥锁。

// reader

while(true) {

    wait(mutex);
    readcount++;
    if (readcount == 1) {
        wait(wrt); // first reader locks the writers
    }
    signal(mutex);

    // reading

    wait(mutex);
    readcount--;
    if (readcount == 0) {
        signal(wrt); // last reader unlocks the writers
    }
    signal(mutex);
}

The Dining-Philosophers Problem

五个哲学家围坐在一张圆桌旁，圆桌中间有一大碗饭，每个哲学家有一个碗，两个哲学家之间有一把叉子。每个哲学家需要两把叉子才能从大碗中拿饭、吃饭，且只能使用与相邻的哲学家之间的叉子。每个哲学家可以处于三种状态之一：思考、饥饿、吃饭（包括打饭）。

不妨设哲学家 \(i\) 的左叉子为 \(i\)，右叉子为 \((i+1) \mod 5\)。

自然地，使用五个 binary semaphore 来表示五把叉子的状态（available or not）。

// philosopher i

while(true) {
    wait(fork[i]); // pick up left fork
    wait(fork[(i+1) % 5]); // pick up right fork

    // eating

    signal(fork[i]); // put down left fork
    signal(fork[(i+1) % 5]); // put down right fork
}

这样设计可能产生的问题： 可能导致死锁（deadlock），因为五个哲学家可能同时拿起左叉子，等待右叉子（右边人的左叉子），从而形成循环等待。

一种简单的避免这个问题的方法是，加入一个 Semaphore room = 4，表示最多允许四个哲学家同时进入餐厅，然后用 wait(room)-signal(room) 逻辑包住原来的 wait-signal 逻辑。这样至少会有一个哲学家能够同时拿到两把叉子，从而避免死锁。

另一种方法：奇数号哲学家先拿左叉子再拿右叉子，偶数号哲学家先拿右叉子再拿左叉子。这样就避免了循环等待。

另一种方法：哲学家总是先拿编号较小的叉子，再拿编号较大的叉子（对于 4 号哲学家，先拿 0 号叉子）。这样也避免了循环等待。

另一种方法：将 entry section 中的一部分设计成 critical section：进入第一个 CS，如果不能同时取到两个叉子，则退出 CS 并等待一段时间后重试；否则，进入 eating 的 critical section。这样就避免了死锁。

left = i;
right = (i + 1) % 5;
while(true) {
    while(true) {
        wait(mutex);
        if (!fork[left] && !fork[right]) {
            fork[left] = true;
            fork[right] = true;
            break;
        }
        signal(mutex);
    }
    signal(mutex);
    // eating

    /* ... */

    fork[left] = false;
    fork[right] = false;

}

这个方法的问题是，如果某个哲学家的左边和右边相邻的哲学家总是先于他拿到叉子，则该哲学家可能一直无法吃饭，导致饥饿（starvation）。用 Critical Section 的条件来说，这个方法不能保证 Bounded Waiting。

其他的方法大多也都是围绕着解决一开始提出的死锁来设计的。

《恐龙书》本章其他小节介绍了同步在现实中的应用，课上没讲，这里不做摘录。

Chapter 8: Deadlocks

• Deadlock Problem

现有一个进程的集合，每个进程持有一些资源，并在等待其他进程持有的资源。

这种情形下就可能形成 Deadlock.

• Bridge Crossing Example

Section 8.1: System Model

建立一个模型。

现有 \(R_1, R_2, \ldots, R_m\) 种类型的资源，类型 \(R_i\) 有 \(W_i\) 个实例，\(\forall i = 1,2,\ldots,m\)。

每一个进程按如下方式利用这些资源：

• request: 请求资源
• use: 使用资源
• release: : 释放资源

以 memory 为例，先 malloc()，然后使用（进行一些操作），最后 free()；对于文件，先 open()，然后使用（读写文件），最后 close()。

Section 8.3: Deadlock Characterization

Necessary Conditions for Deadlock

满足以下条件的进程集合 \(\{P_1, P_2, \ldots, P_n\}\) 形成了一个 deadlock:

• Mutual Exclusion: 存在一个资源，只能被一个进程使用
• Hold and Wait: 每个进程至少持有一个资源，并且正在等待其他进程持有的资源
• No Preemption: 资源不能被强制从进程中剥夺，而是必须在进程完成其任务后，由进程自己（voluntarily）释放
• Circular Wait: 存在一个进程的子集，且存在其一个排序，使得 \(P_i\) 正在等待 \(P_{(i+1) \mod n}\) 持有的资源

注意：要发生死锁，这四个条件必须同时满足

（尽管这四个不是相互独立的，例如 Circular Waiting 蕴含 Hold and Wait）

Resource-Allocation Graph

使用资源分配图来表示系统中进程与资源的分配情况。

• 节点（Node）: 进程节点（Process Node）和资源节点（Resource Node），即：

\[ \begin{aligned} V & = \{P, R\}, \\ P & = \{P_1, P_2, \ldots, P_n\}, \\ R & = \{R_1, R_2, \ldots, R_m\} \\ \end{aligned} \]

• 边（Edge）: 请求边（Request Edge）和分配边（Assignment Edge），即：

\[ \begin{aligned} E & = \{E_{request}, E_{assignment}\} \\ \end{aligned} \]

• 请求边：从进程节点指向资源节点，表示进程正在请求该资源；
• 分配边：从资源节点的 一个实例 指向进程节点，表示该资源已经分配给该进程。

对于 多实例的资源，在考虑resource-allocation graph 中是否存在死锁时，不要忘记 assignment edge 是可以因 release 而被消除的，进而即便有 circular wait，也可能不存在 deadlock。

Section 8.4: Methods for Handling Deadlocks

处理死锁的三种方法：

• Deadlock Prevention: 通过破坏死锁的必要条件来避免死锁
• Deadlock Recovery: 允许系统进入 deadlock 状态，然后检测并恢复
• Deadlock Detection: 检测系统是否进入 deadlock 状态，但是不采取恢复措施，假装死锁不存在

事实上，大多数操作系统都选择了第三种方法。

Section 8.5: Deadlock Prevention

• 破坏四个条件

与 Deadlock Prevention 不同的是，Deadlock Avoidance 是可能发生死锁，但要求在发生死锁之前谨慎地操作，来避免死锁。而 Deadlock Prevention 则是从根本上避免死锁的发生。

课上举了一个开车的例子，为了防止把车开进沟里，要么把沟填上，要么小心点开车。

Mutual Exclusion

这个条件通常是无法破坏的，因为有些资源本质上就是互斥的。

Hold and Wait

？？？？

No Preemption

其反面是“允许抢占”。

带来的问题是，被抢占的进程的反复请求和分配带来的额外开销，以及抢占导致的不一致状态。

Circular Wait

• 破坏 Circular Wait 的一种方法是给每一种资源类型分配一个唯一的编号，然后要求每个进程按照递增的顺序请求资源。

实际操作中这种方法在可行性上也较低。

Section 8.6: Deadlock Avoidance

每一个进程 declare 它在运行期间可能需要的最大资源数目。

Avoidance 算法动态检查资源分配的状态来确保没有 circular wait。

其中资源分配状态由可用的和已分配的资源数目，以及每个进程的最大需求决定。（通过两个矩阵表示）

Safe State

Definition

系统处于安全状态（safe state），如果 存在 一个进程的序列 \(\{P_{1}, P_{2}, \ldots, P_{n}\}\)（即一个 Schedule），使得对于每一个进程 \(P_{i}\)，它所需要的资源数目都 小于等于 系统分配后剩余的资源，再加上它前面进程 （\(P_j,\quad j <i\)） 持有的资源（在运行到 \(P_i\) 时被释放）。

如果 \(P_i\) 的资源需求暂时无法满足，则需要一直等待，直到所有 \(P_j\) 释放资源（\(j<i\)）

Unsafe 的含义是，如果系统中进程自由地请求资源，则可能进入 deadlock （这个发出请求的行为是形成 deadlock 必要的），而不是当前已经处于 deadlock 状态。

对于 Single Instance of Each Resource Type，使用 Resource-Allocation-Graph Algorithm；对于 Multiple Instances of Each Resource Type，使用 Banker's Algorithm。

Resource-Allocation-Graph Algorithm

首先回忆 Assignment Edge 和 Request Edge 的定义。

进而有 Claim Edge 的定义：从进程节点指向资源节点，表示该进程可能会请求该资源。

这样，就有 Claim Edge 到 Request Edge，Request Edge 到 Assignment Edge 的转换。

RAG Algorithm 的核心思想是：如果 Request Edge 到 Assignment Edge 的转换不会导致 RAG 中出现 Cycle，则允许该请求，说明转换后的状态是 safe 的；否则拒绝该请求。

如果形成的 Cycle 中有 Claim Edge（虚线边），则不一定导致 deadlock，是 unsafe 的状态；进一步的，如果 Cycle 中无 Claim Edge，必然导致 deadlock。

Banker's Algorithm

• Assumptions:
  • Multiple Instances of Each Resource Type
  • 每个进程在运行前必须声明它的最大需求（超过的请求报错）
  • 进程请求资源时，必须等待
  • 进程获得其所需的所有资源后，必须在有限时间内返回并释放资源。

为了精确描述 State，我们有如下量：

• Available: 一个长度为 \(m\) 的向量，表示系统中每一种资源类型的可用实例数目，\(m\) 是资源类型的数量
• Max: 一个 \(n \times m\) 的矩阵，表示每一个进程对每一种资源类型的最大需求，\(n\) 是进程的数量
• Allocation: 一个 \(n \times m\) 的矩阵，表示系统当前已经为每一个进程分配的每一种资源类型的实例数目
• Need: 一个 \(n \times m\) 的矩阵，表示每一个进程还需要的每一种资源类型的实例数目，即 \(Need[i][j] = Max[i][j] - Allocation[i][j]\)。

给出 Safe Algorithm:

1. 定义 Work 和 Finish - Work[]: 一个长度为 \(m\) 的向量，初始化为 Available，表示当前可用的资源数目
   • Finish: 一个长度为 \(n\) 的向量，初始化为 false，表示每一个进程是否能够完成
2. 找到一个满足条件的进程 \(P_i\)：
   • Finish[i] == false
   • Need[i] <= Work
   • 如果找不到，转到步骤 4
3. Work = Work + Allocation[i]，并将 Finish[i] 置为 true，转到步骤 2
4. 如果 Finish[i] == true 对所有 \(i\) 都成立，则系统处于 safe state。

另外，有 Resource-Request Algorithm:

定义 Request_i[j]=k 为进程 \(P_i\) 请求资源类型 \(R_j\) 的 \(k\) 个实例。

1. 如果 Request_i > Need_i，则报错
2. 如果 Request_i > Available，则进程 \(P_i\) 必须等待
3. 假设分配请求，更新状态：
   • Available = Available - Request_i
   • Allocation_i = Allocation_i + Request_i
   • Need_i = Need_i - Request_i
   • 调用 Safe Algorithm 检查新的状态是否安全，如果安全，则分配请求；否则，恢复原状态，令进程 \(P_i\) 必须等待。

Section 8.7: Deadlock Detection

思路是，允许系统进入 Deadlock 的状态，然后检测并恢复。

Single Instance of Each Resource Type

改为维护一个 wait-for graph，其中节点是进程，边 \(P_i \to P_j\) 表示进程 \(P_i\) 正在等待进程 \(P_j\) 持有的资源。

换句话说，如果在 RAG 中存在一个路径 \(P_i \to R_k \to P_j\)，则在 wait-for graph 中存在一条边 \(P_i \to P_j\)。

检测 wait-for graph 中的 cycle 即可检测 deadlock。

Multiple Instances of Each Resource Type

Detection-Algorithm Usage

周期性进行检测。

恢复的方法：

• 终止处于 deadlock 的所有进程
• （或）逐一终止进程，直到 deadlock 消失

选择终止的进程时，可以考虑以下因素：

• 进程优先级
• 进程已运行时间
• 进程所需资源量
• 进程已持有资源量
• .......

另外的恢复方法：资源抢占

选择一个进程，剥夺它所持有的资源，然后将这些资源分配给其他等待的进程，直到返回 safe state，重启进程。

这么做可能产生的问题是 starvation。

Chapter 13: File-System Interface

对应 Slides Chap.10

恐龙书上 PART FIVE (Chap.11, ) 部分摘录在后面

一些嵌入式系统，其内存可能是 flash，写、擦除等操作是有限的（可能影响到寿命），需要设计文件系统来减少写、擦除操作造成的昂贵代价。

本章讨论的文件系统，应当是 persistent, abstract 并且 isolated（有时也需要 sharing）。

Overview

• 文件系统接口：
  • Operations
  • File Attributes
  • Data Structures

对于 file system structure，其中有 In-memory File System Structure 和 On-disk File System Structure 两种。

文件系统主要指控制数据在存储介质中存储和检索的方式。

具体来说有如下几个层面：

• File Naming
• Where Files are Placed
• Metadata
• Access Rules

Section 13.1: File Concept

files 是连续的逻辑地址空间。

其内容是一些 bits, bytes, lines, records 的序列，具体含义由使用者定义。内容类型可能是数据，包括 numeric, character, binary；可能是 pragram，包括 source, object, executable。

File Structure

文件可以是无结构的（unstructured），即字节流（byte stream）；也可以是有结构的（structured），即记录流（record stream）。

对于 Simple Record Structure，可能是 lines, fixed length 或者 variable length。对于 Complex Structure， 。。。。

File Attributes

• Name：唯一用人类可读的形式保存的信息
• Identifier：唯一标识文件的标识符
• Type
• Location：指向文件在设备上的位置
• Size
• Protection：控制访问
• Timestamps and user identificatio

File Operations

• Create
• Write
• Read
• Reposition within file
• Delete
• Truncate
• Open/Close

文件系统的设计确实贯彻了 OOP 的思想，Attributes 作为 Member Variables，而 Operations 作为 Member Functions。

对于 open() 操作，系统返回一个指向 open-file table entry 的指针。这些 pointers 被存储在进程的PCB 中

为了管理 open files，需要几个数据：

• file pointer
• file-open count
• disk location of the file
• access rights

对于文件的访问，并发访问是常见的情形，因此需要 file locking 这种同步机制，具体的实现因系统而异

File Types

Name, Extension 从略

File types 在 UNIX 中，可以通过 Magic Number 体现。

后略

Section 13.2: Access Methods

Sequential Access

磁带式地访问，是一种非常原始的方式

Direct Access

• or relative access

加了一个 position 的移动操作，可以在任意位置上读写、擦除。

现在的访问基本上都是 direct access。

Sequential Access 可以通过 Direct Access 来模拟

Other Access

• Indexed Access

维护一个索引文件，可以快速定位文件中的记录。关于 Index Access 本课程中不做过多讨论。

Section 13.3: Directory Structure

目录可以看作一个 symbol table，将文件名翻译为他们的 control blocks。

一个 directory 包含多个 directory entries，每一个 entry 包含文件名和指向文件控制块的指针。为了找到 entry，需要对文件名在 directory 中进行搜索。

事实上，file control block 将文件内容和其本身的信息（如文件名）解耦，这样是为了某种高效的目的。

回看 directory，其中包含多个 directory entries，因此可以将其设计为一个“文件”（因此有嵌套的目录）。事实上 UNIX 就是这么设计的。

directory 和 files 的组合就是一个 file system，存储在磁盘的一个分区（partition）中。有时也可以跨分区。

Operations

其操作包括：

• Search
• Create
• Delete
• List
• Rename
• Traverse（遍历），用于查找满足给定条件的文件

下面讨论目录的组织。

Single-Level Directory

对于所有用户，所有文件都在同一个目录下。

命名和查找都很不方便。

Two-Level Directory

每个用户分配一个目录，彼此之间隔离。

对于单个用户，仍然很不方便。

Tree-Structured Directories

每一个目录都可以有其子目录。

这给查找、分类管理都带来了便利，接近现代使用的文件系统。

这样，需要加入一个 bit 来区分 file(0) 和 directory(1)。另外，还需要知道 current directory。

进入目录有相对、绝对两种方式。

Acyclic-Graph Directories

• 无环图目录

用于 file sharing，两个 user 的目录可以访问同一个文件，即不同 user 的某一个 directory entry 指向同一个文件。

这种方式与 copy 不同，对于修改是不隔离的。

link：同名 directory entry 指向同一个 file control block。

在删除文件时，需要考虑 link 的数量，只有 link 数为 0 时，才能真正删除文件。自然地，需要对 link 进行计数

General Graph Directory

允许环路。directory entry 的指针可以指向上层的一个 directory entry。

这种方式在历史上出现过，但给管理、遍历带来麻烦。

Soft Link & Hard Link

Soft Link (or Symbolic Link) 指的是一个特殊的、分离的文件，其内容是其 original 文件的路径名，从而指向这个 original file。

Hard Link 是一个已存在文件的别名，有另外一个 directory entry 指向它，但本质上是指向同一个文件。Hard Link 增加 link count

从 inode 的角度看， Soft Link 有自己的 inode，而 Hard Link 共享 inode。

对于 Soft Link，如果删除其 target，会变为一个悬空的指针，但不会影响 target。

设计两种 Link 主要是为了使用上的方便，其维护也更简单。

File-System Mounting

• 挂载

从某个点出发，将一个 file system 连接到另一个 file system 上。

文件系统在被访问前必须 mounted

Section 13.4: Protection

三类 access:

• Read
• Write
• Execute

三类 user:

• owner access
• group access
• public access

Chapter 14: File-System Implementation

对应 Slides Chap.11

本章主要讨论文件系统在内部实现上的共性。

Section 14.1: File-System Structure

一般认为文件系统是分层实现的。

• Application programs
• Logical file system
• File-organization module
• Basic file system
• I/O control
• Devices

从下往上看，I/O control 将读写指令翻译为低级的硬件指令；Basic file system 对物理 blocks 的读写操作，另外还需解决多进程同时访问文件时的 I/O 调度问题和 buffer 的管理；File-organization module 将逻辑的 block 地址翻译为物理的 block 地址，并负责管理空闲的空间； Logical file system 负责文件元数据的管理、文件保护与安全。

这种分层的设计是将文件系统模块化，将功能解耦，使得代码能够被大量重用。

另一个好处是分层实现体现了抽象。

Section 14.2: File-System Operations

Data Structure Used to Implement File Systems:

• Disk Structures
  • Boot Control Block
  • Volumn (卷) Control Block
  • Directory Structure
  • Per-file FCB
• In-Memory Structures
  • In-memory mount table (about each mounted volumn)
  • Diretory cache
  • System-wide open-file table
  • Per-process open-file table

典型的 File Control Block 包含如下信息：

• File Permissions
• File Dates (create, access, write)
• File Owner, Group, ACL
• File Size
• Pointers to File Data Blocks (重要)

这里没有出现的是 File Name，因为 file name 存储在 directory entry 中。

对于 In-Memory File System Structures:

Section 15.5: Virtual File Systems

• 虚拟文件系统

将基本系统调用功能与实现细节隔离。

是一个内存的“文件系统”，而不是传统的磁盘文件系统。

VFS 接口的多种实现可以在同一台机器上共存，从而允许透明地访问本地安装的不同类型的文件系统。

不仅如此，VFS 还可以对远程文件系统进行访问。

在 VFS 中实现了四种类型的 object：

• Superblock: 对应磁盘文件系统的文件系统超级块或控制块（是一个抽象类）
• Inode: 对应磁盘文件系统的文件控制块（注意 在 VFS 中 inode 是内存中的对象 ）
• Dentry: 一个独立的 directory entry
• File: 对应一个进程中打开的文件。只要文件一直打开，这个 object 就一直存在与内存

注意上面的“对应”说明，这些对象不是它所描述的块、文件等本身。

Section 14.3: Directory Implementation

• Linear List

使用线性表来将 directory entry （包含 file name 和 pointer to data block） 组织起来。

简单但是耗时。

• Hash Table

使用 hash table 来组织 directory entry。

降低了查找时间，但是可能发生碰撞（collision）。

Section 14.4: Allocation Methods

分配方式（allocation methods） 指的是磁盘中的块是如何分配给文件的。

主要有三种方式：

• Contiguous Allocation
• Linked Allocation
• Indexed Allocation

Contiguous Allocation

每一个文件占据一组连续的块。

上面的操作是基于“磁盘中块是已编号的”的假设。

简单（只需要存储起始地址和块数），支持 Direct Access。

缺点是因为 dynamic storage-allocation problem 导致空间浪费（external fragmentation），以及文件增长受到限制。

逻辑地址和物理地址的转换：偏移即为起始地址

• Extent-Based File System

将多个连续的块合并为一个 extent，然后分配 extent。

Linked Allocation

每一个文件由一组不一定连续的（scattered）块组成，这些块通过指针链接在一起。

另外，单独存储末尾的块，以方便添加。

解决了 fragmentation 的问题。

但是缺点是不支持 Direct Access。为了访问一个特定位置的块，需要从头开始遍历指针，这伴随着相应次数的磁盘访问。

用书上的话说，是一种“捡垃圾式”的访问。

一个改进是加入 File-Allocation Table，将链接的信息不存在 data block 中，而是集中存在 FAT 里。FAT 表占用的空间显然比起 data block 要小得多，因此可以放在内存中，将多次磁盘 blocks 的访问用内存访问代替，从而提高效率。

#### Indexed Allocation

在一个 Block 中维护一个 index table，table 中存储文件所有块的地址。(index block)

这样，一个 directory entry 只需要存储 index block 的地址。

问题在于，一个 index block 中所能存放的地址数量决定了文件的最大大小。

\[ \text{max file size} = \frac{\text{block size}}{\text{address size}} \times \text{block size} \]

对于过大的文件，需要更复杂的 scheme。

• Linked Scheme
• Multilevel Indexing

对于多级索引，一个 index block 存储若干个指向其他 index block 的指针，最后一级 index block 存储数据块的地址。

• Combined Scheme

结合了直接索引、单级间接索引、双级间接索引和三级间接索引。

Cite

在基于 UNIX 的文件系统中使用的另一种选择是将索引块的前 15 个指针保留在文件的 inode 中。这些指针中的前 12 个指向直接块；也就是说，它们包含包含文件数据的块的地址。因此，小文件（不超过12个块）的数据不需要单独的索引块。如果块大小为 4 KB，则最多可以直接访问 48 KB 的数据。接下来的三个指针指向间接块。第一个指向单个间接块，它是一个索引块，不包含数据，但包含包含数据的块的地址。第二个指向双间接块，其中包含块的地址，该块的地址包含指向实际数据块的指针的块的地址。最后一个指针包含三重间接块的地址。

上面的 inode 即 FCB (file control block)。

Section 14.5: Free-Space Management

一个问题是，如何管理磁盘中未被分配的块（free space）。

• Bit Vector

使用一个位图（bit vector）来表示每一个块的状态（free(1) or allocated(0)）。

回忆 minisql-module 1

注意位图在更新时，需要先更新磁盘上的 bits，再更新内存中的 bits。

位图要求额外的空间，但是优势是易于获取连续的文件块。

下面有一些 bit maps 的变种。

• Link Lisk (Free List)

使用一个链表来表示 free blocks。链表中的节点除了指向下一个节点，还可以并排地指向多个 free blocks。

另外，还有包含计数信息的实现。（counting）

Section 14.6: Efficiency and Performance

Efficiency 取决于：

• Disk Allocation 和 Directory 算法
• dentry 中数据的类型

Performance 相关：

• disk cache
• free-behind and read-ahead: 优化顺序访问的技术
• virtual disk (RAM disk)

Chapter 11: Mass-Storage Structure

Section 11.1: Overview of Mass-Storage Structure

• Hard Disk Drives (HDD)
• Non-volatile Memory (NVM)

Hard Disk Drives

\[ \text{Access Time} = \text{Seek Time} + \text{Rotation Latency} + \text{Transfer Time} \]

• seek time: 1-20 msec
• rotation latency: 0-10 msec
• transfer rate: 1 msec per a 4KB page

其中，变化较大的是 seek time。

一般来说，要访问的 sector 随机分布在 track 各处。因此 rotation latency 可平均看作旋转周期的一半。

从 OS 的层面，也可以调整文件在 Disk 中的分布，来影响到 seek time。

Non-volatile Memory

• SSD (solid-state disk)

其上数据不能被直接覆写，而是需要先进行擦除（erasure）。

寿命限制：一个 block 上擦除数据次数有限

需要将磁盘看作一个 1-dimension array。

考虑 accessing logical number of blocks 的问题。

block number 沿 sector 分布，从零号 track 的零号 sector 开始，转一圈到铺满整个零号 track，然后又从一号 track 的零号 sector 接着铺。

Section 11.2: HDD Scheduling

多进程同时访问 disk 时，想要提高硬盘设备的 efficiency，尤其是要缩短 access time 中的 seek time。

• \(\text{seek time} \propto \text{seek distance}\)

将要访问的 logical block 序列，抽象出其 track number 序列，因为我们不考虑 sector (与 rotation latency 相关)，而是只关注 track (与 seek time 相关)。

当带访问序列（track number）到来时，磁头可能处于任意位置，因此希望对序列进行调度，使得对于任意的磁头初始位置，按序访问时磁头经过的 distance 尽可能小。

注意这里 distance 用 track number 之间的差（head movement）来度量。

FCFS

不改变序列，先到先访问。

SSTF

• Shortest-seek-time-first

在已经进入序列的请求中，选择与当前磁头最近的请求。

比 FCFS 更优，但是可能发生 starvation

SCAN

电梯式的移动，沿一个方向扫描，经过请求则服务，不改变方向除非到达最低/最高点。

有时也将其称为 elevator algorithm

一个仍可优化的点是，当经过当前队列中最小/最大，其实可以立刻折返（LOOK），而不需要移动到确实的末尾。

C-SCAN

• circular SCAN

认为 SCAN 的问题是，在 SCAN 路径方向正向上的请求的等待时间比反向小很多（每遇到一个请求，需要 transfer 等操作），这是不够 fair 的。

希望服务时间更加均衡，于是改造 SCAN。

电梯下降时不服务任何请求，只在上升时服务请求。

同样对 C-SCAN 加入 LOOK 机制，而有 C-LOOK。

Selection of a Disk-Scheduling Algorithm

取决于 workload 的大小。

Section 11.a: Disk Management

磁盘需要格式化才能使用。

• Low-level Formatting——将 disk 划分为 sectors

boot block 和 MBR

Section 11.6: Swap-Space Management

跳过

Section 11.8: RAID Structure

• redundant arrays of independent disks (RAIDs)

由于单个磁盘不够大，于是用多个 inexpensive 的磁盘作为阵列连在一起，来储存数据。

提供冗余性，因为磁盘可能发生 failure。

• Disk Striping (条带化)

将原始数据按照某种 pattern 切分、聚类，同类 pattern 的存在同一个 disk 上。

RAID Levels

• RAID 0: 无冗余
• RAID 1: 原来有几个，就 duplicate 几个作为 mirrored disks
• RAID 4: Block-level striping

现代磁盘本身就能发现自身 block 上的错误。因此只需加入一个纠错的盘，就可以将出错的磁盘整个恢复。

• RAID 5

将纠错磁盘信息分布到数据磁盘上。

• RAID 6

更强的纠错能力

• RAID 0+1

先分片，再镜像。

正常备份则能正常工作，一个磁盘 failure，则不能工作。

• RAID 1+0

先镜像，再分配。

只有一个 disk fails，其他仍可运作。

（完）

Chapter 12: I/O Systems

不仅从硬件层面讨论I/O system 的机制，还讨论与上层的接口和交互行为。

Section 12.1: Overview

略

Section 12.2: I/O Hardware

• port

与进程端口的概念不同，也没有什么关系。I/O 设备通过 port 连接到主机。

• bus

可能有多个 port 连接到一根线上，并且负责设备之间的通讯。

• controller

设备控制器

CPU 和内存以内存总线连接。除此之外，最重要的是高速总线 PCIe bus，版本越高，带宽越高。

低速设备可能也需要连接到主机 ，通过 expansion bus 连接，如 USB, Keybroad 等，然后extension bus 通过 expansion bus interface 连接到 PCIe。

GPGPU: General Purpose Graphics Processing Unit，用于将部分计算任务 offload 到 GPU 上。

通过 I/O instructions 来控制 I/O 设备。使用端口号作为硬件地址来对某个特定设备进行控制。

• Memory-Mapped I/O

将设备寄存器映射到内存地址空间中，从而可以通过普通的内存读写指令来访问设备寄存器。

• I/O Port Registers
  • Data-in：设备发出内容，Host 读
  • Data-out：Host 向设备写内容
  • Status
  • Control

Data 相关的寄存器可能有多个，上面只是抽象的说法。

Polling

？？？？？

Interrupts

• Interrupt-request line

在 CPU，由 I/O 设备触发。

• Interrupt handler

• Maskable

部分 interrupt 可以被屏蔽，取决于优先级之类的，较 critical的中断不可以 mask。服务类的中断大部分可以屏蔽，这时中断的处理就可以被 delay。

中断可以细分为软（trap）硬。其中 trap 的优先级是较低的，但是上下文切换仍然是必须的。优先级较低说明可以被高优先级的抢占。

？？？？

Direct Memory Access

• DMA

用于防止大规模数据的 programmed I/O 移动。

？？？？？

Section 12.3: Application I/O Interface

通过以下不同维度对设备进行分类：

• character-stream / block
• sequential / random-access
• sharable / dedicated
• speed of operation
• read-write / read-only / write-only

Block and Character Devices

Block 设备包括 disk drives，character 设备包括 keyboard, mouse 等。

Network Devices

不同的 Network Layer 有不同的 interface。

Clocks and Timers

设置 timer 来产生 periodic interrupts。

Blocking and Nonblocking I/O

• Blocking: I/O 完成之前，进程挂起
• Nonblocking: I/O 调用返回尽可能多
• Asynchronous: I/O 运行时进程同步运行，I/O 完成后通过 signal 通知进程

Section 12.4: A Kernel I/O Structure

内核的软件部分下还包括一层 kernel I/O subsystem，再下一层为 device drivers。

Kernel I/O Sunsystem

I/O Scheduling

当多个进程同时请求同一个设备时，I/O subsystem 负责调度这些请求。

Buffering

当数据在设备之前之间传输时，在内存中暂存以达到缓冲的目的。

协调设备之间的数据传输速度差异和大小的差异（speed & size mismatch）。

Other

• Caching
• Spooling: hold output
• Device Reservation

Error Handling

检测错误并从中恢复。

I/O Protection

????

Kernel Data Structure

通过文件接口实现对 I/O 设备管理（参考 UNIX），这一点也是通过 open-file table 实现。

Section 12.5: Transforming I/O Requests to Hardware Operations

通过 FCB 信息获取设备在哪个 controller 上，然后通过 controller 进行 I/O 操作。

Section 12.7: Performance

影响 I/O performance 的因素：

• Demands CPU to execute device drivers
• 中断导致的上下文切换开销
• 数据拷贝
• 网络流的压力

---

评论区