Монитор (синхронизация)

Монитор — в языках программирования высокоуровневый механизм взаимодействия и синхронизации процессов, обеспечивающий доступ к разделяемым ресурсам.[1] Подход к синхронизации двух или более компьютерных задач, использующих общий ресурс, обычно аппаратуру или набор переменных.

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

История

Пер Бринч Хансен был первым, кто описал и реализовал мониторы, основывая их на идеях Хоара. Впоследствии Хоар разработал теоретическую основу и показал её эквивалентность семафорам (используя исходную семантику). Впервые воплощён в языке Concurrent Pascal и использован для структурирования межпроцессного взаимодействия в операционной системе Solo.

Взаимоисключительность

Монитор состоит из:

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

Простой пример. Рассмотрим монитор, выполняющий транзакции банковского счёта.

monitor account {
  int balance := 0
  
  function withdraw(int amount) {
    if amount < 0 then error "Счёт не может быть отрицательным"
    else if balance < amount then error "Недостаток средств"
    else balance := balance - amount
  }
  
  function deposit(int amount) {
    if amount < 0 then error "Сумма не может быть отрицательной"
    else balance := balance + amount
  }
}

Инвариант здесь просто утверждает, что баланс должен отразить все прошедшие операции до того, как начнётся новая операция. Обычно это не выражено в коде, но подразумевается и может быть упомянуто в комментариях. Однако, есть языки программирования, такие как Эйфель или D, которые могут проверять инварианты. Блокировка добавлена компилятором. Это делает мониторы безопаснее и удобнее, чем другие подходы, требующие от программиста вручную добавлять операции блокировки-разблокировки, — поскольку программист может забыть добавить их.

Условные переменные

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

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

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

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

  function receive() {
    var int received

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

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

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

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

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

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

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

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

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

Применение

Языки программирования, поддерживающие мониторы:

См. также

Примечания
  1. Першиков В. И., Савинков В. М. Толковый словарь по информатике / Рецензенты: канд. физ.-мат. наук А. С. Марков и д-р физ.-мат. наук И. В. Поттосин. — М.: Финансы и статистика, 1991. — 543 с. — 50 000 экз. — ISBN 5-279-00367-0.
  2. Alan Burns, Andy Wellings. Concurrent and Real-Time Programming in Ada. — Cambridge University Press, 2007-07-05. — С. 44. — 476 с. — ISBN 9781139464352.
  3. P. J. Muller. The Active Object System. Design and Multiprocessor Implementation. - ETH Zurich, 2002

Литература

Ссылки


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.