第13周星期二第2大节

视频：screen_操作系统与分布式计算_第13周_星期二_第2大节.mp4
字幕：transcripts/第13周_星期二_第2大节.srt

课程信息

第13周，课程共16周，下节课开始去机房
机房地点在i北理通知
后续课程：实验+答疑+习题课
银行叫号PV操作留作思考（下节课讲）

磁盘访问时间组成

一次磁盘读写的时间 = 寻道时间 + 旋转延迟时间 + 数据传输时间

寻道时间：磁头移动到目标磁道的时间（毫秒级，最慢）
旋转延迟时间：目标扇区旋转到磁头下方的时间
数据传输时间：读写数据的时间（由磁盘物理特性决定，OS无法改变）

OS层面优化目标：减少寻道时间和旋转延迟时间

磁盘调度算法

FCFS（先来先服务）`[06:59]`

按请求到达顺序依次服务，磁头无序移动。

实例：磁头起始100号磁道，请求序列55→58→39→18→90→160→150→38→184
平均寻道：55.3（最差，但公平无饥饿）

SSTF（最短寻道时间优先）`[11:01]`

每次选择离当前磁头最近的磁道请求。

实例：100→90→58→55→39→38→18→150→160→184
平均寻道：27.5（性能最优）
问题：饥饿现象 / 磁壁黏着 — 磁头总在几个相近磁道间来回移动，远端请求长时间得不到响应

SCAN（电梯算法）`[15:01]`

磁头先沿一个方向移动，响应沿途所有请求，到达该方向最远端后折返。

实例（先向增大方向）：100→150→160→184→（折返）→90→58→55→39→38→18
既保留SSTF的局部优势，又防止磁壁黏着

C-SCAN（循环扫描）`[18:29]`

单向扫描，到达最远端后直接回到最始端（不响应沿途请求），再开始新的一轮。

实例（仅向上响应）：100→150→160→184→（直接回18）→18→38→39→55→58→90
响应时间更均匀，减少极端等待

Look / C-Look（改进）

Look：不固定扫描到磁盘两端，只扫描到当前有请求的最远端即折返
C-Look：类似C-SCAN，但只到有请求的最远端即回始端

N-step SCAN `[22:04]`

将磁盘请求队列分成N个子队列（按时间划分），每个子队列内独立执行SCAN。新请求排入后续队列，不影响当前队列的扫描。

N=1 → 退化为FCFS
N很大 → 接近普通SCAN，黏着问题复现

FSCAN（双队列）`[24:32]`

N-step SCAN的简化版：只分两个队列。当前队列扫描期间，新来的请求进入另一个队列。当前队列处理完后再切换到新队列。

现代磁盘调度器常用策略

扇区交替编号（减少旋转延迟）`[26:41]`

不按物理顺序连续编号，而是交错排列（如1,3,5,7,2,4,6,8）。当读完1号扇区并传输数据时，磁盘已旋转到2号扇区位置，可直接读取，避免等待下一圈。减少旋转延迟时间。

RAID（磁盘阵列）`[29:01]`

多块磁盘组合提供数据冗余和/或性能提升。

RAID 0（条带化）：数据分块存储在多个磁盘，提高读写效率，无冗余
RAID 1（镜像）：数据同时写入两块磁盘，一块损坏可恢复
RAID 5：带奇偶校验的条带化，单盘故障可恢复
RAID 0+1 / RAID 1+0：组合模式

RPC（远程过程调用）`[32:41]`

概念

RPC使分布式系统中的远程函数调用，在使用体验上与本地调用一致。Client发请求→网络传输→Server执行→返回结果。

核心组件

Client Stub（客户端存根）：将函数调用参数打包（编组）成消息，发送到Server，并接收返回结果解包
Server Stub（服务器存根）：接收请求消息，解包，调用实际的服务函数，打包结果返回
IDL（接口定义语言）：跨语言/跨平台描述RPC接口。IDL Compiler编译生成三个文件：
1. client_stub.c — 客户端代理
2. server_stub.c — 服务器代理
3. header.h — 接口声明头文件
UUID：每个RPC接口的唯一标识，用于区分不同的服务
ACF（应用程序配置文件）：指定客户端如何请求绑定

调用过程示例（阶乘计算）

IDL定义接口 rpc_fact（含UUID、函数名、参数、返回值）
IDL Compiler生成 client_stub.c、server_stub.c、fact.h
Server端：include fact.h，实现阶乘函数，注册服务到Binder
Client端：include fact.h，直接调用 rpc_fact(n)，语法与本地调用完全相同
底层：Client Stub打包→网络发送→Server Stub解包→执行→打包返回

Binding（绑定）机制

Binder（类似于工商注册中心）：Server注册自己的服务（UUID + 能力），Client查询所需服务
Server注册 → Client查询 → Binder返回Server信息 → Client直接调用
通过Binder实现Client与Server的动态绑定

Linux内存管理

物理内存分区

32位Linux将物理内存分为三个Zone（区域）：

Zone	范围	用途
`ZONE_DMA`	<16MB	DMA方式数据缓冲
`ZONE_NORMAL`	16MB~896MB	内核虚拟地址映射（系统空间）
`ZONE_HIGHMEM`	>896MB	用户空间（进程映像）

分配优先级：首选 HIGHMEM → 满时用 NORMAL → DMA专用

Buddy System（伙伴系统）`[01:01:53]`

Linux物理页面分配的核心算法，管理空闲页块，减少外部碎片。

基本思想：将物理页面组织成2的幂次大小的块链表（1, 2, 4, 8, 16页…），分配时从大到小剖分，回收时将相邻伙伴合并。

示例（16页初始→分配2页）：

初始：空闲链表仅16页块 [0-15]
请求2页 → 剖分16→[0-7]+[8-15]，[8-15]入8页链表
[0-7]剖分→[0-3]+[4-7]，[4-7]入4页链表
[0-3]剖分→[0-1]+[2-3]，[0-1]分配出去，[2-3]入2页链表

回收：释放[0-1] → 检查伙伴[2-3]是否空闲 → 合并为[0-3] → 继续检查伙伴[4-7] → 逐级向上合并

伙伴定义：大小相同 + 物理地址连续 + 第一个页帧编号为2的倍数

优点：

保留大的连续空间
分配的内存尽量连续 → 提高TLB命中率（连续空间使页表项更易在Cache中命中）
减少外部碎片

Slab分配器 `[01:25:31]`

处理小对象分配（Buddy以页为单位，4K以下会造成内部碎片）。

思想：为常用的小对象预分配缓存（Cache），将多个同类型小对象打包成一个大的页面，向Buddy System申请，充当Buddy与内核之间的中间代理。

每种对象类型有自己的Slab缓存（如int cache、inode cache等）
每个Slab由一个或多个连续物理页组成，包含若干个同类型对象
通用预分配大小：32B、64B、128B、4K、128K等

优点：

减小内部碎片
管理局部化，减少与Buddy系统的直接交互，提高效率

相关系统调用：kmem_cache_create、kmalloc、kfree等

Linux进程内存管理 `[01:25:31]`

两级页表（32位）

32位Linux虚拟地址：页目录(10位) + 页表项(10位) + 页内偏移(12位=4K)

线性地址→物理地址转换：

CR3寄存器指向进程的页目录
逻辑地址高10位索引页目录 → 获取页表
中间10位索引页表 → 获取物理页帧号
低12位页内偏移拼接 → 物理地址

页表项标志位：存在位、读写位、访问位、脏位

`mm_struct`

每个进程的task_struct中包含指向mm_struct的指针，描述进程的完整内存映像：

指向页目录的指针（PGD）
指向vm_area_struct链表的指针
代码段/数据段/堆/栈的地址范围等

`vm_area_struct`

描述进程虚拟地址空间中的一个连续区域（如代码段、堆、栈、mmap区域等），组织成链表/红黑树。

用户态与核心态系统调用

brk — 改变堆大小
exit — 结束进程，释放空间
mmap / munmap — 映射/取消映射文件或匿名内存
shmget — 创建共享存储区

Copy-on-Write（写时拷贝）`[01:42:23]`

fork()创建子进程时，父进程与子进程共享同一物理页面（页表项指向相同页帧，标记为只读），不立即复制。

写触发：子进程或父进程要写入共享页面时 → 触发缺页异常 → OS分配新物理页帧 → 复制原内容 → 修改页表为可写 → 分别映射各自的副本。

优点（Lazy策略）：

避免一次性拷贝所有数据，开销分散
只被写入的页面才真正复制，共享页面保留
提高进程创建效率

缺页异常处理：do_page_fault 函数 → 判断地址是否在有效区域 → 区分写缺失/页不在内存 → 执行对应的处理（分配、换入、COW）

考试说明 `[01:54:27]`

试卷结构（总成绩70%）

题型	题量	分值
选择题	15题	30分
填空题	20题	20分
简答题	—	15分
计算分析题	—	35分
合计		100分

强调理解与灵活运用，非死记硬背。

核心考点

FCFS/SSTF/SCAN/C-SCAN磁盘调度计算
RAID级别区别
Buddy System剖分与合并
写时拷贝（Copy-on-Write）
进程状态转换、PV操作、信号量

习题课范围

操作系统概论（发展历程、并发/并行、用户态/核心态、系统调用）
进程管理（状态转换、进程调度、PV操作、死锁）
下节课（机房）：银行叫号PV操作 + 实验 + 答疑

Notes@Tsukino

探索

第13周_星期二_第2大节

第13周星期二第2大节

课程信息

磁盘访问时间组成

磁盘调度算法

FCFS（先来先服务）`[06:59]`

SSTF（最短寻道时间优先）`[11:01]`

SCAN（电梯算法）`[15:01]`

C-SCAN（循环扫描）`[18:29]`

Look / C-Look（改进）

N-step SCAN `[22:04]`

FSCAN（双队列）`[24:32]`

扇区交替编号（减少旋转延迟）`[26:41]`

RAID（磁盘阵列）`[29:01]`

RPC（远程过程调用）`[32:41]`

概念

核心组件

调用过程示例（阶乘计算）

Binding（绑定）机制

Linux内存管理

物理内存分区

Buddy System（伙伴系统）`[01:01:53]`

Slab分配器 `[01:25:31]`

Linux进程内存管理 `[01:25:31]`

两级页表（32位）

`mm_struct`

`vm_area_struct`

用户态与核心态系统调用

Copy-on-Write（写时拷贝）`[01:42:23]`

考试说明 `[01:54:27]`

试卷结构（总成绩70%）

核心考点

习题课范围

关系图谱

目录

Notes@Tsukino

探索

第13周_星期二_第2大节

第13周 星期二 第2大节

课程信息

磁盘访问时间组成

磁盘调度算法

FCFS（先来先服务）[06:59]

SSTF（最短寻道时间优先）[11:01]

SCAN（电梯算法）[15:01]

C-SCAN（循环扫描）[18:29]

Look / C-Look（改进）

N-step SCAN [22:04]

FSCAN（双队列）[24:32]

扇区交替编号（减少旋转延迟）[26:41]

RAID（磁盘阵列）[29:01]

RPC（远程过程调用）[32:41]

概念

核心组件

调用过程示例（阶乘计算）

Binding（绑定）机制

Linux内存管理

物理内存分区

Buddy System（伙伴系统）[01:01:53]

Slab分配器 [01:25:31]

Linux进程内存管理 [01:25:31]

两级页表（32位）

mm_struct

vm_area_struct

用户态与核心态系统调用

Copy-on-Write（写时拷贝）[01:42:23]

考试说明 [01:54:27]

试卷结构（总成绩70%）

核心考点

习题课范围

关系图谱

目录

第13周星期二第2大节

FCFS（先来先服务）`[06:59]`

SSTF（最短寻道时间优先）`[11:01]`

SCAN（电梯算法）`[15:01]`

C-SCAN（循环扫描）`[18:29]`

N-step SCAN `[22:04]`

FSCAN（双队列）`[24:32]`

扇区交替编号（减少旋转延迟）`[26:41]`

RAID（磁盘阵列）`[29:01]`

RPC（远程过程调用）`[32:41]`

Buddy System（伙伴系统）`[01:01:53]`

Slab分配器 `[01:25:31]`

Linux进程内存管理 `[01:25:31]`

`mm_struct`

`vm_area_struct`

Copy-on-Write（写时拷贝）`[01:42:23]`

考试说明 `[01:54:27]`