Интернет магазин китайских планшетных компьютеров

Компьютеры - Монитор (синхронизация) - Условные переменные

Чтобы избегать состояния активного ожидания, процессы должны сигнализировать друг другу об ожидаемых событиях. Мониторы обеспечивают эту возможность с помощью условных переменных. Когда процедура монитора требует для дальнейшей работы выполнения определённого условия, она ждёт связанную с ним условную переменную. Во время ожидания она временно отпускает мьютекс и выбывает из списка исполняющихся процессов. Любой процесс, который в дальнейшем приводит к выполнению этого условия, использует условную переменную для оповещения ждущего её процесса. Оповещённый процесс захватывает мьютекс обратно и может продолжать.

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

monitor channel {
  int contents
  boolean full := false
  condition snd
  condition rcv

  function send {
    while full do wait   // семантика Mesa: см.ниже
    contents := message
    full := true
    notify
  }

  function receive {
    var int received

    while not full do wait   // семантика Mesa: см.ниже
    received := contents
    full := false
    notify
    return received
  }
}

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

Семантика Хоара и Mesa

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

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

В самых современных реализациях, оповещение не прерывает работающий процесс, а просто переводит некоторые ждущие процессы в состояние готовности. Оповещающий процесс продолжает держать блокировку до тех пор, пока не выйдет из процедуры монитора. Побочные эффекты этого подхода в том, что оповещающий процесс не обязан соблюсти инвариант перед оповещением, а ожидающий процесс — должен повторно проверить условие, которого он дожидается. В частности, если процедура монитора включает выражение if test then wait, другой процесс может войти в монитор после момента оповещения и изменить значение test до того, как ждущий процесс возобновит работу. Выражение нужно переписать так: while test do wait, чтобы условие было пере-проверено после ожидания.

Реализации также предоставляют операцию «notifyAll», или «broadcast», которая оповещает все процессы, ждущие данное условие. Эта операция полезна, например, когда несколько процессов ждут доступности различных объёмов памяти. Освобождение памяти позволит продолжить работу кого-то из них, но планировщик не может знать, кого именно.

Примерная реализация условной переменной:

conditionVariable {
  int queueSize = 0;
  semaphore lock;
  semaphore waiting;
  
  wait {
     lock.acquire;
     queueSize++;
     lock.release;
     waiting.down;
  }
  
  signal {
     lock.acquire;
     while{
        queueSize--;
        waiting.up;
     }
     lock.release;
  }
}