TEORIA

Deterministyczne problemy szeregowania zadań (programów) na procesorach (maszynach) polegają na wykonywaniu danego zbioru zadań (których wszystkie parametry są z góry znane) przez określony zbiór procesorów w taki sposób, aby określone kryterium oceny wykonania zbioru zadań było ekstremalizowane. Procesory mogą być przy tym albo równoległe tzn. spełniające te same funkcje, albo dedykowane tzn. różniące się wykonywanymi funkcjami.

Interpretacja problemu szeregowania zadań jest bardzo szeroka i istotna. Zadania i maszyny mogą być interpretowane np. jako: detale i obrabiarki, statki i doki, zajęcia lekcyjne i nauczyciele, pacjenci i wyposażenie szpitala lub miasta i komiwojażerowie. Pomimo iż mówimy o procesorach i zadaniach interpretacja nie powinna być czysto komputerowa.

- Spis treści -

Rozpatrujemy zbiór n zadań Z = {Z₁, Z₂, ..., Z_n} i zbiór m procesorów P = {P₁, P₂, ..., P_n}.

Ogólnie ujmując procesory równoległe to procesory wykonujące te same zadania. Wyróżniamy wśród nich trzy typy w zależności od prędkości pracy:

• Procesory identyczne - wykonują wszystkie zadania ze zbioru zadań Z z równymi prędkościami.
• Procesory jednorodne - wykonują zadania ze zbioru zadań Z z różnymi prędkościami ale w ten sposób, że prędkość każdego z nich jest stała i nie zależy od zadanie ze zbioru Z.
• Procesory dowolne - jeżeli prędkości co najmniej dwóch procesorów ze zbioru P zależą od wykonywnego zadania ze zbioru Z.

- Spis treści -

W przypadku procesorów dedykowanych wyróżnia się trzy systemy obsługi zadań:

• Przepływowy (flow shop) - każde zadanie ze zbioru Z musi być wykonane w tej samej kolejności przez wszystkie procesory ze zbioru P.
• Otwarty (open shop) - kolejność wykonania nie jest narzucona.
• Ogólny (job shop) - zarówno podzbiór procesorów mających wykonać dane zadanie, jak i kolejność wykonywania każdego zadania są dowolne, choć określone.

W przypadku procesorów dedykowanych zadanie Z_j należące do zbioru Z dzieli się na operacje O_{1 j} , O_{2 j} , ...,O_{k j} , z których każda może żądać innego procesora. Przy tym dla systemu przepływowego liczba operacji przypadających na zadanie jest równa liczbie procesorów m, a kolejność ich wykonywania jest taka, że operacja O_1j jest wykonywana na procesorze P₁, operacja O_2j - na procesorze P₂ itd. Ponadto wykonanie operacji O_i-1,  j musi poprzedzać wykonanie operacji O_{i j}, i = 2, 3, ..., m. W przypadku systemu otwartego na wykonanie jednego zadania składa się także m operacji, identyczne jest również ich przyporządkowanie do procesorów. Kolejność wykonania operacji jest natomiast dowolna i nieokreślona. W przypadku systemu ogólnego zarówno liczba operacji przypadających na zadanie jak i przyporządkowanie ich do procesorów i kolejność wykonywania są dowolne, lecz muszą być z góry określone.

- Spis treści -

Zadanie Z_j Î Z jest scharakteryzowane przez następujące dane:

• Wektor czasów wykonywania - t_j = [t_1j, t_2j, ..., t_mj]^T, gdzie t_ij jest czasem, w którym procesor P_i wykonuje zadanie Z_j. W przypadku procesorów identycznych czasy wykonywania zadania Z_j są równe dla wszystkich procesorów, mówimy zatem o czasie wykonywania t_j. W przypadku procesorów jednorodnych czas wykonywania zadania Z_j na procesorze P_i jest równy t_ij = t_j / b_i, i = 1, 2, ...,m, gdzie t_j jest czasem wykonywania zadania Z_j na wybranym procesorze standardowym (np. najwolniejszym), zaś b_i jest współczynnikiem prędkości procesora P_i w stosunku do procesora standardowego.
• Moment przybycia (gotowości do wykonania) - r_j. Jeśli dla wszystkich zadań ze zbioru Z momenty te są jednakowe, to przyjmuje się r_j = 0, j = 1, 2, ..., n.
• Termin zakończenia wykonywania - d_j. Jeśli wykonywanie zadania Z_j musi zostać zakończone przed upływem terminu d_j, to d_j nazwiemy linią krytyczną.
• Waga (priorytet) - w_j, interpretuje się ją jako koszt przebywania zadania Z_j w systemie komputerowym w ciągu jednostki czasu. Zatem koszt przebywania w systemie zadania Z_j zakończonego w chwili t jest równy w_jt.

- Spis treści -

• Zadania podzielne (w przypadku maszyn dedykowanych - operacje) - wykonywanie każdego zadania ze zbioru Z (lub operacji z odpowiedniego zbioru operacji) może być przerwane w dowolnej chwili i następnie kontynuowane, być może na innym procesorze, przy czym obsługa tego przerwania nie jest związana ze stratą czasu.
   
• Zadania niepodzielne - przerwanie wykonywania każdego zadania ze zbioru Z jest niemożliwe.
   
• Ograniczenia kolejnościowe - określone w sposób Z_iZ_j oznacza, że wykonywanie zadania Z_i musi zostać zakończone przed rozpoczęciem wykonywania zadania Z_j. Jeżeli w zbiorze zadań istnieje przynajmniej jedno tak określone ograniczenie kolejnościowe mówimy o zbiorze zadań zależnych, w przeciwnym razie - o zbiorze zadań niezależnych.

  - Spis treści -

• Uszeregowanie - takie przyporządkowanie w czasie procesorów ze zbioru P do zadań ze zbioru Z, dla którego spełnione są następujące warunki:
   
  • w każdej chwili każdy procesor wykonuje co najwyżej jedno zadanie;
  • zadanie Z_j jest wykonywane w przedziale czasowym [r_j, ¥ );
  • wszystkie zadania zostaną wykonane;
  • dla każdych dwóch zadań Z_i, Z_j Î Z, takich że Z_iZ_j, wykonywanie zadania Z_j rozpoczyna się po zakończeniu wykonywania zadania Z_i;
  • w przypadku zadań niepodzielnych wykonanie żadnego zadania w zbiorze Z nie jest przerywane, w przypadku zadań podzielnych liczba przerw w wykonywaniu każdego zadania jest skończona.

W przypadku zadań niepodzielnych mówimy o uszeregowaniu niepodzielnym, w przypadku zadań podzielnych - o uszeregowaniu podzielnym.

W danym uszeregowaniu dla zadania Z_j, j = 1, 2, ..., n, możemy określić:
 
• moment zakończenia wykonywania C_j;
• czas przepływu (przebywania w systemie) F_j, będący sumą czasów oczekiwania i wykonywania:
  
        F_j = C_j - r_j
   
• opóźnienie L_j:
  
        L_j = C_j - d_j
   
• spóźnienie T_j:
  
        T_j = max{C_j - d_j, 0}

- Spis treści -

• Uszeregowanie optymalne - uszeregowanie minimalizujące wybrane kryterium optymalności.
  
  Trzy zasadnicze kryteria wykorzystywane do oceny uszeregowań to:
   
  • Długość uszeregowania (lub czas wykonania zbioru zadań)
    
          C_max = max{C_j}
     
  • Średni czas przepływu (lub średni czas przebywania zadania w systemie)
    
         
    
    lub średni ważony czas przepływu
    
         
    
    gdzie w_j jest priorytetem zadania Z_j.
     
  • Maksymalne opóźnienie
    
          L_max = max{L_j}
    
    W niektórych zastosowaniach są również wykorzystywane: średnie spóźnienie
    
         
    
    i średnie ważone spóźnienie
    
         
    
    

- Spis treści -

Ponizszy algorytm znajduje optymalne uszeregowanie w przypadku dwóch procesorów i dowolnych czasów wykonywania operacji niepodzielnych. Jest to algorytm o złożoności O(nlogn)

Algorytm Johnsona: Szeregowanie na dwóch procesorach operacji niepodzielnych o dowolnych czasach wykonywania w przepływowym systemie obsługi, w celu minimalizacji C_max.

Powyższy algorytm można także rozszerzyć na specjalny przypadek trzech procesorów, dla którego albo . W tym przypadku czas wykonywania na drugim procesorze nie odgrywa roli, a optymlne uszeregowanie można otrzymać, stosując algorytm Johnsona dla czasów wykonywania (t_1j + t_2j,   t_2j + t_3j)

Przykład zastosowania algorytmu Johnsona dla dwóch procesorów (m = 2) i pięciu zadań (n = 5)

- Spis treści -

Rozpatrujemy problem minimalizacji C_max dla dwóch procesorów. Znajdujemy optymalne rozwiązanie stosując poniższy algorytm o złożoności O(n).

Algorytm: Szeregowanie na dwóch procesorach operacji niepodzielnych w otwartym systemie obsługi, w celu minimalizacji C_max.
Przyjmujemy następujące oznaczenia:

aj = t1j,	A = {Zj: aj ł bj}
bj = t2j,	B = {Zj: aj < bj}

1. Wybierz spośród wszystkich zadań dowolne dwa zadania Z_r oraz Z_l, dla których są spełnione warunki:


Niech A' = A \ {Z_r, Z_l},  B' = B \ {Z_r, Z_l}.

2. Skonstruuj uszeregowanie osobno dla B' È {Z_l} oraz dla A' È {Z_r} w sposób pokazany na poniższym rysunku, przy czym uszeregowanie zadań w zbiorach A' i B' jest dowolne.

 
 

3a. Przypadek 1: T₁ - a_l ł T₂ - b_r.
Połącz obydwa uszeregowania w jedno, w sposób pokazany na poniższym rysunku. Przesuń zadania ze zbioru B' È {Z_l} wykonywane na procesorze P₂, maksymalnie w prawo.

 
 

3b. Przypadek 2: T₁ - a_l < T₂ - b_r.
Połącz obydwa uszeregowania w jedno, w sposób pokazany na poniższym rysunku. Przesuń zadania ze zbioru A' È {Z_r} wykonywane na procesorze P₁, maksymalnie w lewo.

 
 

4a. Przypadek 1: T₁ - a_l ł T₂ - b_r.
Zmień kolejność wykonywania operacji na procesorze P₂ tak ,by operacja O_2r była wykonana jako pierwsza. Jeśli a_r Ł T₂ - b_r to uszeregowanie ma postać przedstawioną na rys.1. Jeśli natomiast a_r > T₂ - b_r to uszeregowanie ma postac jak na rys.2.

  
 

4b. Przypadek 2: T₁ - a_l < T₂ - b_r.
Zmień kolejność wykonywania operacji na procesorze P₁ tak, by operacja O_2l była wykonana na końcu. Jeśli b_l Ł T₁ - a_l to uszeregowanie ma postać przedstawioną na rys.3. Jeśli natomiast b_l > T₁ - a_l to uszeregowanie ma postac jak na rys.4.

  
 

- Spis treści -

Poniższy algorytm można stosować w przypadku dwóch procesorów i zadań składających się z co najwyżej dwóch operacji. Algorytm znajduje optymalne rozwiązanie. Jego złożoność jest O(nlogn)

Przyjmujemy wstępne oznaczenia:
J_i - zbiór zadań składających się tylko z jednej operacji, która ma być wykonana na procesorze P_i (i = 1, 2)
J_hi - zbiór zadań składających się z dwóch operacji, z których pierwsza ma być wykonana na procesorze P_h, a druga na procesorze P_i (hi = 12,21).

  Algorytm: Szeregowanie na dwóch procesorach w ogólnym systemie obsługi zadań składających się z co najwyżej dwóch niepodzielnych operaji, o dowolnych czasach wykonywania,w celu minimalizacji C_max.

- Spis treści -

- Spis treści -