Предисловие ............................................................................................................... 15
Предисловие от издательства.......................................................................... 18
ЧАСТЬ I. ВВЕДЕНИЕ ........................................................................................... 19
Глава 1. Введение в системы реального времени............................... 21
1.1. Введение ....................................................................................................................... 21
1.2. Что такое система реального времени ....................................................................... 22
1.3. Базовая архитектура .................................................................................................... 23
1.4. Характеристики систем реального времени.............................................................. 25
1.5. Классификация систем реального времени............................................................... 25
1.6. Пример системы: конвейер бутылок.......................................................................... 27
1.7. Обзор книги .................................................................................................................. 29
1.8. Контрольные вопросы ................................................................................................. 29
1.9. Примечания к главе ..................................................................................................... 30
Справочные материалы ..................................................................................................... 30
Глава 2. Аппаратура................................................................................................. 31
2.1. Введение ....................................................................................................................... 31
2.2. Архитектура процессора.............................................................................................. 32
2.2.1. Шина данных с одним циклом ............................................................................ 33
2.2.2. Канал передачи данных многими циклами ....................................................... 38
2.2.3. Конвейер ............................................................................................................... 40
2.2.3.1. Риски ...................................................................................................43
2.2.4. Микроконтроллеры .............................................................................................. 46
2.3. Память........................................................................................................................... 46
2.3.1. Интерфейс процессора......................................................................................... 47
2.3.2. Кеш......................................................................................................................... 48
2.4. Доступ к вводу/выводу................................................................................................. 50
2.4.1. Интерфейс устройства ввода ............................................................................... 51
2.4.2. Интерфейс устройства вывода ............................................................................ 52
2.4.3. Отображение в память и изолированный ввод/вывод ...................................... 53
2.4.4. Программный интерфейс ввода/вывода ............................................................ 54
2.4.4.1. Опрос...................................................................................................54
2.4.4.2. Ввод/вывод с прерыванием...............................................................55
2.4.4.3. Прямой доступ к памяти....................................................................56
2.4.4.4. Исключения ........................................................................................57
2.4.4.5. Таймеры ..............................................................................................57
2.5. Многоядерные процессоры......................................................................................... 58
2.6. Мультипроцессоры ...................................................................................................... 59
2.7. Контрольные вопросы.................................................................................................. 60
2.8. Примечания к главе ..................................................................................................... 61
2.9. Упражнения .................................................................................................................. 62
Справочные материалы ..................................................................................................... 62
Глава 3. Распределенные системы реального времени .................. 63
3.1. Введение ....................................................................................................................... 63
3.2. Модели.......................................................................................................................... 64
3.2.1. Распределение по времени и событию............................................................... 64
3.2.2. Конечные автоматы.............................................................................................. 65
3.3. Распределенные операционные системы реального времени
и промежуточное программное обеспечение.................................................................. 68
3.3.1. Промежуточное программное обеспечение....................................................... 69
3.3.2. Распределенное планирование ........................................................................... 69
3.3.3. Динамическая балансировка нагрузки............................................................... 71
3.4. Связь в реальном времени .......................................................................................... 72
3.4.1. Трафик в реальном времени................................................................................ 72
3.4.2. Модель взаимосвязи открытых систем............................................................... 73
3.4.3. Топология.............................................................................................................. 74
3.4.4. Уровень канала передачи данных ....................................................................... 76
3.4.4.1. Протоколы доступа к среде................................................................77
3.4.5. Протокол контроллерной сети............................................................................. 77
3.4.6. Протокол запуска по времени ............................................................................. 79
3.4.7. Сеть реального времени Ethernet........................................................................ 80
3.4.8. Стандарт реального времени IEEE 802.11........................................................... 80
3.5. Проблемы в распределенных системах реального времени
с встроенными элементами............................................................................................... 81
3.6. Примеры распределенных систем реального времени ............................................ 82
3.6.1. Современный автомобиль ................................................................................... 82
3.6.2. Беспроводная мобильная сенсорная сеть........................................................... 83
3.7. Контрольные вопросы.................................................................................................. 84
3.8. Примечания к главе ..................................................................................................... 85
3.9. Упражнения .................................................................................................................. 86
Справочные материалы ..................................................................................................... 87
Часть II. СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ .......... 89
Глава 4. Операционные системы реального времени...................... 91
4.1. Введение ....................................................................................................................... 91
4.2. Общие операционные системы и операционные системы реального времени..... 92
4.3. Управление задачей..................................................................................................... 93
4.3.1. Задача управления в UNIX................................................................................... 95
4.3.2. Синхронизация задач........................................................................................... 97
4.3.3. Межзадачные коммуникации.............................................................................. 98
4.3.4. Межпроцессорное взаимодействие в UNIX.......................................................101
4.4. Потоки..........................................................................................................................102
4.4.1. Управление потоками .........................................................................................102
4.4.2. Потоки POSIX.......................................................................................................103
4.4.2.1. Взаимное исключение .....................................................................104
4.4.2.2. Синхронизация.................................................................................105
4.4.2.3. Связь..................................................................................................106
4.5. Управление памятью ..................................................................................................108
4.5.1. Статичное распределение памяти .....................................................................108
4.5.2. Динамическое распределение памяти ..............................................................108
4.5.3. Виртуальная память ............................................................................................108
4.5.4. Управление памятью в реальном времени........................................................109
4.6. Управление вводом/выводом.....................................................................................110
4.6.1. Управляемый прерываниями ввод/вывод.........................................................110
4.6.2. Драйверы устройств ............................................................................................111
4.7. Обзор операционных систем реального времени ....................................................112
4.7.1. Операционная система с открытым кодом RTOS..............................................113
4.7.2. Операционная система VxWorks.........................................................................113
4.7.3. Сиcтема реального времени Linux .....................................................................113
4.8. Контрольные вопросы ................................................................................................114
4.9. Примечания к главе ....................................................................................................115
4.10. Упражнения по программированию .......................................................................115
Справочные материалы ....................................................................................................116
Глава 5. Проектирование экспериментального
распределенного ядра реального времени...........................................117
5.1. Введение ......................................................................................................................117
5.2. Стратегия дизайна ......................................................................................................118
5.3. Функции ядра нижнего уровня..................................................................................119
5.3.1. Структуры данных и операции с очередями.....................................................119
5.3.1.1. Тип блока данных.............................................................................120
5.3.1.2. Тип данных блока управления задачами .......................................121
5.3.2. Планировщик с несколькими очередями..........................................................123
5.3.3. Обработка прерываний и управление временем..............................................126
5.3.3.1. Дельта-очередь .................................................................................127
5.3.4. Управление состоянием задачи..........................................................................128
5.3.4.1. Программа обработки прерываний по времени............................129
5.3.5. Управление вводом/выводом .............................................................................130
5.4. Функции ядра верхнего уровня .................................................................................132
5.4.1. Синхронизация задач..........................................................................................132
5.4.2. Коммуникация задач...........................................................................................136
5.4.3. Управление верхней памятью с использованием пулов ..................................139
5.4.4. Управление задачей.............................................................................................140
5.5. Инициализация...........................................................................................................142
5.6. Тестирование DRTK.....................................................................................................144
5.7. Контрольные вопросы.................................................................................................145
5.8. Примечания к главе ....................................................................................................145
5.9. Проекты программирования .....................................................................................146
Справочные материалы ....................................................................................................147
Глава 6. Операционные системы реального времени
и промежуточное программное обеспечение......................................148
6.1. Введение ......................................................................................................................148
6.2. Распределенные операционные системы реального времени ...............................149
6.2.1. Интерфейс транспортного уровня .....................................................................150
6.2.2. Интерфейс уровня канала передачи данных.....................................................151
6.3. Промежуточное программное обеспечение реального времени............................153
6.3.1. Группы задач в реальном времени ....................................................................154
6.3.2. Синхронизация часов..........................................................................................155
6.3.2.1. Логические часы...............................................................................156
6.3.2.2. Векторные часы................................................................................157
6.3.2.3. Сетевой протокол времени..............................................................158
6.3.2.4. Алгоритм Беркли..............................................................................160
6.3.2.5. Синхронизация часов в беспроводных сенсорных сетях ..............160
6.3.3. Алгоритмы выбора ..............................................................................................162
6.3.3.1. Выбор в однонаправленном кольце................................................162
6.3.3.2. Выборы в беспроводных сенсорных и мобильных
специальных сетях........................................................................................163
6.4. Реализация DRTK ........................................................................................................165
6.4.1. Инициализация сети ...........................................................................................165
6.4.2. Интерфейс транспортного уровня .....................................................................167
6.4.3. Задачи интерфейса канального уровня передачи данных...............................171
6.4.4. Групповое управление ........................................................................................173
6.4.5. Алгоритм синхронизации часов.........................................................................175
6.4.6. Выбор лидера в кольце........................................................................................176
6.5. Контрольные вопросы ................................................................................................178
6.6. Примечания к главе ....................................................................................................178
6.7. Проекты программирования......................................................................................179
Справочные материалы ....................................................................................................179
ЧАСТЬ III. ПЛАНИРОВАНИЕ И РАСПРЕДЕЛЕНИЕ
РЕСУРСОВ..................................................................................................................181
Глава 7. Задача планирования однопроцессорной
независимой задачи..............................................................................................183
7.1. Введение ......................................................................................................................183
7.2. Предпосылки ...............................................................................................................184
7.2.1. Тест планируемости.............................................................................................185
7.2.2. Применение..........................................................................................................186
7.3. Политики планирования ............................................................................................186
7.3.1. Приоритетное или неприоритетное планирование .........................................186
7.3.2. Статичное или динамичное планирование .......................................................188
7.3.3. Независимые или зависимые задачи ................................................................189
7.4. Таксономия алгоритмов планирования в реальном времени.................................190
7.5. Потактовое планирование..........................................................................................191
7.5.1. Планирование на основе таблиц ........................................................................191
7.5.2. Циклическое выполнение ...................................................................................193
7.6. Приоритетное планирование.....................................................................................195
7.6.1. Монотонное планирование.................................................................................195
7.6.2. Планирование с первым самым крайним сроком ............................................197
7.6.2.1. Апериодический алгоритм EDF.......................................................198
7.6.2.2. Периодический алгоритм EDF.........................................................199
7.6.3. Алгоритм наименьшего времени незанятости .................................................201
7.6.4. Анализ времени отклика.....................................................................................202
7.7. Апериодическое планирование задач .......................................................................203
7.7.1. Основные методы.................................................................................................204
7.7.2. Периодические серверы ......................................................................................206
7.7.2.1. Сервер опроса....................................................................................206
7.7.2.2. Отложенный сервер ..........................................................................207
7.7.2.3. Спорадический сервер......................................................................207
7.7.2.4. Серверы с динамическим приоритетом .........................................207
7.8. Планирование спорадических задач .........................................................................208
7.9. Реализация в DTRK......................................................................................................210
7.9.1. Планировщик монотонного рейтинга ...............................................................210
7.9.2. Планировщик самого раннего первого срока ...................................................212
7.9.3. Планировщик первой наименее занятой задачи..............................................212
7.9.4. Сервер опроса.......................................................................................................214
7.10. Контрольные вопросы...............................................................................................214
7.11. Примечания к главе...................................................................................................215
7.12. Упражнения ...............................................................................................................217
Справочные материалы ....................................................................................................218
Глава 8. Планирование однопроцессорной
зависимой задачи...................................................................................................219
8.1. Введение ......................................................................................................................219
8.2. Планирование зависимых задач................................................................................220
8.2.1. Aлгоритм первым последний конечный срок...................................................220
8.2.2. Модифицированный алгоритм первым ранний конечный срок.....................221
8.3. Планирование задач при совместном использовании ресурсов.............................223
8.3.1. Случай марсианского зонда................................................................................226
8.3.2. Основной протокол наследования приоритетов ..............................................227
8.3.3. Протокол приоритетного потолка......................................................................231
8.4. Реализация DRTK ........................................................................................................233
8.4.1. Зависимое планирование задач LDF..................................................................234
8.4.2. Протокол приоритетного наследования............................................................235
8.5. Контрольные вопросы ................................................................................................237
8.6. Примечания к главе ....................................................................................................237
8.7. Упражнения .................................................................................................................238
Справочные материалы ....................................................................................................239
Глава 9. Планирование многопроцессорных
распределенных задач реального времени..........................................240
9.1. Введение ......................................................................................................................240
9.2. Многопроцессорное планирование...........................................................................241
9.2.1. Раздельное планирование ..................................................................................242
9.2.1.1. Распределение задач........................................................................242
9.2.1.2. Алгоритм балансировки использования с EDF ..............................243
9.2.1.3. Алгоритмы ........................................................................................244
9.2.1.4. Алгоритм EDF с упаковкой первое соответствие...........................246
9.2.1.5. Монотонный алгоритм первое соответствие (RM-FF)...................246
9.2.2. Глобальное планирование ..................................................................................247
9.2.2.1. Глобальный монотонный алгоритм................................................248
9.2.2.2. Аномалии..........................................................................................249
9.2.2.3. Пропорциональный алгоритм справедливого планирования......249
9.3. Распределенное планирование..................................................................................249
9.3.1. Балансировка нагрузки .......................................................................................250
9.3.1.1. Центральная балансировка нагрузки .............................................250
9.3.1.2. Распределенная балансировка нагрузки........................................251
9.3.2. Метод целенаправленной адресации и назначения ставок.............................252
9.3.3. Алгоритм Buddy ...................................................................................................253
9.3.4. Планирование сообщений ..................................................................................254
9.4. Реализация DRTK ........................................................................................................255
9.4.1. Центральные задачи балансировки нагрузки...................................................255
9.4.2. Задача балансировки распределенной нагрузки ..............................................257
9.5. Контрольные вопросы ................................................................................................259
9.6. Примечания к главе ....................................................................................................259
9.7. Упражнения .................................................................................................................260
Справочные материалы ....................................................................................................260
ЧАСТЬ IV. ПРИКЛАДНОЕ ПРОЕКТИРОВАНИЕ............................263
Глава 10. Разработка программного обеспечения
систем реального времени ...............................................................................265
10.1. Введение ....................................................................................................................265
10.2. Жизненный цикл разработки программного обеспечения...................................266
10.2.1. Пошаговая модель Waterfall..............................................................................267
10.2.2. V-модель.............................................................................................................268
10.2.3. Спиральная модель Spiral Model.......................................................................268
10.3. Разработка программного обеспечения систем реального времени....................269
10.4. Анализ требований и спецификация ......................................................................270
10.5. Временной анализ.....................................................................................................271
10.6. Структурное проектирование с диаграммами потоков данных ...........................272
10.7. Объектно-ориентированное проектирование ........................................................274
10.8. Методы реализации в реальном времени...............................................................275
10.8.1. Еще о конечных автоматах ...............................................................................275
10.8.1.1. Параллельные иерархические конечные автоматы ....................277
10.8.2. ВременнЫе автоматы........................................................................................278
10.8.3. Сети Петри .........................................................................................................279
10.8.3.1. ВременнЫе сети Петри ..................................................................282
10.9. Унифицированный язык моделирования в реальном времени............................283
10.9.1. UML-диаграммы ................................................................................................283
10.9.2. Функции реального времени............................................................................285
10.10. Метод практического проектирования и реализации .........................................286
10.11. Контрольные вопросы ............................................................................................287
10.12. Примечания к главе ................................................................................................288
10.13. Программирование проектов ................................................................................289
Справочные материалы ....................................................................................................290
Глава 11. Языки программирования в реальном времени .........291
11.1. Введение ....................................................................................................................291
11.2. Требования ................................................................................................................292
11.3. Приложение в реальном времени............................................................................293
11.4. Операционная система C/POSIX в реальном времени...........................................293
11.4.1. Инкапсуляция данных и управление модулями .............................................294
11.4.2. Управление потоком POSIX ..............................................................................295
11.4.2.1. Управление временем....................................................................296
11.4.2.2. Синхронизация потоков и связь ...................................................297
11.4.2.3. Сигналы...........................................................................................297
11.4.2.4. Взаимное исключение....................................................................298
11.4.2.5. Условная синхронизация ...............................................................299
11.4.2.6. Семафоры........................................................................................299
11.4.3. Обработка исключений и низкоуровневое программирование ....................300
11.4.4. Реализация управления процессом C/POSIX в реальном времени................300
11.5. Ада..............................................................................................................................302
11.5.1. Параллелизм ......................................................................................................303
11.5.1.1. Управление временем....................................................................304
11.5.1.2. Periodic Tasks...................................................................................304
11.5.1.3. Приоритеты задач ..........................................................................305
11.5.1.4. Синхронизация задач и связь........................................................305
11.5.2. Обработка исключений.....................................................................................306
11.5.3. Реализация управления процессами на языке ADA........................................308
11.6. Язык программирования Java ..................................................................................309
11.6.1. Потоки Java.........................................................................................................310
11.6.2. Синхронизация потоков ...................................................................................311
11.6.2.1. Управление временем и расписание ............................................311
11.6.3. Обработка исключений.....................................................................................312
11.7. Контрольные вопросы...............................................................................................312
11.8. Примечания к главе ..................................................................................................313
11.9. Упражнения по программированию .......................................................................314
Справочные материалы ....................................................................................................314
Глава 12. Отказоустойчивость.........................................................................315
12.1. Введение ....................................................................................................................315
12.2. Понятия и терминология..........................................................................................316
12.3. Классификация неисправностей .............................................................................317
12.4. Резервирование.........................................................................................................318
12.4.1. Аппаратное резервирование ............................................................................318
12.4.2. Избыточность информации..............................................................................320
12.4.2.1. Кодирование ...................................................................................320
12.4.3. Резервирование времени..................................................................................322
12.4.4. Резервирование программного обеспечения..................................................323
12.4.4.1. Методы с одной версией................................................................323
12.4.4.2. Многократное резервирование.....................................................324
12.5. Отказоустойчивые системы реального времени....................................................325
12.5.1. Статичное планирование..................................................................................326
12.5.2. Динамическое планирование...........................................................................326
12.6. Отказоустойчивость в распределенных системах реального времени.................327
12.6.1. Классификация отказов ....................................................................................327
12.6.2. Пересмотр состава целевых групп ...................................................................328
12.6.2.1. Надежная многоадресная связь ....................................................328
12.7. Реализация DRTK.......................................................................................................331
12.8. Контрольные вопросы ..............................................................................................334
12.9. Примечания к главе ..................................................................................................335
12.10. Упражнения .............................................................................................................335
Справочные материалы ....................................................................................................336
Глава 13. Тематический пример: мониторинг окружающей
среды по беспроводной сенсорной сети .................................................338
13.1. Введение ....................................................................................................................338
13.2. Вопросы проектирования.........................................................................................339
13.3. Требования к спецификации ...................................................................................339
13.4. Временно́й анализ и функциональные характеристики .......................................340
13.5. Связующее дерево и кластеризация........................................................................341
13.6. Вопросы проектирования.........................................................................................345
13.7. Листовой узел ............................................................................................................346
13.7.1. Дизайн высокого уровня ...................................................................................347
13.7.2. Детальная разработка и реализация ................................................................349
13.8. Промежуточный узел................................................................................................355
13.8.1. Дизайн верхнего уровня....................................................................................355
13.8.2. Детальное проектирование и реализация.......................................................356
13.9. Узел управления кластером......................................................................................360
13.9.1. Дизайн высокого уровня...................................................................................361
13.9.1. Дизайн верхнего уровня....................................................................................361
13.10. Приемник.................................................................................................................364
13.10.1. Дизайн высокого уровня .................................................................................364
13.11. Тестирование...........................................................................................................365
13.12. Альтернативная реализация с потоками POSIX ...................................................367
13.13. Примечания к главе ................................................................................................367
13.14. Упражнения по программированию .....................................................................368
Справочные материалы ....................................................................................................368
Приложение А. Соглашение о псевдокоде..............................................369
Приложение В. Функции нижнего ядра....................................................374
Предметный указатель........................................................................................378