Shortest-Job-First (SJF) (44)

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

Может быть вытесняющим и невытесняющим. При вытесняющем если CPU burst нового процесса меньше, чем остаток CPU burst у исполняющегося, то исполняющийся процесс вытесняется новым.

Основную сложность при реализации алгоритма SJF представляет невозможность точного знания продолжительности очередного CPU burstдля исполняющихся процессов.

При краткосрочном планировании мы можем делать только прогноз длительности следующего CPU burst, исходя из предыстории работы процесса.

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

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

T(0)=const,первое слагаемое учитывает последнее поведение процесса, второе слагаемое учитывает его предысторию.

При мы перестаем следить за последним поведением процесса, фактически полагая, что T(n)= T(n+1)=...=T(0) т. е. оценивая все CPU burst одинаково, исходя из некоторого начального предположения.

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

Обычно выбирают для равноценного учета последнего поведения и предыстории.

Гарантированное планирование (45)

Каждый из пользователей будет иметь в своем распоряжении ~1/N часть процессорного времени.

T_i – время нахождения пользователя в системе (длительность сеанса его общения с машиной)

– суммарное процессорное время уже выделенное всем его процессам в течение сеанса.

коэффициент справедливости:

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

Приоритетное планирование (46)

Примеры: SJF (продолжительность следующего CPU burst) и гарантированное (коэффициент справедливости)

При приоритетном планировании каждому процессу присваивается приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS.

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

Неизменяющийся приоритет – статистический. Такие легко реализовать, но они не реагируют на изменения ситуации в вычислительной системе, которые могут сделать желательной корректировку порядка исполнения процессов. Более гибкими являются динамические приоритеты процессов, изменяющие свои значения по ходу исполнения процессов.

- низкоприоритетные процессы могут не запускаться долгое время.