Algorytm planowania okrężnego z przykładem

Co to jest planowanie okrężne?

Nazwa tego algorytmu pochodzi od zasady round-robin, w której każda osoba otrzymuje po kolei równy udział w czymś. Jest to najstarszy i najprostszy algorytm planowania, używany głównie w przypadku wielozadaniowości.

W harmonogramowaniu typu round-robin każde gotowe zadanie jest uruchamiane kolejno w kolejce cyklicznej przez ograniczony czas. Algorytm ten oferuje również wykonywanie procesów bez ryzyka głodowania.

Charakterystyka planowania okrężnego

Oto ważne cechy planowania okrężnego:

• Round robin jest algorytmem wyprzedzającym.
• Procesor przełącza się na następny proces po ustalonym odstępie czasu, który nazywa się kwantem czasu/wycinkiem czasu.
• Proces, który został wywłaszczony, jest dodawany na koniec kolejki.
• Round robin to model hybrydowy, którego działanie opiera się na zegarze.
• Przedział czasowy powinien być minimalny i przypisany do konkretnego zadania, które należy wykonać. Może się on jednak różnić w zależności od systemu operacyjnego.
• Jest to algorytm działający w czasie rzeczywistym, który reaguje na zdarzenia w określonym przedziale czasowym.
• Metoda kołowa jest jednym z najstarszych, najsprawiedliwszych i najłatwiejszych algorytmów.
• Jest to powszechnie stosowana metoda planowania w tradycyjnych systemach operacyjnych.

Przykład planowania okrężnego

Rozważmy następujące trzy procesy:

Krok 1) Wykonywanie rozpoczyna się od procesu P1, którego czas trwania serii wynosi 4. Tutaj każdy proces jest wykonywany przez 2 sekundy. P2 i P3 nadal czekają w kolejce.

Krok 2) W chwili = 2 P1 zostaje dodany na koniec kolejki, a wykonywanie P2 rozpoczyna się.

Krok 3) W momencie = 4 P2 zostaje wywłaszczony i dodany na koniec kolejki. Rozpoczyna się wykonywanie P3.

Krok 4) W momencie = 6 P3 zostaje wywłaszczony i dodany na koniec kolejki. Rozpoczyna się wykonywanie P1.

Krok 5) W chwili = 8 P1 ma czas trwania serii równy 4. Zakończono wykonywanie. P2 rozpoczyna wykonywanie.

Krok 6) P2 ma czas burst równy 3. Wykonał już 2 interwały. W czasie = 9, P2 kończy wykonywanie. Następnie P3 rozpoczyna wykonywanie, aż do jego zakończenia.

Krok 7) Obliczmy średni czas oczekiwania dla powyższego przykładu.

Wait time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

Zalety harmonogramowania typu round-robin

Oto zalety i korzyści metody harmonogramowania Round-robin:

• Nie dotyczy go problem głodu ani efektu konwoju.
• Wszystkie zadania otrzymują sprawiedliwy przydział procesora.
• Zajmuje się wszystkimi procesami bez żadnego priorytetu.
• Jeśli znasz całkowitą liczbę procesów w kolejce wykonywania, możesz także założyć najgorszy czas odpowiedzi dla tego samego procesu.
• Ta metoda harmonogramowania nie zależy od czasu burst. Dlatego jest łatwa do wdrożenia w systemie.
• Gdy proces jest wykonywany przez określony czas, proces jest wywłaszczany i przez ten określony okres wykonywany jest inny proces.
• Umożliwia systemowi operacyjnemu wykorzystanie metody przełączania kontekstu w celu zapisania stanów procesów przejętych.
• Zapewnia najlepszą wydajność pod względem średniego czasu reakcji.

Wady planowania okrężnego

Oto wady/przeciwskazania związane z wykorzystaniem harmonogramu Round-robin:

• Jeśli czas podziału systemu operacyjnego jest krótki, wydajność procesora ulegnie zmniejszeniu.
• Ta metoda poświęca więcej czasu na przełączanie kontekstu.
• Jego działanie w dużym stopniu zależy od kwantu czasu.
• Nie można ustalać priorytetów dla procesów.
• Harmonogramowanie typu round-robin nie nadaje specjalnego priorytetu ważniejszym zadaniom.
• Zmniejsza zrozumienie.
• Niższy kwant czasu skutkuje większym obciążeniem systemu związanym z przełączaniem kontekstu.
• Znalezienie właściwego kwantowego czasu w tym systemie jest zadaniem wyjątkowo trudnym.

Najgorsze opóźnienie w przypadku

Terminem tym określa się maksymalny czas realizacji wszystkich zadań.

• dt = Oznacza czas wykrycia, gdy zadanie zostanie umieszczone na liście
• st = oznacza czas przełączania z jednego zadania na drugie
• et = oznacza czas wykonania zadania

Wzór:

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR
tISR = sum of all execution times

FAQ