Co to jest planowanie najkrótszej pracy w pierwszej kolejności?
Shortest Job First (SJF) to algorytm, w którym do następnego wykonania wybierany jest proces o najkrótszym czasie wykonania. Ta metoda planowania może być wywłaszczająca lub nieprzedmiotowa. Znacząco skraca średni czas oczekiwania na inne procesy oczekujące na wykonanie. Pełna forma SJF to Shortest Job First.
Zasadniczo istnieją dwa rodzaje metod SJF:
- SJF bez wywłaszczania
- Zapobiegawcze SJF
W tym samouczku dotyczącym systemu operacyjnego dowiesz się:
- Co to jest planowanie najkrótszej pracy w pierwszej kolejności?
- Charakterystyka harmonogramowania SJF
- SJF bez wywłaszczania
- Zapobiegawcze SJF
- Zalety SJF
- Wady / wady SJF
Charakterystyka harmonogramowania SJF
- Jest powiązany z każdym zadaniem jako jednostka czasu do wykonania.
- Ta metoda algorytmu jest pomocna w przypadku przetwarzania wsadowego, w którym oczekiwanie na zakończenie zadań nie jest krytyczne.
- Może poprawić przepustowość procesu, upewniając się, że krótsze zadania są wykonywane jako pierwsze, stąd prawdopodobnie krótki czas realizacji.
- Poprawia wydajność pracy, oferując krótsze prace, które powinny być wykonywane jako pierwsze, które zazwyczaj mają krótszy czas realizacji.
SJF bez wywłaszczania
W planowaniu bez wywłaszczania, gdy cykl procesora zostanie przydzielony do procesu, proces wstrzymuje go, aż osiągnie stan oczekiwania lub zostanie zakończony.
Rozważ następujące pięć procesów, z których każdy ma swój własny, niepowtarzalny czas wybuchu i czas przybycia.
| Kolejka procesów | Czas wybuchu | Czas przybycia |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 0) W czasie = 0, P4 przybywa i rozpoczyna wykonywanie.
Krok 1) W czasie = 1 nadejdzie proces P3. Ale P4 nadal potrzebuje 2 jednostek wykonawczych do ukończenia. Będzie kontynuowana.
Krok 2) W czasie = 2 przychodzi proces P1 i jest dodawany do kolejki oczekiwania. P4 będzie kontynuował wykonywanie.
Krok 3) W czasie = 3 proces P4 zakończy wykonywanie. Porównuje się czas rozerwania P3 i P1. Proces P1 jest wykonywany, ponieważ jego czas burst jest krótszy w porównaniu do P3.
Krok 4) W czasie = 4 przychodzi proces P5 i jest dodawany do kolejki oczekiwania. P1 będzie kontynuował wykonywanie.
Krok 5) W czasie = 5 przychodzi proces P2 i jest dodawany do kolejki oczekiwania. P1 będzie kontynuował wykonywanie.
Krok 6) W czasie = 9 proces P1 zakończy wykonywanie. Porównuje się czas rozerwania P3, P5 i P2. Proces P2 jest wykonywany, ponieważ jego czas burst jest najniższy.
Krok 7) W czasie = 10 P2 wykonuje się, a P3 i P5 znajdują się w kolejce oczekiwania.
Krok 8) W czasie = 11 proces P2 zakończy wykonywanie. Porównuje się czas rozerwania P3 i P5. Proces P5 jest wykonywany, ponieważ jego czas burst jest krótszy.
Krok 9) W czasie = 15 proces P5 zakończy wykonywanie.
Krok 10) W czasie = 23 proces P3 zakończy wykonywanie.
Krok 11) Obliczmy średni czas oczekiwania dla powyższego przykładu.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Zapobiegawcze SJF
W Preemptive SJF Scheduling zadania są umieszczane w kolejce gotowości, gdy nadejdą. Rozpoczyna się proces z najkrótszym czasem serii. Jeśli nadejdzie proces z nawet krótszym czasem serii, bieżący proces jest usuwany lub wykluczany z wykonania, a krótsze zadanie otrzymuje cykl procesora.
Rozważ następujące pięć procesów:
| Kolejka procesów | Czas wybuchu | Czas przybycia |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 0) W czasie = 0, P4 przybywa i rozpoczyna wykonywanie.
| Kolejka procesów | Czas wybuchu | Czas przybycia |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 1) W czasie = 1 nadejdzie proces P3. Ale P4 ma krótszy czas wybuchu. Będzie kontynuowana.
Krok 2) W czasie = 2 nadejdzie proces P1 z czasem impulsu = 6. Czas impulsu jest dłuższy niż z P4. W związku z tym P4 będzie kontynuował wykonywanie.
Krok 3) W czasie = 3 proces P4 zakończy wykonywanie. Porównuje się czas rozerwania P3 i P1. Proces P1 jest wykonywany, ponieważ jego czas burst jest krótszy.
Krok 4) W czasie = 4 nadejdzie proces P5. Porównuje się czas rozerwania P3, P5 i P1. Proces P5 jest wykonywany, ponieważ jego czas burst jest najkrótszy. Proces P1 jest wywłaszczony.
| Kolejka procesów | Czas wybuchu | Czas przybycia |
| P1 | Pozostało 5 z 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Krok 5) W czasie = 5 nadejdzie proces P2. Porównuje się czas rozerwania P1, P2, P3 i P5. Proces P2 jest wykonywany, ponieważ jego czas burst jest najmniejszy. Proces P5 jest wywłaszczony.
| Kolejka procesów | Czas wybuchu | Czas przybycia |
| P1 | Pozostało 5 z 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Pozostało 3 z 4 | 4 |
Krok 6) W czasie = 6 wykonywany jest P2.
Krok 7) W czasie = 7 P2 kończy wykonywanie. Porównuje się czas rozerwania P1, P3 i P5. Proces P5 jest wykonywany, ponieważ jego czas burst jest krótszy.
| Kolejka procesów | Czas wybuchu | Czas przybycia |
| P1 | Pozostało 5 z 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Pozostało 3 z 4 | 4 |
Krok 8) W czasie = 10, P5 zakończy wykonywanie. Porównuje się czas rozerwania P1 i P3. Proces P1 jest wykonywany, ponieważ jego czas burst jest krótszy.
Krok 9) W czasie = 15, P1 kończy wykonywanie. P3 to jedyny proces, jaki pozostał. Rozpocznie się wykonywanie.
Krok 10) W czasie = 23, P3 kończy wykonywanie.
Krok 11) Obliczmy średni czas oczekiwania dla powyższego przykładu.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Zalety SJF
Oto zalety / zalety korzystania z metody SJF:
- SJF jest często używany do planowania długoterminowego.
- Zmniejsza średni czas oczekiwania na algorytm FIFO (First in First Out).
- Metoda SJF daje najniższy średni czas oczekiwania na określony zestaw procesów.
- Jest odpowiedni do zadań uruchamianych wsadowo, w przypadku których czasy wykonywania są znane z góry.
- W przypadku systemu wsadowego planowania długoterminowego oszacowanie czasu serii można uzyskać z opisu zadania.
- W przypadku planowania krótkoterminowego musimy przewidzieć wartość następnego czasu serii.
- Prawdopodobnie optymalny pod względem średniego czasu realizacji.
Wady / wady SJF
Oto kilka wad / wad algorytmu SJF:
- Czas ukończenia pracy trzeba znać wcześniej, ale trudno go przewidzieć.
- Jest często używany w systemie wsadowym do długoterminowego planowania.
- SJF nie może być zaimplementowany do planowania procesora w krótkim okresie. Dzieje się tak, ponieważ nie ma określonej metody przewidywania długości nadchodzącej serii procesora.
- Ten algorytm może powodować bardzo długie czasy realizacji lub głód.
- Wymaga wiedzy o tym, jak długo będzie działać proces lub zadanie.
- Prowadzi do głodu, który nie skraca średniego czasu realizacji.
- Trudno jest określić długość nadchodzącego żądania procesora.
- Należy zarejestrować upływający czas, co skutkuje większym obciążeniem procesora.
Podsumowanie
- SJF to algorytm, w którym do następnego wykonania wybierany jest proces o najmniejszym czasie wykonania.
- Harmonogram SJF jest powiązany z każdym zadaniem jako jednostka czasu do wykonania.
- Ta metoda algorytmu jest pomocna w przypadku przetwarzania wsadowego, w którym oczekiwanie na zakończenie zadań nie jest krytyczne.
- Zasadniczo istnieją dwa rodzaje metod SJF: 1) nie wywłaszczający SJF i 2) wywłaszczeniowy SJF.
- W planowaniu bez wywłaszczania, gdy cykl procesora zostanie przydzielony do procesu, proces wstrzymuje go, aż osiągnie stan oczekiwania lub zostanie przerwany.
- W Preemptive SJF Scheduling zadania są umieszczane w kolejce gotowości, gdy nadejdą.
- Chociaż rozpoczyna się proces z krótkim czasem serii, bieżący proces jest usuwany lub wykluczany z wykonania, a zadanie, które jest krótsze, jest wykonywane jako pierwsze.
- SJF jest często używany do planowania długoterminowego.
- Zmniejsza średni czas oczekiwania na algorytm FIFO (First in First Out).
- W planowaniu SJF czas zakończenia zadania musi być znany wcześniej, ale trudno go przewidzieć.
- SJF nie może być zaimplementowany do planowania procesora w krótkim okresie. Dzieje się tak, ponieważ nie ma określonej metody przewidywania długości nadchodzącej serii procesora.