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

Ответ 1

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

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

Ответ 2

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

• tLow работает, tMed и tHigh в настоящее время заблокированы (но не в критическом разделе).
• tLow входит и входит в критический раздел.
• tHigh unblocks и, поскольку это задача с наивысшим приоритетом в системе, она запускается.
• tHigh затем пытается ввести критический ресурс, но блокирует его как tLow.
• tMed разблокирует и, поскольку в данный момент это задача с наивысшим приоритетом в системе, она запускается.

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

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

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

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

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

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

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

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

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

Ответ 3

Приоритетная задача инверсии:
Рассмотрим один пример: Задачи:
Высокий приоритет (H)
Средний приоритет (M)
Низкий приоритет (L)

и блокировка X, может быть semaphore_lock (X).

Сценарий:
1. L запускается и приобретает X 2. Затем H пытается получить доступ к X, когда L имеет его, из-за семафора H спит.
3. M прибывает, pre-empts L и запускается. Фактически, H и M были двумя процессами, ожидающими выполнения, но M побежал, потому что H ожидал блокировки и не мог запустить.
4. M заканчивается, H не может войти, потому что L имеет замок, поэтому L запускается.
5. L заканчивается, освобождает замок. Теперь H получает блокировку и выполняет.

H имел наивысший приоритет, но выполнялся после выполнения процессов с более низким приоритетом. Это приоритетная инверсия.

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

Ответ 4

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

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

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

Ответ 5

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

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

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

В начале примера нить 1 и нить 2 спадают или блокируются. Тема 3 запускается и входит в критический раздел.

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

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

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

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

Ответ 6

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

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

Тем временем создается 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 имеет блокировку ресурсов.

Ответ 7

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

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

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

Итак, что происходит, так это то, что Proc1 блокируется до тех пор, пока Proc2 не завершится с FileA, по сути, их приоритеты "перевернуты", в то время как Proc2 содержит дескриптор FileA.

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

Ответ 8

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

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

Ответ 9

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

Ответ 10

Задача диспетчеризации возникает, когда процесс с более высоким приоритетом должен читать или изменять данные ядра, к которым в настоящее время обращаются процесс с более низким приоритетом, или цепочку процессов с более низким приоритетом. Поскольку данные ядра, как правило, защищены блокировкой, более высокоприоритетный процесс должен будет ждать, когда более низкий приоритет будет завершен с ресурсом. Ситуация усложняется, если процесс с более низким приоритетом вытесняется в пользу другого процесса с более высоким приоритетом. В качестве примера предположим, что мы имеем три процесса: L, M и H, приоритеты которых следуют порядку L < M < H. Предположим, что для процесса H требуется ресурс R, к которому в настоящее время обращается процесс L. Обычно процесс H будет ждать, пока L будет работать с использованием ресурса R. Однако теперь предположим, что процесс M становится управляемым, тем самым вытесняя процесс L. Косвенно, процесс с более низким приоритетом-процессом M-повлиял на то, как долго процесс H должен ждать, пока L не откажется от ресурса R. Эта проблема известна как инверсия приоритета. Она встречается только в системах с более чем двумя приоритетами, поэтому одно решение состоит в том, чтобы только два приоритета. Однако это неэффективно для большинства операционных систем общего назначения. Обычно эти системы решают проблему, реализуя протокол приоритета-наследования. Согласно этому протоколу все процессы, которые обращаются к ресурсам, требуемым более высокоприоритетным процессом, наследуют более высокий приоритет до тех пор, пока они не будут завершены с рассматриваемыми ресурсами. Когда они завершатся, их приоритеты возвращаются к их первоначальным значениям. В приведенном выше примере протокол приоритета-наследования позволит процессу L временно наследовать приоритет процесса H, тем самым предотвращая процесс M от вытеснения его выполнения. Когда процесс L завершил работу с использованием ресурса R, он откажется от своего унаследованного приоритета от H и примет свой первоначальный приоритет. Поскольку ресурс R теперь будет доступен, процесс H-not M-будет работать следующим образом. Ссылка: ABRAHAM SILBERSCHATZ

Ответ 11

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

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

Ответ 12

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

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

Скажем

• 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, она никогда не будет выполнена. Что может быть опасным во временных критических приложениях

И для решений см. приведенные выше ответы:)