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

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

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

Листинг 2.3. Проблема производителя и потребителя с неустранимым состоянием соревнования

#define N 100 /* Максимальное количество элементов в буфере */

int count = 0; /* Текущее количество элементов в буфере */

void producer (void)

{ int item;

while (TRUE) { /* Повторять вечно */

item = produce_item(); /* Сформировать следующий элемент */

if (count == N) sleep (); /* Если буфер полон, уйти в состояние ожидания */

insert_item(item) ; /* Поместить элемент в буфер */

count = count + 1; /* Увеличить количество элементов в буфере */

if (count==1) wakeup(consumer); /* Был ли буфер пуст */}

}

void consumer (void)

{ int item;

while (TRUE) { /* Повторять вечно */

if (count == 0) sleep(); /* Если буфер пуст, уйти в состояние ожидания */

item = remove_item( ); /* Забрать элемент из буфера */

count = count - 1; /* Уменьшить счетчик элементов в буфере */

if (count == N - 1) wakeup(producer); /* Был ли буфер полон? */

consume_item(item); /* Отправить элемент на печать */

}}

Для описания на языке С системных вызовов sleep и wakeup мы представили их в виде вызовов библиотечных процедур. В стандартной библиотеке С их нет, но они будут доступны в любой системе, в которой присутствуют такие системные вызовы. Процедуры insert_item и remove_item помещают элементы в буфер и извлекают их оттуда.

Теперь давайте вернемся к состоянию состязания. Его возникновение возможно, поскольку доступ к переменной count не ограничен. Может возникнуть следу­ющая ситуация; буфер пуст, и потребитель только что считал значение перемен- ной count, чтобы проверить, не равно ли оно нулю. В этот момент планировщик передал управление производителю, производитель поместил элемент в буфер и увеличил значение count, проверив, что теперь оно стало равно 1. Зная, что перед этим оно было равно 0 и потребитель находился в состоянии ожидания, производитель активизирует его с помощью вызова wakeup.

Но потребитель не был в состоянии ожидания, так что сигнал активизации пропал впустую. Когда управление перейдет к потребителю, он вернется к считанному когда-то значению count, обнаружит, что оно равно 0, и уйдет в состояние ожидания. Рано или поздно производитель наполнит буфер и также уйдет в состояние ожидания. Оба процесса так и останутся в этом состоянии.

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

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

Семафоры

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

Дейкстра предложил две операции, down и up (обобщения sleep и wakeup). Опе­рация down сравнивает значение семафора с нулем. Если значение семафора боль­ше нуля, операция down уменьшает его, (то есть расходует один из сохраненных сиг­налов активации) и просто возвращает управление. Если значение семафора равно нулю, процедура down не возвращает управление процессу, а процесс переводится в состояние ожидания. Все операции проверки значения семафора, его изменения и перевода процесса в состояние ожидания выполняются как единое и неделимое элементарное действие. Тем самым гарантируется, что после начала операции ни один процесс не получит доступа к семафору до окончания или блокирования операции. Элементарность операции чрезвычайно важна для разрешения пробле­мы синхронизации и предотвращения состояния состязания.

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

В оригинале Дейкстра использовал вместо down и up обозначения Р и V соот­ветственно. Мы не будем в дальнейшем использовать оригинальные обозначения, поскольку тем, кто не знает датского языка, эти обозначения ничего не гово­рят (да и тем, кто знает язык, говорят немного). Впервые обозначения down и up появились в языке Algol 68.

Решение проблемы производителя и потребителя с помощью семафоров

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

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

#define N 100 /* количество сегментов в буфере */

typedef int semaphore; /* семафоры - особый вид целочисленных переменных */

semaphore mutex = 1; /* контроль доступа в критическую область */

semaphore empty = N; /* число пустых сегментов буфера */

semaphore full = 0; /* число полных сегментов буфера */

void producer(void)

(

int item:

while (TRUE) {

item - produce_item(); /* создать данные, помещаемые в буфер */

down(&empty); /* уменьшить счетчик пустых сегментов буфера */

down(&mutex); /* вход в критическую область */

insert_item(item); /* поместить в буфер новый элемент */

up(&mutex); /* выход из критической области */

up(&full); /* увеличить счетчик полных сегментов буфера */

}}

void consumer(void)

{

int item;

while (TRUE) { /* бесконечный цикл */

down (& full); /* уменьшить числа полных сегментов буфера */

down(&mutex); /* вход в критическую область */

item = remove_item(); /* удалить элемент из буфера */

up(&mutex); /* выход из критической области */

up(&empty); /* увеличить счетчик пустых сегментов буфера */

consume_item(item); /* обработка элемента */

}}

В представленном решении используются три семафора: один для подсчета за­полненных сегментов буфера (full), другой для подсчета пустых сегментов (empty), а третий предназначен для исключения одновременного доступа к буферу произ­водителя и потребителя (mutex). Значение счетчика full исходно равно нулю, счет­чик empty равен числу сегментов в буфере, a mutex равен 1. Семафоры, исходное значение которых равно 1 , используемые для исключения одновременного нахож­дения в критической области двух процессов, называются двоичными семафора­ми. Взаимное исключение обеспечивается, если каждый процесс выполняет опе­рацию down перед входом в критическую область и up после выхода из нее.

Теперь, когда у нас есть примитивы межпроцессного взаимодействия, вернем­ся к последовательности прерываний, показанной в табл. 2.2. В системах, исполь­зующих семафоры, естественным способом скрыть прерывание будет связать с каждым устройством ввода-вывода семафор, исходно равный нулю. Сразу после запуска устройства ввода-вывода управляющий процесс выполняет операцию down на соответствующем семафоре, тем самым, входя в состояние блокировки. В случае прерывания обработчик прерывания выполняет up на соответствующем семафоре, переводя процесс в состояние готовности. В такой модели пятый шаг в табл. 2.2 заключается в выполнении up на семафоре устройства, чтобы следующим шагом планировщик смог запустить программу, управляющую устройством. Разумеет­ся, если в этот момент несколько процессов находятся в состоянии готовности, планировщик может выбрать другой, более значимый процесс. Мы рассмотрим некоторые алгоритмы планирования позже в этой главе.

В примере, представленном в листинге 2.4, семафоры использовались двумя различными способами. Это различие достаточно значимо, чтобы сказать о нем особо. Семафор mutex используется для реализации взаимного исключения, то есть для исключения одновременного обращения к буферу и связанным переменным двух процессов. Мы рассмотрим взаимное исключения и методы его реализации в следующем разделе.

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

Мьютексы

Иногда используется упрощенная версия семафора, называемая мьютексом (mutex, сокращение от mutual exclusion — взаимное исключение). Мьютекс не способен считать, он может лишь управлять взаимным исключением доступа к совместно используемым ресурсам или кодам. Реализация мьютекса проста и эффективна, что делает использование мьютексов особенно полезным в случае потоков, дей­ствующих только в пространстве пользователя.

Мьютекс — переменная, которая может находиться в одном из двух состояний: блокированном или неблокированном. Поэтому для описания мьютекса требует­ся всего один бит, хотя чаще используется целая переменная, у которой 0 означает неблокированное состояние, а все остальные значения соответствуют блокирован­ному состоянию. Значение мьютекса устанавливается двумя процедурами. Если поток (или процесс) собирается войти в критическую область, он вызывает проце­дуру mutex_lock. Если мыотекс не заблокирован (то есть вход в критическую область разрешен), запрос выполняется и вызывающий поток может попасть в критическую область.

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

Мьютексы легко реализовать в пользовательском пространстве, если доступна команда TSL. Код программы для процедур mutex_lock и mutex_unlock в случае по­токов на уровне пользователя представлен в листинге 2.5.

Листинг 2.5. Реализация mutex_lock и mutex_unlock

mutex_lock:

TSL REGISTER.MUTEX |Старое значение мьютекса копируется в регистр;

|устанавливается новое значение

CMP REGISTER, #0 | Сравнение старого значения с нулем

JZE ok |Если старое значение было нулем, мьютекс не был блокирован.

CALL thread_yield |Мьютекс занят, управление передается другому потоку

JMP mutex_lock |Повторить попытку позже

ok: RET | Возврат, вход в критическую область

mutex_unlock :

MOVE MUTEX.#0

RET

Процедура mutex_lock похожа на процедуру enter_region в листинге 2.2, но с одним существенным отличием. Если процедуре enter_region не удается войти в критичес­кую область, она продолжает в цикле проверять наличие блокировки (активное ожидание). В конце концов время, отведенное этому процессу, кончается и пла­нировщик передает управление другому процессу. Раньше или позже процесс, за­блокировавший вход в критическую область, освобождает его.

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

В этой ситуации mutex_lock ведет себя по-другому. Если войти в критическую область невозможно, mutexjock вызовет thread_yeld, чтобы предоставить процес­сор другому потоку. Активного ожидания здесь нет. При следующем запуске по­ток снова проверит блокировку.

Поскольку вызов threadjyeld является всего лишь обращением к планировщику потоков в пространстве пользователя, он выполняется очень быстро. Следователь­но, ни mutex_lock, ни mutexjunlock не требуют обращений к ядру. Синхронизация потоков на уровне пользователя происходит полностью в пространстве пользовате­ля, с применением процедур, состоящих всего из нескольких команд процессора.

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

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

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

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