Inwersja priorytetów

Inwersja priorytetów – zjawisko mogące występować w wielozadaniowych systemach operacyjnych takie, że w danej chwili wykonuje się inne zadanie niż powinno się wykonywać zgodnie z regułami algorytmu szeregowania.

Pojawienie się inwersji priorytetów związane jest najczęściej z dostępem zadań do zasobów chronionych przez algorytmy synchronizacji międzyprocesowej takie jak na przykład semafory. W praktyce inwersja priorytetów to zdobycie przez zadanie będące w sekcji krytycznej pierwszeństwa w dostępie do procesora kosztem zadań o wyższych priorytetach.

W niektórych przypadkach inwersja priorytetów może powodować opóźnienie w wykonywaniu zadań o wysokim priorytecie, ewentualnie zadania o niskim priorytecie mogą zwalniać dzielone zasoby, co odbywa się zwykle bez większej szkody. Jednakże istnieje wiele sytuacji, w których inwersja priorytetów może sprawić spore problemy. Jeśli zadanie o wysokim priorytecie ulega zagłodzeniu, może doprowadzić do nieprawidłowego działania systemu lub wywoływać działania zapobiegające uszkodzeniu, takie jak watchdog restartujący cały system. Klasycznym przykładem problemów spowodowanych inwersją priorytetów w systemie czasu rzeczywistego są kłopoty z działaniem lądownika sondy kosmicznej Mars Pathfinder.

Inwersja priorytetów może również ograniczyć wydajność systemu. Niektóre zadania mają niski priorytet dlatego, że nie jest dla nich ważna szybka realizacja (np. nie wymagają interakcji użytkownika lub jest to seria zadań w przetwarzaniu wsadowym). Odwrotnie jest natomiast z zadaniami o wysokim priorytecie – te z kolei często wymagają jakiejś interakcji lub pełnią ważną rolę gwarantującą poprawne działanie aktualnie wykorzystywanych elementów systemu. Inwersja priorytetów powoduje to, że wywoływanie zadań o niskim priorytecie blokuje zadania z wysokim priorytetem, co może doprowadzić do utraty stabilności i zawieszeń systemu.

Przykład

W systemie uruchomione są trzy procesy o identyfikatorach 1, 2 i 3, przy czym najwyższy priorytet posiada proces 1, a najniższy proces 3. Ponadto procesy 1 i 3 wykorzystują semafor jako mechanizm synchronizujący dostęp do pewnego zasobu.

Proces 3 podczas swojego wykonania uzyskuje dostęp do chronionego semaforem zasobu. Tuż po tym zostaje on wywłaszczony, po czym wykonanie rozpoczyna proces o najwyższym priorytecie – proces 1.

Proces 1 usiłuje uzyskać dostęp do zasobu chronionego przez semafor, jednak jest to niemożliwe, dopóki proces 3 nie zwolni zasobu. Wykonanie procesu 1 zostaje wstrzymane.

Algorytm szeregowania systemu operacyjnego wybiera do wykonania proces 2, proces ten zostaje wykonany do końca, gdyż posiada najwyższy priorytet spośród procesów gotowych do wykonania (gotowe do wykonania są procesy 2 i 3).

Dopiero po zakończeniu procesu 2 zostaje ponownie uruchomiony proces 3, który natychmiast po zwolnieniu zasobu zostaje wywłaszczony przez proces 1, który może kontynuować wykonanie.

W powyższym przykładzie proces 1 o wyższym priorytecie jest wykonywany dopiero po zakończeniu procesu 2 o niższym priorytecie – taka sytuacja jest nazywana inwersją priorytetów. Jako środek zaradczy stosuje się dziedziczenie priorytetów. Polega ono na tymczasowym podniesieniu priorytetu procesów wywłaszczonych, które rezerwują zasoby, do najwyższego priorytetu procesu oczekującego na te zasoby. Oryginalna wartość priorytetu zostaje im przywrócona natychmiast po zwolnieniu zasobów.