Глава_1 (1085730), страница 8

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

Текст из файла (страница 8)

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

Send (destination, &message);

receive(source, &message);

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

Разработка систем передачи сообщений

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

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

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

Решение проблемы производителя и потребителя с передачей сообщений

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

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

Листинг 2.9. Решение проблемы производителя и потребителя с использованием N сообщений

#define N 100 /* количество сегментов в буфере */

void producer(void)

{

int item;

message m; /* буфер для сообщений */

while (TRUE) {

item = produce_item(); /* сформировать нечто, чтобы заполнить буфер */

receive(consumer, &m): /* ожидание прибытия пустого сообщения */

build_message(&m, item); /* сформировать сообщение для отправки */

send(consumer, &m); /* отослать элемент потребителю */

} }

void consumer(void)

{

int itern, i;

message m;

for (i = 0; i < N; i++) send(producer, &m): /* отослать N пустых сообщений */

while (TRUE) {

receive(producer, &m); /* получить сообщение с элементом */

item = extract_item(&m); /* извлечь элемент из сообщения */

send(producer, &m); /* отослать пустое сообщение */

consume_item(item); /* обработка элемента */

}}

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

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

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

Передача сообщений часто используется в системах с параллельным програм­мированием. Характерным примером системы передачи сообщений является MPI (Message-Passing Interface — интерфейс передачи сообщений).

Барьеры

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

Процессы

Барьер

а

Барьер

б

Барьер

с

Время

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

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

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

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

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

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

Классические проблемы межпроцессного взаимодействия

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

Проблема обедающих философов

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

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

Характеристики

Список файлов книги