Инверсия приоритета

редактировать

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

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

Содержание

1 Пример
2 Последствия
3 Решения
4 См. Также
5 Ссылки
6 Внешние ссылки

Пример

Рассмотрим две задачи H и L с высоким и низким приоритетом соответственно, каждый из которых может получить исключительное использование совместно используемого ресурса R. Если H пытается получить R после того, как L получил его, то H блокируется до тех пор, пока L не откажется от ресурса. Совместное использование ресурса монопольного использования (в данном случае R) в хорошо спроектированной системе обычно включает в себя незамедлительный отказ L от R, чтобы H (задача с более высоким приоритетом) не оставалась заблокированной в течение чрезмерных периодов времени. Однако, несмотря на хороший дизайн, возможно, что третья задача M среднего приоритета (p (L) < p(M) < p(H), where p(x) represents the priority for task (x)) becomes runnable during L's use of R. At this point, M being higher in priority than L, preempts L (since M does not depend on R), causing L to not be able to relinquish R promptly, in turn causing H—the highest priority process—to be unable to run (that is, H suffers unexpected blockage indirectly caused by lower priority tasks like M).

Последствия

В некоторых случаях инверсия приоритета может произойти без немедленного ущерба - отсроченное выполнение задачи с высоким приоритетом остается незамеченным, и, в конечном итоге, задача с низким приоритетом освобождает общий ресурс. Однако есть также много ситуаций, в которых инверсия приоритета может вызвать серьезные проблемы. Если задача с высоким приоритетом остается голодной ресурсов, это может привести к сбою системы или срабатыванию заранее определенных корректирующих мер, таких как сторожевой таймер, сбрасывающий всю систему. Неисправность, с которой столкнулся Mars Pathfinder Посадочный модуль 1997 года является классическим примером проблем, вызванных инверсией приоритета в системах реального времени.

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

Аналогичная проблема, называемая обмен крайним сроком, может возникнуть в пределах самого раннего крайнего срока первого планирования (EDF).

Решения

О существовании этой проблемы известно с 1970-х годов. Лэмпсон и Ределл опубликовали одну из первых статей, в которой указали на проблему инверсии приоритета. Такие системы, как ядро UNIX, уже решали проблему с примитивом splx (). Не существует надежного способа предсказать ситуацию. Однако существует множество существующих решений, наиболее распространенными из которых являются:

Отключение всех прерываний для защиты критических секций: Когда отключение прерываний используется для предотвращения инверсии приоритета, есть только два приоритета: вытесняемый и прерывания отключены. Без третьего приоритета инверсия невозможна. Поскольку имеется только одна часть данных блокировки (бит разрешения прерывания), переупорядочивание блокировки невозможно, и поэтому взаимоблокировки не могут возникнуть. Поскольку критические области всегда работают до завершения, зависаний не происходит. Обратите внимание, что это работает, только если все прерывания отключены. Если отключено прерывание только определенного аппаратного устройства, инверсия приоритета повторно вводится посредством определения приоритета прерываний аппаратными средствами. В ранних версиях UNIX ряд примитивов splx (0)... splx (7) отключал все прерывания до указанного приоритета. Правильно выбирая наивысший приоритет любого прерывания, которое когда-либо входило в критическую секцию, проблема инверсии приоритета могла быть решена без блокировки всех прерываний. Максимальные значения были назначены в порядке монотонной скорости, то есть более медленные устройства имели более низкие приоритеты.

В системах с несколькими процессорами используется простой вариант, «блокировка с одним общим флагом». Эта схема предоставляет один флаг в разделяемой памяти, который используется всеми процессорами для блокировки всех межпроцессорных критических секций с помощью занято-ожидание. Межпроцессорная связь в большинстве систем с несколькими процессорами является дорогостоящей и медленной. Поэтому большинство таких систем предназначены для минимизации общих ресурсов. В результате эта схема действительно хорошо работает во многих практических системах. Эти методы широко используются в простых встроенных системах, где они ценятся за надежность, простоту и низкое потребление ресурсов. Эти схемы также требуют умного программирования, чтобы критические разделы были очень краткими. Многие инженеры-программисты считают их непрактичными в компьютерах общего назначения.

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

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

Случайное повышение: Готовые задачи с блокировками случайным образом повышают приоритет до тех пор, пока они не выйдут из критической секции. Это решение используется в Microsoft Windows.

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

См. также

Ссылки

Внешние ссылки