Общие характеристики связи между процессами

* направление связи.

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

* тип адресации. В случае прямой адресации информация посылается непосредственно получателю, например, процессу P-Send (P, message). В случае непрямой или косвенной адресации информация помещается в некоторый промежуточный объект, например, в почтовый ящик;

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

* объем передаваемой информации и сведения о том, обладает ли канал буфером необходимого размера;

* синхронность обмена данными. Если отправитель сообщения блокируется до получения этого сообщения адресатом, то обмен считается синхронным, в противном случае - асинхронным

Основные способы обмена:

а) каналы

б) разделяемая память.

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

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

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

Двумя основными моделями передачи данных по каналу являются поток ввода-вывода и сообщения.

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

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

Сигналы

Сигнал – это нечто, что может быть послано процессу системой или другим процессом.

С сигналом не связано никакой информации, кроме номера (кода), указывающего, какой именно тип сигнала посылается.

При получении сигнала процесс прерывает свою текущую работу и переходит на выполнение функции, определенной как обработчик сигналов данного типа.

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

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

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

Сигналы вызывают прерывание задачи и выполнение заранее предусмотренных Действий.

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

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

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

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

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

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

Сообщения

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

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

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

Общая память

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

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

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

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

Программные каналы

Другое часто используемое средство обмена данными – программный канал (pipe; иногда переводится как «трубопровод»).

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

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

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

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

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

Конкуренция процессов в борьбе за ресурсы. Основные понятия и проблемы

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

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

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

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

Между конкурирующими процессами не происходит никакого обмена информацией.

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

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

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

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

О таком ресурсе будем говорить как о критическом ресурсе, а о части программы, которая его использует, - как о критическом разделе (секции) (critical section) программы.

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

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

Осуществление взаимных исключений создает две дополнительные проблемы. Одна из них - взаимоблокировки (deadlock) или тупики.

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

Рассмотрим, например, два процесса - Р1 и Р2 и два ресурса - R1 и R2. Предположим, что каждому процессу для выполнения части своих функций требуется доступ к общим ресурсам R1 и R2.

Тогда возможно возникновение следующей ситуации: ОС выделяет первоначально ресурс R1 процессу Р2, а ресурс R2 - процессу Р1.

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

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

Существует еще одна проблема у конкурирующих процессов - голодание.

Предположим, что имеются 3 процесса (P1, P2, РЗ), каждому из которых периодически требуется доступ к ресурсам R.

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

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

Синхронизация процессов и потоков. Основные понятия и проблемы

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

Синхронизация необходима для исключения гонок и тупиков при:

• обмене данными между потоками,

• разделении данных,

• при доступе к процессору

• при доступе устройствам ввода-вывода

• Во многих операционных системах эти средства называются средствами межпроцессного взаимодействия — Inter Process Communications (IPC), что отражает историческую первичность понятия «процесс» по отношению к понятию «поток».

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

• Выполнение потока в мультипрограммной среде всегда имеет асинхронный характер.

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

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

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

• При совместном использовании аппаратных ресурсов синхронизация также совершенно необходима.

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

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

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

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

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

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

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

1. Считать из файла базы данных в буфер запись о клиенте с заданным идентификатором.

2. Внести новое значение в поле Заказ (для потока А) или Оплата (для потока В).

3. Вернуть модифицированную запись в файл базы данных.

Обозначим соответствующие шаги для потока А как Al, A2 и A3, а для потока В как Bl, B2 и ВЗ.

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

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

Заметим, что в буфере у потока В находится запись о клиенте N, в которой поле Заказ имеет прежнее, не измененное значение.

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

После прерывания потока А и активизации потока В последний запишет в базу данных поверх только что обновленной записи о клиенте N свой вариант записи, в которой обновлено значение поля Оплата.

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

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

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

Или, напротив, все исправления были успешно внесены (рис. в).

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

Поэтому отладка взаимодействующих потоков является сложной задачей.

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

Рис. Влияние относительных скоростей потоков на результат решения задачи