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.

Niewywłaszczający SJF

Krok 1) W chwili = 1 nadchodzi proces P3. Ale P4 nadal potrzebuje 2 jednostek wykonawczych do ukończenia. Będzie kontynuować realizację.

Niewywłaszczający SJF

Krok 2) W chwili =2 przybywa proces P1 i zostaje dodany do kolejki oczekujących. P4 będzie kontynuować wykonywanie.

Niewywłaszczający SJF

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.

Niewywłaszczający SJF

Krok 4) W chwili = 4 przybywa proces P5 i zostaje dodany do kolejki oczekujących. P1 będzie kontynuować wykonywanie.

Niewywłaszczający SJF

Krok 5) W chwili = 5 przybywa proces P2 i zostaje dodany do kolejki oczekujących. P1 będzie kontynuować wykonywanie.

Niewywłaszczający SJF

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.

Niewywłaszczający SJF

Krok 7) W chwili = 10, P2 jest wykonywany, a P3 i P5 znajdują się w kolejce oczekującej.

Niewywłaszczający SJF

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.

Niewywłaszczający SJF

Krok 9) W chwili = 15 proces P5 zakończy swoje wykonywanie.

Niewywłaszczający SJF

Krok 10) W chwili = 23 proces P3 zakończy swoje wykonywanie.

Niewywłaszczający SJF

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

Uprzedzający SJF

Krok 1) W chwili = 1 nadchodzi proces P3. Ale P4 ma krótszy czas wybuchu. Będzie kontynuować realizację.

Uprzedzający SJF

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.

Uprzedzający SJF

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.

Uprzedzający SJF

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

Uprzedzający SJF

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

Uprzedzający SJF

Krok 6) W chwili =6 wykonywany jest P2.

Uprzedzający SJF

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

Uprzedzający SJF

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.

Uprzedzający SJF

Krok 9) W chwili =15 P1 kończy wykonywanie. Pozostał już tylko proces P3. Rozpocznie się wykonanie.

Uprzedzający SJF

Krok 10) W chwili =23 P3 kończy wykonywanie.

Uprzedzający SJF

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.