SJN (Shortest job next)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:54, 6 июня 2019.

SJN (Shortest job next - рус. "кратчайшая работа следующей"), также известный как кратчайшее задание первым (SJF) или кратчайшее выполнение следующего (SPN) - алгоритм краткосрочного планирования, который выбирает для выполнения процесс с наименьшим временем выполнения.[1]

Обзор

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

Невытесняющее планирование

Рисунок 1 - Таблица с данными для примера невытесняющего алгоритма SJN

При невытесняющем SJN - планировании процессор предоставляется избранному процессу на все необходимое ему время, независимо от событий, происходящих в вычислительной системе.

Рассмотрим пример работы невытесняющего алгоритма SJN. Пусть в состоянии готовность находятся четыре процесса, p0, p1, p2 и p3, для которых известны времена их очередных CPU burst (см. рисунок 1). Как и прежде, будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода и что временем переключения контекста можно пренебречь.

Рисунок 2 - Таблица с результатами примера невытесняющего алгоритма SJN

При использовании невытесняющего алгоритма SJN первым для исполнения будет выбран процесс p3, имеющий наименьшее значение продолжительности очередного CPU burst. После его завершения для исполнения выбирается процесс p1, затем p0 и, наконец, p2 (см. рисунок 2).

Как мы видим, среднее время ожидания для алгоритма SJN составляет (4 + 1 + 9 + 0)/4 = 3,5 единицы времени. К примеру, легко посчитать, что для алгоритма FCFS при порядке процессов p0, p1, p2, p3 эта величина будет равняться (0 + 5 + 8 + 15)/4 = 7 единицам времени, т. е. будет в два раза больше, чем для алгоритма SJN. Можно показать, что для заданного набора процессов (если в очереди не появляются новые процессы) алгоритм SJN является оптимальным с точки зрения минимизации среднего времени ожидания среди класса невытесняющих алгоритмов.

Вытесняющее планирование

При вытесняющем SJN - планировании учитывается появление новых процессов в очереди готовых к исполнению (из числа вновь родившихся или разблокированных) во время работы выбранного процесса. Если CPU burst нового процесса меньше, чем остаток CPU burst у исполняющегося, то исполняющийся процесс вытесняется новым.

Рисунок 3 -Таблица с данными для примера вытесняющего алгоритма SJN

Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд процессов p0, p1, p2 и p3 с различными временами CPU burst и различными моментами их появления в очереди процессов, готовых к исполнению (см. рисунок 3).

Рисунок 4 - Таблица с результатами примера вытесняющего алгоритма SJN

В начальный момент времени в состоянии готовность находятся только два процесса, p0 и p3. Меньшее время очередного CPU burst оказывается у процесса p3, поэтому он и выбирается для исполнения (см. рисунок 4). По прошествии 2 единиц времени в систему поступает процесс p1. Время его CPU burst меньше, чем остаток CPU burst у процесса p3, который вытесняется из состояния исполнение и переводится в состояние готовность. По прошествии еще 2 единиц времени процесс p1 завершается, и для исполнения вновь выбирается процесс p3. В момент времени t = 6 в очереди процессов, готовых к исполнению, появляется процесс p2, но поскольку ему для работы нужно 7 единиц времени, а процессу p3 осталось трудиться всего 1 единицу времени, то процесс p3 остается в состоянии исполнение. После его завершения в момент времени t = 7 в очереди находятся процессы p0 и p2, из которых выбирается процесс p0. Наконец, последним получит возможность выполняться процесс p2.

Сложности алгоритма

Основную сложность при реализации алгоритма SJN представляет невозможность точного знания продолжительности очередного CPU burst для исполняющихся процессов. В пакетных системах количество процессорного времени, необходимое заданию для выполнения, указывает пользователь при формировании задания. Мы можем брать эту величину для осуществления долгосрочного SJN - планирования. Если пользователь укажет больше времени, чем ему нужно, он будет ждать результата дольше, чем мог бы, так как задание будет загружено в систему позже. Если же он укажет меньшее количество времени, задача может не досчитаться до конца. Таким образом, в пакетных системах решение задачи оценки времени использования процессора перекладывается на плечи пользователя. При краткосрочном планировании мы можем делать только прогноз длительности следующего CPU burst, исходя из предыстории работы процесса.

Пусть τ(n) – величина n -го CPU burst, T(n + 1) – предсказываемое значение для n + 1 -го CPU burst, α – некоторая величина в диапазоне от 0 до 1.

Определим рекуррентное соотношение:

T(n + 1) = ατ(n) + (1 - α)T(n),

T(0) положим произвольной константой. Первое слагаемое учитывает последнее поведение процесса, тогда как второе слагаемое учитывает его предысторию. При α = 0 мы перестаем следить за последним поведением процесса, фактически полагая:

T(n)= T(n+1)=...=T(0),

т. е. оценивая все CPU burst одинаково, исходя из некоторого начального предположения.

Положив α = 1, мы забываем о предыстории процесса. В этом случае мы полагаем, что время очередного CPU burst будет совпадать со временем последнего CPU burst:

T(n+1)= τ(n).

Обычно выбирают α = 1/2 для равноценного учета последнего поведения и предыстории. Надо отметить, что такой выбор α удобен и для быстрой организации вычисления оценки T(n + 1). Для подсчета новой оценки нужно взять старую оценку, сложить с измеренным временем CPU burst и полученную сумму разделить на 2, например, сдвинув ее на 1 бит вправо. Полученные оценки T(n + 1) применяются как продолжительности очередных промежутков времени непрерывного использования процессора для краткосрочного SJN - планирования.[Источник 1]

Области применения

Наибольшая трудность в практической реализации SJN заключается в невозможности заранее определить величину времени последующего обслуживания.

Поэтому стратегия SJN часто применяется в долгосрочных планировщиках, обслуживающих пакетный режим. В этом случае вместо величины времени последующего обслуживания используется допустимое максимальное время выполнения задания, которое программист должен специфицировать перед отправкой задания в пакет.[Источник 2]

Источники

  1. Лекция: Планирование процессов // НОУ ИНТУИТ URL: https://www.intuit.ru/studies/courses/2192/31/lecture/972?page=4 (дата обращения: 19.05.2019).
  2. Стратегия SJF // Студенческая библиотека онлайн URL: https://studbooks.net/2040004/informatika/strategiya_shortest_first (дата обращения: 19.05.2019).


Примечания

  1. Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter Scheduling Introduction] (PDF), Arpaci-Dusseau Books