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ń.
.