Szeregowalność zbioru zadań
Szeregowalność zbioru zadań – taka własność zbioru zadań, że istnieje przynajmniej jeden algorytm, który te zadania poszereguje tak, by spełnione były związane z nimi założenia.
Pojęcie to jest istotne dla systemów czasu rzeczywistego, gdzie oprócz podstawowych informacji o zadaniach takich jak określenie ich zbioru i priorytetów, kluczowe są czasy ich aktywacji, wykonywania i chwili granicznej oraz zależności międzyprocesowych. Zbiór zadań jest zatem szeregowalny, jeśli przynajmniej jeden algorytm jest w stanie poszeregować zadania tak, by zadania były wykonywane zgodnie z ich założeniami.
Przykłady[edytuj | edytuj kod]
- Mamy dwa zadania, które mają być wykonane od chwili t=0 do chwili t=7. Każde potrzebuje 4 kwanty czasu by się zakończyć. Zatem aby wykonać je oba potrzeba 8 kwantów czasu. Jest to więcej niż czas, którym dysponujemy i te zadania nie są szeregowalne.
W praktyce nie zawsze jednak wystarczy, aby suma czasów potrzebnych na wykonanie zadań była mniejsza od czasu, którym dysponujemy:
- Mamy trzy zadania, które muszą zostać wykonane od chwili t=0 do chwili t=10. Każde z zadań trwa 3 kwanty czasu. Zadanie 3 jest tworzone przez zadanie 2. Zadanie 2 staje się aktywne w chwili t=7. Te zadania również nie są szeregowalne, mimo że suma ich czasów jest mniejsza od granicznej chwili t=10.