Найкоротше завдання спочатку (SJF): превентивний, невипереджувальний приклад

⚡ Розумний підсумок

Найкоротший час виконання (SJF) – це алгоритм планування процесора, який вибирає процес з найменшим часом виконання для наступного запуску. Він може бути випереджаючим або невипереджуючим і значно скорочує середній час очікування для процесів.

  • 🇧🇷 Визначення: Для наступного виконання обирається процес з найкоротшим часом пакетної обробки.
  • 🔀 Два типи: SJF може бути непревентивним або превентивним (спочатку найкоротший час, що залишився).
  • 📉 Основна перевага: Це забезпечує найнижчий середній час очікування для заданого набору процесів.
  • 🏭 Найкраще використовувати: Ідеально підходить для пакетних систем, де час виконання завдань відомий заздалегідь.
  • ❓ Основне обмеження: Час вибуху має бути відомий заздалегідь, що важко передбачити.
  • ⚠️ Ризик: Довгі процеси можуть простоювати, якщо продовжують надходити короткі завдання.

Планування роботи за найкоротшим графіком (SJF)

Що таке найкоротший графік роботи?

Найкоротша робота спочатку (SJF) це алгоритм, в якому для наступного виконання вибирається процес, який має найменший час виконання. Цей метод планування може бути випереджальним або невипереджальним. Це значно скорочує середній час очікування для інших процесів, які очікують на виконання. Повна форма SJF – це найкоротша робота.

В основному існує два типи методів SJF:

  • Непревентивний SJF
  • Превентивний SJF

Характеристики SJF Scheduling

  • Він пов’язаний із кожною роботою як одиницею часу для виконання.
  • Цей метод алгоритму корисний для обробки пакетного типу, де очікування завершення завдань не є критичним.
  • Це може покращити пропускну здатність процесу, забезпечуючи виконання коротших завдань спочатку, що, можливо, скорочує час виконання.
  • Це покращує продуктивність, пропонуючи коротші завдання, які слід виконувати в першу чергу, і які здебільшого мають коротший час виконання.

Непревентивний SJF

У невитісному плануванні, після того, як цикл процесора виділено процесу, процес утримує його, доки не досягне стану очікування або не буде завершено.

Розглянемо наступні п'ять процесів, кожен з яких має свій унікальний час пакетної обробки та час надходження.

Черга процесу Час вибуху Час прибуття
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Крок 0) У момент часу = 0 прибуває P4 та починає виконання.

Непревентивний SJF

Крок 1) У момент часу = 1 надходить процес P3. Але для завершення P4 все ще потрібні 2 виконавчі блоки. Виконання продовжиться.

Непревентивний SJF

Крок 2) У момент часу = 2 процес P1 надходить і додається до черги очікування. P4 продовжить виконання.

Непревентивний SJF

Крок 3) У момент часу = 3 процес P4 завершить своє виконання. Порівнюється час пакету P3 і P1. Процес P1 виконується, оскільки його час пакету менший порівняно з P3.

Непревентивний SJF

Крок 4) У момент часу = 4 процес P5 надходить і додається до черги очікування. P1 продовжить виконання.

Непревентивний SJF

Крок 5) У момент часу = 5 процес P2 надходить і додається до черги очікування. P1 продовжить виконання.

Непревентивний SJF

Крок 6) У момент часу = 9 процес P1 завершить своє виконання. Час пакету P3, P5 і P2 порівнюється. Процес P2 виконується, тому що його пакетний час найнижчий.

Непревентивний SJF

Крок 7) У момент часу = 10 виконується P2, а P3 та P5 знаходяться в черзі очікування.

Непревентивний SJF

Крок 8) У момент часу = 11 процес P2 завершить своє виконання. Порівнюється час пакету P3 і P5. Процес P5 виконується, тому що його час пакету менший.

Непревентивний SJF

Крок 9) У момент часу = 15 процес P5 завершить своє виконання.

Непревентивний SJF

Крок 10) У момент часу = 23 процес P3 завершить своє виконання.

Непревентивний SJF

Крок 11) Давайте розрахуємо середній час очікування для наведеного вище прикладу.

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

Превентивний SJF

У випереджувальному плануванні SJF завдання ставляться в чергу готовності в міру їх надходження. Процес з найкоротшим часом пакетного виконання починає виконання. Якщо надходить процес з ще коротшим часом пакетного виконання, поточний процес видаляється або витісняється з виконання, а коротшому завданню виділяється цикл процесора.

Розглянемо наступні п'ять процесів:

Черга процесу Час вибуху Час прибуття
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Крок 0) У момент часу = 0 прибуває P4 та починає виконання.

Черга процесу Час вибуху Час прибуття
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Превентивний SJF

Крок 1) У момент часу = 1 надходить процес P3. Але P4 має коротший час пакетної обробки. Він продовжить виконання.

Превентивний SJF

Крок 2) У момент часу = 2 процес P1 надходить із часом пакету = 6. Час пакету більше, ніж у P4. Отже, P4 продовжить виконання.

Превентивний SJF

Крок 3) У момент часу = 3 процес P4 завершить своє виконання. Порівнюється час пакету P3 і P1. Процес P1 виконується, тому що його час пакету менший.

Превентивний SJF

Крок 4) У момент часу = 4 надійде процес P5. Час пакету P3, P5 і P1 порівнюється. Процес P5 виконується, тому що його пакетний час найменший. Процес P1 витісняється.

Черга процесу Час вибуху Час прибуття
P1 Залишилось 5 із 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Превентивний SJF

Крок 5) У момент часу = 5 надійде процес P2. Порівнюється час пакетної обробки P1, P2, P3 та P5. Процес P2 виконується, оскільки його час пакетної обробки найменший. Процес P5 витісняється.

Черга процесу Час вибуху Час прибуття
P1 Залишилось 5 із 6 2
P2 2 5
P3 8 1
P4 3 0
P5 Залишилось 3 із 4 4

Превентивний SJF

Крок 6) У момент часу = 6 виконується P2.

Превентивний SJF

Крок 7) У момент часу = 7, P2 завершує своє виконання. Порівнюється час пакетної обробки P1, P3 та P5. Процес P5 виконується, оскільки його час пакетної обробки менший.

Черга процесу Час вибуху Час прибуття
P1 Залишилось 5 із 6 2
P2 2 5
P3 8 1
P4 3 0
P5 Залишилось 3 із 4 4

Превентивний SJF

Крок 8) О моменті часу = 10, P5 завершить своє виконання. Порівнюється час пакетної обробки P1 та P3. Процес P1 виконується, оскільки його час пакетної обробки менший.

Превентивний SJF

Крок 9) У момент часу = 15, P1 завершує своє виконання. P3 – єдиний процес, що залишився. Він розпочне виконання.

Превентивний SJF

Крок 10) У момент часу = 23, P3 завершує своє виконання.

Превентивний SJF

Крок 11) Давайте розрахуємо середній час очікування для наведеного вище прикладу.

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

Переваги SJF

Ось переваги/плюси використання методу SJF:

  • SJF часто використовується для довгострокового планування.
  • Це зменшує середній час очікування порівняно з алгоритмом FIFO (First In First Out - перший прийшов, перший вийшов).
  • Метод SJF дає найнижчий середній час очікування для певного набору процесів.
  • Це підходить для завдань, що виконуються пакетно, коли час виконання відомий заздалегідь.
  • Для пакетної системи довгострокового планування оцінку часу пакету можна отримати з посадової інструкції.
  • Для короткострокового планування нам потрібно передбачити значення часу наступного пакету.
  • Це, ймовірно, оптимально з точки зору середнього часу виконання.

Недоліки/мінуси SJF

Ось деякі недоліки/мінуси алгоритму SJF:

  • Термін виконання роботи повинен бути відомий раніше, але його важко передбачити.
  • Він часто використовується в пакетній системі для довгострокового планування.
  • SJF не може бути реалізований для Планування ЦП на короткий термін. Це тому, що немає спеціального методу для прогнозування тривалості майбутнього вибуху ЦП.
  • Цей алгоритм може спричинити дуже тривалий час виконання або голодування.
  • Вимагає знання того, як довго триватиме процес або робота.
  • Це призводить до голодування, яке не зменшує середній час виконання робіт.
  • Важко дізнатися довжину майбутнього запиту ЦП.
  • Слід записувати час, що минув, оскільки це призводить до збільшення навантаження на процесор.

Поширені запитання

SRTF (Shortest Remaining Time First — завдання, що залишилося найкоротшим) — це просто випереджальна версія SJF. В SJF виконуване завдання завершується до вибору наступного. У SRTF щойно надійшло завдання з коротшим часом, що залишився, може випередити виконуваний процес.

SJF завжди надає перевагу найкоротшому завданню. Якщо короткі процеси постійно надходять, довгий процес може ніколи не отримати доступ до процесора та чекати нескінченно довго. Це називається голодуванням. Для запобігання цьому використовується старіння, яке повільно підвищує пріоритет завдання, що очікує.

Так. SJF є доведено оптимальним, оскільки він забезпечує мінімально можливий середній час очікування для заданого набору процесів. Однак це вірно лише в тому випадку, якщо час пакетної обробки відомий заздалегідь, що рідко можливо на практиці.

Штучний інтелект та машинне навчання можуть аналізувати історію процесу, особливості коду та минулі запуску, щоб оцінити час його пікової навантаженості процесора. Кращі прогнози роблять SJF точнішим, зменшуючи час очікування порівняно з традиційними оцінками експоненціального усереднення.

Потенційно. SJF має труднощі з короткостроковим плануванням, оскільки час пакетної обробки невідомий. Штучний інтелект, який прогнозує пакетну копію в режимі реального часу, може зробити SJF придатним для використання, але накладні витрати на прогнозування та помилки повинні залишатися достатньо низькими, щоб рішення щодо планування було виправданим.

Підсумуйте цей пост за допомогою: