Добавлен: 29.10.2018
Просмотров: 48033
Скачиваний: 190
2.3. Взаимодействие процессов
171
рующий данные и помещающий их в общий буфер. У потребителя есть аналогичный
бесконечный цикл, извлекающий данные из общего буфера и производящий над ними
некие полезные действия.
Интересующей нас частью этой программы является класс our_monitor, который со-
держит буфер, управляющие переменные и два синхронизированных метода. Когда
производитель активен внутри метода insert, он знает наверняка, что потребитель
не может быть активен внутри метода remove, что позволяет обновлять переменные
и буфер без опасений создать условия для состояния состязательности. В переменной
count отслеживается количество записей, находящихся в буфере. Она может принимать
любые значения от 0 и до N − 1 включительно. Переменная lo является индексом места
в буфере, откуда будет извлечена следующая запись. Аналогично этому переменная hi
является индексом места в буфере, куда будет помещена следующая запись. Допусти-
мо равенство lo = hi, которое означает, что в буфере находится либо 0, либо N записей.
Значение count указывает на суть создавшейся ситуации.
Синхронизированные методы в Java существенно отличаются от классических мо-
ниторов: в Java отсутствуют встроенные условные переменные. Вместо них этот
язык предлагает две процедуры, wait и notify, которые являются эквивалентами sleep
и wakeup, за исключением того, что при использовании внутри синхронизированных
методов они не могут попасть в состязательную ситуацию. Теоретически метод wait
может быть прерван, для чего, собственно, и предназначен весь окружающий его код.
Java требует, чтобы обработка исключений проводилась в явном виде. В нашем случае
нужно просто представить, что использование метода go_to_sleep — это всего лишь
способ приостановки работы.
Благодаря автоматизации взаимного исключения входа в критические области монито-
ры (по сравнению с семафорами) позволяют снизить уровень ошибок при параллель-
ном программировании. Тем не менее у них тоже имеется ряд недостатков. Недаром оба
наших примера мониторов приведены на языке Pidgin Pascal, а не на C, как все другие
примеры в этой книге. Как уже упоминалось, мониторы являются понятием языка
программирования. Компилятор должен их распознать и каким-то образом устроить
взаимное исключение. C, Pascal и большинство других языков не имеют мониторов,
поэтому не имеет смысла ожидать от их компиляторов реализации каких-нибудь пра-
вил взаимного исключения. И действительно, как компилятор сможет узнать, какие
процедуры были в мониторах, а какие нет?
В этих языках нет и семафоров, но их легко добавить: нужно всего лишь дополнить
библиотеку двумя короткими подпрограммами на ассемблере, чтобы получить си-
стемные вызовы up и down. Компиляторам даже не нужно знать, что они существуют.
Разумеется, операционная система должна знать о семафорах, но во всяком случае,
если у вас операционная система, использующая семафоры, вы можете создавать
пользовательские программы для нее на C или С++ (или даже на ассемблере, если
вам настолько нечем больше заняться). Для использования мониторов нужен язык,
в который они встроены.
Другая особенность, присущая мониторам и семафорам, состоит в том, что они раз-
работаны для решения проблем взаимного исключения при работе с одним или не-
сколькими центральными процессорами, имеющими доступ к общей памяти. Помещая
семафоры в общую память и защищая их командами TSL или XCHG, мы можем из-
бежать состязательной ситуации. При переходе к распределенной системе, состоящей
из связанных по локальной сети нескольких центральных процессоров, у каждого из
172
Глава 2. Процессы и потоки
которых имеется собственная память, эти примитивы становятся непригодными. Сле-
дует сделать вывод, что семафоры имеют слишком низкоуровневую природу, а мони-
торы бесполезны, за исключением небольшого количества языков программирования.
К тому же ни один из примитивов не позволяет осуществлять информационный обмен
между машинами. Здесь нужно что-то иное.
2.3.8. Передача сообщений
Этим другим средством является передача сообщений. Этот метод взаимодействия
процессов использует два примитива, send и receive, которые, подобно семафорам и в
отличие от мониторов, являются системными вызовами, а не конструкциями языка.
Как таковые они легко могут быть помещены в библиотечные процедуры, например:
send(destination, &message);
или
receive(source, &message);
Первый вызов отправляет сообщение заданному получателю, а второй получает со-
общение из заданного источника (или из любого источника, если получателю все
равно). Если доступные сообщения отсутствуют, получатель может заблокироваться
до их поступления. Или же он может немедленно вернуть управление с кодом ошибки.
Проблемы разработки систем передачи сообщений
Системы передачи сообщений имеют массу сложных проблем разработки, которых не
возникает при использовании семафоров или мониторов, особенно если взаимодей-
ствующие процессы проходят на различных машинах, связанных между собой по сети.
К примеру, сообщение может быть утрачено при передаче по сети. Чтобы застраховаться
от утраты сообщений, отправитель и получатель должны договориться о том, что как
только сообщение будет получено, получатель должен отправить в ответ специальное
подтверждение
. Если по истечении определенного интервала времени отправитель не
получит подтверждение, он отправляет сообщение повторно.
Листинг 2.11. Решение задачи производителя-потребителя на языке Java
public class ProducerConsumer {
static final int N = 100; // константа, задающая размер буфера
static producer p = new producer( ); // создание экземпляра потока
// производителя
static consumer c = new consumer( ); // создание экземпляра потока
// потребителя
static our monitor mon = new our monitor( ); // создание экземпляра
// монитора
public static void main(String args[ ]) {
p.start( ); // запуск потока производителя
c.start( ); // запуск потока потребителя
}
static class producer extends Thread {
public void run( ) { // код потока содержится в методе run
int item;
2.3. Взаимодействие процессов
173
while (true) { // цикл производителя
item = produce item( );
mon.insert(item);
}
}
private int produce_item( ) { ... } // производство записей
}
static class consumer extends Thread {
public void run( ) { // код потока содержится в методе run
int item;
while (true) { // цикл потребителя
item = mon.remove( );
consume_item(item);
}
}
private void consume_item(int item) { ... } // потребление записи
}
static class our_monitor { // монитор
private int buffer[ ] = new int[N];
private int count = 0, lo = 0, hi = 0; // счетчики и индексы
public synchronized void insert(int val) {
if (count == N) go_to_sleep( ); // если буфер полон, приостановка
buffer [hi] = val; // помещение записи в буфер
hi = (hi + 1) %N; // место для следующей записи
count = count + 1; // теперь в буфере появилась еще одна запись
if (count == 1) notify( ); // если потребитель был приостановлен,
// его нужно активизировать
}
public synchronized int remove( ) {
int val;
if (count == 0) go_to_sleep( ); // если буфер пуст, приостановка
val = buffer [lo]; // извлечение записи из буфера
lo = (lo + 1) %N; // место извлечения следующей записи from
count = count − 1; // в буфере стало на одну запись меньше
buffer
if (count == N − 1) notify( ); // если производитель был приостановлен,
// его нужно активизировать
return val;
}
private void go_to_sleep() { try{wait();} catch(InterruptedException exc) {};}
}
}
Теперь рассмотрим, что получится, если сообщение было успешно получено, а под-
тверждение, возвращенное отправителю, утрачено. Отправитель заново передаст со-
общение, и оно придет к получателю повторно. Важно, чтобы получатель мог отличить
новое сообщение от повторно переданного старого. Обычно эта проблема решается за
счет присвоения всем оригинальным сообщениям последовательно идущих номеров.
Если получателю приходит сообщение, несущее тот же самый серийный номер, что
и предыдущее, он знает, что это дубликат, который можно проигнорировать. Органи-
зация успешной передачи информации в условиях ненадежной передачи сообщений
является основной частью учебного курса по компьютерным сетям.
174
Глава 2. Процессы и потоки
Системе передачи сообщений приходится также решать вопрос о том, как именовать
процессы, чтобы однозначно указывать процесс в вызовах отправки — send или
получения — receive. Для системы передачи сообщений важна и проблема аутен-
тификации
: как клиент может отличить связь с реальным файловым сервером от
связи с самозванцем?
На другой стороне этого спектра, где отправитель и получатель находятся на одной
и той же машине, конструирование также не обходится без серьезных проблем. Одна
из них касается производительности. Копирование сообщений из одного процесса
в другой всегда проводится медленнее, чем операции с семафорами или вход в монитор.
На повышение эффективности передачи сообщений было затрачено немало усилий.
Решение задачи производителя-потребителя
с помощью передачи сообщений
Теперь давайте рассмотрим, как с помощью передачи сообщений и без использования
общей памяти может решаться задача производителя-потребителя. Решение этой
задачи показано в листинге 2.12. Будем исходить из предположения, что все сообще-
ния имеют один и тот же размер и что переданные, но еще не полученные сообщения
буферизуются автоматически средствами операционной системы. В этом решении
всего используется N сообщений, что аналогично N местам в буфере, организованном
в общей памяти. Потребитель начинает с того, что посылает N пустых сообщений
производителю. Как только у производителя появится запись для передачи потре-
бителю, он берет пустое сообщение и отправляет его назад в заполненном виде. При
этом общее количество сообщений в системе остается постоянным, поэтому они могут
быть сохранены в заданном, заранее известном объеме памяти.
Листинг 2.12. Решение задачи производителя-потребителя с помощью
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 item, i;
message m;
for (i = 0; i < N; i++) send(producer, &m); /* отправка N пустых
сообщений */
while (TRUE) {
2.3. Взаимодействие процессов
175
receive(producer, &m); /* получение сообщения с записью */
item = extract_item(&m); /* извлечение записи из сообщения */
send(producer, &m); /* возвращение пустого ответа */
consume_item(item); /* обработка записи */
}
}
Если производитель работает быстрее потребителя, все сообщения в конце концов ста-
новятся заполненными, ожидая потребителя; производитель должен будет заблокиро-
ваться, ожидая возвращения пустого сообщения. Если потребитель работает быстрее, то
получается обратный эффект: все сообщения опустошатся, ожидая, пока производитель
их заполнит, и потребитель заблокируется в ожидании заполненного сообщения.
Доступно множество вариантов передачи сообщений. Для начала рассмотрим способ
адресации сообщений. Можно присвоить каждому процессу уникальный адрес и адре-
совать сообщения процессам. Можно также изобрести новую структуру данных, на-
зываемую почтовым ящиком. Этот ящик представляет собой место для буферизации
конкретного количества сообщений, которое обычно указывается при его создании.
При использовании почтовых ящиков в качестве параметров адреса в вызовах send
и receive указываются почтовые ящики, а не процессы. Когда процесс пытается послать
сообщение заполненному почтовому ящику, он приостанавливается до тех пор, пока
из этого почтового ящика не будет извлечено сообщение, освобождая пространство
для нового сообщения.
При решении задачи производителя-потребителя оба они, и производитель и потреби-
тель, создадут почтовые ящики, достаточные для размещения N сообщений. Произво-
дитель станет отправлять сообщения, содержащие реальные данные, в потребительский
почтовый ящик. При использовании почтовых ящиков механизм буферизации вполне
понятен: в почтовом ящике получателя содержатся сообщения, посланные процессу-
получателю, но еще не принятые им.
Другой крайностью при использовании почтовых ящиков является полный отказ от
буферизации. При этом подходе, если операция send проводится до операции receive,
процесс-отправитель блокируется до завершения операции receive, в это время со-
общение может быть непосредственно скопировано с отправителя получателю без ис-
пользования промежуточной буферизации. А если первой проводится операция receive,
получатель блокируется до осуществления операции send. Такую стратегию обычно
называют рандеву. Она проще в реализации, чем схема с буферизацией сообщений, но
является менее гибкой, поскольку отправитель и получатель должны работать в строго
предопределенном режиме.
Передача сообщений широко используется в системах параллельного программи-
рования. В качестве примера можно привести общеизвестную систему передачи со-
общений MPI (Message-Passing Interface). Она нашла широкое применение в научных
вычислениях. Более подробные сведения об этой системе изложены в трудах Gropp et
al., 1994; Snir et al., 1996.
2.3.9. Барьеры
Последний из рассматриваемых нами механизмов синхронизации предназначен для
групп процессов, в отличие от задачи производителя-потребителя, в которой задейство-
ваны всего два процесса. Некоторые приложения разбиты на фазы и следуют правилу,