Организация вычислительного процесса

5.1. Концепция процессов и потоков. Задание, процессы, потоки (нити), волокна

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

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

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

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

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

Процессы рассматриваются операционной системой как заявки или контейнеры для всех видов ресурсов, кроме одного – процессорного времени. Это важнейший ресурс распределяется операционной системой между другими единицами работы – потоками, которые и получили свое название благодаря тому, что они представляют собой последовательности (потоки выполнения) команд. Каждый процесс начинается с одного потока, но новые потоки могут создаваться (порождаться) процессом динамически. В простейшем случае процесс состоит из одного потока, и именно таким образом трактовалось понятие "процесс" до середины 80-х годов (например, в ранних версиях UNIX). В некоторых современных ОС такое положение сохранилось, т.е. понятие "поток" полностью поглощается понятием "процесс".

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

Взаимосвязь между заданиями, процессами и потоками показана на рис. 5.2.

Переключение потоков в ОС занимает довольно много времени, так как для этого необходимы переключение в режим ядра, а затем возврат в режим пользователя. Достаточно велики затраты процессорного времени на планирование и диспетчеризацию потоков. Для предоставления сильно облегченного псевдопараллелизма в Windows 2000 (и последующих версиях) используются волокна (Fiber), подобные потокам, но планируемые в пространстве пользователя создавшей их программой. У каждого потока может быть несколько волокон, с той разницей, что когда волокно логически блокируется, оно помещается в очередь блокированных волокон, после чего для работы выбирается другое волокно в контексте того же потока. При этом ОС "не знает" о смене волокон, так как все тот же поток продолжает работу.

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

Возникает вопрос: зачем нужна такая сложная организация работ, выполняемых операционной системой? Ответ нужно искать в развитии теории и практики мультипрограммирования, цель которой – в обеспечении максимально эффективного использования главного ресурса вычислительной системы – центрального процессора (нескольких центральных процессоров).

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

5.2. Мультипрограммирование. Формы многопрограммной работы

Мультипрограммирование призвано повысить эффективность использования вычислительной системы [10, 17]. Однако эффективность может пониматься по-разному. Наиболее характерными показателями эффективности вычислительных систем являются:

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

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

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

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

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

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

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

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

Интересная форма мультипрограммной работы связана с мультипроцессорной обработкой. Мультипроцессорная обработка – это способ организации вычислительного процесса в системе с несколькими процессорами, при котором несколько задач (процессов, потоков) могут одновременно выполняться на разных процессорах системы. Концепция мультипроцессирования не нова, она известна с 70-х годов, однако стала доступной в широком масштабе лишь в последнее десятилетие, особенно с появлением многопроцессорных ПК (часто в качестве серверов ЛВС).

В отличие от мультипрограммной обработки, в мультипроцессорных системах несколько задач выполняется одновременно, т.к. имеется несколько процессоров. Однако это не исключает мультипрограммной обработки на каждом процессоре. При этом резко усложняются все алгоритмы управления ресурсами, т.е. операционная система. Современные ОС, как правило, поддерживают мультипроцессирование (Sun Solaris 2.x, Santa Cruz Operation Open Server 3.x, OS/2, Windows NT/2000/2003/XP, NetWare, начиная с версии 4.1 и др.).

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

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

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

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

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

5.3. Управление процессами и потоками

Одной из основных подсистем любой современной мультипрограммной ОС, непосредственно влияющей на функционирование компьютера, является подсистема управления процессами и потоками. Основные функции этой подсистемы [10, 12, 17]:

К созданию процесса приводят пять основных событий:

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

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

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

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

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

Диспетчеризация заключается в реализации найденного в результате планирования решения, т.е. в переключении процессора с одного потока на другой. Диспетчеризация проходит в три этапа:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.4. Создание процессов и потоков. Модели процессов и потоков

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

Примерами таких описателей процесса являются [10, 17]:

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

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

Типичные элементы образа процесса приведены ниже.

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

При управлении процессами ОС использует два основных типа информационных структур: блок управления процессом ( дескриптор процесса) и контекст процесса. Дескрипторы процессов объединяются в таблицу процессов, которая размещается в области ядра. На основании информации, содержащейся в таблице процессов, ОС осуществляет планирование и синхронизацию процессов.

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

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

Информация по состоянию и управлению процессом включает следующие основные данные:

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

В контексте процесса содержится следующая основная информация [10]:

Следует заметить, что часть этой информации, известная как "слово состояния программы" (Program Status Word – PSW), фиксируется в специальном регистре процессора (например, в регистре EFLAGS в процессорах Pentium).

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

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

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

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

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

Есть два способа реализации пакета потоков [17]:

Рассмотрим эти способы, их преимущества и недостатки.

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

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

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

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

Таких процедур может быть по крайней мере четыре: thread-create, thread-exit, thread-wait и thread-yield, но обычно их больше. Библиотека подпрограмм для работы с потоками создает структуру данных для нового потока, а потом передает управление одному из готовых к выполнению потоков данного процесса, руководствуясь некоторым алгоритмом планирования. Когда управление переходит к библиотечной программе, контекст текущего процесса сохраняется в таблице потоков, а когда управление возвращается к потоку, его контекст восстанавливается. Все эти события происходят в пользовательском пространстве в рамках одного процесса. Ядро даже "не подозревает" об этой деятельности и продолжает осуществлять планирование процесса как единого целого и приписывать ему единое состояние выполнения.

Использование потоков на уровне пользователя имеет следующие преимущества [17]:

Однако имеются и недостатки по сравнению с использованием потоков на уровне ядра:

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

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

Возможно планирование работы нескольких потоков одного и того же процесса на нескольких процессорах:

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

5.5. Планирование заданий, процессов и потоков

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

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

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

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

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

Среднесрочное планирование является частью системы свопинга. Обычно решение о загрузке процесса в память принимается в зависимости от степени многозадачности (например, OS MFT, OS MVT). Кроме того, в системе с отсутствием виртуальной памяти среднесрочное планирование тесно связано с вопросами управления памятью.

Диспетчеризация сводится к следующему:

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

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

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

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

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

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

В первом случае механизм планирования распределяется между операционной системой и прикладными программами. Во втором случае функции планирования потоков целиком сосредоточены в операционной системе.

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

Однако почти во всех ОС (UNIX, Windows NT/2000/2003, OS/2, VAX/VMS и др.) реализованы вытесняющие алгоритмы планирования. В основе многих таких алгоритмов лежит концепция квантования. В соответствии с ней каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени – квант.

Смена активного потока происходит, если:

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

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

Некоторые потоки, получив квант времени, используют его не полностью, например, из-за необходимости выполнить ввод или вывод данных. В результате может возникнуть ситуация, когда потоки с интенсивным вводом-выводом используют только небольшую часть выделенного им процессорного времени. Можно исправить эту "несправедливость", изменив алгоритм планирования, например, так: создать две очереди потоков, очередь 1 – для потоков, которые пришли в состояние готовности в результате исчерпания кванта времени, и очередь 2 – для потоков, у которых завершилась операция ввода-вывода. При выборе потока для выполнения сначала просматривается вторая очередь, и если она пуста, квант выделяется потоку из первой очереди.

Отметим три замечания об алгоритмах, основанных на квантовании.

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

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

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

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

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

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

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

В качестве примера рассмотрим организацию приоритетного обслуживания в Windows 2000/2003/XP/Vista. Здесь приоритеты организованны в виде двух групп, или классов: реального времени и переменные. Каждая из групп состоит из 16 уровней приоритетов (рис. 5.10). Потоки, требующие немедленного внимания, находятся в классе реального времени, который включает такие функции, как осуществление коммуникаций и задачи реального времени [17].

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

Приоритеты из разных классов обрабатываются несколько по-разному. В классе приоритетов реального времени все потоки имеют фиксированный приоритет (от 16 до 31), который никогда не изменяется, и все активные потоки с определенным уровнем приоритета располагаются в круговой очереди данного класса (tкв=20 мс для W2K Professional, 120 мс – для однопроцессорных серверов).

В классе переменных приоритетов поток начинает работу с базового приоритета процесса, который может принимать значение от 1 до 15. Каждый поток, связанный с процессом имеет, свой базовый приоритет, равный базовому приоритету процесса, или отличающийся от него не более чем на 2 уровня в большую или меньшую сторону. После активации потока его динамический приоритет может колебаться в определенных пределах – он не может упасть ниже наименьшего базового приоритета данного класса, т.е. 15 (для потоков с приоритетом 16 и выше никогда не делается никаких изменений приоритетов).

Когда же увеличивается приоритет потока? Во-первых, когда завершается операция ввода-вывода и освобождается ожидающий ее поток, его приоритет увеличивается, чтобы дать шанс этому потоку запуститься быстрее и снова запустить операцию ввода-вывода. Суть в том, чтобы поддержать занятость устройств ввода-вывода. Величина, на которую увеличивается приоритет, зависит от устройства ввода-вывода. Как правило, это 1 – для диска, 2 – для последовательной линии, 6 – для клавиатуры и 8 – для звуковой карты.

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

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

Последняя модификация алгоритма планирования W2K заключается в том, что когда окно становится окном переднего плана, все его потоки получают более длительные кванты времени (величина прибавки хранится в системном реестре).

Поток, созданный в системе, может находиться в одном из 6 состояний в соответствии с графом, приведенным на рис. 5.11.

5.6. Взаимодействие и синхронизация процессов и потоков

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

Способы взаимодействия процессов (потоков) можно классифицировать по степени осведомленности одного процесса о существовании другого [10].

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

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

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

В случае конкурирующих процессов (потоков) возможно возникновение трех проблем. Первая из них – необходимость взаимных исключений (mutual exclusion). Предположим, что два или большее количество процессов требуют доступ к одному неразделяемому ресурсу, как например принтер (рис. 5.12). О таком ресурсе будем говорить как о критическом ресурсе, а о части программы, которая его использует, – как о критическом разделе (critical section) программы. Крайне важно, чтобы в критической ситуации в любой момент могла находиться только одна программа. Например, во время печати файла требуется, чтобы отдельный процесс имел полный контроль над принтером, иначе на бумаге можно получить чередование строк двух файлов.

Осуществление взаимных исключений создает две дополнительные проблемы. Одна из них – взаимоблокировки (deadlock) или тупики. Рассмотрим, например, два процесса – P1 и P2, и два ресурса – R1 и R2. Предположим, что каждому процессу для выполнения части своих функций требуется доступ к общим ресурсам. Тогда возможно возникновение следующей ситуации: ОС выделяет ресурс R1 процессу Р2, а ресурс R2 – процессу Р1. В результате каждый процесс ожидает получения одного из двух ресурсов. При этом ни один из них не освобождает уже имеющийся ресурс, ожидая получения второго ресурса для выполнения функций, требующих наличие двух ресурсов. В результате процессы оказываются взаимно заблокированными.

Очень удобно моделировать условия возникновения тупиков, используя направленные графы [17] (предложено Holt, 1972). Графы имеют 2 вида узлов: процессы-кружочки и ресурсы-квадратики. Ребро, направленное от квадрата (ресурса) к кружку (процессу), означает, что ресурс был запрошен, получен и используется. В нашем примере это будет изображено так, как показано на рис. 5.13 а).

Ребро, направленное от процесса (кружка) к ресурсу (квадрату), означает, что процесс в данный момент заблокирован и находится в состоянии ожидания доступа к этому ресурсу. В нашем примере граф надо достроить, как показано на рис. 5.13 б) или в). Цикл в графе означает наличие взаимной блокировки процессов.

Существует еще одна проблема у конкурирующих процессов – голодание. Предположим, что имеется 3 процесса ( Р1, Р2, Р3 ), каждому из которых периодически требуется доступ к ресурсам R. Представим ситуацию, в которой Р1 обладает ресурсом, а Р2 и Р3 приостановлены в ожидании освобождения ресурса R. После выхода Р1 из критического раздела доступ к ресурсу будет получен одним из процессов Р2 или Р3.

Пусть ОС предоставила доступ к ресурсу процессу Р3. Пока он работает с ресурсом, доступ к ресурсу вновь требуется процессу Р1. В результате по освобождении ресурса R процессом Р3 может оказаться, что ОС вновь предоставит доступ к ресурсу процессу Р1. Тем временем процессу Р3 вновь требуется доступ к ресурсу R. Таким образом, теоретически возможна ситуация, в которой процесс Р2 никогда не получит доступ к требуемому ему ресурсу, несмотря на то, что никакой взаимной блокировки в данном случае нет.

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

Однако в этом случае вносится новое требование синхронизации процессов для обеспечения согласованности данных.

Пусть имеются два процесса, представленные последовательностью неделимых (атомарных) операций:

P: a; b; c; и Q: d; e; f;

где a, b, c, d, e, f – атомарные операции.

При последовательном выполнении активностей мы получаем следующую последовательность атомарных действий:

PQ: a b c d e f

Что произойдет при исполнении этих процессов псевдопараллельно, в режиме разделения времени? Процессы могут расслоиться на неделимые операции с различным их чередованием, то есть может произойти то, что на английском языке принято называть словом interleaving. Возможные варианты чередования:

а b c d e f
a b d c e f
a b d e c f
a b d e f c
a d b c e f
......
d e f a b c

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

P: x=2;   y=x-1;           Q: x=3;   y=x+1

Что мы получим в результате их псевдопараллельного выполнения, если переменные x и y являются общими для процессов? Легко видеть, что возможны четыре разных набора значений для пары (x, y): (3, 4), (2, 1), (2, 3) и (3, 2). Будем говорить, что набор процессов детерминирован, если всякий раз при псевдопараллельном исполнении для одного и того же набора входных данных он дает одинаковые выходные данные. В противном случае он недетерминирован. Выше приведен пример недетерминированного набора программ. Понятно, что детерминированный набор активностей можно безбоязненно выполнять в режиме разделения времени. Для недетерминированного набора такое исполнение нежелательно.

Можно ли до получения результатов, заранее, определить, является ли набор активностей детерминированным или нет? Для этого существуют достаточные условия Бернстайна [17]. Изложим их применительно к программам с разделяемыми переменными.

Введем наборы входных и выходных переменных программы. Для каждой атомарной операции наборы входных и выходных переменных – это наборы переменных, которые атомарная операция считывает и записывает. Набор входных переменных программы R(P) ( R от слова read ) суть объединение наборов входных переменных для всех ее неделимых действий. Аналогично, набор выходных переменных программы W(P) ( W от слова write ) суть объединение наборов выходных переменных для всех ее неделимых действий. Например, для программы

P: x = u + v;   y = x * w;

получаем R(P) = {u, v, x, w}, W(P) = {x, y}. Заметим, что переменная x присутствует как в R(P), так и в W(P).

Теперь сформулируем условия Бернстайна.

Если для двух данных процессов P и Q:

тогда выполнение P и Q детерминировано.

Если эти условия не соблюдены, возможно, что параллельное выполнение P и Q детерминировано, но возможно, что и нет. Случай двух процессов естественным образом обобщается на их большее количество.

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

Про недетерминированный набор программ говорят, что он имеет race condition (состояние гонки, состояние состязания). В приведенном выше примере процессы состязаются за вычисление значений переменных x и y.

Задачу упорядоченного доступа к разделяемым данным (устранение race condition), в том случае, если нам не важна его очередность, можно решить, если обеспечить каждому процессу эксклюзивное право доступа к этим данным. Каждый процесс, обращающийся к разделяемым ресурсам, исключает для всех других процессов возможность одновременного с ним общения с этими ресурсами, если это может привести к недетерминированному поведению набора процессов. Такой прием называется взаимоисключением (mutual exclusion). Если очередность доступа к разделяемым ресурсам важна для получения правильных результатов, то одними взаимоисключениями уже не обойтись.

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

Поскольку в процессе передачи сообщений не происходит какого-либо совместного использования ресурсов, взаимоисключения не требуется, хотя проблемы взаимоблокировок и голодания остаются актуальными. В качестве примера взаимоблокировки можно привести ситуацию, при которой каждый из двух процессов заблокирован ожиданием сообщения от другого процесса. Голодание можно проиллюстрировать следующим образом. Пусть есть три процесса Р1, Р2, Р3, а те, в свою очередь, пытаются связаться с процессом Р1. Может возникнуть ситуация, когда Р1 и Р2 постоянно связываются друг с другом, а Р3 остается заблокированным, ожидая связи с процессом Р1.

5.7. Методы взаимоисключений

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

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

Наиболее простым решением поставленной задачи является организация пролога и эпилога запретом на прерывания:

while (some condition)
  {
    запретить все прерывания
    critical section
    разрешить все прерывания
    remainder section
  }

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

Тем не менее, запрет и разрешение прерываний часто применяются как пролог и эпилог к критическим секциям внутри самой операционной системы, например, при обновлении содержимого PSW (Programming Status Word).

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

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

shared int lock = 0;
while (some condition)
  {
    while(lock); lock = 1;
    critical section
    lock = 0;
    remainder section
  }

К сожалению, внимательное изучение показывает, что такое решение не удовлетворяет условию взаимоисключения, так как действие while(lock); lock = 1 ; не является атомарным. Допустим, что поток P0 протестировал значение переменной lock и принял решение двигаться дальше. В этот момент, еще до присваивания переменной lock значения 1, планировщик передал управление потоку P1. Он тоже изучает содержимое переменной lock и тоже принимает решение войти в критический участок. Мы получаем два процесса, одновременно выполняющих свои критические секции.

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

shared int turn = 0;
while (some condition)
  {
    while(turn != i);
    critical section
    turn = 1-i;
    remainder section
  }

Легко видеть, что взаимоисключение гарантируется, процессы входят в критическую секцию строго по очереди: P0, P1, P0, P1, P0, ... Но наш алгоритм не удовлетворяет условию прогресса. Например, если значение turn равно 1 и процесс P0 готов войти в критический участок, он не может сделать этого, даже если процесс P1 находится в remainder section.

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

shared int ready[2] = {0, 0};

Когда i-й процесс готов войти в критическую секцию, он присваивает элементу массива ready[i] значение, равное 1. После выхода из критической секции он, естественно, сбрасывает это значение в 0. Процесс не входит в критическую секцию, если другой процесс уже готов к входу в критическую секцию или находится в ней.

shared int turn = 0;
while (some condition)
  {
    ready[i] = 1;
    while(ready[1-i]);
    critical section
    ready[i] = 0;
    remainder section
  }

Полученный алгоритм обеспечивает взаимоисключение, позволяет процессу, готовому к входу в критический участок, войти в него сразу после завершения эпилога в другом процессе, но все равно нарушает условие прогресса. Пусть процессы практически одновременно подошли к выполнению пролога. После выполнения присваивания ready[0] = 1 планировщик передал процессор от процесса 0 процессу 1, который также выполнил присваивание ready[1] = 1. После этого оба процесса бесконечно долго ждут друг друга на входе в критическую секцию. Возникает ситуация, которую принято называть тупиковой (deadlock).

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

shared int ready[2] = {0, 0};
shared int turn;
while (some condition)
  {
    ready[i] = 1;
    turn =1- i; 
    while(ready[1-i]  turn == 1-i);
    critical section
    ready[i] = 0;
    remainder section
  }

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

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

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

О выполнении команды Test-and-Set, осуществляющей проверку значения логической переменной с одновременной установкой ее значения в 1, можно думать как о выполнении функции

int Test_and_Set (int *target)
  {
    int tmp = *target;
    *target = 1;
    return tmp;
  }

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

shared int lock = 0;
while (some condition)
  {
    while(Test_and_Set(lock));
    critical section
    lock = 0;
    remainder section
  }

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

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

5.8. Семафоры и мониторы

Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году. Семафор представляет собой целую переменную, принимающую неотрицательные значения, доступ любого процесса к которой, за исключением момента ее инициализации, может осуществляться только через две атомарные операции: P (от датского слова proberen – проверять) и V (от verhogen – увеличивать). Классическое определение этих операций выглядит следующим образом:

P(S): пока S == 0 процесс блокируется;
S = S - 1;
V(S): S = S + 1;

Эта запись означает следующее: при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается 1. Если оно меньше или равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1. При выполнении операции V над семафором S к его значению просто прибавляется 1.

Подобные переменные-семафоры могут с успехом использоваться для решения различных задач организации взаимодействия процессов. В ряде языков программирования они были непосредственно введены в синтаксис языка (например, в ALGOL-68), в других случаях применяются через использование системных вызовов. Соответствующая целая переменная располагается внутри адресного пространства ядра операционной системы. Операционная система обеспечивает атомарность операций P и V, используя, например, метод запрета прерываний на время выполнения соответствующих системных вызовов. Если при выполнении операции P заблокированными оказались несколько процессов, то порядок их разблокирования может быть произвольным, например, FIFO.

Одной из типовых задач, требующих организации взаимодействия процессов, является задача producer-consumer (производитель-потребитель). Пусть два процесса обмениваются информацией через буфер ограниченного размера. Производитель закладывает информацию в буфер, а потребитель извлекает ее оттуда. Грубо говоря, на этом уровне деятельность потребителя и производителя можно описать следующим образом:

Producer: while(1) 
  {
    produce_item;
    put_item;
  }
    Consumer:
    while(1)
 {
   get_item;
   consume_item;
  }

Если буфер забит, то производитель должен ждать, пока в нем появится место, чтобы положить туда новую порцию информации. Если буфер пуст, то потребитель должен дожидаться нового сообщения. Как можно реализовать эти условия с помощью семафоров? Возьмем три семафора empty, full и mutex. Семафор full будем использовать для гарантии того, что потребитель будет ждать, пока в буфере появится информация.

Семафор empty будем использовать для организации ожидания производителя при заполненном буфере, а семафор mutex – для организации взаимоисключения на критических участках, которыми являются действия put_item и get_item (операции "положить информацию" и "взять информацию" не могут пересекаться, поскольку возникнет опасность искажения информации). Тогда решение задачи выглядит так:

Semaphore mutex = 1;
Semaphore empty = N, где N – емкость буфера;
Semaphore full = 0;
Producer: while(1)
  {
    produce_item;
    P(empty);
    P(mutex);
    put_item;
    V(mutex);
    V(full);
  }
    Consumer: while(1) 
  {
   P(full);
   P(mutex);
   put_item;
   V(mutex);
   V(empty);
   consume_item;
  }

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

Хотя решение задачи producer-consumer с помощью семафоров выглядит достаточно элегантно, программирование с их использованием требует повышенной осторожности и внимания, чем, отчасти, напоминает программирование на языке ассемблера. Допустим, что в рассмотренном примере мы случайно поменяли местами операции P, сначала выполняя ее для семафора mutex, а уже затем для семафоров full и empty. Допустим теперь, что потребитель, войдя в свой критический участок ( mutex сброшен), обнаруживает, что буфер пуст. Он блокируется и начинает ждать появления сообщений. Но производитель не может войти в критический участок для передачи информации, так как тот заблокирован потребителем. Получаем тупиковую ситуацию.

В сложных программах произвести анализ правильности использования семафоров с карандашом в руках становится очень непростым занятием. В то же время обычные способы отладки программ зачастую не дают результата, поскольку возникновение ошибок зависит от interleaving'а атомарных операций, и ошибки могут быть трудно воспроизводимы. Для того чтобы облегчить труд программистов, в 1974 году Хоаром (Hoare) был предложен механизм еще более высокого уровня, чем семафоры, получивший название мониторов. Рассмотрим конструкцию, несколько отличающуюся от оригинальной.

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

monitor monitor_name 
  {
    описание переменных ;
    void m1(...){...
  }
   void m2(...)
  {
    ...
  }
    ...
    void mn(...)
  {
    ...
  }
  {
    блок инициализации внутренних переменных ;
  }

Здесь функции m1,..., mn представляют собой функции-методы монитора, а блок инициализации внутренних переменных содержит операции, которые выполняются только один раз: при создании монитора или при самом первом вызове какой-либо функции-метода до ее исполнения.

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

Однако одних только взаимоисключений недостаточно для того, чтобы в полном объеме реализовать решение задач, возникающих при взаимодействии процессов. Нам нужны еще и средства организации очередности процессов, подобно семафорам full и empty в предыдущем примере. Для этого в мониторах было введено понятие условных переменных (condition variables), над которыми можно совершать две операции – wait и signal, до некоторой степени похожие на операции P и V над семафорами.

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

Когда ожидаемое событие происходит, другой процесс внутри функции-метода совершает операцию signal над той же самой условной переменной. Это приводит к пробуждению ранее заблокированного процесса, и он становится активным. Если несколько процессов дожидались операции signal для этой переменной, то активным становится только один из них. Что нужно предпринять для того, чтобы не оказалось двух процессов, разбудившего и пробужденного, одновременно активных внутри монитора? Хор предложил, чтобы пробужденный процесс подавлял исполнение разбудившего процесса, пока он сам не покинет монитор. Несколько позже Хансен (Hansen) предложил другой механизм: разбудивший процесс покидает монитор немедленно после исполнения операции signal. Рассмотрим подход Хансена. Применим концепцию мониторов к решению задачи "производитель-потребитель".

monitor ProducerConsumer 
  {
    condition full, empty;
    int count;
    void put()
 {
    if(count == N) full.wait;
    put_item;
    count += 1;
   if(count == 1) empty.signal;
  }
    void get()
  {
   if (count == 0) empty.wait;
  get_item();
  count -= 1;
  if(count == N-1) full.signal;
  }
  {
    count = 0;
  }
    }
      Producer:
      while(1)
    {
    produce_item;ProducerConsumer.put();
    }
   Consumer:
   while(1)
     {
       ProducerConsumer.get();
       consume_item;
}

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

5.9. Взаимоблокировки (тупики)

Коффман и другие исследователи доказали, что для возникновения тупиковой ситуации должны выполняться четыре условия [37].

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

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

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

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

Рассмотрим методы обнаружения взаимоблокировок.

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

Например, пусть система из семи процессов (A, B, C, D, E, F, G) и шести ресурсов (R, S, T, V,W, U) в некоторый момент соответствует следующему списку [17].

1. Процесс A занимает ресурс R и хочет получить ресурс S.

Вопрос: заблокирована ли эта система, и если да, то какие процессы в этом участвуют?

Чтобы ответить на этот вопрос, нужно составить граф ресурсов и процессов (рис. 5.14).

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

Рассмотрим возможность обнаружения взаимоблокировок при наличии нескольких ресурсов каждого типа. Пусть имеется множество процессов P={P1, P2,... Pn}, всего n процессов, и множество ресурсов E={E1, E2,... Em}, где m – число классов ресурсов. В любой момент времени некоторые из ресурсов могут быть заняты и, соответственно, недоступны. Пусть А – вектор доступных ресурсов A={A1, A2,... Am}. Очевидно, что Aj<= Ej, j = 1, 2, …, m.

Введем в рассмотрение две матрицы:

C={ci,j| i = 1, 2,…, n; j = 1, 2, …, m} – матрица текущего распределения ресурсов, где ci,j – количество ресурсов j-ого класса, которые занимает процесс Pi ;

R={ri,j| i = 1, 2,…, n; j = 1,2, …, m} – матрица требуемых (запрашиваемых) ресурсов, ri,j – количество ресурсов j-ого класса, которые хочет получить процесс Pi.

Справедливо m соотношений по ресурсам:

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

Алгоритм обнаружения тупиков состоит из следующих шагов.

Когда нужно искать возникновение тупиков? Можно, конечно, проверять систему каждый раз, когда запрашивается очередной ресурс, это позволит обнаружить тупик максимально рано, но приведет к большим издержкам процессорного времени. Поэтому период проверки нужно выбрать: например, каждые К (сколько – нужно определить!) минут или когда процессор слабо загружен.

Предположим, обнаружен тупик. Какие методы можно использовать для его ликвидации? Здесь возможно несколько подходов.

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

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

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

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

5.10. Синхронизирующие объекты ОС

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

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

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

Потоки с помощью специального системного вызова (Wait (X), где Х – указатель на объект синхронизации) сообщают операционной системе о том, что они хотят синхронизировать свое выполнение с состоянием объекта Х. Системный вызов, с помощью которого поток может перевести объект синхронизации в сигнальное состояние, назовем Set(X).

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

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

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

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

Мьютекс (mutex – сокращение от mutual exclusion – взаимное исключение) – упрощенный семафор, не способный считать; он может управлять лишь взаимным исключением доступа к совместно используемым ресурсам или кодам. Реализация мьютекса полезна в случае потоков, действующих только в пространстве пользователя.

Объект "событие" обычно используется не для доступа к данным, а для того, чтобы оповестить другие потоки о том, что некоторые действия завершены.

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

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

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

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

Для прямой и непрямой адресации достаточно двух примитивов, чтобы описать передачу сообщений по линии связи – send и receive. В случае прямой адресации их можно обозначать так:

send(P, message) – послать сообщение message процессу P;

receive(Q, message) – получить сообщение message от процесса Q.

В случае непрямой адресации мы будем обозначать их так:

send(A, message) – послать сообщение message в почтовый ящик A;

receive(A, message) – получить сообщение message из почтового ящика A.

Примитивы send и receive уже имеют скрытый от наших глаз механизм взаимоисключения. Более того, в большинстве систем они уже имеют и скрытый механизм блокировки при чтении из пустого буфера и при записи в полностью заполненный буфер. Реализация решения задачи producer-consumer для таких примитивов становится тривиальной. Надо отметить, что, несмотря на простоту использования, передача сообщений в пределах одного компьютера происходит существенно медленнее, чем работа с семафорами и мониторами

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

Вызов удаленной процедуры (Remote Procedure Call, RPC) представляет собой способ, которым процесс А просит процесс В вызвать процедуру в адресном пространстве процесса В от имени процесса А и вернуть результат процессу А.

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

5.11. Аппаратно-программные средства поддержки мультипрограммирования

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

В зависимости от источника прерывания делятся на три класса (правда, это весьма условно, разные авторы классифицируют прерывания различно):

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

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

Программные прерывания отличаются от предыдущих классов тем, что они по своей сути не являются "истинными" (непредсказуемыми) прерываниями. Программное прерывание "запланировано" программистом и возникает при выполнении особой команды процессора, имитирующей прерывание, т.е. переход на новую последовательность инструкций. Например, такой командой в процессоре Pentium является INT, в процессорах Motorola – trap. Причинами использования таких команд являются:

Прерываниям приписывается приоритет, с помощью которого они ранжируются по степени важности и срочности. Операционные системы имеют специальные модули для работы с прерываниями – обработчики прерываний, или процедуры обслуживания прерываний (Interrupt Service Routine, ISR). Аппаратные прерывания обрабатываются драйверами соответствующих внешних устройств, исключения – специальными модулями ядра, а программные прерывания – процедурами ОС, обслуживающими системные вызовы. Кроме этих моделей, в ОС может быть диспетчер прерываний, координирующий работу отдельных обработчиков прерываний.

Аппаратная поддержка прерываний имеет свои особенности, зависящие от типа процессора и других аппаратных компонентов (контроллер внешнего устройства, шина подключения внешних устройств, контроллеры прерываний и др.). Существует два основных способа, с помощью которых шины выполняют прерывания: векторный (vectored) и опрашиваемый (polled). В обоих случаях процессору предоставляется информация об уровне приоритета прерывания на шине подключения внешних устройств. В случае векторных прерываний в процессор передается информация о начальном адресе программы обработки прерываний – обработчика прерывания.

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

Возможен комбинированный подход, сочетающий векторный и опрашиваемый типы прерываний. Такой подход реализован в ПК на основе процессоров Intel Pentium. Вектор прерываний в процессоре Pentium поставляет контроллер прерываний, который отображает поступающий от шины сигнала IRQ (Interrupt request) на определенный номер вектора. Вектор прерываний представляет собой число, указывающее на одну из 256 программ обработки прерываний, адреса которых хранятся в таблице обработчиков прерываний. В том случае, когда к каждой линии IRQ подключается только одно устройство, процедура прерываний работает как чисто векторная. Однако при совместном использовании одного уровня IRQ несколькими устройствами обработка прерываний реализуется по схеме опрашиваемых прерываний, т.е. в данном случае необходимо выполнить опрос всех устройств, подключенных к данному уровню IRQ (Interrupt Request).

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

Обобщенно последовательность действий аппаратных и программных средств по обработке прерываний можно представить следующим образом.

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

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

5.12. Системные вызовы

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

Реализация системных вызовов должна удовлетворять следующим требованиям [10, 17]:

Первое требование – переключение в привилегированный режим выполняется через механизм программных прерываний.

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

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

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

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

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

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

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

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