ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 12149
Скачиваний: 10
Виртуальные команды ввода-вывода 473
В листинге 6.1 на языке Java показано решение задачи с производителем и по-
требителем.
Здесь используются три класса:
m,produser
и
consumer.
Класс
т
содержит неко-
торые константы, указатели буфера
in
и
out
и сам буфер, который в нашем примере
вмещает 100 простых чисел (от buffer[O] до buffer[99]).
Для моделирования параллельных процессов в данном случае используются
потоки (threads).
У нас есть класс
producer
и класс
consumer,
которым приписыва-
ются значения переменных
р
и
с
соответственно. Каждый из этих классов образу-
ется из базового класса
Thread с
процедурой
run.
Класс
run
содержит код для
thread.
Когда вызывается процедура
start
для объекта, образованного из
Thread,
запуска-
ется новый поток.
Каждый поток похож на процесс. Единственным различием является то, что
все потоки в пределах одной программы на языке Java работают в одном адресном
пространстве. Это позволяет им разделять один общий буфер. Если в компьютере
имеется два и более процессоров, каждый поток может выполняться на другом
процессоре, поэтому в данном случае имеет место реальный параллелизм. Если
компьютер содержит только один процессор, потоки разделяются во времени на
одном процессоре. Мы будем продолжать называть производителя и потребителя
процессами (поскольку нас в данный момент интересуют параллельные процес-
сы), хотя Java поддерживает только параллельные потоки, а не реальные парал-
лельные процессы.
Функция
next
позволяет увеличивать значения
in
и
out,
при этом не нужно каж-
дый раз записывать код, чтобы проверить условие циклического возврата. Если
параметр в
next
равен 98 или указывает на более низкое значение, то возвращается
следующее по порядку целое число. Если параметр равен 99, это значит, что мы
наткнулись на конец буфера, поэтому возвращается 0.
Должен быть способ «усыплять» любой из процессов, если он не может про-
должаться. Для этого разработчики Java включили в класс
Thread
специальные
процедуры
suspend
(отключение) и
resume
(возобновление). Они используются
в листинге 6.1.
А теперь рассмотрим саму программу для производителя и потребителя. Сна-
чала производитель порождает новое простое число (шаг Р1). Обратите внимание
на строку m.MAX_PRIME. Префикс т. здесь указывает, что имеется в виду
MAXPRIME,
определенный в классе
т.
По той же причине этот префикс нужен для
in, out, buffer
и next.
Затем производитель проверяет (шаг Р2), не находится ли
in
ниже
out.
Если да
(например, ш=62 и
out=63),
то буфер заполнен и производитель вызывает проце-
дуру
suspend
в Р2. Если буфер не заполнен, туда помещается новое простое число
(шаг РЗ) и значение
in
увеличивается (шаг Р4). Если новое значение
in
на 1 боль-
ше значения
out
(шаг Р5) (например, ш=17,
out=l6),
значит,
in
и
out
были равны
перед тем, как увеличилось значение
in.
Производитель делает вывод, что буфер
был пуст и что потребитель не функционировал (находился в режиме ожидания)
и в данный момент тоже не функционирует. Поэтому производитель вызывает
процедуру
resume,
чтобы возобновить работу потребителя (шаг Р5). Наконец, про-
изводитель начинает искать следующее простое число.
4 7 4
Глава 6. Уровень операционной системы
Листинг 6 . 1
. Параллельная обработка с состоянием гонок
public class m {
final public static i n t BUF_SIZE = 100;
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 c;
public static void mam(Stnng args[ ] ) {
p = new producer );
с = new consumer ),
p s t a r t O :
с s t a r t O .
// буфер от 0 до 99
//остановиться здесь
// указатели на данные
//простые числа хранятся здесь
//имя производителя
//имя потребителя
// основной класс
//создание производителя
//создание потребителя
//запуск производителя
//запуск потребителя
//Это утилита для циклического увеличения m и out
public static int next(int k) { i f (k < BUF_SIZE - 1) return(k+l). else return(O):
class producer extends Thread {
public void runO {
long prime = 2;
while (prime < m.MAX_PRIME) {
prime = next_pnme(pnme):
if (m next(m.m) == m.out) suspendO:
m buffer[m. in] = prime;
m in = m.next(m i n ) .
if (m next(m out) = m in) m c.resumeO.
//класс производителя
//код производителя
// временная переменная
//шаг Р1
//шаг Р2
//шаг РЗ
//шаг Р4
//шаг Р5
private long next_pnme(long pnme){ ..} //функция, вычисляющая следующее число
class consumer extends Thread {
public void run() {
long emirp = 2;
while (emirp < m MAX_PRIME) {
if (m in == m out) suspendO:
emirp = m buffer[m.out]:
m.out = m next(m out);
if (m.out — m.next(m next(m.in))) m p.resumeO;
System out print!n(emirp).
//класс потребителя
// код потребителя
// временная переменная
//шаг С1
//шаг С2
//шаг СЗ
//шаг С4
//шаг С5
Программа потребителя по структуре очень проста. Сначала производится про-
верка (шаг С1), чтобы узнать, пуст ли буфер. Если он пуст, то потребителю ничего
не нужно делать, поэтому он отключается. Если буфер не пуст, то потребитель уда-
ляет из него следующее число для печати (шаг С2) и увеличивает значение
out.
Если после этого
out
стало на две позиции выше
in,
значит, до этого
out
было на
одну позицию выше
in.
Так как
in=out-\
— это условие заполненности буфера,
значит, производитель не работает и потребитель должен вызвать процедуру
resume.
После этого число выводится на печать, и весь цикл повторяется снова.
Виртуальные команды ввода-вывода
4 7 5
К сожалению, такая программа содержит ошибку (рис. 6.23). Напомним, что
эти два процесса работают асинхронно и с разными скоростями, которые, к тому
же, могут меняться. Рассмотрим случай, когда в буфере осталось только одно
число в элементе 21, и m=22, a
out=2i
(см. рис. 6.23,
а).
Производитель на шаге Р1
ищет простое число, а потребитель на шаге С5 печатает число из позиции 20. Потре-
битель заканчивает печатать число, совершает проверку на шаге С1 и забирает по-
следнее число из буфера на шаге С2. Затем он увеличивает значение
out.
В этот мо-
мент и
in
и ом? равны 22. Потребитель печатает число, а затем переходит к шагу С1,
на котором он вызывает
in
и
out
из памяти, чтобы сравнить их (рис. 6.23, б).
Процесс-производитель
на шаге Р1
Процесс-потребитель
на шаге С5
100
In = 22
Out = 21
Простое
число
1 число
в буфере
Процесс-производитель
на шаге Р1
Процесс-потребитель
на шаге С5
100
In = Out = 22
Процесс-производитель
на шаге Р5 посылает
сигнал пробуждения
процессу-потребителю
на шаге С1
100
In = 23
Out = 22
Простое
число
1 число
в буфере
Рис. 6.23. Ситуация, при которой механизм взаимодействия
производителя
w
потребителя не работает
В этот момент, после того как потребитель вызвал
in
и
out,
но еще до того как
он сравнил их, производитель находит следующее простое число. Он помещает
это простое число в буфер на шаге РЗ и увеличивает
in
на шаге Р4. Теперь щ=23,
а ом
£=22.
На шаге Р5 производитель обнаруживает, что
in=*next(out).
Иными сло-
вами,
in
на единицу больше
out,
а это значит, что в буфере в данный момент нахо-
дится один элемент.
Исходя из этого, производитель делает неверный вывод, что потребитель от-
ключен, и вызывает процедуру
resume
(рис. 6.23,
в).
На самом деле потребитель
все это время продолжал работать, поэтому вызов процедуры
resume
оказался лож-
ным. Затем производитель начинает искать следующее простое число.
В этот момент потребитель продолжает работать. Он уже вызвал
in
и
out
из
памяти, перед тем как производитель поместил последнее число в буфер. Так как
ш=22 и
out-22,
потребитель отключается. К этому моменту производитель нахо-
дит следующее простое число. Он проверяет указатели и обнаруживает, что ш=24,
a
out=22.
Из этого он делает заключение, что в буфере находится 2 числа (что соот-
ветствует действительности) и что потребитель функционирует (что неверно).
4 7 6 Глава 6. Уровень операционной системы
Производитель продолжает цикл. В конце концов он заполняет буфер и отключа-
ется. Теперь оба процесса отключены и будут находиться в таком состоянии до
скончания веков.
Сложность здесь в том, что между моментом, когда потребитель вызывает
in
и
out,
и моментом, когда он отключается, производитель, обнаружив, что
in=out+\,
и
предположив, что потребитель отключен (хотя на самом деле он еще продолжает
функционировать), вызывает процедуру
resume,
чего не нужно делать, поскольку
потребитель функционирует. Такая ситуация называется
состоянием гонок,
по-
скольку успех процедуры зависит от того, кто выиграет гонку по проверке
in
и
out,
после того как значение
out
увеличилось.
Проблема состояния гонок хорошо известна. Она была настолько серьезна, что
через несколько лет после появления Java компания Sun изменила класс
Thread
и убрала вызовы процедур
suspend
и
resume,
поскольку они очень часто приводили
к состоянию гонок. Предложенное решение было основано на изменении языка,
но поскольку мы изучаем операционные системы, мы обсудим другое решение,
которое используется во многих операционных системах, в том числе UNIX и NT.
Синхронизация процесса
с использованием семафоров
Проблему состояния гонок можно разрешить по крайней мере двумя способами.
Первый способ — снабдить каждый процесс специальным битом ожидания про-
буждения. Если процесс, который функционирует в данный момент, получает сиг-
нал «пробуждения», то этот бит устанавливается. Если процесс отключается в тот
момент, когда этот бит установлен, он немедленно перезапускается, а бит сбрасы-
вается. Данный бит сохраняет сигнал пробуждения для будущего использования.
Этот метод решает проблему состояния гонок только в том случае, если у нас
есть всего 2 процесса. В общем случае при наличии п процессов он не работает.
Конечно, каждому процессу можно приписать п -1 таких битов ожидания пробуж-
дения, но это неудобно.
Дейкстра [31] предложил другое решение этой проблемы. Где-то в памяти на-
ходятся две переменные, которые могут содержать неотрицательные целые числа.
Эти переменные называются
семафорами.
Операционная система предоставляет
два системных вызова,
up
и
down,
которые оперируют семафорами.
Up
прибавляет
1 к семафору, a
down
отнимает 1 от семафора. Если операция
down
совершается
над семафором, значение которого больше 0, этот семафор уменьшается на 1 и про-
цесс продолжается. Если значение семафора равно 0, то операция
down
не может
завершиться. Тогда данный процесс отключается до тех пор, пока другой процесс
не выполнит операцию
up
над этим семафором.
Команда
up
проверяет, не равен ли семафор нулю. Если он равен 0 и другой
процесс находится в режиме ожидания, то семафор увеличивается на 1. После это-
го процесс, который «спит», может завершить операцию
down,
установив семафор
на 0. Теперь оба процесса могут продолжать работу. Если семафор не равен 0, ко-
манда
up
просто увеличивает его на 1. Семафор позволяет сохранять сигналы про-
буждения, так что они не пропадут зря. У семафорных команд есть одно важное
свойство: если один из процессов начал выполнять команду над семафором, то
Виртуальные команды ввода-вывода
4 7 7
другой процесс не может получить доступ к этому семафору до тех пор, пока пер-
вый не завершит выполнение команды или не будет приостановлен при попытке
выполнить команду
down
над 0. В таблице 6.5 изложены важные свойства систем-
ных вызовов
up
и
down.
Таблица 6.5.
Результаты операций над семафором
Команда Семафор = 0 Семафор
>
О
Up Семафор = семафор + 1; если другой процесс пытается Семафор = семафор +1
совершить команду down над этим семафором, теперь
он сможет это сделать и продолжить свою работу
Down Процесс останавливается до тех пор, пока другой Семафор = семафор -1
процесс не выполнит операцию up над этим
семафором
Как мы уже сказали, в языке Java предусмотрено свое решение проблемы со-
стояния гонок, но мы сейчас обсуждаем операционные системы. Следовательно,
нам нужно каким-либо образом выразить использование семафоров в языке Java.
Мы предположим, что были написаны две процедуры,
up
и
down,
которые совер-
шают системные вызовы
up
и
down
соответственно. Используя в качестве пара-
метров обычные целые числа, мы сможем выразить применение семафоров в про-
граммах на языке Java.
В листинге 6.2 показано, как можно устранить состояние гонок с помощью се-
мафоров. В класс
т
добавляются два семафора:
available,
который изначально ра-
вен 100 (это размер буфера),
w. filled,
который изначально равен 0. Производитель
начинает работу с шага Р1, а потребитель — с шага С1. Выполнение процедуры
down
над семафором
filled
сразу же приостанавливает работу потребителя. Когда
производитель находит первое простое число, он вызывает процедуру
down
с
available
в качестве параметра, устанавливая
available
на 99. На шаге Р5 он вызывает про-
цедуру
up
с параметром
filled,
устанавливая
filled
на 1. Это действие освобождает
потребителя, который теперь может завершить вызов процедуры
down.
После это-
го
filled
принимает значение 0, и оба процесса продолжают работу.
А теперь давайте еще раз рассмотрим состояние гонок. В определенный момент
ш=22, a
out=2\,
производитель находится на шаге Р1, а потребитель — на шаге С5.
Потребитель завершает действие и переходит к шагу С1, который вызывает про-
цедуру
down,
чтобы выполнить ее над семафором
filled,
который до вызова имел
значение 1, а после вызова принял значение 0. Затем потребитель берет последнее
число из буфера и выполняет процедуру
up
над
available,
после чего
available
при-
нимает значение 100. Потребитель печатает это число и переходит к шагу С1.
Как раз перед тем, как потребитель может вызвать процедуру
down,
производи-
тель находит следующее простое число и быстро выполняет шаги Р2, РЗ и Р4.
В этот
MOMemfilled=0.
Производитель собирается выполнить над ним команду
up, а потребитель собирается вызвать процедуру
up.
Если потребитель выполнит
команду первым, то он будет приостановлен до тех пор, пока производитель не
освободит его (вызвав процедуру
up).
Если же первым будет производитель, то
семафор примет значение 1 и потребитель вообще не будет приостановлен. В обо-
их случаях сигнал пробуждения не пропадет. Именно для этого мы и ввели в про-
грамму семафоры.