题型：
单选10
多选5
判断5
简答（解释概念
综合分析题（给一个调度的关键指标选择算法等

12班复习内容

Os

操作系统做的一件事——抽象abstraction（为什么要抽象）os是一个软件位于程序和硬件之间
OS对三类资源进行抽象管理

  • 1.CPU资源的抽象是进程
  • 2.内存资源的抽象是内存管理相关
  • 3.各种设备资源的抽象是设备管理

CPU管理（进程管理）

将任务抽象的结果是进程
‼️PCB进程控制块—结构：存储存储器的上下文、内存的指针（堆、栈、and？？？）

  • PCB是唯一进行进程标识的，是进程的核心组成部分（代码段、数据段），包括了PID，UID，Process Control and Management Information， Processor related information （like Register）

‼️进程的状态及状态转换：（什么事件导致状态变化）
new、ready、running、blocked、exit

init（初始）—可以执行—ready—通过调度—running—

调度问题与指标计算

调度问题（不同的调度算法：FIFC、SJF、RR、组合
计算不同的指标turnaround、wait、respond time可能画Gutt图
•RR—最公平，上下文切换开销大，整体任务开销增加
除了周转时间（Turnaround）、等待时间（Waiting）和响应时间（Response）之外，常见的调度性能指标还有：

下面以两个进程的 FCFS 调度为例，说明这三个指标的计算方法。

公式回顾

  • 周转时间（Turnaround Time, TAT）

TAT=完成时间（Finish）−到达时间（Arrival） \text{TAT} = \text{完成时间（Finish）} - \text{到达时间（Arrival）}

  • 等待时间（Waiting Time, WT）

WT=周转时间（TAT）−执行时间（Burst） \text{WT} = \text{周转时间（TAT）} - \text{执行时间（Burst）}

  • 响应时间（Response Time, RT）

RT=首次开始执行时间（Start）−到达时间（Arrival） \text{RT} = \text{首次开始执行时间（Start）} - \text{到达时间（Arrival）}

示例

假设有两个进程，它们按到达顺序（FCFS）执行：

进程 到达时刻 AT 服务时长 BT 开始时刻 Start 完成时刻 Finish
P1 0 4 0 4
P2 1 3 4 7

  • P1

    • TAT₁ = Finish₁ – AT₁ = 4 – 0 = 4
    • WT₁ = TAT₁ – BT₁ = 4 – 4 = 0
    • RT₁ = Start₁ – AT₁ = 0 – 0 = 0

  • P2

    • TAT₂ = Finish₂ – AT₂ = 7 – 1 = 6
    • WT₂ = TAT₂ – BT₂ = 6 – 3 = 3
    • RT₂ = Start₂ – AT₂ = 4 – 1 = 3
进程 TAT WT RT
P1 4 0 0
P2 6 3 3

这样就得到了每个进程的周转、等待和响应时间。

指标 计算公式或方法 侧重点
吞吐量（Throughput） 完成进程数总时间\dfrac{\text{完成进程数}}{\text{总时间}} 系统处理能力
CPU 利用率（Utilization） CPU 忙碌时间总时间\dfrac{\text{CPU 忙碌时间}}{\text{总时间}} 资源使用效率
上下文切换次数 调度触发的切换总次数 调度开销
平均负载（Load Average） OS 内部指数衰减统计 运行队列长度
慢化比（Slowdown） TurnaroundBurst Time\dfrac{\text{Turnaround}}{\text{Burst Time}} 短作业延迟敏感度
公平性（Fairness） 运行时间份额与权重偏差 资源分配公正性
Deadline Miss Rate Missed DeadlinesTotal Jobs\dfrac{\text{Missed Deadlines}}{\text{Total Jobs}} 实时约束满足情况

掌握这些指标及其计算方法，有助于从不同角度评估调度算法的优劣，也能针对系统需求（高吞吐、低延迟、实时性或公平性）选择或设计合适的策略。

系统调用是什么？？
系统调用是用户模块到内核模块的转换
User Mode - Kernel Mode

‼️process进程 vs thread线程
process通过fork（复制父进程的全部信息）系统调用建立，exec进行子进程自己的工作
thread也是独立的执行单元（可以执行代码，需要栈），共享了全部的堆内存空间以及全局变量
现代操作系统实际的执行单元是线程thread

进程是操作系统分配资源的基本单位，是系统进行资源调度的基本单位。每个进程都拥有独立的地址空间。
线程是CPU调度额最小分配单位，是进程的的最小调度单位，线程之间可以共享进程内的资源和地址。

file describe文件描述符不是全局唯一的，它与进程绑定，在进程里面是唯一的。可以实现文件的并发等

解决并发问题—锁机制
并发vs并行：并行是真正的同时执行，并发是看起来同时执行
Concurrency and Parallelism：
并发是多个任务交替完成，宏观上是同时法生，但实际上是每个任务交替进行
并行是多个任务或进程同时进行，在同一时刻进行。但依赖于hardware device，需要多核设备

e.g.一个单核CPU可以并发不能并行✅

race codition：多个任务对共享资源的访问
通过锁机制确保只有一个进程能进入CS（critical section），锁机制—互斥锁mutual mutex
e.g.锁机制可以通过纯粹的软件实现❌分析：锁机制需要硬件的支持

锁机制（互斥锁）
codition variables单纯的通知“等待”功能
semaphore信号量—对任意的数据类型进行抽象，semaphore是整数类型，功能：资源的数量控制和codition variable的通知功能
e.g.比较信号量为1和互斥锁的功能信号量多一个通知的功能

并发另一个问题—deadlock死锁（哲学家问题）
通过信号量解决死锁问题/在逻辑上解决死锁问题

死锁的四个条件：

  • Mutual Exclusion
  • No preemption
  • Hold and Wait
  • Circule Wait

解决死锁问题：破坏死锁条件‼️检查一组进程是否会产生死锁—银行家算法banker algorithm（线程安全性）

  • Deadlock avoidance
  • Deadlock prevention

内存管理

最重要‼️页表机制/多级页表机制怎么对虚拟内存空间进行管理，翻译成物理地址

内存的分配是以页面大小4k的page分配

设备和文件管理

大部分概念问题
一个设备是怎么被抽象的
一个文件系统
‼️调度问题（最短寻道时间seek time
‼️换页机制可能导致缺页page fault
换入换出算法（基于时空的局部性选择LRU &OPT
计算缺页次数和缺页率

Ch1:

Hardware (★)
Architecture
CPU
Disk
Memory
IO
Interrupt-driven (★★)
在操作系统中，中断驱动（Interrupt-driven） 是一种通过硬件或软件机制处理异步事件的方式。当外部或内部事件发生时，操作系统会通过中断来响应这些事件，而不是通过轮询等方式不断检查事件的状态。这种方式的最大优点是 提高了系统的响应性和效率。

中断驱动的工作原理

在中断驱动模式下，当外部硬件设备（如键盘、鼠标、硬盘等）或软件产生事件时，会向 CPU 发出 中断请求（IRQ）。此时，CPU 会停止当前的执行，保存现场，然后跳转到相应的 中断处理程序（Interrupt Service Routine，ISR）。处理完中断事件后，CPU 会恢复执行之前的程序。

具体流程如下：

  1. 中断请求：当外部硬件或软件产生中断时，会向 CPU 发送一个中断请求。

  2. 中断响应：CPU 停止当前任务的执行，保存当前状态（如寄存器值）并跳转到指定的中断处理程序。

  3. 中断处理程序（ISR）：操作系统或硬件通过中断处理程序来处理特定的事件。中断处理程序执行完后，会通知操作系统并恢复到中断前的执行状态。

  4. 恢复执行：处理完中断事件后，CPU 恢复现场，继续执行中断之前的任务。

中断驱动的类型

  1. 硬件中断（Hardware Interrupt）：

    • 由外部硬件设备生成的中断请求，如键盘输入、网络数据包到达、定时器溢出等。
    • 硬件中断有高优先级，能够立即打断 CPU 当前的工作，处理实时事件。
    • 例子：I/O 操作（硬盘读写、网络传输）需要等待硬件设备准备好，硬件设备通过中断告知操作系统进行下一步操作。

  2. 软件中断（Software Interrupt）：

    • 由程序或软件生成的中断请求，通常用于系统调用或某些特定的操作。
    • 软件中断通常用于程序和操作系统之间的交互，允许用户程序请求操作系统提供的服务（如文件操作、进程管理等）。
    • 例子：用户程序向操作系统发起系统调用请求，操作系统通过软件中断进行处理。

中断的作用和优势

  1. 提高响应性：

    • 中断驱动模式使操作系统能够对外部事件（如硬件输入、I/O 请求等）做出快速响应，而无需等待周期性的轮询操作。这样，系统能迅速处理重要事件，提高实时性和响应速度。

  2. 节省 CPU 时间：

    • 使用中断可以避免不必要的轮询检查。传统的轮询方法需要 CPU 定期检查设备状态，而中断则是基于事件驱动，只有事件发生时，CPU 才会中断当前的执行并处理事件，这样能节省大量 CPU 时间。

  3. 资源管理和效率：

    • 中断使得系统资源（如 CPU、内存等）能够更高效地分配。当设备处于空闲状态时，CPU 可以继续执行其他任务；只有在设备需要处理时，才会触发中断，系统的整体效率得到了优化。

  4. 实时处理：

    • 中断机制非常适合实时操作系统（RTOS），在此类系统中，事件的响应时间至关重要。例如，控制系统中的传感器数据采集或机器人控制等任务，需要在非常短的时间内做出反应，避免延迟。

总结

中断驱动是操作系统中非常重要的一种机制，通过硬件中断和软件中断处理事件。它的优势在于高效的资源利用、实时响应和简化管理，但也需要小心设计，避免死锁和中断风暴等问题。操作系统通过中断管理技术，优化了对硬件和外部事件的处理能力。
(1.2.1)
Multi-programming & time-sharing (★★★)
(1.4)

Ch2

Dual mode (★★★) 1.5
User mode
Kernel mode

1.1 用户模式（User Mode）

用户模式是指应用程序（用户进程）运行的环境。在用户模式下，程序运行时只能访问有限的系统资源，无法直接与硬件交互，也无法访问操作系统的核心功能。用户程序在这个模式下运行时，如果执行了可能破坏系统的操作（如非法内存访问或硬件操作），操作系统会通过中断机制将控制权交回内核模式，进行错误处理。

  • 限制：在用户模式下，应用程序无法直接访问硬件设备，也无法执行敏感操作（如修改内存管理、操作I/O设备等）。所有与硬件相关的操作都需要通过系统调用由操作系统代为执行。
  • 优点：保护了系统的稳定性和安全性。用户程序无法直接修改系统资源，从而避免了潜在的系统崩溃或安全漏洞。

1.2 内核模式（Kernel Mode）

内核模式是操作系统本身运行的环境，在这种模式下，操作系统能够访问所有的硬件资源，并且能够执行任何操作。内核模式具有最高的权限，它允许操作系统控制硬件、管理内存、调度进程、进行设备I/O操作等关键任务。

  • 特权：内核模式下，操作系统拥有完全的控制权，能够执行对硬件的直接访问、系统资源的管理以及保护机制。
  • 访问控制：操作系统在内核模式下运行时，可以访问和修改所有资源，包括硬件设备、内存、系统表格等。而用户模式下的程序不能直接访问这些资源。

OS’s Services (★)2.1

OS’s Services (★)2.1 2.1 操作系统服务的种类

  1. 进程管理：

    • 操作系统负责管理系统中的所有进程，包括进程的创建、调度、同步、终止等。
    • 服务包括进程调度、进程间通信、进程同步与互斥等。

  2. 内存管理：

    • 操作系统管理内存的分配和回收，确保每个进程有足够的内存空间，并防止进程间的内存冲突。
    • 服务包括虚拟内存管理、内存分页、内存保护等。

  3. 文件管理：

    • 操作系统提供文件的存储、读取、修改、删除等功能。
    • 服务包括文件系统管理、目录管理、文件读写、权限管理等。

  4. 设备管理：

    • 操作系统负责管理外部硬件设备，如磁盘、键盘、显示器、打印机等。
    • 服务包括设备驱动程序、I/O设备管理、设备分配与调度等。

  5. 安全与保护：

    • 操作系统提供安全性功能，确保系统免受未授权访问或恶意操作。
    • 服务包括用户认证、访问控制、加密服务等。

  6. 网络服务：

    • 操作系统提供网络功能，支持数据通信和网络资源共享。
    • 服务包括网络连接管理、协议栈处理、网络数据传输等。

User and OS interface (★★)2.2
Command
GUI
System call (★★) 2.3
Types of System calls 2.4 (★★★)
System programs 2.5 (★)

3. System Call (系统调用)

系统调用（System Call）是用户程序和操作系统之间进行交互的接口。它是应用程序请求操作系统服务的机制。操作系统提供了一组系统调用，允许用户程序执行各种操作系统级的任务，如文件操作、进程控制、内存分配等。

  • 系统调用的工作原理：当用户程序需要操作系统服务时，它会通过系统调用接口向操作系统发起请求。这些请求会触发操作系统的内核代码运行，完成任务后返回给用户程序。

  • 系统调用的分类：不同操作系统提供的系统调用接口有所不同，但大体上都包括以下几种类型：

4. Types of System Calls (系统调用的类型)

系统调用通常可以分为以下几类，每一类处理操作系统中的不同功能：

4.1 进程控制（Process Control）

这类系统调用用于控制进程的创建、终止、暂停等操作。包括：

  • fork()：创建新进程。
  • exec()：执行新程序。
  • exit()：终止当前进程。
  • wait()：等待子进程终止。
  • getpid()：获取当前进程的进程ID。

4.2 文件操作（File Management）

这类系统调用用于文件的创建、读取、写入、删除等操作。包括：

  • open()：打开文件。
  • read()：读取文件。
  • write()：写入文件。
  • close()：关闭文件。
  • unlink()：删除文件。
  • stat()：获取文件状态信息。

4.3 设备操作（Device Management）

这类系统调用用于与设备的交互，包括设备的控制和管理。包括：

  • ioctl()：控制设备。
  • read()：从设备读取数据。
  • write()：向设备写入数据。

4.4 内存管理（Memory Management）

这类系统调用用于管理进程的内存分配和访问。包括：

  • mmap()：映射内存。
  • brk()：调整数据段大小。
  • sbrk()：动态分配内存。

4.5 通信（Interprocess Communication, IPC）

这类系统调用用于进程之间的通信和同步。包括：

  • pipe()：创建管道。
  • msgget()：获取消息队列。
  • semop()：操作信号量。
  • shmget()：获取共享内存。

Ch3

Process concept

  • Process vs program (★★) (3.1.1)

2. Process vs Program (进程与程序)

进程 和 程序 虽然有很大关系，但它们是两个不同的概念：

  • 程序（Program）：程序是静态的、静止的，它只是存储在硬盘上的代码。程序在磁盘上作为一个文件存在。

  • 进程（Process）：进程是程序在内存中的执行实例。一个程序可以有多个进程实例在同一时间运行，每个进程都有独立的资源（如内存空间、寄存器、堆栈等）。进程是程序的动态表现，是程序的执行。

区别：

  • 程序 是指令的集合，通常在磁盘上存在。
  • 进程 是程序的一次执行，具有独立的执行路径、内存空间、程序计数器等。
  • 一个程序可以对应多个进程，例如，启动多个浏览器窗口，每个浏览器窗口都是程序的一个进程实例。
  • Process in memory (★) (3.1.1)
  • Process states (★★★) (3.1.2) e.g.
  • PCB (★★★) (3.1.3) e.g.

Scheduling
在操作系统中，调度（Scheduling） 是进程管理的核心部分，负责决定哪个进程在某一时刻使用 CPU。操作系统通过调度算法来控制进程的执行顺序，并确保系统资源得到高效和公平的分配。调度过程中的关键组成部分包括 队列、调度器 和 上下文切换。

  • Queues (★) (3.2.1)
  • Scheduler (★) (3.2.2)
  • Context switch (★★★) (3.2.3) e.g.

Context Switch (上下文切换)

上下文切换（Context Switch）是指操作系统暂停当前正在执行的进程，保存其执行状态，然后选择另一个进程进行执行。上下文切换是操作系统进行多任务并发处理的核心机制。

上下文切换的过程：

  1. 保存当前进程的状态：操作系统保存当前正在执行的进程的上下文信息（如程序计数器、寄存器值等），这通常保存在 进程控制块（PCB） 中。

  2. 选择新进程：调度器从就绪队列中选择一个新的进程，并将其调度到 CPU 上执行。

  3. 恢复新进程的状态：操作系统恢复新进程的上下文信息，将其从 PCB 中读取并加载到 CPU 中，从而使新进程继续执行。

  4. 执行新进程：新进程开始执行，并通过程序计数器等信息从上次中断的位置继续执行。

上下文切换的开销：

  • 性能开销：上下文切换需要保存和恢复大量的寄存器和状态信息，因此是一个相对昂贵的操作。频繁的上下文切换会导致系统的性能下降，因为 CPU 时间被浪费在切换进程上，而不是执行有意义的计算任务。
  • 优化：操作系统通常会尽量减少上下文切换的频率，使用高效的调度算法来减少切换的开销。

上下文切换的原因：

  1. 时间片用尽：在时间片轮转调度中，每个进程在 CPU 上的执行时间是有限的。当时间片耗尽时，操作系统会强制进行上下文切换，暂停当前进程并调度另一个进程。
  2. 高优先级进程到达：如果一个更高优先级的进程到达了就绪队列，操作系统会进行上下文切换，将当前进程暂停并调度高优先级进程执行。
  3. 阻塞事件：当进程等待某个资源（如 I/O 操作）时，操作系统会进行上下文切换，将该进程挂起，调度其他进程执行。

Process creation & termination

  • fork (★★)
  • exec (★)
  • wait (★)： 系统调用用于使父进程等待一个或多个子进程的终止。父进程会阻塞，直到子进程结束并返回一个状态值。该系统调用通常用于父进程获取子进程的退出状态。
  • exit (★)

Shared memory (★)
3.4.1

Message passing (★)
3.4.2

Socket (★★)
3.6.1

Pipe (★★)
3.6.3

Ch4

Thread vs process (★★★)
(4.1)

特性 进程 线程
独立性 进程拥有独立的地址空间和资源 线程共享进程的地址空间和资源
资源占用 每个进程占用较多的内存和资源 线程相对较轻，占用较少的内存和资源
创建开销 创建和销毁进程的开销较大 创建和销毁线程的开销较小
通信方式 进程间通信较复杂，使用IPC机制 线程间通信更高效，使用共享内存和同步机制
上下文切换 进程的上下文切换开销较大 线程的上下文切换开销较小
故障隔离 进程之间相互独立，一个进程崩溃不会影响其他进程 线程间共享内存，一个线程崩溃可能导致整个进程崩溃

Multi-core programming
多核编程是指在具有多个CPU核心的系统中，合理利用多个核心来并行处理任务。每个核心可以独立执行一个线程或进程，这样可以大幅提高系统的并行处理能力。

  • Parallel vs concurrency (★★)
  • Amdahl’s Law & speedup (★★)
特性 并行（Parallelism） 并发（Concurrency）
定义 多个任务同时进行计算 多个任务在时间上交替执行
任务执行 任务分解为多个子任务并在多个核心/处理器上同时执行 任务分解并交替执行，通常在单个处理器上调度
应用场景 适合计算密集型任务 适合I/O密集型任务，如用户交互、服务器等
资源要求 需要多个处理器核心/处理器 仅需要一个处理器核心，通过时间片切换实现并发

Multithreading models

  • 1-1 (★★)
  • m-1 (★★)
  • m-m (★)
线程模型 用户级线程 内核级线程 特点 适用场景
1-1 模型 每个用户线程对应一个内核线程 每个线程独立调度和执行 高度并行，充分利用多核处理器，每个线程由内核管理。 高并发、高性能要求的应用（如视频渲染、服务器）。
m-1 模型 多个用户线程共享一个内核线程 只有一个内核线程管理所有用户线程 线程管理开销较小，但无法利用多核处理器。 轻量级、低并发应用（如简单的网络服务）。
m-m 模型 多个用户线程映射到多个内核线程 多个内核线程动态分配给用户线程 灵活高效，支持多核处理，能够动态分配线程。 高并发、需要高效资源管理的应用（如高性能数据库、Web 服务）。

Pthread & Java thread (★)
Thread pool (★) (4.5.1)

Ch5

CPU/IO burst, CPU/IO bound (★) (5.1.1)
Time for scheduling (★★) (5.1.3)

Preemptive/non-preemptive scheduling (★★) (5.1.3)

3. 抢占式与非抢占式调度（Preemptive/Non-preemptive Scheduling）

抢占式调度（Preemptive Scheduling）

  • 定义：抢占式调度是指操作系统可以随时暂停正在执行的进程，并将CPU分配给其他进程。即使当前进程没有完成，它也可以被操作系统中断，并由其他进程或更高优先级的进程抢占。
  • 优点：更容易实现公平调度，避免低优先级的进程占用过多CPU时间，提高响应时间。
  • 缺点：可能导致较高的上下文切换开销，因为进程可能频繁被暂停。
  • 适用场景：适用于响应性要求较高的系统，如交互式操作系统、实时操作系统等。

非抢占式调度（Non-preemptive Scheduling）

  • 定义：非抢占式调度是指操作系统在进程执行时不会主动打断它，进程会继续执行直到自愿释放CPU（如执行完任务、等待I/O等）。此时，进程必须自己放弃CPU控制权，操作系统才能调度其他进程。
  • 优点：上下文切换较少，系统开销较小。
  • 缺点：如果低优先级的进程占用CPU时间，可能导致高优先级的进程等待过长时间。
  • 适用场景：适用于批处理系统、需要大量计算的任务等。

总结：

  • 抢占式调度可以提高系统响应速度，适用于交互式环境，但增加了上下文切换的开销。
  • 非抢占式调度可以减少上下文切换的开销，但可能导致低优先级进程占用过多CPU时间，影响响应速度。
    Scheduling criteria (★★★) (5.2)
    Scheduling algorithm
  • FCFS (★★★)
  • SJF (★★★)
  • Round-robin (★★★)
  • Priority (★★★)
  • Shortest remaining time first (★)
  • Multilevel Queue Scheduling (★)

e.g. average wait time, average turnaround time, Gantt chart

Thread scheduling (★) (5.4.1)

  • Contention scope

Multi-processor scheduling

  • Processor affinity (★★) (5.5.2)
  • NUMA (★) (5.5.2)
  • Load balancing (★★) (5.5.3)

Real time scheduling

  • Hard/soft real time (★)
  • Deadline, period, rate (★)
  • RM scheduling algorithm (★★)
  • EDF scheduling algorithm (★★)

Ch6

算法 英文名称 特点 缺点
首次适应算法 First Fit 快速查找，第一个符合要求的空闲块即可分配。 可能产生较大的内存碎片，且分配不均匀。
循环首次适应算法 Next Fit 避免重复检查空闲块，稍微提高效率。 仍然容易产生碎片，且内存分布不均。
最坏适应算法 Worst Fit 将大进程分配到大的空闲区，避免小碎片的产生。 可能导致大空闲块的浪费，增加内存碎片的发生。
最佳适应算法 Best Fit 尽量减少分配后的空闲空间，使空闲空间最小。 容易产生大量小碎片，无法高效利用剩余空间。

1. 竞争条件（Race Condition）

竞争条件是指多个进程或线程在没有适当同步的情况下，访问共享资源并且至少有一个进程修改该资源时，程序的输出依赖于执行的顺序。由于操作系统的调度可能不确定，导致不同的执行顺序会导致不同的结果，形成竞争条件。

示例：

假设有两个线程分别修改一个共享变量counter，线程A执行 counter = counter + 1，线程B执行 counter = counter + 1。由于线程的调度不可预测，如果两者在相同时间段内访问counter，并且都读取到相同的值后再进行修改，就会发生错误，最终结果可能比预期少1。

解决方法：

  • 同步机制：通过互斥锁（mutex）、信号量（semaphore）、条件变量等同步原语来避免多个线程同时访问共享资源。

2. 临界区问题（Critical Section Problem）

临界区问题是指在多进程或多线程环境中，多个进程或线程访问共享资源（如变量、文件等），其中至少有一个进程或线程会修改该资源，而其他进程或线程可能也在同时访问该资源，导致竞态条件的发生。临界区指的是访问共享资源的那一段代码。

问题：

在多进程或多线程环境下，如果多个进程或线程同时执行临界区的代码而没有适当的同步机制，可能会导致数据不一致和程序行为不可预测。

要求：

为了避免竞态条件，必须对临界区进行控制，确保在任一时刻只有一个进程或线程能够进入临界区。

3. 临界区问题的三项要求

在解决临界区问题时，任何有效的解决方案都必须满足以下三个要求：

  1. 互斥（Mutual Exclusion）：

    • 只有一个进程或线程可以同时进入临界区，其他进程必须等待，直到临界区释放。

  2. 进程进度（Progress）：

    • 如果没有进程在临界区中，则必须有一个进程能够进入临界区。
    • 进程进入临界区的决定应该仅依赖于它自己，而不应受到其他进程是否正在等待的影响。

  3. 有限等待（Bounded Waiting）：

    • 每个进程必须有一个界定的时间来等待进入临界区，防止某些进程无限期地阻塞，确保每个进程最终都能够进入临界区。

4. Peterson的解决方案（Peterson’s Solution）

Peterson的解决方案是解决两个进程之间的临界区问题的一种经典算法。该算法使用两个标志变量和一个共享的turn变量来实现进程的同步，确保在任意时刻只有一个进程能够进入临界区。

工作原理：

  • 每个进程有一个标志位flag[i]，表示进程i是否想要进入临界区。
  • turn变量表示当前轮到哪个进程进入临界区。

算法步骤：

  1. 每个进程在进入临界区之前将自己的标志设置为true，并设置turn为另一个进程。
  2. 然后，每个进程检查是否轮到自己进入临界区，若不是，等待直到轮到自己。
  3. 一旦进入临界区，进程完成其任务并将标志设置为false，表示退出临界区。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define NUM_THREADS 2

bool flag[NUM_THREADS];  // 记录进程是否想进入临界区
int turn;                // 记录哪个进程可以进入临界区

void enter_critical_section(int i) {
    int j = 1 - i;
    flag[i] = true;  // 表示进程i想进入临界区
    turn = j;        // 让另一个进程进入临界区
    while (flag[j] && turn == j) {
        // 如果另一个进程也想进入临界区，并且轮到它进入，则等待
    }
}

void exit_critical_section(int i) {
    flag[i] = false;  // 进程退出临界区
}

5. 原子指令（Atomic Instruction）

原子操作是指在执行过程中不可被中断的操作。原子指令具有不可分割性，即一个原子操作要么完全成功，要么完全失败，不会处于中间状态。它们对于同步和保证并发程序的正确性至关重要。

常见的原子指令：

  • test_and_set：检查标志位并设置为1。这个操作是原子的，能防止多个进程同时进入临界区。
  • compare_and_swap：如果一个变量的值与预期值相等，则将其更新为新值。

原子操作通常由硬件提供支持，保证了在并发执行时不会发生中断，从而保证了操作的正确性。

6. test_and_set（测试并设置）

test_and_set 是一种常见的原子指令，通常用于实现锁或互斥量。它先检查一个布尔标志位的值，如果该值为false，它将其设置为true，并返回设置前的值。这个操作是原子的，确保了在并发环境下的正确性。

  • 线程 1 调用 test_and_set(lock_flag)，发现 lock_flag 为 0，于是将 lock_flag 设置为 1，表示锁被占用。
  • 线程 2 调用 test_and_set(lock_flag)，发现 lock_flag 为 1，于是它会被阻塞，直到 lock_flag 被设置回 0。

工作原理：

  • 如果进程检查到锁为false，它会将锁设置为true，表示它成功地获得了锁。
  • 如果锁已经是true，则表示已经有其他进程获得了锁，当前进程需要等待。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool lock = false;

bool test_and_set(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

void enter_critical_section() {
    while (test_and_set(&lock)) {
        // 如果锁已被占用，等待
    }
    // 进入临界区
}

void exit_critical_section() {
    lock = false;  // 释放锁
}

7. compare_and_swap（比较并交换）

compare_and_swap 是另一种常用的原子指令。它首先将目标变量与给定的值进行比较，如果两者相等，则将目标变量更新为新值。该操作在并发环境中保证了线程安全。

工作原理：

  • 比较：将目标变量与期望值进行比较。
  • 交换：如果目标变量与期望值相等，交换目标变量的值为新值。

compare_and_swap 操作确保了在并发环境下的互斥性。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int compare_and_swap(int *ptr, int old_value, int new_value) {
    int old = *ptr;
    if (*ptr == old_value) {
        *ptr = new_value;
    }
    return old;
}

void enter_critical_section() {
    int lock = 0;
    while (compare_and_swap(&lock, 0, 1) != 0) {
        // 如果锁被占用，等待
    }
    // 进入临界区
}

void exit_critical_section() {
    lock = 0;  // 释放锁
}

8. 互斥锁（Mutex Lock）

互斥锁是操作系统中最常见的同步原语，用于保护临界区。只有一个进程或线程可以拥有锁并进入临界区，其他进程或线程必须等待锁被释放。

工作原理：

  • 获取锁：一个线程或进程请求锁，如果锁被其他线程占用，它就会阻塞，直到锁被释放。
  • 释放锁：当进程或线程完成其临界区任务时，它释放锁，允许其他进程获取锁并进入临界区。

优点：

  • 通过互斥锁，能够有效避免多个进程或线程同时进入临界区，确保资源的安全访问。

示例：

1
2
3
4
5
6
7
8
9
10
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void enter_critical_section() {
    pthread_mutex_lock(&lock);  // 获取锁
    // 进入临界区
}

void exit_critical_section() {
    pthread_mutex_unlock(&lock);  // 释放锁
}

总结：

  • 竞争条件：多个进程或线程在没有同步的情况下访问共享资源，可能导致不一致的结果。
  • 临界区问题：如何保证在任意时刻只有一个进程或线程访问共享资源。
  • 原子指令：如test_and_set和compare_and_swap，这些操作确保了线程在访问共享资源时的安全性。
  • 互斥锁：用于确保只有一个进程或线程能够进入临界区，解决临界区问题。

通过适当的同步机制，如互斥锁和原子操作，我们可以有效避免竞争条件和确保并发程序的正确性。

Race condition (★★) (6.1)
Critical section problems (★★) (6.2)
Three requirements for the solution
Peterson’s solution (★)
Atomic instruction (★★)
test_and_set
compare_and_swap
Mutex lock (★★★)
spinlock
e.g. 互斥问题
Semaphore (★★★)
Counting
Binary
wait
signal
Atomic
Waiting list
Initialization of mutex lock and semaphores
E.g. 同步、互斥问题
Deadlock & starvation (★) (6.6.3)
Priority inversion (★) (6.6.4)
Classic synchronization problems (★★★)
Producer-consumer
Reader-writer
Dining philosopher
E.g. 能灵活运用这几个经典问题
Monitor
Structure and properties of monitor (★★) (6.8.1)
Use of monitor (★) (6.8.2)

1. Spinlock

Spinlock（自旋锁）是一种同步机制，用于在多线程或多进程环境中确保对共享资源的互斥访问。它与传统的锁（如互斥锁）不同，自旋锁不会使线程阻塞，而是让线程在获取锁失败时一直循环（即“自旋”）并不断检查锁是否可用，直到成功获取锁。

自旋锁的工作原理：

  • 线程尝试获取自旋锁。如果锁已被其他线程占用，当前线程会持续循环检查锁的状态。
  • 一旦锁释放，线程会继续执行，获得锁并进入临界区。

优点：

  • 快速锁定：在多处理器系统中，自旋锁的性能较好，因为线程可以在等待锁的过程中保持活跃状态，避免了上下文切换的开销。
  • 简单实现：自旋锁的实现较为简单，不需要涉及线程调度。

缺点：

  • CPU 消耗：如果锁长时间无法获得，线程会浪费大量 CPU 时间进行自旋，导致性能下降。
  • 死锁风险：自旋锁如果与其他同步机制（如普通锁）不当组合，可能导致死锁。
  • 不适合单处理器系统：在单处理器系统中，自旋锁不会释放 CPU，因此可能导致其他线程长时间无法执行。

2. Deadlock & Starvation

死锁（Deadlock）

死锁是指在多进程或多线程环境中，多个进程（或线程）因互相等待对方释放资源而永远无法继续执行的状态。死锁通常发生在资源管理不当的情况下。

死锁的必要条件：

  1. 互斥条件（Mutual Exclusion）：至少有一个资源是以排他方式分配的，即一次只有一个进程可以访问。
  2. 占有并等待条件（Hold and Wait）：至少有一个进程持有一个资源，并等待其他进程持有的资源。
  3. 不剥夺条件（No Preemption）：进程已经获得的资源不能被强制剥夺，必须由进程自己释放。
  4. 循环等待条件（Circular Wait）：进程形成一个环形等待链，每个进程等待下一个进程持有的资源。

解决死锁的方法：

  • 预防：通过破坏死锁的某些条件来预防死锁，如要求所有资源一次性分配给进程（打破占有并等待条件）。
  • 避免：使用资源分配算法（如银行家算法）动态地检测和避免死锁。
  • 检测与恢复：允许死锁发生，但使用死锁检测算法来检测死锁并采取措施（如回滚进程、撤销资源等）进行恢复。

饥饿（Starvation）

饥饿是指一个进程由于系统调度的原因，长时间得不到资源而无法继续执行。与死锁不同，饥饿不会使进程完全停止，而是使进程的执行被长期推迟。

饥饿的原因：

  • 低优先级进程：在优先级调度中，低优先级进程可能因为高优先级进程的频繁执行而长时间无法获得 CPU 时间，从而造成饥饿。
  • 不公平的资源分配：如果资源分配机制不公平，某些进程可能永远得不到资源。

解决饥饿的方法：

  • 优先级调整：通过动态调整进程优先级（如渐进式增加优先级）来避免低优先级进程长期饥饿。
  • 公平调度算法：使用公平的调度算法，如 轮转调度（Round Robin），确保所有进程都有机会执行。

3. Priority Inversion (优先级反转)

优先级反转是指高优先级的进程被低优先级的进程阻塞，导致低优先级进程先于高优先级进程执行，从而违反了优先级调度的设计目标。

优先级反转的发生：

  • 假设有三个进程：高优先级进程 A、低优先级进程 B 和 中优先级进程 C。
  • 进程 B 占用了一个共享资源（例如锁），进程 A 需要该资源才能继续执行，但进程 B 被中优先级的进程 C 阻塞。
  • 结果是高优先级进程 A 被中优先级进程 C 阻塞，导致进程 A 的执行顺序被反转。

优先级反转的解决方案：

  1. 优先级继承协议：当低优先级进程持有资源并阻塞高优先级进程时，它会继承高优先级进程的优先级，确保它尽快释放资源。
  2. 优先级传播协议：通过级联提高优先级，使得整个等待链上的进程优先级得到提高，直到高优先级进程能够获取资源。
  3. 避免不必要的锁：减少进程之间对共享资源的竞争，从而降低优先级反转的风险。

4. 调度算法评价的几个指标

为了评估调度算法的好坏，通常会使用以下几个指标：

1. CPU 利用率（CPU Utilization）

  • 定义：表示 CPU 在一段时间内的使用比例。CPU 利用率越高，表示系统的资源使用效率越高。
  • 目标：操作系统应尽可能保持 CPU 的高利用率，避免 CPU 长时间处于空闲状态。

2. 吞吐量（Throughput）

  • 定义：单位时间内完成的进程数量。
  • 目标：调度算法应该尽可能增加吞吐量，使得系统能够在单位时间内完成更多的进程。

3. 周转时间（Turnaround Time）

  • 定义：一个进程从提交到完成所经历的总时间。周转时间包括等待时间、执行时间和 I/O 时间等。
  • 目标：调度算法应尽量减小周转时间，使得进程尽早完成。

4. 等待时间（Waiting Time）

  • 定义：一个进程在就绪队列中等待执行的时间，不包括它在运行时的时间。
  • 目标：调度算法应尽量减少进程的等待时间，避免长时间阻塞。

5. 响应时间（Response Time）

  • 定义：从进程提交请求到操作系统开始响应的时间，通常用于交互式系统。
  • 目标：对于交互式应用，调度算法应尽量减少响应时间，提高系统的交互体验。

6. 公平性（Fairness）

  • 定义：调度算法应确保每个进程都能获得合理的资源分配，避免某些进程长时间得不到 CPU 时间。
  • 目标：调度算法应尽量避免进程饥饿，保证公平性。

7. 调度开销（Scheduling Overhead）

  • 定义：执行调度所需要的时间和资源。
  • 目标：调度算法的开销应尽量低，以减少不必要的上下文切换和调度时间。

Ch7

Necessary conditions for deadlock (★★)
四个条件

  • Mutual Exclusion：资源在某个时刻只能被一个资源占用
  • No Preemption：某个时刻中资源被进程使用，那么系统不能收回资源或者该资源被其他进程抢占，必须等该进程使用玩
  • Circule wait:形成一个资源请求的循环，每个进程都在等待其他进程释放资源
  • Hold and wait ：进程在持有某些资源的同时，申请新的资源。如果新申请的资源不可用，进程就会进入等待状态，保持对已占有资源的占有。
    Resource allocation graph (★★)
  • Cycle and deadlock

Deadlock prevention (★★)

  • Break four conditions

Deadlock avoidance (★)

  • Safe/unsafe/deadlock
  • Banker’s algorithm
  • Safety algorithm
  • Resource request algorithm

Deadlock detection (★)
死锁的四个必要条件

Ch8

Virtual address space (★★) (9.1)
Virtual address vs physical address (★) (8.1.3)
Memory management hardware (★)

  • MMU (8.1.3)
  • Base/limit register (8.1.1)

1. 虚拟地址空间（Virtual Address Space）

虚拟地址空间是操作系统为每个进程提供的逻辑地址空间。在虚拟内存管理中，程序访问的是虚拟地址，而不是物理地址。虚拟地址空间的目的是通过地址映射技术，提供每个进程独立的地址空间，保护进程免受其他进程的影响，并优化内存使用。

虚拟地址空间的特点：

  • 隔离性：每个进程都认为自己有一个独立的内存空间，不会受到其他进程的干扰。
  • 扩展性：通过使用虚拟内存，操作系统可以将较大的程序映射到较小的物理内存上，从而有效地扩展程序可用的内存空间。
  • 保护性：虚拟地址空间确保一个进程无法直接访问另一个进程的内存，这样即使程序存在错误或漏洞，也不会影响到其他进程。

虚拟地址空间的实现：

  • 通过**分页（Paging）或分段（Segmentation）**的技术，虚拟地址空间被映射到物理内存上。操作系统和硬件共同管理虚拟地址到物理地址的转换。

2. 虚拟地址与物理地址（Virtual Address vs Physical Address）

  • **虚拟地址（Virtual Address）**是程序在运行时使用的地址空间。当程序执行时，操作系统将程序使用的虚拟地址转换为物理地址，进程并不直接访问物理内存。

  • **物理地址（Physical Address）**是计算机硬件（如内存控制器）中实际的内存地址。物理地址指向的是内存芯片中的实际数据存储位置。

虚拟地址与物理地址的关系：

  • 在现代计算机中，操作系统通过**内存管理单元（MMU）**来实现虚拟地址到物理地址的转换。MMU通过查阅页表，将程序使用的虚拟地址转换为相应的物理地址。
  • 地址映射：虚拟地址和物理地址之间的映射通常是通过分页机制或分段机制进行的。在分页系统中，虚拟地址被分为页号和页内偏移，操作系统根据页表进行转换。

3. 内存管理硬件（Memory Management Hardware）

内存管理硬件是支持虚拟内存和内存保护的硬件组件，通常由**内存管理单元（MMU）和基址/界限寄存器（Base/Limit Register）**组成。

3.1 MMU（内存管理单元，Memory Management Unit）

MMU是处理虚拟地址到物理地址转换的硬件部件。它通常与操作系统的内存管理机制协作，支持分页和分段。

  • 工作原理：MMU通过查阅页表或段表，将虚拟地址转换为物理地址。当CPU执行指令时，MMU会在每次访问内存时进行转换。

  • 功能：

    1. 地址转换：将虚拟地址转换为物理地址。
    2. 内存保护：根据权限检查每个内存访问是否有效。
    3. 缓存管理：通过**TLB（Translation Lookaside Buffer）**等缓存机制提高地址转换的速度。

3.2 基址/界限寄存器（Base/Limit Register）

基址和界限寄存器用于在简单的内存管理系统中进行地址映射。

  • 基址寄存器（Base Register）：存储进程的虚拟地址空间的起始位置。所有进程的虚拟地址都相对于基址进行计算。
  • 界限寄存器（Limit Register）：存储进程的虚拟地址空间的结束位置。界限寄存器用于保护进程的内存不被越界访问。

基址/界限寄存器的工作原理：

  • 当进程请求访问内存时，硬件会将虚拟地址与基址寄存器中的值相加，得到实际的物理地址。如果计算的地址超出了界限寄存器的范围，硬件会触发异常，保护进程的内存空间不被非法访问。

Static/dynamic linking (★) (8.1.2, 8.1.4, 8.1.5)
Memory mapped files & shared memory & memory mapped I/O (★★) (9.7)
Dynamic memory allocation (★★)

  • Best/worst/first fit (8.3.2)
算法 优点 缺点
First Fit 实现简单，快速 可能导致外部碎片
Best Fit 最大程度利用内存空间 需要扫描整个空闲块列表，可能导致小块碎片
Worst Fit 适合大块请求，留下较大的空闲空间 可能产生大量外部碎片
  • Internal/external fragmentation (8.3.3)

内部碎片：发生在已分配的内存块内部，剩余空间无法使用。
外部碎片：发生在系统的空闲内存中，虽然有足够的内存空间，但由于空闲块不连续，无法满足大的内存请求。

Segmentation (★★) (8.4)

  • Segmentation table, base, limit

Paging (★★★)

  • Frame, page, page no., frame no., page offset, page size
  • Page table, frame table
  • translation look-aside buffer or associate memory (TLB)
  • TLB miss, TLB hit, hit ratio
  • Effective memory-access time
  • Valid bit, r/w bit
  • E.g. page offset, page size, TLB hit, hit ratio, Effective memory-access time的计算等

Hierarchical page table (★★)
Inverted page table (★★)

E.g. 各种适应算法中空闲块的排列方式

Ch9

Swapping (★★) (8.2)

  • Demand paging (★★★) (9.2)
  • Resident memory
  • Swap space
  • Pure demand paging
  • Page fault
  • Page fault rate
  • Effect access time
  • E.g. Page fault, Page fault rate, Effect access time等的计算； 另外，给出逻辑地址，计算页号，将逻辑地址转换为物理地址等。

1. 交换（Swapping）

交换是操作系统内存管理的一种方式，主要用于管理物理内存的不足。它通过将不活跃的进程或进程的部分数据从内存转移到磁盘上的交换空间（Swap Space），从而腾出内存给当前需要的进程。交换过程的核心目的是优化内存使用，尤其是在多任务操作系统中。

交换的过程：

  • 交换入（Swap-in）：将数据从磁盘中的交换空间移回内存，以供程序继续使用。
  • 交换出（Swap-out）：将内存中的部分数据（通常是当前不活跃的进程数据）写入磁盘的交换空间。

交换的缺点：

  • 性能下降：频繁的交换操作会造成磁盘I/O操作增加，导致系统性能下降，特别是在物理内存不足的情况下。
  • 延迟增加：磁盘的访问速度远远低于内存，导致系统响应变慢。

2. 按需分页（Demand Paging）

按需分页是一种虚拟内存管理方案，它允许进程在实际访问内存页时才将其从磁盘载入内存。这种方式比全盘分页更高效，因为它避免了不必要的内存读写操作。

关键概念：

  • Resident Memory（常驻内存）：指的是目前已加载到内存中的进程页面。在分页系统中，只有部分页可能驻留在内存中，其余部分可能保留在磁盘上。
  • Swap Space（交换空间）：指磁盘上专门用来存储不活跃进程数据的空间，用于交换操作。当内存不足时，操作系统会将内存中的部分数据交换到这个区域。
  • Pure Demand Paging（纯按需分页）：只有在程序实际需要时，操作系统才会加载页面。程序启动时，内存中并不包含程序的所有页面，而是通过页面错误来触发加载。

工作原理：

  1. 程序开始运行时，操作系统仅加载一个页面到内存中。
  2. 如果程序访问了未加载的页面，则会产生页面错误（Page Fault）。
  3. 页面错误触发操作系统从磁盘加载该页面，并将其放入内存。
  4. 操作系统可能需要交换出其他页面到磁盘，以腾出内存给新加载的页面。

按需分页的优势：

  • 内存利用率高：只加载程序实际使用的页面，避免了不必要的内存占用。
  • 节省资源：对于大程序，按需分页能够有效避免不必要的内存分配，提高内存使用效率。

3. 页面错误（Page Fault）

页面错误是虚拟内存管理中的一个关键概念，指的是当程序访问的内存页面不在内存中时，操作系统会产生页面错误。操作系统通过处理页面错误来加载缺失的页面到内存。

页面错误的处理步骤：

  1. 检测页面错误：当进程尝试访问一个未加载到内存的页面时，硬件触发页面错误。
  2. 中断并传递给操作系统：硬件中断将控制权交给操作系统，操作系统暂停进程的执行。
  3. 加载页面：操作系统从磁盘的交换空间或文件系统中加载缺失的页面。
  4. 恢复执行：当页面加载完毕后，操作系统恢复进程的执行。

页面错误的计算：

  • 页面错误会带来额外的延迟，因为操作系统需要从磁盘读取页面。
  • 页面错误率（Page Fault Rate）和访问时间是衡量按需分页效率的两个重要指标。

4. 页面错误率（Page Fault Rate）

页面错误率是指程序运行过程中发生页面错误的频率。它通常表示为页面错误次数与总内存访问次数的比率。

页面错误率=页面错误次数总内存访问次数\text{页面错误率} = \frac{\text{页面错误次数}}{\text{总内存访问次数}}

影响页面错误率的因素：

  • 程序访问模式：程序如果有很强的局部性（局部性原理：程序会集中访问一小部分内存），则会减少页面错误的发生。
  • 内存大小：如果可用内存较小，程序更容易频繁地访问未加载到内存的页面，导致页面错误。
  • 页面替换算法：例如，LRU（最近最少使用）或FIFO（先进先出）等页面替换策略对页面错误率有直接影响。

5. 有效访问时间（Effective Access Time, EAT）

有效访问时间（EAT）是指进程访问内存的平均时间，考虑到可能的页面错误。EAT的计算通常包括内存访问时间和页面错误处理时间。

EAT=(1−页面错误率)×内存访问时间+(页面错误率)×(页面错误服务时间)\text{EAT} = (1 - \text{页面错误率}) \times \text{内存访问时间} + (\text{页面错误率}) \times (\text{页面错误服务时间})

其中：

  • 内存访问时间：指从内存中读取或写入数据的时间。
  • 页面错误服务时间：指发生页面错误时，从磁盘读取页面的时间。这个时间比内存访问时间要长得多，因为磁盘的访问速度比内存慢得多。

计算示例：

假设：

  • 每次内存访问的时间为100ns。
  • 页面错误服务时间为10ms（10,000,000ns）。
  • 页面错误率为0.02（即2%的时间发生页面错误）。

那么：

EAT=(1−0.02)×100ns+0.02×10,000,000ns=0.98×100ns+0.02×10,000,000ns\text{EAT} = (1 - 0.02) \times 100 \text{ns} + 0.02 \times 10,000,000 \text{ns} = 0.98 \times 100 \text{ns} + 0.02 \times 10,000,000 \text{ns}

EAT=98ns+200,000ns=200,098ns(即 200.1 μs)\text{EAT} = 98 \text{ns} + 200,000 \text{ns} = 200,098 \text{ns} \quad (\text{即 200.1 μs})

6. 逻辑地址转换为物理地址（Logical Address to Physical Address）

在分页系统中，程序使用的地址是逻辑地址，而实际访问内存时使用的是物理地址。逻辑地址由**页号（Page Number）和页内偏移量（Offset）**组成。页号用来索引页表，而页内偏移量用来访问页面内的数据。

计算过程：

  1. 逻辑地址格式：假设一个程序的逻辑地址是32位，其中前16位表示页号，后16位表示页内偏移量。
  2. 页表：页表存储页号到物理地址框架的映射。假设页表的第N项包含物理页面框架地址。

步骤：

  • 从逻辑地址中提取页号和页内偏移量。
  • 查找页表，获取该页号对应的物理页框架地址。
  • 将物理页框架地址和页内偏移量结合，得到物理地址。

示例：

假设：

  • 逻辑地址为：0x12345（十六进制）。
  • 页大小为4KB（即2^12字节），所以页内偏移量为12位。
  • 页表中，页号0x12对应的物理页框架地址为0x5678。

逻辑地址0x12345的转换步骤：

  1. 页号 = 0x12345 >> 12 = 0x12（页号的高12位）。
  2. 页内偏移量 = 0x12345 & 0xFFF = 0x345（页号的低12位）。
  3. 查找页表，页号0x12对应的物理框架地址是0x5678。
  4. 物理地址 = 0x5678 << 12 + 0x345 = 0x5678345。

所以，逻辑地址0x12345对应的物理地址是0x5678345。

总结：

  • 交换通过将不活跃的进程数据移出内存，来优化内存使用，但可能导致性能下降。
  • 按需分页是虚拟内存管理的核心技术，通过按需加载页面来节省内存资源。
  • 页面错误和页面错误率是衡量分页系统性能的重要指标，页面错误率越低，系统性能越好。
  • 有效访问时间考虑了页面错误的时间，反映了系统访问内存的真实延迟。
  • 逻辑地址转换为物理地址是分页系统中的关键操作，依赖于页表和页内偏移量的结合。

Copy-on-write (★) (9.3)

Page replacement

  • Victim page, dirty/modify bit (★) (9.4.1)
  • Replacement scope (★) (9.5)
  • Reference string (★★) (9.4.1)
  • FIFO (★★★) (9.4.2)
  • OPT (★★★) (9.4.3)
  • LRU (★★★) (9.4.4)
  • Reference bit, clock algorithm (★★) (9.4.5.2)
  • Page buffering (★) (9.4.7)

E.g. 给出页面号调用顺序串，按照不同的页面置换算法，计算缺页中断次数和缺页率。注意Valid bit的影响。

1. 写时复制（Copy-on-Write, COW）

写时复制（COW）是一种内存管理优化技术，在进程创建时（通常是通过fork()系统调用）复制内存页面时，它不会立即复制整个页面，而是让父子进程共享同一内存页面。当任意一个进程尝试修改共享的页面时，操作系统会进行复制操作，即写时复制，从而确保父子进程的内存独立。

工作原理：

  • 在fork()系统调用后，父子进程共享相同的内存页面，且这些页面处于只读状态。
  • 当父进程或子进程尝试修改这些共享页面时，操作系统会将该页面复制一份（“copy”）并允许进程修改。
  • 修改的页面只会在实际需要写入时被复制，避免了不必要的内存复制，从而提高了内存使用效率。

优势：

  • 内存效率：父子进程在复制时只共享内存，避免了不必要的内存开销。
  • 延迟写入：只有在修改时才进行复制，减少了不必要的复制操作。

2. 页面置换（Page Replacement）

页面置换算法用于在虚拟内存管理中，当物理内存不够时，决定哪个页面被从内存中移出（即置换到磁盘）以腾出空间加载新的页面。页面置换是虚拟内存管理的核心，目标是尽量减少页面错误，提升性能。

受害页面（Victim Page）：

  • 当需要置换时，操作系统必须选择一个页面作为“受害页面”被替换出去。选择的受害页面通常是最不常使用的页面。
  • 修改位（Dirty/Modify Bit）：表示页面自从加载到内存后是否被修改。如果页面没有修改过，则可以直接丢弃。如果页面被修改过，则必须将页面内容写回磁盘。

3. 页面置换范围（Replacement Scope）

页面置换范围指的是选择受害页面的策略和算法。在虚拟内存系统中，操作系统可以根据不同的策略选择要置换的页面。常见的页面置换算法包括：

页面置换算法：

  1. FIFO（First-In, First-Out）：最简单的页面置换算法，选择最早进入内存的页面进行置换。
  2. OPT（Optimal Page Replacement）：最理想的页面置换算法，选择未来最长时间内不会被访问的页面进行置换（理论上最优，但不可实现，因为需要预测未来的访问模式）。
  3. LRU（Least Recently Used）：选择最近最久未使用的页面进行置换。
  4. 时钟算法（Clock Algorithm）：一种近似LRU的算法，使用环形队列和参考位来实现。

4. 参考字符串（Reference String）

参考字符串是指程序访问页面的顺序。它是评估页面置换算法性能的基础。例如，参考字符串[0, 1, 2, 3, 0, 1, 4, 0, 3]表示程序按照这个顺序访问页面。

缺页中断次数计算：

  • 给定参考字符串，LRU会在每次访问页面时更新页面的使用记录。当内存满时，选择最近最久未使用的页面进行置换。

9. 页面缓冲（Page Buffering）

页面缓冲是一种优化技术，用于减少页面置换的开销。当系统需要置换页面时，缓冲技术可以将页面缓存起来，以便更快地访问。这减少了页面写回磁盘的次数，尤其是在页面被重新访问时。

通过计算，我们可以评估不同页面置换算法的性能，并选择适合的算法来优化内存管理。

Thrashing (★★) (9.6.1 & 9.6.2)

  • Locality
  • Working set window
  • Working set
  • Working set size

Buddy system (★★) (9.8.1)
Slab allocator (★) (9.8.2)
Pre-paging (★) (9.9.1)
Page size choice (★) (9.9.2)

1. 抖动（Thrashing）

抖动是指由于过多的页面交换（页面错误处理），系统的性能急剧下降，导致处理器时间几乎全部被用于处理页面错误，而几乎没有时间用于执行实际进程。通常，抖动是由于进程使用了过多的内存，而操作系统无法有效地进行页面置换，从而导致频繁的页面错误。

原因：

  • 系统中的进程所需要的内存超过了物理内存的大小，导致频繁的页面置换。
  • 页面置换的次数过多，操作系统花费大量时间进行页面交换，而没有足够的时间来执行进程。

影响：

  • 性能下降：由于频繁的页面错误和页面置换，系统资源被大量浪费在磁盘I/O上，导致进程执行速度显著下降。
  • CPU空转：处理器花费大量时间等待内存的页面加载，而不是执行有效的计算任务。

解决方案：

  • 局部性原理（Locality）：局部性原理是指程序在执行过程中，内存访问有一定的局部性，即访问的内存地址在某一时间段内具有一定的集中性。基于局部性原理，操作系统可以通过优化页面置换策略来减少页面错误，避免抖动。

    • 时间局部性（Temporal Locality）：最近访问的页面很可能会在短时间内再次访问。
    • 空间局部性（Spatial Locality）：访问的内存地址相邻的地址很可能会被连续访问。

  • 工作集（Working Set）：工作集是指进程在一段时间内频繁访问的页面集合。如果进程的工作集被加载到内存中，就可以减少页面错误和抖动的发生。

工作集（Working Set）：

工作集是进程最近一段时间内活跃使用的内存页面集合。操作系统通过维持每个进程的工作集，可以有效地减少页面错误。

  • 工作集窗口（Working Set Window）：工作集的时间窗口，用来定义在什么时间段内的页面被认为是“工作集”的一部分。例如，过去N秒内访问的页面就构成该进程的工作集。
  • 工作集大小（Working Set Size）：工作集中的页面数。工作集大小的合理控制可以有效避免抖动，因为它限制了系统中每个进程的内存需求。

工作集与抖动：

当工作集大小过大时，进程会要求更多的内存，导致频繁的页面置换，可能导致抖动。反之，当工作集过小时，进程的运行可能会受到限制，影响性能。理想情况下，操作系统需要动态调整工作集大小，以适应系统的内存负载，避免抖动。

2. 伙伴系统（Buddy System）

伙伴系统是一种内存分配算法，它将内存划分为大小为2的幂次方的块，每个块被称为“伙伴”。当一个进程需要内存时，操作系统会找到一个足够大的块，并将其分成两个“伙伴”块，这样的划分可以保证内存的高效管理和回收。

工作原理：

  1. 内存块划分：内存被分成大小为2的幂次方的块。例如，如果系统有64KB的内存，那么可以将其划分为32KB、16KB、8KB、4KB等块。
  2. 分配内存：当进程需要内存时，操作系统会从这些块中找到最小的足够大的块。如果块太大，操作系统会将其进一步分割成更小的“伙伴”块。
  3. 合并空闲块：当内存块不再使用时，操作系统会检查相邻的空闲块，如果它们是同样大小的伙伴块，操作系统会将它们合并成一个更大的块，以减少碎片。

优点：

  • 高效的内存管理：减少内存碎片，提高内存利用率。
  • 快速分配和回收：由于内存块大小是2的幂次方，分配和释放内存较为简单和高效。

缺点：

  • 可能导致内存浪费：由于内存块是2的幂次方，无法完全适应某些大小的内存请求，可能会浪费一部分内存。

3. Slab分配器（Slab Allocator）

Slab分配器是一种内存管理机制，特别用于操作系统内核的内存分配。它将内存分成不同大小的块，并将这些块分配给特定类型的对象（如数据结构、内核缓冲区等）。每个类型的对象会有一个对应的“slab”，从slab中分配内存块。

工作原理：

  1. 缓存（Cache）：Slab分配器为每种类型的内核对象（如进程控制块、文件描述符等）维护一个缓存。
  2. 对象分配：每个缓存由一个或多个slab组成，slab中存放相同类型的对象。通过使用slab分配器，内核可以高效地为对象分配内存。
  3. 内存回收：当不再需要这些对象时，slab分配器会回收内存块。

优点：

  • 内存效率：减少了碎片化，提高了内存分配效率。
  • 快速分配和回收：通过预分配固定大小的内存块，分配和回收变得更加高效。

缺点：

  • 管理开销：虽然提高了内存效率，但对于小对象的分配可能会有额外的管理开销。

4. 预分页（Pre-paging）

预分页是一种虚拟内存管理策略，它的目的是通过提前加载程序将来可能会访问的页面来减少页面错误的次数。操作系统通过分析进程的访问模式，预测接下来可能会被访问的页面，然后提前加载到内存中。

工作原理：

  1. 页面预测：操作系统监测进程的内存访问模式，并预测哪些页面可能会被访问。
  2. 提前加载：操作系统提前将这些页面加载到内存中，避免在实际访问时发生页面错误。
  3. 提高性能：通过减少页面错误的发生，操作系统能够提高进程的运行效率，尤其是在高负载系统中。

优点：

  • 减少页面错误：通过预测页面访问，减少了不必要的页面错误，提升了系统性能。
  • 提高响应时间：减少了由于页面错误而引起的延迟。

缺点：

  • 预测不准确：如果页面预测不准确，可能会提前加载不需要的页面，浪费内存资源。

5. 页面大小选择（Page Size Choice）

页面大小的选择是虚拟内存管理中的一个重要决策。页面大小直接影响内存的利用率、页面错误率和系统性能。页面的大小通常是2的幂次方（如4KB、8KB、16KB等）。

影响因素：

  1. 较小页面大小：

    • 优点：减少了内存碎片，适用于小型数据结构。
    • 缺点：增加了页面表的大小，因为每个页面表项需要表示更多的页面。

  2. 较大页面大小：

    • 优点：减少了页面错误率，因为较大的页面能够覆盖更多的数据。
    • 缺点：增加了内存浪费，因为一些较大的页面可能并没有被完全使用。

最佳页面大小：

选择页面大小时，需要平衡内存碎片、页面错误率和页面表的大小。通常，较小的页面适用于内存访问局部性较差的程序，较大的页面适用于内存访问局部性较好的程序。操作系统通常会根据应用的需求和硬件架构动态调整页面大小。

Ch10

File concept (★★)
Access methods (★★)
Directory and Disk structure (★★★)
File-system mounting (★)
File sharing (★)
Protection (★★)

6. 文件保护（Protection）

文件保护是操作系统确保文件的安全性和完整性的机制。文件保护机制的目标是限制不必要的访问、修改和删除文件的权限。

访问控制（Access Control）

访问控制指的是定义哪些用户或进程有权访问文件，并指定他们能进行的操作（如读取、写入、执行等）。常见的访问控制机制包括：

  • 访问控制位（Access Control Bits）：通过设置文件的权限位，指定文件的访问级别。常见的权限位有：

    • r：读权限，允许读取文件内容。
    • w：写权限，允许修改文件内容。
    • x：执行权限，允许执行文件（通常是程序文件）。

    文件的权限可以通过位操作（如UNIX的chmod命令）进行修改。

文件所有权（File Ownership）

文件的所有者通常是创建该文件的用户，操作系统根据文件所有权来控制文件的访问权限。通常文件所有者可以修改文件的权限，而其他用户只能按照文件权限读取或修改文件。

强制访问控制（MAC, Mandatory Access Control）

在某些高安全性的系统中，强制访问控制被用来限制用户对文件的访问。例如，**SELinux（Security-Enhanced Linux）**是一个强制访问控制的实现，可以设置更细粒度的文件访问权限。

总结

  • 文件概念（File Concept）：文件是存储在磁盘上的数据集合，包含了文件名、大小、所有者等元数据。
  • 访问方法（Access Methods）：文件可以通过顺序访问、随机访问或索引访问等方法进行操作。
  • 目录和磁盘结构（Directory and Disk Structure）：目录结构用于组织文件，磁盘结构决定了文件在磁盘上的存储方式。
  • 文件系统挂载（File-System Mounting）：文件系统挂载是将一个文件系统接入操作系统的过程，允许用户通过路径访问文件。
  • 文件共享（File Sharing）：文件共享允许多个用户或进程共同访问同一文件，涉及并发访问和同步控制。
  • 文件保护（Protection）：文件保护机制通过访问控制、文件权限等手段，确保文件的安全性和完整性。
    这一章重点在基本概念，比如File concept ，Access methods， Access control bits等。

Ch11

File-system structure (★★★)
File-system implementation (★★★)
Directory implementation (★★)
Allocation methods (★★)
Free-Space management (★★★)
E.g. 计算磁盘的空间大小、空闲空间管理中各种方法所占空间的计算等。
E.g. Textbook Fig.11.9 UNIX inode，计算这种文件最多能存储多少字节的内容、存储多少副图像等问题。

1. 文件系统结构（File-System Structure）

文件系统结构定义了操作系统如何组织和管理磁盘上的文件。它决定了文件如何存储、检索、访问、组织和共享。理解文件系统结构对提高文件访问效率和数据管理至关重要。

文件系统的组成：

文件系统一般由以下几个主要部分组成：

  • 文件控制块（FCB, File Control Block）：文件控制块是操作系统用于描述文件的内部结构，每个文件都对应一个文件控制块。FCB存储了文件的元数据（如文件名、文件大小、文件创建时间、文件权限等）以及文件在磁盘上的位置。

  • 索引节点（Inode）：在Unix和类Unix系统中，文件的元数据存储在inode中。每个文件都有一个唯一的inode，inode包含文件的所有信息（如文件大小、拥有者、权限、数据块的地址等），但不包含文件名。文件名通过目录结构与inode关联。

  • 数据区（Data Area）：这是文件存储实际内容的地方。文件系统会将文件的内容存储在磁盘上的多个数据块中。

  • 目录结构（Directory Structure）：文件系统中的目录用于组织和管理文件。每个目录包含若干文件名和对应的inode或文件控制块。目录本身也被视为文件，有自己的inode。

  • 空闲空间管理（Free Space Management）：文件系统需要跟踪磁盘上空闲空间的使用情况，以便在创建文件时能够找到足够的空闲区域。常见的空闲空间管理方法有位图、链表等。

文件系统的基本操作：

文件系统提供了基本的文件操作接口，如：

  • 文件创建：为新文件分配空间并创建对应的FCB或inode。
  • 文件删除：释放文件占用的空间，并从目录中移除。
  • 文件读取和写入：根据文件的inode或FCB访问文件内容。
  • 文件修改：更新文件的内容和元数据（如修改文件的大小、时间戳等）。

文件系统层次结构：

  • 块（Block）：磁盘分为多个块，每个块包含一定大小的数据。文件的内容通常被分割为多个块存储。
  • 逻辑与物理结构：文件系统通过逻辑结构组织文件（例如通过目录、文件名），并通过物理结构将数据存储在磁盘上。

2. 文件系统实现（File-System Implementation）

文件系统的实现涉及如何将文件系统结构和操作转化为具体的操作系统内核中的数据结构和算法。实现文件系统时，必须考虑效率、可靠性和灵活性。

文件系统实现的关键组件：

  • 文件分配表（File Allocation Table, FAT）：FAT文件系统是一种常见的文件分配方法，它通过维护一个文件分配表来记录文件在磁盘上的存储位置。每个文件的每个数据块都会在FAT表中有一个条目，指向下一个数据块的位置。FAT文件系统的缺点是文件碎片较严重。

  • 日志文件系统（Log-structured File System, LFS）：日志文件系统是一种通过写入日志来管理文件系统操作的方式。所有的修改操作都会先写入日志，直到操作完成。日志系统的优势是具有良好的容错能力，减少了磁盘碎片。

  • 索引分配（Indexed Allocation）：在索引分配方法中，文件的每个数据块都有一个索引块，索引块存储了该文件数据块的位置。常见的实现方式是通过inode来实现。

  • 磁盘块管理：文件系统实现需要有效管理磁盘块的分配和回收。常见的磁盘块管理方法有：

    • 链式分配：文件的每个数据块存储下一个数据块的位置。
    • 连续分配：文件的所有数据块在磁盘上是连续的，减少了磁头的寻道时间。
    • 非连续分配：文件的数据块在磁盘上分散存储，通过索引表来管理。

  • 缓存管理（Caching）：为了提高文件系统的性能，操作系统通常会实现磁盘缓存机制，将常用的文件数据缓存在内存中，以减少磁盘I/O的次数。

  • 文件系统的可靠性：为了保证文件系统的稳定性和数据的一致性，操作系统通常会实现日志记录、写回操作、备份和恢复策略。例如，**写时复制（Copy-On-Write, COW）**是常见的实现可靠性的一种方法。

3. 目录实现（Directory Implementation）

目录结构的实现决定了文件如何在文件系统中被组织、存储和查找。目录本质上是文件名与文件数据位置（通常是inode或FCB）之间的映射关系。

目录结构的实现方法：

  • 线性列表（Linear List）：在这种实现方式中，目录中的所有文件名都存储在一个线性列表中，查找文件时需要逐个比较文件名，效率较低。

  • 哈希表（Hash Table）：哈希表通过哈希函数将文件名映射到哈希桶中，从而加快文件的查找速度。哈希表解决了线性列表的效率问题，但需要处理哈希冲突。

  • 树状结构（Tree Structure）：树状结构将文件和目录组织成类似文件夹的层次结构，便于管理和查找。常见的实现方式有B树（B-Tree）和B+树（B+ Tree），它们提供高效的文件查找和插入操作。

  • 反向索引（Reverse Index）：一些系统可能使用反向索引来优化查找过程。例如，通过文件的内容建立索引，可以快速定位包含某些特定内容的文件。

目录实现的关键操作：

  • 创建目录：为新的目录分配空间，并在父目录中插入新的目录项。
  • 删除目录：删除目录时，必须确保目录为空，否则无法删除。删除目录时，父目录需要删除相应的目录项。
  • 目录查找：给定文件名，查找该文件在目录结构中的位置。目录查找的效率直接影响文件访问的性能。

目录结构与路径名：

  • 绝对路径（Absolute Path）：文件路径从根目录开始，提供文件的完整路径信息。
  • 相对路径（Relative Path）：文件路径相对于当前目录的位置，不需要从根目录开始。

目录的多级实现：

  • 多级目录结构：每个目录可以包含文件或子目录，允许用户创建多级目录结构来组织文件。目录之间形成父子关系。

总结

文件系统的结构和实现是操作系统中的核心组成部分，直接影响磁盘的存储效率、文件访问速度以及系统的可靠性。目录实现方法为文件提供了有效的组织和快速检索机制，确保文件在系统中的管理高效而有序。对于文件系统的实现，操作系统需要平衡性能、可靠性和可维护性。在设计时，使用缓存、日志、索引等机制是提高文件系统效率和稳定性的常见方法。

1. 磁盘分配方法（Allocation Methods）

磁盘分配方法是操作系统用来管理文件在磁盘上存储空间的策略。常见的磁盘分配方法有：

连续分配（Contiguous Allocation）

  • 概念：文件的所有数据块在磁盘上是连续存储的。操作系统分配一块连续的磁盘空间来存储文件。
  • 优点：文件访问速度较快，因为文件的所有块都是连续的，减少了磁头寻道的时间。
  • 缺点：可能会导致磁盘空间的碎片化，尤其在文件的删除和创建过程中。文件的大小必须在创建时已知，且不能动态扩展。

链式分配（Linked Allocation）

  • 概念：文件的每个数据块包含指向下一个数据块的指针，文件的块通过指针串联在一起。每个文件有一个文件头记录该文件的第一个数据块。
  • 优点：没有碎片问题，因为文件的块可以存储在磁盘的任何位置，动态扩展文件时不需要重新分配空间。
  • 缺点：查找文件时需要按顺序访问每个块，可能导致访问速度变慢。磁头寻道效率较低。

索引分配（Indexed Allocation）

  • 概念：每个文件有一个索引块，索引块记录了文件所有数据块的磁盘地址。文件的内容通过索引块找到对应的磁盘块。
  • 优点：可以支持非连续的磁盘存储，同时减少了链式分配中的顺序访问问题。
  • 缺点：索引块的大小固定，如果文件非常大，索引块可能不够用，需要多级索引。

2. 空闲空间管理（Free-Space Management）

空闲空间管理的目的是跟踪磁盘上的空闲空间并高效地分配给文件。常见的空闲空间管理方法有：

位图（Bitmap）

  • 概念：位图是一种使用位（0或1）来表示磁盘上每个磁盘块是否空闲的方式。每个位表示一个磁盘块，0表示空闲，1表示已分配。
  • 优点：简单、直观，适用于较大的磁盘。
  • 缺点：对于较大的磁盘，位图的大小可能会非常大。每次检查空闲块时，需要扫描整个位图，可能较为耗时。

链表（Linked List）

  • 概念：使用链表记录空闲块的位置。每个空闲块包含指向下一个空闲块的指针。
  • 优点：占用空间少，因为只需要记录空闲块的位置。
  • 缺点：查找空闲块时需要遍历链表，可能会导致较慢的性能。

分区表（Partition Table）

  • 概念：将磁盘分为多个区段，每个区段可以独立管理。每个区段的空闲块数量和位置都会记录在分区表中。
  • 优点：适用于大型存储系统，分区管理可以提高空间利用率。
  • 缺点：可能会导致分区的浪费，如果一个分区的空闲空间用尽，可能无法有效利用其他分区的空闲空间。

3. 空闲空间管理中各种方法所占空间的计算

位图的空间计算

  • 假设磁盘的大小为1TB，每个块的大小为4KB，则磁盘上有多少块：

    总块数=磁盘大小块大小=1TB4KB=1012B4×103B=250×109块\text{总块数} = \frac{\text{磁盘大小}}{\text{块大小}} = \frac{1 \text{TB}}{4 \text{KB}} = \frac{10^{12} \text{B}}{4 \times 10^3 \text{B}} = 250 \times 10^9 \text{块}

  • 每个块需要1位来表示是否空闲（0为空闲，1为已分配）。因此，位图的大小为：

    位图大小=250×109块8位/字节=31.25×109字节=31.25GB\text{位图大小} = \frac{250 \times 10^9 \text{块}}{8 \text{位/字节}} = 31.25 \times 10^9 \text{字节} = 31.25 \text{GB}

  • 通过位图管理1TB磁盘的空闲空间将占用大约31.25GB的空间。

链表的空间计算

  • 假设磁盘上有500GB的空闲空间，且每个空闲块的指针大小为8字节。那么空闲链表的大小为：

    链表大小=空闲块数×指针大小\text{链表大小} = \text{空闲块数} \times \text{指针大小}

    假设每个块的大小为4KB，则空闲块的数量为：

    空闲块数=500GB4KB=125×109块\text{空闲块数} = \frac{500 \text{GB}}{4 \text{KB}} = 125 \times 10^9 \text{块}

    因此链表的大小为：

    链表大小=125×109×8字节=1×1012字节=1TB\text{链表大小} = 125 \times 10^9 \times 8 \text{字节} = 1 \times 10^{12} \text{字节} = 1TB

  • 空闲链表需要的空间相对较大，特别是当磁盘的空闲空间很大时。

4. UNIX inode示例计算（Textbook Fig. 11.9 UNIX inode）

UNIX系统中的inode（索引节点）是存储文件元数据的结构，包含文件的大小、创建时间、修改时间、权限、指向数据块的指针等信息。

计算每个inode能存储多少字节：

  • 假设inode中存储了一个指向文件内容数据块的指针，且每个指针大小为4字节。

  • 假设一个inode有128字节的存储空间，去掉用于存储文件元数据的部分（例如文件权限、时间戳等），剩余的空间用于存储数据块的指针。

  • 如果每个指针4字节，那么一个inode最多可以存储：

    最大指针数=128字节4字节/指针=32个指针\text{最大指针数} = \frac{128 \text{字节}}{4 \text{字节/指针}} = 32 \text{个指针}

  • 每个指针指向一个数据块。如果每个数据块大小为4KB（常见大小），那么每个inode最多可以存储：

    存储字节数=32×4KB=128KB\text{存储字节数} = 32 \times 4 \text{KB} = 128 \text{KB}

计算每个inode能存储多少副图像：

  • 假设每副图像的大小为10KB，那么每个inode最多可以存储：

    存储图像数=128KB10KB/图像=12副图像\text{存储图像数} = \frac{128 \text{KB}}{10 \text{KB/图像}} = 12 \text{副图像}

总结

  • 磁盘分配方法包括连续分配、链式分配和索引分配，它们各有优缺点，影响着文件的访问速度、扩展性和磁盘碎片管理。
  • 空闲空间管理方法包括位图、链表和分区表，它们在磁盘空间管理中起到了关键作用，每种方法都有不同的空间开销和性能特点。
  • UNIX inode的大小决定了它能存储的数据量，通过计算可以得出每个inode最多能存储的字节数和图像数量。

Ch12

1. 磁盘结构（Disk Structure） 详细讲解

磁盘结构是指磁盘的物理和逻辑组织方式。理解磁盘的结构对于优化磁盘存取和调度有着重要作用。磁盘的物理结构可以帮助理解磁头的运动、数据的存储方式及其效率。

磁盘的物理结构：

磁盘由若干个磁盘盘片（Platters）组成，每个盘片表面有两个数据存储区域（上下两面），每个区域上有多个磁道（Tracks）。盘片表面和磁头间的配合决定了磁盘的性能和效率。

  • 盘片（Platters）：磁盘的物理圆形表面，通常是由铝或玻璃材料制成，表面镀有磁性材料。每个盘片上有两个面可以存储数据。每个面都包含了若干个磁道，磁道是同心圆。

  • 磁道（Tracks）：磁道是磁盘上的同心圆状路径，磁道上的数据按照顺序存储，读取/写入时，磁头会移动到相应的磁道来操作数据。

  • 扇区（Sectors）：磁道上进一步分割为多个扇区，扇区是磁盘的最小数据单位。每个扇区的大小通常为512字节或4KB。一个磁道包含多个扇区。

  • 磁头（Heads）：磁头用于在磁盘的磁道上读写数据。每个盘片通常有两个磁头，一个在上面一个在下面。

  • 柱面（Cylinders）：磁盘上同一位置的所有磁道构成一个柱面。因为磁头需要在磁盘的不同面之间移动，所以柱面是逻辑上的层次结构。

磁盘的逻辑结构：

  • 逻辑块地址（LBA）：为了简化磁盘寻址，磁盘使用逻辑块地址（LBA）来代替物理地址。LBA是逻辑上对数据块的编号，而物理地址（Cylinder, Head, Sector）表示数据在磁盘上的物理位置。

2. 磁盘附加（Disk Attachment） 详细讲解

磁盘附加是指计算机系统与磁盘设备之间的连接方式。磁盘附件方式决定了计算机如何访问磁盘、传输数据的速度和效率。常见的磁盘附加技术有：

  • SATA（Serial ATA）：串行ATA是串行连接标准，相较于并行SCSI，SATA提供更高的传输速率，支持较长的传输距离。现代个人计算机通常使用SATA作为磁盘接口。

  • SCSI（Small Computer System Interface）：是一种较为老旧但仍在某些服务器和高性能计算机中使用的接口。SCSI接口支持多个设备（如磁盘、扫描仪等）共享同一个总线。

  • SAS（Serial Attached SCSI）：SAS是SCSI的串行版本，适用于高性能要求的应用，提供更高的传输速率和更大的带宽，通常用于企业级硬盘存储阵列。

  • RAID（Redundant Array of Independent Disks）：RAID技术将多个磁盘组合成一个虚拟磁盘，用于提供数据冗余、提高性能或两者兼得。

  • USB和FireWire：这些接口用于外部存储设备，通常用于便捷的外接存储。

3. 磁盘管理（Disk Management） 详细讲解

磁盘管理包括对磁盘的分区、格式化、存储空间分配、错误修复和性能优化等操作。现代操作系统会提供专门的磁盘管理工具来帮助用户高效地管理磁盘。

磁盘分区（Partitioning）

  • 磁盘分区是将物理磁盘划分成多个逻辑部分，每个分区可以有不同的文件系统。
  • 常见的分区方案有主分区和扩展分区。扩展分区可以进一步划分为多个逻辑分区。

文件系统（File System）

  • 文件系统定义了如何在磁盘上存储和组织文件。常见的文件系统有 FAT32、NTFS、EXT4 等。

磁盘的格式化（Formatting）

  • 格式化磁盘是对磁盘进行初步配置，使其可以存储数据。格式化时会创建文件系统，并擦除磁盘上所有现有的数据。

磁盘错误修复与健康监测

  • SMART（Self-Monitoring, Analysis, and Reporting Technology）：SMART技术用于监测磁盘的健康状态，检测出潜在的故障风险。

磁盘性能优化

  • 磁盘碎片整理：当文件在磁盘上分布不连续时，系统会进行碎片整理，将文件重新排列以提高访问速度。

  • 磁盘缓存：使用缓存（如硬盘缓存或内存缓存）来减少磁盘访问的延迟。

4. RAID结构（RAID Structure） 详细讲解

RAID是通过将多个磁盘组合成一个阵列，以提供更好的数据冗余、性能和可用性。不同的RAID级别适用于不同的需求，常见的RAID级别有：

RAID 0 - 条带化

  • 特点：将数据分成若干块（条带）并分布在多个磁盘上，最大限度提高性能。但没有冗余，若一个磁盘损坏，所有数据丢失。
  • 适用场景：需要高性能，且能接受数据丢失风险的场景。

RAID 1 - 镜像

  • 特点：将数据完整复制到两个磁盘上，每个磁盘都有相同的数据。RAID 1提供数据冗余，若一个磁盘发生故障，数据不会丢失。
  • 适用场景：对数据安全要求较高的场合，数据冗余的场景。

RAID 5 - 带奇偶校验的条带化

  • 特点：数据和奇偶校验信息分散存储在磁盘上，允许一个磁盘的故障恢复数据。RAID 5提供较高的读写性能，同时保证数据冗余。
  • 适用场景：性能和冗余都需要的应用。

RAID 10 - RAID 1 + RAID 0

  • 特点：结合了RAID 1的镜像和RAID 0的条带化优点，同时提供了数据冗余和高性能。
  • 适用场景：对高性能和数据冗余都有要求的场合。

5. 寻道时间计算（Seek Time Calculation）

寻道时间是指磁头从当前位置移动到目标位置的时间，它是磁盘访问性能的关键因素。寻道时间包括 平均寻道时间 和 最大寻道时间。

计算寻道时间的公式：

  • 寻道时间 = |目标位置 - 当前磁头位置|
  • 磁头的移动速度和寻道时间受多种因素影响，如磁盘的旋转速度、磁道的分布等。

寻道时间计算例子：

假设当前磁头位置是100，磁盘请求顺序为45, 150, 65, 190，计算不同调度算法下的总寻道时间：

  • FCFS（First-Come, First-Served）：磁头按照请求到达的顺序进行处理。

    • 寻道时间 = |100 - 45| + |45 - 150| + |150 - 65| + |65 - 190| = 55 + 105 + 85 + 125 = 370。

  • SSTF（Shortest Seek Time First）：每次选择离当前磁头位置最近的请求。

    • 请求顺序为：100 → 65 → 45 → 150 → 190
    • 寻道时间 = |100 - 65| + |65 - 45| + |45 - 150| + |150 - 190| = 35 + 20 + 105 + 40 = 200。

6. 磁盘调度算法及其计算

不同的磁盘调度算法在优化寻道时间和磁盘性能方面有不同的效果。常见的算法包括：

  • SCAN：磁头在磁盘上往返扫描，处理所有请求。磁头到达一端后，会反向移动继续处理请求。

  • C-SCAN：磁头在扫描到磁盘一端后，不是反向扫描，而是快速回到磁盘的另一端继续扫描。

  • LOOK 和 C-LOOK：LOOK和C-LOOK是SCAN和C-SCAN的优化版本，磁头只扫描到请求的最远位置，而不会扫描磁盘的两端。

Disk structure (★★★)
Disk Attachment(★★)
Disk scheduling(★★★)
Disk management (★★★)
RAID structure (★)
E.g. seek time计算, 各种disk scheduling algorithm中调度顺序与总调度时间计算等。

Ch13

I/O Hardware
Application I/O interface
Kernel I/O subsystem
Transforming I/O requests to hardware system
DMA
Direct Memory Access, 直接内存访问，是一种内存管理技术，允许外设直接访问内存，而不需要CPU的干预，从而提高数据传输的效率。
SPOOLing
Spooling（Simultaneous Peripheral Operations On-line）是一种将外部设备的输出操作（如打印任务）暂时存储在磁盘上的技术，然后按顺序处理。它常用于打印机或其他设备，以避免直接干扰计算机的正常操作。

Buffering

缓冲是一种临时存储技术，用于在I/O操作过程中缓存数据，以提高系统的整体性能。缓冲区通常位于内存中，用于存储正在传输的数据。

工作原理：

  1. 读取数据到缓冲区：当数据需要从外部设备读取时，数据先被存储在缓冲区中，等待后续处理。
  2. 写入缓冲区：当数据需要输出到外部设备时，数据先写入缓冲区，然后由操作系统将数据从缓冲区发送到设备。
  3. 缓存管理：操作系统会根据情况管理缓冲区，确保数据顺序正确并尽量减少等待时间。

优点：

  • 减少I/O操作次数：缓冲区可以将多个I/O操作合并为一个，从而减少对设备的访问次数。
  • 提高性能：缓冲技术可以平衡外设和计算机的速度差异，提高数据传输效率。