logo

Planowanie najkrótszego zadania (SJF).

Do tej pory planowaliśmy procesy według czasu ich przybycia (w harmonogramowaniu FCFS). Jednakże algorytm szeregowania SJF planuje procesy według czasu ich impulsów.

W harmonogramowaniu SJF jako następny zostanie zaplanowany proces z najkrótszym czasem impulsu spośród listy dostępnych procesów w kolejce gotowych.

Jednak bardzo trudno jest przewidzieć czas impulsu potrzebny do realizacji procesu, dlatego też algorytm ten jest bardzo trudny do zaimplementowania w systemie.

Zalety SJF

  1. Maksymalna przepustowość
  2. Minimalny średni czas oczekiwania i realizacji

Wady SJF

  1. Może cierpieć z powodu głodu
  2. Nie da się tego wdrożyć, ponieważ nie można z góry znać dokładnego czasu Burst dla procesu.

Dostępne są różne techniki pozwalające określić czas obciążenia procesora w procesie. Omówimy je szczegółowo później.

stdin w c

Przykład

W poniższym przykładzie istnieje pięć zadań o nazwach P1, P2, P3, P4 i P5. Ich czas przybycia i czas wybuchu podano w poniższej tabeli.

och, Java
PID Czas przybycia Czas wybuchu Czas realizacji Czas zawrócenia Czas oczekiwania
1 1 7 8 7 0
2 3 3 13 10 7
3 6 2 10 4 2
4 7 10 31 24 14
5 9 8 dwadzieścia jeden 12 4

Ponieważ żaden proces nie dociera do czasu 0; w gnieździe będzie puste miejsce Wykres Gantta od czasu 0 do 1 (czas, w którym przybywa pierwszy proces).

Zgodnie z algorytmem system operacyjny planuje proces, który ma najkrótszy czas impulsu spośród dostępnych procesów w kolejce gotowości.

Do tej pory w kolejce gotowości znajdował się tylko jeden proces, dlatego program planujący zaplanuje to dla procesora bez względu na czas trwania serii.

Będzie to wykonywane do 8 jednostek czasu. Do tego czasu w kolejce gotowości pojawią się jeszcze trzy procesy, dlatego planista wybierze proces z najkrótszym czasem impulsu.

Spośród procesów podanych w tabeli jako następny zostanie wykonany P3, ponieważ ma najkrótszy czas impulsu spośród wszystkich dostępnych procesów.

Krotka sortowania w Pythonie

A więc tak będzie przebiegać procedura Najpierw najkrótsza praca (SJF) algorytm planowania.

algorytm planowania SJF os

Średni czas oczekiwania = 27/5