分布式实时系统：理论与实践

　　这本经过课堂检验的教材讲述分布式实时系统软件的设计和实现，使用了自底向上的方法。本书讨论了涉及实时系统的软件项目中面临的常见挑战，并提出了一种简单而有效地执行所有软件工程步骤的新方法。每一章都以对核心概念的讨论开始，并回顾了相关的方法和可用的软件。接下来是对示例内核中概念实现的描述，以及可执行代码。

　　K.埃尔吉耶斯（K.Erciyes），博士，土耳其于斯屈达尔大学计算机工程系的全职教授，著有Guide to Graph Algorithms、Distributed and Sequential Algorithms for Bioinformatics 和Distributed Graph Algorithms for Computer Networks。蔡国扬，20世纪80年代毕业于清华大学计算机系统程序设计专业，现任中山大学计算机学院高级讲师，一直从事计算机系统和网络安全架构的研究与工程实践工作，在自主可信操作系统平台和可信网络的设计与实现以及工业控制系统信息安全架构等领域做出了一定贡献。

译者序
前言
部分　入门知识
第1章　实时系统入门2
1.1　引言2
1.2　什么是实时系统2
1.3　基本体系结构3
1.4　实时系统的特点3
1.5　实时系统的分类4
1.6　示例系统：牛奶灌装厂5
1.7　本书大纲6
1.8　复习题6
1.9　本章提要6
参考文献7
第2章　硬件8
2.1　引言8
2.2　处理器体系结构8
2.2.1　单周期数据通路9
2.2.2　多周期数据通路13
2.2.3　流水线13
2.2.4　微控制器18
2.3　存储器19
2.3.1　与处理器的接口19
2.3.2　缓存19
2.4　输入/输出访问21
2.4.1　输入设备接口22
2.4.2　输出设备接口22
2.4.3　内存映射I/O和隔离I/O23
2.4.4　软件与I/O的接口23
2.5　多核处理器26
2.6　多处理器27
2.7　复习题27
2.8　本章提要28
2.9　练习题28
参考文献29
第3章　分布式实时系统30
3.1　引言30
3.2　模型30
3.2.1　时间触发和事件触发分布式系统30
3.2.2　有限状态机31
3.3　分布式实时操作系统和中间件33
3.3.1　中间件33
3.3.2　分布式调度34
3.3.3　动态负载均衡35
3.4　实时通信35
3.4.1　实时流量35
3.4.2　开放系统互连模型36
3.4.3　拓扑结构37
3.4.4　实时数据链路层38
3.4.5　控制器局域网协议38
3.4.6　时间触发协议39
3.4.7　实时以太网40
3.4.8　实时IEEE 802.1140
3.5　分布式实时嵌入式系统面临的挑战41
3.6　分布式实时系统示例41
3.6.1　现代化轿车41
3.6.2　移动无线传感器网络42
3.7　复习题43
3.8　本章提要43
3.9　练习题43
参考文献44
第二部分　系统软件
第4章　实时操作系统46
4.1　引言46
4.2　普通操作系统与实时操作系统46
4.3　任务管理47
4.3.1　UNIX中的任务管理48
4.3.2　任务间同步49
4.3.3　任务间通信51
4.3.4　UNIX进程间通信53
4.4　线程53
4.4.1　线程管理53
4.4.2　POSIX 线程54
4.5　内存管理57
4.5.1　静态内存分配57
4.5.2　动态内存分配57
4.5.3　虚拟内存57
4.5.4　实时内存管理58
4.6　输入/输出管理59
4.6.1　中断驱动I/O59
4.6.2　设备驱动程序59
4.7　实时操作系统综述60
4.7.1　FreeRTOS60
4.7.2　VxWorks60
4.7.3　实时Linux60
4.8　复习题61
4.9　本章提要61
4.10　编程练习题61
参考文献62
第5章　实验性的分布式实时系统内核的设计63
5.1　引言63
5.2　设计策略63
5.3　低层内核功能64
5.3.1　数据结构和队列操作64
5.3.2　多队列调度程序67
5.3.3　中断处理和时间管理69
5.3.4　任务状态管理70
5.3.5　输入/输出管理72
5.4　高层内核功能74
5.4.1　任务同步74
5.4.2　任务通信76
5.4.3　使用缓冲池的高级内存管理79
5.4.4　任务管理80
5.5　初始化81
5.6　测试DRTK83
5.7　复习题84
5.8　本章提要84
5.9　编程练习题85
参考文献85
第6章　分布式实时操作系统和中间件86
6.1　引言86
6.2　分布式实时操作系统86
6.2.1　传输层接口87
6.2.2　数据链路层接口87
6.3　实时中间件88
6.3.1　实时任务组89
6.3.2　时钟同步90
6.3.3　选举算法94
6.4　DRTK的实现96
6.4.1　初始化网络96
6.4.2　传输层接口97
6.4.3　数据链路层接口任务100
6.4.4　组管理102
6.4.5　时钟同步算法103
6.4.6　环形结构的领导者选举104
6.5　复习题105
6.6　本章提要105
6.7　编程练习题106
参考文献106
第三部分　调度和资源共享
第7章　单处理器独立任务调度108
7.1　引言108
7.2　背景知识108
7.2.1　可调度性测试109
7.2.2　利用率109
7.3　调度策略109
7.3.1　抢占式调度与非抢占式调度110
7.3.2　静态调度与动态调度111
7.3.3　独立任务与非独立任务111
7.4　实时调度算法分类112
7.5　时钟驱动调度113
7.5.1　表驱动调度113
7.5.2　循环执行调度114
7.6　基于优先级的调度116
7.6.1　单调速率调度116
7.6.2　早截止期限优先调度118
7.6.3　松弛度优先调度120
7.6.4　响应时间分析120
7.7　非周期性任务调度122
7.7.1　基本方法122
7.7.2　周期性服务器123
7.8　偶发任务调度125
7.9　DRTK的实现125
7.9.1　单调速率调度程序126
7.9.2　早截止期限优先调度程序127
7.9.3　松弛度优先调度程序128
7.9.4　轮询服务器129
7.10　复习题129
7.11　本章提要130
7.12　练习题131
参考文献131
第8章　单处理器非独立任务调度132
8.1　引言132
8.2　非独立任务调度132
8.2.1　迟截止期限优先算法132
8.2.2　改进的早截止期限优先算法134
8.3　共享资源任务的调度135
8.3.1　火星探路者案例136
8.3.2　基本优先级继承协议137
8.3.3　优先级置顶协议140
8.4　DRTK的实现141
8.4.1　LDF非独立任务调度141
8.4.2　优先级继承协议142
8.5　复习题144
8.6　本章提要144
8.7　练习题145
参考文献146
第9章　多处理器与分布式实时调度147
9.1　引言147
9.2　多处理器调度147
9.2.1　分区调度148
9.2.2　全局调度152
9.3　分布式调度154
9.3.1　负载均衡154
9.3.2　聚焦寻址与投标方案156
9.3.3　伙伴算法157
9.3.4　消息调度157
9.4　DRTK的实现158
9.4.1　中心负载均衡任务158
9.4.2　分布式负载均衡任务160
9.5　复习题161
9.6　本章提要162
9.7　练习题162
参考文献162
第四部分　应用程序设计
第10章　实时系统的软件工程166
10.1　引言166
10.2　软件开发生命周期166
10.2.1　增量瀑布模型167
10.2.2　V模型167
10.2.3　螺旋模型167
10.3　实时系统的软件设计168
10.4　需求分析与规格说明168
10.5　时序分析169
10.6　带数据流图的结构化设计169
10.7　面向对象设计170
10.8　实时的实现方法171
10.8.1　再次讨论有限状态机171
10.8.2　时间自动机173
10.8.3　Petri网173
10.9　实时UML176
10.9.1　UML图解176
10.9.2　实时特性177
10.10　实用的设计和实现方法178
10.11　复习题178
10.12　本章提要179
10.13　编程练习题179
参考文献180
第11章　实时编程语言181
11.1　引言181
11.2　需求181
11.3　一个实时应用程序182
11.4　C/Real-time POSIX182
11.4.1　数据封装和模块管理182
11.4.2　POSIX线程管理184
11.4.3　异常处理和底层编程187
11.4.4　C/Real-time POSIX过程控制的实现187
11.5　Ada189
11.5.1　并发190
11.5.2　异常处理192
11.5.3　Ada过程控制的实现193
11.6　Java194
11.6.1　Java线程194
11.6.2　线程同步195
11.6.3　异常处理196
11.7　复习题196
11.8　本章提要197
11.9　编程练习题197
参考文献197
第12章　容错198
12.1　引言198
12.2　概念和术语198
12.3　故障分类199
12.4　冗余199
12.4.1　硬件冗余200
12.4.2　信息冗余200
12.4.3　时间冗余202
12.4.4　软件冗余202
12.5　容错实时系统204
12.5.1　静态调度204
12.5.2　动态调度204
12.6　分布式实时系统中的容错205
12.6.1　失效分类205
12.6.2　再次讨论任务组206
12.7　DRTK的实现208
12.8　复习题210
12.9　本章提要211
12.10　练习题211
参考文献212
第13章　案例研究：无线传感器网络实现的环境监控213
13.1　引言213
13.2　基本思想213
13.3　需求规格说明213
13.4　时序分析和功能规格说明214
13.5　生成树和簇214
13.6　设计思路217
13.7　叶子节点218
13.7.1　高层设计218
13.7.2　详细设计和实现219
13.8　中间节点224
13.8.1　高层设计224
13.8.2　详细设计和实现226
13.9　簇头节点228
13.9.1　高层设计228
13.9.2　详细设计和实现229
13.10　汇聚节点230
13.11　测试231
13.12　使用POSIX线程的替代实现233
13.13　本章提要233
13.14　编程练习题233
参考文献233
附录A　使用伪代码的一些约定234
附录B　低层内核函数238