Планирование задач. 
Технологии параллельных и распределенных систем

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

Алгоритмы планирования задач. Цель циклического алгоритма планирования — обеспечить справедливое выделение ресурсов. Задача ставится в очередь, поддерживающую принцип «первым пришел — первым обслужен» (FIFO). Задаче, находящейся в начале списка готовых, назначается процессор, которым она может владеть в течение фиксированного промежутка времени, называемого квантом. Если квант времени истек до того, как задача приостановилась сама (например, в ожидании завершения ввода/ вывода или сообщения), то ее приостанавливает ядро, после чего задача помещается в конец списка готовых. Затем ЦП выделяется другой задаче, оказавшейся в начале списка.

Для систем реального времени циклическое планирование не годится. Справедливое распределение ресурсов — это не главное, задачам нужно назначать приоритеты в соответствии с важностью выполняемых операций. Так, критичные по времени задачи обязательно должны уложиться в отведенные временные рамки. Поэтому для систем реального времени больше подходит алгоритм вытесняющего планирования с приоритетами. Каждой задаче назначается приоритет, и список готовых упорядочивается по значению этого приоритета. ЦП выделяется задаче с наивысшим приоритетом. Затем эта задача выполняется до тех пор, пока не приостановится сама либо не будет вытеснена задачей с большим приоритетом (которая только что возобновила работу). Задачам с одинаковыми приоритетами ЦП выделяется по циклическому алгоритму. Следует отметить, что при вытесняющем планировании с приоритетами квантование времени не применяется.

Состояния задач. Рассмотрим различные состояния, которые проходит задача с момента создания до момента завершения (рис. 7.4). Эти состояния поддерживаются многозадачным ядром, где применяется алгоритм вытесняющего планирования с приоритетами.

Новая задача сразу оказывается в состоянии «Готова» и помещается в список готовых. Когда она передвигается в начало данного списка, ей выделяется ЦП, и задача переходит в состояние «Исполняется». Потом она может быть вытеснена другой задачей и снова окажется в состоянии «Готова»; в этот момент операционная система перенесет ее в нужное место в списке готовых.

Случается и так, что находящаяся в состоянии «Исполняется» задача будет заблокирована и перейдет в то или иное состояние блокировки. Блокировка вызывается ожиданием завершения ввода/вывода, ожиданием сообщения от другой задачи или ожиданием разрешения войти в критическую секцию. Заблокированная задача перейдет в состояние «Готова», как только будет устранена причина блокировки.

Рис. 4. Диаграмма состояний параллельной задачи

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

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