Algorytm harmonogramowania Round Robin z przykładem

Co to jest Round-Robin Scheduling?

Nazwa tego algorytmu pochodzi od zasady round-robin, gdzie każda osoba dostaje równy udział w czymś po kolei. Jest to najstarszy, najprostszy algorytm harmonogramowania, który jest najczęściej używany do wielozadaniowości.

W harmonogramie Round-robin, każde gotowe zadanie działa kolejno tylko w cyklicznej kolejce przez ograniczony wycinek czasu. Ten algorytm oferuje również wykonywanie procesów bez głodu.

W tym samouczku systemu operacyjnego, dowiesz się:

  • Co to jest Round-Robin Scheduling?
  • Charakterystyka harmonogramowania typu Round-Robin
  • Przykład harmonogramowania typu Round-robin
  • Zalety harmonogramowania typu Round-robin
  • Wady harmonogramowania typu Round-robin
  • Najgorszy przypadek opóźnienia

Charakterystyka harmonogramowania typu Round-Robin

Oto ważne cechy harmonogramowania typu Round-Robin:

  • Round robin jest algorytmem typu pre-emptive
  • Procesor jest przesuwany do następnego procesu po ustalonym interwale czasowym, który jest nazywany kwantem czasu/wycinkiem czasu.
  • Proces, który jest uprzedzony jest dodawany na koniec kolejki.
  • Round robin jest modelem hybrydowym, który jest napędzany zegarem
  • Wycinek czasu powinien być minimalny, który jest przypisany do konkretnego zadania, które musi być przetworzone. Jednak może się różnić OS do OS.
  • Jest to algorytm czasu rzeczywistego, który reaguje na zdarzenie w określonym czasie.
  • Round robin jest jednym z najstarszych, najuczciwszych i najprostszych algorytmów.
  • Szerzej stosowana metoda planowania w tradycyjnych OS.

Przykład harmonogramowania typu Round-robin Scheduling

Rozważmy następujące trzy procesy

Kolejka procesów Czas burzy
P1 4
P2 3
P3 5

Krok 1) Wykonanie rozpoczyna się od procesu P1, który ma czas burst time 4. Tutaj każdy proces wykonuje się przez 2 sekundy. P2 i P3 nadal znajdują się w kolejce oczekujących.

Krok 2) W czasie =2, P1 jest dodawany na koniec kolejki, a P2 rozpoczyna wykonywanie

Krok 3) W czasie =4 , P2 jest wypierany i dodawany na koniec kolejki. P3 rozpoczyna wykonywanie.

Krok 4) W chwili time=6 , P3 zostaje wyprzedzony i dodany na koniec kolejki. P1 rozpoczyna wykonywanie.

Krok 5) W chwili time=8 , P1 ma czas rozerwania równy 4. Zakończył wykonywanie. P2 rozpoczyna wykonywanie

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

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

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

Zalety harmonogramowania typu Round-robin

Oto zalety metody harmonogramowania typu Round-robin:

  • Nie boryka się z problemami głodu lub 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 uruchomień, to możesz również założyć najgorszy czas odpowiedzi dla tego samego procesu.
  • Ta metoda szeregowania nie zależy od czasu rozruchu. Dlatego jest łatwo implementowalna w systemie.
  • Gdy proces jest wykonywany przez określony czas, jest on wyczekiwany, a inny proces jest wykonywany przez dany okres czasu.
  • Pozwala systemowi operacyjnemu używać metody przełączania kontekstu do zapisywania stanów wyczekiwanych procesów.
  • Daje najlepszą wydajność pod względem średniego czasu odpowiedzi.

Wady harmonogramowania rundowego

Tutaj są wady/konie używania harmonogramowania rundowego:

  • Jeśli czas krojenia systemu operacyjnego jest niski, wydajność procesora zostanie zmniejszona.
  • Ta metoda spędza więcej czasu na przełączaniu kontekstu
  • Jej wydajność silnie zależy od kwantu czasu.
  • Priorytety nie mogą być ustawione dla procesów.
  • Round-robin scheduling nie daje specjalnego priorytetu dla ważniejszych zadań.
  • Zmniejsza zrozumiałość
  • Niższy kwant czasu powoduje wyższy narzut przełączania kontekstu w systemie.
  • Znalezienie prawidłowego kwantu czasu jest dość trudnym zadaniem w tym systemie.

Worst Case Latency

Ten termin jest używany dla maksymalnego czasu potrzebnego na wykonanie wszystkich zadań.

  • dt = Oznacza czas wykrycia, gdy zadanie jest wprowadzane na listę
  • st = Oznacza czas przełączania z jednego zadania do drugiego
  • et = Oznacza czas wykonania zadania

Formuła:

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

Podsumowanie:

  • Nazwa tego algorytmu pochodzi od zasady round-robin, gdzie każda osoba dostaje równy udział w czymś po kolei.
  • Round robin jest jednym z najstarszych, najuczciwszych i najłatwiejszych algorytmów i szeroko stosowanych metod harmonogramowania w tradycyjnych OS.
  • Round robin jest algorytmem pre-emptive
  • Największą zaletą metody szeregowania round-robin jest to, że jeśli znasz całkowitą liczbę procesów na kolejce uruchomień, to możesz również założyć najgorszy przypadek czasu odpowiedzi dla tego samego procesu.
  • Ta metoda spędza więcej czasu na przełączaniu kontekstu
  • Worst-case latency jest terminem używanym do określenia maksymalnego czasu potrzebnego na wykonanie wszystkich zadań.

.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.