Ogólnie

 

Szeregowanie procesów - w przypadku gdy kilka procesów może być wykonywanych jednocześnie, należy ustalić kolejność ich wykonywania (gdy mamy jeden proces) albo przydział tych procesów do maszyn (gdy mamy wiele procesorów). Czynności prowadzone do ustalania tej kolejności (tego podziału) nazywamy szeregowaniem procesów.

Szeregowanie długoterminowe - wybór procesów, które przejdą do kolejki gotowych; wykonywane rzadko (sekundy, minuty); może być wolne; określa poziom wieloprogramowości
Szeregowanie krótkoterminowe - wybór następnego procesu do wykonania i przydział CPU; wykonywane często (milisekundy); musi być szybkie

Czasami dochodzi szeregowanie średnioterminowe (swapping) czyli czasowe usuwanie zadania w całości z pamięci głównej do pomocniczej

Algorytmy krótkoterminowego szeregowania procesów

 

  • Kolejka prosta (FIFO)
    Procesy są wykonywane w kolejności przybywania. Brak wywłaszczania
    Efekt konwoju: krótkie procesy wstrzymywane przez długie
    Zalety: sprawiedliwy, niski narzut systemowy
    Wady: długi średni czas oczekiwania i wariancja czasu oczekiwania, nieakceptowalny w systemach z podziałem czasu

  • „Najkrótsze zadanie najpierw” (SRTF)
    Procesor przydziela się temu procesowi, który ma najkrótszą najbliższą fazę zapotrzebowania na CPU (gdy równe, to FIFO), z wywłaszczaniem lub bez
    Zalety: optymalny
    Wady: wymaga określenia długości przyszłej fazy CPU (można próbować oszacować np. jako średnią wykładniczą poprzednich faz)

  • Szeregowanie priorytetowe
    Z każdym procesem jest związany priorytet (liczba całkowita)
    CPU przydziela się procesowi z najwyższym priorytetem, FIFO gdy priorytety równe (zwykle mała liczba = wysoki priorytet)
    Z wywłaszczaniem lub bez wywłaszczania SRTF jest strategią szeregowania priorytetowego (priorytet = przewidywana długość następnej fazy CPU)
    Problem: zagłodzenie
    Rozwiązanie: wzrost priorytetu z upływem czasu (proces się „starzeje”)

  • Szeregowanie karuzelowe (Round Robin)
    Każdy proces otrzymuje kwant czasu CPU, zwykle 10 - 100 milisekund. Po upływie kwantu proces zostaje wywłaszczony i idzie na koniec kolejki procesów gotowych. Jeśli w kolejce procesów gotowych jest n procesów, a q to wielkość kwantu, to każdy proces dostaje 1/n czasu procesora w odcinkach długości co najwyżej q. Żaden proces nie czeka na następny kwant dłużej niż (n-1) * q jednostek czasu
    Cechy: zwykle wyższy średni czas obrotu niż dla SRTF, lecz lepszy czas reakcji

  • Kolejki wielopoziomowe
    Kolejka procesów gotowych jest podzielona na odrębne kolejki.
    Przykład:
    • procesy piewszoplanowe (interakcyjne)
    • procesy drugoplanowe (wsadowe)

  • Szeregowanie w systemach czasu rzeczywistego
    • Systemy czasu rzeczywistego ze „sztywnymi” wymaganiami - zadania krytyczne muszą się zakończyć w zadanym czasie
    • Systemy czasu rzeczywistego z „łagodnymi” wymaganiami - zadania krytyczne są obsługiwane z wyższym priorytetem niż pozostałe