Протоколы доступа к разделяемым ресурсам

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

10.1. Инверсия приоритетов. Эта проблема возникает в случае, когда взаимодействующие задания обслуживаются в строгом соответствии с их статическими приоритетами. Оказывается, что в этом случае могут возникнуть непредвиденные разработчиками отклонения в работе системы. Пример взаимодействия заданий с инверсией приоритетов приведен на рис. 29.

Задание типа t₃ в момент t ₁ захватывает ресурс g и потому более приоритетное задание типа t₁, активизированное в момент t ₃ и запросившее в момент t ₄ ресурс g, не может действовать до тех пор, пока ресурс g не освободится. Суть проблемы в том, что задание типа t₂, получающее процессор в момент t ₂ возникновения события типа e _рег(t₂) и не имеющее отношения к использованию ресурса g, может владеть процессором сколь угодно долго.

Рис. 29. Инверсия приоритетов

Момент t ₅ предоставления процессора заданию типа t₂ может быть отложен и после выполнения t₂, если в ходе выполнения t₂ были зарегистрированы задания с приоритетами в промежутке между приоритетами t₂ и t₃. Таким образом, продолжительность интервала (t ₄, t ₆) ожидания ресурса g заданием типа t₁ и, соответственно, время отклика этого задания, то есть, продолжительность интервала (t ₃, t ₇), может оказаться недопустимо большим.

Негативные эффекты, вызываемые инверсией приоритетов, проявляются неустойчиво, и потому могут остаться не выявленными в ходе тестирования системы, в результате чего система со скрытым дефектом может быть принята в эксплуатацию. Известно, что в результате инверсии приоритетов возник отказ системы управления американским марсоходом.

10.2. Наследование приоритетов. В качестве варианта решения проблемы инверсии приоритетов был предложен протокол доступа к разделяемым ресурсам, получивший название протокола наследования приоритетов. Суть протокола сводится к тому, что если в момент запроса ресурса g заданием _x t _i ресурс g оказывается захвачен менее приоритетным заданием _y t _j, то временно, до момента освобождения этого ресурса, уровень приоритета _y t _j повышается до уровня приоритета _x t _i (то есть, _y t _j наследует значение приоритета _x t _i).

Пример взаимодействия заданий в условиях применения этого протокола представлен диаграммой на рис. 30. Порядок активизации заданий и выполнения операций запроса ресурсов (моменты времени t ₁ – t ₄) здесь такой же, как в случае рис. 29. Диаграмма рис. 30 совпадает с диаграммой рис. 29 до момента t ₄ возникновения события e _рег(t₂). В этот момент ядро системы, поддерживающей протокол наследования приоритетов, временно повышает уровень приоритета задания типа t₃ до уровня статического приоритета t₁. Поэтому в момент t ₄ процессор предоставляется не заданию типа t₂, а повысившему уровень приоритета заданию t₃.

Рис. 30. Наследование приоритетов

В момент t ₅ освобождения ресурса g заданию типа t₃ возвращается прежнее значение приоритета. Как видно из сравнения рис. 29 и рис. 30, применение протокола наследования приоритетов позволяет уменьшить продолжительность интервала выполнения высокоприоритетного задания типа t₁. Продолжительность интервала (t ₃, t ₆), то есть, время отклика высокоприоритетного задания, становится независимым от времени отклика среднеприоритетного задания.

10.3. Пороговые приоритеты разделяемых ресурсов. При использовании дисциплины обслуживания по приоритетам задач, разделяющих ресурсы, возможно применение таких методов удовлетворения запросов на ресурсы, которые исключают возможность взаимных блокировок (типа рис. 28). К таким методам относится использование протокола пороговых приоритетов (priority celling protocol). Суть метода в следующем.

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

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

Пример C.

Структура каждой из задач в примере C аналогична структуре задач из примера B. Нетрудно убедиться, что для комплекса трех задач из примера C без использования специального протокола доступа к ресурсам при любом способе назначения приоритетов найдется такая комбинация относительных сдвигов моментов регистрации заданий, которая вызовет взаимную блокировку (рис 31 а). Использование механизма инверсии приоритетов ничего не меняет в том смысле, что возможность взаимной блокировки сохраняется.

На рис. 31 б показано, как использование протокола пороговых приоритетов позволяет избежать взаимной блокировки. Ресурсам g 1и g 3 назначается высший пороговый приоритет, поскольку оба потенциально используются заданиями типа t₁, имеющими высший статический приоритет. Ресурсу g 2 назначается средний пороговый приоритет, поскольку он потенциально используется заданиями типа t₂, имеющими средний уровень статического приоритета и не используется заданиями типа g 3, имеющими высший уровень статического приоритета. На интервале (t ₁, t ₄) ресурс g 2 занят задачей t₃. Из этого следует, что на этом интервале запросы на ресурсы могут удовлетворяться только для заданий с высшим приоритетом (задания типа t₁). Вот почему в момент t ₂ запроса ресурса g 1 задание типа t₂ приостанавливается, несмотря на то, что в этот момент g 1 свободен. В момент t ₃ завершения задания типа t₁ ресурс g 2, имеющий средний пороговый приоритет, все еще занят и потому свободный g 1 все еще не может быть предоставлен заданию типа t₂. В момент t ₄ освобождения ресурса g 2 задание типа t₂ попрежнему не может быть возобновлено потому, что к этому моменту уже занят r 3, имеющий высший пороговый приоритет. Ресурс g 1 предоставляется задаче t₂ только в момент t ₅, когда освобождается высокоприоритетный g 3.

Рис. 31. Пример применения протокола пороговых приоритетов

С протоколом пороговых приоритетов реализация операций предоставления ресурсов усложняется. Зато разработчик приложения гарантирован от возникновения взаимных блокировок задач.

10.4. Протокол превентивного наследования приоритетов. Этот метод удовлетворения запросов на ресурсы, как и использование протокола пороговых приоритетов, исключает возможность взаимных блокировок. Опять с каждым ресурсом связывается параметр, называемый пороговым приоритетом ресурса, равный высшему статическому приоритету задания, которое может занять ресурс. Что же касается порядка предоставления ресурса, то здесь он принципиально иной. Метод построен таким образом, что всякий раз, когда задание _j t _i достигает оператора системного вызова по запросу ресурса g, этот ресурс оказывается свободен. То есть, запрос ресурса не может вызвать перевод задания в состояние ожидания. Если же пороговый приоритет запрашиваемого ресурса g превышает текущий уровень приоритета _j t _i, то уровень приоритета _j t _i временно (на период владения ресурсом) повышается до порогового приоритета занимаемого ресурса. Таким образом, задание с относительно низким уровнем статического приоритета может задержать ход реализации вновь зарегистрированных заданий с более высоким значением статического приоритета. Исключительно за счет таких задержек обеспечивается полезное свойство метода: задачи не могут перейти в состояние ожидания.

На рис. 32 использование протокола превентивного наследования приоритетов проиллюстрировано на том же примере из трех задач, который представлен на рис. 31).

Рис. 32. Применение протокола превентивного наследования приоритетов

В момент t ₁ низкоприоритетное задание типа t₃ захватывает среднеприоритетный ресурс g 2 и на время владения этим ресурсом становится среднеприоритетным. Поэтому в момент t ₂ вновь регистрируемое среднеприоритетное задание типа t₂, не получает ресурс процессора, поскольку не может вытеснить равное ему по приоритету задание типа t₃. Таким образом в момент регистрации задание типа t₂ приводится в состояние “ожидание CPU”. Далее, в момент t ₃ задание типа t₃ захватывает высокоприоритетный ресурс r 3 и как следствие, уровень его приоритет еще раз повышается. Поэтому его уже не может вытеснить и регистрируемое в момент t ₃ высокоприоритетное задание типа t₁. Исходный низший приоритет возвращается заданию типа t₃ в момент t ₅ освобождения им ресурса r 3 – в этот момент оно вытесняется высокоприоритетным заданием типа t₁.

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

Контрольные вопросы.

1. В чем суть понятия «инверсия приоритетов»?

2. От чего может зависеть продолжительность исполнения задания при возникновении инверсии приоритетов?

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

4. Гарантируется ли неконтролируемая инверсия приоритетов при использовании протокола наследования приоритетов?

5. Гарантируется ли предотвращение взаимных блокировок при использовании протокола наследования приоритетов?

6. Как определяются значения пороговых приоритетов разделяемых ресурсов?

7. Как выполняются операции операций захвата и освобождения ресурса при использовании протокола пороговых приоритетов?

8. Гарантируется ли неконтролируемая инверсия приоритетов при использовании протокола пороговых приоритетов?

9. Гарантируется ли предотвращение взаимных блокировок при использовании протокола пороговых приоритетов?

10. Чем отличается протокол пороговых приоритетов от протокола превентивного наследования приоритетов?

11. Возможен ли перевод задания в состояние ожидания при использовании протокола превентивного наследования приоритетов?

Поиск по сайту: