23. Задачи синхронизации и взаимного исключения. Коллизии, критические ресурсы, критические секции. Задача обмена данными в многозадачной системе.

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

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

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

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

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

Для организации коммуникации между одновременно работающими процессами применяются средства межпроцессного взаимодействия (Interprocess Communication - IPC).

Выделяются три уровня средств IPC:

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

Удаленные IPC предоставляют механизмы, которые обеспечивают взаимодействие как в пределах одного процессора, так и между программами на различных процессорах, соединенных через сеть. Сюда относятся удаленные вызовы процедур (Remote Procedure Calls - RPC), сокеты Unix, а также TLI (Transport Layer Interface - интерфейс транспортного уровня) фирмы Sun.

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

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

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

Синхронный доступ. Если все процессы считывают данные из файла, то в большинстве случае проблем не возникает. Однако, при попытке одним из процессов изменить этот файл, могут возникнуть так называемые конкурентные ситуации (race conditions). Дисциплина доступа. Если нужно, чтобы как можно большее количество пользователей могли записывать данные, организуется так называемая очередь (по правилу один пишет, несколько читают). Практически организуется две очереди: одна - для чтения, другая - для записи. Такую дисциплину доступа можно организовать с помощью барьеров (блокировок). При этом создается общий барьер для считывателей, так как несколько процессов могут одновременно считывать данные, а также отдельный барьер для процесса-писателя. Такая организация предотвращает взаимные помехи в работе. Голодание процессов. Организация дисциплины доступа может привести к ситуации, когда процесс будет длительно ждать своей очереди для записи данных. Поэтому иногда нужно организовывать очереди с приоритетами. Управление потоком. Если нельзя точно определить, какой из процессов запрашивает или возвращает свои данные в нужный компьютер первым, используется так называемое взаимодействие по модели “клиент-сервер”. При этом используются один или несколько клиентов и один сервер. Клиент посылает запрос серверу, а сервер отвечает на него. После этого клиент должен дождаться ответа сервера, чтобы продолжать дальнейшее взаимодействие. Такое поведение называется управлением потоком. При одновременном доступе здесь также могут использоваться очереди с приоритетами. Тупик (deadlock). Классический тупик возникает, если процесс A получает доступ к файлу A и ждет освобождения файла B. Одновременно процесс B, получив доступ к файлу B, ждет освобождения файла A. Оба процесса теперь ждут освобождения ресурсов другого процесса и не освобождают при этом собственный файл. Тупика можно избежать, если ресурсы будут пронумерованы и предоставляться только в восходящем порядке номеров. Кроме того, все ресурсы должны освобождаться сразу после окончания использования. Каналы Канал (pipe) представляет собой средство связи стандартного вывода одного процесса со стандартным вводом другого. Каналы старейший из инструментов IPC, существующий приблизительно со времени появления самых ранних версий оперативной системы UNIX.

Для реализации IPC возможно использование полудуплексных и/или именованных каналов (FIFO).

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

in <—– Process Kernel out —–> Из этого рисунка легко увидеть, как файловые дескрипторы связаны друг с другом. Если процесс посылает данные через канал (fd0), он имеет возможность получить эту информацию из fd1. Однако этот простенький рисунок отображает и более глобальную задачу. Хотя канал первоначально связывает процесс с самим собой, данные, идущие через канал, проходят через ядро. В частности, в Linux каналы внутренне представлены корректным inode. Конечно, этот inode существует в пределах самого ядра, а не в какой-либо физической файловой системе. Эта особенность откроет нам некоторые привелекательные возможности для ввода/вывода, как мы увидим немного позже.

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

in <—– —–> in Parent Process Kernel Child Process out —–> <—– out

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

in <—– in Parent Process Kernel Child Process out <—– out Конструкция канала теперь полная. Чтобы использовать его, можно применять системные вызовы, подобные тем, которые нужны для ввода/вывода в файл или из файла на низком уровне (вспомним, что в действительности каналы внутренне представлены как корректный inode). Это означает, что для чтения из канала можно использовать вызов read(), а для записи - write().

Примечания:

Двусторонние каналы могут быть созданы посредством открывания двух каналов и правильным переопределением файловых дескрипторов в процессе-потомке. Вызов pipe() должен быть произведен ПЕРЕД вызовом fork(), или дескрипторы не будут унаследованы процессом-потомком! (то же для popen()). С полудуплексными каналами любые связанные процессы должны разделять происхождение. Поскольку канал находится в пределах ядра, любой процесс, не состоящий в родстве с создателем канала, не имеет способа адресовать его. Это не относится к случаю с именованными каналами (FIFOS). Именованные каналы (FIFO: First In First Out) Именованные каналы во многом работают так же, как и обычные каналы, но все же имеют несколько заметных отличий.

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

Если FIFO открыт для чтения, процесс его блокирует до тех пор, пока какой-нибудь другой процесс не откроет FIFO для записи.

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

Механизм передачи сигналов состоит из следующих частей:

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

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

Известно три варианта реакции на сигналы:

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

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

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

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

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

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

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

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

Двоичный семафор может принимать только значения 0 или 1. Считающий семафор может принимать целые неотрицательные значения.

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

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

увеличить значение; уменьшить значение; дождаться обнуления. Для выполнения первых двух операций у процесса должно быть право на изменение, для выполнения третьей достаточно права на чтение. Чтобы увеличить значение семафора, системному вызову semop следует передать требуемое число. Чтобы уменьшить значение семафора, нужно передать требуемое число, взятое с обратным знаком; если результат получается отрицательным, операция не может быть успешно выполнена. Для третьей операции нужно передать 0; если текущее значение семафора отлично от нуля, операция не может быть успешно выполнена.

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

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

Рис.1 Схема обмена через сокет

Сокеты находятся в областях связи (доменах). Домен сокета - это абстракция, которая определяет структуру адресации и набор протоколов. Сокеты могут соединяться только с сокетами в том же домене. Всего выделено 23 класса сокетов (см. файл <sys/socket.h>), из которых обычно используются только UNIX-сокеты и Интернет-сокеты. Сокеты могут использоваться для установки связи между процессами на отдельной системе подобно другим формам IPC.

Класс сокетов UNIX обеспечивает их адресное пространство для отдельной вычислительной системы. Сокеты области UNIX называются именами файлов UNIX. Сокеты также можно использовать, чтобы организовать связь между процессами на различных системах. Адресное пространство сокетов между связанными системами называют доменом Интернета. Коммуникации домена Интернета используют стек протоколов TCP/IP.

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

Основные типы сокетов Поточный - обеспечивает двухсторонний, последовательный, надежный, и недублированный поток данных без определенных границ. Тип сокета - SOCK_STREAM, в домене Интернета он использует протокол TCP.

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

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

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

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