Операционные системы. Кручинин А.Ю. - 8 стр.

      Но потребитель не был в состоянии ожидания, так что сигнал активизации
пропал впустую. Когда управление перейдет к потребителю, он вернется к
считанному когда-то значению count, обнаружит, что оно равно 0, и уйдет в
состояние ожидания. Рано или поздно производитель наполнит буфер и также уйдет
в состояние ожидания. Оба процесса так и останутся в этом состоянии.
      Суть проблемы в данном случае состоит в том, что сигнал активизации,
пришедший к процессу, не находящемуся в состоянии ожидания, пропадает. Если
бы не это, проблемы бы не было. Быстрым решением может быть добавление бита
ожидания активизации. Если сигнал активизации послан процессу, не находящемуся
в состоянии ожидания, этот бит устанавливается. Позже, когда процесс пытается
уйти в состояние ожидания, бит ожидания активизации сбрасывается, но процесс
остается активным. Этот бит исполняет роль копилки сигналов активизации.
      Несмотря на то что введение бита ожидания запуска спасло положение в этом
примере, легко сконструировать ситуацию с несколькими процессами, в которой
одного бита будет недостаточно. Мы можем добавить еще один бит, или 8, или 32,
но это не решит проблему.
      В 1965 году Дейкстра (Е. W. Dijkstra) предложил использовать целую
переменную для подсчета сигналов запуска, сохраненных на будущее. Им был
предложен новый тип переменных, так называемые семафоры, значение которых
может быть нулем (в случае отсутствия сохраненных сигналов активизации) или
некоторым положительным числом, соответствующим количеству отложенных
активизирующих сигналов.
      Дейкстра предложил две операции, down и up (обобщения sleep и wakeup).
Операция down сравнивает значение семафора с нулем. Если значение семафора
больше нуля, операция down уменьшает его (то есть расходует один из сохраненных
сигналов активации) и просто возвращает управление. Если значение семафора
равно нулю, процедура down не возвращает управление процессу, а процесс
переводится в состояние ожидания. Все операции проверки значения семафора, его
изменения и перевода процесса в состояние ожидания выполняются как единое и
неделимое элементарное действие. Тем самым гарантируется, что после начала
операции ни один процесс не получит доступа к семафору до окончания или
блокирования операции. Элементарность операции чрезвычайно важна для
разрешения проблемы синхронизации и предотвращения состояния состязания.
      Операция up увеличивает значение семафора. Если с этим семафором связаны
один или несколько ожидающих процессов, которые не могут завершить более
раннюю операцию down, один из них выбирается системой (например, случайным
образом) и ему разрешается завершить свою операцию down. Таким образом, после
операции up, примененной к семафору, связанному с несколькими ожидающими
процессами, значение семафора так и останется равным 0, но число ожидающих
процессов уменьшится на единицу. Операция увеличения значения семафора и
активизации процесса тоже неделима. Ни один процесс не может быть блокирован
во время выполнения операции up, как ни один процесс не мог быть блокирован во
время выполнения операции wakeup в предыдущей модели.
      В оригинале Дейкстра использовал вместо down и up обозначения Р и V
соответственно. Мы не будем в дальнейшем использовать оригинальные
                                                                             8