Harmonogramowanie procesora Algorithms in OperaSystemy tingowe

Rodzaje planowania procesora

Oto dwa rodzaje metod planowania:

Planowanie z wyprzedzeniem

W planowaniu wyprzedzającym zadania są przeważnie przydzielane według priorytetów. Czasami ważne jest, aby uruchomić zadanie o wyższym priorytecie przed innym zadaniem o niższym priorytecie, nawet jeśli zadanie o niższym priorytecie jest nadal uruchomione. Zadanie o niższym priorytecie jest wstrzymywane przez pewien czas i zostaje wznowione po zakończeniu wykonywania zadania o wyższym priorytecie.

Planowanie bez wywłaszczania

W tego typu metodzie planowania procesor jest przydzielany konkretnemu procesowi. Proces, który utrzymuje procesor zajęty, zwolni procesor poprzez zmianę kontekstu lub zakończenie. Jest to jedyna metoda, którą można zastosować dla różnych platform sprzętowych. Dzieje się tak dlatego, że nie wymaga specjalnego sprzętu (na przykład timera), takiego jak planowanie z wywłaszczaniem.

Kiedy planowanie jest z wywłaszczaniem czy z wywłaszczaniem?

Aby określić, czy planowanie ma charakter z wywłaszczaniem, czy z wywłaszczaniem, 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 uruchomionego do stanu gotowości.
3. Konkretny proces przechodzi ze stanu oczekiwania do stanu gotowości.
4. Proces zakończył swoje wykonywanie i został zakończony.

Mają zastosowanie wyłącznie warunki 1 i 4, planowanie nazywa się niewywłaszczającym.

Wszystkie inne harmonogramy mają charakter wywłaszczający.

Ważne terminologie dotyczące planowania procesora

• Czas serii/Czas wykonania: Jest to czas wymagany przez proces do zakończenia wykonywania. Nazywa się to także czasem działania.
• Czas przybycia: kiedy proces wejdzie w stan gotowości
• Czas zakończenia: po zakończeniu procesu i wyjściu z systemu
• Wieloprogramowanie: Wiele programów, które mogą być jednocześnie obecne w pamięci.
• Oferty pracy: Jest to rodzaj programu bez jakiejkolwiek interakcji użytkownika.
• Użytkownik: Jest to rodzaj programu posiadającego interakcję z użytkownikiem.
• Proces: Jest to odniesienie używane zarówno dla zadania, jak i użytkownika.
• Cykl serii procesora/IO: Charakteryzuje wykonanie procesu, które naprzemiennie obejmuje aktywność procesora i operacji we/wy. Czasy procesora są zwykle krótsze niż czas operacji we/wy.

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 upewnić się, że procesor pozostaje tak zajęty, jak to możliwe. Może się wahać od 0 do 100 procent. Jednak w przypadku RTOS może się wahać od 40 procent dla systemu niskiego poziomu do 90 procent dla systemu wysokiego poziomu.

Wydajność: Znana jest liczba procesów, które kończą swoje wykonanie w jednostce czasu. Przepustowość. Tak więc, gdy procesor jest zajęty wykonywaniem procesu, w tym czasie wykonywana jest praca, a praca wykonana w jednostce czasu nazywana jest przepustowością.

Zminimalizować

Czas oczekiwania: Czas oczekiwania to ilość, jaką konkretny proces musi poczekać w kolejce gotowych.

Czas odpowiedzi: Jest to czas, w jakim wniosek został złożony do momentu otrzymania pierwszej odpowiedzi.

Czas realizacji: Czas realizacji to czas potrzebny na wykonanie określonego procesu. Jest to obliczenie całkowitego czasu spędzonego na oczekiwaniu na wejście do pamięci, oczekiwaniu w kolejce i wykonywaniu na procesorze. Okres od chwili przekazania procesu do chwili 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.

Co to jest dyspozytor?

Jest to moduł zapewniający kontrolę procesora nad procesem. Dispatcher powinien być szybki, aby mógł działać przy każdym przełączeniu kontekstu. Opóźnienie wysyłki to ilość czasu potrzebna programowi planującemu procesora do zatrzymania jednego procesu i uruchomienia innego.

Funkcje pełnione przez Dyspozytora:

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

Rodzaje algorytmów planowania procesora

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

Kto pierwszy ten lepszy

„Kto pierwszy, ten lepszy” to pełna forma FCFS. Jest to najłatwiejszy i najprostszy algorytm planowania procesora. W tego typu algorytmie proces żądający procesora najpierw otrzymuje przydział procesora. Tą metodą planowania można zarządzać za pomocą kolejki FIFO.

Gdy proces trafia do kolejki procesów gotowych, jego PCB (blok sterowania procesem) zostaje połączona z końcem kolejki. Zatem gdy procesor stanie się wolny, należy go przypisać do procesu na początku kolejki.

Charakterystyka metody FCFS

• Oferuje algorytm planowania z wywłaszczaniem i z wywłaszczaniem.
• 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 forma SRT to Najkrótszy pozostały czas. Nazywa się to również planowaniem wywłaszczającym SJF. W tej metodzie proces zostanie przypisany do zadania, które jest najbliżej jego zakończenia. Ta metoda zapobiega wstrzymywaniu ukończenia starszego procesu przez nowszy proces w stanie gotowości.

Charakterystyka metody szeregowania SRT

• Metodę tę stosuje się najczęściej w środowiskach wsadowych, w których preferowane są krótkie zadania.
• Nie jest to idealna metoda wdrożenia go we współdzielonym systemie, w którym wymagany czas procesora jest nieznany.
• Powiąż z każdym procesem długość jego następnego impulsu procesora. Tak więc system operacyjny używa tych długości, co pomaga zaplanować proces z najkrótszym możliwym czasem.

Planowanie oparte na priorytetach

Planowanie priorytetowe to metoda planowania procesów w oparciu o priorytety. W tej metodzie osoba planująca wybiera zadania do wykonania według priorytetu.

Planowanie priorytetów pomaga również systemowi operacyjnemu w uwzględnianiu przypisań priorytetów. W pierwszej kolejności powinny być realizowane procesy o wyższym priorytecie, natomiast zadania o jednakowych priorytetach realizowane są metodą okrężną lub FCFS. O priorytecie można decydować na podstawie wymagań dotyczących pamięci, wymagań czasowych itp.

Harmonogram okrężny

Round robin to najstarszy, najprostszy algorytm harmonogramowania. Nazwa tego algorytmu pochodzi od zasady round robin, w której każda osoba otrzymuje po kolei równą część czegoś. Jest on najczęściej używany do algorytmów harmonogramowania w wielozadaniowości. Ta metoda algorytmu pomaga w wykonywaniu procesów bez głodowania.

Charakterystyka planowania okrężnego

• Round Robin to model hybrydowy napędzany zegarem
• Przedział czasu powinien być minimalny, jaki jest przypisany do konkretnego zadania do realizacji. Może się jednak różnić w przypadku różnych procesów.
• Jest to system czasu rzeczywistego, który reaguje na zdarzenie w określonym terminie.

Najpierw najkrótsza praca

SJF to pełna postać (najpierw najkrótsze zadanie) to algorytm planowania, w którym do wykonania powinien zostać wybrany proces o najkrótszym czasie wykonania. Ta metoda planowania może być z wywłaszczaniem lub bez wywłaszczania. Znacząco skraca średni czas oczekiwania na wykonanie innych procesów.

Charakterystyka harmonogramowania SJF

• Jest powiązany z każdym zadaniem jako jednostka czasu do wykonania.
• W tej metodzie, gdy procesor jest dostępny, jako pierwszy zostanie wykonany następny proces lub zadanie o najkrótszym czasie zakończenia.
• Jest wdrażany w oparciu o politykę bez wywłaszczania.
• Ta metoda algorytmiczna jest przydatna w przypadku przetwarzania wsadowego, gdzie oczekiwanie na zakończenie zadań nie jest krytyczne.
• Poprawia wydajność zadań, oferując krótsze zadania, które należy wykonać w pierwszej kolejności i które w większości mają krótszy czas realizacji.

Planowanie kolejek wielopoziomowych

Algorytm ten dzieli gotową kolejkę na różne oddzielne kolejki. W tej metodzie procesy są przypisywane do kolejki na podstawie określonej właściwości procesu, takiej jak priorytet procesu, rozmiar pamięci itp.

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

Charakterystyka planowania kolejek wielopoziomowych

• Dla procesów o pewnych cechach należy utrzymywać wiele kolejek.
• Każda kolejka może mieć swój własny algorytm planowania.
• Dla każdej kolejki nadawane są priorytety.

Cel algorytmu planowania

Oto powody stosowania algorytmu planowania:

• Procesor wykorzystuje planowanie w celu poprawy swojej wydajności.
• Pomaga w alokacji zasobów pomiędzy konkurującymi procesami.
• Maksymalne wykorzystanie procesora można uzyskać dzięki programowaniu wieloprogramowemu.
• Procesy do wykonania znajdują się w gotowej kolejce.

Podsumowanie

• Planowanie procesora to proces określania, który proces będzie właścicielem procesora do wykonania, podczas gdy inny proces jest wstrzymany.
• W planowaniu wyprzedzającym zadania są przeważnie przydzielane według priorytetów.
• W metodzie planowania bez wywłaszczania procesor został przydzielony do konkretnego procesu.
• Czas serii to czas wymagany do zakończenia wykonywania procesu. Nazywa się to także czasem działania.
• Wykorzystanie procesora to najważniejsze zadanie, przy którym system operacyjny musi zadbać o to, aby procesor był maksymalnie obciążony.
• Znana jest liczba procesów, które kończą swoje wykonanie w jednostce czasu. Przepustowość.
• Czas oczekiwania to ilość, jaką konkretny proces musi poczekać w kolejce gotowych.
• Jest to czas, w jakim wniosek został złożony do momentu otrzymania pierwszej odpowiedzi.
• Czas realizacji to czas potrzebny na wykonanie określonego procesu.
• Przerwanie timera jest metodą ściśle powiązaną z wywłaszczaniem.
• Dyspozytor to moduł zapewniający kontrolę nad procesorem procesu.
• Sześć typów algorytmów planowania procesów to: algorytm „pierwszy przyszedł, pierwszy obsłużony” (FCFS), 2) algorytm „najpierw najkrótsze zadanie” (SJF), 3) algorytm „najkrótszy pozostały czas”, 4) algorytm priorytetowy, 5) algorytm round robin, 6) algorytm kolejkowania wielopoziomowego.
• W Metoda „kto pierwszy, ten lepszy”., proces żądający procesora najpierw otrzymuje przydział procesora.
• W Najkrótszym pozostałym czasie proces zostanie przydzielony do zadania najbliższego jego ukończenia.
• W harmonogramie priorytetowym osoba planująca wybiera zadania do wykonania zgodnie z priorytetem.
• Harmonogram okrężny działa na zasadzie, że każda osoba otrzymuje po kolei równy udział w czymś.
• W pierwszej kolejności należy wybrać najkrótsze zadanie, a następnie wybrać najkrótszy czas wykonania.
• Metoda planowania wielopoziomowego dzieli gotową kolejkę na różne oddzielne kolejki. W tej metodzie procesy są przypisywane do kolejki na podstawie określonej właściwości.
• Procesor wykorzystuje planowanie w celu poprawy swojej wydajności.