实时系统 翻译版PDF电子书下载

第一章 典型实时应用 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