Способы распределения времени центрального процессора сильно влияют и на скорость выполнения отдельных вычислений, и на общую эффективность вычислительной системы.
От выбранных механизмов распределения памяти между выполняющимися процессорами очень сильно зависит и эффективность использования ресурсов системы, и ее производительность.
Здесь не будем стараться разделять понятия процесс (process) и поток (thread), вместо этого используя обобщающий термин task (задача).
Операционная система выполняет следующие основные функции, связананнные с управлением задачами:
создание и удаление задач;
планирование процессов и диспетчеризация задач;
синхронизация задач, обеспечение их средствами коммуникации.
Создание и удаление задач осуществляется по соответствующим запросам от пользователей или от самих задач.
Созданный новый процесс необходимо разместить в основной памяти — следовательно, ему необходимо выделить часть адресного пространства. Новый порожденный поток текущего процесса необходимо включить в общий список задач, конкурирующих между собой за ресурсы центрального процессора.
Задача может породить новую задачу. При этом между процессами появляются «родственные» отношения. Порождающая задача называется «предком», «родителем», а порожденная — «потомком», «сыном» или «дочерней задачей». «Предок» может приостановить или удалить свою дочернюю задачу, тогда как «потомок» не может управлять «предком».
Если подобрать набор таких процессов, которые не будут конкурировать между собой за неразделяемые ресурсы при параллельном выполнении, то, скорее всего, процессы смогут выполниться быстрее (из-за отсутствия дополнительных ожиданий), да и имеющиеся в системе ресурсы будут использоваться более эффективно. Задача подбора такого множества процессов, что при выполнении они будут как можно реже конфликтовать из-за имеющихся в системе ресурсов, называется планированием вычислительных процессов.
Задача планирования процессов возникла очень давно — в первых пакетных ОС. В настоящее время актуальность этой задачи не так велика.
На первый план вышли задачи динамического (или краткосрочного) планирования, то есть текущего наиболее эффективного распределения ресурсов, возникающего практически при каждом событии. Задачи динамического планирования стали называть диспетчеризацией.
Иногда диспетчеризацию называют краткосрочным планированием.
Долгосрочный планировщик решает, какой из процессов, находящихся во входной очереди, должен быть переведен в очередь готовых процессов в случае освобождения ресурсов.
Краткосрочный планировщик решает, какая из задач, находящихся в очереди готовых к выполнению, должна быть передана на исполнение.
При рассмотрении стратегий планирования, как правило, идет речь о краткосрочном планировании, то есть о диспетчеризации.
Стратегия планирования определяет, какие процессы мы планируем на выполнение для того, чтобы достичь поставленной цели. Известно большое количество различных стратегий выбора процесса, которому необходимо предоставить процессор. Среди них, прежде всего, можно назвать следующие стратегии:
по возможности заканчивать вычисления (вычислительные процессы) в том же самом порядке, в котором они были начаты;
отдавать предпочтение более коротким процессам;
предоставлять всем пользователям (процессам пользователей) одинаковые услуги, в том числе и одинаковое время ожидания
Известно большое количество правил (дисциплин диспетчеризации), в соответствии с которыми формируется список (очередь) готовых к выполнению задач, различают два больших класса дисциплин обслуживания — бесприоритетные и приоритетные.
При бесприоритетном обслуживании выбор задачи производятся в некотором заранее установленном порядке без учета их относительной важности и времени обслуживания.
При реализации приоритетных дисциплин обслуживания отдельным задачам предоставляется преимущественное право попасть в состояние исполнения.
Самой простой в реализации является дисциплина FCFS (first come — first served), согласно которой задачи обслуживаются «в порядке очереди», то есть в порядке их появления. Те задачи, которые были заблокированы в процессе работы (попали в какое-либо из состояний ожидания, например, из-за операций ввода/вывода), после перехода в состояние готовности ставятся в эту очередь готовности перед теми задачами, которые еще не выполнялись.
Другими словами, образуются две очереди (см. рис.): одна очередь образуется из новых задач, а вторая очередь - из ранее выполнявшихся, но попавших в состояние ожидание.
К достоинствам этой дисциплины, прежде всего, можно отнести простоту реализации и малые расходы системных ресурсов на формирование очереди задач.
Однако эта дисциплина приводит к тому, что при увеличении загрузки вычислительной системы растет и среднее время ожидания обслуживания, причем короткие задания (требующие небольших затрат машинного времени) вынуждены ожидать столько же, сколько и трудоемкие задания. Избежать этого недостатка позволяют дисциплины SJN и SRT.
Дисциплина обслуживания SJN (shortest job next: следующим будет выполняться кратчайшее задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Необходимость сообщать ОС характеристики задач, в которых описывались бы потребности в ресурсах вычислительной системы, привела к тому, что были разработаны соответствующие языковые средства.
Пользователи должны были указывать предполагаемое время выполнения, и чтобы они не пытались указать заведомо меньшее время выполнения, ввели подсчет реальных потребностей. Диспетчер задач сравнивал заказанное время и время выполнения, и в случае превышения указанной оценки в данном ресурсе ставил данное задание не в начало, а в конец очереди.
Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. И задания, которые в процессе своего исполнения были временно заблокированы (например, ожидали завершения операций ввода/вывода), вновь попадают в конец очереди готовых к выполнению наравне с вновь поступающими.
Это приводит к тому, что задания, которым требуется очень немного времени для своего завершения, вынуждены ожидать процессор наравне с длительными работами, что не всегда хорошо.
Для устранения этого недостатка и была предложена дисциплина SRT (shortest remaining time, следующее задание требует меньше всего времени для своего завершения).
Все эти три дисциплины обслуживания могут использоваться для пакетных режимов обработки.
Для интерактивных же вычислений желательно прежде всего обеспечить приемлемое время реакции системы и равенство в обслуживании, если система является мультитерминальной.
Если же это однопользовательская система, но с возможностью мультипрограммной обработки, то желательно, чтобы те программы, с которыми мы сейчас непосредственно работаем, имели лучшее время реакции, нежели наши фоновые задания.
Для решения подобных проблем используется дисциплина обслуживания, называемая RR (round robin, круговая, карусельная), и приоритетные методы обслуживания.
Дисциплина обслуживания RR предполагает, что каждая задача получает процессорное время порциями (говорят: квантами времени, Time slice, q). После окончания кванта времени q задача снимается с процессора и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению.
Для оптимальной работы системы необходимо правильно выбрать закон, по которому кванты времени выделяются задачам.
Диспетчеризация без перераспределения процессорного времени, то есть не вытесняющая многозадачность (non-preemptive multitasking) — это такой способ диспетчеризации процессов, при котором активный процесс выполняется до тех пор, пока он сам, «по собственной инициативе», не отдаст управление диспетчеру задач для выбора из очереди другого, готового к выполнению процесса или треда.
Дисциплины обслуживания FCFS, SJN, SRT относятся к не вытесняющим.
Диспетчеризация с перераспределением процессорного времени между задачами, то есть вытесняющая многозадачность (preemptive multitasking) — это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается диспетчером задач, а не самой активной задачей.
При вытесняющей многозадачности механизм диспетчеризации задач целиком сосредоточен в операционной системе. При этом операционная система выполняет следующие функции:
определяет момент снятия с выполнения текущей задачи,
сохраняет ее контекст в дескрипторе задачи,
выбирает из очереди готовых задач следующую и запускает ее на выполнение, предварительно загрузив ее контекст.
Дисциплина RR и многие другие, построенные на ее основе, относятся к вытесняющим.
