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

---

Память является разделяемым ресурсом. Способы разделения памяти и времени центрального процессора сильно влияют на скорость выполнения отдельных вычислений и на общую эффективность вычислительной системы.
ОС выполняет следующие основные функции, связанные с управлением задачами:
- создание и удаление задач;
- планирование процессов и диспетчеризация задач;
- синхронизация задач, обеспечение их средствами коммуникации.
Система управления задачами обеспечивает похождение их через компьютер. В зависимости от состояния процесса ему должен быть предоставлен тот или иной ресурс.
Создание и удаление задач производится по соответствующим запросам от пользователей или самих задач.
Основным подходом к организации того или иного метода управления процессами является организация очередей процессов и ресурсов.
На распределение ресурсов влияют конкретные потребности тех задач, которые должны выполняться параллельно.
Задачи динамического планирования, т.е. наиболее эффективного распределения ресурсов, возникающие практически при каждом событии, называются диспетчеризацией. Планирование осуществляется реже, чем задача текущего распределения ресурсов между уже выполняющимися процессами и потоками. Различие между долгосрочным и краткосрочным планированием заключается в частоте запуска.
Долгосрочный планировщик решает, какой из процессов, находящихся во входной очереди, должен быть переведен в очередь готовых к выполнению процессов в случае освобождения ресурсов памяти. В очереди готовых к выполнению процессов должны находиться в равной пропорции процессы, ориентированные на ввод/вывод, и процессы, ориентированные на работу центрального процессора.
Краткосрочный планировщик решает, какая из задач, находящихся в очереди готовых к выполнению, должна быть передана на выполнение. В большинстве современных ОС долгосрочный планировщик отсутствует.

Планирование и диспетчеризация процессов и задач

Стратегия планирования

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

Дисциплины диспетчеризации

Диспетчеризация связана с понятием задачи (потока). Если ОС не поддерживает механизма потоков, то понятие задачи можно заменить на понятие процесса.
Известно большое количество правил, в соответствии с которыми формируется очередь (список) готовых к выполнению задач.
Имеются два больших класса дисциплин обслуживания:
- бесприоритетные:
- приоритетные.
При бесприоритетном обслуживании выбор задачи производится в некотором порядке без учета их важности и времени обслуживания.
При реализации приоритетных дисциплин обслуживания отдельным задачам предоставляется преимущественное право на исполнение.
Бесприоритетные дисциплины обслуживания делятся на следующие:
- линейные:
o в порядке очереди;
o случайный выбор процесса;
- циклический:
o циклический алгоритм;
o многоприоритетный циклический алгоритм.
Приоритетные дисциплины обслуживания делятся на следующие:
- с фиксированным приоритетом:
o с относительным приоритетом;
o с абсолютным приоритетом;
o адаптивное обслуживание;
o приоритет зависит от времени ожидания;
- с динамическим приоритетом:
o приоритет зависит от времени ожидания;
o приоритет зависит от времени обслуживания.
Свойства приоритетов:
- приоритет, присвоенный задаче, может являться величиной постоянной;
- приоритет задачи может изменяться в процессе ее решения.
Диспетчеризация с динамическими приоритетами требует дополнительных расходов на вычисление значений приоритетов, поэтому многие ОС реального времени используют методы диспетчеризации на основе статических (постоянных) приоритетов.
Самой простой в реализации является дисциплина FCFS (first come – first served), задачи обслуживаются в порядке очереди, т.е. в порядке их появления. Задачи, приостановленные для ожидания какого-либо ресурса, после перехода в состояние готовности становятся в эту очередь перед задачами, которые еще не выполнялись.
Образуются две очереди:
- новые задачи;
- ранее выполнявшиеся, но попавшие в состояние ожидания.
Дисциплина FCFS реализует стратегию обслуживания «по возможности заканчивать вычисления в порядке их появления». Эта дисциплина не требует внешнего вмешательства в ход вычислений и перераспределения процессорного времени. По классу диспетчеризации (вытесняющие и не вытесняющие) дисциплина FCFS относится к не вытесняющим.

Достоинства дисциплины FCFS:
- простота реализации;
- малые расходы системных ресурсов на формирование очереди задач.
Основной недостаток – при увеличении загрузки вычислительной системы растет среднее время ожидания обслуживания, короткие задачи ожидают столько же времени, как и трудоемкие.
Дисциплина обслуживания SJN (shortest job next) требует, чтобы для каждого задания была известна оценка в потребностях процессорного времени. Пользователи должны были указывать предположительное время выполнения. Диспетчер задач сравнивал указанное время с реальным временем выполнения и, если время выполнения превышало указанное, то помещал это задание в конец очереди.
Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. Если задание было временно заблокировано из-за занятости какого-либо ресурса, то оно помещается в конец очереди готовых к выполнению заданий наравне с вновь поступившими. Задания, которым требуется совсем немного времени для завершения, попадают в конец очереди.
Для устранения этого недостатка была предложена дисциплина SRT (shortest remaining time, следующее задание требует меньше всего времени для своего завершения).
Перечисленные три дисциплины обслуживания могут использоваться для пакетных режимов работы, когда не важно время отклика.
Для интерактивной работы надо обеспечить приемлемое время реакции системы и равенство в обслуживании, если система мультитерминальная. Интерактивные задания должны иметь преимущество перед фоновыми. Эти условия решены в дисциплине RR (round robin – круговая, карусельная).
Дисциплина обслуживания RR предполагает, что каждая задача получает процессорное время порциями (квантами). После окончания выделенного кванта времени задача снимается с исполнения и на выполнение выбирается следующая задача. Снятая задача помещается в конец очереди готовых к выполнению задач.
Величина кванта времени выбирается как компромисс между приемлемым временем реакции системы на запросы пользователей и накладными расходами на частоту смены контекста задач.

Вытесняющие и не вытесняющие алгоритмы диспетчеризации

Диспетчеризация без перераспределения процессорного времени, то есть не вытесняющая многозадачность – это такой способ диспетчеризации процессов, при котором активный процесс выполняется до тех пор, пока он сам, по своей инициативе, не отдаст управление диспетчеру задач для выбора из очереди другого, готового к исполнению процесса. Дисциплины обслуживания FCFS, SJN, SRT относятся к не вытесняющим.
Диспетчеризация с перераспределением процессорного времени между задачами, то есть вытесняющая многозадачность – это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается диспетчером задач, а не самой активной задачей. Механизм диспетчеризации сосредоточен в самой ОС и программист не должен заботиться о параллельном выполнении своего приложения с другими приложениями.
Операционная система выполняет следующие функции:
- определяет момент снятия с выполнения текущей задачи;
- сохраняет контекст текущей задачи в дескрипторе задачи;
- выбирает из очереди готовых к выполнению задач следующую;
- загружает контекст выбранной задачи;
- запускает выбранную задачу на исполнение.
Дисциплина RR и аналогичные ей относятся к вытесняющим.
При не вытесняющей многозадачности механизм распределения процессорного времени распределен между ОС и прикладной программой. Прикладная программа должна быть разделена на кванты, по окончанию которых с помощью системного вызова управление передается супервизору ОС. Диспетчер задач формирует очереди и выбирает задачу на исполнение.

Качество диспетчеризации и гарантии обслуживания

Одна из проблем при выборе дисциплины обслуживания – гарантия обслуживания. При некоторых дисциплинах обслуживания, например, с абсолютными приоритетами, низкоприоритетные задачи долго могут не получать процессорное время.
Требование к системе – не только завершить процесс, но завершить его к указанному времени или в течение указанного времени.
Наиболее рациональное решение – выделять процессорное время квантами.
Гарантировать обслуживание можно тремя способами:
- выделять минимальную долю процессорного времени некоторому классу процессов, если, по крайней мере, один из них готов к исполнению;
- выделять минимальную долю процессорного времени некоторому конкретному процессу, готовому к исполнению;
- выделить столько процессорного времени некоторому процессу, чтобы он мог выполнить свои вычисления к сроку.
Для сравнения алгоритмов диспетчеризации используются следующие критерии:
- использование (загруженность) центрального процессора;
- пропускная способность – количество процессов, выполняющихся в единицу времени;
- время оборота – интервал времени от момента появления процесса во входной очереди до момента его завершения (время ожидания во входной очереди + время ожидания в очереди готовых к выполнению процессов + время ожидания в очередях к оборудованию + время выполнения в процессоре + время ввода/вывода);
- время ожидания – суммарное время нахождения процесса в очереди готовых к выполнению процессов;
- время отклика – время от момента попадания процесса во входную очередь до момента первого обращения к терминалу.
Главные причины уменьшения производительности системы:
- накладные расходы на переключение процессора (переключения контекстов задач, перемещения страниц виртуальной памяти, обновление данных в кэш-области);
- переключение на другой процесс в тот момент, когда текущий процесс выполняет критическую секцию, а другие процессы активно ожидают входа в свою критическую секцию.
Методы повышения производительности системы в мультипроцессорных системах:
- совместное планирование, все потоки одного приложения одновременно выбираются для выполнения процессорами и одновременно снимаются с них;
- находящиеся в критической секции задачи не прерываются, а активно ожидающие входа в критическую секцию задачи не выбираются до тех пор, пока вход в секцию не освободится;
- планирование с учетом «советов» программы.

Диспетчеризация задач с использованием динамических приоритетов

При выполнении программ может случиться ситуация, когда одна или несколько задач не могут быть выполнены в течение значительного времени из-за высокой нагрузки в вычислительной системе. Введение механизма динамических приоритетов позволяет реализовать быстрое выполнение коротких задач и гарантировать выполнение любых запросов. Эта дисциплина используется в ОС UNIX.
Каждый процесс имеет два атрибута приоритета, с учетом которого распределяется процессорное время между исполняющимися задачами:
- текущий приоритет, на основе которого осуществляется планирование;
- заказанный относительный приоритет (nice number).
Более высокому значению текущего приоритета может соответствовать более низкий фактический приоритет планирования.
Рассмотрим частный случай, когда текущий приоритет процесса варьируется в диапазоне от 0 (низкий приоритет) до 127 (высокий приоритет). Процессы, выполняющиеся в режиме задачи, имеют более низкий приоритет (0 – 65), чем в режиме ядра (66 – 95, системный диапазон). Приоритеты в диапазоне 96 – 127 относятся к процессам с фиксированным приоритетом.
Процессу, ожидающему недоступный в данный момент ресурс, система присваивает приоритет сна (sleep) из диапазона системных приоритетов и связанное с событием, вызвавшим это состояние. Когда процесс пробуждается, ему присваивается приоритет, равный приоритету сна, который находится в системной области, поэтому вероятность выбора такого процесса на выполнение велика. Такой подход позволяет быстро завершить системный вызов.
После завершения системного вызова восстанавливается приоритет режима задачи, сохраненный перед выполнением системного вызова. Это может привести к снижению приоритета и переключению контекста.
Для принятия решения о выборе следующего запускаемого процесса планировщику необходима информация об использовании процессора. Эта составляющая приоритета уменьшается обработчиком прерываний по таймеру по каждому тику таймера. Когда процесс выполняется в режиме задачи, его текущий приоритет линейно уменьшается.
Каждую секунду процессор пересчитывает приоритеты процессов, готовых к выполнению, что приводит к перемещению процессов в более приоритетные очереди и повышает вероятность их последующего запуска.
Данный алгоритм планирования обеспечивает:
- интересы низкоприоритетных процессов, так как в результате длительного ожидания их приоритет и вероятность выполнения увеличиваются;
- более вероятный выбор интерактивных процессов по сравнению с вычислительными.