Systemy Wbudowane
Dr inż. Mariusz Fraś
Systemy czasu rzeczywistego
" Szeregowanie zadań
" Zarządzanie dostępem do zasobów
© maf 1
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
ZarzÄ…dzanie zasobami w SCR
" Problem ograniczeń na użycie zasobów
Rywalizacja o zasoby
Zabezpieczenie systemu przed wyczerpaniem zasobów
spowodowanym przez ich nadmierne zużycie przez procesy
W SCR mechanizm limitujący pobieranie zasobów przez procesy
musi uwzględniać terminowość wykonania
Szeregowanie zadań bazujące na określonym terminie wykonania
" Przydzielanie zasobów
Zapobieganie zjawiskom zagłodzenia i blokady
Problem określenia harmonogramu (ciągu) operacji, tak aby
wszystkie zostały wykonane na czas
Czas pracy procesora
© maf 2
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań w SCR
" Szeregowanie
Przyporządkowanie kolejności wykonania wszystkich zadań (prac,
jobs) do procesorów w systemie, w każdym momencie czasu
wykonania tych zadań
" Poprawne szeregowanie w czasie rzeczywistym
Każdy procesor obsługuje ma co najwyżej jedno zadanie
Każde zdanie jest obsługiwane co najwyżej przez jeden procesor
Zadania nie sÄ… zaszeregowane przed czasem wyzwolenia
Wszystkie ograniczenia kolejnościowe i na zasoby są zachowane
" W tym ograniczenia na sumaryczny czas pracy procesora
" Dopuszczalne szeregowanie w czasie rzeczywistym
Zapewnione są ograniczenia czasowe dla wszystkich zadań
" Wskaz
nik uchybień - % zadań zaszeregowanych ale spóz
nionych
" Wskaz
nik utraty - % zadań w ogóle niewykonanych
" Szeregowanie optymalne (algorytm szeregowania)
Takie szeregowanie, które dopuszczalnie szereguje każdy zbiór zadań,
który jest dopuszczalnie szeregowalny przez każde inne szeregowanie
© maf 3
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań w SCR
" Test szeregowalności
Ocena możliwości dopuszczalnego uszeregowania dla danego
zbioru zadań
Test (warunek) wystarczajÄ…cy
" Jeśli spełniony to zadania są szeregowalne dopuszczająco
" Mogą być zadania nie przechodzące testu, ale szeregowalne
Np. dla RM dla 2 zadań warunek: UCPUd"70%.
Może być, że UCPU=90% ale zadania są szeregowalne dopuszczająco
Test (warunek) konieczny
" Jeśli nie spełniony to zadania nie są szeregowalne dopuszczająco
" Mogą być zadania przechodzące test, ale nie są szeregowalne dop.
Np. warunek UCPUd"100%.
Dla RM przy UCPU=90% dla 4 zadań z reguły nie szeregowalne
dopuszczajÄ…co
" Punkty szeregowania
Punkty na linii czasu (momenty) w których podejmowane są
decyzje szeregowania (alg. szeregowania jest aktywowany)
© maf 4
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań w SCR
" Taksonomia algorytmów szeregowania zadań w SCR
Sterowane czasem (clock-driven)
" Sterowane tablicowo (table-driven)
" Sterowane cyklicznie (cyclic)
Sterowane zdarzeniami (priorytetowe)
" Szeregowanie z priorytetami stałymi (ang. fixed-priority scheduling)
" Szeregowanie z dynamicznym przydziałem priorytetu (ang.
dynamic-priority scheduling)
Hybrydowe
" Adaptowany alg. karuzelowy (round-robin)
Time-sliced round-robin
Weighted round-robin
© maf 5
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie sterowane czasem
" Szeregowanie sterowane tablicowo
Punkty szeregowania określone przez przerwania zegarowe
Parametry wszystkich zadań periodycznych znane a priori
Uszeregowanie
" Wyznaczane przed wykonaniem (zazwyczaj przed uruchomieniem
systemu)
" Alokowany czas procesora równy TE
" Statyczna tablica uszeregowania dla hiper-okresu
Brak narzutu algorytmu szeregowania
Możliwość użycia złożonych algorytmów
Możliwość optymalizacji wybranych charakterystyk działania systemu
" Przerwania zegarowe ustawiane na kolejne momenty wykonania
zadań tk
Zadania nieperiodyczne
" Mogą istnieć
Jedna kolejka dla wszystkich
Nie zapewnia twardych ograniczeń czasowych
© maf 6
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie sterowane czasem
Zadanie tk
" Przykład
Z1 0
Zadania:
Z2 1
" Z1=(0,4,1,3) Z1 4
Z3 5
" Z2: (1,6,2,3)
Z2 8
" Z2: (1,12,3,7)
Z1 10
t
0 3 6 9 12 15 18 21
H H
t
0 3 6 9 12 15 18 21
H H
© maf 7
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie sterowane czasem
" Szeregowanie cykliczne
Główny cykl (hiperokres) dzielony na mniejsze cykle (ramki) o
długości f
" W ramce uruchamiany stały zbiór zadań / jedno zadanie (job)
" Zadanie uruchamiane na poczÄ…tku ramki
" Decyzje szeregowania na granicach ramki
" Szeregowanie za pomocą periodycznych przerwań
" Mniejszy narzut i łatwa kontrola przekroczenia terminów
Wymagania
" f e" {TE,i}  zapobieganie przerywania zadań
 minimalizacja przełączeń kontekstu
" ðÅ‚H/fûÅ‚ = H/f  hiperokres jest wielokrotnoÅ›ciÄ… ramki
 minimalizacja rozmiaru tablicy
" ( 2·f  nwp(Ti , f) ) d" TD,i  zapewnienie ograniczeÅ„ czasowych zadaÅ„
Podział zadań
" Aby spełniać wymagania
© maf 8
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie sterowane czasem
" Przykład
Zadania
" Z1 = (4, 1.0) , Z2 = (5, 1.8) , Z3 = (20, 1.0) , Z4 = (20, 2.0)
" Åši = 0 , TD,i = Ti , H=20
Ograniczenia
" f e" 2.0
" f " {2, 4, 5, 10, 20}
f = 2
" 2·f  nwp(4 , f) d" 4
2·f  nwp(5 , f) d" 5
2·f  nwp(20 , f) d" 20
© maf 9
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie priorytetowe
" Zasada działania
Punkty szeregowania określone przez zdarzenia takie jak:
pojawienie się zadania, ukończenie zadania, itp.
Decyzje szeregujÄ…ce na bazie priorytetu zadania
" Priorytet przyznawany wg określonego algorytmu
" Decyzje szeregujące podejmowane na bieżąco
" Wywłaszczanie zadań o niższym priorytecie
" Założenia analityczne:
Zadania sÄ… okresowe (pojawiajÄ… siÄ™ w regularnych odcinkach
czasu) o okresach równych limitom czasowym: TD,i = Ti
Zadania są niezależne  bez współdzielenia zasobów,
synchronizacji itp.  zadania nie blokujÄ… siÄ™
Wykonywane jest zawsze zadanie o najwyższym priorytecie,
które jest gotowe
Pomijane czasy operacji zarzÄ…dzania procesami (czas
przełączania kontekstu itp.)
© maf 10
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie priorytetowe
" Rate-Monotonic Scheduling (RM)
Tylko dla zadań periodycznych
Szeregowanie z priorytetami stałymi
Przydzielanie priorytetów w oparciu o to jak często zadania są
wywoływane
" Przypadek najprostszy: zadania z najwyższą częstością
wykonywania dostają najwyższy priorytet
PRi = 1/Ti
Algorytm nie jest optymalny dla zadań o dowolnych okresach
Optymalny dla zadań w systemach prosto-periodycznych
" System prosto-periodyczny
Ti < T Ò! T = n Å"Ti
j j
" "
n"N
Zi ,Z
j
" Test wystarczajÄ…cy UCPU d" UALG=1
© maf 11
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie priorytetowe
" Rate-Monotonic Scheduling (RM)
Warunek wystarczajÄ…cy skutecznego szeregowania
" Dla n zadań z priorytetami RM wszystkie limity czasowe typu hard
są spełnione jeśli zachowana jest zależność:
1
ëÅ‚ öÅ‚
n
TE,i
n
UCPU = d" U = n Å"ìÅ‚2 -1÷Å‚
" ALG
ìÅ‚ ÷Å‚
Ti
ìÅ‚ ÷Å‚
i=1
íÅ‚ Å‚Å‚
" n " Ò! UALG ln(2) (czyli ok. 0,693=69,3 %)
U
1
0,8
0,6
0,4
0,2
0
n
0 1 2 3 4 5 6 7 8 9 10
© maf 12
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie priorytetowe
" Przykład  dotrzymanie terminów
Parametry:
" P1: TE =2, TD=5, T=5
" P2: TE =4, TD=10, T=10
P1 P1,P2
P1,P2 P1 P1,P2
2 5 7 10 12 20
15 17 18 22
czas
" UCPU=(2/5)+(4/10)=0.8 d" UALG=2Å"(21/2  1) H" 0.83
" Przykład  niedotrzymanie terminów
Parametry:
" P1: TE =2.5, TD=5, T=5
" P2: TE =3.5, TD=8, T=8
P1
P1,P2 P2 P1 P1 P2 P1
2 5 7 10 20
8 15
czas
" UCPU=(2,5/5)+(3,5/8)=0.9375 > UALG=2Å"(21/2  1) H" 0.83
© maf 13
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie priorytetowe
" Deadline-Monotonic Scheduling (DM)
Zadania z krótszym limitem wykonania (względny deadline)
dostają proporcjonalnie wyższy priorytet
Dla zadań jak RM ale:
" TD d" T
Optymalność jak dla RM
" DM może czasem generować dopuszczalne szeregowanie gdy RM
nie robi tego
" Jeśli DM nie uszereguje dopuszczalnie to i RM nie wykona tego
" Test Lehoczkiego (Lehoczky test)
Dla RM i DM
Warunek skutecznego szeregowania
Pozwala określać dopuszczalność szeregowania dla zadań gdy
UCPU > UALG
© maf 14
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie priorytetowe
" Earliest Deadline First (EDF)
Szeregowanie z priorytetami dynamicznymi
Dla zadań periodycznych i aperiodycznych
Priorytet przyznawany indywidualnie do wartości odwrotnie
proporcjonalnej do czasu pozostałego do limitu czasu wykonania
(deadline) aktywnego zadania
Warunek wystarczajÄ…cy skutecznego szeregowania
" Dla założeń jak dla RM (zadania periodyczne) oraz TD,i e" Ti
n n
i
UCPU =
"Tc = "U d"1
Ti i=1 i
i=1
" Granica wykorzystania UALG=1
" Algorytm optymalny
Sens: jeśli dla danych parametrów zadań inny algorytm dotrzyma limity
to EDF też dotrzyma
© maf 15
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie priorytetowe
" Earliest Deadline First (EDF)
Wady
" Przy przeciążeniu nieprzewidywalne skutki
" Wyższy prioryted dla zadań, które przekroczyły deadline
" Dość trudny w implementacji
Przykład  dotrzymanie terminów (zadania szeregowalne)
Parametry:
" P1: TE =2.5, TD=5, T=5
" P2: TE =3.5, TD=8, T=8
P1,P2 P1 P2 P1 P1 P2 P1
2 5 10 20
0 6 8 15 16
czas
" UCPU=(2,5/5)+(3,5/8)=0.9375 < UALG=1
© maf 16
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie priorytetowe
" Earliest Deadline First (EDF)
Przypadek gdy TD < T
" P1: TE =2.5, TD=3.9, T=5
" P2: TE =3.5, TD=6, T=8
P1,P2 P1 P2 P1 P1 P2 P1
0 2 5 6 8 10 15 16 20
czas
Test wystarczajÄ…cy
" GÄ™stość zadania: ´i = TE,i / min(TD,i, Ti)
n
" Gęstość systemu: " =
"´
i
i=1
" Warunek: " d" 1
© maf 17
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie priorytetowe
" Least Slack Time (LST) / Least Laxity First (LLF)
Slack time (laxity)
L = tD,i  t  Trem
gdzie: Trem  czas wykonania pozostałej części zadania
Do wykonania wybierany proces z najmniejszym laxity
2 wersje
" Ścisły LST
" Nieścisły LST
Optymalność
" Jak EDF
" UALG = 1
Większy koszt niż EDF
Suboptymalny przy krótkich przeciążeniach i dla zadań
niewywłaszczalnych
Często dla: systemów wbudowanych i zadań aperiodycznych
© maf 18
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie priorytetowe
" Przykładowe porównanie algorytmów
Parametry zadań
" Z1: TE =2, TD=T=4 " H=20
" Z2: TE =5, TD=T=10 " UCPU = 1
J2,1 J2,2 J2,3
J1,1 J1,2 J1,3 J1,4 J1,5 J1,6
J1,1 J2,1 J1,2 J1,3 J2,2 J1,4 J1,5
FIFO
J1,1 J2,1 J1,2 J2,1 J1,3 J2,1 J2,2 J1,4 J2,2 J1,5 J2,2
RM
J1,1 J2,1 J1,2 J2,1 J1,3 J2,2 J1,4 J2,2 J1,5 J2,2
EDF
J1,1 J2,1 J1,2 J2,1 J1,3 J2,2 J1,4 J2,2 J1,5 J2,2
LST
2 4 6 8 10 12 14 16 18 20 t
0
© maf 19
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań nieperiodycznych
" Zadania periodyczne i nieperiodyczne
Test akceptacyjny dla zadań  twardych
Wykonywanie w tle
" Przyznanie priorytetów niższych niż zadaniom  twardym
" Może nie zapewniać limitów czasu wykonania
Metoda kradzieży  luzów (slack time stealing)
Technika kontroli zadań aperiodycznych przez specjalnie zadanie
 np. tzw. polling server
" Zadanie kontrolujÄ…ce jest zadaniem periodycznym
odrzucenie
sporadyczne
test
akceptacyjny
aperiodyczne
Scheduler Processor
periodyczne
© maf 20
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań nieperiodycznych
" Sterowanie czasem
Czasy przybycia nieznane a priori nie można przydzielać
ramek
Uruchamianie w szczelinach (slices)
Uruchamianie w tle
" Po zakończeniu zadań twardych w ramce
" Zadania aperiodyczne
Nie ma gwarancji dotrzymania terminu
Minimalizacja czasu odpowiedzi dla takich zadań
" Zadania sporadyczne
Test akceptacyjny
t
0 3 6 9 12 15 18 21
24
© maf 21
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań nieperiodycznych
" Sterowanie czasem
Slack time stealing
" Przerywanie zadań nieperiodycznych
" Dla zadań twardych nie ma korzyści z ukończenia czasu wcześniej
niż w momencie tD
" Przesuwanie szczelin adekwatnie do pojawiania siÄ™ zad. nieperiod.
t
0 3 6 9 12 15 18 21
24
TE=1,5, TD=2 TE=1,5, TD=2 TE=2,5, TD=3
t
0 3 6 9 12 15 18 21
24
Więcej zadań: kolejka EDF
© maf 22
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań nieperiodycznych
" Sterowanie zdarzeniami
Szeregowanie w tle
" Uruchamianie tylko gdy nie ma zadań periodycznych
Niezwykle prosta implementacja
Możliwe długie czasy odpowiedzi dla zadań nieperiodycznych
Szeregowanie przerwaniowe
" Gdy przychodzi zadanie nieperiodyczne wstrzymywane jest
wykonanie zadań periodycznych
Może powodować niedotrzymywanie terminów zadań periodycznych
Ewentualnie stosowane dla zadań sporadycznych
Generalnie nie do przyjęcia
Slack stealing
" Szeregowanie zadań periodycznych tak aby nie przekroczyć
terminów i uzyskać użyteczne szczeliny
" Złożone algorytmy sterowania i trudne do implementacji
Aperiodic Tasks Server (ATS)
" Specjalne zadanie traktowane jak periodyczne dla obsługi zadań
nieperiodycznych
© maf 23
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań nieperiodycznych
" ATS
ZS=(TS,TE,S)
" TS  czas (okres) odnowienia (replenishment time) /
okres kontroli wykonania
" TE,S  budżet wykonania (budżet, pojemność)
Wykonuje zadania nieperiodyczne w ramach budżetu
Gdy serwer jest szeregowany i wykonuje zadania
nieperiodyczne zużywa budżet
Szeregowanie serwera jak inne zadanie periodyczne
" Różne typy serwerów ze względu na sposób
zużywania i odnawiania budżetów
Polling server
" Zadanie serwera z najwyższym priorytetem
" Zużycie budżetu 1/1 jednostkę czasu, potem oddanie sterowania
" Odnowienie budżetu na początku okresu (co TS) o wartość TE,S
" Brak zadań nieperiodycznych zużycie budżetu (wyzerowanie)
 serwer oddaje procesor i nie wznawia siÄ™ w tym okresie
Deferrable server
Bandwith-preserving server
© maf 24
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań nieperiodycznych
" Deferrable server
Ulepszenie Polling server
Reguły działania
" Konsumpcja budżetu 1/1
" Nie zużyty budżet jest zachowywany
" Odnowienie budżetu co okres TS=TDS
Z2=(Åš=4,T=7,TE=3)
Z1=(Åš=0,T=13,TE=2)
0 2 4 6 8 14 16 18 czas
10 12
© maf 25
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań nieperiodycznych
" Deferrable server
Ulepszenie Polling server
Reguły działania
" Konsumpcja budżetu 1/1
" Nie zużyty budżet jest zachowywany
" Odnowienie budżetu co okres TS=TDS
2
budżet
0
JA=(TE=3,5)
ZDS=(Åš=0,T=6,TE=2)
Z2=(Åš=4,T=7,TE=3)
Z1=(Åš=0,T=13,TE=2)
0 2 4 6 8 14 16 18 czas
10 12
© maf 26
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań nieperiodycznych
" Deferrable server
Szeregowalność dla stałopriorytetowych algorytmów
" W ogólności nie ma warunku (wystarczającego lub koniecznego)
maksymalnego wykorzystania procesora
" Przypadek szczególny:
n periodycznych, niezależnych i wywłaszczalnych zadań takich, że:
Ti = TD,i
TS < T1 < T2 < & < Tn < 2Å"TS
Tn < TS + TE,S
szeregowanie RM jest skuteczne dla
U <
© maf 27
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań nieperiodycznych
" Deferrable server
Szeregowalność dla zmiennopriorytetowych algorytmów
(uwzględniających czas do TD)
" Dla systemu:
N periodycznych zadań niezależnych i wywłaszczalnych
TD,S = TS
Tn < TS + TE,S
szeregowanie EDF zapewnia terminy wykonania dla zadania Zi gdy:
N
ëÅ‚ öÅ‚
TE,n TS -TE,S ÷Å‚ d" 1
wi = +US Å"ìÅ‚1+
"
ìÅ‚
min(Tn,TD,n ) TD,i ÷Å‚
n=1 íÅ‚ Å‚Å‚
Trzeba obliczać dla każdego zadania
" Przykład:
TS =4, TE,S =0,8
Z1=(3, 0.6), Z2=(5.0, 0.5), Z3=(7, 1.4)
w1=0,913, w2=0,828. w3=0,792
Zadania szeregowalne
© maf 28
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Szeregowanie zadań nieperiodycznych
" Total Bandwith Server (TBS)
Rezerwacja Us (limit obciążenia) dla zadań aperiodycznych w
kolejce serwera
" Całkowite obciążenie zadaniami aperiodycznymi d" US
" PoczÄ…tkowo: TE,0 = TD,0 = 0
" Obliczany deadline dla każdego nowego zadania aperiodycznego i
TE,i
TD,i = max(ti,TD,i-1)+
US
ti  moment przybycia zadania aperiodycznego i
" Po przyznaniu limitu zadanie wstawiane w kolejkę zadań gotowych i
szeregowane algorytmem EDF, tak jak inne zadania periodyczne
Warunek wystarczajÄ…cy skutecznego szeregowania
" Pomijalny koszt szeregowania zadań aperiodycznych
n
UCPU =
"U +US d"1
Pi
i=1
© maf 29
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Ograniczenia na użycie zasobów
Ograniczenia
" Ilościowe (np. pamięć)
" Współdzielenie
Problem niewywłaszczalności
Dostęp wzajemnie wykluczający
Mechanizmy limitujące zużycie zasobów przez procesy
" Zabezpieczanie przed nadmiernym zużyciem przez procesy
" Zabezpieczanie przed opóz
nieniami związanymi z ich użytkowaniem
" Współdzielony dostęp do zasobów
Blokowanie zasobów  sekcje krytyczne
Zapobieganie zjawiskom zagłodzenia i zakleszczeń
" Sekcja krytyczna < maksymalne opóz
nienie obsługi przerwań
Tymczasowe maskowanie przerwań
" DÅ‚uga sekcja krytyczna
Metody jak w s.o. ogólnego przeznaczenia
Zapobieganie zjawiskom inwersji priorytetów
© maf 30
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Zarządzanie pamięcią
Model Task Control Block
Pamięć wirtualna
" LRU (wolny od anomalii Bellady ego)
" Funkcje zgłaszania przez proces systemu "ważnych stron"
" Funkcje blokowania stron w pamięci
" Technika zbiorów roboczych (ang. working sets)
Lokalność wykonywania kodu
Zachowywanie w pamięci podręcznej jak stron
" Często brak mechanizmu wymiatania stron
" System plików
Opóz
nienia związane z fragmentacją systemu plików
Contiguous file allocation
" Np. w systemach RT Linux
© maf 31
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Współdzielony dostęp zasobów
2 problemy przy rywalizacji o zasób
" Opóz
nienia w wykonywaniu zadań
" Zakleszczenia
Rezultat: zaburzenia temporalne działania systemu
© maf 32
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Inwersja priorytetów
Wykonywanie zadań o niższym priorytecie przed zadaniami o
wyższym priorytecie
" Występuje zasób współdzielony
" Dostęp do zasobu przez mechanizm ochrony (SK)
" Zadanie o niższym priorytecie zajmuje zasób przed zadaniem o
wyższym priorytecie potrzebującym tego samego zasobu
Opóz
nianie zadań krytycznych
" Trudne do oszacowania w przypadku pojawiania się zadań o
pośrednich priorytetach
priorytet
priorytet
Z  odwołanie do zasobu Z
Z
Zw  zwolnienie
Zw
zasobu Z
Z
Z
czas
czas
© maf 33
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Przypadek sondy Pathfinder (1997 r.)
Generalia
" System operacyjny VxWorks firmy Wind River Systems
" Wywłaszczająca strategia szeregowania wątków z priorytetami
" Po kilku dniach trwania misji sonda zamilkła na jakiś czas 
wykonała restart systemu co spowodowało utratę zgromadzonych
wcześniej danych
Okoliczności
" W awarii brały udział trzy wątki:
WÄ…tek informacyjny  wÄ…tek o wysokim priorytecie zarzÄ…dzajÄ…cy  szynÄ…
informacyjną  wspólnym obszarem pamięci w którym inne wątki
umieszczały swe dane
WÄ…tek przekazywania danych meteorologicznych  niski priorytet
Watek komunikacyjny  pośredni priorytet
" Wspólny obszar pamięci był zabezpieczony muteksem
© maf 34
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Przypadek sondy Pathfinder (1997 r.)
Fakty:
" WÄ…tek meteorologiczny zajÄ…Å‚ muteks.
" Przerwanie uaktywniło wątek informacyjny który próbował zająć
muteks, ale ponieważ był on zajęty to zablokował się.
" Wątek komunikacyjny wywłaszczył wątek meteorologiczny. Było to
długotrwałe zadanie. Muteks nie mógł być zwolniony przez wątek
meteorologiczny.
" Proces nadzorujący działanie całego systemu (Watchdog Timer)
zaobserwował że  szyna informacyjna nie działa i przeprowadził
restart całego systemu.
© maf 35
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Protokoły sterowania dostępu do zasobów
Niewywłaszczalne sekcje krytyczne
Protokół PIP (ang. Priority Inheritance Protocol)
Protokół HLP (ang. Highest Locker Protocol)
Protokół PCP (ang. Priority Ceiling Protocol)
" Cele:
Ograniczanie zjawiska inwersji priorytetów
Kontrola zjawiska inwersji priorytetów
Zapobieganie zakleszczeniom
© maf 36
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Niewywłaszczalna sekcja krytyczna
Czas przebywania w sekcja krytycznej < latency systemu
Zadanie (job) uzyskujące dostęp do zasobu otrzymuje
najwyższy priorytet i jest niewywłaszczalne
Wady
" Każde zadanie o wyższym priorytecie może być blokowane przez
zadanie o niższym priorytecie
" Blokowanie nawet gdy nie ma konfliktów dostępu do zasobu
© maf 37
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Protokół PIP (ang. Priority Inheritance Protocol)
Wymagania
" Szeregowanie priorytetowe i wywłaszczanie procesów
" Nie wymaga wiedzy a priori o zapotrzebowaniu na zasoby
Zasada
" Zadanie mające dany zasób dziedziczy priorytet wstrzymywanego
zadania (o wyższym priorytecie) oczekującego na ten zasób
priorytet
Z
Zw
Z
czas
© maf 38
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Protokół PIP (ang. Priority Inheritance Protocol)
Cechy
" Zmniejszenie czasu trwania inwersji
" Zapobiega wywłaszczeniu w SK przez zadania pośrednie
" Niebezpieczeństwo wzajemnego zakleszczenia
priorytet
Z2 Z Z2 Zw
Z
zakleszczenie
czas
© maf 39
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika
Sterowanie dostępem do zasobów
" Protokół PCP (ang. Priority Ceiling Protocol)
Eliminuje problem zakleszczeń
Ogólny schemat działania
" Procesy majÄ… priorytety P(j)
Niezmienny do momentu wywołania procedury podniesienia priorytetu
" Każdy zasób Ri ma przypisany tzw. pułap priorytetów PP(Ri)
" W chwili t jest pułap priorytetowy systemu PP(t)
PP(t) = max (PP(Ri)) z zasobów zamówionych
" Zasada alokacji zasobu dla procesu zależy od P(j), PP(t) i PP(Ri)
zamawianego zasobu
" Reguła podnoszenia priorytetu
Gdy blokuje się zadanie j, to zadanie k które blokuje j dziedziczy
priorytet PP(j)
Zadanie k wykonuje się z podniesionym priorytetem do momentu aż
zwolni wszystkie zasoby dla których PP(R) >= PP(j)
W tym momencie jego priorytet jest obniżany do priorytetu sprzed
procedury dziedziczenia priorytetu wyższego
© maf 40
Å›
Fra
awska
Å‚
Informatyki
Mariusz
Wroc
Instytut
Politechnika