分佈式實時系統：理論與實踐 Distributed Real-Time Systems: Theory and Practice

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