Вычислительных систем

Ниже приведены краткие сведения о планировщиках операционных систем (ОС) и ссылки на литературные источники, материалы которые рекомендуется использовать при выполнении первого задания курсовой работы.

Переход от одного процесса (потока) к другому осуществляется в результате планирования и диспетчеризации. Работа по определению того, в какой момент необходимо прервать выполнение текущего активного потока и какому потоку предоставить возможность выполняться, называется планированием. Планирование реализуется компонентой ОС, называемой планировщиком (scheduler). Планирование процессов по существу включает в себя решение двух задач /1,2/:

1) определение момента времени для смены текущего активного потока;

2) выбор для выполнения потока из очереди готовых потоков.

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

В большинстве операционных систем универсального назначения планирование осуществляется динамически (on-line), то есть решения принимаются во время работы системы на основе анализа текущей ситуации. ОС работает в условиях неопределенности – потоки и процессы появляются в случайные моменты времени и так же непредсказуемо завершаются. Динамические планировщики могут гибко приспосабливаться к изменяющейся ситуации и не используют никаких предположений о мультипрограммной смеси.

Другой тип планирования – статический (off-line) – может быть использован в специализированных системах, в которых весь набор одновременно выполняемых задач определен заранее, например, в системах реального времени.

Диспетчеризация заключается в реализации найденного в результате планирования (динамического или статического) решения, то есть в переключении процессора с одного потока на другой. Процесс диспетчеризации осуществляется диспетчером (dispatcher) ОС.

Диспетчеризация сводится к следующему:

1)сохранению контекста текущего потока, который требуется сменить;

2)загрузке контекста нового потока, выбранного в результате планирования;

3)запуску нового потока на выполнение.

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

С самых общих позиций все множество алгоритмов планирования можно разделить на два класса: вытесняющие и невытесняющие алгоритмы планирования /1-6/.

Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению поток.

Вытесняющие (preemptive) алгоритмы – это такие способы планирования потоков, в которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается ОС, а не активной задачей.

В большинстве современных операционных систем (ОС), например Windows или Linux, используются вытесняющие алгоритмы планирования /5/.

Далее среди множества алгоритмов планирования выделяются два больших класса – бесприоритетные и приоритетные алгоритмы (рис.2.1) /7,8/.

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

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

Рассмотрим кратко некоторые наиболее распространенные алгоритмы планирования, временные диаграммы работы которых необходимо построить в первом задании курсовой работы.

Линейные алгоритмы планирования реализуют выполнение процессов и потоков в порядке очереди, которая организуется согласно тем или иным соглашениям /7-9/.

Самой простой в реализации является дисциплина обслуживания, при которой процессы и потоки выполняются в порядке их появления в ВС. Этот алгоритм называется «первым пришел – первым обслужен», или FCFS (First come – First Served). Те процессы и потоки, которые были заблокированы в процессе выполнения, после перехода в состояние готовности вновь ставятся в очередь готовности. При этом возможны два варианта.

В первом наиболее простом варианте разблокированный процесс или поток ставится в конец очереди готовых процессов и потоков.

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

К основным преимуществам этого алгоритма можно отнести его простую реализацию, справедливость и малые затраты системных ресурсов на формирование очереди задач.

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

Избежать указанного недостатка позволяет невытесняющий алгоритм, при котором планировщик выбирает первым для выполнения самый короткий процесс (задачу). Этот алгоритм называется «кратчайший процесс (задача) – первый», или SJN (Shortest Job Next) /2/. Алгоритм позволяет уменьшить оборотное время – среднее время от момента поступления процесса (задачи) на выполнение до завершения выполнения.

Пусть имеются четыре процесса с временем выполнения первого - a, второго - b, третьего – c и четвертого - d. Тогда первый процесс выполнится через время t_a=a, второй – через время t_b=a+b, третий через время t_c=a+b+c, а четвертый через время t_d=a+b+c+d. Следовательно, среднее оборотное время t_o вычисления четырех процессов равно t_o=(t_a+t_b+t_c+t_d)/4 =(4a+3b+2c+d)4. Очевидно, что вклад времени a в среднее больше, чем всех остальных интервалов времени, поэтому первым должен выполняться самый короткий процесс, а последним – самый длинный, вносящий вклад равный собственному оборотному времени. Этот вывод справедлив для любого количества процессов и потоков.

Пример. Положим, имеются четыре процесса со временем выполнения первого a=10, второго b=8, третьего c=6 и четвертого d=4 единиц времени.

Вычислим среднее оборотное время t_o1 четырехпроцессов для случая выполнения в порядке a-b-c-d. Это время равно t_o1=(4a+3b+2c+d)4=20.

Вычислим среднее оборотное время t_o2 четырехпроцессов для случая выполнения в порядке «кратчайший процесс - первый», т.е. d-c-b-a. Это время равно t_o2=(4d+3c+2b+a)4=15. Очевидно, t_o1> t_o2.

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

Следующей версией предыдущего алгоритма планирования является алгоритм наименьшего оставшегося времени выполнения, или SRT (Shortest Remaining Time) /2,7-9/. В соответствии с этим алгоритмом планировщик всякий раз выбирает на выполнение процесс с наименьшим оставшимся временем выполнения. Когда появляется новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса. Если время выполнения нового процесса меньше, текущий процесс приостанавливается и управление передается новому процессу. Этот алгоритм позволяет быстро обслуживать короткие процессы.

В вытесняющем алгоритме планирования, основанном на квантовании, каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени – квант (time slice). Этот алгоритм получил название циклического (карусельного), или RR (Round Robin) /7-9/.

Смена активного потока происходит, если:

поток завершился и покинул систему;

произошла ошибка;

поток перешел в состояние ожидания;

исчерпан квант процессорного времени, отведенный данному потоку.

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

Кванты, выделяемые процессам (потоками), могут быть одинаковыми для всех процессов или различными.

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

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

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

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

В системах с относительными приоритетами активный поток выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (или же из-за ошибки или завершения потока).

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

Смешанные алгоритмы планирования построены с использованием как концепции квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора потока из очереди готовых определяется приоритетами потоков.

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

Подобным образом реализовано планирование в системах Windows, в которых квантование сочетается с динамическими абсолютными приоритетами. На выполнение выбирается готовый поток с наивысшим приоритетом, и ему выделяется квант времени. Если во время выполнения в очереди готовых потоков появляется поток с более высоким приоритетом, то он вытесняет выполняемый поток.

Алгоритмы планирования с предельными сроками основаны на дополнительной информа­ции о процессах, которая может включать следующее.

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

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

В непериодическом задании это время может быть известно заранее, но может быть и так, что ОС узнает его только в тот момент, ко­гда задание станет действительно готовым к выполнению.

Предельное время начала выполнения - время, когда должно нача­ть­ся выполнение задания.

Предельное время завершения выполнения - время, когда задание должно быть полностью завершено. Обычно задания реального времени имеют ограниче­ние либо по предельному времени начала выполнения, либо по предельному времени завершения выполнения, но не оба ограничения одновременно.

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

Одним из эффективных методов планирования для периодических задач является частотно-монотонное плани­рование (rate monotonic scheduling — RMS).

Система RMS назначает приоритеты заданиям на основе их периодов /13/.

В частотно-монотонном планировании заданием с наивысшим приоритетом является задание с наименьшим периодом; вторым по приоритетности является задание со вторым по величине пе­риодом и т.д. Соответственно, в случае готовности для выполнения нескольких зада­ний первым обслуживается задание с наименьшим периодом.