Распределенные системы реального времени. Теория и практика (6000,00 руб.)

Стр.5

Стр.8

Стр.9

Стр.10

Стр.11

Стр.12

Стр.13

Стр.14

Стр.15

УДК 004.45 ББК 32.973 Э75 Э75 Распределенные системы реального времени. Теория и практика / пер. с анг. В. А. Яроцкий. – М.: ДМК Пресс, 2020. – 382 с.: ил. К. Эрджиес ISBN 978-5-97060-852-4 В книге описываются разработка и реализация программного обеспечения распределенных систем реального времени с использованием подхода «снизу вверх». В начале каждой главы обсуждаются основные концепции, представлен обзор соответствующих методов и доступного ПО. Затем рассматривается реализация концепций в образце ядра, сопровожденная исполняемым кодом. В завершение главы приводится обширный код на языке C, многочисленные примеры, реализующие описанные методы. Издание предназначено студентам, инженерам, разработчикам ПО, имеющим базовый опыт работы в области компьютерной архитектуры и операционных систем УДК 004.45 ББК 32.973 First published in English under the title Distributed Real-Time Systems; Theory and Practice by K Erciyes, edition: 1 Copyright © Springer Nature Switzerland AG, 2019 * This edition has been translated and published under licence from Springer Nature Switzerland AG. Springer Nature Switzerland AG takes no responsibility and shall not be made liable for the accuracy of the transl Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. ISBN (анг.) 978-3-030-22569-8 ISBN (рус.) 978-5-97060-852-4 © Springer Nature Switzerland AG 2019 © Оформление, издание, перевод, ДМК Пресс, 2020

Стр.5

Оглавление Предисловие от автора ........................................................................................ 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

Стр.8

8  Оглавление Глава 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

Стр.9

Оглавление  9 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

Стр.10

10  Оглавление 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

Стр.11

Оглавление  11 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

Стр.12

12  Оглавление 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

Стр.13

Оглавление  13 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

Стр.14

14  Оглавление 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

Стр.15