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

Question

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

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

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

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

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

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

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

Answer 3

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

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

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

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

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

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

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

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

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

Answer 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 имеет блокировку ресурса.

Answer 7

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

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

Сказать

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

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

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

Answer 8

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

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

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

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

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

Answer 9

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

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

Answer 10

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

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

Answer 11

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

Answer 12

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