Эта проблема называется проблемой ограниченного буфера. Если один процесс (производитель) помещает данные в буфер, а другой процесс (потребитель), забирает их оттуда – может возникнуть проблема. Трудности могут возникнуть в момент, когда производитель хочет поместить в буфер очередную порцию данных, но обнаруживает, что буфер полон. Для производителя решением является ожидание, пока потребитель полностью или частично не освободит буфер. Аналогично, если потребитель хочет забрать данные из буфера, а он пуст, потребитель уходит в состояние ожидания до тех пор, пока производитель что-нибудь не положит туда и не разбудит потребителя. Это решение является простым, однако оно приводит к состоянию состязания, когда оба процесса могут оказаться в состоянии ожидания. Решением может быть использование бита ожидания активации. Если сигнал активации послан процессу, не находящемуся в состоянии ожидания, этот бит устанавливается. Позднее, когда процесс пытается уйти в состояние ожидания – бит активации сбрасывается, но процесс остается активным. Этот бит играет роль «копилки» сигналов активации.
СЕМАФОРЫ
В 1965 г. Дейкстра предложил использовать целую переменную для подсчета сигналов запуска, сохраненных на будущее. Им был предложен новый тип переменных – семафоры, значение которых может быть нулем (в случае отсутствия сохраненных сигналов активации) или некоторым положительным числом, соответствующим количеству отложенных активирующих сигналов. Он предложил две операции: down и up. Операция down сравнивает значение семафора с нулем. Если значение семафора >0, то операция down уменьшает его, т.е. расходует один из отложенных сигналов активации, и возвращает управление. Если значение семафора равно нулю – то процедура не возвращает управление процессу, а он сам переводится в состояние ожидания. Все операции проверки значения семафора, его изменение или переводы процессов в состоянии ожидания, выполняется как единое, не делимое, элементарное действие. Тем самым гарантируется, что после начала операции ни один процесс не получит доступа к семафору до окончания, либо блокировки операции. Операция up – увеличивает значение семафора. Если с ним связаны один или несколько ожидающих процессов, которые не могут завершить более раннюю операцию down, один из них выбирается системой, напр., случайным образом, и ему разрешается завершить свою операцию down. Т.О. после операции up, примененной к семафору, связанному с несколькими ожидающими процессами, значение семафора так и остается равным нулю. Но за то число ожидающих процессов уменьшается на единицу. Операция увеличения значения семафора и активации процесса также неделимы, т.е. ни один процесс не может быть блокирован во время выполнения операции up, также, как ни один процесс не может быть блокирован во время выполнения операции.
Семафоры. Решение проблемы производителя и потребителя
Проблему потерянных сигналов запуска можно решить с помощью семафоров. Стандартным решением является реализация операций down и up в виде системных запросов с запретом ОС всех прерываний на время проверки семафора, изменение его значения и возможного перевода процесса в состояние ожидания. Поскольку для выполнения всех этих действий требуется лишь несколько команд процессора запрет прерываний на столь короткий промежуток времени не приносит вреда. Если используется несколько процессов, каждый семафор необходимо защитить переменной блокировки с использованием команды ТSL, чтобы гарантировать обращение к семафору лишь одного процесса. Использование команды ТSL принципиально отличается от активного ожидания, при котором производитель и потребитель ждут опорожнения или пополнения буфера. Операции с семафором занимают лишь несколько микросекунд, тогда как активное ожидание может затянуться на время, больше нескольких порядков.
МЬЮТЕКСЫ
Взаимное исключение. Иногда используется упрощенная версия семафора, называемая мьютексом. Мьютекс не способен считать, он может лишь управлять взаимным исключением доступа к совместно используемым ресурсам или кодам. Реализация мьютекса проста и эффективна, что делает их использование особенно удобным в случае потоков, действующих только в пространстве пользователя. Мьютекс – это переменная, которая может находиться в одном из двух состояний, блокированном и не блокированном. Потому для описания мьютекса нужен всего 1 бит, хотя чаще используется целочисленная переменная, у которой: 0 – не блокируемое состояние, а любое другое положительное целое, соответствует блокируемому состоянию. Значение мьютекса устанавливается двумя процедурами. Если поток (процесс) собирается войти в критическую область – он вызывает процедуру мьютекс-lock. Если Мьютекс не заблокирован (вход в критическую область разрешен), запрос выполняется и вызывающий поток может попасть в критическую область. Напротив, если Мьютекс заблокирован, вызывающий поток блокируется до тех пор, пока другой поток, находящийся в критической области не выйдет из нее, вызвав процедуру Мьютекс-anlock. Если мьютекс блокирует несколько потоков, то из них случайным образом выбирается один. Мьютексы легко реализуются в пространстве пользователя, если доступна команда DSL.