Модуль Условий

Переменные условия.

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

Переменная условия — это канал связи. Со стороны получателя один или несколько потоков могут указать, что они хотят ожидать, пока определенное свойство не станет истинным. Со стороны отправителя поток может сигнализировать, что это свойство стало истинным, вызывая пробуждение одного (или нескольких) ожидающих потоков.

Например, в реализации структуры данных очереди, если поток, желающий извлечь элемент, обнаруживает, что очередь пуста, то этот поток ожидает, пока очередь не станет непустой. Поток, вставляющий элемент в очередь, сигнализирует о том, что очередь стала непустой. Для этой цели используется переменная условия. Этот канал связи передает информацию о том, что свойство «очередь непуста» истинно, или, точнее, может быть истинным. (Ниже мы объясним, почему получатель сигнала не может быть уверен, что свойство выполняется.)

Продолжая пример очереди, предположим, что очередь имеет фиксированную максимальную емкость, тогда поток, желающий вставить элемент, может обнаружить, что очередь полна. Тогда этот поток должен ждать, пока очередь не станет неполной, и поток, извлекающий элемент из очереди, сигнализирует о том, что очередь стала неполной. Для этой цели используется другая переменная условия.

Короче говоря, переменная условия c используется для передачи информации о том, что определенное свойство P относительно общей структуры данных D, защищенной мьютексом m, может быть истинным.

Переменные условия предоставляют эффективный альтернативный способ по сравнению с ожиданиями в цикле. Когда необходимо дождаться, пока свойство P станет истинным, вместо написания цикла ожидания в цикле:

     Mutex.lock m;
     while not P do
       Mutex.unlock m; Mutex.lock m
     done;
     <update the data structure>;
     Mutex.unlock m
   

используется Condition.wait в теле цикла, как показано ниже:

     Mutex.lock m;
     while not P do
       Condition.wait c m
     done;
     <update the data structure>;
     Mutex.unlock m
   

Цикл ожидания в цикле неэффективен, потому что ожидающий поток потребляет время обработки и создает конфликт мьютекса m. Вызов Condition.wait позволяет приостановить ожидающий поток, поэтому он не потребляет вычислительные ресурсы во время ожидания.

С переменной условия c, точно один мьютекс m ассоциируется. Эта ассоциация неявная: мьютекс m не передаётся явно как аргумент для Condition.create. Программист должен знать для каждой переменной условия c, какой мьютекс m с ней ассоциирован.

С мьютексом m, с ним могут быть связаны несколько переменных условий. В примере ограниченной очереди одна переменная условия используется для обозначения того, что очередь непуста, а другая — для обозначения того, что очередь неполна.

С переменной условия c, должно быть связано ровно одно логическое свойство P. Примеры таких свойств включают «очередь непуста» и «очередь неполна». Программист должен отслеживать для каждой переменной условия соответствующее свойство P. Сигнал отправляется на переменную условия c как указание того, что свойство P истинно или может быть истинным. Однако на принимающей стороне поток, который был разбужен, не может предположить, что P истинно; после завершения вызова Condition.wait, необходимо явно проверить, является ли P истинным. Существует несколько причин для этого. Одна из причин заключается в том, что между моментом отправки сигнала и моментом, когда ожидающий поток получает сигнал и планируется, свойство P может быть ложным другим потоком, который может получить мьютекс m и изменить структуру данных D. Другая причина заключается в том, что могут произойти ложные пробуждения: ожидающий поток может быть разбужен, даже если сигнал не был отправлен.

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

     type 'a safe_queue =
       { queue : 'a Queue.t; mutex : Mutex.t; nonempty : Condition.t }

     let create () =
       { queue = Queue.create(); mutex = Mutex.create();
         nonempty = Condition.create() }

     let add v q =
       Mutex.lock q.mutex;
       let was_empty = Queue.is_empty q.queue in
       Queue.add v q.queue;
       if was_empty then Condition.broadcast q.nonempty;
       Mutex.unlock q.mutex

     let take q =
       Mutex.lock q.mutex;
       while Queue.is_empty q.queue do Condition.wait q.nonempty q.mutex done;
       let v = Queue.take q.queue in (* cannot fail since queue is nonempty *)
       Mutex.unlock q.mutex;
       v
   

Поскольку вызов Condition.broadcast выполняется внутри критической секции, следующее свойство выполняется всякий раз, когда мьютекс разблокирован: если очередь непуста, то ни один поток не ожидает или, другими словами, если какой-то поток ожидает, то очередь должна быть пустой. Это желаемое свойство: если поток, пытающийся выполнить операцию take, может остаться приостановленным, даже если очередь непуста, это будет проблематичная ситуация, известная как тупик.