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

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

Формулировка

Рассмотрим две задачи H и L с высоким и низким приоритетом соответственно, каждая из которых может получить эксклюзивное использование общего R. ресурса Если H попытается получить R после того, как L получил его, то H блокируется до тех пор, пока L не откажется от ресурса. Совместное использование ресурса с эксклюзивным использованием ( в данном случае R ) в хорошо спроектированной системе обычно предполагает быстрый отказ от R , чтобы H (задача с более высоким приоритетом) не оставалась заблокированной в течение чрезмерных периодов времени. Однако, несмотря на хороший дизайн, возможно, что третья задача M со средним приоритетом станет работоспособной во время L использования R . В этот момент M имеет более высокий приоритет, чем L , вытесняет L (поскольку M не зависит от R ), из-за чего L не может быстро отказаться от R , что, в свою очередь, приводит к тому, что H — процесс с самым высоким приоритетом — не может run (то есть H подвергается неожиданной блокировке, косвенно вызванной задачами с более низким приоритетом, такими как M ).

Последствия

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

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

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

Решения

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

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

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

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

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

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

См. также

Ссылки

^ Гленн Ривз, «Что на самом деле произошло на Марсе» , команда JPL Pathfinder , получено 4 января 2019 г.
^ Объяснение проблемы инверсии приоритетов, с которой столкнулся Mars Pathfinder (PDF) , заархивировано из оригинала (PDF) 20 февраля 2021 г. , получено 4 января 2019 г.
^ Лэмпсон, Б; Ределл, Д. (июнь 1980 г.). «Опыт работы с процессами и мониторами в MESA». Коммуникации АКМ . 23 (2): 105–117. CiteSeerX 10.1.1.46.7240 . дои : 10.1145/358818.358824 . S2CID 1594544 .
^ Инверсия приоритета на MSDN

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

[1] Гленн Ривз, «Что на самом деле произошло на Марсе» , команда JPL Pathfinder , получено 4 января 2019 г.

[2] Объяснение проблемы инверсии приоритетов, с которой столкнулся Mars Pathfinder (PDF) , заархивировано из оригинала (PDF) 20 февраля 2021 г. , получено 4 января 2019 г.

[Lampson79-3] Лэмпсон, Б; Ределл, Д. (июнь 1980 г.). «Опыт работы с процессами и мониторами в MESA». Коммуникации АКМ . 23 (2): 105–117. CiteSeerX 10.1.1.46.7240 . дои : 10.1145/358818.358824 . S2CID 1594544 .

[4] Инверсия приоритета на MSDN

[1]

[2]

[3]

[4]