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

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

Другое определение монитора - потокобезопасный класс , объект или модуль, который обертывает мьютекс , чтобы безопасно разрешить доступ к методу или переменной более чем одному потоку . Определяющей характеристикой монитора является то, что его методы выполняются с взаимным исключением : в каждый момент времени максимум один поток может выполнять любой из его методов . Используя одну или несколько условных переменных, он также может предоставить возможность потокам ожидать определенного условия (таким образом, используя приведенное выше определение «монитора»). В остальной части этой статьи это понятие «монитор» будет называться «потокобезопасный объект / класс / модуль».

Мониторы были изобретены Пером Бринчем Хансеном и Карлом Хоаром и впервые были реализованы на языке Concurrent Pascal Бринча Хансена .

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

В качестве простого примера рассмотрим потокобезопасный объект для выполнения транзакций на банковском счете: 

monitor class Account {
    private int balance := 0
    invariant balance >= 0

    public method boolean withdraw(int amount)
        precondition amount >= 0
    {
        if balance < amount {
            return false
        } else {
            balance := balance - amount
            return true
        }
    }

    public method deposit(int amount)
        precondition amount >= 0
    {
        balance := balance + amount
    }
}

Когда поток выполняет метод поточно-безопасного объекта, говорят, что он занимает объект, удерживая его мьютекс (блокировку) . Реализованы потокобезопасные объекты для обеспечения того, чтобы в каждый момент времени максимум один поток мог занимать объект . Блокировка, которая изначально разблокирована, блокируется при запуске каждого общедоступного метода и разблокируется при каждом возврате из каждого общедоступного метода.

После вызова одного из методов поток должен дождаться, пока никакой другой поток не выполнит какой-либо из методов поточно-безопасного объекта, прежде чем начать выполнение своего метода. Обратите внимание, что без этого взаимного исключения в данном примере два потока могут привести к потере или получению денег без причины. Например, два потока, снимающие 1000 со счета, могут вернуть истину, в то время как баланс упадет только на 1000, как показано ниже: сначала оба потока извлекают текущий баланс, находят его больше 1000 и вычитают из него 1000; затем оба потока сохраняют баланс и возвращаются.

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

class Account {
    private lock myLock

    private int balance := 0
    invariant balance >= 0

    public method boolean withdraw(int amount)
       precondition amount >= 0
    {
        myLock.acquire()
        try {
            if balance < amount {
                return false
            } else {
                balance := balance - amount
                return true
            }
        } finally {
            myLock.release()
        }
    }

    public method deposit(int amount)
       precondition amount >= 0
    {
        myLock.acquire()
        try {
            balance := balance + amount
        } finally {
            myLock.release()
        }
    }
}

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

Постановка задачи

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

while not( P ) do skip

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

Пример: классическая проблема ограниченного производителя / потребителя

Классическая проблема параллелизма - это проблема ограниченного производителя / потребителя , в котором есть очередь или кольцевой буфер задач с максимальным размером, причем один или несколько потоков являются «производящими» потоками, которые добавляют задачи в очередь, и один или несколько другие потоки являются «потребительскими» потоками, которые берут задачи из очереди. Предполагается, что сама очередь не является потокобезопасной и может быть пустой, полной или между пустой и полной. Когда очередь заполняется задачами, нам нужно, чтобы потоки-производители блокировались, пока не останется место для потоков-потребителей, удаляющих задачи из очереди. С другой стороны, всякий раз, когда очередь пуста, нам нужно, чтобы потоки-потребители блокировались до тех пор, пока не станут доступны дополнительные задачи из-за добавления потоков-производителей.

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

Неправильно без синхронизации

Наивный подход заключается в разработке кода с ожиданием занятости и без синхронизации, что делает код зависимым от условий гонки: 

global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.
        while (queue.isFull()) {} // Busy-wait until the queue is non-full.
        queue.enqueue(myTask); // Add the task to the queue.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        while (queue.isEmpty()) {} // Busy-wait until the queue is non-empty.
        myTask = queue.dequeue(); // Take a task off of the queue.
        doStuff(myTask); // Go off and do something with the task.
    }
}

Этот код имеет серьезную проблему, заключающуюся в том, что доступ к очереди может прерываться и чередоваться с доступом других потоков к очереди. В queue.enqueue и queue.dequeue методы , вероятно , есть инструкции для обновления переменных членов , помещённых в очереди, такие как размер, начало и окончание позиций, назначение и распределение элементов очереди, и т.д. Кроме того, queue.isEmpty () и queue.isFull () методы также читают это общее состояние. Если потокам производителя / потребителя разрешено чередование во время вызовов для постановки / удаления из очереди, то может быть выявлено несогласованное состояние очереди, что приведет к условиям гонки. Вдобавок, если один потребитель делает очередь пустой между выходом другого потребителя из режима ожидания занятости и вызовом «dequeue», то второй потребитель попытается исключить очередь из пустой очереди, что приведет к ошибке. Аналогичным образом, если производитель заполняет очередь между выходом другого производителя из режима ожидания занятости и вызовом «enqueue», то второй производитель попытается добавить в полную очередь, что приведет к ошибке.

Спин-ожидание

Один наивный подход к достижению синхронизации, о котором говорилось выше, заключается в использовании « спин-ожидания », в котором мьютекс используется для защиты критических участков кода, а ожидание занятости по-прежнему используется, при этом блокировка захватывается и освобождается в между каждой проверкой занятости-ожидания. 

global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock; // A mutex for the ring-buffer of tasks.

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial busy-wait check.
        while (queue.isFull()) { // Busy-wait until the queue is non-full.
            queueLock.release();
            // Drop the lock temporarily to allow a chance for other threads
            // needing queueLock to run so that a consumer might take a task.
            queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isFull()".
        }

        queue.enqueue(myTask); // Add the task to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial busy-wait check.
        while (queue.isEmpty()) { // Busy-wait until the queue is non-empty.
            queueLock.release();
            // Drop the lock temporarily to allow a chance for other threads
            // needing queueLock to run so that a producer might add a task.
            queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isEmpty()".
        }
        myTask = queue.dequeue(); // Take a task off of the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.
        doStuff(myTask); // Go off and do something with the task.
    }
}

Этот метод гарантирует, что несогласованное состояние не возникает, но расходует ресурсы ЦП из-за ненужного ожидания занятости. Даже если очередь пуста и потокам-производителям нечего добавить в течение длительного времени, потоки-потребители всегда заняты и без необходимости ждут. Точно так же, даже если потребители заблокированы в течение длительного времени при обработке своих текущих задач и очередь заполнена, производители всегда заняты-ждут. Это расточительный механизм. Что необходимо, так это способ блокировки потоков-производителей до тех пор, пока очередь не будет заполнена, и способ блокировки потоков-потребителей до тех пор, пока очередь не станет пустой.

(NB: сами мьютексы также могут быть спин-блокировками, которые включают ожидание занятости для получения блокировки, но для решения этой проблемы потраченных впустую ресурсов ЦП мы предполагаем, что queueLock не является спин-блокировкой и правильно использует блокировку заблокировать саму очередь.)

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

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

Таким образом, над условными переменными выполняются три основные операции:

  • wait c, m, где c- условная переменная, а m- мьютекс (блокировка), связанный с монитором. Эта операция вызывается потоком, которому необходимо дождаться, пока утверждение P c не станет истинным, прежде чем продолжить. Пока поток ожидает, он не занимает монитор. Функция и основной контракт операции "ожидания" заключается в выполнении следующих шагов:
    1. Атомно :
      1. освободить мьютекс m,
      2. переместите этот поток из «запущенного» в c«очередь ожидания» (также известную как «спящая очередь») потоков, и
      3. спать эту ветку. (Контекст синхронно передается другому потоку.)
    2. После того, как этот поток впоследствии будет уведомлен / сигнализирован (см. Ниже) и возобновлен, он автоматически повторно получит мьютекс m.
    Шаги 1a и 1b могут выполняться в любом порядке, обычно после них следует 1c. Пока поток спит и находится в cочереди ожидания, следующий счетчик программы, который должен быть выполнен, находится на шаге 2, в середине функции / подпрограммы "ожидания" . Таким образом, поток засыпает, а затем просыпается в середине операции «ожидания».
    Атомарность операций на шаге 1 важна, чтобы избежать состояний гонки, которые могут быть вызваны вытесняющим переключением потоков между ними. Один из режимов отказа, который мог бы произойти, если бы они не были атомарными, - это пропущенное пробуждение , при котором поток мог находиться в cспящей очереди и освободил мьютекс, но упреждающее переключение потока произошло до того, как поток перешел в спящий режим, и другой поток вызывается операцией сигнал / уведомление (см. ниже) при cперемещении первого потока обратно из cочереди. Как только первый рассматриваемый поток будет переключен обратно, его программный счетчик будет на шаге 1c, и он перейдет в спящий режим и не сможет быть разбужен снова, нарушая инвариант, что он должен был находиться в cспящей очереди, когда он спал. Другие условия гонки зависят от порядка шагов 1a и 1b и зависят от того, где происходит переключение контекста.
  • signal c, также известный как notify c, вызывается потоком, чтобы указать, что утверждение P c истинно. В зависимости от типа и реализации монитора, это перемещает один или несколько потоков из cспящей очереди в «очередь готовности» или другую очередь для его выполнения. Обычно считается лучшей практикой выполнить операцию «сигнал» / «уведомление» перед освобождением mсвязанного с ним мьютекса c, но если код правильно разработан для параллелизма и в зависимости от реализации потоковой передачи, часто также приемлемо перед подачей сигнала отпустите блокировку. В зависимости от реализации многопоточности, порядок этого может иметь разветвления с приоритетом планирования. (Некоторые авторы вместо этого отстаивают предпочтение снятия блокировки перед сигнализацией.) Реализация потоковой передачи должна документировать любые специальные ограничения на этот порядок.
  • broadcast c, также известная как notifyAll c, - это аналогичная операция, которая пробуждает все потоки в очереди ожидания c. Это очищает очередь ожидания. Как правило, когда с одной и той же переменной условия связано более одного условия предиката, приложению потребуется широковещательная передача вместо сигнала, потому что поток, ожидающий неправильного условия, может быть разбужен, а затем немедленно вернуться в спящий режим без пробуждения потока, ожидающего правильное условие, которое только что стало верным. В противном случае, если условие предиката взаимно однозначно с связанной с ним переменной условия, тогда сигнал может быть более эффективным, чем широковещательный .

Как правило, несколько переменных состояния могут быть связаны с одним мьютексом, но не наоборот. (Это соответствие один-ко-многим .) Это связано с тем, что предикат P c одинаков для всех потоков, использующих монитор, и должен быть защищен взаимным исключением из всех других потоков, которые могут вызвать изменение условия или которое может прочтите его, пока рассматриваемый поток вызывает его изменение, но могут быть разные потоки, которые хотят дождаться другого условия для одной и той же переменной, требующего использования одного и того же мьютекса. В описанном выше примере производитель-потребитель очередь должна быть защищена уникальным мьютексным объектом m. Потоки-производители захотят ждать на мониторе, используя блокировку mи переменную условия, которая блокирует, пока очередь не будет заполнена. «Потребительские» потоки захотят ждать на другом мониторе, используя тот же мьютекс, но другую переменную условия, которая блокируется до тех пор, пока очередь не станет непустой. (Обычно) никогда не имеет смысла иметь разные мьютексы для одной и той же переменной условия, но этот классический пример показывает, почему часто, безусловно, имеет смысл иметь несколько переменных условия, использующих один и тот же мьютекс. Мьютекс, используемый одной или несколькими условными переменными (одним или несколькими мониторами), также может использоваться совместно с кодом, который не использует условные переменные (и который просто получает / освобождает его без каких-либо операций ожидания / сигнала), если эти критические разделы не происходят. требовать ожидания определенного условия для параллельных данных. m

Мониторинг использования

Правильное базовое использование монитора: 

acquire(m); // Acquire this monitor's lock.
while (!p) { // While the condition/predicate/assertion that we are waiting for is not true...
	wait(m, cv); // Wait on this monitor's lock and condition variable.
}
// ... Critical section of code goes here ...
signal(cv2); -- OR -- notifyAll(cv2); // cv2 might be the same as cv or different.
release(m); // Release this monitor's lock.

Если быть более точным, это тот же псевдокод, но с более подробными комментариями, чтобы лучше объяснить, что происходит: 

// ... (previous code)
// About to enter the monitor.
// Acquire the advisory mutex (lock) associated with the concurrent
// data that is shared between threads, 
// to ensure that no two threads can be preemptively interleaved or
// run simultaneously on different cores while executing in critical
// sections that read or write this same concurrent data. If another
// thread is holding this mutex, then this thread will be put to sleep
// (blocked) and placed on m's sleep queue.  (Mutex "m" shall not be
// a spin-lock.)
acquire(m);
// Now, we are holding the lock and can check the condition for the
// first time.

// The first time we execute the while loop condition after the above
// "acquire", we are asking, "Does the condition/predicate/assertion
// we are waiting for happen to already be true?"

while (!p()) 	// "p" is any expression (e.g. variable or 
		// function-call) that checks the condition and
		// evaluates to boolean.  This itself is a critical
		// section, so you *MUST* be holding the lock when
		// executing this "while" loop condition!
				
// If this is not the first time the "while" condition is being checked,
// then we are asking the question, "Now that another thread using this
// monitor has notified me and woken me up and I have been context-switched
// back to, did the condition/predicate/assertion we are waiting on stay
// true between the time that I was woken up and the time that I re-acquired
// the lock inside the "wait" call in the last iteration of this loop, or
// did some other thread cause the condition to become false again in the
// meantime thus making this a spurious wakeup?

{
	// If this is the first iteration of the loop, then the answer is
	// "no" -- the condition is not ready yet. Otherwise, the answer is:
	// the latter.  This was a spurious wakeup, some other thread occurred
	// first and caused the condition to become false again, and we must
	// wait again.

	wait(m, cv);
		// Temporarily prevent any other thread on any core from doing
		// operations on m or cv.
		// release(m) 		// Atomically release lock "m" so other
		//			// code using this concurrent data
		// 			// can operate, move this thread to cv's
		//			// wait-queue so that it will be notified
		//			// sometime when the condition becomes
		// 			// true, and sleep this thread. Re-enable
		//			// other threads and cores to do 
		//			// operations on m and cv.
		//
		// Context switch occurs on this core.
		//
		// At some future time, the condition we are waiting for becomes
		// true, and another thread using this monitor (m, cv) does either
		// a signal/notify that happens to wake this thread up, or a
		// notifyAll that wakes us up, meaning that we have been taken out
		// of cv's wait-queue.
		//
		// During this time, other threads may cause the condition to
		// become false again, or the condition may toggle one or more
		// times, or it may happen to stay true.
		//
		// This thread is switched back to on some core.
		//
		// acquire(m)		// Lock "m" is re-acquired.
		
	// End this loop iteration and re-check the "while" loop condition to make
	// sure the predicate is still true.
	
}

// The condition we are waiting for is true!
// We are still holding the lock, either from before entering the monitor or from
// the last execution of "wait".

// Critical section of code goes here, which has a precondition that our predicate
// must be true.
// This code might make cv's condition false, and/or make other condition variables'
// predicates true.

// Call signal/notify or notifyAll, depending on which condition variables'
// predicates (who share mutex m) have been made true or may have been made true,
// and the monitor semantic type being used.

for (cv_x in cvs_to_notify) {
	notify(cv_x); -- OR -- notifyAll(cv_x);
}
// One or more threads have been woken up but will block as soon as they try
// to acquire m.

// Release the mutex so that notified thread(s) and others can enter their critical
// sections.
release(m);

Решение ограниченной проблемы производителя / потребителя

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

global volatile RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock;  	// A mutex for the ring-buffer of tasks. (Not a spin-lock.)
global CV queueEmptyCV; 	// A condition variable for consumer threads waiting for the queue to 
				// become non-empty.
                        	// Its associated lock is "queueLock".
global CV queueFullCV; 		// A condition variable for producer threads waiting for the queue 
				// to become non-full. Its associated lock is also "queueLock".

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isFull()) { // Check if the queue is non-full.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto queueFullCV, and sleep this thread.
            wait(queueLock, queueFullCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        
        // Critical section that requires the queue to be non-full.
        // N.B.: We are holding queueLock.
        queue.enqueue(myTask); // Add the task to the queue.

        // Now the queue is guaranteed to be non-empty, so signal a consumer thread
        // or all consumer threads that might be blocked waiting for the queue to be non-empty:
        signal(queueEmptyCV); -- OR -- notifyAll(queueEmptyCV);
        
        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isEmpty()) { // Check if the queue is non-empty.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto queueEmptyCV, and sleep this thread.
            wait(queueLock, queueEmptyCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        // Critical section that requires the queue to be non-empty.
        // N.B.: We are holding queueLock.
        myTask = queue.dequeue(); // Take a task off of the queue.
        // Now the queue is guaranteed to be non-full, so signal a producer thread
        // or all producer threads that might be blocked waiting for the queue to be non-full:
        signal(queueFullCV); -- OR -- notifyAll(queueFullCV);

        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.

        doStuff(myTask); // Go off and do something with the task.
    }
}

Это обеспечивает параллелизм между потоками-производителями и потребителями, совместно использующими очередь задач, и блокирует потоки, которым нечего делать, а не ожидание занятости, как показано в вышеупомянутом подходе с использованием спин-блокировок.

Вариант этого решения может использовать одну переменную условия как для производителей, так и для потребителей, возможно, с именем «queueFullOrEmptyCV» или «queueSizeChangedCV». В этом случае с переменной условия связано более одного условия, так что переменная условия представляет более слабое условие, чем условия, проверяемые отдельными потоками. Переменная условия представляет потоки, которые ждут, пока очередь не будет заполнена, и потоки, ожидающие, что она будет непустой. Однако для этого потребуется использовать notifyAll во всех потоках, использующих переменную условия, и нельзя использовать обычный сигнал . Это связано с тем, что обычный сигнал может разбудить поток неправильного типа, условие которого еще не выполнено, и этот поток вернется в спящий режим без получения сигнала потока правильного типа. Например, производитель может заполнить очередь и разбудить другого производителя вместо потребителя, а проснувшийся производитель вернется в режим сна. В дополнительном случае потребитель может сделать очередь пустой и разбудить другого потребителя вместо производителя, и потребитель вернется в режим сна. Использование notifyAll гарантирует, что некоторый поток правильного типа будет работать так, как ожидалось в заявлении о проблеме.

Вот вариант, использующий только одну условную переменную и notifyAll: 

global volatile RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock; // A mutex for the ring-buffer of tasks.  (Not a spin-lock.)
global CV queueFullOrEmptyCV; // A single condition variable for when the queue is not ready for any thread
                              // -- i.e., for producer threads waiting for the queue to become non-full 
                              // and consumer threads waiting for the queue to become non-empty.
                              // Its associated lock is "queueLock".
                              // Not safe to use regular "signal" because it is associated with
                              // multiple predicate conditions (assertions).

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isFull()) { // Check if the queue is non-full.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto the CV, and sleep this thread.
            wait(queueLock, queueFullOrEmptyCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        
        // Critical section that requires the queue to be non-full.
        // N.B.: We are holding queueLock.
        queue.enqueue(myTask); // Add the task to the queue.

        // Now the queue is guaranteed to be non-empty, so signal all blocked threads
        // so that a consumer thread will take a task:
        notifyAll(queueFullOrEmptyCV); // Do not use "signal" (as it might wake up another producer instead).
        
        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isEmpty()) { // Check if the queue is non-empty.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto the CV, and sleep this thread.
            wait(queueLock, queueFullOrEmptyCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        // Critical section that requires the queue to be non-full.
        // N.B.: We are holding queueLock.
        myTask = queue.dequeue(); // Take a task off of the queue.

        // Now the queue is guaranteed to be non-full, so signal all blocked threads
        // so that a producer thread will take a task:
        notifyAll(queueFullOrEmptyCV); // Do not use "signal" (as it might wake up another consumer instead).

        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.

        doStuff(myTask); // Go off and do something with the task.
    }
}

Примитивы синхронизации

Для реализации мьютексов и условных переменных требуется какой-то примитив синхронизации, обеспечиваемый аппаратной поддержкой, обеспечивающей атомарность . Блокировки и условные переменные представляют собой абстракции более высокого уровня по сравнению с этими примитивами синхронизации. На однопроцессоре отключение и включение прерываний - это способ реализовать мониторы, предотвращая переключение контекста во время критических секций блокировок и переменных состояния, но этого недостаточно на многопроцессоре. На мультипроцессоре обычно используются специальные атомарные инструкции чтения-изменения-записи в памяти, такие как test-and-set , compare-and-swap и т. Д., В зависимости от того, что предоставляет ISA . Обычно для этого требуется отложить спин-блокировку для самого состояния внутренней блокировки, но эта блокировка очень краткая. В зависимости от реализации атомарные инструкции чтения-изменения-записи могут блокировать шину от доступа других ядер и / или предотвращать изменение порядка команд в ЦП. Вот пример реализации псевдокода частей системы потоковой передачи и мьютексов, а также переменных условий в стиле Mesa с использованием политики test-and-set и политики «первым пришел - первым обслужен». Это затушевывает большую часть того, как работает система потоков, но показывает части, относящиеся к мьютексам и условным переменным:

Пример реализации Mesa-монитора с помощью Test-and-Set

// Basic parts of threading system:
// Assume "ThreadQueue" supports random access.
public volatile ThreadQueue readyQueue; // Thread-unsafe queue of ready threads.  Elements are (Thread*).
public volatile global Thread* currentThread; // Assume this variable is per-core.  (Others are shared.)

// Implements a spin-lock on just the synchronized state of the threading system itself.
// This is used with test-and-set as the synchronization primitive.
public volatile global bool threadingSystemBusy = false;

// Context-switch interrupt service routine (ISR):
// On the current CPU core, preemptively switch to another thread.
public method contextSwitchISR() {
    if (testAndSet(threadingSystemBusy)) {
        return; // Can't switch context right now.
    }

    // Ensure this interrupt can't happen again which would foul up the context switch:
    systemCall_disableInterrupts();

    // Get all of the registers of the currently-running process.
    // For Program Counter (PC), we will need the instruction location of
    // the "resume" label below.  Getting the register values is platform-dependent and may involve
    // reading the current stack frame, JMP/CALL instructions, etc.  (The details are beyond this scope.)
    currentThread->registers = getAllRegisters(); // Store the registers in the "currentThread" object in memory.
    currentThread->registers.PC = resume; // Set the next PC to the "resume" label below in this method.

    readyQueue.enqueue(currentThread); // Put this thread back onto the ready queue for later execution.
    
    Thread* otherThread = readyQueue.dequeue(); // Remove and get the next thread to run from the ready queue.
    
    currentThread = otherThread; // Replace the global current-thread pointer value so it is ready for the next thread.

    // Restore the registers from currentThread/otherThread, including a jump to the stored PC of the other thread
    // (at "resume" below).  Again, the details of how this is done are beyond this scope.
    restoreRegisters(otherThread.registers);

    // *** Now running "otherThread" (which is now "currentThread")!  The original thread is now "sleeping". ***

    resume: // This is where another contextSwitch() call needs to set PC to when switching context back here.

    // Return to where otherThread left off.

    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
}

// Thread sleep method:
// On current CPU core, a synchronous context switch to another thread without putting
// the current thread on the ready queue.
// Must be holding "threadingSystemBusy" and disabled interrupts so that this method
// doesn't get interrupted by the thread-switching timer which would call contextSwitchISR().
// After returning from this method, must clear "threadingSystemBusy".
public method threadSleep() {
    // Get all of the registers of the currently-running process.
    // For Program Counter (PC), we will need the instruction location of
    // the "resume" label below.  Getting the register values is platform-dependent and may involve
    // reading the current stack frame, JMP/CALL instructions, etc.  (The details are beyond this scope.)
    currentThread->registers = getAllRegisters(); // Store the registers in the "currentThread" object in memory.
    currentThread->registers.PC = resume; // Set the next PC to the "resume" label below in this method.

    // Unlike contextSwitchISR(), we will not place currentThread back into readyQueue.
    // Instead, it has already been placed onto a mutex's or condition variable's queue.
    
    Thread* otherThread = readyQueue.dequeue(); // Remove and get the next thread to run from the ready queue.
    
    currentThread = otherThread; // Replace the global current-thread pointer value so it is ready for the next thread.

    // Restore the registers from currentThread/otherThread, including a jump to the stored PC of the other thread
    // (at "resume" below).  Again, the details of how this is done are beyond this scope.
    restoreRegisters(otherThread.registers);

    // *** Now running "otherThread" (which is now "currentThread")!  The original thread is now "sleeping". ***

    resume: // This is where another contextSwitch() call needs to set PC to when switching context back here.

    // Return to where otherThread left off.
}

public method wait(Mutex m, ConditionVariable c) {
    // Internal spin-lock while other threads on any core are accessing this object's
    // "held" and "threadQueue", or "readyQueue".
    while (testAndSet(threadingSystemBusy)) {}
    // N.B.: "threadingSystemBusy" is now true.
    
    // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
    // the thread-switching timer on this core which would call contextSwitchISR().
    // Done outside threadSleep() for more efficiency so that this thread will be sleeped
    // right after going on the condition-variable queue.
    systemCall_disableInterrupts();
 
    assert m.held; // (Specifically, this thread must be the one holding it.)
    
    m.release();
    c.waitingThreads.enqueue(currentThread);
    
    threadSleep();
    
    // Thread sleeps ... Thread gets woken up from a signal/broadcast.
    
    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    
    // Mesa style:
    // Context switches may now occur here, making the client caller's predicate false.
    
    m.acquire();
}

public method signal(ConditionVariable c) {
    // Internal spin-lock while other threads on any core are accessing this object's
    // "held" and "threadQueue", or "readyQueue".
    while (testAndSet(threadingSystemBusy)) {}
    // N.B.: "threadingSystemBusy" is now true.
    
    // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
    // the thread-switching timer on this core which would call contextSwitchISR().
    // Done outside threadSleep() for more efficiency so that this thread will be sleeped
    // right after going on the condition-variable queue.
    systemCall_disableInterrupts();
    
    if (!c.waitingThreads.isEmpty()) {
        wokenThread = c.waitingThreads.dequeue();
        readyQueue.enqueue(wokenThread);
    }
    
    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    
    // Mesa style:
    // The woken thread is not given any priority.
}

public method broadcast(ConditionVariable c) {
    // Internal spin-lock while other threads on any core are accessing this object's
    // "held" and "threadQueue", or "readyQueue".
    while (testAndSet(threadingSystemBusy)) {}
    // N.B.: "threadingSystemBusy" is now true.
    
    // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
    // the thread-switching timer on this core which would call contextSwitchISR().
    // Done outside threadSleep() for more efficiency so that this thread will be sleeped
    // right after going on the condition-variable queue.
    systemCall_disableInterrupts();
    
    while (!c.waitingThreads.isEmpty()) {
        wokenThread = c.waitingThreads.dequeue();
        readyQueue.enqueue(wokenThread);
    }
    
    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    
    // Mesa style:
    // The woken threads are not given any priority.
}

class Mutex {
    protected volatile bool held = false;
    private volatile ThreadQueue blockingThreads; // Thread-unsafe queue of blocked threads.  Elements are (Thread*).
    
    public method acquire() {
        // Internal spin-lock while other threads on any core are accessing this object's
        // "held" and "threadQueue", or "readyQueue".
        while (testAndSet(threadingSystemBusy)) {}
        // N.B.: "threadingSystemBusy" is now true.
        
        // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
        // the thread-switching timer on this core which would call contextSwitchISR().
        // Done outside threadSleep() for more efficiency so that this thread will be sleeped
        // right after going on the lock queue.
        systemCall_disableInterrupts();

        assert !blockingThreads.contains(currentThread);

        if (held) {
            // Put "currentThread" on this lock's queue so that it will be
            // considered "sleeping" on this lock.
            // Note that "currentThread" still needs to be handled by threadSleep().
            readyQueue.remove(currentThread);
            blockingThreads.enqueue(currentThread);
            threadSleep();
            
            // Now we are woken up, which must be because "held" became false.
            assert !held;
            assert !blockingThreads.contains(currentThread);
        }
        
        held = true;
        
        threadingSystemBusy = false; // Must be an atomic assignment.
        systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    }        
        
    public method release() {
        // Internal spin-lock while other threads on any core are accessing this object's
        // "held" and "threadQueue", or "readyQueue".
        while (testAndSet(threadingSystemBusy)) {}
        // N.B.: "threadingSystemBusy" is now true.
        
        // System call to disable interrupts on this core for efficiency.
        systemCall_disableInterrupts();
        
        assert held; // (Release should only be performed while the lock is held.)

        held = false;
        
        if (!blockingThreads.isEmpty()) {
            Thread* unblockedThread = blockingThreads.dequeue();
            readyQueue.enqueue(unblockedThread);
        }
        
        threadingSystemBusy = false; // Must be an atomic assignment.
        systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    }
}

struct ConditionVariable {
    volatile ThreadQueue waitingThreads;
}

Семафор

В качестве примера рассмотрим потокобезопасный класс, реализующий семафор . Существуют методы увеличения (V) и уменьшения (P) частного целого числа s. Однако целое число никогда не должно уменьшаться ниже 0; таким образом, поток, который пытается уменьшить, должен ждать, пока целое число не станет положительным. Мы используем условную переменную sIsPositiveс соответствующим утверждением . 

monitor class Semaphore
{
    private int s := 0
    invariant s >= 0
    private Condition sIsPositive /* associated with s > 0 */

    public method P()
    {
        while s = 0:
            wait sIsPositive
        assert s > 0
        s := s - 1
    }

    public method V()
    {
        s := s + 1
        assert s > 0
        signal sIsPositive
    }
}

Реализовано отображение всей синхронизации (удаление предположения о потокобезопасном классе и отображение мьютекса): 

class Semaphore
{
    private volatile int s := 0
    invariant s >= 0
    private ConditionVariable sIsPositive /* associated with s > 0 */
    private Mutex myLock /* Lock on "s" */

    public method P()
    {
        myLock.acquire()
        while s = 0:
            wait(myLock, sIsPositive)
        assert s > 0
        s := s - 1
        myLock.release()
    }

    public method V()
    {
        myLock.acquire()
        s := s + 1
        assert s > 0
        signal sIsPositive
        myLock.release()
    }
}

Монитор реализован с использованием семафоров

И наоборот, блокировки и переменные условия также могут быть получены из семафоров, что делает мониторы и семафоры сводимыми друг к другу:

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

public method wait(Mutex m, ConditionVariable c) {
    assert m.held;

    c.internalMutex.acquire();
    
    c.numWaiters++;
    m.release(); // Can go before/after the neighboring lines.
    c.internalMutex.release();

    // Another thread could signal here, but that's OK because of how
    // semaphores count.  If c.sem's number becomes 1, we'll have no
    // waiting time.
    c.sem.Proberen(); // Block on the CV.
    // Woken
    m.acquire(); // Re-acquire the mutex.
}

public method signal(ConditionVariable c) {
    c.internalMutex.acquire();
    if (c.numWaiters > 0) {
        c.numWaiters--;
        c.sem.Verhogen(); // (Doesn't need to be protected by c.internalMutex.)
    }
    c.internalMutex.release();
}

public method broadcast(ConditionVariable c) {
    c.internalMutex.acquire();
    while (c.numWaiters > 0) {
        c.numWaiters--;
        c.sem.Verhogen(); // (Doesn't need to be protected by c.internalMutex.)
    }
    c.internalMutex.release();
}

class Mutex {
    protected boolean held = false; // For assertions only, to make sure sem's number never goes > 1.
    protected Semaphore sem = Semaphore(1); // The number shall always be at most 1.
                                          // Not held <--> 1; held <--> 0.

    public method acquire() {
        sem.Proberen();
        assert !held;
        held = true;
    }
    
    public method release() {
        assert held; // Make sure we never Verhogen sem above 1.  That would be bad.
        held = false;
        sem.Verhogen();
    }
}

class ConditionVariable {
    protected int numWaiters = 0; // Roughly tracks the number of waiters blocked in sem.
                                // (The semaphore's internal state is necessarily private.)
    protected Semaphore sem = Semaphore(0); // Provides the wait queue.
    protected Mutex internalMutex; // (Really another Semaphore.  Protects "numWaiters".)
}

Когда сигнал поступает в переменную условия, которую ожидает хотя бы один другой поток, есть по крайней мере два потока, которые затем могут занять монитор: поток, который сигнализирует, и любой из потоков, которые ожидают. Чтобы не более одного потока занимали монитор каждый раз, необходимо сделать выбор. Существуют две точки зрения на то, как лучше всего решить этот выбор. Это приводит к двум типам условных переменных, которые будут рассмотрены далее:

  • Переменные условия блокировки отдают приоритет сигнализируемому потоку.
  • Неблокирующие условные переменные отдают приоритет сигнальному потоку.

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

Первоначальные предложения CAR Hoare и Per Brinch Hansen заключались в блокировании условных переменных . С переменной условия блокировки сигнальный поток должен ждать вне монитора (по крайней мере), пока сигнальный поток не освободит монитор, либо вернувшись, либо снова дождавшись переменной условия. Мониторы, использующие переменные условия блокировки, часто называют мониторами в стиле Хоара или мониторами ожидания и сигнала срочности .

Монитор в стиле Хоара с двумя переменными состояния aи b. После Buhr et al.

Мы предполагаем, что с каждым объектом монитора связаны две очереди потоков.

  • e очередь на вход
  • s это очередь потоков, которые отправили сигнал.

Кроме того, мы предполагаем, что для каждой переменной условия c существует очередь

  • c.q, которая представляет собой очередь для потоков, ожидающих переменной условия c

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

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

enter the monitor:
    enter the method
    if the monitor is locked
        add this thread to e
        block this thread
    else
        lock the monitor

leave the monitor:
    schedule
    return from the method

wait c:
    add this thread to c.q
    schedule
    block this thread

signal c:
    if there is a thread waiting on c.q
        select and remove one such thread t from c.q
        (t is called "the signaled thread")
        add this thread to s
        restart t
        (so t will occupy the monitor next)
        block this thread

schedule:
    if there is a thread on s
        select and remove one thread from s and restart it
        (this thread will occupy the monitor next)
    else if there is a thread on e
        select and remove one thread from e and restart it
        (this thread will occupy the monitor next)
    else
        unlock the monitor
        (the monitor will become unoccupied)

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

Результирующая дисциплина сигнализации известна как «ожидание сигнала и срочное ожидание», поскольку сигнализатор должен ждать, но ему дается приоритет над потоками во входной очереди. Альтернативой является «сигнал и ожидание», при котором нет sочереди, и eвместо этого сигнализатор ожидает в очереди.

Некоторые реализации предоставляют сигнал и операцию возврата, которая объединяет сигнализацию с возвратом из процедуры. 

signal c and return:
    if there is a thread waiting on c.q
        select and remove one such thread t from c.q
        (t is called "the signaled thread")
        restart t
        (so t will occupy the monitor next)
    else
        schedule
    return from the method

В любом случае («сигнал и срочное ожидание» или «сигнал и ожидание»), когда сигнализируется переменная условия и есть хотя бы один поток, ожидающий переменной условия, сигнальный поток передает занятость сигнализируемому потоку без проблем, поэтому что никакой другой поток не может занять промежуточное положение. Если P c истинно в начале каждой операции сигнала c , оно будет истинным в конце каждой операции ожидания c . Об этом свидетельствуют следующие контракты . В этих контрактах I - инвариант монитора . 

enter the monitor:
    postcondition I

leave the monitor:
    precondition I

wait c:
    precondition I
    modifies the state of the monitor
    postcondition Pc and I

signal c:
    precondition Pc and I
    modifies the state of the monitor
    postcondition I

signal c and return:
    precondition Pc and I

В этих контрактах предполагается, что I и P c не зависят от содержимого или длины каких-либо очередей.

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

wait c:
    precondition I
    modifies the state of the monitor
    postcondition Pc

signal c
    precondition (not empty(c) and Pc) or (empty(c) and I)
    modifies the state of the monitor
    postcondition I

(Для получения дополнительной информации см. Howard and Buhr et al .)

Здесь важно отметить, что утверждение P c полностью зависит от программиста; он или она просто должны быть последовательны в том, что это такое.

Мы завершаем этот раздел примером поточно-безопасного класса, использующего блокирующий монитор, который реализует ограниченный поточно-безопасный стек . 

monitor class SharedStack {
    private const capacity := 10
    private int[capacity] A
    private int size := 0
    invariant 0 <= size and size <= capacity
    private BlockingCondition theStackIsNotEmpty /* associated with 0 < size and size <= capacity */
    private BlockingCondition theStackIsNotFull /* associated with 0 <= size and size < capacity */

    public method push(int value)
    {
        if size = capacity then wait theStackIsNotFull
        assert 0 <= size and size < capacity
        A[size] := value ; size := size + 1
        assert 0 < size and size <= capacity
        signal theStackIsNotEmpty and return
    }

    public method int pop()
    {
        if size = 0 then wait theStackIsNotEmpty
        assert 0 < size and size <= capacity
        size := size - 1 ;
        assert 0 <= size and size < capacity
        signal theStackIsNotFull and return A[size]
    }
}

Обратите внимание, что в этом примере потокобезопасный стек внутренне предоставляет мьютекс, который, как и в предыдущем примере производителя / потребителя, совместно используется обеими переменными условий, которые проверяют разные условия для одних и тех же параллельных данных. Единственное отличие состоит в том, что в примере производителя / потребителя предполагалась обычная очередь, не обеспечивающая потокобезопасность, и использовались автономные мьютексные и условные переменные без абстрагирования этих деталей монитора, как здесь. В этом примере, когда вызывается операция «ожидание», она каким-то образом должна быть снабжена мьютексом поточно-безопасного стека, например, если операция «ожидание» является неотъемлемой частью «класса монитора». Помимо такой абстрактной функциональности, когда используется «сырой» монитор, он всегда должен включать мьютекс и переменную условия с уникальным мьютексом для каждой переменной условия.

Неблокирующие переменные условия

С неблокирующими условными переменными (также называемыми условными переменными «стиля Mesa» или условными переменными «сигнал и продолжение» ) сигнализация не заставляет сигнальный поток терять занятость монитора. Вместо этого сигнальные потоки перемещаются в eочередь. sОчередь не нужна .

Монитор в стиле Mesa с двумя переменными состояния aиb

С неблокирующими условными переменными операция сигнала часто называется уведомлением - терминология, которой мы будем следовать здесь. Также обычно предоставляют операцию notify all, которая перемещает все потоки, ожидающие переменной условия, в eочередь.

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

enter the monitor:
    enter the method
    if the monitor is locked
        add this thread to e
        block this thread
    else
        lock the monitor

leave the monitor:
    schedule
    return from the method

wait c:
    add this thread to c.q
    schedule
    block this thread

notify c:
    if there is a thread waiting on c.q
        select and remove one thread t from c.q
        (t is called "the notified thread")
        move t to e

notify all c:
    move all threads waiting on c.q to e

schedule :
    if there is a thread on e
        select and remove one thread from e and restart it
    else
        unlock the monitor

Как вариант этой схемы, уведомленный поток может быть перемещен в вызываемую очередь w, которая имеет приоритет над e. См. Howard and Buhr et al. для дальнейшего обсуждения.

Можно связать утверждение P c с каждой переменной условия c , так что P c обязательно будет истинным после возврата из . Однако необходимо гарантировать, что P c сохраняется с момента, когда уведомляющий поток отказывается от занятости, до тех пор, пока уведомляемый поток не будет выбран для повторного входа в монитор. В это время могли быть активны другие обитатели. Таким образом, обычно P c просто истинно . wait c

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

while not( P ) do
    wait c

где P - некоторое условие, более сильное, чем P c . Операции и рассматриваются как «намеки» на то, что P может быть истинным для некоторого ожидающего потока. Каждая итерация такого цикла после первой представляет потерянное уведомление; таким образом, с неблокирующими мониторами нужно быть осторожным, чтобы не потерять слишком много уведомлений. notify cnotify all c

В качестве примера "подсказки" рассмотрим банковский счет, на котором поток вывода будет ждать, пока на счете будет достаточно средств, прежде чем продолжить. 

monitor class Account {
    private int balance := 0
    invariant balance >= 0
    private NonblockingCondition balanceMayBeBigEnough

    public method withdraw(int amount)
        precondition amount >= 0
    {
        while balance < amount do wait balanceMayBeBigEnough
        assert balance >= amount
        balance := balance - amount
    }

    public method deposit(int amount)
        precondition amount >= 0
    {
        balance := balance + amount
        notify all balanceMayBeBigEnough
    }
}

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

Неявные мониторы переменных условий

Монитор в стиле Java

В языке Java каждый объект может использоваться как монитор. Методы, требующие взаимного исключения, должны быть явно помечены ключевым словом synchronized . Блоки кода также могут быть помечены как синхронизированные .

Вместо того, чтобы иметь явные переменные условия, каждый монитор (т. Е. Объект) снабжен единственной очередью ожидания в дополнение к своей очереди на вход. Все ожидания делается на этой одной очереди ожидания и все оповещать и notifyAll операции относятся к этой очереди. Этот подход был принят в других языках, например C # .

Неявная сигнализация

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

wait P:
    precondition I
    modifies the state of the monitor
    postcondition P and I

История

Бринч Хансен и Хоар разработали концепцию монитора в начале 1970-х, основываясь на более ранних собственных идеях и идеях Эдсгера Дейкстры . Бринч Хансен опубликовал первую нотацию монитора, приняв концепцию классов Simula 67 , и изобрел механизм очередей. Хоар уточнил правила возобновления процесса. Бринч Хансен создал первую реализацию мониторов на Concurrent Pascal . Хоар продемонстрировал их эквивалентность семафорам .

Мониторы (и Concurrent Pascal) вскоре стали использоваться для структурирования синхронизации процессов в операционной системе Solo .

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

Был написан ряд библиотек, которые позволяют создавать мониторы на языках, которые не поддерживают их изначально. Когда используются библиотечные вызовы, программист должен явно отметить начало и конец кода, выполняемого с взаимным исключением. Pthreads - одна из таких библиотек.

Смотрите также

Заметки

дальнейшее чтение

  • Мониторы: концепция структурирования операционной системы, CAR Hoare - Communications of the ACM , v.17 n.10, p. 549–557, октябрь 1974 г. [1]
  • Классификация мониторов PA Buhr, M. Fortier, MH Coffin - ACM Computing Surveys , 1995 [2]

Внешние ссылки