4. Перечислите и поясните основные функции ОС, которые связаны с управлением задачами. Какие дисциплины диспетчеризации вы знаете?

Предмет: Операционные системы.
Вопрос: №4

***

Основные функции ОС, связанные с управлением задачами:

1.) создание и удаление задач (создание и удаление задач осуществляется по соответствующим запросам от пользова-телей или от самих задач. Задача может породить новую задачу. При этом между процессами появляются «родственные» отношения. Порождающая задача называ-ется «предком», «родителем», а порожден-ная – «потомком», «сыном» или «дочерней задачей». «Предок» может приостановить или удалить свою дочернюю задачу, тогда как «потомок» не может управлять «предком»);

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

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

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

3.) синхронизация задач, обеспечение их средствами коммуникации.

—————————————————————

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

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

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

Основные стратегии планирования:

1.) обеспечения соответствия порядка окончания вычислений (вычислительных процессов) последовательности, в которой они были приняты к исполнению;

2.) оказание предпочтения более коротким процессам;

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

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

Когда говорят о краткосрочном плани-ровании (диспетчеризации), то всегда в явном или неявном виде имеют ввиду понятие задачи  (потока). Если ОС не поддерживает механизм тредов, то можно заменить понятие задачи понятием процесса.

discipl-dispetcher

Различают 2 больших класса дисциплин диспетчеризации: бесприоритетные и приоритетные.

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

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

Приоритеты имеют следующие свойства:

1.) приоритет, присвоенный задаче, может являться величиной постоянной (статичес-кий приоритет);

2.) приоритет задачи может изменяться в процессе ее решения (динамический приоритет).

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

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

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

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

—————————————————————

Дисциплина FCFS (first come – first served) –

discipl-dispetcher2

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

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

—————————————————————

Дисциплина обслуживания SJN (Shortest Job Next) – предполагает, что следующим будет выполняться кратчайшее задание. Для ее реализации необходимо, чтобы для каждого задания была известна оценка в потребностях машинного времени. Необходимость сообщать ОС характерис-тики задач, в которых описывались бы потребности в ресурсах вычислительной системы, привела к тому, что были разработаны соответствующие языковые средства. Одним из наиболее известных был, в частности, язык управления заданиями JCL (Job Control Language).

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

Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. Задания, которые в процессе своего исполнения были временно заблокированы (например, ожидали завершения операций ввода/вывода), вновь попадают в конец очереди готовых к выполнению наравне с вновь поступающими. Это приводит к тому, что задания, которым требуется очень немного времени для своего завершения, вынуждены ожидать процессор наравне с длительными работами, что не всегда целесообразно.

Для устранения этого недостатка была предложена дисциплина, описанная ниже:

—————————————————————

Дисциплина SRT (Shortest Remaining Time) – следующим будет выполняться задание, требующее наименьшего времени для своего завершения.

—————————————————————

Итоги описанных выше дисциплин:

Три вышеназванные дисциплины обслу-живания могут использоваться для пакетных режимов обработки, когда для пользователя не является обязательным ожидание реакции системы: он просто сдает свое задание и через несколько часов получает результаты вычислений. Для интерактивных же вычислений желательно, прежде всего, обеспечить приемлемое время реакции системы и равенство в обслуживании, если система является мультитерминальной. Если же это однопользовательская система,

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

Для решения подобных проблем исполь-зуется дисциплина обслуживания, называ-емая RR (Round Robin, круговая, карусель-ная), и приоритетные методы обслуживания.

—————————————————————

Дисциплина RR (Round Robin) – предпола-гает, что каждая задача получает процессорное время порциями (квантами времени). После окончания кванта времени q задача снимается с процессора, и процессорное время передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению. Для оптимальной работы системы необходимо правильно выбрать закон, по которому кванты времени выделяются задачам.

discipl-dispetcher3

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

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

В своей простейшей реализации дисциплина карусельной диспетчеризации предполагает, что все задачи имеют одинаковый приоритет. Если же необходимо ввести механизм приоритетного обслуживания, то это, как правило, делается за счет организации нескольких очередей. Процессорное время будет предоставляться в первую очередь тем задачам, которые стоят в привилегированной очереди. Если она пуста, то диспетчер задач начнет просматривать остальные очереди. Именно по такому алгоритму действует диспетчер задач в операционных системах OS/2 и Windows NT.

—————————————————————

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

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

—————————————————————

Механизм динамических приоритетов в ОС Unix:

Вычисление приоритета процесса происходит следующим образом: Во-первых, в вычислении участвуют значения двух полей дескриптора процесса – p_nice и

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

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

Схема нумерации (числовых значений) текущих приоритетов различна для различных версий UNIX.

Рассмотрим частный случай, когда текущий приоритет процесса варьируется в диапазоне от 0 (низкий приоритет) до 127 (наивысший приоритет). Процессы, выполняющиеся в режиме задачи, имеют более низкий приоритет, чем в режиме ядра. Для режима задачи приоритет меняется в диапазоне 0–65, для режима ядра – 66–95 (системный диапазон). Процессы, приоритеты которых лежат в диапазоне 96 –127, являются процессами с фиксированным приоритетом, не изменяемым операционной системой, и предназначены для поддержки приложений

реального времени.

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