Najpierw najkrótsza praca (SJF): przykład z wywłaszczeniem, bez wywłaszczenia
Jaki jest najkrótszy harmonogram pierwszej pracy?
Najkrótsza pierwsza praca (SJF) to algorytm, w którym do kolejnego wykonania wybierany jest 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. Pełna forma SJF to Najkrótsza praca.
Zasadniczo istnieją dwa typy metod SJF:
- Niewywłaszczający SJF
- Uprzedzający SJF
Charakterystyka harmonogramowania SJF
- Jest powiązany z każdym zadaniem jako jednostka czasu do wykonania.
- Ta metoda algorytmiczna jest przydatna w przypadku przetwarzania wsadowego, gdzie oczekiwanie na zakończenie zadań nie jest krytyczne.
- Może poprawić przepustowość procesu, upewniając się, że w pierwszej kolejności wykonywane są krótsze zadania, a tym samym prawdopodobnie mają krótki czas realizacji.
- 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.
Niewywłaszczający SJF
W przypadku planowania niewywłaszczającego, gdy cykl procesora zostanie przydzielony procesowi, proces wstrzymuje go do momentu osiągnięcia stanu oczekiwania lub zakończenia.
Rozważmy pięć następujących procesów, z których każdy ma swój własny, unikalny 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 chwili = 0 przybywa P4 i rozpoczyna wykonanie.
Krok 1) W chwili = 1 nadchodzi proces P3. Ale P4 nadal potrzebuje 2 jednostek wykonawczych do ukończenia. Będzie kontynuować realizację.
Krok 2) W chwili =2 przybywa proces P1 i zostaje dodany do kolejki oczekujących. P4 będzie kontynuować wykonywanie.
Krok 3) W chwili = 3 proces P4 zakończy swoje wykonywanie. Porównuje się czas rozerwania P3 i P1. Proces P1 jest wykonywany, ponieważ jego czas impulsu jest krótszy w porównaniu do P3.
Krok 4) W chwili = 4 przybywa proces P5 i zostaje dodany do kolejki oczekujących. P1 będzie kontynuować wykonywanie.
Krok 5) W chwili = 5 przybywa proces P2 i zostaje dodany do kolejki oczekujących. P1 będzie kontynuować wykonywanie.
Krok 6) W chwili = 9 proces P1 zakończy swoje wykonywanie. Porównuje się czas rozerwania P3, P5 i P2. Proces P2 jest wykonywany, ponieważ jego czas impulsu jest najkrótszy.
Krok 7) W chwili = 10, P2 jest wykonywany, a P3 i P5 znajdują się w kolejce oczekującej.
Krok 8) W chwili = 11 proces P2 zakończy swoje wykonywanie. Porównuje się czas rozerwania P3 i P5. Proces P5 jest wykonywany, ponieważ jego czas impulsu jest krótszy.
Krok 9) W chwili = 15 proces P5 zakończy swoje wykonywanie.
Krok 10) W chwili = 23 proces P3 zakończy swoje wykonywanie.
Krok 11) Obliczmy średni czas oczekiwania dla powyższego przykładu.
Wait time P4= 0-0=0 P1= 3-2=1 P2= 9-5=4 P5= 11-4=7 P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Uprzedzający SJF
W planowaniu z wywłaszczaniem SJF zadania są umieszczane w kolejce gotowych w miarę ich pojawiania się. Rozpoczyna się proces z najkrótszym czasem trwania serii. Jeśli nadejdzie proces z jeszcze krótszym czasem impulsu, bieżący proces zostanie usunięty lub wywłaszczony z wykonania, a krótszemu zadaniu przydzielany jest cykl procesora.
Rozważmy 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 chwili = 0 przybywa P4 i rozpoczyna wykonanie.
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 chwili = 1 nadchodzi proces P3. Ale P4 ma krótszy czas wybuchu. Będzie kontynuować realizację.
Krok 2) W chwili = 2 przybywa proces P1 z czasem serii = 6. Czas serii jest dłuższy niż P4. Dlatego P4 będzie kontynuować wykonywanie.
Krok 3) W chwili = 3 proces P4 zakończy swoje wykonywanie. Porównuje się czas rozerwania P3 i P1. Proces P1 jest wykonywany, ponieważ jego czas impulsu jest krótszy.
Krok 4) W chwili = 4 nadejdzie proces P5. Porównuje się czas rozerwania P3, P5 i P1. Proces P5 jest wykonywany, ponieważ jego czas impulsu jest najkrótszy. Proces P1 zostaje 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 chwili = 5 nadejdzie proces P2. Porównuje się czas rozerwania P1, P2, P3 i P5. Proces P2 jest wykonywany, ponieważ jego czas impulsu jest najmniejszy. Proces P5 został 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 chwili =6 wykonywany jest P2.
Krok 7) W chwili =7 P2 kończy wykonywanie. Porównuje się czas rozerwania P1, P3 i P5. Proces P5 jest wykonywany, ponieważ jego czas impulsu 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 chwili =10 P5 zakończy wykonywanie. Porównuje się czas rozerwania P1 i P3. Proces P1 jest wykonywany, ponieważ jego czas impulsu jest krótszy.
Krok 9) W chwili =15 P1 kończy wykonywanie. Pozostał już tylko proces P3. Rozpocznie się wykonanie.
Krok 10) W chwili =23 P3 kończy wykonywanie.
Krok 11) Obliczmy średni czas oczekiwania dla powyższego przykładu.
Wait time P4= 0-0=0 P1= (3-2) + 6 =7 P2= 5-5 = 0 P5= 4-4+2 =2 P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Zalety SJF
Oto zalety/zalety stosowania metody SJF:
- SJF jest często używany do planowania długoterminowego.
- Skraca średni czas oczekiwania w porównaniu z algorytmem FIFO (First in First Out).
- Metoda SJF daje najniższy średni czas oczekiwania dla określonego zestawu procesów.
- Jest to odpowiednie w przypadku zadań uruchamianych wsadowo, gdzie czas wykonania jest znany z góry.
- W przypadku wsadowego systemu planowania długoterminowego szacunkowy czas serii można uzyskać z opisu zadania.
- W przypadku planowania krótkoterminowego musimy przewidzieć wartość następnego czasu impulsu.
- Prawdopodobnie optymalne ze względu na średni czas realizacji.
Wady/minusy SJF
Oto kilka wad/wad algorytmu SJF:
- Czas realizacji zadania musi być znany wcześniej, ale jest trudny do przewidzenia.
- Jest często używany w systemie wsadowym do planowania długoterminowego.
- Nie można zaimplementować SJF Planowanie procesora na krótką metę. Dzieje się tak dlatego, że nie ma konkretnej metody przewidywania długości nadchodzącego impulsu procesora.
- Algorytm ten może powodować bardzo długie czasy realizacji lub głód.
- Wymaga wiedzy o tym, jak długo będzie trwał proces lub zadanie.
- Prowadzi to do głodu, który nie skraca średniego czasu realizacji.
- Trudno jest określić długość nadchodzącego żądania procesora.
- Należy rejestrować czas, który upłynął, co powoduje większe obciążenie procesora.
Podsumowanie
- SJF to algorytm, w którym do kolejnego wykonania wybierany jest proces o najkrótszym czasie wykonania.
- Harmonogram SJF jest powiązany z każdym zadaniem jako jednostka czasu do wykonania.
- Ta metoda algorytmiczna jest przydatna w przypadku przetwarzania wsadowego, gdzie oczekiwanie na zakończenie zadań nie jest krytyczne.
- Zasadniczo istnieją dwa typy metod SJF: 1) SJF bez wywłaszczania i 2) SJF z wywłaszczaniem.
- W przypadku planowania niewywłaszczającego, gdy cykl procesora zostanie przydzielony procesowi, proces wstrzymuje go do momentu osiągnięcia stanu oczekiwania lub zakończenia.
- W planowaniu z wywłaszczaniem SJF zadania są umieszczane w kolejce gotowych w miarę ich pojawiania się.
- Chociaż rozpoczyna się proces o krótkim czasie trwania 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.
- Skraca średni czas oczekiwania w porównaniu z algorytmem FIFO (First in First Out).
- W harmonogramowaniu SJF czas realizacji zadania musi być znany wcześniej, ale jest trudny do przewidzenia.
- SJF nie może zostać zaimplementowany do planowania procesora w krótkim okresie. Dzieje się tak dlatego, że nie ma konkretnej metody przewidywania długości nadchodzącego impulsu procesora.