636

41

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

Системы разделения времени призваны исправить основ-

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

42

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

Системы реального времени применяются для управле-

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

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

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

43

литной ОС можно назвать Windows 9x или ОС Linux. Ядро ОС Windows нельзя изменить, пользователям недоступны его исходные коды и у них нет программы для сборки (компиляции) этого ядра. А вот в случае работы с ОС Linux пользователи могут сами собрать ядро, отвечающее их потребностям, включив в него программные модули и драйверы, которые целесообразно, по их мнению, включить именно в ядро.

Вопросы для самопроверки

1.Дайте объяснение понятиям операционной среды и операционной системы.

2.В чем отличие между понятиями процесса и задачи?

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

4.Объясните значения следующих терминов: task (задача), process (процесс), thread (поток, нить). Как они между собой соотносятся?

5.Для чего каждая задача получает соответствующий дескриптор? Какие поля, как правило, содержатся в дескрипторе процесса (задачи)?

6.Объясните понятие ресурса. Почему понятие ресурса является одним из фундаментальных при рассмотрении ОС? Какие виды и типы ресурсов вы знаете?

7.Как вы считаете: сколько и каких списков дескрипторов задач может быть в системе? От чего должно зависеть это число?

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

9.С какой целью в ОС вводится специальный системный модуль, иногда называемый супервизором прерываний?

10.Приведите классификацию ОС?

44

2. УПРАВЛЕНИЕ ЗАДАЧАМИ

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

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

-создание и удаление задач;

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

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

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

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

ется организация очередей процессов и ресурсов [2]. Очевид-

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

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

45

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

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

чила название диспетчеризации.

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

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

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

46

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

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

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

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

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

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

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

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

Известно большое количество правил (дисциплин) диспетчеризации, в соответствии с которыми формируется список (очередь) готовых к выполнению задач. Различают два больших класса дисциплин диспетчеризации (дисциплин обслуживания) – бесприори-

тетные и приоритетные. При бесприоритетном обслуживании

47

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

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

вания отдельным задачам предоставляется преимущественное право попасть в состояние исполнения. Классификация дисциплин диспетчеризации приведена на рис. 2.1.

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

Рис. 2.1 − Дисциплины диспетчеризации

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

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

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

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

48

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

Рассмотрим кратко основные, наиболее часто используемые

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

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

вытесняющие (preemptive) и невытесняющие (nonpreemptive). В ранее разработанных пакетных ОС часто реализовывали параллельное выполнение заданий без принудительного перераспределения процессора между задачами. В большинстве современных ОС для мощных вычислительных систем, а также и в ОС для ПК, ориентированных на высокопроизводительное выполнение приложений (Windows NT, OS/2, Linux), реализована вытесняющая многозадачность. Можно сказать, что рассмотренная дисциплина относится к невытесняющим.

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

49

сколько и трудоемкие задания. Избежать этого недостатка позволяют дисциплины SJN и SRT.

Выполненные задачи

Очередь новых задач

Рис. 2.2 − Дисциплины диспетчеризации FCFS

Дисциплина обслуживания SJN (Shortest Job Next) пред-

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

50

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

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

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

циплина SRT (Shortest Remaining Time), в соответствии с кото-

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

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

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