W tym samouczku nauczymy się ważnej koncepcji algorytmów planowania procesów procesora. Ważna nazwa koncepcji to „Kto pierwszy, ten lepszy”. Jest to podstawowy algorytm, którego każdy student musi się nauczyć, aby zrozumieć wszystkie podstawy algorytmów planowania procesów procesora.
Kto pierwszy, ten lepszy toruje drogę do zrozumienia innych algorytmów. Algorytm ten może mieć wiele wad. Ale te wady stworzyły bardzo nowe i wydajne algorytmy. Naszym obowiązkiem jest więc poznać algorytmy planowania procesów procesora, które „kto pierwszy, ten lepszy”.
Ważne skróty
- Procesor - - - > Jednostka centralna
- FCFS - - - > Kto pierwszy, ten lepszy
- W - - - > Czas przybycia
- BT - - - > Czas wybuchu
- WT - - - > Czas oczekiwania
- TAT - - - > Czas zwrotu
- CT - - - > Czas zakończenia
- FIFO - - - > Pierwsze weszło, pierwsze wyszło
Kto pierwszy ten lepszy
Algorytm planowania procesora, kto pierwszy ten lepszy, w skrócie znany jako FCFS, jest pierwszym algorytmem algorytmu planowania procesów procesora. W algorytmie „kto pierwszy, ten lepszy” naszym zadaniem jest umożliwienie wykonania procesu w sposób liniowy.
Oznacza to, że proces, który wejdzie do kolejki gotowych, zostanie wykonany jako pierwszy. To pokazuje, że algorytm „kto pierwszy, ten lepszy” jest zgodny z zasadą „pierwsze weszło, pierwsze wyszło” (FIFO).
Algorytm „kto pierwszy, ten lepszy” można wykonać w sposób z wywłaszczaniem i bez wywłaszczania. Zanim przejdziemy do przykładów, pozwól nam zrozumieć, czym jest podejście z wywłaszczaniem i bez wywłaszczania w planowaniu procesów procesora.
Podejście z wyprzedzeniem
W tym przypadku planowania procesów z wywłaszczaniem, system operacyjny przydziela zasoby procesowi na z góry określony okres czasu. Proces przechodzi ze stanu działania do stanu gotowości lub ze stanu oczekiwania do stanu gotowości podczas alokacji zasobów. To przełączanie ma miejsce, ponieważ procesor może przypisać pierwszeństwo innym procesom i zastąpić aktualnie aktywny proces procesem o wyższym priorytecie.
Podejście bez wykupu
W tym przypadku planowania procesów bez wywłaszczania zasobów nie można wycofać z procesu przed zakończeniem jego działania. Kiedy działający proces zakończy się i przejdzie w stan oczekiwania, następuje przełączenie zasobów.
Efekt konwoju w trybie „kto pierwszy, ten lepszy” (FCFS)
Efekt konwoju to zjawisko występujące w algorytmie planowania o nazwie „Kto pierwszy, ten lepszy” (FCFS). Algorytm planowania „kto pierwszy, ten lepszy” działa w sposób nieprzerywający.
Sposób bez wywłaszczania oznacza, że jeśli proces lub zadanie zostanie rozpoczęte, system operacyjny musi zakończyć swój proces lub zadanie. Dopóki proces lub zadanie nie osiągnie wartości zerowej, nowy lub następny proces lub zadanie nie rozpocznie wykonywania. Definicja harmonogramu niewywłaszczającego w odniesieniu do systemu operacyjnego oznacza, że jednostka centralna (CPU) będzie całkowicie wydzielona do końca procesu lub zadania rozpoczętego jako pierwsza, a nowy proces lub zadanie zostanie wykonane dopiero po zakończeniu starszego procesu lub zadania. stanowisko.
Może wystąpić kilka przypadków, które mogą spowodować, że jednostka centralna (CPU) przydzieli zbyt dużo czasu. Dzieje się tak dlatego, że w przypadku algorytmu planowania „kto pierwszy, ten lepszy”, podejście bez wywłaszczania, procesy lub zadania są wybierane w kolejności seryjnej. Z tego powodu krótsze zadania lub procesy stojące za większymi procesami lub zadaniami zajmują zbyt dużo czasu, aby zakończyć ich wykonanie. Z tego powodu czas oczekiwania, czas realizacji i czas ukończenia są bardzo długie.
Zatem w tym przypadku, gdy pierwszy proces jest duży lub czas jego zakończenia jest zbyt długi, występuje efekt konwoju w algorytmie „kto pierwszy, ten lepszy”.
Załóżmy, że wykonanie dłuższej pracy zajmuje nieskończony czas. Następnie pozostałe procesy muszą czekać przez ten sam nieskończony czas. Ze względu na efekt konwoju wywołany dłuższą pracą, zagłodzenie procesów oczekujących wzrasta bardzo szybko. Jest to największa wada planowania procesów procesora FCFS.
Charakterystyka planowania procesów procesora FCFS
Charakterystyka planowania procesów procesora FCFS to:
- Implementacja jest prosta.
- Nie powoduje żadnych skutków ubocznych podczas stosowania
- Przyjmuje strategię niewywłaszczającą i wywłaszczającą.
- Uruchamia każdą procedurę w kolejności jej otrzymania.
- Czas przybycia stosowany jest jako kryterium wyboru procedur.
Zalety planowania procesów procesora FCFS
Zalety planowania procesów procesora FCFS to:
- Do alokacji procesów wykorzystuje kolejkę First In First Out.
- Proces planowania procesora FCFS jest prosty i łatwy do wdrożenia.
- W przypadku planowania z wyprzedzeniem w sytuacji FCFS nie ma ryzyka głodzenia procesu.
- Ponieważ nie bierze się pod uwagę priorytetu procesu, jest to algorytm sprawiedliwy.
Wady planowania procesów procesora FCFS
Wady planowania procesów procesora FCFS to:
- Algorytm planowania procesora FCFS ma długi czas oczekiwania
- Harmonogramowanie procesora FCFS faworyzuje procesor w stosunku do operacji wejścia lub wyjścia
- W FCFS istnieje szansa wystąpienia efektu konwoju
- Ponieważ FCFS jest tak prosty, często nie jest zbyt skuteczny. Towarzyszą temu wydłużone okresy oczekiwania. Wszystkie pozostałe zamówienia pozostają bezczynne, jeśli procesor jest zajęty przetwarzaniem jednego czasochłonnego zamówienia.
Problemy w algorytmie planowania procesora „kto pierwszy, ten lepszy”.
lista Java do tablicy
Przykład
S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2
Podejście bez wykupu
Rozwiążmy teraz ten problem za pomocą algorytmu planowania o nazwie „Kto pierwszy, ten lepszy” w podejściu bez wywłaszczania.
Wykres Gantta dla powyższego przykładu 1 to:
Czas zwrotu = Czas zakończenia – Czas przybycia
Czas oczekiwania = czas zwrotu – czas wybuchu
Rozwiązanie powyższego pytania Przykład 1
| Tak nie | Identyfikator procesu | Czas przybycia | Czas wybuchu | Czas realizacji | Czas zawrócenia | Czas oczekiwania | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 9 | 9 | 0 |
| 2 | P 2 | B | 1 | 3 | 12 | jedenaście | 8 |
| 3 | P 3 | C | 1 | 2 | 14 | 13 | jedenaście |
| 4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | I | 2 | 3 | dwadzieścia jeden | 19 | 16 |
| 6 | P 6 | F | 3 | 2 | 23 | 20 | 18 |
Średni czas ukończenia wynosi:
Średni CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
Średni CT = 97 / 6
Średni CT = 16,16667
Średni czas oczekiwania wynosi:
Średni WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Średni WT = 66 / 6
Średni WT = 11
Średni czas zwrotu wynosi:
Średni TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
ciąg w Javie
Średni TAT = 89 / 6
Średni TAT = 14,83334
W ten sposób rozwiązuje się FCFS w podejściu bez wywłaszczania.
Teraz zrozumiemy, jak można je rozwiązać w podejściu z wywłaszczaniem
Podejście z wyprzedzeniem
Rozwiążmy teraz ten problem za pomocą algorytmu planowania o nazwie „Kto pierwszy, ten lepszy” w podejściu z wywłaszczaniem.
W podejściu Pre Emptive Approach wyszukujemy najlepszy dostępny proces
Wykres Gantta dla powyższego przykładu 1 to:
| Tak nie | Identyfikator procesu | Czas przybycia | Czas wybuchu | Czas realizacji | Czas zawrócenia | Czas oczekiwania | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | A | 0 | 9 | 23 | 23 | 14 |
| 2 | P 2 | B | 1 | 3 | 8 | 7 | 4 |
| 3 | P 3 | C | 1 | 2 | 3 | 2 | 0 |
| 4 | P 4 | D | 1 | 4 | piętnaście | 14 | 10 |
| 5 | P 5 | I | 2 | 3 | jedenaście | 9 | 7 |
| 6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
| następny → ← poprzednie Aby pozbyć się problemu marnowania sygnałów budzenia, Dijkstra zaproponował podejście polegające na przechowywaniu wszystkich sygnałów budzenia. Dijkstra stwierdza, że zamiast dawać pobudkę bezpośrednio konsumentowi, producent może przechowywać pobudkę w zmiennej. Każdy konsument może go przeczytać, kiedy tylko zajdzie taka potrzeba. Semafor to zmienna przechowująca wszystkie sygnały alarmowe przesyłane od producenta do konsumenta. Jest to zmienna, której odczyt, modyfikacja i aktualizacja odbywa się automatycznie w trybie jądra. Semafora nie można zaimplementować w trybie użytkownika, ponieważ sytuacja wyścigu może zawsze wystąpić, gdy dwa lub więcej procesów próbuje jednocześnie uzyskać dostęp do zmiennej. Do wdrożenia zawsze potrzebne jest wsparcie ze strony systemu operacyjnego. Zgodnie z zapotrzebowaniem sytuacji Semafor można podzielić na dwie kategorie.
Każdy z nich omówimy szczegółowo. |