第一章 典型实时应用 1
1.1 数字控制 1
目录 1
1.1.1 采样数据系统 2
1.1.2 更复杂的控制规律计算 7
1.2 高层控制 8
1.2.1 控制层次举例 8
1.2.2 制导和控制 10
1.2.3 实时命令与控制 11
1.3.1 处理带宽要求 12
1.3 信号处理 12
1.3.2 雷达系统 13
1.4 其他实时应用 17
1.4.1 实时数据库 17
1.4.2 多媒体应用 18
1.5 小结 21
第二章 强实时系统与弱实时系统 22
2.1 作业与处理器 22
2.2 释放时间、时限和定时约束 22
2.3.1 常用定义 23
2.3 强定时约束与弱定时约束 23
2.3.2 强定时约束与时间服务质量保证 24
2.4 强实时系统 25
2.4.1 要求确保定时的几个理由 25
2.4.2 进一步讨论强定时约束 26
2.5 弱实时系统 27
2.6 小结 27
第三章 实时系统参考模型 29
3.1 处理器和资源 29
3.2 实时系统工作负荷的时间参数 31
3.2.1 固定的、抖动的和偶发的释放时间 32
3.2.2 执行时间 33
3.3 周期性任务模型 34
3.3.1 周期、执行时间和周期任务的阶段 34
3.3.2 非周期的与偶发的任务 36
3.4 优先约束和数据依赖 36
3.4.1 前趋图和任务图 37
3.4.2 数据依赖 38
3.5 其他类型的依赖关系 39
3.5.1 时间依赖关系 39
3.5.2 AND/OR优先约束 39
3.5.3 条件分支 40
3.5.4 流水线关系 41
3.6 功能参数 41
3.6.1 作业的抢占性 41
3.6.2 作业的关键程度 42
3.6.3 可选执行 43
3.6.4 松弛类型和松弛函数 43
3.7 作业的资源参数以及资源的参数 44
3.7.1 资源的抢占性 44
3.8 调度等级 45
3.7.2 资源图 45
3.8.1 调度程序和调度 46
3.8.2 可行性、优化和性能度量 46
3.8.3 调度程序之间的交互 48
3.9 小结 48
3.9.1 应用系统的特征化 49
3.9.2 支撑系统的特征化 50
3.9.3 调度程序 50
习题 51
4.1 时钟驱动调度方法 52
4.2 加权的轮转调度方法 52
第四章 常用的实时调度方法 52
4.3 优先级驱动方法 54
4.4 动态系统与静态系统 56
4.5 有效释放时间与时限 56
4.6 EDF和LST算法的最优性 58
4.7 EDF和LST算法的非最优性 60
4.8 优先级驱动系统中验证定时约束的困难 61
4.8.1 优先级驱动系统的反常行为 62
4.8.2 执行的可预知性 63
4.8.3 验证算法及其性能 65
4.9 脱机调度与联机调度 66
4.10 小结 70
习题 70
第五章 时钟驱动调度 73
5.1 符号表示与假设 73
5.2 静态定时器驱动调度程序 73
5.3 循环调度的通用结构 75
5.3.1 帧与主循环 75
5.3.2 帧长约束 76
5.3.3 作业片 77
5.4 循环执行程序 78
5.5 改善非周期作业的平均响应时间 79
5.5.1 空闲挪用 80
5.5.2 平均响应时间 81
5.6 调度偶发作业 83
5.6.1 接受测试 83
5.6.2 已接受作业的EDF调度 84
5.6.3 接受测试的实现 86
5.6.4 循环EDF算法的最优性 88
5.7 关于实际情况的考虑与一般化 89
5.7.1 处理帧超时运行 89
5.7.2 模式转换 90
5.7.3 通用工作负荷与多处理器调度 92
5.8 构建静态调度的算法 93
5.8.1 调度可抢占的独立任务 93
5.8.2 后处理 96
5.9 时钟驱动调度的优、缺点 96
5.10 小结 97
习题 98
第六章 周期任务的优先级驱动调度 100
6.1 静态假设 100
6.2.1 速率单调（Rate-Monotonic）和时限单调（Deadline-Monotonic）算法 102
6.2 固定优先级算法与动态优先级算法 102
6.2.2 常用的动态算法 104
6.2.3 相关特性 105
6.3 最大可调度利用率 107
6.3.1 EDF算法的可调度利用率 107
6.3.2 EDF算法的可调度性测试 110
6.4 RM和DM算法的最优性 111
6.5 具有又短响应时间的固定优先级任务的可调度性测试 112
6.5.1 临界时刻 113
6.5.2 时间需求分析 115
6.5.3 时间需求分析的替代者 118
6.6 具有任意响应时间的固定优先级任务的可调度性测试 119
6.6.1 繁忙区间 119
6.6.2 通用可调度性测试 120
6.6.3 通用可调度性测试的正确性 122
6.7 RM和DM算法可调度性的充分条件 124
6.7.1 Di=Pi时任务RM算法的可调度利用率 124
6.7.2 定理6.1 1的证明 125
6.7.3 作为任务参数函数的RM算法的可调度利用率 129
6.7.4 具有任意相对时限的固定优先级任务的可调度利用率 132
6.7.5 多帧任务的RM算法的可调度利用率 133
6.8.1 不可抢占性 135
6.8 实际因素 135
6.8.2 自挂起 138
6.8.3 任务切换 139
6.8.4 受限的优先级级别 140
6.8.5 Tick调度 141
6.8.6 固定优先级系统中的优先级变化 144
6.8.7 分层调度的周期任务的可调度性测试 150
6.9 小结 151
6.9.1 可调度性的充分条件 152
6.9.3 实际因素的影响 153
6.9.2 固定优先级系统可调度性的充分必要测试 153
习题 154
第七章 优先级驱动系统中调度非周期作业与偶发作业 161
7.1 假定与方法 161
7.1.1 目标、正确性和最优性 161
7.1.2 可选择的方法 163
7.2 可延期的服务器 166
7.2.1 可延期服务器的操作 166
7.2.2 包含可延期的服务器的固定优先级系统的可调度性 168
7.2.3 具有可延期服务器的时限驱动系统的可调度性 172
7.3 偶发服务器 173
7.3.1 固定优先级系统中的偶发服务器 174
7.3.2 固定优先级偶发服务器的改进 178
7.3.3 时限驱动系统中的简单偶发服务器 184
7.4 常量利用率、总带宽以及加权公平排队服务器 185
7.4.1 时限驱动系统中偶发作业的可调度性 186
7.4.2 常量利用率服务器算法 188
7.4.3 总带宽服务器算法 190
7.4.4 公平性与饥饿 192
7.4.5 可抢占的加权公平排队算法 195
7.5 时限驱动系统中的空闲挪用 200
7.5.1 静态空闲计算 201
7.5.2 实用考虑 206
7.5.3 动态空闲计算 207
7.6 固定优先级系统中的空闲挪用 209
7.6.1 优化准则和设计的考虑 209
7.6.2 固定优先级系统中的静态空闲计算 211
7.6.3 调度非周期性作业 214
7.7 偶发作业的调度 215
7.7.1 时限驱动系统中的简单接受测试 215
7.7.2 时限驱动系统中基于空闲计算的接受测试 218
7.7.4 周期性、偶发和非周期性任务调度的集成 222
7.7.3 固定优先级系统中的简单接受测试 222
7.8 具有弱定时约束作业的实时性能 223
7.8.1 流量模型 223
7.8.2 带宽保留服务器算法的性能 225
7.9 集成调度的两级方案 227
7.9.1 概述和术语 227
7.9.2 可预知应用程序的调度 228
7.9.3 不可预知应用程序的调度 230
7.10.1 非周期性作业的调度算法 231
7.10 小结 231
7.10.2 偶发作业的调度算法 232
7.10.3 具有弱时限的偶发作业的调度 232
7.10.4 周期性任务、偶发任务和非周期性任务的集成调度 233
习题 233
第八章 资源与资源访问控制 240
8.1 与资源及其使用相关的假设 240
8.1.1 互斥与临界区的执行 240
8.1.2 资源冲突与阻塞 241
8.2 资源竞争与资源访问控制的作用 243
8.2.1 优先级逆转、定时异常与时限 243
8.2.2 附加术语、符号与假设 244
8.3 不可抢占的临界区 246
8.4 基本的优先级继承协议 247
8.4.1 基本的优先级继承协议的定义 248
8.4.2 优先级继承协议的特性 250
8.5 基本的优先级最高限度协议 251
8.5.1 基本的优先级最高限度协议的定义 252
8.5.2 优先级继承协议与优先级最高限度协议之间的差异 254
8.5.3 使用优先级最高限度协议避免死锁 254
8.5.4 阻塞的持续时间 256
8.5.5 固定优先级调度与优先级最高限度协议 259
8.6 基于栈的优先级最高限度（最高限度优先级）协议 261
8.6.1 共享栈优先级最高限度协议的动机和定义 261
8.6.2 最高限度优先级协议的定义 263
8.6.3 阻塞时间与关联切换开销 263
8.7 动态优先级系统中优先级最高限度协议的使用 264
8.7.1 动态优先级系统中优先级最高限度协议的实现 264
8.7.2 阻塞持续时间 266
8.7.3 作业级动态优先级系统中基本优先级最高限度协议的适用性 267
8.8 抢占级最高限度协议 267
8.8.1 作业与周期性任务的抢占级别 268
8.8.2 协议定义与阻塞持续时间 269
8.9 对多部件资源的访问控制 272
8.9.1 多部件资源的优先级（抢占级）最高限度 272
8.9.2 改进规则 273
8.9.3 优先级继承规则 273
8.10 数据对象的并发访问控制 275
8.10.1 凸最高限度协议 276
8.10.2 其他实时并发控制方案 279
8.11 小结 280
8.11.1 资源访问控制协议 280
8.11.2 与非周期性作业的资源竞争 282
8.11.3 模式转换 283
习题 284
第九章 多处理器调度、资源访问控制与同步 287
9.1 多处理器和分布式系统的模型 287
9.1.1 同类处理器与异类处理器 288
9.1.2 端到端的作业与任务 288
9.1.3 本地资源与远程资源 291
9.1.4 处理器间的通信 292
9.1.5 用于端到端任务的分布式调度程序的结构 294
9.2 任务分配 294
9.2.1 基于执行时间需求的任务分配 295
9.2.2 最小化总通信开销的任务分配 299
9.2.3 任务与资源分配的集成 303
9.3 多处理器优先级最高限度协议 305
9.3.1 资源竞争引起的阻塞时间 306
9.3.2 阻塞时间6（rc）的构成要素上限 307
9.3.3 一个直观示例 309
9.3.4 可调度性测试 311
9.3.5 不同处理器上资源嵌套请求的影响 311
9.4 端到端周期性任务的调度算法要素 312
9.4.1 处理器间的同步协议 313
9.4.2 各处理器上的子任务调度 319
9.5 固定优先级端到端周期性任务的可调度性 322
9.5.1 不贪心同步任务的可调度性 322
9.5.2 使用贪心同步算法的任务的可调度性 328
9.5.3 端到端方法和MPCP方法的相对性能 331
9.6 异类系统中的端到端任务 333
9.7 动态多处理器系统的可预知性与验证 335
9.8 小结 336
习题 338
第十章 调度柔性计算与有时间距离约束的任务 342
10.1 柔性应用 342
10.1.1 柔性应用的特性 343
10.1.2 调度柔性应用的算法 349
10.2 具有时间距离约束的任务 358
10.2.1 时间距离模型 358
10.2.2 距离约束单调（DCM）算法 359
10.2.3 调度具有任意距离约束的任务 360
10.3 小结 363
10.3.1 柔性计算 363
10.3.2 具有距离约束的任务 364
习题 365
11.1.1 结构概述 366
第十一章 实时通信 366
11.1 实时通信模型 366
11.1.2 信息包、网络带宽以及物理大小 368
11.1.3 实时通信模型 368
11.1.4 性能目标和约束 370
11.1.5 实时连接与服务规程 371
11.2 交换网络的基于优先级的服务规程 374
11.2.1 加权公平排队规程 374
11.2.2 与速率成比例的服务器（RPS）模型和算法 378
11.2.3 基于帧的加权公平排队算法 379
11.2.4 延迟－EDD抖动－EDD服务规程 383
I1.2.5 固定优先级规程 387
11.3 加权轮转服务规程 388
11.3.1 贪心的WRR规程 389
11.3.2 时间驱动的WRR规程 390
11.3.3 有预算的加权轮转算法 392
11.4 广播网络的媒介访问控制协议 395
11.4.1 在CAN以及IEEE802.5 令牌环网中的媒介访问协议 396
11.4.2 定时令牌媒介访问控制协议 399
11.4.3 DQDB网络中的媒介访问控制 404
11.5 网络与资源预定协议 409
11.5.1 资源预定中的问题 410
11.5.2 RSVP（资源预定协议） 412
11.5.3 ST-II、因特网流协议 417
11.6 实时协议 419
11.6.1 数据传输 419
11.6.2 RTCP控制协议 421
11.7 多机系统中的通信 423
11.7.1 虫孔网络 424
11.7.2 优先级驱动的流控制 425
11.8 小结 427
11.8.1 针对交换网络的服务规程 427
11.8.2 广播网的媒介访问协议 429
11.8.3 资源预定和实时传输协议 430
习题 431
第十二章 操作系统 434
12.1 概述 435
12.1.1 线程和任务 435
12.1.2 内核 437
12.2 时间服务和调度机制 442
12.2.1 时间服务 443
12.2.2 调度机制 449
12.3.1 通信和同步 456
12.3 操作系统的其他基本功能 456
12.3.2 事件通知与软中断 460
12.3.3 内存管理 463
12.3.4 I/O和网络 464
12.4 处理器预定及资源内核 466
12.4.1 资源模式及预定类型 466
12.4.2 应用程序接口和SSP结构 468
12.5 开放系统体系结构 469
12.5.1 目标及其他 469
12.5.2 两级调度程序 471
12.5.3 服务器的维护 474
12.5.4 充分可调度性条件与接受测试 476
12.5.5 调度开销与处理器利用率 477
12.5.6 服务提供程序的结构及实时API函数 477
12.6 商用实时操作系统的能力 479
12.6.1 LynxOS 480
12.6.2 pSOSystem 481
12.6.3 QNX/Neutrino 482
12.6.4 VRTX 482
12.6.5 VxWorks 483
12.7.1 WindowsNT操作系统 485
12.7 通用操作系统的可预知性 485
12.7.2 Linux操作系统的实时扩展 489
12.8 小结 493
12.8.1 商用操作系统 493
12.8.2 值得拥有的操作系统原语 494
12.8.3 资源预定与开放环境 494
习题 495
附录 POSIX线程和实时扩展 498
参考文献 503
英汉对照表 515
译后记 542