Wstęp do deterministycznego szeregowania zadań

Data dodania: 2011-10-07, Autor: SoDan, Dodał: Karol, Wyświetleń: 668

Deterministyczne szeregowanie zadań zajmuje się szeregowaniem (układaniem harmonogramów) zadań (programów, czynności, prac) na maszynach (procesorach, obrabiarkach, stanowiskach obsługi). Szukamy harmonogramu wykonania dla danego zbioru zadań w określonych warunkach, tak by zminimalizować przyjęte kryterium oceny (koszt) uszeregowania.

Model deterministyczny: parametry systemu i zadań są od początku znane.

Geneza i motywacje praktyczne:

• harmonogramowanie produkcji przemysłowej,
• planowanie projektów,
• organizacja pracy,
• plany zajęć szkolnych, spotkań i konferencji,
• przetwarzanie procesów w wielozadaniowych systemach operacyjnych,
• organizacja obliczeń rozproszonych.

Przykład. Pięć zadań o czasach wykonania p₁,...,p₅=6,9,4,1,4 należy uszeregować na trzech maszynach tak, by zakończyły się one możliwie jak najszybciej.

Rys.1. Reprezentacja graficzna harmonogramu - diagram Gantta.

Zasada poprawności harmonogramu:

• żadne zadanie nie może być jednocześnie wykonywane przez różne maszyny,
• żaden procesor nie pracuje równocześnie nad różnymi zadaniami.

Sposoby obsługi zadań

Procesory równoległe (każdy procesor może obsłużyć każde zadanie):

• procesory identyczne – wszystkie są jednakowo szybkie,
• procesory jednorodne – mają różne szybkości, ale stosunki czasów wykonania zadań są niezależne od maszyn,
• procesory dowolne – prędkości zależą od wykonywanych zadań.

Rys.2. Uszeregowanie na maszynach równoległych.

Procesory dedykowane

• zadania są podzielone na operacje (zadanie Z_j zawiera operacje O_ij do wykonania na maszynach M_i, o długościach czasowych p_ij). Zadanie kończy się wraz z wykonaniem swej najpóźniejszej operacji,
• dopuszcza się sytuację, gdy zadanie nie wykorzystuje wszystkich maszyn (operacje puste),
• żadne dwie operacje tego samego zadania nie mogą wykonywać się równocześnie,
• żaden procesor nie może równocześnie pracować nad różnymi operacjami.

Trzy główne typy systemów obsługi dla maszyn dedykowanych:

• system przepływowy (flow shop) – operacje każdego zadania są wykonywane przez procesory w tej samej kolejności wyznaczonej przez numery maszyn,
• system otwarty (open shop) – kolejność wykonania operacji w obrębie zadań jest dowolna,
• system gniazdowy (job shop) – dla każdego zadania mamy dane przyporządkowanie maszyn operacjom oraz wymaganą kolejność.

Przykład. Jednodniowy plan zajęć szkolnych. (Nauczyciele[M]-Klasy[Z])

M1  M2      M3 
Z1  3   2   1
Z2  3   2   2
Z3  1   1   2

Rys.3. Procesory dedykowane - system otwarty (kolejność operacji dowolna).

Przykład. Taśma produkcyjna.(Roboty[M]-Detale[Z])

M1  M2      M3
Z1  3   2   1   
Z2  3   2   2
Z3  1   1   2

Rys.4. Procesory dedykowane - system przepływowy (kolejność operacji musi być zgodna z numeracją maszyn).

Parametry zadań:

__Dane są: __zbiór n zadań Z={Z₁,...,Z_n} oraz m maszyn (procesorów) M={M₁,...,M_m}.

Zadanie Z_j :

• Czas wykonywania. Dla procesorów identycznych jest on niezależny od maszyny i wynosi p_j. Procesory jednorodne M_i charakteryzują się współczynnikami szybkości b_i, wtedy czas dla M_i to p_j/b_i. Dla maszyn dowolnych mamy czasy p_ij zależne od zadań i procesorów.
• Moment przybycia (release time) r_j . Czas, od którego zadanie może zostać podjęte. Wartość domyślna - zero.
• Termin zakończenia d_j . Opcjonalny parametr. Występuje w dwóch wariantach. Może oznaczać czas, od którego nalicza się spóźnienie (due date), lub termin, którego przekroczyć nie wolno (deadline).
• Waga w_j – opcjonalny parametr, określający ważność zadania przy naliczaniu kosztu harmonogramu. Domyślnie zadania są jednakowej wagi i wtedy w_j=1.

Zadania zależne:

• W zbiorze zadań Z można wprowadzić ograniczenia kolejnościowe w postaci dowolnej relacji częściowego porządku. Wówczas Z_i<Z_j oznacza, że zadanie Z_j może się zacząć wykonywać dopiero po zakończeniu Z_i (czemu? np. Z_j korzysta z wyników pracy Z_i).
• Jeśli ograniczenia te nie występują, mówimy o zadaniach niezależnych (tak się przyjmuje domyślnie) w przeciwnym razie są one zależne.
• Relację zwykle podaje się w postaci acyklicznego digrafu o wierzchołkach z Z (droga z Z_i do Z_j oznacza, że Z_i<Z_j) z łukami przechodnimi, lub bez (tylko relacje nakrywania – diagram Hassego).

Zadania mogą być:

• niepodzielne – przerwy w wykonaniu są niedopuszczalne (domyślnie)
• podzielne – wykonanie można przerwać i podjąć ponownie, w przypadku maszyn równoległych nawet na innym procesorze.

Rys.5. Uszeregowanie zadań podzielnych na maszynach równoległych.

Zasady poprawności harmonogramu:

• w każdej chwili procesor może wykonywać co najwyżej jedno zadanie,
• w każdej chwili zadanie może być obsługiwane przez co najwyżej jeden procesor,
• zadanie Z_j wykonuje się w całości w przedziale czasu (r_j,INF),
• spełnione są ograniczenia kolejnościowe,
• w przypadku zadań niepodzielnych każde zadanie wykonuje się nieprzerwanie w pewnym domknięto–otwartym przedziale czasowym, dla zadań podzielnych czasy wykonania tworzą skończoną sumę rozłącznych przedziałów.

Kryteria kosztu harmonogramu

Położenie zadania Z_i w gotowym harmonogramie:

• moment zakończenia C_i (ang. completion time),
• czas przepływu przez system (flow time) F_i=C_i–r_i,
• opóźnienie (lateness) L_i=C_i–d_i,
• spóźnienie (tardiness) T_i=max{C_i–d_i,0},
• “znacznik spóźnienia” U_i=w(C_i>d_i), a więc odpowiedź (0/1 czyli Nie/Tak) na pytanie „czy zadanie się spóźniło?”

Najczęściej stosowane:

• długość uszeregowania C_max=max{C_j : j=1,...,n},
• całkowity (łączny) czas zakończenia zadania SC_j = S_i=1,...,n C_i,
• średni czas przepływu F = (S_i=1,...,n F_i)/n.

Oparte na wymaganych terminach zakończenia:

• maksymalne opóźnienie L_max=max{L_j : j=1,...,n},
• maksymalne spóźnienie T_max=max{T_j : j=1,...,n},
• całkowite spóźnienie ST_j = S_i=1,...,n T_i,
• liczba spóźnionych zadań SU_j = S_i=1,...,n U_i,
• można wprowadzać wagi zadań, np łączne ważone spóźnienie Sw_jT_j = S_i=1,...,n w_iT_i.

Niektóre kryteria są sobie równoważne:

• SL_i = SC_i –Sd_i, F= (SC_i)/n – (Sr_i)/n.
• Minimalizacja długości harmonogramu. Maszyny równoległe.
• Procesory identyczne, zadania niezależne.
• Zadania podzielne P|pmtn|C_max.

Algorytm McNaughtona Złożoność O(n)

1. Wylicz optymalną długość C_max*=max{S_j=1,...,n p_j/m, max _j=1,...,n p_j},
2. Szereguj kolejno zadania na maszynie, po osiągnięciu C_max* przerwij zadanie i (jeśli się nie zakończyło) kontynuuj je na następnym procesorze począwszy od chwili 0.

Przykład. m=3, n=5, p₁,...,p₅=4,5,2,1,2.

S_i=1,...,5 p_i=14, max p_i=5, C_max*=max{14/3,5}=5.

Algorytm Liu O(n2), oparty na regule EDD(Earliest Due Date), działający nawet przy 1|ri,pmtn|L_max:

1. Spośród dostępnych zadań przydziel maszynę temu, które ma najmniejszy wymagany termin zakończenia,
2. Jeśli zadanie zostało zakończone, lub przybyło nowe – wróć do 1 (w drugim przypadku przerywamy zadanie).

Reguła EDD (Earliest Due Date) Reguła EDD stosowana jest do szeregowania zadań na jednej maszynie o czasach przybycia ustalonych na 0. Reguła EDD porządkuje sekwencje zadań według niemalejących wymaganych terminów zakończenia d_j.

Opis algorytmów szeregowania zadań http://riot.ieor.berkeley.edu/riot/Applications/Scheduling/index.html

Program LEKIN umożliwiający tworzenie harmonogramów http://www.stern.nyu.edu/om/software/lekin/index.htm

Notacja trójpolowa

Przykłady.

P3|prec|C_max – szeregowanie niepodzielnych zadań zależnych na trzech identycznych maszynach równoległych w celu zminimalizowania długości harmonogramu. R|pmtn,prec,r_i|SU_i – szeregowanie podzielnych zadań zależnych z różnymi czasami przybycia i terminami zakończenia na równoległych dowolnych maszynach (liczba procesorów jest częścią danych) w celu minimalizacji liczby zadań spóźnionych. 1|r_i,C_i=<d_i|– – pytanie o istnienie (brak kryterium kosztu, więc nic nie optymalizujemy!) uszeregowania zadań niepodzielnych i niezależnych o różnych momentach przybycia na jednej maszynie, tak by żadne zadanie nie było spóźnione.

INF - nieskończoność S - suma

Opracowano na podstawie materiałów do wykładu autorstwa dr hab. inż. Krzysztofa Giaro.