Что такое инверсия приоритетов?

Question

Я слышал фразу «инверсия приоритетов» применительно к разработке операционных систем.

Что такое инверсия приоритетов?

Какую проблему нужно решить и как она решается?

Answer 1

Представьте себе три (3) задачи разного приоритета: tLow, tMed и tHigh.tLow и THigh получают доступ к одному и тому же критическому ресурсу в разное время;tMed делает свое дело.

1. tLow работает, tMed и tHigh в настоящее время заблокированы (но не в критической секции).
2. tLow приходит и входит в критическую секцию.
3. tHigh разблокирует и, поскольку это задача с наивысшим приоритетом в системе, она выполняется.
4. tHigh затем пытается войти в критический ресурс, но блокируется, так как tLow находится там.
5. tMedразблокируется, и поскольку теперь она является задачей с наивысшим приоритетом в системе, она запускается.

tНе может выполняться, пока tLow не откажется от ресурса.tLow не может работать до тех пор, пока tMed не прекратит работу.Приоритет задач был инвертирован;tHigh, хотя он имеет наивысший приоритет, находится в нижней части цепочки выполнения.

Чтобы «решить» инверсию приоритетов, приоритет tLow должен быть увеличен, чтобы он был как минимум таким же высоким, как tHigh.Некоторые могут повысить свой приоритет до максимально возможного уровня приоритета.Столь же важно, как повышение уровня приоритета tLow, снижение уровня приоритета tLow в соответствующие моменты времени.Различные системы будут использовать разные подходы.

Когда отбрасывать приоритет tLow ...

1. Никакие другие задачи не заблокированы ни на одном из ресурсов, которые имеет tLow.Это может быть связано с таймаутами или освобождением ресурсов.
2. Никакие другие задачи, способствующие повышению уровня приоритета tLow, не блокируются на ресурсах, которые имеет tLow.Это может быть связано с тайм-аутами или высвобождением ресурсов.
3. Когда происходит изменение того, какие задачи ожидают ресурс (ы), сбросьте приоритет tLow, чтобы он соответствовал приоритету задачи с наивысшим уровнем приоритета.заблокирован для его ресурса (ов).

Метод # 2 является усовершенствованием по сравнению с методом # 1 в том, что он сокращает время, в течение которого tLow имеет свой уровень приоритета.Обратите внимание, что в течение этого периода его уровень приоритета остается на уровне приоритета tHigh.

Метод # 3 позволяет уровню приоритета tLow постепенно снижаться, если необходимо, вместо одного шага «все или ничего».

Различные системы будут реализовывать разные методы в зависимости от того, какие факторы они считают важными.

• объем памяти
• сложность
• скорость реагирования в реальном времени
• Знание разработчика

Надеюсь, это поможет.

Answer 2

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

Довольно известным примером была проблема, с которой столкнулся марсоход Mars Pathfinder: http://www.cs.duke.edu/~carla/mars.html, это довольно интересное чтение.

Answer 3

Это проблема , а не решение.

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

Распространенное решение состоит в том, чтобы потоки с низким приоритетом временно наследовали высокий приоритет всех, кто ожидает блокировки, которые они удерживают.

Answer 4

Предположим, что приложение имеет три потока:

Thread 1 has high priority.
Thread 2 has medium priority.
Thread 3 has low priority.

Предположим, что поток 1 и поток 3 используют один и тот же код критической секции

Поток 1 и поток 2 спят или заблокированы в начале примера. Поток 3 запускается и входит в критическую секцию.

В этот момент поток 2 начинает работать, вытесняя поток 3, поскольку поток 2 имеет более высокий приоритет. Итак, поток 3 продолжает владеть критическим разделом.

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

В этот момент поток 2 начинает работать, поскольку он имеет более высокий приоритет, чем поток 3, а поток 1 не работает. Поток 3 никогда не освобождает критическую секцию, которую ожидает поток 1, потому что поток 2 продолжает работать.

Следовательно, поток с самым высоким приоритетом в системе, поток 1, блокируется в ожидании запуска потоков с более низким приоритетом.

Answer 5

[Предположим, низкий процесс = LP, средний процесс = MP, высокий процесс = HP]

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

Тем временем HP создается. Из-за более высокого приоритета CPU выполняет переключение контекста, и теперь HP выполняет (не тот же критический раздел, а какой-то другой код). В какой-то момент во время выполнения HP ему требуется блокировка на том же OBJ (может быть, а может и не быть на том же критическом участке), но блокировка на OBJ все еще удерживается LP, так как она была заблокирована при выполнении критического раздела , LP не может отказаться сейчас, потому что процесс находится в состоянии READY, а не RUNNING. Теперь HP переходит в состояние BLOCKED / WAITING.

Теперь MP входит и выполняет свой собственный код. MP не нуждается в блокировке OBJ, поэтому он продолжает работать нормально. HP ждет, пока LP снимет блокировку, а LP ждет, пока MP завершит выполнение, чтобы LP мог вернуться в состояние RUNNING (.. и выполнить и снять блокировку). Только после снятия блокировки LP может вернуться HP в состояние READY (а затем перейти в режим RUNNING, опередив задачи с низким приоритетом.)

Таким образом, фактически это означает, что до тех пор, пока MP не завершит работу, LP не сможет выполнить и, следовательно, HP не сможет выполнить. Таким образом, кажется, что HP ждет MP, даже если они не связаны напрямую через любые блокировки OBJ. -> Приоритетная инверсия .

Решением для приоритетной инверсии является Приоритетное наследование -

увеличить приоритет процесса (A) до максимального приоритета любого другой процесс ожидает любого ресурса, для которого A имеет блокировку ресурса.

Answer 6

Позвольте мне сделать это очень просто и понятно.(Этот ответ основан на ответах выше, но представлен четко).

Скажем, есть ресурс R и 3 процесса.L, M, H.где p(L) < p(M) < p(H) (где p(X) - приоритет X).

Say

• L начинает выполняться первым, а catch удерживается на R.(эксклюзивный доступ к R)
• H приходит позже и также требует эксклюзивного доступа к R, и поскольку L удерживает его, H должен ждать.
• M идет после H и , ему не нужно R.И поскольку M имеет все, что хочет выполнить, он заставляет L уйти, поскольку он имеет более высокий приоритет по сравнению с L.Но H не может этого сделать, поскольку у него есть ресурс, заблокированный L, который ему необходим для выполнения.

Теперь, чтобы прояснить проблему, на самом деле M должен ждать Hзавершить как p(H) > p(M), что не произошло, и это само по себе является проблемой.Если многие процессы, такие как M, приходят и не позволяют L выполнить и снять блокировку, H никогда не будет выполняться.Что может быть опасно в критических по времени приложениях

А для решения см. Ответы выше :)

Answer 7

Приоритет инверсии происходит так: Данные процессы H, M и L, где имена обозначают высокий, средний и низкий приоритеты, только H и L имеют общий ресурс.

Скажем, L сначала получает ресурс и начинает работать. Поскольку H также нужен этот ресурс, он попадает в очередь ожидания. M не делит ресурс и может начать работать, следовательно, это так. Когда L прерывается любым способом, M переходит в рабочее состояние, так как имеет более высокий приоритет и работает в тот момент, когда происходит прерывание. Хотя H имеет более высокий приоритет, чем M, поскольку он находится в очереди ожидания, он не может получить ресурс, что подразумевает более низкий приоритет, чем даже M. После того, как M закончится, L снова займет процессор, заставляя H все время ждать.

Answer 8

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

например: Файл A должен быть доступен для Proc1 и Proc2. Proc 1 имеет более высокий приоритет, чем Proc2, но Proc2 удается сначала открыть FileA.

Обычно Proc1 запускается, может быть, в 10 раз чаще, чем Proc2, но не может ничего сделать, потому что Proc2 держит файл.

В итоге происходит то, что блоки Proc1 до тех пор, пока Proc2 не завершит работу с FileA, по сути, их приоритеты будут «инвертированы», а Proc2 содержит дескриптор FileA.

Что касается «решения проблемы», то инверсия приоритетов сама по себе является проблемой, если она продолжается. Худший случай (большинство операционных систем не позволяют этому случиться), если Proc2 не разрешали работать до Proc1. Это может привести к блокировке системы, поскольку Proc1 будет продолжать получать назначенное время ЦП, а Proc2 никогда не получит время ЦП, поэтому файл никогда не будет выпущен.

Answer 9

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

Эта ситуация называется Priority Inversion.Поскольку процесс с более высоким приоритетом ожидает процесс с более низким приоритетом.

Answer 10

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