Реклама: купить картриджи hp

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

Рассмотрим два независимых процесса, процесс 1 и процесс 2, которые взаимодействуют через общий буфер в основной памяти. Для простоты будем называть процесс 1 производителем (producer), а процесс 2 - потребителем (consumer). Производитель генерирует простые числа и помещает их в буфер по одному. Потребитель по одному извлекает их из буфера и печатает.

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

В нашем примере для взаимодействия процессов мы задействуем кольцевой буфер. Указатели in и out используются следующим образом: in указывает на следующее свободное слово (куда производитель сможет поместить очередное число), a out - на следующее число, которое должен извлечь потребитель. Если in = out, буфер пуст, как показано на рис. 6.22, а. На рис. 6.22, б показана ситуация после того, как производитель сгенерировал несколько чисел. На рис. 6.22, в изображен буфер после того, как потребитель извлек из него несколько чисел для печати. На рис. 6.22, г-е представлены промежуточные этапы работы буфера. Буфер заполняется циклически. Если в буфер отправлено слишком много чисел, и он начинает заполняться по второму кругу (снизу), а под адресом out есть только одно свободное слово (например, in = 52, a out = 53), буфер заполнится. Последнее слово не используется; в противном случае не было бы возможности сообщить, что именно значит равенство in = out, полный буфер или пустой.

Состояние гонок

Рис. 6.22. Кольцевой буфер

В листинге 6.1 показано решение задачи с производителем и потребителем на языке Java. Здесь имеется три класса: m, producer и consumer. Класс т содержит некоторые константы, указатели буфера in и out и сам буфер, который в нашем примере вмещает 100 простых чисел (от buffer[0] до buffer[99]).

Для моделирования параллельных процессов в данном случае используются программные потоки (threads). У нас есть классы producer и consumer, которым приписываются значения переменных рис соответственно. Каждый из этих классов образуется из базового класса Thread. Метод run этого класса содержит код программного потока. Когда вызывается метод start для объекта, производного от класса Thread, запускается новый поток.

Листинг 6-1- Параллельная работа в условиях гонок

public class m {

final public static int BUF_SIZE = 100; // буфер от 0 до 99 final public static long MAX_PRIME = 100000000000L; // остановиться здесь public static int in = 0, out = 0; // указатели на данные

public static long buffer[ ] = new long[BUF_SIZE]; // числа хранятся здесь public static producer p; // имя производителя

public static consumer с; // имя потребителя

public static void main(String args[ ]){ // основной класс

p = new producer ); // создание производителя с = new consumer ); // создание потребителя

p.startO; // запуск производителя

c.startO; // запуск потребителя

}

// Это утилита для циклического увеличения in и out

public static int next(int k) { if (k < BUF_SIZE - 1) return(k + 1); else return(O); }

}

class producer extends Thread { // класс производителя

public void run() { // код производителя

long prime = 2; // временная переменная

while (prime < m.MAX_PRIME) {

prime = next_prime(prime); // оператор PI

if (m.next(m.in) == m.out) suspendO; // оператор P2 m. buffer[m. in] = prime; // оператор P3

m.in = m.next(m.in); // оператор P4

if (m.next(m.out) == m.in) m.c.resumeO: // оператор P5

}

}

private long next_prime(long prime){ ... } // функция, вычисляющая

// следующее число

}

class consumer extends Thread { // класс потребителя

public void run() { // код потребителя

long emirp = 2; // временная переменная

while (emirp < m.MAX_PRIME) { if (m.in == m.out) suspendO; // оператор CI

emirp = m.buffer[m.out]; // оператор C2

m.out = m.next(m.out); // оператор C3

if (m.out == m.next(m.next(m.in))) m.p.resume(); // оператор C4 System.out.println(emirp); // оператор C5

}

}

}

Каждый программный поток похож на процесс. Единственным отличием является то, что все потоки в пределах одной ^уа-программы находятся в едином адресном пространстве. Это позволяет им разделять один общий буфер. Если в компьютере имеется два и более процессора, каждый поток может выполняться на собственном процессоре, поэтому в данном случае имеет место реальный параллелизм. Если компьютер содержит только один процессор, потоки разделяются во времени на одном процессоре. Мы будем продолжать называть производителя и потребителя процессами (поскольку нас в данный момент интересуют параллельные процессы), хотя Java поддерживает параллелизм только на уровне программных потоков, а не "настоящих" процессов.

Функция next позволяет увеличивать значения in и out, при этом не нужно каждый раз писать код, чтобы проверять условие окончания цикла. Если параметр в next равен 98 или ниже, то возвращается следующее по порядку целое число. Если параметр равен 99, это значит, что мы достигли конца буфера, поэтому возвращается 0.

Если какой-то из процессов не может продолжаться, желательно иметь способ временно его приостановить. Зная об этой потребности, разработчики первой версии Java включили в класс Thread специальные методы suspend (приостановка) и resume (возобновление работы). Они используются в листинге 6.1.

А теперь рассмотрим сам код производителя и потребителя. Сначала производитель генерирует новое число (оператор Р1). Обратите внимание на идентификатор m.MAXPRIME. Префикс m здесь указывает, что имеется в виду идентификатор MAXPRIME, определенный в классе т. По той же причине этот префикс нужен для идентификаторов in, out, buffer и next.

Затем (оператор Р2) производитель проверяет, не меньше ли in значения out. Если да (например, in = 62 и out = 63), это означает, что буфер заполнен, и производитель вызывает метод suspend. Если буфер не заполнен, туда помещается новое число (оператор РЗ), и значение in инкрементируется (оператор Р4). Если при проверке в операторе Р5 обнаруживается, что новое значение in на 1 больше, чем out (например, in = 17, out = 16), это означает, что значения in и out перед увеличением in были равны. Тогда производитель делает вывод, что буфер был пуст, потребитель не функционировал (был приостановлен) и продолжает простаивать. Поэтому производитель вызывает метод resume, чтобы заставить потребителя возобновить работу (оператор Р5). После этого производитель начинает формировать следующее число.

Программа потребителя по структуре очень проста. Сначала проверяется, пуст ли буфер (оператор С1). Если пуст, то потребителю ничего не нужно делать, поэтому он отключается. Если буфер не пуст, то потребитель извлекает из него следующее число для печати (оператор С2) и инкрементирует значение out (оператор СЗ). Если после этого значение out становится на 2 единицы больше in (оператор С4), это означает, что на предыдущем шаге значение out было на единицу меньше in. Так как условием заполнения буфера как раз и является значение in = out - 1, это означает, что производитель был приостановлен, и потребитель вызывает для производителя метод resume. После этого число выводится на печать (оператор С5), и весь цикл повторяется.

К сожалению, программа содержит ошибку (рис. 6.23). Напомним, что наши два процесса работают асинхронно, то есть с разными скоростями, которые, к тому же, могут меняться. Рассмотрим случай, когда в буфере остается только одно число в элементе 21, и in = 22, a out = 21 (рис. 6.23, а). Производитель в операторе Р1 ищет число, а потребитель в операторе С5 печатает число с позиции 20.

Потребитель заканчивает печатать число, совершает проверку в операторе С1 и извлекает последнее число из буфера в операторе С2. Затем он инкрементиру-ет значение out. В этот момент и in, и out равны 22. Потребитель печатает число, а затем переходит к оператору СІ, в котором он вызывает значения in и out из памяти, чтобы сравнить их (рис. 6.23, б).

Состояние гонок

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

В этот момент, после того, как потребитель вызвал значения in и out, но еще до того, как он сравнил их, производитель генерирует следующее число. Он помещает это число в буфер в операторе РЗ и инкрементирует in в операторе Р4. Теперь in = 23, a out = 22. В операторе Р5 производитель обнаруживает, что in на единицу больше out, а это означает, что в буфере находится одно число. Исходя из этого, производитель делает неверный вывод о том, что потребитель приостановлен, и вызывает для его запуска метод resume, как показано на рис. 6.23, в. На самом деле потребитель все это время продолжает работать, поэтому вызов метода resume оказывается лишним. Затем производитель начинает формировать следующее число.

В этот момент потребитель продолжает работать. Он успевает вызвать значения in и out из памяти раньше, чем производитель поместил последнее число в буфер. Так как in = 22 и out = 22, потребитель приостанавливается. К этому моменту производитель генерирует следующее число. Он проверяет указатели и обнаруживает, что in = 24, a out = 22. Из этого он делает заключение, что в буфере находится 2 числа (что соответствует действительности), а потребитель функционирует (что неверно). Производитель продолжает цикл. В конце концов, он заполняет буфер и приостанавливается. После этого оба процесса остаются приостановленными до скончания веков.

Сложность здесь в том, что между моментом, когда потребитель вызывает in и out, и моментом, когда он отключается, производитель, обнаружив, что in = = out + 1 и предположив, что потребитель приостановлен (хотя на самом деле он продолжает функционировать), вызывает метод resume, чего делать не нужно, поскольку потребитель и так функционирует. Такая ситуация называется состоянием гонок, поскольку успех метода зависит от того, кто после инкремента out выиграет гонку по проверке in и out.

Проблема гонок хорошо известна. Она настолько серьезна, что через несколько лет после создания Java компания Sun переработала класс Thread, изъяв из него вызовы методов suspend и resume, поскольку они очень часто приводили к состоянию гонок. Предложенное решение заключается в изменении языка, но поскольку наша цель - операционные системы, мы обсудим другое решение, которое используется во многих операционных системах, в том числе UNIX и Windows ХР.

Формирование процесса || Оглавление || Синхронизация процесса с использованием семафоров