1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328

\documentclass{article}

% 中文支持
\usepackage{ctex}

% 数学公式支持
\usepackage{amsmath}
\usepackage{amssymb}

% 代码块支持 (使用 verbatim 环境，简单直接，不提供语法高亮)
% 如果需要语法高亮，请使用 listings 包并配置
\usepackage{verbatim}

% 调整页边距
\usepackage[margin=1in]{geometry}

% 标题信息
\title{操作系统课程笔记 (2025)}
\author{基于 jyywiki.cn/OS/2025/lect13 \& lect14 详尽整理}
\date{\today} % 自动显示当前日期

\begin{document}

\maketitle

\hrule % 分隔线
\vspace{1em} % 垂直间距

% ==================================================
% 第13讲：同步 (Synchronization) - 详尽内容
% 来源: https://jyywiki.cn/OS/2025/lect13.md
% ==================================================
\section{第13讲：同步 (Synchronization)}

本讲深入讨论多线程/多进程环境下共享资源的访问控制和协调问题，即同步。

\subsection{并发执行与竞争 (Concurrent Execution and Race)}
并发是指多个任务（线程或进程）在宏观上同时执行。在多处理器或支持时间片轮转的单处理器上都会发生并发。

\paragraph{竞争条件 (Race Condition):}
当多个控制流（线程或进程）访问和修改同一个共享状态时，如果最终结果取决于这些控制流执行的精确交错顺序，那么就存在竞争条件。

\paragraph{示例：计数器增加}
考虑一个全局变量 `count`，初始为 0。两个线程都执行 `count++` 1000次。期望最终结果是 2000。
`count++` 在硬件层面通常不是原子操作，例如可能被翻译成以下指令序列：
\begin{verbatim}
Load R, count   ; 从内存加载 count 的值到寄存器 R
Add R, 1        ; 寄存器 R 中的值加一
Store R, count  ; 将寄存器 R 中的值存回内存 count
\end{verbatim}
如果在两个线程并发执行时发生如下交错：
\begin{itemize}
    \item 线程 A: `Load R1, count` (R1 = 0)
    \item 线程 B: `Load R2, count` (R2 = 0)
    \item 线程 A: `Add R1, 1` (R1 = 1)
    \item 线程 B: `Add R2, 1` (R2 = 1)
    \item 线程 A: `Store R1, count` (count = 1)
    \item 线程 B: `Store R2, count` (count = 1)
\end{itemize}
尽管执行了两次 `count++`，最终 `count` 的值却是 1，而不是期望的 2。这就是更新丢失，由竞争导致。

\paragraph{临界区 (Critical Section):}
访问共享资源的代码段称为临界区。同步问题本质上是保证对临界区的互斥访问。

\subsection{互斥 (Mutual Exclusion)}
目标是保证在任何时刻，最多只有一个线程在执行临界区中的代码。

\subsubsection{锁 (Lock / Mutex)}
锁是实现互斥的最常用工具。它是一个对象，可以在进入临界区前获取，在离开临界区后释放。
\begin{verbatim}
acquire(lock);
// 临界区 (Critical Section)
// 访问或修改共享资源
release(lock);
\end{verbatim}

\paragraph{锁的性质:} 一个好的锁实现应该满足以下性质：
\begin{itemize}
    \item **互斥 (Mutual Exclusion):** 任何时刻只有一个线程持有锁。
    \item **进步 (Progress):** 如果没有线程在临界区内，并且有线程想进入临界区，那么在有限时间内，某个想进入临界区的线程必须能够成功获取锁并进入临界区。
    \item **有限等待 (Bounded Waiting):** 如果一个线程请求进入临界区，那么在它被允许进入之前，其他线程进入临界区的次数是有限制的。这避免了饥饿 (Starvation)。
\end{itemize}

\paragraph{锁的实现方式:}
\begin{itemize}
    \item **禁用中断 (Disabling Interrupts):** 在单处理器上，进入临界区前禁用中断，离开后恢复。简单但粗暴，可能导致丢失重要中断，且在多处理器上无效。
    \item **自旋锁 (Spin Lock):** 线程在 `acquire()` 时，如果锁被持有，就在一个循环中不断“自旋”检查锁状态，直到锁可用。
    \begin{verbatim}
    acquire(lock):
        while (test_and_set(&lock->flag)); // 原子操作，设置标志并返回原值
    release(lock):
        lock->flag = 0;
    \end{verbatim}
    `test_and_set` 是一个原子硬件指令。自旋锁在多处理器且临界区非常短时有效（避免上下文切换开销），但如果临界区长，会导致大量 CPU 浪费在忙等上。
    \item **阻塞锁 (Blocking Lock):** 线程在 `acquire()` 时，如果锁被持有，则将自己放入一个等待队列并进入睡眠状态（阻塞）。当锁被 `release()` 时，唤醒等待队列中的一个或所有线程。
    \begin{verbatim}
    acquire(lock):
        while (lock_is_held) {
            add_to_wait_queue(current_thread);
            sleep(); // 线程阻塞，让出 CPU
        }
        lock_is_held = true;
    release(lock):
        lock_is_held = false;
        if (wait_queue_not_empty) {
            wakeup(a_waiting_thread);
        }
    \end{verbatim}
    阻塞锁适用于临界区较长的情况，避免 CPU 浪费，但上下文切换有开销。
\end{itemize}

\subsection{信号量 (Semaphore)}
信号量是一个整数变量 $S$，只能通过两个原子操作 `P` (或 `wait`, `acquire`) 和 `V` (或 `signal`, `release`) 来访问。
\begin{itemize}
    \item `P(S)`: $S = S - 1$。如果 $S$ 变为负值，则执行 `P` 的线程阻塞，放入信号量的等待队列。
    \item `V(S)`: $S = S + 1$。如果 $S$ 原本是负值（意味着有线程在等待），则唤醒等待队列中的一个线程。
\end{itemize}
信号量可以用来实现互斥和更复杂的同步。

\paragraph{二元信号量 (Binary Semaphore):}
初始值为 1 的信号量，功能与互斥锁类似。
\begin{verbatim}
semaphore mutex = 1;
P(mutex);
// 临界区
V(mutex);
\end{verbatim}

\paragraph{计数信号量 (Counting Semaphore):}
初始值大于 1 的信号量，用于控制对具有多个相同资源的访问。初始值表示可用资源的数量。

\paragraph{生产者-消费者问题 (Producer-Consumer Problem):}
使用有限大小的缓冲区同步生产者和消费者。
\begin{itemize}
    \item `mutex = 1`: 保护缓冲区本身的数据访问。
    \item `empty = N`: 表示缓冲区中空槽的数量 (初始为缓冲区大小 N)。
    \item `full = 0`: 表示缓冲区中已填充槽的数量 (初始为 0)。
\end{itemize}
\textbf{生产者代码:}
\begin{verbatim}
while (true) {
    item = produce_item(); // 生产物品
    P(empty); // 等待空槽可用
    P(mutex); // 锁定缓冲区
    add_item_to_buffer(item); // 将物品放入缓冲区
    V(mutex); // 解锁缓冲区
    V(full);  // 通知消费者，有新物品可用
}
\end{verbatim}
\textbf{消费者代码:}
\begin{verbatim}
while (true) {
    P(full);  // 等待物品可用
    P(mutex); // 锁定缓冲区
    item = remove_item_from_buffer(); // 从缓冲区取出物品
    V(mutex); // 解锁缓冲区
    V(empty); // 通知生产者，有空槽可用
    consume_item(item); // 消费物品
}
\end{verbatim}
注意 `P(empty)` 和 `P(full)` 在 `P(mutex)` 之前，这是为了避免可能的死锁（例如，如果先获取 mutex，但发现条件不满足需要等待 full/empty，而释放 mutex 才能让对方生产/消费，就可能死锁）。

\subsection{管程 (Monitor)}
管程是一种更高级的同步抽象，它将共享数据和访问这些数据的过程（函数）封装在一个模块中。管程保证在任何时刻，只有一个线程可以在管程内的某个过程中执行。

管程通常包含：
\begin{itemize}
    \item 共享数据 (Shared data)
    \item 访问共享数据的过程 (Procedures/Functions)
    \item 管程锁 (Monitor Lock): 隐式地由管程机制管理，确保互斥。
    \item 条件变量 (Condition Variables): 用于线程在管程内部等待某个条件成立。
\end{itemize}

\paragraph{条件变量 (Condition Variable):}
用于线程在持有管程锁的情况下，等待某个条件（基于共享数据）成立。有两个基本操作：
\begin{itemize}
    \item `wait(condition_variable)`: 调用线程原子地释放管程锁并进入该条件变量对应的等待队列中睡眠。当被唤醒时，线程会重新尝试获取管程锁，成功后从 `wait` 调用点返回。
    \item `signal(condition_variable)`: 如果有线程在 `condition_variable` 上等待，唤醒其中一个。如果没有线程等待，`signal` 操作无效果（与信号量的 `V` 不同）。唤醒的线程会排队等待获取管程锁。
\end{itemize}
`wait()` 和 `signal()` 都必须在持有管程锁的情况下调用。
关于 `signal` 的语义有两种常见实现：Hoare 语义（发出 signal 的线程立即将管程交给被唤醒的线程）和 Mesa 语义（发出 signal 的线程继续执行直到退出管程或再次等待，被唤醒的线程需要重新竞争管程锁）。Java 使用的是 Mesa 语义。

\subsection{经典同步问题}
\begin{itemize}
    \item **读者-写者问题 (Readers-Writers Problem):** 允许多个读者同时访问共享数据，但写者必须独占访问。有偏向读者和偏向写者的不同策略。
    \item **哲学家进餐问题 (Dining Philosophers Problem):** 五个哲学家围坐，每人左右一把筷子，思考或吃饭。吃饭需要两把筷子。这是一个经典的死锁和饥饿问题示例。解决方法包括：最多允许四个哲学家同时拿左手筷子、奇数号哲学家先拿左筷子偶数号先拿右筷子、使用管程等。
\end{itemize}

\vspace{2em} % 垂直间距
\hrule % 分隔线
\vspace{1em} % 垂直间距

% ==================================================
% 第14讲：内存管理 (Memory Management) - 详尽内容
% 来源: https://jyywiki.cn/OS/2025/lect14.md
% ==================================================
\section{第14讲：内存管理 (Memory Management)}

本讲深入探讨操作系统如何管理计算机的内存资源，包括地址空间、地址翻译、以及虚拟内存等核心概念。

\subsection{内存层次 (Memory Hierarchy)}
现代计算机系统采用分级存储结构，以平衡速度、容量和成本：
\begin{enumerate}
    \item **寄存器 (Registers):** CPU 内部，速度最快，容量最小，成本极高。
    \item **缓存 (Cache):** CPU 与主存之间，速度快，容量较小，成本高（L1, L2, L3 等）。
    \item **主内存 (Main Memory / RAM):** CPU 可直接访问，速度较慢，容量较大，成本相对较低。
    \item **磁盘存储 (Disk Storage / SSD):** 速度慢，容量巨大，成本最低（用于长期存储和虚拟内存交换）。
\end{enumerate}
内存管理的一个重要目标是利用数据的局部性原理（时间局部性：最近访问的数据很可能再次访问；空间局部性：访问一个数据后，其附近的数据也很可能被访问），通过缓存和虚拟内存等机制，使得程序能够以接近上一层存储介质的速度访问数据。

\subsection{地址空间 (Address Spaces)}
\paragraph{物理地址空间 (Physical Address Space):}
物理内存（RAM）上的地址范围。这是硬件实际的内存单元地址，由 CPU 的地址总线决定。

\paragraph{逻辑地址空间 (Logical Address Space):}
程序在编译或链接后看到的地址空间。每个进程都有自己的逻辑地址空间，通常从地址 0 开始编址。在没有内存保护和虚拟内存的简单系统中，逻辑地址可能直接对应物理地址（例如早期的 DOS）。

\paragraph{虚拟地址空间 (Virtual Address Space):}
在支持虚拟内存的操作系统中，进程看到的地址空间。它是一个抽象的概念，通常比物理内存大得多。虚拟地址需要通过地址翻译转换为物理地址才能访问实际内存。虚拟地址空间为每个进程提供了一个独立、连续的地址视图，简化了编程。

\subsection{内存管理单元 (Memory Management Unit, MMU)}
MMU 是 CPU 中的一个硬件组件，负责在程序运行时将虚拟地址（或逻辑地址）实时翻译成物理地址。

\paragraph{地址翻译 (Address Translation):}
MMU 根据页表（或段表）进行地址转换。

\subsection{连续内存分配 (Contiguous Allocation)}
早期的内存管理方法，要求进程的整个地址空间在物理内存中占据一个连续的块。
\begin{itemize}
    \item **固定分区 (Fixed Partitioning):** 物理内存被预先划分为固定大小的分区。会导致内部碎片（分区大于进程需求）和可用分区数量限制进程数量。
    \item **动态分区 (Dynamic Partitioning):** 物理内存根据进程需求动态划分，分区大小可变。
    \begin{itemize}
        \item 首次适应 (First Fit): 查找第一个足够大的空闲块。
        \item 最佳适应 (Best Fit): 查找最小的足够大的空闲块。
        \item 最差适应 (Worst Fit): 查找最大的空闲块。
    \end{itemize}
    动态分区的主要问题是外部碎片 (External Fragmentation): 总空闲空间足够，但分散成许多小块，无法满足新进程对连续大块内存的需求。可以通过紧缩 (Compaction) 来解决，但开销很大。
\end{itemize}
连续分配需要基址寄存器 (Base Register) 和界限寄存器 (Limit Register) 来实现简单的地址翻译和内存保护：物理地址 = 基址寄存器 + 逻辑地址，且逻辑地址必须小于界限寄存器。

\subsection{分页 (Paging)}
一种非连续内存分配方式，是实现虚拟内存的基础。它解决了连续内存分配的外部碎片问题。
\begin{itemize}
    \item **物理内存 (Physical Memory):** 被划分为固定大小的块，称为**页帧 (Page Frames)**。
    \item **虚拟地址空间 (Virtual Address Space):** 被划分为同样大小的块，称为**页 (Pages)**。页的大小通常是 2 的幂次方，例如 4KB。
\end{itemize}

\paragraph{地址翻译过程 (Paging):}
虚拟地址被分成两部分：页号 (Page Number, P) 和页内偏移量 (Offset, O)。
虚拟地址 = (页号 P, 页内偏移量 O)
MMU 使用进程的页表 (Page Table) 进行翻译：
页表以页号 P 作为索引，查找对应的页表条目 (Page Table Entry, PTE)。PTE 包含该虚拟页在物理内存中的起始地址，即对应的物理页帧号 (Frame Number, F)。
物理地址 = (物理页帧号 F, 页内偏移量 O)
物理地址 = F $\times$ Page\_Size + O

\paragraph{页表 (Page Table):}
每个进程都有一个页表，它存储了进程的虚拟页到物理页帧的映射关系。页表本身存储在物理内存中。
一个页表条目 (PTE) 通常包含以下信息：
\begin{itemize}
    \item **物理页帧号 (Physical Page Frame Number):** 指向该虚拟页所在的物理内存位置。
    \item **有效位 (Valid Bit):** 通常是一位。如果为 1，表示该页当前在物理内存中且映射有效；如果为 0，表示该页不在物理内存中（可能在磁盘上或从未被分配），访问会导致缺页中断 (Page Fault)。
    \item **保护位 (Protection Bits):** 控制对该页的访问权限，如只读、读写、可执行等。
    \item **修改位 / 脏位 (Dirty Bit):** 如果该页被写入过（修改过），此位为 1。在进行页面置换时，如果脏位为 1，需要将页的内容写回磁盘交换区；如果为 0，则无需写回。
    \item **访问位 (Accessed Bit):** 如果该页在上次页表被检查后被访问过（读或写），此位为 1。用于某些页面置换算法（如近似 LRU）。
\end{itemize}

\paragraph{页表的存储和开销:}
页表通常很大，因为它需要为进程虚拟地址空间中的每一个页提供一个条目。将整个页表保存在物理内存中会占用大量空间。
例如，一个 32 位地址空间（4GB）如果页大小是 4KB (2^12 bytes)，则有 2^20 = 1M 个页。如果每个 PTE 占 4 字节，页表大小就是 4MB。对于大量进程，总页表大小可能非常大。

\paragraph{多级页表 (Multilevel Page Tables):}
为了减少页表所需的物理内存空间，可以采用多级页表结构。将页表本身也进行分页。只有当前需要访问的页表页才需要驻留在物理内存中。这以增加地址翻译时的内存访问次数为代价（例如二级页表需要两次内存访问来查找 PTE）。

\paragraph{快表 (Translation Lookaside Buffer, TLB):}
为了加速页式存储系统中的地址翻译过程，MMU 中包含一个 TLB。TLB 是一个高速缓存，用于存储最近使用的页表条目 (PTEs)。
\begin{itemize}
    \item **TLB 命中 (TLB Hit):** 如果在 TLB 中找到了虚拟地址对应的 PTE，则可以直接获取物理页帧号，地址翻译非常快（硬件完成）。
    \item **TLB 未命中 (TLB Miss):** 如果 TLB 中没有对应的 PTE，MMU 需要访问主内存中的页表来获取 PTE，然后将 PTE 存入 TLB (可能需要替换一个旧条目)，最后完成地址翻译。TLB 未命中会显著增加地址翻译的时间。
\end{itemize}
TLB 通常很小但速度极快。

\subsection{虚拟内存与按需分页 (Virtual Memory and Demand Paging)}
虚拟内存允许程序使用的虚拟地址空间大小超过物理内存的容量。这是通过将不常用的虚拟页存储在磁盘上的交换区 (Swap Space / Paging File) 实现的。
按需分页 (Demand Paging) 是虚拟内存的一种实现策略：只有当进程实际访问到某个虚拟页时，才将其从磁盘加载到物理内存。

\paragraph{缺页中断 (Page Fault):}
当 CPU 访问一个虚拟地址，MMU 查找页表发现对应的 PTE 的有效位为 0（表示页不在内存中）时，会触发一个陷阱 (Trap) 或异常，称为缺页中断。
操作系统内核的缺页中断处理程序会执行以下步骤：
\begin{enumerate}
    \item 捕获缺页中断。
    \item 确定是哪个虚拟地址导致了中断，计算出页号。
    \item 检查该页的合法性（是否在进程的虚拟地址空间范围内）。
    \item 如果合法，找到该页在磁盘交换区中的位置。
    \item 查找一个空闲的物理页帧。
    \item **页面置换 (Page Replacement):** 如果没有空闲页帧，根据页面置换算法选择一个物理页帧，将其内容换出到磁盘（如果该页是脏页），并释放该页帧。
    \item 将缺页从磁盘加载到选定的物理页帧中。
    \item 更新进程的页表，将新加载页的 PTE 的有效位设为 1，并填入物理页帧号。
    \item 重新执行导致缺页中断的指令。
\end{enumerate}

\paragraph{页面置换算法 (Page Replacement Algorithms):}
在物理内存满时，决定替换哪个页以腾出空间。目标是尽量减少缺页率。
\begin{itemize}
    \item **最优算法 (OPT - Optimal):** 替换将来最长时间内不会被访问的页。理论上最优，但无法实现（需要预知未来访问序列）。
    \item **先进先出 (FIFO - First-In, First-Out):** 替换在内存中驻留时间最长的页。实现简单，但可能淘汰常用页（Belady's anomaly）。
    \item **最近最少使用 (LRU - Least Recently Used):** 替换最近最长时间未被使用的页。基于时间局部性原理，是实际系统中常用的算法或其近似。实现开销较大（需要记录访问时间或顺序）。
    \item **时钟算法 (Clock):** LRU 的一种近似实现，使用访问位 (Accessed Bit) 构建一个循环列表。开销较低。
\end{itemize}

\subsection{交换 (Swapping)}
比分页更粗粒度的内存管理方式。可以将整个进程的地址空间（所有页或段）作为一个整体从内存换出到磁盘，或从磁盘换入内存。在内存资源极度紧张时使用。

\subsection{分段 (Segmentation)}
另一种非连续内存分配方式，将程序的地址空间划分为多个逻辑上独立的段 (Segment)，如代码段、数据段、栈段、堆段等。每个段有独立的起始地址和长度。
\begin{itemize}
    \item **地址表示:** 虚拟地址由 (段号 S, 段内偏移量 O) 组成。
    \item **地址翻译:** MMU 使用段表 (Segment Table) 将段号 S 映射到该段在物理内存中的起始物理地址（基地址 Base）。物理地址 = Base + O。需要检查 O 是否小于段的长度 Limit。
    \item **优点:** 更符合程序逻辑结构，易于实现内存保护和共享（不同进程的段表可以指向同一个物理内存区域）。
    \item **缺点:** 容易产生外部碎片。段的长度可变，内存回收和分配时可能出现大小不一的空闲块。
\end{itemize}
现代操作系统通常结合使用分页和分段，例如 x86 架构的硬件支持分段，但操作系统软件层面通常主要依赖于分页和虚拟内存。

\section{总结}
第13讲重点讲解了多任务环境下的同步挑战，从基本的竞争条件引出锁、信号量、管程等同步原语，并讨论了经典同步问题及其解决方案。理解这些机制对于编写正确的并发程序至关重要。

第14讲详细介绍了操作系统的内存管理，从内存层次结构到地址空间的概念，再到分页机制的原理和实现细节，包括页表、TLB、虚拟内存和页面置换。高效的内存管理是实现多任务和提高系统性能的基础。

\end{document}