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

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

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

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

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

Мониторы

Межпроцессное взаимодействие с применением семафоров выглядит довольно просто, не правда ли? Эта простота кажущаяся. Взгляните внимательнее на поря­док выполнения процедур down перед помещением или удалением элементов из буфера в листинге 2.4. Представьте себе, что две процедуры down в программе про­изводителя поменялись местами, так что значение mutex было уменьшено раньше, чем empty. Если буфер был заполнен, производитель блокируется, установив mutex на 0. Соответственно, в следующий раз, когда потребитель обратится к буферу, он выполнит down с переменной mutex, равной 0, и тоже заблокируется. Оба процесса заблокированы навсегда. Эта неприятная ситуация называется взаимоблокиров­кой, и мы вернемся к ней в главе 3.

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

Чтобы упростить написание программ, в 1974 году Хоар (Ноаге) [155] и Бринч Хансен (Brinch Hansen) [43] предложили примитив синхронизации более высо­кого уровня, называемый монитором. Их предложения несколько отличались друг от друга, как мы увидим дальше. Монитор — набор процедур, переменных и дру­гих структур данных, объединенных в особый модуль или пакет. Процессы могут вызывать процедуры монитора, но у процедур, объявленных вне монитора, нет прямого доступа к внутренним структурам данных монитора. В листинге 2.6 пред­ставлен монитор, написанный на воображаемом языке Pidgin Pascal.

Листинг 2.6. Монитор

monitor example

integer i;

condition с;

procedure producer ();

…….

end;

procedure consumer ():

…….

end;

end monitor;

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

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

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

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

Другой процесс, в нашем примере потребитель может активизировать ожи­дающего напарника, например, выполнив операцию signal на той переменной со­стояния, на которой он был заблокирован. Чтобы в мониторе не оказалось двух активных процессов одновременно, нам необходимо правило, определяющее по­следствия операции signal. Xoap предложил запуск «разбуженного» процесса и остановку второго. Бринч Хансен предложил другое решение: процесс, выполнив­ший signal, должен немедленно покинуть монитор. Иными словами, операция signal выполняется только в самом конце процедуры монитора. Мы будем использовать это решение, поскольку оно в принципе проще и к тому же легче в реализации. Если операция signal выполнена на переменной, с которой связаны несколько за­блокированных процессов, планировщик выбирает и «оживляет» только один из них.

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

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

В листинге 2.7 представлена схема решения проблемы производителя и потре­бителя с применением мониторов, написанная на воображаемом языке Pidgin Pascal. В данной ситуации этот язык удобен своей простотой, а также тем, что он позво­ляет в точности следовать модели Хоара и Бринча Хансена. В каждый момент вре­мени активна только одна процедура монитора. Буфер состоит из N сегментов.

Листинг 2.7. Схема решения проблемы производителя и потребителя с применением мониторов

monitor ProducerConsumer

condition full, empty;

integer count;

procedure insert (item: integer);

begin

if count = N then wait(full);

insert_jtem(item);

count := count+1;

if count = 1 then signal(empty)

end;

function remove: integer;

begin

if count=0 then wait(empty);

remove = remove_item;

count := count-1;

if count = N-l then signal(full)

end;

count := 0;

end monitor;

procedure producer;

begin

while true do

begin

item = produce_item;

ProducerConsumer_.insert(item)

End; end;

procedure consumer;

begin

while true do

begin

item = ProducerConsumer_.remove;

consume_item(item)

end end;

Можно подумать, что операции wait и signal похожи на sleep и wakeup, которые приводили к неустранимым состояниям соревнования. Они действительно похожи, но с одним существенным отличием: неудачи применения операций sleep и wakeup были связаны с тем, что один процесс пытался уйти в состояние ожидания, в то время как другой процесс пытался активировать его. С мониторами такого произой­ти не может. Автоматическое взаимное исключение, реализуемое процедурами монитора, гарантирует: если производитель, находящийся в мониторе, обнаружит полный буфер и решит выполнить операцию wait, можно не опасаться, что плани­ровщик передаст управление потребителю раньше, чем операция wait будет завер­шена. Потребитель даже не сможет попасть в монитор, пока операция wait не бу­дет выполнена и производитель не прекратит работу.

Несмотря на то, что Pidgin Pascal — воображаемый язык, существует несколько языков программирования, поддерживающих мониторы, хотя и не всегда в соответ­ствии с моделью Хоара и Бринча Хансена. Один из таких языков — Java, объект­но-ориентированный язык, поддерживающий потоки на уровне пользователя и позволяющий группировать методы (процедуры) в классы. Добавление в описание метода ключевого слова synchronized гарантирует, что если хотя бы один поток на­чал выполнение этого метода, ни один другой поток не сможет выполнять другой синхронизированный (определенный как synchronized) метод из этого класса.

Решение проблемы производителя и потребителя с использованием монито­ров, написанное на Java, представлено в листинге 2.8. Решение состоит из четырех классов. Внешний класс, ProducerConsumer, создает и запускает два потока, Листинг 2.8. Второй и третий классы, producer и consumer соответственно, содержат программы производителя и потребителя. Класс outjmonitor является монитором. Он содер­жит два синхронизированных потока, используемых для текущего помещения эле­ментов в буфер и извлечения их оттуда. В отличие от предыдущих примеров, здесь приведен полный текст программ insert и remove.

Листинг 2.8. Решение проблемы производителя и потребителя на Java

public class ProducerConsumer {

static final int N = 100: // константа, задающая размер буфера

static producer p = new producer(); // создать экземпляр потока производителя

static consumer с = 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;

while (true) { // цикл производителя

item = produce_item();

mon.insert(item);

} }

private int produce_jtem () { ... } // собственно производство

}

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, his= 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]: // забрать элемент из буфера

lо = (1о+1)%N; // следующий сегмент, из которого заберут элемент

count = count -1: // теперь в буфере на один элемент меныне-

if (count == N -1) notify (); // если производитель в состоянии ожидания,

активировать его

return val: }

private void go_to_sleep()

{ try{wait();}

catch (interruptedException exc) {}:} } }

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

Интерес для нас представляет класс our_monitor, содержащий буфер, перемен­ные администрирования и два метода синхронизации. Когда производитель акти­вен в процедуре insert, потребитель не может быть активным в процедуре remove, что исключает состояние состязания. Переменная count отслеживает количество элементов в буфере, принимая значения от 0 до N - 1. Переменная lо является индексом следующего сегмента буфера, из которого следует извлечь данные. Пере­менная hi является индексом следующего сегмента буфера, в который следует поместить данные. Разрешена ситуация, в которой lо = hi, что означает 0 или N элементов в буфере. Различать эти два случая можно по переменной count.

Синхронизированные методы в языке Java отличаются от стандартных мони­торов отсутствием переменных состояния. Взамен предлагаются две процедуры, wait и notify, которые аналогичны sleep и wakeup с той лишь разницей, что они ис­пользуются в синхронизированных методах, а это исключает состояния состязания. Теоретически процедура может быть прервана, для чего и служит весь окружающий ее набор программ. Java требует, чтобы исключения обрабатывались явно. В нашем случае просто представьте, что go_to_sleep описывает уход в состояние ожидания. Благодаря автоматизации взаимного исключения применение мониторов сде­лало параллельное программирование значительно менее подверженным ошиб­кам, чем применение семафоров. Но и у мониторов тоже есть свои недостатки.

Недаром два примера мониторов, которые мы рассмотрели, были написаны на Pidgin Pascal и Java, а не на С, как все остальные примеры этой книги. Как мы уже говорили, мониторы являются структурным компонентом языка программиро­вания, и компилятор должен их распознавать и организовывать взаимное ис­ключение. В Pascal, С и многих других языках нет мониторов, поэтому странно было бы ожидать от их компиляторов выполнения правил взаимного исключения. И в самом деле, как может отличить компилятор процедуры монитора от остальных? В этих языках также нет и семафоров, но их легко добавить: нужно всего лишь присоединить к библиотеке две короткие программы, написанные на ассемблере и реализующие системные вызовы up и down. Компиляторы при этом не обязаны знать об их существовании. Разумеется, операционная система должна знать о се­мафорах, но даже если у вас операционная система с семафорами, вы можете пи­сать программы для нее на С или C++ (или на ассемблере, если вы склонны к ма­зохизму). Если же у вас операционная система с мониторами, вам необходим язык со встроенными, мониторами.

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

Передача сообщений

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

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