Тема 6. Взаимодействие процессов и ОС

6.1. Взаимодействие процесса с ОС. Интерфейс прикладных программ

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

6.2.1. Критические ресурсы и критические секции процессов

6.2.2. Использование блокировки памяти. Алгоритм Деккера

6.2.3. Семафорные примитивы Дийкстры. Мьютексы. Задачи "поставщик-потребитель", "читатели-писатели"

6.2.4. Объекты синхронизации Windows NT/2000/XP (Процесс, поток, задание, файл, консольный ввод, изменение в файловой системе, события с автосбросом или сбросом вручную, ожидаемый таймер с автосбросом или сбросом вручную, семафор, мьютекс, критическая секция)

6.2.5. Посылка синхронных сообщений

6.2.6. Вызовы удаленных процедур

6.2.7. Проблема тупиков

6.2.8. Мониторы

6.2.9. Синхронизация в распределенных системах

6.3. Взаимодействие процессов: обмен данными

6.3.1. Сигналы

6.3.2. Сообщения. Очереди сообщений, алгоритмы выборки сообщений и управления очередями сообщений

6.3.3. Файлы, проецируемые в память

6.3.4. Именованные и неименованные каналы

6.3.5. Почтовые ящики

6.3.6. Сокеты

Основные сокращения темы:

6.1. Взаимодействие процесса с ОС. Интерфейс прикладных программ

Интерфейс прикладных программ (API — Application Programming Interface) ­ – часть ОС, через которую происходит взаимодействие ОС с

Практически все операционные системы (Unix, Windows, Mac OS, и т. д.) имеют API, с помощью которого программисты могут создавать приложения для этой операционной системы. Главный API операционных систем — это множество системных вызовов.

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

С другой стороны, отличия в API различных операционных систем существенно затрудняют перенос приложений между платформами. Существуют различные методы обхода этой сложности — написание «промежуточных» API (API графических интерфейсов Qt, Gtk, и т. п.), написание библиотек, которые отображают системные вызовы одной ОС в системные вызовы другой ОС (такие среды исполнения, как Wine, cygwin, и т. п.), введение стандартов кодирования в языках программирования (например, стандартная библиотека языка C), написание интерпретируемых языков, реализуемых на разных платформах (sh, python, perl, php, tcl, Java, и т. д.).

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

Например: для того чтобы увидеть в браузере строчку «Hello, world!», достаточно лишь создать HTML-документ с минимальным заголовком и простейшим телом, содержащим данную строку. Что произойдёт, когда браузер откроет этот документ? Программа-браузер передаст имя файла (или уже открытый дескриптор файла) библиотеке, обрабатывающей HTML-документы, та, в свою очередь, при помощи API операционной системы прочитает этот файл и разберётся в его устройстве, затем последовательно вызовет через API библиотеки стандартных графических примитивов операции типа «очистить окошко», «написать выбранным шрифтом «Hello, world!». Во время выполнения этих операций библиотека графических примитивов обратится к библиотеке оконного интерфейса с соответствующими запросами, уже эта библиотека обратится к API операционной системы, чтобы записать данные в буфер видеокарты.

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

Основными сложностями существующих многоуровневых систем API, таким образом, являются:

Сложность портирования программного кода с одной системы API на другую (например, при смене ОС);

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

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

6.2.1 Критические ресурсы и критические секции процессов

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

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

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

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

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

Задача взаимного исключения может быть сформулирована следующим образом:

- в любой момент временитолько один процесс должен находиться в своей критической секции;

- ни один процесс не должен находиться в своей критической секции бесконечно долго;

- ни один процесс не должен бесконечно долго ждать входа в свою критическую секцию.

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

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

6.2.2 Использование блокировки памяти. Алгоритм Деккера

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

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

6.2.3 Семафорные примитивы. Мьютексы. Задачи "поставщик-потребитель", "читатели-писатели"

Понятие семафорных механизмов было введено Дейкстрой.

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

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

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

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

Использование средств взаимного исключения позволяет взаимодействующим процессам корректно обмениваться данными, чтобы правильно выполнялась их общая работа. Типичным примером взаимодействующих процессов, использующих разделяемые ресурсы, является задача ПОСТАВЩИК-ПОТРЕБИТЕЛЬ.

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

6.2.4 Объекты синхронизации Windows NT/2000/XP (Процесс, поток, задание, файл, консольный ввод, изменение в файловой системе, события с автосбросом или сбросом вручную, ожидаемый таймер с автосбросом или сбросом вручную, семафор, мьютекс, критическая секция)

Выполнить самостоятельно

6.2.5 Посылка синхронных сообщений

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

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

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

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

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

6.2.6 Вызовы удаленных процедур (RPC)

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

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

Асимметричность, то есть одна из взаимодействующих сторон является инициатором;

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

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

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

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

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

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

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

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

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

6.2.7 Проблема тупиков

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

Борьба с тупиковыми ситуациями основывается на одной из трех стратегий:

– предотвращение тупика;

– обход тупика;

– обнаружение тупика с последующим восстановлением работоспособности системы.

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

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

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

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

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

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

6.2.8 Мониторы

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

Монитор состоит из:

набора процедур, взаимодействующих с общим ресурсом,

мьютекса,

переменных, связанных с этим ресурсом,

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

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

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

6.2.9 Синхронизация в распределенных системах

Обычно децентрализованные алгоритмы имеют следующие свойства:

Относящаяся к делу информация распределена среди ЭВМ.

Процессы принимают решение на основе только локальной информации.

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

Не существует общих часов или другого источника точного глобального времени.

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

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

Алгоритм "задиры"

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

P посылает сообщение "ВЫБОРЫ" всем процессам с большими чем у него номерами.

Если нет ни одного ответа, то P считается победителем и становится координатором.

Если один из процессов с большим номером ответит, то он берет на себя проведение выборов. Участие процесса P в выборах заканчивается.

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

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

Круговой алгоритм.

Алгоритм основан на использовании кольца (физического или логического), но без маркера. Каждый процесс знает следующего за ним в круговом списке. Когда процесс обнаруживает отсутствие координатора, он посылает следующему за ним процессу сообщение "ВЫБОРЫ" со своим номером. Если следующий процесс не отвечает, то сообщение посылается процессу, следующему за ним, и т.д., пока не найдется работающий процесс. Каждый работающий процесс добавляет в список работающих свой номер и переправляет сообщение дальше по кругу. Когда процесс обнаружит в списке свой собственный номер (круг пройден), он меняет тип сообщения на "КООРДИНАТОР" и оно проходит по кругу, извещая всех о списке работающих и координаторе (процессе с наибольшим номером в списке). После прохождения круга сообщение удаляется.

6.3. Взаимодействие процессов: обмен данными

6.3.1 Сигналы

6.3.2 Сообщения. Очереди сообщений, алгоритмы выборки сообщений и управления очередями сообщений

6.3.3 Файлы, проецируемые в память

6.3.4 Именованные и неименованные каналы

6.3.5 Почтовые ящики

6.3.6 Сокеты

Самым распространенным средством взаимодействия процессов являются сокеты /sockets/. Программы подключаются к сокету и выдают запрос на привязку к нужному адресу. Затем данные передаются от одного сокета к другому в соответствии с указанным адресом.

Со́кеты (англ. socket — углубление, гнездо, разъём) — название программного интерфейса для обеспечения обмена данными между процессами. Процессы при таком обмене могут исполняться как на одной ЭВМ, так и на различных ЭВМ, связанных между собой сетью. Сокет — абстрактный объект, представляющий конечную точку соединения.

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

Интерфейс сокетов впервые появился в BSD Unix. Программный интерфейс сокетов описан в стандарте POSIX.1 и в той или иной мере поддерживается всеми современными операционными системами.

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

Каждый сокет имеет свой адрес. ОС семейства UNIX могут поддерживать много типов адресов, но обязательными являются INET-адрес и UNIX-адрес. Если привязать сокет к UNIX-адресу, то будет создан специальный файл (файл сокета) по заданному пути, через который смогут сообщаться любые локальные процессы путём чтения/записи из него (см. Доменный сокет Unix). Сокеты типа INET доступны из сети и требуют выделения номера порта.

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