Распределенные системы реального времени. Теория и практика

Кайхан Эрджиес
Распределенные системы 
реального времени
Теория и практика

Distributed Real-Time 
Systems
Theory and Practice
Kayhan Erciyes

Распределенные системы 
реального времени
Теория и практика
Кайхан Эрджиес
Москва, 2020

УДК 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 
© Springer Nature Switzerland AG 2019
ISBN (рус.) 978-5-97060-852-4 
©  Оформление, издание, перевод, ДМК Пресс, 2020

Посвящается памяти профессора Синана Йылмазу, 
который был прекрасным педагогом и глубоким исследователем 
систем реального времени, а также профессору Невзет Тархану, 
приверженному науке и научному поиску 

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

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

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