Harmonogramowanie procesora Algorithms in OperaSystemy tingowe

Co to jest planowanie procesora?

Harmonogramowanie procesora to proces określania, który proces będzie posiadał procesor do wykonania, podczas gdy inny proces jest wstrzymany. Głównym zadaniem harmonogramowania procesora jest zapewnienie, że za każdym razem, gdy procesor pozostaje bezczynny, system operacyjny wybiera co najmniej jeden z procesów dostępnych w kolejce procesów gotowych do wykonania. Proces wyboru jest realizowany przez harmonogram procesora, który wybiera jeden z procesów w pamięci, które są gotowe do wykonania.

Rodzaje planowania procesora

Istnieją dwa rodzaje metod planowania:

Planowanie z wyprzedzeniem

W harmonogramowaniu wyprzedzającym zadania są najczęściej przypisywane zgodnie z ich priorytetami. Czasami ważne jest uruchomienie zadania o wyższym priorytecie przed innym zadaniem o niższym priorytecie, nawet jeśli zadanie o niższym priorytecie jest nadal wykonywane. Zadanie o niższym priorytecie jest utrzymywane przez pewien czas i wznawiane po zakończeniu wykonywania zadania o wyższym priorytecie.

Planowanie bez wywłaszczania

W tym typie metody planowania, procesor jest przydzielany do konkretnego procesu. Proces, który utrzymuje procesor zajętym, zwalnia go, zmieniając kontekst lub kończąc działanie. Jest to jedyna metoda, którą można stosować na różnych platformach sprzętowych, ponieważ nie wymaga ona specjalnego sprzętu (na przykład timera), jak w przypadku planowania z wywłaszczaniem.

Kiedy planowanie jest wyprzedzające, a kiedy niewyprzedzające?

Aby ustalić, czy harmonogramowanie ma charakter wyprzedzający czy też niewyprzedzający, należy wziąć pod uwagę następujące cztery parametry:

1. Proces przechodzi ze stanu uruchomionego do stanu oczekiwania.
2. Konkretny proces przechodzi ze stanu uruchomienia do stanu gotowości.
3. Konkretny proces przechodzi ze stanu oczekiwania do stanu gotowości.
4. Proces kończy swoje wykonywanie i kończy działanie.

Jeśli spełnione są tylko warunki 1 i 4, harmonogramowanie nazywa się niepreemptywnym. Wszystkie pozostałe sytuacje harmonogramowania są preemptywne.

Ważne terminologie planowania procesora

• Czas serii/Czas wykonania: Czas potrzebny procesowi na ukończenie wykonania. Nazywany jest również czasem wykonania.
• Czas przybycia: Moment, w którym proces wchodzi w stan gotowości.
• Czas zakończenia: Moment, w którym proces zostaje zakończony i opuszcza system.
• Wieloprogramowanie: Wiele programów, które mogą być obecne w pamięci w tym samym czasie.
• Oferty pracy: Rodzaj programu, w którym nie ma żadnej interakcji z użytkownikiem.
• Użytkownik: Rodzaj programu wymagającego interakcji z użytkownikiem.
• Proces: Odniesienie używane zarówno w odniesieniu do zadania, jak i użytkownika.
• Cykl serii procesora/IO: Charakteryzuje wykonywanie procesu, które naprzemiennie obejmuje aktywność procesora i wejścia/wyjścia. Czasy pracy procesora są zazwyczaj krótsze niż czasy wejścia/wyjścia.

Kryteria planowania procesora

Algorytm planowania wykorzystania procesora próbuje maksymalizować i minimalizować następujące elementy:

Maksymalizuj

Zużycie procesora: Wykorzystanie procesora to główne zadanie, w którym system operacyjny musi zapewnić jego maksymalne wykorzystanie. Może ono wynosić od 0 do 100 procent. Jednak w przypadku systemu operacyjnego czasu rzeczywistego (RTOS) może ono wynosić od 40 procent w systemie niskiego poziomu do 90 procent w systemie wysokiego poziomu.

Wydajność: Liczba procesów, które kończą swoje wykonywanie w jednostce czasu, nazywana jest przepustowością. Zatem, gdy procesor jest zajęty wykonywaniem procesu, wykonywana jest praca, a praca wykonana w jednostce czasu nazywana jest przepustowością.

Zminimalizować

Czas oczekiwania: Czas oczekiwania to ilość czasu, jaką konkretny proces musi spędzić w kolejce procesów gotowych do użycia.

Czas odpowiedzi: Jest to czas od momentu wysłania wniosku do momentu otrzymania pierwszej odpowiedzi.

Czas realizacji: Czas realizacji to czas potrzebny na wykonanie określonego procesu. Jest to całkowity czas oczekiwania na dostęp do pamięci, oczekiwania w kolejce i wykonania na procesorze. Okres między momentem przesłania procesu a momentem jego zakończenia to czas realizacji.

Timer interwałowy

Przerwanie timera jest metodą ściśle powiązaną z wywłaszczaniem. Kiedy określony proces otrzyma przydział procesora, licznik czasu może zostać ustawiony na określony interwał. Zarówno przerwanie timera, jak i wywłaszczenie wymuszają na procesie zwrócenie procesora przed zakończeniem jego działania.

Większość wieloprogramowych systemów operacyjnych korzysta z jakiejś formy licznika czasu, aby zapobiec blokowaniu systemu przez proces na zawsze.

Co to jest dyspozytor?

Dyspozytor to moduł, który zapewnia procesowi kontrolę nad procesorem. Dyspozytor powinien być szybki, aby mógł działać przy każdej zmianie kontekstu. Opóźnienie dyspozytora to czas potrzebny harmonogramowi procesora na zatrzymanie jednego procesu i uruchomienie innego.

Funkcje wykonywane przez dyspozytora:

• Przełączanie kontekstu.
• Przełączanie do trybu użytkownika.
• Przejście do właściwej lokalizacji w nowo załadowanym programie.

Rodzaje planowania procesora Algorithms

Istnieje głównie sześć rodzajów algorytmy planowania procesów:

1. Kto pierwszy, ten lepszy (FCFS)
2. Harmonogramowanie według najkrótszego zadania (SJF).
3. Najkrótszy pozostały czas
4. Planowanie priorytetowe
5. Planowanie okrężne
6. Wielopoziomowe planowanie kolejek

Scheduling Algorithms

Kto pierwszy ten lepszy

FCFS oznacza Kto pierwszy ten lepszyJest to najłatwiejszy i najprostszy algorytm planowania przydziału procesora. W tym typie algorytmu proces, który żąda przydziału procesora, otrzymuje go jako pierwszy. Tą metodą planowania można zarządzać za pomocą kolejki FIFO.

Gdy proces wchodzi do kolejki gotowych procesów, jego blok PCB (Process Control Block) jest połączony z końcem kolejki. Zatem, gdy procesor staje się wolny, powinien zostać przypisany do procesu na początku kolejki.

Charakterystyka metody FCFS

• Jest to algorytm planowania niewywłaszczający.
• Zadania są zawsze wykonywane na zasadzie „kto pierwszy, ten lepszy”.
• Jest łatwy do wdrożenia i użytkowania.
• Jednak ta metoda ma słabą wydajność, a ogólny czas oczekiwania jest dość długi.

Najkrótszy pozostały czas

Pełna nazwa metody SRT to Shortest Remaining Time (najkrótszy pozostały czas). Jest ona również znana jako planowanie wyprzedzające SJF (Shortest Remaining Time). W tej metodzie proces jest przydzielany do zadania najbliższego ukończenia. Zapobiega to wstrzymywaniu ukończenia starszego procesu przez nowszy proces w stanie gotowości.

Charakterystyka metody harmonogramowania SRT

• Metodę tę stosuje się głównie w środowiskach wsadowych, w których konieczne jest dawanie pierwszeństwa zadaniom krótkim.
• Nie jest to idealna metoda implementacji w systemie współdzielonym, w którym wymagany czas procesora nie jest znany.
• Każdy proces jest powiązany z długością kolejnego obciążenia procesora, więc system operacyjny wykorzystuje te długości, aby zaplanować proces w możliwie najkrótszym czasie.

Planowanie oparte na priorytetach

Planowanie priorytetowe to metoda planowania procesów oparta na priorytetach. W tej metodzie planista wybiera zadania do realizacji według ich priorytetu.

Harmonogramowanie priorytetowe pomaga również systemowi operacyjnemu w przydzielaniu zadań o wyższym priorytecie. Procesy o wyższym priorytecie są wykonywane jako pierwsze, natomiast zadania o równym priorytecie są wykonywane w trybie „każdy z każdym” lub metodą FCFS. Priorytet można ustalić na podstawie zapotrzebowania na pamięć, czasu i innych czynników.

Harmonogram okrężny

Round robin to jeden z najstarszych i najprostszych algorytmów harmonogramowania. Nazwa tego algorytmu pochodzi od zasady „każdy z każdym”, zgodnie z którą każdy otrzymuje po kolei równy udział w czymś. Jest on najczęściej wykorzystywany do harmonogramowania w systemach wielozadaniowych. Metoda ta pomaga osiągnąć wykonywanie procesów bez niedoboru mocy obliczeniowej.

Charakterystyka planowania okrężnego

• Round robin to hybrydowy model, którego działanie opiera się na zegarze.
• Przedział czasowy przeznaczony na wykonanie konkretnego zadania powinien być minimalny. Może się on jednak różnić w zależności od procesu.
• Zachowuje się jak system podziału czasu, który reaguje na każdy proces w ramach określonego limitu czasu.

Najpierw najkrótsza praca

SJF (Shortest Job First) to algorytm szeregowania, w którym proces o najkrótszym czasie wykonania jest wybierany do wykonania jako następny. Ta metoda szeregowania może być wywłaszczająca lub niewywłaszczająca. Znacznie skraca średni czas oczekiwania na wykonanie innych procesów.

Charakterystyka harmonogramowania SJF

• Każde zadanie ma przypisaną jednostkę czasu na jego wykonanie.
• W tej metodzie, jeśli procesor jest dostępny, jako pierwszy wykonywany jest kolejny proces lub zadanie z najkrótszym czasem wykonania.
• Jest ona wdrażana przy użyciu polityki nieprewencyjnej.
• Algorytm ten jest przydatny w przypadku przetwarzania wsadowego, w którym oczekiwanie na zakończenie zadań nie jest krytyczne.
• Poprawia wydajność pracy poprzez wykonywanie w pierwszej kolejności zadań krótszych, których czas realizacji jest zazwyczaj krótszy.

Planowanie kolejek wielopoziomowych

Ten algorytm rozdziela kolejkę gotowych procesów na kilka osobnych kolejek. W tej metodzie procesy są przypisywane do kolejki na podstawie określonej właściwości procesu, takiej jak priorytet procesu, rozmiar pamięci itd.

Nie jest to jednak niezależny algorytm planowania, gdyż w celu zaplanowania zadań wymaga użycia innych typów algorytmów.

Charakterystyka harmonogramowania kolejek wielopoziomowych

• Dla procesów o wspólnych cechach należy utrzymywać wiele kolejek.
• Każda kolejka może mieć swój własny, oddzielny algorytm planowania.
• Każdej kolejce przypisane są priorytety.

Cel algorytmu harmonogramowania

Oto powody stosowania algorytmu planowania:

• Procesor wykorzystuje planowanie w celu poprawy swojej wydajności.
• Pomaga przydzielać zasoby pomiędzy konkurującymi procesami.
• Maksymalne wykorzystanie procesora można uzyskać stosując multiprogramowanie.
• Procesy, które mają zostać wykonane, są przechowywane w kolejce procesów gotowych.

FAQ