Алгоритм планирования с наименьшим оставшимся временем (упреждающий SJF)

В предыдущем посте мы обсудили набор 1 SJF, то есть неупреждающий. В этом посте мы обсудим упреждающую версию SJF, известную как Shortest Remaining Time First (SRTF).

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

Примеры, демонстрирующие работу алгоритма планирования упреждающего кратчайшего задания в первую очередь ЦП:

Пример 1. Рассмотрим следующую таблицу времени прибытия и времени пакета для пяти процессов P1, P2, P3, P4 и P5 .

Алгоритм планирования кратчайшего задания в первую очередь будет работать на основе шагов, указанных ниже:

В момент времени = 0,

• Приходит процесс P4 и начинает выполняться

В момент времени = 1,

• Приходит процесс P3.
• Но, поскольку P4 имеет более короткое время серийной съемки. Он продолжит выполнение.
• Таким образом, P3 будет ждать, пока не выполнится P4.

В момент времени =2,

• Процесс P1 прибывает с пакетным временем = 6
• Поскольку время взрыва P1 больше, чем у P4
• Таким образом, P4 продолжит свое выполнение.

В момент времени = 3,

• Процесс P4 завершит свое выполнение.
• Затем сравнивается время пакетной передачи P3 и P1.
• Процесс P1 выполняется, потому что его пакетное время меньше по сравнению с P3.

В момент времени = 4,

• Приходит процесс P5.
• Затем сравнивается время пакетной передачи P3, P5 и P1.
• Процесс P5 выполняется первым среди них, потому что его время пакета самое низкое, а процесс P1 вытеснен .

В момент времени = 5,

• Приходит процесс P2.
• Время взрыва всех процессов сравнивается,
• Процесс P2 запускается, так как его время пакета самое низкое среди всех.
• Процесс P5 вытеснен.

В момент времени = 6,

• Процесс P2 будет продолжать выполняться.
• Он будет выполняться до времени = 8, так как время пакета P2 составляет 2 мс.

В момент времени=7,

• Процесс P2 завершает свое выполнение.
• Затем снова сравнивается время всплеска всех оставшихся процессов.
• Процесс P5 выполняется, потому что его время пакета меньше, чем у других.

В момент времени = 10,

• Процесс P5 завершит свое выполнение.
• Затем сравнивается время пакета оставшихся процессов P1 и P3.
• Таким образом, процесс P1 выполняется, так как его время пакета меньше, чем P3.

В момент времени = 15,

• Процесс P1 завершает свое выполнение, и остается только процесс P3.
• P3 начнет выполняться.

В момент времени = 23,

• Процесс P3 завершит свое выполнение.
• Общее выполнение процессов будет таким, как показано ниже:

Диаграмма Ганта для вышеуказанного исполнения:

Теперь давайте рассчитаем среднее время ожидания и время оборота:

Как мы знаем,

• Время оборота = время завершения – время прибытия
• Время ожидания = время оборота – время взрыва

В настоящее время,

• Среднее время оборота = (13 + 2 + 22 + 3 + 6)/5 = 9,2
• Среднее время ожидания = (7 + 0 + 14 + 0 + 2)/5 = 23/5 = 4,6

Реализация алгоритма SRTF:

Подход:

• Перемещайтесь, пока весь процесс не будет полностью выполнен.
  • Найдите процесс с минимальным оставшимся временем на каждом временном интервале.
  • Уменьшите его время на 1.
  • Проверьте, становится ли оставшееся время равным 0
  • Увеличить счетчик завершения процесса.
  • Время завершения текущего процесса = текущее_время + 1;
  • Рассчитайте время ожидания для каждого завершенного процесса.
    • wt[i]= время завершения – время прибытия-время_взрыва
  • Увеличение времени круга на единицу.
• Найдите время обработки (время ожидания + время всплеска).

Программа для реализации кратчайшего оставшегося времени сначала:

Временная сложность: O(N)
Вспомогательное пространство: O(1)

Преимущества:

• Короткие процессы обрабатываются очень быстро.
• Система также требует очень мало накладных расходов, поскольку она принимает решение только тогда, когда завершается процесс или добавляется новый процесс.
• Когда добавляется новый процесс, алгоритму нужно только сравнить выполняющийся в данный момент процесс с новым процессом, игнорируя все другие процессы, ожидающие выполнения в данный момент.

Недостатки:

• Как и самая короткая работа в первую очередь, это может привести к голоданию процесса.
• Длинные процессы могут откладываться на неопределенное время, если постоянно добавляются короткие процессы.

Источник: Вики
Эта статья предоставлена Сахилом Чхабра. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью с помощью write.geeksforgeeks.org или отправить ее по адресу review-team@geeksforgeeks.org. Посмотрите, как ваша статья появится на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.