Реклама:

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

Однако этот метод решает проблему гонок только для двух процессов. В общем случае при наличии п процессов он не работает. Конечно, каждому процессу можно приписать п - 1 таких битов ожидания пробуждения, но это неудобно.

В [56] предложено другое решение этой проблемы. Где-то в памяти находятся две переменные, которые могут содержать неотрицательные целые числа. Эти переменные называются семафорами. Операционная система предоставляет два системных вызова, up и down, которые оперируют семафорами. Вызов up прибавляет 1 к значению семафора, а вызов down вычитает 1 из значения семафора.

Если операция down совершается для семафора, значение которого больше О, значение этого семафора уменьшается на 1, и процесс продолжается. Если же значение семафора равно 0, то операция down не может завершиться. Тогда данный процесс приостанавливается до тех пор, пока другой процесс не выполнит для этого семафора операцию up. Как правило, приостановленные процессы собираются в одну очередь, что упрощает задачу их отслеживания.

Команда up проверяет, не равно ли 0 значение семафора. Если равно, а другой процесс приостановлен, значение семафора увеличивается на 1. После этого приостановленный процесс должен завершить операцию down, установив в 0 значение семафора. В этом случае оба процесса могут продолжать работу. Если значение семафора не равно 0, команда up просто увеличивает его на 1. Семафор позволяет сохранять сигналы пробуждения, так что они не пропадут зря. У семафорных команд есть одно важное свойство: если один из процессов начал выполнять команду для семафора, то другой процесс не сможет получить доступ к этому семафору до тех пор, пока первый процесс не завершит выполнение команды или не будет приостановлен, пытаясь выполнить команду down при нулевом значении семафора. В табл. 6.2 представлены важные свойства системных вызовов up и down.

Таблица 6.2. Результаты опер8аций с семафором

   

Команда

Семафор = 0

Семафор > 0

up

Семафор = семафор + 1 (если другой процесс пытается теперь выполнить операцию down для этого семафора, он сможет это сделать и продолжить свою работу)

Семафор

= семафор +1

down

Процесс приостанавливается до тех пор, пока другой процесс не выполнит операцию up для этого семафора

Семафор

= семафор -1

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

В листинге 6.2 показано, как можно устранить состояние гонок с помощью семафоров. В класс m добавляются два семафора: семафор available, изначально равный 100 (это размер буфера), и семафор filled, изначально равный 0. Производитель начинает работу с оператора Р1, а потребитель - с оператора С1. Вызов down для семафора filled сразу же приостанавливает работу потребителя. Когда производитель находит первое число, он вызывает метод down с переменной available в качестве параметра, присваивая ей значение 99. В операторе Р5 производитель вызывает метод up с параметром filled, присваивая переменной filled значение 1. Это действие освобождает потребителя, который теперь может завершить вызов метода down. После этого filled принимает значение 0, и оба процесса продолжают работу.

Давайте еще раз вернемся к состоянию гонок. Пусть в определенный момент in = 22, a out = 21, производитель выполняет оператор Р1, а потребитель - оператор С5. Потребитель завершает действие и переходит к оператору СІ, в котором вызывается метод down для семафора filled, до вызова имевшего значение 1, а после вызова получившего значение 0. Затем потребитель извлекает последнее число из буфера и вызывает метод up для семафора available, после чего available принимает значение 100. Потребитель печатает это число и переходит к оператору С1. Как раз перед тем, как потребитель собирается вызвать метод down, производитель формирует следующее число и быстро выполняет операторы Р2, РЗ и Р4.

В этот момент filled = 0. Производитель собирается вызывать для этого семафора метод up, а потребитель - метод down. Если потребитель сделает вызов первым, он будет приостановлен до тех пор, пока производитель его не освободит (вызвав метод up). Если же первым вызов сделает производитель, то семафор получит значение 1, и потребитель вообще не будет приостановлен. В обоих случаях сигнал запуска не пропадет. Именно для этого мы и ввели в программу семафоры.

Листинг 6.2. Параллельная работа с использованием семафоров

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 int filled = 0, available = 100; // семафоры

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

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

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

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

}

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

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

}

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

native void up(int s); native void down(int s); // методы для семафоров

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

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

while (prime < m.MAX_PRIME) { prime = next_prime(prime); // оператор PI

down(m.avail able); // оператор P2

m.buffer[m.in] = prime; // оператор P3

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

up(m.filled); // оператор P5

}

}

// Функция, которая вычисляет следующее число private long next_prime(long prime){ ...}

}

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

native void up(int s); native void down(int s); // методы для семафоров public void run() { // код потребителя

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

while (emirp < m.MAX_PRIME) { down(m.filled); // оператор CI

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

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

up(m. available); // оператор C4

System.out.println(emirp); // оператор C5

}

}

}

Операции с семафорами неделимы. Если операция с семафором уже началась, то никакой другой процесс не может использовать этот семафор до тех пор, пока первый процесс не завершит операцию или пока он не будет приостановлен. Более того, при наличии семафоров сигналы запуска не пропадают. А вот операторы if в листинге 6.1 делимы. Между проверкой условия и выполнением нужного действия другой процесс может послать сигнал запуска.

В сущности, проблема синхронизации была решена путем введения неделимых системных вызовов up и down. Чтобы эти операции были неделимыми, операционная система должна запретить двум и более процессам использовать один и тот же семафор одновременно. То есть если делается системный вызов up или down, никакой пользовательский код не может быть запущен, пока вызов не завершится. Как правило, в однопроцессорных системах для этого во время выполнения операций с семафорами вводится запрет на прерывания. В мультипроцессорных системах этот прием не проходит.

Технология семафоров работает для произвольного количества процессов. Несколько процессов могут приостановиться, пытаясь выполнить системный вызов down для одного и того же семафора. Когда какой-нибудь другой процесс выполнит системный вызов up для этого же семафора, один из приостановленных процессов может завершить вызов down и продолжить работу. В этом случае семафор сохранит значение 0, и другие процессы останутся приостановленными.

Поясним ситуацию на другом примере. Представьте себе 20 волейбольных команд, играющих 10 партий (процессов). Каждая игра проходит на отдельном поле. Имеется большая корзина (семафор) для волейбольных мячей. К сожалению, мячей только 7. В каждый момент в корзине находится от 0 до 7 мячей (семафор принимает значение от 0 до 7). Помещение мяча в корзину - это операция up, поскольку она увеличивает значение семафора. Извлечение мяча из корзины - это операция down, поскольку она уменьшает значение семафора.

В самом начале один игрок от каждого поля посылается к корзине за мячом. Семерым из них удается получить мяч (завершить операцию down); оставшиеся трое вынуждены ждать. Их игры временно приостановлены. В конце концов, одна из партий заканчивается, и мяч возвращается в корзину (выполняется операция up). Эта операция позволяет одному из трех оставшихся игроков получить мяч (закончить незавершенную операцию down) и продолжить игру. Оставшиеся две партии остаются приостановленными до тех пор, пока еще два мяча не возвратятся в корзину. Когда эти два мяча попадут в корзину (то есть выполнятся еще две операции up), можно будет продолжить последние две партии.

Состояние гонок || Оглавление || Примеры операционных систем