Deadlock Prevention in OS for Programmable Systems on a Chip
K. S. Gaiduk, O. G. Shevchenko · Science and Education a New Dimension · 2018
Аннотация.В работе представлен подход к предотвращению взаимоблокировок во встраиваемых операционных системах, основанный на объединении событийно-управляемой и сервис-ориентированной архитектур, асинхронного ввода-вывода, а также других приемов, использованных при разработке авторской операционной системы.С целью сокращения накладных расходов процессорного времени, обусловленных потребностью в динамическом распределении памяти, а также сокращения дисперсии времени выделения блоков памяти, операционная система использует ресурс программируемой логики.Ключевые слова: предотвращение взаимоблокировок, автоматное программирование, встраиваемые операционные системы, программируемые системы на кристалле, Predicate OS.Введение.Основная часть работ в направлении исследований проблемы взаимоблокировок (ВБ) была завершена еще до 1980 г., однако для ряда систем данная проблема остается актуальной.К числу таковых можно отнести: системы, характеризующиеся большим количеством элементов и связей (например, современная локальная вычислительная сеть автомобиля содержит порядка 80 микроконтроллеров, а общий объем исходного кода встраиваемого программного обеспечения может достигать 100 MLOC); системы с динамически изменяемым составом, топологией и алгоритмом работы; системы с децентрализованным управлением.Большинство методов уклонения от взаимоблокировок и их предотвращения предполагает существенные накладные расходы процессорного времени и ОЗУ, либо являются непрактичными (алгоритм банкира, порядковая нумерация ресурсов, принудительное отнятие ресурсов и пр.).Применение парадигмы автоматного программирования позволяет достичь предотвращения взаимоблокировок, однако может потребовать динамического распределения памяти, что ограничивает применение указанной парадигмы при разработке встраиваемых операционных систем.Частичная либо полная аппаратная реализация распределителя памяти в значительной мере нивелирует вышеуказанное ограничение.Краткий обзор публикаций по теме.Предотвращение взаимоблокировок посредством атак на условия Коффмана, а также ряд алгоритмов уклонения от ВБ, описаны в [1].В [2, 3] упоминается о языках формального описания программного обеспечения (Funclet+, xGiotto, АФС), а также методе Model Checking, позволяющих достичь предотвращения ВБ путем верификации.Важным инструментом в борьбе с взаимоблокировками являются сети Петри [4, 5], позволяющие выполнять проверку системы на предмет свободы от тупиков формализованными математическими методами, а также добиваться уклонения от ВБ либо их предотвращения за счет организации супервизорного контроля.В [6] представлен распределенный алгоритм уклонения от ВБ в системах автоматизированных транспортных тележек, в соответствии с которым роботы многократно останавливаются на пути своего движения и