Альтернатива приоритетному наследованию: операционная система

Question

Я только что столкнулся с наследованием приоритетов, которое является решением проблемы инверсии приоритетов в операционных системах. Кто-нибудь может предложить какое-либо другое решение, кроме этого?

Спасибо

Answer 1

альтернативы

1. Приоритет потолка
2. Можно использовать комбинацию наследования приоритета и потолка приоритета.

Чем продвижение prio-потолка отличается от prio-наследования?

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

Недостатки:

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

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

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

Повышение приоритетного потолка: приоритетный потолок указывается для каждого мьютекса при его создании. Это равно приоритету задачи с наивысшим приоритетом, которую может занять мьютекс. Когда задача с низким уровнем prio принимает этот мьютекс, его prio немедленно повышается до потолка. Следовательно, задача среднего уровня не может выполнять приоритет перед этой задачей, если она владеет мьютексом.

Недостаток:

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

Answer 2

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

Когда поток с высоким приоритетом блокируется на ресурсе, выберите случайный готовый поток с более низким приоритетом. Повысьте приоритет этого потока до приоритета заблокированного потока в течение определенного промежутка времени, который считается достаточным для освобождения ресурса. Затем отбросьте приоритет и выберите другой поток. Повторяйте это, пока ресурс не будет освобожден.

Я не знаю ни о каком формальном анализе алгоритма, но должно быть очевидно, что наследование приоритетов и потолок приоритетов, охватываемый @ShreyasS, более эффективны при сокращении времени инверсии приоритетов. Насколько они более эффективны, я понятия не имею. Конечно, это зависит от приложения, поэтому тестирование будет необходимо в любом случае.

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

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