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

本书描述了一种自底向上的分布式实时系统软件的设计与实现方法，内容安排经过了实际教学测试。全书共分为四部分，讨论了涉及实时系统的软件项目中常见的挑战，并给出了一种新的方法来简单有效地执行项目中的所有软件工程步骤。每章都从核心概念入手，配以对相关方法和可用软件的回顾，然后描述这些概念在示例内核中的实现，还给出了可执行代码。
只需具备计算机体系结构和操作系统的基本背景知识，就可以阅读本书。本书可以作为电子与计算机工程专业以及计算机科学专业的高年级本科生和研究生的教材，也可以作为对实时系统感兴趣的研究人员的参考资料。

本书特色
介绍实时系统的基本概念，包括实时系统架构和分布式实时系统。
关注实时操作系统，覆盖了任务、内存和输入/输出管理等概念。
给出构建实时操作系统内核的详细步骤，并使用此内核测试各种高层实现。
描述周期性和非周期性调度、资源管理以及分布式调度。
从高层设计方法到低层设计和实现细节，全面回顾应用程序设计过程。
总结实时编程语言和容错技术。
多数章节带有复习题、大量的C代码和示例，还给出了一个在真实应用程序中实现所述方法的案例研究。

　　《分布式实时系统：理论与实践》描述分布式实时系统软件的设计与实现，全书其分为四部分。首部分介绍实时系统、硬件及分布式实时系统的基本概念。第二部分介绍实时操作系统、分布式实时系统内核的设计、分布式实时操作系统和中间件。第三部分介绍单处理器独立任务和非独立任务的调度以及多处理器和分布式实时调度。第四部分介绍实时系统的软件工程技术、实时编程语言及容错技术，回顾应用程序从高层概要设计到低层详细设计与实现的全过程，给出一个在真实应用中实现所述方法的案例研究。
　　《分布式实时系统：理论与实践》可作为电子与计算机工程专业及计算机科学专业的高年级本科生和研究生的教材，也可作为对实时系统感兴趣的研究人员的参考资料。
　　《分布式实时系统：理论与实践》特色：
　　介绍实时系统的基本概念，包括实时系统架构和分布式实时系统。
　　关注实时操作系统，覆盖了任务、内存和输入/输出管理等概念。
　　给出构建实时操作系统内核的详细步骤，并使用此内核测试各种高层实现。
　　描述周期性和非周期性调度、资源管理以及分布式调度。
　　从高层设计方法到低层设计和实现细节，全面回顾应用程序设计过程。
　　总结实时编程语言和容错技术。
　　多数章节带有复习题、大量的C代码和示例，还给出了一个在真实应用程序中实现所述方法的案例研究。

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

　　★“本书以专题的形式总结了实时系统的现代知识和范式，从基础硬件和低层实时系统特性开始讲解，适用于本科生及以上层次。本书的章节结构和内容安排也颇具特色，将理论背景和实践合理地安排在一个统一的框架内。”
　　——Balint Molnar，Computing Reviews

译者序
前言
第一部分　入门知识
第1章　实时系统入门2
11　引言2
12　什么是实时系统2
13　基本体系结构3
14　实时系统的特点3
15　实时系统的分类4
16　示例系统：牛奶灌装厂5
17　本书大纲6
18　复习题6
19　本章提要6
参考文献7
第2章　硬件8
21　引言8
22　处理器体系结构8
221　单周期数据通路9
222　多周期数据通路13
223　流水线13
224　微控制器18
23　存储器19
231　与处理器的接口19
232　缓存19
24　输入/输出访问21
241　输入设备接口22
242　输出设备接口22
243　内存映射I/O和隔离I/O23
244　软件与I/O的接口23
25　多核处理器26
26　多处理器27
27　复习题27
28　本章提要28
29　练习题28
参考文献29
第3章　分布式实时系统30
31　引言30
32　模型30
321　时间触发和事件触发分布式系统30
322　有限状态机31
33　分布式实时操作系统和中间件33
331　中间件33
332　分布式调度34
333　动态负载均衡35
34　实时通信35
341　实时流量35
342　开放系统互连模型36
343　拓扑结构37
344　实时数据链路层38
345　控制器局域网协议38
346　时间触发协议39
347　实时以太网40
348　实时IEEE 8021140
35　分布式实时嵌入式系统面临的挑战41
36　分布式实时系统示例41
361　现代化轿车41
362　移动无线传感器网络42
37　复习题43
38　本章提要43
39　练习题43
参考文献44
第二部分　系统软件
第4章　实时操作系统46
41　引言46
42　普通操作系统与实时操作系统46
43　任务管理47
431　UNIX中的任务管理48
432　任务间同步49
433　任务间通信51
434　UNIX进程间通信53
44　线程53
441　线程管理53
442　POSIX 线程54
45　内存管理57
451　静态内存分配57
452　动态内存分配57
453　虚拟内存57
454　实时内存管理58
46　输入/输出管理59
461　中断驱动I/O59
462　设备驱动程序59
47　实时操作系统综述60
471　FreeRTOS60
472　VxWorks60
473　实时Linux60
48　复习题61
49　本章提要61
410　编程练习题61
参考文献62
第5章　实验性的分布式实时系统内核的设计63
51　引言63
52　设计策略63
53　低层内核功能64
531　数据结构和队列操作64
532　多队列调度程序67
533　中断处理和时间管理69
534　任务状态管理70
535　输入/输出管理72
54　高层内核功能74
541　任务同步74
542　任务通信76
543　使用缓冲池的高级内存管理79
544　任务管理80
55　初始化81
56　测试DRTK83
57　复习题84
58　本章提要84
59　编程练习题85
参考文献85
第6章　分布式实时操作系统和中间件86
61　引言86
62　分布式实时操作系统86
621　传输层接口87
622　数据链路层接口87
63　实时中间件88
631　实时任务组89
632　时钟同步90
633　选举算法94
64　DRTK的实现96
641　初始化网络96
642　传输层接口97
643　数据链路层接口任务100
644　组管理102
645　时钟同步算法103
646　环形结构的领导者选举104
65　复习题105
66　本章提要105
67　编程练习题106
参考文献106
第三部分　调度和资源共享
第7章　单处理器独立任务调度108
71　引言108
72　背景知识108
721　可调度性测试109
722　利用率109
73　调度策略109
731　抢占式调度与非抢占式调度110
732　静态调度与动态调度111
733　独立任务与非独立任务111
74　实时调度算法分类112
75　时钟驱动调度113
751　表驱动调度113
752　循环执行调度114
76　基于优先级的调度116
761　单调速率调度116
762　最早截止期限优先调度118
763　最低松弛度优先调度120
764　响应时间分析120
77　非周期性任务调度122
771　基本方法122
772　周期性服务器123
78　偶发任务调度125
79　DRTK的实现125
791　单调速率调度程序126
792　最早截止期限优先调度程序127
793　最低松弛度优先调度程序128
794　轮询服务器129
710　复习题129
711　本章提要130
712　练习题131
参考文献131
第8章　单处理器非独立任务调度132
81　引言132
82　非独立任务调度132
821　最迟截止期限优先算法132
822　改进的最早截止期限优先算法134
83　共享资源任务的调度135
831　火星探路者案例136
832　基本优先级继承协议137
833　优先级置顶协议140
84　DRTK的实现141
841　LDF非独立任务调度141
842　优先级继承协议142
85　复习题144
86　本章提要144
87　练习题145
参考文献146
第9章　多处理器与分布式实时调度147
91　引言147
92　多处理器调度147
921　分区调度148
922　全局调度152
93　分布式调度154
931　负载均衡154
932　聚焦寻址与投标方案156
933　伙伴算法157
934　消息调度157
94　DRTK的实现158
941　中心负载均衡任务158
942　分布式负载均衡任务160
95　复习题161
96　本章提要162
97　练习题162
参考文献162
第四部分　应用程序设计
第10章　实时系统的软件工程166
101　引言166
102　软件开发生命周期166
1021　增量瀑布模型167
1022　V模型167
1023　螺旋模型167
103　实时系统的软件设计168
104　需求分析与规格说明168
105　时序分析169
106　带数据流图的结构化设计169
107　面向对象设计170
108　实时的实现方法171
1081　再次讨论有限状态机171
1082　时间自动机173
1083　Petri网173
109　实时UML176
1091　UML图解176
1092　实时特性177
1010　实用的设计和实现方法178
1011　复习题178
1012　本章提要179
1013　编程练习题179
参考文献180
第11章　实时编程语言181
111　引言181
112　需求181
113　一个实时应用程序182
114　C/Real-time POSIX182
1141　数据封装和模块管理182
1142　POSIX线程管理184
1143　异常处理和底层编程187
1144　C/Real-time POSIX过程控制的实现187
115　Ada189
1151　并发190
1152　异常处理192
1153　Ada过程控制的实现193
116　Java194
1161　Java线程194
1162　线程同步195
1163　异常处理196
117　复习题196
118　本章提要197
119　编程练习题197
参考文献197
第12章　容错198
121　引言198
122　概念和术语198
123　故障分类199
124　冗余199
1241　硬件冗余200
1242　信息冗余200
1243　时间冗余202
1244　软件冗余202
125　容错实时系统204
1251　静态调度204
1252　动态调度204
126　分布式实时系统中的容错205
1261　失效分类205
1262　再次讨论任务组206
127　DRTK的实现208
128　复习题210
129　本章提要211
1210　练习题211
参考文献212
第13章　案例研究：无线传感器网络实现的环境监控213
131　引言213
132　基本思想213
133　需求规格说明213
134　时序分析和功能规格说明214
135　生成树和簇214
136　设计思路217
137　叶子节点218
1371　高层设计218
1372　详细设计和实现219
138　中间节点224
1381　高层设计224
1382　详细设计和实现226
139　簇头节点228
1391　高层设计228
1392　详细设计和实现229
1310　汇聚节点230
1311　测试231
1312　使用POSIX线程的替代实现233
1313　本章提要233
1314　编程练习题233
参考文献233
附录A　使用伪代码的一些约定234
附录B　低层内核函数238

从工厂、现代汽车到航空电子设备，分布式和嵌入式实时系统无处不在。分布式实时系统的特点是由许多通过实时网络连接起来的计算节点协同完成实时任务。实时任务有一个截止期限，很多应用要求实时任务必须在其截止期限之前完成。近年来的技术进步使这种分布式实时系统的节点数量大幅增加，从而使相应的系统软件设计面临巨大的挑战。分布式实时系统的节点具有一定的计算能力，它通常通过传感器和作动器与外部世界连接。并非所有的嵌入式系统都是实时的，我们将使用“分布式实时系统”这个术语描述那些具有实时特性的分布式嵌入式系统。
本书讨论设计和实现分布式实时系统软件的自底向上方法。我教授了几十年本科和研究生阶段的相关课程，并且参与了与实时系统相关的一些大型软件项目，因此了解人们在系统设计和实现过程中所遇到的主要瓶颈。首先，设计师或程序员经常面临将应用程序与一些商业化实时操作系统（或者中间件）进行结合的挑战，有时候甚至需要为这些系统编写补丁。这就要求我们深入了解与实时处理相关的硬件和操作系统概念。本书第一部分（第1～3章）介绍了一些入门知识。第二部分（第4～6章）的内容与系统软件相关，其中第4章回顾了实时操作系统的基本概念，第5章详细介绍了从头开始构建实验性的分布式实时操作系统内核的过程，第6章回顾了分布式实时操作系统和中间件的概念，描述了如何设计网络通信部分，以使实时内核能够相互协作，形成分布式实时系统的软件框架。本书的后续部分展示了把实验性内核逐渐转化为带有相应中间件的分布式实时操作系统内核的所有实现细节。
其次，设计师面临的挑战是任务调度，实时系统需要让所有任务都能够在截止期限前完成。实时系统中的任务可以大致分为硬实时任务、软实时任务和严格实时任务。它们可以是周期性的，也可以是非周期性的，分别需要不同的调度策略。不同任务之间既可能相互独立，也可能相互依赖，在相互依赖的情况下需要实现任务间同步。我们还需要提供端到端的任务调度，在满足任务截止期限要求的同时，将负载均匀地分布到分布式实时系统的节点上。另一个相关的问题是网络资源管理。所有这些都将在本书的第三部分（第7～9章）进行讨论并加以实现。
最后，设计师面临的任务是完成从需求说明开始到高层设计、详细设计和编码的所有软件工程步骤，在这个过程中会遇到很多困难。我们提供了一种执行所有步骤的简单而有效的方法。本书第四部分（第10～13章）对此进行了介绍。第10章介绍利用有限状态机进行高层设计和详细设计的方法，其中有限状态机通过操作系统线程实现。第11章介绍一些实时编程语言，包括C/POSIX、Ada和Java。为了预防灾难性事件，容错能力在实时系统中必不可少，第12章专门讨论了这个主题。第13章按照高层设计、详细设计和编码的顺序，结合我们已经开发的方法，实现了一个实时案例。
本书大致这样安排每一章的内容。首先，回顾相关概念，简要介绍一些商业软件，描述设计和实现我们需要的软件的方法。其次，给出应用，其可执行代码展示了如何在实验性示例内核中实现相关概念，该部分叫作“DRTK的实现”。如果课程仅涉及有限的实时系统知识，可以跳过这一部分以及描述DRTK的第5章。最后，会在章末提供一些复习题，总结本章重点，并给出近期参考文献。此外，每一章的“本章提要”部分还指出了一些可能的开放研究领域。
关于DRTK
本书第5章详细介绍的分布式实时内核（Distributed Real-Time Kernel，DRTK）的主要模块在与实时处理相关的各门课程的教学过程中进行了测试。但是，此章之后的各章中，与分布式处理部分相关的程序没有经过充分测试，这意味着它们可能（甚至很可能）有一些语法或者其他实现错误。本书的网站为http://akademikubeegeedutr/~erciyes/DRTS，里面包含DRTK代码、教学幻灯片和勘误表。我希望DRTK成为一个实用的、实验性的分布式实时内核，能够用于相关课程的教学，因此欢迎对DRTK代码进行有益的修改。
本书的目标读者是电子与计算机工程、计算机科学和一般工程专业的高年级本科生、研究生和研究人员，以及任何有计算机体系结构和操作系统基础的人。书中包含了大量用于DRTK实现的样例和各种示例的C代码。感谢在各所大学选修我的实时系统、嵌入式系统、高级操作系统等课程的本科生和研究生，按照时间顺序排列，这些学校包括爱琴海大学、俄勒冈州立大学、加州大学戴维斯分校、加州州立大学圣马科斯分校、伊兹密尔理工学院、伊兹密尔大学和于斯屈达尔大学。针对我在课堂讲述的本书各个部分的内容以及在实验室测试的内核样例，这些学生提供了宝贵的反馈意见。感谢Springer资深编辑Wayne Wheeler和助理编辑Simon Rees在本书的撰写过程中提供的支持。

K Erciyes
土耳其伊斯坦布尔