Software & Systems

Для обеспечения своевременного выполнения прикладных задач в операционных системах реального времени (ОСРВ) используют алгоритмы вытесняющего планирования, основанного на приоритетах*. Работа с разделяемыми ресурсами в системах такого рода потенциально влечет инверсию приоритетов*. Неконтролируемая инверсия приоритетов ухудшает предсказуемость поведения системы и может стать причиной нарушения установленных сроков выполнения задач с высоким приоритетом. Поэтому в состав сервисов ОСРВ должны включаться механизмы защиты разделяемых ресурсов, ограничивающие продолжительность инверсии приоритетов. К числу таких механизмов относится протокол приоритетных порогов (П3). Обеспечивая защиту разделяемых ресурсов, П3 исключает возможность взаимных блокировок и в рамках концепции взаимного исключения минимизирует продолжительность инверсии приоритетов.

Работа синхронизирующих механизмов, реализующих П3, характеризуется высокой степенью предсказуемости. Однако необходимой ценой за предсказуемость является пессимизм при определении прав доступа прикладных задач к разделяемым ресурсам.

Данная статья посвящена рассмотрению вопроса о том, как использование дополнительной информации о типе обращения задач к разделяемым ресурсам позволяет сделать более реалистичным П3.

Работа синхронизирующих механизмов, реализующих П3, характеризуется следующими положениями.

-         Каждому ресурсу ставится в соответствие приоритетный порог, численно равный приоритету задачи с наибольшим приоритетом из числа тех задач, что используют данный ресурс:

.

Задача, захватывая ресурс, тем самым устанавливает соответствующий приоритетный порог.

-         Задача, желая захватить ресурс, может сделать это только в том случае, если она преодолевает все установленные пороги, то есть ее приоритет строго больше, чем пороговые приоритеты всех захваченных в данный момент ресурсов. В случае, когда это условие не выполняется, решение текущей задачи блокируется, и низкоприоритетная задача, установившая непреодолимый порог, наследует ее приоритет.

-         Задача не может завершить выполнение до освобождения всех захваченных ею ресурсов. Данное ограничение естественно. Действительно, если позволить задаче удерживать ресурс между порождениями, то может возникнуть ситуация, когда задача с высшим приоритетом должна будет ожидать очередного запуска низкоприоритетной задачи.

-         Критические секции вложены, то есть разделяемые ресурсы освобождаются в порядке, обратном их захвату.

Таким образом, в качестве средства контроля над инверсией приоритетов П3 реализует идею наследования приоритетов.

Первое и второе свойства протокола неявно задают порядок захвата разделяемых ресурсов и тем самым исключают возможность выхода системы из строя по причине взаимной блокировки. Кроме того, задача с высоким приоритетом может войти в первую критическую секцию не раньше чем низкоприоритетные задачи освободят все необходимые ей ресурсы, таким образом, выполнение задачи из-за занятости разделяемого ресурса может быть отложено лишь однажды.

Добавление последних двух ограничений позволяет свести к простой формульной зависимости отношение между худшим временем блокирования задачи (наихудшее время задержки выполнения задачи по причине занятости ресурса) и длинами критических секций (под длиной критической секции подразумевается время ее выполнения). Время блокирования может быть найдено из следующего выражения:

.

Что означает: время блокирования i-й задачи равно наибольшей длине критической секции (cs) k-й задачи и ресурса r, где k и r удовлетворяют следующим условиям: (а) k-я задача имеет приоритет меньший, чем i-я задача; (б) k-я задача использует ресурс r; (в) приоритетный порог ресурса r выше либо равен приоритетному уровню i-й задачи.

Итак, П3 обеспечивает высокую степень предсказуемости и ограниченное время ожидания высокоприоритетной задачей освобождения ресурса низкоприоритетной задачей, причем формально инверсия приоритетов отсутствует (вследствие наследования приоритетов). Однако, по сути, инверсия осталась. Причем с введением приоритетных порогов механизм защиты разделяемых ресурсов стал пессимистичным: при использовании семафора блокируется выполнение только тех задач, которые пытаются захватить уже занятый ресурс; применение П3, как видно из формулы, приводит к тому, что по причине занятости ресурса откладывается решение, в том числе и тех задач, которые не имеют к нему непосредственного отношения.

Сумма инверсий. Важной характеристикой системы реального времени (СРВ) является степень пессимизма механизма защиты разделяемых ресурсов, контролирующего инверсию приоритетов. При переходе от одного протокола к другому степень пессимизма меняется. Изучение этих изменений количественными методами требует, чтобы пессимизм был измеримой величиной. Соответствующую характеристику назовем суммой инверсий и определим ее как сумму времени блокирования по всем задачам, выполнение которых было отложено по причине инверсии приоритетов, вызванной захватом i-й задачей ресурса r.

Тогда сумма инверсий для П3 будет вычисляться по формуле: Si= csi,r ´ (ceilr - prii ).

Сумма инверсий для протокола приоритетных порогов равна произведению длинны критической секции i-й задачи по отношению к ресурсу r и разности между высотой приоритетного порога ресурса r и приоритетным уровнем i-й задачи (см. рис. 1). Длина критической секции служит оценкой времени блокирования. Разность между высотой приоритетного порога ресурса и приоритетом захватившей его задачи характеризует число задач, выполнение которых отложено по причине инверсии приоритетов (традиционно в СРВ каждой задаче выделяется свой приоритетный уровень).

Чем меньше Si, тем меньше инверсия приоритетов, тем больше шансов, что в ходе анализа приложение реального времени будет признано выполнимым [1]. Пути уменьшения суммы инверсий для протоколов, базирующихся на понятии порога, очевидны. Во-первых, необходимо сделать длину критических секций как можно короче, во-вторых, следует стремиться к понижению приоритетных порогов ресурсов.

Автором статьи найдено решение, позволяющее в ряде случаев уменьшить сумму инверсий П3 за счет частичного смягчения требования доступа к разделяемому ресурсу в режиме взаимного исключения.

Читатели и писатели. Под разделяемым ресурсом обычно понимают набор данных, совместно используемый несколькими задачами, вследствие чего возникает опасность нарушения их целостности [2]. В вычислительных системах обычно имеются некие задачи, которые читают данные и называются читателями, и другие задачи, которые записывают данные и называются писателями [3]. Задачи-читатели не изменяют разделяемых данных, поэтому несколько таких задач могут производить обращение к ним одновременно. Задача-писатель может изменять данные, поэтому необходимо обеспечить к ним исключительный доступ.

Таким образом, необходимость во взаимном исключении возникает только в случае захвата разделяемых данных задачей-писателем. Достоинство данного решения заключается в том, что выполнение задачи-читателя не будет отложено по причине захвата ресурса другой задачей-читателем.

При реализации простейшей дисциплины доступа, учитывающей тип обращения к разделяемым данным (чтение/запись), может возникнуть ситуация, в которой писатель не может получить доступ к разделяемому ресурсу из-за постоянного появления запросов читателей – так называемая проблема бесконечного ожидания. В условиях применяемого в СРВ приоритетного планирования проблема бесконечного ожидания трансформируется в усугубленный возможностью перекрытия во времени критических секций задач-читателей вариант неконтролируемой (непредсказуемой) инверсии приоритетов.

Этот недостаток во многом предопределил ограниченность применения решения задачи о читателях и писателях – практически все современные протоколы защиты разделяемых ресурсов обеспечивают доступ к ним в режиме взаимного исключения.

Асимметричный П3. В основе разработанной автором статьи модификации П3 – асимметричного П3 (АП3 ) – лежит идея разделения обращений к разделяемому ресурсу на обращение для чтения и обращение для изменения разделяемых данных.

В соответствии с этим положением первое свойство оригинального П3 изменяется следующим образом.

Каждому ресурсу ставится в соответствие два приоритетных порога: читателей и писателей. Порог читателей устанавливается при удовлетворении запроса задачи-читателя и численно равен приоритету задачи с наибольшим приоритетом из числа тех задач, что могут произвести захват данного ресурса для записи: ceil_readr= .

Порог писателей устанавливается при удовлетворении запроса задачи-писателя и численно равен приоритету задачи с наибольшим приоритетом из числа задач, производящих любое обращение к данному ресурсу: ceil_writer= .

При этом формула для нахождения максимального времени ожидания задачей освобождения ресурса приобретет вид:

.

Что означает: время блокирования i-й задачи равно наибольшей длине критической секции (cs) k-й задачи и ресурса r по обращению типа t, где k, r и t удовлетворяют следующим условиям: (а) k-я задача имеет приоритет меньший, чем i-я задача; (б) k-я задача производит обращение типа t к ресурсу r; (в) приоритетный порог ресурса r по обращению типа t выше либо равен приоритетному уровню i-й задачи.

Таким образом, если раньше задачи, использующие некоторый разделяемый ресурс, либо представлялись однородным множеством, как в случае использования П3, либо разбивались на два подмножества, как в задаче о читателях-писателях, то теперь они делятся на три группы:

-         писатели – задачи, захватывающие ресурс для записи; как и раньше, их работа с разделяемыми данными происходит в режиме взаимного исключения как с читателями, так и друг с другом;

-         низкоприоритетные читатели – задачи-читатели с приоритетом, не превышающим приоритетного порога читателей; их работа с разделяемыми данными происходит в режиме взаимного исключения друг с другом и с задачами-писателями;

-         высокоприоритетные читатели – задачи-читатели, имеющие приоритет выше, чем порог читателей; их работа с разделяемыми данными происходит в режиме взаимного исключения только с писателями.

Главным результатом, которого позволяет добиться совместное использование идеи, заложенной в задаче о читателях-писателях, и П3, является тот факт, что теперь одновременно к ресурсу могут обращаться один низкоприоритетный и несколько высокоприоритетных читателей. Причем протокол наследует все полезные свойства П3, такие как гарантированное отсутствие взаимных блокировок и ограничение времени блокирования длиной только одной критической секции.

Кроме того, появляется возможность выполнения обращения на запись, вложенного в обращение на чтение. Действительно, в П3 не требуется никакой другой защиты разделяемых ресурсов, кроме установки приоритетных порогов, другими словами, имя ресурса используется лишь как идентификатор, по которому определяется, какой именно порог необходимо установить. Таким образом, нет причин, по которым задача не может сначала захватить ресурс для чтения, тем самым исключив только возможность изменения данных, а затем захватить тот же ресурс для записи, исключая любой доступ к нему. Данное свойство может оказаться полезным в случае, когда работа задачи-писателя с разделяемыми данными представляет собой логически неделимую цепочку чтение-обработка-запись, где монопольного доступа требует лишь последняя фаза, первые две исключают только другие задачи-писатели.

Сумма инверсий для АП3 при простом захвате ресурса будет вычисляться по формуле:

Si= csi,r,t ´ max(ceilr,t - prii , 0).

Для вычисления суммы инверсий вложенных обращений к разделяемым данным будет использоваться формула: Si = (csi,r,rd - csi,r,wr ) ´ (ceilr,rd - prii )+ +csi,r,wr ´ (ceilr,wr - prii ).

Сформулируем необходимое и достаточное условие снижения пессимизма механизма защиты ресурса r при переходе от оригинального П3 к АП3.

Переход от П3 к АП3 будет сопровождаться уменьшением суммы инверсий при обращениях к ресурсу r тогда и только тогда, когда выполняются следующие два условия:

-         задача, обладающая высшим приоритетом во множестве задач, использующих ресурс r, не является писателем (приоритетный порог писателей превышает порог читателей);

-         существуют как минимум две задачи-читателя.

Выполнение первого условия означает возможность перекрытия во времени критических секций задач-читателей без потери полезных свойств П3, выполнение второго условия говорит о том, что такая возможность будет востребована.

Итак, в ряде случаев удается снизить пессимизм механизма защиты разделяемых ресурсов, что, в свою очередь, увеличивает шансы положительного исхода анализа выполнимости программной СРВ.

Рассмотрим, как переход к АП3 позволяет добиться выполнимости приложения, невыполнимого в случае использования оригиналь- ного П3.

Три задачи: t1 с высшим приоритетом, t2 со средним и t3 с низшим могут производить обращение к разделяемым данным (ресурс r) для чтения, записи и чтения соответственно. Причем работа задачи-писателя t2 с данными представима цепочкой действий чтение-обработка-запись, на протяжении выполнения которой данные не должны изменяться другими задачами. Согласно П3 приоритетный порог ресурса r устанавливается на уровне приоритета задачи t1, то есть любое обращение задачи к разделяемым данным будет производиться в режиме взаимного исключения.

На рисунке 2 показано поведение системы в этом случае. Задача со средним приоритетом t2 захватывает ресурс r и в тот же момент (t2) вытесняется высокоприоритетной t1. Задача t1 запрашивает доступ к разделяемому ресурсу, но так как ресурс уже занят задачей t2, приостанавливается до момента его освобождения. После возобновления (момент t4) задача t1 завершает выполнение (t5) с опозданием, не уложившись в установленные сроки (d1). Выполнение следующего экземпляра задачи t1 блокируется низкоприоритетной задачей-читателем t3 на протяжении интервала t9-t10. Как видно из рисунка, длина критической секции задачи t3 достаточно велика, поэтому t1 и в этом случае нарушает установленные сроки выполнения (t12>d2). Таким образом, приложение невыполнимо.

В случае применения АП3 ресурсу r ставится в соответствие два приоритетных порога, высота порога для чтения устанавливается на уровне задачи-писателя (t2), уровень порога для записи совпадает с приоритетом задачи t1. Таким образом разрешается перекрытие во времени критических секций задач-читателей (t1 и t3). Однако остается проблема длительного блокирования задачей-писателем (t2) задачи-читателя (t1). Решить ее позволяет использование того факта, что работа задачи-писателя с разделяемыми данными производится по схеме чтение-обработка-запись. Работу задачи t1 к разделяемым данным следует построить в виде обращения к ресурсу r для чтения с вложенным в него обращением для записи (см. рис. 3).

Как видно из рисунка 3, использование АП3 позволяет добиться выполнимости набора задач, невыполнимого в случае П3. Действительно, выполнение высокоприоритетной задачи t1 не блокируется больше задачами t2 и t3 на время чтения разделяемых данных, продолжительность интервала, на протяжении которого t2 работает в режиме взаимного исключения с остальными задачами, достаточно мала и не приводит к нарушению установленных для t1 сроков выполнения.

Список литературы

1.     Tindell K., Hansson H. Real Time Systems by Fixed Priority Scheduling. DoCS, Uppsala University, 1997.

2.     Audsley N.C. Resource Control For Hard Real-Time Systems. University of York, UK, 1991.

3.     Дейтел Г. Введение в операционные системы. - М.: Мир. - 1987. - Т.1. -  С.137-140