第1章 简介（Introduction） 1
1-1 什么是操作系统（What is an Operating System） 2
1-1-1 用户观点（User View） 2
1-1-2 系统观点（System View） 3
1-1-3 系统目标（System Goals） 3
1-1-4 系统特征迁移（System Feature Migration） 4
1-2 单节点系统（Single-Node Systems） 5
1-2-1 大型计算机系统（Mainframe Systems） 5
1-2-2 个人计算机系统（Personal-Computer Systems） 7
1-2-3 多处理器计算机系统（Multiprocessor Systems） 7
1-3 多节点系统（Multiple-Node Systems） 9
1-3-1 分布式系统（Distributed Systems） 9
1-3-2 集群式系统（Clustered Systems） 10
1-4-1 实时系统（Real-Time Systems） 11
1-4 特殊目的系统（Special-Purpose Systems） 11
1-4-2 掌上型系统（Handheld Systems） 12
1-4-3 嵌入式系统（Embedded Systems） 13
1-5 计算环境（Computing Environments） 13
1-5-1 传统式计算（Traditional Computing） 13
1-5-2 因特网式计算（Web-based Computing） 14
1-5-3 嵌入式计算（Embedded Computing） 14
1-6 小结 15
1-7 作业（Homework） 15
第2章 硬件结构（Hardware Structures） 17
2-1 CPU(Central Processing Unit) 18
2-1-1 寄存器（Register） 19
2-1-2 冯诺依曼计算机（Von Neumann Machine） 19
2-2-1 内存（Memory） 20
2-2 存储设备（Storage Device） 20
2-2-2 高速缓存（Caching） 21
2-2-3 磁盘（Magnetic Disk） 22
2-2-4 磁带（Magnetic Tape） 22
2-3 I/O结构（I/O Structure） 23
2-3-1 总线（Bus） 23
2-3-2 控制器（Controller） 24
2-3-3 I/O中断（I/O Interrupt） 25
2-3-4 直接内存访问（Direct Memory Access,DMA） 26
2-4 存储层次结构（Storage Hierarchy） 27
2-4-1 连贯性（Coherency） 28
2-4-2 一致性（Consistency） 29
2-5 硬件保护（Hardware Protection） 29
2-5-2 I/O保护（I/O Protection） 30
2-5-1 双状态运行（Dual-Mode Operation） 30
2-5-3 CPU保护（CPU Protection） 31
2-5-4 内存保护（Memory Protection） 31
2-6 小结 32
2-7 作业（Homework） 33
第3章 操作系统结构（Operating-System Structures） 35
3-1 系统组成（System Components） 36
3-1-1 进程管理（Process Management） 36
3-1-2 主存储器管理（Main Memory Management） 37
3-1-3 文件管理（File Management） 37
3-1-4 I/O系统管理（I/O System Management） 38
3-1-5 辅存管理（Secondary-Storage Management） 38
3-1-6 网络（Networking） 39
3-1-7 保护系统（Protection System） 39
3-1-8 命令解释程序系统（Command-Interpreter System） 39
3-2 操作系统服务（Operating-System Services） 40
3-3 系统调用（System Call） 41
3-3-1 进程控制（Process Control） 42
3-3-2 内存管理（Memory Management） 42
3-3-3 文件操作（File Manipulation） 43
3-3-4 设备管理（Device Management） 43
3-3-5 信息维护（Information Maintenance） 43
3-3-6 进程间通信（Interprocess Communication） 44
3-4 系统结构（System Structure） 45
3-4-1 简单结构（Simple Structure） 45
3-4-2 分层方法（Layered Approach） 46
3-4-3 微内核（Microkernel） 46
3-5 虚拟机（Virtual Machine） 47
3-5-1 实现（Implementation） 48
3-5-2 优点（Benefits） 48
3-6-2 机制和策略（Mechanism and Policies） 49
3-6 系统设计（System Design） 49
3-6-1 设计目标（Design Goals） 49
3-6-3 实现（Implementation） 50
3-7 小结 50
3-8 作业（Homework） 51
第4章 进程（Processes） 53
4-1 进程概念（Process Concept） 54
4-1-1 简介（Introduction） 54
4-1-2 进程的状态（Process State） 54
4-1-3 进程控制块（Process Control Block） 55
4-2 进程调度（Process Scheduling） 56
4-2-1 调度队列（Scheduling Queue） 56
4-2-2 调度器（Schedulers） 57
4-3-1 进程的建立（Process Creation） 58
4-2-3 上下文切换（Context Switch） 58
4-3 进程的建立与结束（Process Creation and Termination） 58
4-3-2 进程的结束（Process Termination） 59
4-4 线程（Thread） 60
4-4-1 线程概念（Thread Concept） 60
4-4-2 线程的优点（Benefits of Thread） 60
4-4-3 用户和内核线程（User and Kernel Thread） 61
4-4-4 多线程的模型（Multithreading Models） 61
4-5 进程合作（Processes Cooperation） 62
4-5-1 缓冲区（Buffer） 63
4-5-2 生产者（Producer） 63
4-5-3 消费者（Consumer） 64
4-6 进程间通信（InterProcess Communication） 64
4-6-1 基本结构（Basic Structure） 64
4-6-2 直接通信（Direct Communication） 65
4-6-3 间接通信（Indirect Communication） 66
4-6-4 同步（Synchronization） 67
4-6-5 缓冲（Buffering） 67
4-6-6 异常状况（Exception Conditions） 68
4-7 小结 69
4-8 作业（Homework） 70
第5章 调度（Scheduling） 71
5-1 调度概念（Scheduling Concept） 72
5-1-1 进程行为（Process Behavior） 72
5-1-2 CPU调度器（CPU Scheduler） 73
5-1-3 调度时机（Schedule Occasion） 73
5-1-4 分派器（Dispatcher） 74
5-1-5 调度准则（Scheduling Criteria） 74
5-2-1 先来先服务调度（FCFS Scheduling） 75
5-2 调度方法（ Scheduling Method） 75
5-2-2 最短工作优先调度（SJF Scheduling） 76
5-2-3 优先级调度（Priority Scheduling） 79
5-2-4 时间片轮转调度（Round-Robin Scheduling） 80
5-2-5 多级队列调度（Multilevel Queue Scheduling） 81
5-2-6 多级反馈队列调度（Multilevel Feedback Queue Scheduling） 82
5-3 特殊用途调度（Special Purpose Scheduling） 83
5-3-1 多处理器调度（Multiple-Processor Scheduling） 83
5-3-2 实时调度（Real-Time Scheduling） 84
5-4 调度评估（Scheduling Evaluation） 85
5-4-1 定性模式（Deterministic Modeling） 85
5-4-2 排队模型（Queuing Models） 86
5-4-4 实现（Implementation） 87
5-4-3 仿真（Simulations） 87
5-5 小结 88
5-6 作业（Homework） 89
第6章 同步与死锁（Synchronization and Deadlock） 91
6-1 进程同步（Process Synchronization） 92
6-2 临界区（Critical Section） 93
6-2-1 交替算法（Turn Algorithm） 94
6-2-2 标识算法（Flag Algorithm） 94
6-2-3 综合算法（Combination Algorithm） 95
6-2-4 面包店算法（Bakery Algorithm） 96
6-2-5 硬件支持（Hardware Support） 97
6-3 信号量（Semaphore） 99
6-3-1 计数信号量（Counting Semaphore） 99
6-4 同步的经典问题（Classical Problems of Synchronization） 101
6-4-1 有限缓冲区问题（The Bounded-Buffer Problem） 101
6-3-2 二元信号量（Binary Semaphore） 101
6-4-2 读取者与写入者问题（The Readers and Writers Problem） 102
6-4-3 哲学家晚餐问题（The Dining-Philosophers Problem） 103
6-5 临界区域与监控程序（Critical Region and Monitor） 104
6-5-1 临界区域（Critical Region） 104
6-5-2 监控程序（Monitor） 105
6-6 死锁简介（Deadlock Introduction） 107
6-6-1 死锁特性（Deadlock Characterization） 107
6-6-2 死锁检测（Deadlock Detection） 108
6-6-3 死锁解除（Recovery from Deadlock） 109
6-7 死锁预防（Deadlock Prevention） 110
6-7-1 互斥（Mutual Exclusion） 110
6-7-2 占用与等待（Hold and Wait） 110
6-7-3 不可抢占（No Preemption） 110
6-8-1 安全状态（Safe State） 111
6-7-4 循环等待（Circular Wait） 111
6-8 死锁避免（Deadlock Avoidance） 111
6-8-2 资源分配图算法（Resource-Allocation Graph Algorithm） 112
6-8-3 银行家算法（Banker's Algorithm） 112
6-9 小结 114
6-10 作业（Homework） 114
第7章 与进程相关的实现（Process Related Implementation） 117
7-1 数据结构（Data Structure） 118
7-1-1 进程描述符（Process Descriptor） 118
7-1-2 进程状态（Process State） 119
7-1-3 进程链表（Process List） 120
7-1-4 就绪队列（Ready Queue） 120
7-2 进程运行（Process Operation） 121
7-2-1 进程建立（Process Creation） 121
7-2-2 上下文切换（Context Switch） 124
7-2-3 进程结束（Process Termination） 128
7-3 进程间的通信（Interprocess Communication） 129
7-3-1 自旋锁（Spin Lock） 129
7-3-2 信号量（Semaphore） 131
7-3-3 消息队列（Message Queue） 133
7-4 小结 137
7-5 作业（Homework） 138
第8章 内存管理（Memory Management） 139
8-1 背景介绍（Background） 140
8-1-1 地址空间（Address Space） 140
8-1-2 地址绑定（Address Binding） 141
8-1-3 重叠（Overlays） 141
8-1-4 置换（Swapping） 142
8-2-1 单一分割分配（Single-Partition Allocation） 143
8-2 连续分配（Contiguous Allocation） 143
8-2-2 多重分割分配（Multiple-Partition Allocation） 144
8-2-3 碎片（Fragmentation） 146
8-3 分页（Paging） 147
8-3-1 基本方法（Basic Method） 147
8-3-2 分页表的结构（Structure of Page Table） 148
8-3-3 多层分页法（Multilevel Paging） 151
8-3-4 反转分页表（Inverted Page Table） 152
8-4 分段（Segmentation） 153
8-4-1 基本方法（Basic Method） 153
8-4-2 段页式（Segmentation with Paging） 155
8-5 小结 156
8-6 作业（Homework） 157
第9章 虚拟内存（Virtual Memory） 159
9-1-1 基本概念（Basic Concept） 160
9-1 背景介绍（Background） 160
9-1-2 需求分页（Demand Paging） 161
9-1-3 需求分页的性能（Performance of Demand Paging） 163
9-2 分页替换（Page Replacement） 164
9-2-1 先进先出算法（FIFO Algorithm） 165
9-2-2 优化算法（Optimal Algorithm） 166
9-2-3 最近最久未使用淘汰算法（LRU Algorithm） 167
9-2-4 最近最久未使用淘汰近似算法（LRU Approximation Algorithms） 168
9-2-5 最不频繁使用淘汰算法（LFU Algorithm） 170
9-2-6 最频繁使用淘汰算法（MFU Algorithm） 170
9-2-7 分页缓冲算法（Page Buffering Algorithm） 170
9-3 页框分配（Frame Allocation） 171
9-3-1 最少页框数目（Minimum Number of Frames） 171
9-3-3 全局与局部分配（Global and Local Allocation） 172
9-3-2 分配算法（Allocation Algorithms） 172
9-4 颠簸现象（Thrashing） 173
9-4-1 颠簸现象的成因（Cause of Thrashing） 173
9-4-2 工作集模型（Working Set Model） 174
9-4-3 分页错误频率（Page Fault Frequency） 175
9-5 实现问题（Implementation Issues） 176
9-5-1 预先分页（Prepaging） 176
9-5-2 程序结构（Program Structure） 176
9-5-3 分页服务程序（Paging Daemons） 177
9-5-4 分页上锁（Page Locking） 177
9-5-5 分页大小（Page Size） 178
9-5-6 其他考虑（Other Considerations） 178
9-6 小结 178
9-7 作业（Homework） 179
第10章 内存管理实现（Memory Management Implementation） 181
10-1 内存寻址（Memory Addressing） 182
10-1-1 硬件分段支持（Segmentation in Hardware） 182
10-1-2 Linux上的分段（Segmentation in Linux） 185
10-1-3 硬件分页支持（Paging in Hardware） 186
10-1-4 Linux上的分页（Paging in Linux） 188
10-2 页框管理（Page Frame Management） 190
10-2-1 页框运行（Operations of Page Frames） 190
10-2-2 对偶式系统算法（Buddy System Algorithm） 193
10-3 内存区域管理（Memory Area Management） 195
10-3-1 Slab分配器（Slab Allocator） 195
10-3-2 Slab运行（Slab Operations） 196
10-4 小结 197
10-5 作业（Homework） 198
第11章 文件系统简介（File System Introduction） 199
11-1 文件基本概念（File Concept） 200
11-1-1 文件属性（File Attributes） 200
11-1-2 文件操作（File Operations） 201
11-1-3 文件类型（File Types） 202
11-1-4 文件分配表（File Allocation Table） 203
11-2 文件访问与保护（File Access and Protection） 204
11-2-1 文件访问（File Access） 204
11-2-2 访问权限（Access Type） 205
11-2-3 访问组（Access Groups） 206
11-3 目录结构（Directory Structure） 207
11-3-1 单层目录（Single-Level Directory） 208
11-3-2 双层目录（Double-Level Directory） 209
11-3-3 树状目录（Tree-Structured Directory） 210
11-3-4 非循环图状目录（Acyclic-Graph Directory） 210
11-3-5 一般图状目录（General Graph Directory） 211
11-4 目录访问与保护（Directory Access and Protection） 212
11-4-1 目录访问指令（Directory Access Operation） 212
11-4-2 目录与文件路径（Path） 212
11-4-3 目录访问保护（Directory Protection） 213
11-4-4 文件系统挂接（Mounting） 214
11-5 一致性语义（Consistency Semantics） 214
11-5-1 UNIX语义（UNIX Semantics） 214
11-5-2 Session语义（Session Semantics） 214
11-5-3 Immutable语义（Immutable Semantics） 215
11-6 小结 215
11-7 作业（Homework） 216
第12章 文件系统实现（File System Implementation） 217
12-1-1 文件访问（File Access） 218
12-1 文件系统结构（File System Structure） 218
12-1-2 打开文件表（Open File Table） 219
12-1-3 共享文件（Shared Files） 220
12-2 可用空间管理（Free Space Management） 220
12-2-1 链表（Linked List） 221
12-2-2 位向量（Bit Vector） 222
12-2-3 计数（Counting） 222
12-3 文件分配方法（File Allocation Method） 223
12-3-1 连续式分配（Contiguous Allocation） 223
12-3-2 链表式分配（Linked List Allocation） 224
12-3-3 索引式分配（Indexed Allocation） 226
12-4 文件目录实现（Directory Implementation） 227
12-4-1 线性链表（Linear List） 227
12-4-2 哈希表（Hash Table） 228
12-5-1 性能（Performance） 229
12-5 文件系统评估（File System Evaluation） 229
12-5-2 效率（Efficiency） 230
12-5-3 可靠性（Reliability） 230
12-5-4 一致性（Consistency） 231
12-6 小结 232
12-7 作业（Homework） 233
第13章 文件系统实例（File System Examples） 235
13-1 UNIX文件系统（UNIX File System） 236
13-1-1 架构（Framework） 236
13-1-2 inode 236
13-1-3 Superblock 238
13-2 Linux文件系统（Linux File Systems） 238
13-2-1 虚拟文件系统（Virtual File System） 239
13-2-2 一般文件系统（General File Systems） 240
13-2-3 目志式文件系统（Journaling File Systems） 242
13-2-4 其他文件系统（Other File Systems） 243
13-3 Windows文件系统（Windows File System） 244
13-3-1 内部布局（Internal Layout） 244
13-3-2 复原（Recovery） 245
13-3-3 安全（Security） 246
13-3-4 压缩（Compression） 246
13-4 小结 247
13-5 作业（Homework） 248
第14章 输出／输入系统（I/O Systems） 249
14-1 I/O硬件（I/O Hardware） 250
14-1-1 轮询（Polling） 251
14-1-2 中断（Interrupts） 252
14-1-3 直接内存访问（Direct Memory Access） 254
14-2 应用系统I/O接口（Application I/O Interface） 255
14-2-1 块和字符设备（Block and Character Devices） 257
14-2-2 网络设备（Network Devices） 258
14-2-3 时钟与定时器（Clocks and Timers） 258
14-2-4 阻塞与非阻塞I/O（Blocking and Nonblocking I/O） 259
14-3 内核I/O子系统（Kernel I/O Subsystem） 259
14-3-1 I/O调度（I/O Scheduling） 259
14-3-2 缓冲（Buffering） 260
14-3-3 高速缓存（Caching） 261
14-3-4 假脱机和设备预留（Spooling and Device Reservation） 261
14-3-5 错误处理（Error Handling） 262
14-3-6 内核数据结构（Kernel Data Structures） 262
14-4 实现问题（Implementation Issues） 264
14-4-1 操作转换（Operations Transforming） 264
14-4-2 驱动流（STREAMS） 266
14-4-3 性能（Performance） 267
14-5 小结 269
14-6 作业（Homework） 270
第15章 大容量存储结构（Mass-Storage Structure） 271
15-1 磁盘调度（Disk Scheduling） 272
15-1-1 磁盘结构（Disk Structure） 272
15-1-2 FCFS调度（FCFS Scheduling） 272
15-1-3 SSTF调度（SSTF Scheduling） 273
15-1-4 SCAN与C-SCAN调度（SCAN and C-SCAN Scheduling） 273
15-1-5 LOOK与C-LOOK调度（LOOK and C-LOOK Scheduling） 274
15-1-6 算法选择（Algorithm Selection） 275
15-2 磁盘管理（Disk Management） 275
15-2-1 磁盘格式化（Disk Formatting） 275
15-2-2 启动块（Boot Block） 276
15-3 RAID结构（RAID Structure） 277
15-2-3 损坏块（Bad Blocks） 277
15-3-1 可靠性和性能（Reliability and Performance） 278
15-3-2 RAID层次结构（RAID Levels） 278
15-3-3 选择RAID层次结构（Selecting a RAID Level） 281
15-4 存储设备附加方式（Storage Attachment） 281
15-4-1 主机附加存储设备（Host-Attached Storage） 281
15-4-2 附网存储设备（Network-Attached Storage） 282
15-4-3 存储区域网（Storage-Area Network） 282
15-5 其他存储问题（Other Storage Issues） 283
15-5-1 稳定存储体（Stable Storage） 283
15-5-2 第三存储设备（Tertiary Storage Devices） 283
15-5-3 操作系统问题（Operating-System Issues） 284
15-5-4 性能问题（Performance Issues） 285
15-6 小结 287
15-7 作业（Homework） 288
第16章 系统服务程序（System Service Routines） 289
16-1 中断简介（Interrupt Introduction） 290
16-1-1 中断描述表（Interrupt Descriptor Table） 291
16-1-2 异常处理（Exception Handling） 291
16-1-3 中断处理（Interrupt Handling） 292
16-2 软件中断（Software Interrupts） 294
16-2-1 底半部（Bottom Half） 294
16-2-2 Softirq 295
16-2-3 Tasklet 296
16-3 系统调用（System Calls） 299
16-3-1 执行系统调用（Invoking System Calls） 299
16-3-2 参数传递（Parameter Passing） 300
16-3-3 封装程序（Wrapper Routines） 300
16-4-1 字符与块设备（Character and Block Device） 302
16-4 设备驱动程序（Device Driver） 302
16-4-3 编写设备驱动程序（Write a Device Driver） 303
16-4-2 内核程序环境（Kernel Programming Environment） 303
16-5 小结 307
16-6 作业（Homework） 308
第17章 分布式系统简介（Introduction to Distributed Systems） 309
17-1 简介（Introduction） 310
17-1-1 系统优点（Advantages） 310
17-1-2 系统缺点（Disadvantages） 311
17-2 系统结构（Architecture） 311
17-2-1 网络式操作系统（Network Operating System） 311
17-2-2 分布式操作系统（Distributed Operating System） 312
17-3 系统通信（Communication） 313
17-3-1 寻址（Addressing） 314
17-3-3 缓冲（Buffering） 315
17-3-2 阻塞（Blocking） 315
17-3-4 可靠性（Reliability） 316
17-3-5 包发送（Packet Delivery） 317
17-4 远程服务（Remote Service） 319
17-4-1 远程过程调用模型（RPC Model） 319
17-4-2 动态绑定（Dynamic Binding） 321
17-5 设计考虑（Design Issues） 322
17-5-1 透明性（Transparency） 322
17-5-2 可伸缩性（Flexibility） 323
17-5-3 可靠性（Reliability） 324
17-5-4 性能（Performance） 324
17-5-5 可扩展性（Scalability） 325
17-6 小结 325
17-7 作业（Homework） 326
第18章 分布式文件系统（Distributed File Systems） 327
18-1 系统设计（System Design） 328
18-1-1 文件服务接口（File Service Interface） 328
18-1-2 目录服务接口（Directory Service Interface） 329
18-1-3 命名透明性（Naming Transparency） 331
18-1-4 文件共享（File Sharing） 332
18-2 系统实现（Implementation） 334
18-2-1 文件与目录结构（File and Directory Organization） 334
18-2-2 服务类型（Service Types） 335
18-3 高速缓存（Cache） 337
18-3-1 高速缓存机制（Caching Scheme） 337
18-3-2 高速缓存一致性（Cache Consistency） 338
18-4 文件拷贝（File Replication） 339
18-4-1 基本概念（Basic Concepts） 340
18-4-2 拷贝方法（Replication Methods） 340
18-5 小结 341
18-6 作业（Homework） 342
第19章 分布式协调（Distributed Coordination） 343
19-1 事件顺序（Event Ordering） 344
19-1-1 先发生于（Happened—Before） 344
19-1-2 全局排序（Global Ordering） 344
19-2 互斥（Mutual Exclusion） 345
19-2-1 集中式算法（Centralized Algorithm） 346
19-2-2 分布式算法（Distributed Algorithm） 346
19-2-3 令牌环算法（Token Ring Algorithm） 348
19-3 推选算法（Election Algorithms） 348
19-3-1 强势算法（The Bully Algorithm） 349
19-3-2 环状算法（Ring Algorithm） 349
19-4 原子事务（Atomic Transactions） 350
19-4-2 两段式交付协议的错误处理（Failure Handling in 2PC） 351
19-4-1 两段式交付协议（Two-Phase Commit Protocol） 351
19-5 并发控制（Concurrency Control） 353
19-5-1 上锁（Locking） 353
19-5-2 乐观并发控制（Optimistic Concurrency Control） 353
19-5-3 时间戳（Timestamps） 354
19-6 死锁处理（Deadlocks） 355
19-6-1 死锁预防（Deadlock Prevention） 355
19-6-2 死锁检测（Deadlock Detection） 357
19-7 小结 359
19-8 作业（Homework） 360
第20章 分布式系统实例（Distributed System Examples） 361
20-1 Java RMI 362
20-1-1 RMI结构（RMI Architecture） 362
20-1-2 RMI服务端程序设计（RMI Server Programming） 363
20-1-3 RMI客户端程序设计（RMI Client Program） 365
20-2 CORBA 366
20-2-1 CORBA结构（CORBA Architecture） 366
20-2-2 ORB简介（ORB Introduction） 368
20-2-3 对象服务（Object Service） 369
20-3 网络文件系统（Network File System） 371
20-3-1 NFS简介（NFS Introduction） 371
20-3-2 NFS实现（NFS Implementation） 373
20-3-3 NFS协议（NFS Protocol） 374
20-4 小结 375
20-5 作业（Homework） 376
附录A Linux汇编语言简介 377
A-1 汇编语言的语法 378
A-2 Inline Assembly 378
A-3 相关参考数据 380