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ć wydajność procesu poprzez zapewnienie, że najpierw wykonywane są krótsze zadania, co może skrócić czas realizacji.
• Poprawia wydajność pracy, oferując krótsze zadania, które należy wykonać w pierwszej kolejności i których czas realizacji jest zazwyczaj krótszy.

Niewywłaszczający SJF

W przypadku harmonogramowania niewywłaszczającego, gdy cykl procesora zostanie przydzielony procesowi, proces ten zatrzymuje go, aż osiągnie stan oczekiwania lub zostanie zakończony.

Rozważmy następujące pięć 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 czasie = 0, P4 przybywa i rozpoczyna wykonywanie.

Krok 1) W czasie = 1, nadchodzi proces P3. Jednak proces P4 nadal potrzebuje 2 jednostek wykonawczych do ukończenia. Będzie kontynuował wykonywanie.

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ących.

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 przypadku planowania SJF z wywłaszczaniem (Preemptive SJF Scheduling) zadania są umieszczane w kolejce zadań gotowych w miarę ich pojawiania się. Proces z najkrótszym czasem buforowania rozpoczyna wykonywanie. Jeśli pojawi się proces z jeszcze krótszym czasem buforowania, bieżący proces jest usuwany lub wywłaszczany z wykonywania, 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 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, nadchodzi proces P3. Jednak proces P4 ma krótszy czas trwania. Będzie on kontynuował wykonywanie.

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 czasie = 5 pojawi się proces P2. Porównywany jest czas trwania serii P1, P2, P3 i P5. Proces P2 zostaje wykonany, ponieważ jego czas trwania serii jest najkrótszy. Proces P5 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	Pozostało 3 z 4	4

Krok 6) W czasie = 6 wykonywany jest P2.

Krok 7) W chwili = 7 proces P2 kończy wykonywanie. Porównuje się czas trwania serii procesów P1, P3 i P5. Proces P5 zostaje wykonany, ponieważ jego czas trwania serii 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 proces P5 zakończy wykonywanie. Porównuje się czas trwania serii P1 i P3. Proces P1 zostaje wykonany, ponieważ jego czas trwania serii jest krótszy.

Krok 9) W chwili = 15 proces P1 kończy wykonywanie. Pozostał tylko proces P3. Rozpocznie on wykonywanie.

Krok 10) W chwili = 23 P3 kończy swoje 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 korzyści/zalety stosowania metody SJF:

• SJF jest często używany do planowania długoterminowego.
• Skraca średni czas oczekiwania w porównaniu z algorytmem FIFO (pierwsze weszło, pierwsze wyszło).
• Metoda SJF pozwala uzyskać 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.
• Jest to prawdopodobnie optymalne rozwiązanie biorąc pod uwagę średni czas realizacji.

Wady/minusy SJF

Oto kilka wad/przeciwwskazań 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.
• SJF nie może być wdrożony dla 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ć upływający czas, co wiąże się z większym obciążeniem procesora.

FAQ