Algorytm RR

Algorytm RR (Round‑Robin) jest jedną z podstawowych strategii planowania stosowaną w systemach operacyjnych do przydzielania czasu procesorowi w środowiskach wielozadaniowych. Nazwa pochodzi od angielskiego terminu „round‑robin”, co dosłownie oznacza „krążenie w kręgu”. Algorytm ten charakteryzuje się prostą zasadą: każdy proces znajdujący się w kolejce gotowej do wykonania otrzymuje określony, stały fragment czasu zwany kwantem czasu. Po upłynięciu tego czasu proces jest przenoszony na koniec kolejki, a procesor przechodzi do następnego zadania.

Podstawowe pojęcia

Proces – jednostka wykonawcza programu, którą system operacyjny zarządza jako oddzielny byt.
Kolejka gotowych procesów – struktura danych (zwykle kolejka FIFO), w której przechowywane są procesy oczekujące na przydział CPU.
Kwant czasu – maksymalny, nieprzekraczalny okres, w którym proces może korzystać z procesora przed jego przełączeniem.
Przełącznik kontekstu – operacja polegająca na zapisaniu stanu bieżącego procesu i przywróceniu stanu kolejnego.

Działanie algorytmu

Wszystkie procesy gotowe do wykonania umieszcza się w kolejce w kolejności ich przybycia (FIFO).
Procesor przydziela pierwszy proces z kolejki i pozwala mu wykonywać się przez określony kwant czasu.
Po upływie kwantu:
- jeżeli proces zakończył się przed upływem kwantu, usuwa się go z kolejki.
- jeżeli proces nie zakończył się, zostaje przerwany, a jego stan zostaje zapisany (przełącznik kontekstu) i proces zostaje umieszczony na końcu kolejki.
Powtarza się krok 2, aż kolejka stanie się pusta.

Zalety i wady

Aspekt	Zalety	Wady
Prostota implementacji	Łatwy do zaimplementowania w jądrze systemu.	Brak adaptacji do różnic w wymaganiach procesów.
Sprawiedliwość	Każdy proces otrzymuje równy udział czasu CPU.	Możliwe zwiększenie liczby przełączeń kontekstu.
Reakcja na interaktywne zadania	Krótki kwant zapewnia szybkie reagowanie na procesy interaktywne.	Jeżeli kwant jest zbyt krótki, wydajność spada z powodu narzutu.
Zastosowanie w czasie rzeczywistym	Możliwość przewidywalnego przydziału czasu.	Nie spełnia wymagań twardego czasu rzeczywistego (wymaga dodatkowych mechanizmów).

Dobór kwantu czasu

Optymalny rozmiar kwantu czasu jest kluczowy dla wydajności algorytmu. Zbyt mały kwant powoduje nadmierną liczbę przełączeń kontekstu, co zwiększa narzut systemowy. Zbyt duży kwant natomiast przypomina algorytm FIFO i może prowadzić do starvation procesów o krótkim czasie wykonywania.

Porównanie z innymi algorytmami planowania

W przeciwieństwie do FIFO, w którym procesy są wykonywane w kolejności przybycia bez ograniczenia czasu, algorytm RR zapewnia równomierny podział zasobów. W porównaniu z Shortest Job First (SJF), RR nie wymaga znajomości czasu trwania procesu, co czyni go bardziej uniwersalnym, choć mniej efektywnym pod względem średniego czasu zakończenia.

Zastosowania praktyczne

Algorytm Round‑Robin jest szeroko stosowany w:

systemach operacyjnych typu Unix oraz Linux, w module planowania procesora;
serwerach aplikacji, które obsługują wiele równoległych żądań;
routerach i przełącznikach sieciowych do zarządzania kolejkami pakietów.

Implementacje w popularnych systemach

W jądrze Linux podstawowy algorytm RR został rozszerzony o hierarchiczne kolejki czasu rzeczywistego, co pozwala na stosowanie różnych rozmiarów kwantu dla różnych klas procesów.

Podsumowanie

Algorytm RR pozostaje jednym z filarów planowania procesów ze względu na swoją prostotę oraz zdolność do zapewnienia równego podziału czasu CPU w środowiskach wielozadaniowych. Jego skuteczność zależy jednak od właściwego dobrania kwantu czasu oraz ewentualnego połączenia z innymi strategiami, aby zminimalizować narzut i uniknąć sytuacji, w których niektóre procesy są zaniedbywane.

Przyszłe kierunki badań

W literaturze naukowej badane są hybrydowe podejścia łączące RR z adaptacyjnymi mechanizmami, które dynamicznie zmieniają długość kwantu w zależności od obciążenia systemu, profilu procesów i wymagań czasowych. Takie rozwiązania mają na celu zwiększenie wydajności systemu przy zachowaniu prostoty klasycznego algorytmu RR.

Źródła: Podręczniki z zakresu systemów operacyjnych, materiały wykładów akademickich oraz dokumentacje rdzeni systemów Linux i Unix.