Системное программное обеспечение - Учебное пособие (Терехин А.Н.)

2         часть i. теоретические основы.

ВВЕДЕНИЕ.

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

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

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

обеспечение жизненного цикла процессов (порождение, выполнение и уничтожение процессов);

распределение ресурсов ВС;

синхронизацию процессов;

организацию межпроцессного взаимодействия.

Понятие процесса.

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

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

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

Некоторые типы процессов.    

 «Полновесные процессы»

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

«Легковесные процессы»

Наряду с «полновесными процессами» существуют и «легковесные процессы», они же нити, которые в той или иной степени присутствуют в различных операционных системах. При мультипрограммировании повышается пропускная способность системы, но отдельный процесс никогда не может быть выполнен быстрее, чем если бы он выполнялся в однопрограммном режиме. Однако задача, решаемая в рамках одного процесса, может обладать внутренним параллелизмом, который позволяет ускорить ее выполнение. Например, в ходе выполнения задачи происходит обращение к внешнему устройству, и на время этой операции можно не блокировать полностью выполнение процесса, а продолжить вычисления по другой "ветви" процесса. Для этих целей современные ОС предлагают использовать механизм многонитевой обработки (multithreading). При этом вводится новое понятие "нить" (thread). Нити, относящиеся к одному процессу, не настолько изолированы друг от друга, как процессы в традиционной многозадачной системе, между ними легко организовать тесное взаимодействие. Нити, или «легковесные процессы», во многих отношениях схожи с процессами. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити-потомки, могут переходить из состояния в состояние. Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находится в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выполняться. Нити разделяют процессор так, как это делают процессы, в соответствии с различными вариантами планирования.

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

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

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

Обобщая сказанное, отметим, что понятие процесса в любой ОС включает в себя:

исполняемый код;

собственное виртуальное адресное пространство;

совокупность ресурсов, выделенных данному процессу операционной системой;

хотя бы одну исполняемую нить.

Жизненный цикл процесса.

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

ПОРОЖДЕНИЕ – состояние процесса, когда он уже создан, но не готов к запуску, при этом создаются информационные структуры, описывающие данный процесс; загружается кодовый сегмент процесса в оперативную память или в область свопинга.

ВЫПОЛНЕНИЕ - активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

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

ГОТОВНОСТЬ - также пассивное состояние процесса: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.

ЗАВЕРШЕНИЕ – конечное состояние в жизненном цикле процесса, процесс выгружается из памяти и разрушаются все структуры данных, связанные с ним.

    Рис. 1 Общая схема состояний процесса.

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

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

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

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

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

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

 

Синхронизация параллельных процессов.

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

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

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

Таким образом, необходимо  уметь решать две важнейшие задачи:

Распределение ресурсов между процессами.

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

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

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

void echo()

     {

char in;

input(in);

output(in)

     }  

В данном примере мы используем некоторые условные функции input() и output(), так как в данный момент для нас неважно, как конкретно реализован ввод/вывод в данной системе. Поскольку такой кусок кода будет использоваться практически в любой программе, его удобно сделать разделяемым, когда ОС загружает в некоторую область памяти, доступную всем процессам, одну-единственную копию данной программы, и все процессы используют эту копию совместно. Заметим, что в этом случае переменная in является разделяемой. Представим теперь ситуацию, изображенную на Рис. 2:

 

Рис. 2 Конкуренция процессов за ресурс.

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

Процесс В тоже вызывает функцию echo(). После выполнения функции echo() переменная in содержит уж новое значение, считанное с клавиатуры.

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

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

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

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

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

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

Рис. 3 Возникновение тупиковой ситуации.

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

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

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

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

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

Способы реализации взаимного исключения.

Запрещение прерываний и специальные инструкции.

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

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

Для организации взаимного исключения на многопроцессорной системе с общей памятью могут использоваться специальные машинные инструкции. Примером такой инструкции может служить TSL – test and set lock, реализующая чтение ячейки памяти и запись нового значения в ту же ячейку как единую операцию. При этом гарантируется, что совокупность операций чтения и записи ячейки памяти является неделимой, т.е. доступ к ячейке памяти со стороны других процессоров блокируется на все время исполнения инструкции.  Вариацией этой идеи является специальная инструкция exchange, которая меняет местами содержимое регистра и ячейки памяти. Здесь опять гарантируется, что на все время выполнения инструкции доступ к ячейке памяти блокируется.

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

Алгоритм Петерсона.

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

Алгоритм Петерсона для случая 2х процессов представлен на Рис. 4.

 

Рис. 4 Алгоритм Петерсона

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

Активное ожидание.

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

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

Семафоры.

Первый из таких подходов был предложен Дейкстрой в 1965 г.  Дейкстра предложил новый тип данных, именуемый семафором.  Семафор представляет собой переменную целого типа, над которой определены две операции: down(P) и up(V).[2] Операция down проверяет значение семафора, и если оно больше нуля, то уменьшает его на 1. Если же это не так, процесс блокируется, причем операция down считается незавершенной.  Важно отметить, что вся операция является неделимой, т.е. проверка значения, его уменьшение и, возможно, блокирование процесса производятся как одно атомарное действие, которое не может быть прервано. Операция up увеличивает значение семафора на 1. При этом, если в системе присутствуют процессы, блокированные ранее при выполнении down на этом семафоре, ОС разблокирует один из них с тем, чтобы он завершил выполнение операции down, т.е. вновь уменьшил значение семафора. При этом также постулируется, что увеличение значения семафора и, возможно, разблокирование одного из процессов и уменьшение значения являются атомарной неделимой операцией.

Чтобы прояснить смысл использования семафоров для синхронизации, можно привести простую аналогию из повседневной жизни. Представим себе супермаркет, посетители которого, прежде чем войти в торговый зал, должны обязательно взять себе инвентарную тележку. В момент открытия магазина на входе имеется N свободных тележек – это начальное значение семафора. Каждый посетитель забирает одну из тележек (уменьшая тем самым количество оставшихся на 1) и проходит в торговый зал – это аналог операции down. При выходе посетитель возвращает тележку на место, увеличивая тележек на 1 – это аналог операции up. Теперь представим себе, что очередной посетитель обнаруживает, что свободных тележек нет – он вынужден блокироваться на входе в ожидании появления тележки. Когда один из посетителей, находящихся в торговом зале, покидает его, посетитель, ожидающий тележку, разблокируется, забирает тележку и проходит в зал. Таким образом, наш семафор в виде тележек позволяет находиться в торговом зале (аналоге критической секции) не более чем N посетителям одновременно. Положив N = 1, получим реализацию взаимного исключения. Семафор,  начальное (и максимальное) значение которого равно 1, называется двоичным семафором (так как имеет только 2 состояния: 0 и 1). Использование двоичного семафора для организации взаимного исключения проиллюстрировано на Рис. 5.

Рис. 5 Взаимное исключение с использованием семафора

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

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

Мониторы.

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

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

Процесс «входит» в монитор путем вызова одной из его процедур

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

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

Дополнительная синхронизация: переменные-условия.

Помимо обычных структур данных, мониторы могут включать в себя специальные переменные-условия, на которых определены операции wait и signal. Они используются для синхронизации. Если процесс, находящийся внутри монитора (т.е. исполняющий одну из его процедур), обнаруживает, что логически он не может продолжать выполнение, пока не выполнится определенное условие (например, буфер для записи данных переполнился), он вызывает операцию wait над определенной переменной-условием. При этом его дальнейшее выполнение блокируется, и это позволяет другому процессу, ожидающему входа в монитор, попасть в него. В дальнейшем, если этот другой процесс произведет некоторые действия, которые приведут к изменению обстоятельств (в нашем примере – считает часть данных из буфера), он должен вызвать для соответствующей переменной-условия операцию signal, что позволит разблокировать ожидающий процесс. Тонкость заключается в том, что разблокированный процесс, как и тот, кто его разблокировал, должен оказаться внутри монитора, но нахождение двух процессов внутри монитора одновременно невозможно по определению. Хоар постулировал, что в этом случае процесс, вызвавший signal, приостанавливается. Хансен в своей модификации мониторов в 1975 г. предложил более простое дополнительное условие: вызов signal должен быть самым последним внутри процедуры монитора, чтобы процесс немедленно после его выполнения покинул монитор. Заметим, что переменные-условия используются в мониторах не для организации взаимного исключения (оно постулируется самим определением монитора), а для дополнительной синхронизации процессов. В нашем примере разделяемый ресурс – буфер для чтения/записи охраняется от одновременного доступа по чтению и по записи самим монитором, а переменная-условие предохраняет пишущий процесс от затирания ранее записанных данных.

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

Обмен сообщениями.

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

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

send(destination, message)

receive(source, message)

Как и семафоры, и в отличие от мониторов, эти примитивы являются системными вызовами, а не конструкциями языка.

Рассмотрим основные особенности, которыми может обладать та или иная система обмена сообщениями.

Синхронизация.

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

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

Блокирующий send и блокирующий receive – эта схема известна под названием «схемы рандеву». Она не требует буферизации сообщений и часто используется для синхронизации процессов

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

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

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

Адресация.

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

Иное решение заключается в том, чтобы предоставить специальную структуру данных – почтовый ящик, или очередь сообщений, которая по сути своей является буфером, рассчитанным на определенное количество сообщений. В этом случае сообщения адресуются не процессам, а почтовым ящикам, при этом один и тот же ящик может использоваться и несколькими отправителями, и несколькими получателями. Такая схема, называемая косвенной адресацией, обеспечивает дополнительную гибкость.  Заметим, что связь между процессом-получателем или отправителем и почтовым ящиком может быть не только статической (т.е. раз навсегда заданной при создании ящика), но и динамической; в последнем случае для установления  и разрыва связи используются дополнительные примитивы (connect/disconnect). Кроме того, поскольку почтовый ящик является самостоятельным объектом, необходимо наличие примитивов создания и удаления ящика (create/destroy).

Длина сообщения.

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

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

Классические задачи синхронизации процессов.

«Обедающие философы»

Рассмотрим одну из классических задач, демонстрирующих проблему разделения доступа к критическим ресурсам – «задачу об обедающих философах» [2]. Данная задача иллюстрирует ситуацию, когда процессы конкурируют за право исключительного доступа к ограниченному числу ресурсов. Пять философов собираются за круглым столом, перед каждым из них стоит блюдо со спагетти, и между каждыми двумя соседями лежит вилка. Каждый из философов некоторое время размышляет, затем берет две вилки (одну в правую руку, другую в левую) и ест спагетти, затем кладет вилки обратно на стол и опять размышляет и так далее. Каждый из них ведет себя независимо от других, однако вилок запасено ровно столько, сколько философов, хотя для еды каждому из них нужно две. Таким образом, философы должны совместно использовать имеющиеся у них вилки (ресурсы). Задача состоит в том, чтобы найти алгоритм, который позволит философам организовать доступ к вилкам таким образом, чтобы каждый имел возможность насытиться, и никто не умер с голоду.

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

#define N 5                              /* число философов*/

void philosopher (int i)           /* i – номер философа от 0 до 4*/

{

while (TRUE)

          {

think();                                    /*философ думает*/

take_fork(i);                            /*берет левую вилку*/

take_fork((i+1)\%N);                /*берет правую вилку*/

eat();                              /*ест*/

put_fork(i);                              /*кладет обратно левую вилку*/    

put_fork((i+1)\%N);                 /* кладет обратно правую вилку */

}

}

Функция take_fork() описывает поведение философа по захвату вилки: он ждет, пока указанная вилка не освободится, и забирает ее. 

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

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

# define N 5                             /* количество философов */

# define LEFT (i-1)\%N  /* номер легого соседа для i-ого философа */

# define RIGHT (i+1)\%N        /* номер правого соседа для i-ого философа*/

# define THINKING 0                      /* философ думает */

# define HUNGRY 1                         /* философ голоден */

# define EATING 2                           /* философ ест */

 

typedef int semaphore;  /* тип данных «семафор» */

int state[N];                    /* массив состояний философов */

semaphore mutex=1;     /* семафор для критической секции */

semaphore s[N];   /* по одному семафору на философа */

 

void philosopher (int i) 

/* i : номер философа от 0 до N-1 */

{

while (TRUE)                          /* бесконечный цикл */

{

think();                           /* философ думает */

take_forks(i);        /*философ берет обе вилки  или блокируется */

eat();                              /* философ ест */

put_forks(i);         /* философ освобожает обе вилки */

}

}

 

void take_forks(int i)    

/* i : номер философа от 0 до N-1 */

{

down(&mutex);             /* вход в критическую секцию */

state[i] = HUNGRY;      /*записываем, что i-ый  философ голоден */

test(i);                   /* попытка взять обе вилки */

up(&mutex);        /* выход из критической секции */

down(&s[i]);         /* блокируемся, если вилок нет */

}

 

void put_forks(i) 

                   /* i : номер философа от 0 до N-1 */

{

down(&mutex);             /* вход в критическую секцию */

state[i] = THINKING;    /* философ закончил есть */

test(LEFT);

/* проверить может ли левый сосед сейчас есть */

test(RIGHT);  

/* проверить может ли правый сосед сейчас есть*/

up(&mutex);        /* выход из критической секции */

}

 

void test(i) 

                   /* i : номер философа от 0 до N-1 */

{

if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING)

{

state[i] = EATING;

up (&s[i]);

}

}

Задача «читателей и писателей»

Другой классической задачей синхронизации доступа к ресурсам является задача «читателей и писателей» [2], иллюстрирующая широко распространенную модель совместного доступа к данным. Представьте себе ситуацию, например, в системе резервирования билетов, когда множество конкурирующих процессов хотят читать и обновлять одни и те же данные. Несколько процессов могут читать данные одновременно, но когда один процесс начинает записывать данные (обновлять базу данных проданных билетов), ни один другой процесс не должен иметь доступ к данным, даже для чтения. Возникает вопрос, как спланировать работу такой системы? Одно из решений представлено ниже:

typedef int semaphore;  /* тип данных «семафор» */ 

semaphore mutex = 1;   /* контроль за доступом к «rc» (разделямый  ресурс) */

semaphore db = 1;         /* контроль за доступом к базе данных */

int rc = 0;    /* кол-во процессов читающих или пишущих */

 

void reader (void)

{

while (TRUE)                          /* бесконечный цикл */

{

down(&mutex);    /* получить эксклюзивный доступ к «rc»*/

rc = rc + 1;           /* еще одним читателем больше */

if (rc == 1) down(&db);           /* если это первый читатель, нужно заблокировать эксклюзивный доступ к базе */                

up(&mutex);                  /*освободить ресурс rc */

read_data_base(); /* доступ к данным */

down(&mutex);    /*получить эксклюзивный доступ к «rc»*/

rc = rc - 1:   /* теперь одним читателем меньше */

if (rc == 0) up(&db);      /*если это был последний читатель, разблокировать эксклюзивный доступ к базе данных */

up(&mutex);        /*освободить разделяемый ресурс rc */

use_data_read();   /* некритическая секция */

}

}

 

void writer (void)

{

          while(TRUE)                           /* бесконечный цикл */

          {

                   think_up_data();  /* некритическая секция */

down(&db);          /* получить эксклюзивный доступ к данным*/

                   write_data_base();         /* записать данные */

up(&db);     /* отдать эксклюзивный доступ */

          }

}

В этом примере, первый процесс, обратившийся к базе данных по чтению, осуществляет операцию down() над семафором db, тем самым блокируя эксклюзивный доступ к базе, который нужен для записи. Число процессов, осуществляющих чтение в данный момент, определяется переменной rc (обратите внимание! Так как переменная rc является разделяемым ресурсом – ее изменяют все процессы, обращающиеся к базе данных по чтению – то доступ к ней охраняется семафором mutex). Когда читающий процесс заканчивает свою работу, он уменьшает значение rc на единицу. Если он является последним читателем, он также совершает операцию up над семафором db, тем самым разрешая заблокированному писателю, если таковой имелся, получить эксклюзивный доступ к базе для записи.

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

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