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

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

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

Мониторы были изобретены Пер Бринч Хансен[1] и К. А. Р. Хоар,[2] и были впервые реализованы в Бринч Хансен Параллельный Паскаль язык.[3]

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

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

класс монитора Счет {    частный int баланс: = 0 инвариантный баланс> = 0 публичный метод логический снять со счета(int количество) предварительное условие amount> = 0 { если balance вернуть ложь        } еще {баланс: = баланс - сумма вернуть истину        }    }    публичный метод депозит (int количество) предварительное условие сумма> = 0 {баланс: = баланс + сумма}}

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

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

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

учебный класс Счет {    частный замок myLock частный int баланс: = 0 инвариантный баланс> = 0 публичный метод логический снять со счета(int количество) предварительное условие количество> = 0 {myLock.acquire () пытаться {            если balance вернуть ложь            } еще {баланс: = баланс - сумма вернуть истину            }        } наконец-то {myLock.release ()}} публичный метод депозит (int количество) предварительное условие количество> = 0 {myLock.acquire () пытаться {баланс: = баланс + сумма} наконец-то {myLock.release ()}}}

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

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

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

пока нет( п ) делать пропускать

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

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

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

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

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

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

Глобальный RingBuffer очередь; // Небезопасный для потоков кольцевой буфер задач.// Метод, представляющий поведение каждого потока-производителя:общественный метод режиссер() {    пока (истинный) {        задача мое задание = ...; // Продюсер добавляет новую задачу.        пока (очередь.полон()) {} // Занят - ждем, пока очередь не заполнится.        очередь.ставить в очередь(мое задание); // Добавляем задачу в очередь.    }}// Метод, представляющий поведение каждого потребительского потока:общественный метод потребитель() {    пока (истинный) {        пока (очередь.пусто()) {} // Занят - ждем, пока очередь не станет пустой.        мое задание = очередь.исключать из очереди(); // Снимаем задачу из очереди.        doStuff(мое задание); // Уходим и делаем что-нибудь с задачей.    }}

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

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

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

Глобальный RingBuffer очередь; // Небезопасный для потоков кольцевой буфер задач.Глобальный Замок queueLock; // Мьютекс для кольцевого буфера задач.// Метод, представляющий поведение каждого потока-производителя:общественный метод режиссер() {    пока (истинный) {        задача мое задание = ...; // Продюсер добавляет новую задачу.        queueLock.приобретать(); // Получение блокировки для начальной проверки ожидания-занятости.        пока (очередь.полон()) { // Занят - ждем, пока очередь не заполнится.            queueLock.релиз();            // Временно снимаем блокировку, чтобы дать шанс другим потокам            // требуется выполнение queueLock, чтобы потребитель мог выполнить задачу.            queueLock.приобретать(); // Повторное получение блокировки для следующего вызова queue.isFull ().        }        очередь.ставить в очередь(мое задание); // Добавляем задачу в очередь.        queueLock.релиз(); // Снимаем блокировку очереди, пока она нам снова не понадобится для добавления следующей задачи.    }}// Метод, представляющий поведение каждого потребительского потока:общественный метод потребитель() {    пока (истинный) {        queueLock.приобретать(); // Получение блокировки для начальной проверки ожидания-занятости.        пока (очередь.пусто()) { // Занят - ждем, пока очередь не станет пустой.            queueLock.релиз();            // Временно снимаем блокировку, чтобы дать шанс другим потокам            // требуется выполнение queueLock, чтобы производитель мог добавить задачу.            queueLock.приобретать(); // Повторное получение блокировки для следующего вызова queue.isEmpty ().        }        мое задание = очередь.исключать из очереди(); // Снимаем задачу из очереди.        queueLock.релиз(); // Снимаем блокировку очереди до тех пор, пока она нам снова не понадобится для выполнения следующей задачи.        doStuff(мое задание); // Уходим и делаем что-нибудь с задачей.    }}

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

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

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

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

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

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

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

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

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

приобретать(м); // Получение блокировки этого монитора.пока (!п) { // Пока условие / предикат / утверждение, которого мы ждем, не соответствует действительности ...	ждать(м, резюме); // Ожидание переменной блокировки и состояния этого монитора.}// ... Здесь находится критическая часть кода ...сигнал(cv2); -- ИЛИ ЖЕ -- notifyAll(cv2); // cv2 может совпадать с cv или отличаться от него.релиз(м); // Снимаем блокировку этого монитора.

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

// ... (предыдущий код)// Собираемся войти в монитор.// Получение рекомендательного мьютекса (блокировки), связанного с параллельным// данные, которые разделяются между потоками, // чтобы гарантировать, что никакие два потока не могут чередоваться с приоритетом или// работать одновременно на разных ядрах при выполнении в критических// разделы, которые читают или записывают одни и те же параллельные данные. Если другой// поток удерживает этот мьютекс, тогда этот поток будет переведен в спящий режим// (заблокирован) и помещен в очередь ожидания m. (Мьютекс «м» не подлежит// спин-блокировка.)приобретать(м);// Теперь мы удерживаем блокировку и можем проверить условие для// первый раз.// В первый раз мы выполняем условие цикла while после указанного выше// "получить", мы спрашиваем: "Есть ли условие / предикат / утверждение// ждем, когда это уже будет правдой? "пока (!п()) 	// "p" - любое выражение (например, переменная или 		// вызов функции), который проверяет условие и		// оценивается как логическое. Это само по себе критическое		// раздел, поэтому вы * ДОЛЖНЫ * удерживать блокировку, когда		// выполнение этого условия цикла "while"!				// Если это не первый раз, когда проверяется условие "while",// тогда мы задаем вопрос: "Теперь, когда другой поток, использующий это// монитор уведомил меня и разбудил меня, и у меня был переключен контекст// возвращаемся к выполнению условия / предиката / утверждения, которое мы ждем// истина между временем, когда меня разбудили, и временем, когда я снова приобрел// блокировка внутри вызова "ожидания" на последней итерации этого цикла, или// заставил ли какой-то другой поток снова стать ложным условие в// тем временем, что делает это ложным пробуждением?{	// Если это первая итерация цикла, то ответ будет	// «нет» - условие еще не готово. В противном случае ответ таков:	// последний. Это было ложное пробуждение, произошла какая-то другая тема	// сначала и заставил условие снова стать ложным, и мы должны	// ждем снова.	ждать(м, резюме);		// Временно запрещаем выполнение любого другого потока на любом ядре		// операции с m или cv.		// release (m) // Атомарно снимаем блокировку "m", чтобы остальные		// // код, использующий эти параллельные данные		// // можно работать, переместите этот поток в cv		// // очередь ожидания, чтобы было уведомление		// // когда-нибудь, когда условие станет		// // true, и засыпаем этот поток. Повторно включить		// // другие потоки и ядра, которые нужно сделать 		// // операции с m и cv.		//		// На этом ядре происходит переключение контекста.		//		// В будущем условие, которого мы ждем, станет		// true, а другой поток, использующий этот монитор (m, cv), либо		// сигнал / уведомление, которое пробуждает этот поток, или		// notifyAll, что нас будит, что означает, что нас вывели		// очереди ожидания резюме.		//		// В это время другие потоки могут вызвать условие		// снова становится ложным, или условие может переключить одно или несколько		// раз, или может случиться так, что оно останется верным.		//		// Этот поток снова переключается на какое-то ядро.		//		// accept (m) // Блокировка "m" повторно захвачена.			// Завершаем эту итерацию цикла и еще раз проверяем условие цикла "while", чтобы	// уверен, что предикат все еще верен.	}// Условие, которого мы ждем, верно!// Мы все еще удерживаем блокировку, либо до входа в монитор, либо от// последнее выполнение "ожидания".// Здесь идет критический раздел кода, который имеет предварительное условие, что наш предикат// должно быть верно.// Этот код может сделать условие cv ложным и / или сделать другие переменные условия '// предикаты истинны.// Вызвать сигнал / уведомить или notifyAll, в зависимости от того, какие переменные условия '// предикаты (которые разделяют мьютекс m) стали истинными или могли стать истинными,// и используемый семантический тип монитора.за (cv_x в cvs_to_notify) {	уведомлять(cv_x); -- ИЛИ ЖЕ -- notifyAll(cv_x);}// Один или несколько потоков были разбужены, но будут заблокированы, как только попытаются// приобрести м.// Освобождаем мьютекс, чтобы уведомленные потоки и другие могли ввести свои критические// разделы.релиз(м);

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

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

Глобальный летучий RingBuffer очередь; // Небезопасный для потоков кольцевой буфер задач.Глобальный Замок queueLock;  	// Мьютекс для кольцевого буфера задач. (Не спин-лок.)Глобальный резюме queueEmptyCV; 	// Переменная условия для потребительских потоков, ожидающих очереди в 				// стать непустым.                        	// Связанная с ним блокировка - "queueLock".Глобальный резюме queueFullCV; 		// Переменная условия для потоков-производителей, ожидающих очереди 				// стать неполным. Связанная с ним блокировка также называется queueLock.// Метод, представляющий поведение каждого потока-производителя:общественный метод режиссер() {    пока (истинный) {        задача мое задание = ...; // Продюсер добавляет новую задачу.        queueLock.приобретать(); // Получение блокировки для начальной проверки предиката.        пока (очередь.полон()) { // Проверяем, не заполнена ли очередь.            // Заставляем поточную систему атомарно освободить queueLock,            // поставить этот поток в очередь на queueFullCV и засыпать этот поток.            ждать(queueLock, queueFullCV);            // Затем "wait" автоматически повторно получает "queueLock" для повторной проверки            // условие предиката.        }                // Критический раздел, требующий неполного заполнения очереди.        // N.B .: У нас есть queueLock.        очередь.ставить в очередь(мое задание); // Добавляем задачу в очередь.        // Теперь очередь гарантированно непуста, поэтому сигнализируем потоку-потребителю        // или все потребительские потоки, которые могут быть заблокированы в ожидании непустой очереди:        сигнал(queueEmptyCV); -- ИЛИ ЖЕ -- notifyAll(queueEmptyCV);                // Конец критических секций, относящихся к очереди.        queueLock.релиз(); // Снимаем блокировку очереди, пока она нам снова не понадобится для добавления следующей задачи.    }}// Метод, представляющий поведение каждого потребительского потока:общественный метод потребитель() {    пока (истинный) {        queueLock.приобретать(); // Получение блокировки для начальной проверки предиката.        пока (очередь.пусто()) { // Проверяем, не пуста ли очередь.            // Заставляем поточную систему атомарно освободить queueLock,            // ставим этот поток в очередь queueEmptyCV и засыпаем этот поток.            ждать(queueLock, queueEmptyCV);            // Затем "wait" автоматически повторно получает "queueLock" для повторной проверки            // условие предиката.        }        // Критический раздел, который требует, чтобы очередь была непустой.        // N.B .: У нас есть queueLock.        мое задание = очередь.исключать из очереди(); // Снимаем задачу из очереди.        // Теперь очередь гарантированно не заполнена, поэтому сигнализируйте потоку производителя        // или все потоки-производители, которые могут быть заблокированы в ожидании неполного заполнения очереди:        сигнал(queueFullCV); -- ИЛИ ЖЕ -- notifyAll(queueFullCV);        // Конец критических секций, относящихся к очереди.        queueLock.релиз(); // Снимаем блокировку очереди до тех пор, пока она нам снова не понадобится для выполнения следующей задачи.        doStuff(мое задание); // Уходим и делаем что-нибудь с задачей.    }}

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

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

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

Глобальный летучий RingBuffer очередь; // Небезопасный для потоков кольцевой буфер задач.Глобальный Замок queueLock; // Мьютекс для кольцевого буфера задач. (Не спин-лок.)Глобальный резюме queueFullOrEmptyCV; // Единственная условная переменная, когда очередь не готова ни для одного потока                              // - то есть для потоков-производителей, ожидающих неполного заполнения очереди                               // и потребительские потоки ждут, пока очередь не станет непустой.                              // Связанная с ним блокировка - "queueLock".                              // Небезопасно использовать обычный "сигнал", потому что он связан с                              // несколько условий предиката (утверждения).// Метод, представляющий поведение каждого потока-производителя:общественный метод режиссер() {    пока (истинный) {        задача мое задание = ...; // Продюсер добавляет новую задачу.        queueLock.приобретать(); // Получение блокировки для начальной проверки предиката.        пока (очередь.полон()) { // Проверяем, не заполнена ли очередь.            // Заставляем поточную систему атомарно освободить queueLock,            // поставить этот поток в очередь на CV и приостановить этот поток.            ждать(queueLock, queueFullOrEmptyCV);            // Затем "wait" автоматически повторно получает "queueLock" для повторной проверки            // условие предиката.        }                // Критический раздел, требующий неполного заполнения очереди.        // N.B .: У нас есть queueLock.        очередь.ставить в очередь(мое задание); // Добавляем задачу в очередь.        // Теперь очередь гарантированно непуста, поэтому сигнализируем всем заблокированным потокам        // чтобы потребительский поток выполнял задачу:        notifyAll(queueFullOrEmptyCV); // Не используйте "сигнал" (вместо этого он может разбудить другого производителя).                // Конец критических секций, относящихся к очереди.        queueLock.релиз(); // Снимаем блокировку очереди, пока она нам снова не понадобится для добавления следующей задачи.    }}// Метод, представляющий поведение каждого потребительского потока:общественный метод потребитель() {    пока (истинный) {        queueLock.приобретать(); // Получение блокировки для начальной проверки предиката.        пока (очередь.пусто()) { // Проверяем, не пуста ли очередь.            // Заставляем поточную систему атомарно освободить queueLock,            // поставить этот поток в очередь на CV и приостановить этот поток.            ждать(queueLock, queueFullOrEmptyCV);            // Затем "wait" автоматически повторно получает "queueLock" для повторной проверки            // условие предиката.        }        // Критический раздел, требующий неполного заполнения очереди.        // N.B .: У нас есть queueLock.        мое задание = очередь.исключать из очереди(); // Снимаем задачу из очереди.        // Теперь очередь гарантированно не заполнена, поэтому сигнализируем всем заблокированным потокам        // чтобы поток-производитель взял задачу:        notifyAll(queueFullOrEmptyCV); // Не используйте «сигнал» (вместо этого он может разбудить другого потребителя).        // Конец критических секций, относящихся к очереди.        queueLock.релиз(); // Снимаем блокировку очереди до тех пор, пока она нам снова не понадобится для выполнения следующей задачи.        doStuff(мое задание); // Уходим и делаем что-нибудь с задачей.    }}

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

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

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

// Основные части системы потоковой передачи:// Предположим, что ThreadQueue поддерживает произвольный доступ.общественный летучий ThreadQueue readyQueue; // Поточно небезопасная очередь готовых потоков. Элементами являются (Thread *).общественный летучий Глобальный Нить* currentThread; // Предположим, что эта переменная для каждого ядра. (Другие общие.)// Реализует спин-блокировку только для синхронизированного состояния самой потоковой системы.// Используется с test-and-set в качестве примитива синхронизации.общественный летучий Глобальный bool threadingSystemBusy = ложный;// Программа обслуживания прерывания переключения контекста (ISR):// На текущем ядре ЦП превентивно переключаемся на другой поток.общественный метод contextSwitchISR() {    если (testAndSet(threadingSystemBusy)) {        возвращаться; // Невозможно переключить контекст прямо сейчас.    }    // Гарантируем, что это прерывание не может повториться, что нарушит переключение контекста:    systemCall_disableInterrupts();    // Получить все регистры текущего процесса.    // Для Program Counter (PC) нам понадобится расположение инструкции    // метка «возобновить» ниже. Получение значений регистров зависит от платформы и может включать    // чтение текущего кадра стека, инструкций JMP / CALL и т. д. (подробности выходят за рамки этой области.)    currentThread->регистры = getAllRegisters(); // Сохраняем регистры объекта "currentThread" в памяти.    currentThread->регистры.ПК = продолжить; // Устанавливаем следующий компьютер на метку «возобновить» ниже в этом методе.    readyQueue.ставить в очередь(currentThread); // Помещаем этот поток обратно в очередь готовности для последующего выполнения.        Нить* otherThread = readyQueue.исключать из очереди(); // Удаляем и запускаем следующий поток из очереди готовности.        currentThread = otherThread; // Заменить значение глобального указателя текущего потока, чтобы оно было готово для следующего потока.    // Восстанавливаем регистры из currentThread / otherThread, включая переход к сохраненному ПК другого потока    // (в «резюме» ниже). Опять же, подробности того, как это делается, выходят за рамки этой области.    восстановитьРегистры(otherThread.регистры);    // *** Теперь выполняется "otherThread" (который теперь является "currentThread")! Исходный поток теперь "спит". ***    продолжить: // Здесь другой вызов contextSwitch () должен установить ПК при переключении контекста обратно сюда.    // Вернуться туда, где остановился otherThread.    threadingSystemBusy = ложный; // Должно быть атомарное присвоение.    systemCall_enableInterrupts(); // Включаем упреждающее переключение снова на этом ядре.}// Метод сна потока:// На текущем ядре ЦП синхронное переключение контекста на другой поток без помещения// текущий поток в очереди готовности.// Должен содержать "threadingSystemBusy" и отключенные прерывания, чтобы этот метод// не прерывается таймером переключения потоков, который вызывает contextSwitchISR ().// После возврата из этого метода необходимо очистить "threadingSystemBusy".общественный метод threadSleep() {    // Получить все регистры текущего процесса.    // Для Program Counter (PC) нам понадобится расположение инструкции    // метка «возобновить» ниже. Получение значений регистров зависит от платформы и может включать    // чтение текущего кадра стека, инструкций JMP / CALL и т. д. (подробности выходят за рамки этой области.)    currentThread->регистры = getAllRegisters(); // Сохраняем регистры объекта "currentThread" в памяти.    currentThread->регистры.ПК = продолжить; // Устанавливаем следующий компьютер на метку «возобновить» ниже в этом методе.    // В отличие от contextSwitchISR (), мы не будем помещать currentThread обратно в readyQueue.    // Вместо этого он уже был помещен в очередь мьютекса или условной переменной.        Нить* otherThread = readyQueue.исключать из очереди(); // Удаляем и запускаем следующий поток из очереди готовности.        currentThread = otherThread; // Заменить значение глобального указателя текущего потока, чтобы оно было готово для следующего потока.    // Восстанавливаем регистры из currentThread / otherThread, включая переход к сохраненному ПК другого потока    // (в «резюме» ниже). Опять же, подробности того, как это делается, выходят за рамки этой области.    восстановитьРегистры(otherThread.регистры);    // *** Теперь выполняется "otherThread" (который теперь является "currentThread")! Исходный поток теперь "спит". ***    продолжить: // Здесь другой вызов contextSwitch () должен установить ПК при переключении контекста обратно сюда.    // Вернуться туда, где остановился otherThread.}общественный метод ждать(Мьютекс м, ConditionVariable c) {    // Внутренняя блокировка вращения, в то время как другие потоки на любом ядре обращаются к этому объекту    // "удерживается" и "threadQueue" или "readyQueue".    пока (testAndSet(threadingSystemBusy)) {}    // Примечание: теперь "threadingSystemBusy" истинно.        // Системный вызов для отключения прерываний на этом ядре, чтобы threadSleep () не прерывался    // таймер переключения потоков на этом ядре, который будет вызывать contextSwitchISR ().    // Выполняется вне threadSleep () для большей эффективности, чтобы этот поток был в спящем режиме    // сразу после перехода в очередь условных переменных.    systemCall_disableInterrupts();     утверждать м.держал; // (В частности, этот поток должен быть тем, кто его держит.)        м.релиз();    c.waitThreads.ставить в очередь(currentThread);        threadSleep();        // Поток засыпает ... Поток просыпается от сигнала / трансляции.        threadingSystemBusy = ложный; // Должно быть атомарное присвоение.    systemCall_enableInterrupts(); // Включаем упреждающее переключение снова на этом ядре.        // Стиль Mesa:    // Здесь могут происходить переключения контекста, в результате чего предикат вызывающего клиента становится ложным.        м.приобретать();}общественный метод сигнал(ConditionVariable c) {    // Внутренняя блокировка вращения, в то время как другие потоки на любом ядре обращаются к этому объекту    // "удерживается" и "threadQueue" или "readyQueue".    пока (testAndSet(threadingSystemBusy)) {}    // Примечание: теперь "threadingSystemBusy" истинно.        // Системный вызов для отключения прерываний на этом ядре, чтобы threadSleep () не прерывался    // таймер переключения потоков на этом ядре, который будет вызывать contextSwitchISR ().    // Выполняется вне threadSleep () для большей эффективности, чтобы этот поток был в спящем режиме    // сразу после перехода в очередь условных переменных.    systemCall_disableInterrupts();        если (!c.waitThreads.пусто()) {        wokenThread = c.waitThreads.исключать из очереди();        readyQueue.ставить в очередь(wokenThread);    }        threadingSystemBusy = ложный; // Должно быть атомарное присвоение.    systemCall_enableInterrupts(); // Включаем упреждающее переключение снова на этом ядре.        // Стиль Mesa:    // Пробужденному потоку не дается никакого приоритета.}общественный метод транслировать(ConditionVariable c) {    // Внутренняя блокировка вращения, в то время как другие потоки на любом ядре обращаются к этому объекту    // "удерживается" и "threadQueue" или "readyQueue".    пока (testAndSet(threadingSystemBusy)) {}    // Примечание: теперь "threadingSystemBusy" истинно.        // Системный вызов для отключения прерываний на этом ядре, чтобы threadSleep () не прерывался    // таймер переключения потоков на этом ядре, который будет вызывать contextSwitchISR ().    // Выполняется вне threadSleep () для большей эффективности, чтобы этот поток был спящим    // сразу после перехода в очередь условных переменных.    systemCall_disableInterrupts();        пока (!c.waitThreads.пусто()) {        wokenThread = c.waitThreads.исключать из очереди();        readyQueue.ставить в очередь(wokenThread);    }        threadingSystemBusy = ложный; // Должно быть атомарное присвоение.    systemCall_enableInterrupts(); // Включаем упреждающее переключение снова на этом ядре.        // Стиль Mesa:    // Пробужденным потокам не дается никакого приоритета.}учебный класс Мьютекс {    защищенный летучий bool держал = ложный;    частный летучий ThreadQueue blockingThreads; // Небезопасная очередь заблокированных потоков. Элементами являются (Thread *).        общественный метод приобретать() {        // Внутренняя блокировка вращения, в то время как другие потоки на любом ядре обращаются к этому объекту        // "удерживается" и "threadQueue" или "readyQueue".        пока (testAndSet(threadingSystemBusy)) {}        // Примечание: теперь "threadingSystemBusy" истинно.                // Системный вызов для отключения прерываний на этом ядре, чтобы threadSleep () не прерывался        // таймер переключения потоков на этом ядре, который будет вызывать contextSwitchISR ().        // Выполняется вне threadSleep () для большей эффективности, чтобы этот поток был в спящем режиме        // сразу после постановки в очередь блокировок.        systemCall_disableInterrupts();        утверждать !blockingThreads.содержит(currentThread);        если (держал) {            // Помещаем "currentThread" в очередь этой блокировки, чтобы он был            // считается "спящим" на этой блокировке.            // Обратите внимание, что "currentThread" по-прежнему должен обрабатываться threadSleep ().            readyQueue.удалять(currentThread);            blockingThreads.ставить в очередь(currentThread);            threadSleep();                        // Теперь мы проснулись, что должно быть потому, что "hold" стало ложным.            утверждать !держал;            утверждать !blockingThreads.содержит(currentThread);        }                держал = истинный;                threadingSystemBusy = ложный; // Должно быть атомарное присвоение.        systemCall_enableInterrupts(); // Включаем упреждающее переключение снова на этом ядре.    }                    общественный метод релиз() {        // Внутренняя блокировка вращения, в то время как другие потоки на любом ядре обращаются к этому объекту        // "удерживается" и "threadQueue" или "readyQueue".        пока (testAndSet(threadingSystemBusy)) {}        // Примечание: теперь "threadingSystemBusy" истинно.                // Системный вызов для отключения прерываний на этом ядре для повышения эффективности.        systemCall_disableInterrupts();                утверждать держал; // (Освобождение должно выполняться только при удержании блокировки.)        держал = ложный;                если (!blockingThreads.пусто()) {            Нить* unblockedThread = blockingThreads.исключать из очереди();            readyQueue.ставить в очередь(unblockedThread);        }                threadingSystemBusy = ложный; // Должно быть атомарное присвоение.        systemCall_enableInterrupts(); // Включаем упреждающее переключение снова на этом ядре.    }}структура ConditionVariable {    летучий ThreadQueue waitThreads;}

Семафор

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

класс монитора Семафор{    частный int s: = 0 инвариантный s> = 0 частный Условие sIsPositive /* связана с s> 0 * /    публичный метод П()    { пока s = 0: ждать sIsPositive утверждать s> 0 s: = s - 1} публичный метод V () {s: = s + 1 утверждать s> 0 сигнал sIsPositive}}

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

учебный класс Семафор{    частный летучий int s: = 0 инвариантный s> = 0 частный ConditionVariable sIsPositive /* связана с s> 0 * /    частный Мьютекс myLock / * Заблокировать "s" * /    публичный метод P () {myLock.acquire () пока s = 0: ждать(myLock, sIsPositive) утверждать s> 0 s: = s - 1 myLock.release ()} публичный метод V () {myLock.acquire () s: = s + 1 утверждать s> 0 сигнал sIsPositive myLock.release ()}}

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

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

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

общественный метод ждать(Мьютекс м, ConditionVariable c) {    утверждать м.держал;    c.internalMutex.приобретать();        c.numWaiters++;    м.релиз(); // Может идти до / после соседних строк.    c.internalMutex.релиз();    // Другой поток может сигнализировать здесь, но это нормально, потому что    // количество семафоров. Если число c.sem станет 1, у нас не будет    // время ожидания.    c.сем.Proberen(); // Заблокировать по резюме.    // Проснулся    м.приобретать(); // Заново получить мьютекс.}общественный метод сигнал(ConditionVariable c) {    c.internalMutex.приобретать();    если (c.numWaiters > 0) {        c.numWaiters--;        c.сем.Verhogen(); // (Не требует защиты c.internalMutex.)    }    c.internalMutex.релиз();}общественный метод транслировать(ConditionVariable c) {    c.internalMutex.приобретать();    пока (c.numWaiters > 0) {        c.numWaiters--;        c.сем.Verhogen(); // (Не требует защиты c.internalMutex.)    }    c.internalMutex.релиз();}учебный класс Мьютекс {    защищенный логический держал = ложный; // Только для утверждений, чтобы гарантировать, что число sem никогда не превышает 1.    защищенный Семафор сем = Семафор(1); // Число всегда должно быть не больше 1.                                          // Не удерживается <--> 1; удерживается <--> 0.    общественный метод приобретать() {        сем.Proberen();        утверждать !держал;        держал = истинный;    }        общественный метод релиз() {        утверждать держал; // Убедитесь, что мы никогда не будем Verhogen sem выше 1. Это было бы плохо.        держал = ложный;        сем.Verhogen();    }}учебный класс ConditionVariable {    защищенный int numWaiters = 0; // Примерно отслеживает количество официантов, заблокированных в sem.                                // (Внутреннее состояние семафора обязательно частное.)    защищенный Семафор сем = Семафор(0); // Предоставляет очередь ожидания.    защищенный Мьютекс internalMutex; // (На самом деле еще один семафор. Защищает "numWaiters".)}

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

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

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

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

Монитор в стиле Хоара с двумя переменными состояния а и б. После Бура и другие.

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

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

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

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

Все очереди обычно гарантированно справедливый и в некоторых реализациях может быть гарантировано первым пришел-первым вышел.

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

введите монитор: введите метод если монитор заблокирован, добавьте эту тему, чтобы заблокировать эту тему еще        заблокировать монитор оставить монитор: расписание возвращаться из методаждать c: добавить эту тему в c.q расписание заблокировать этот потоксигнал c:    если есть поток, ожидающий c.q выбрать и удалить один такой поток t из c.q (t называется "сигнальным потоком") добавить этот поток в s restart t (чтобы t занял монитор следующим) заблокировать это расписание потоков: если есть поток на s, выберите и удалите один поток из s и перезапустите его (этот поток будет занимать монитор следующим) иначе если есть поток на e, выберите и удалите один поток из e и перезапустите его (этот поток будет занимать монитор следующим) еще        разблокировать монитор (монитор не будет занят)

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

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

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

сигнал c и вернуться:    если есть поток, ожидающий c.q выбрать и удалить один такой поток t из c.q (t называется "сигнальным потоком") перезапустить t (так что t займёт монитор следующим) еще        график возвращаться из метода

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

войдите в монитор: постусловие яоставьте монитор: предварительное условие яждать c:    предварительное условие я    изменяет состояние монитора постусловие пc и ясигнал c:    предварительное условие пc и я    изменяет состояние монитора постусловие ясигнал c и вернуться:    предварительное условие пc и я

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

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

ждать c:    предварительное условие я    изменяет состояние монитора постусловие пcсигнал c    предварительное условие (нет пустой(c) и пc) или же (пустой(c) и я)    изменяет состояние монитора постусловие я

См Ховарда[4] и Бур и другие.,[5] для большего).

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

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

класс монитора SharedStack {    частная константа вместимость: = 10 частный int[вместимость] A частный int размер: = 0 инвариантный 0 <= размер и размер <= емкость частный BlockingCondition theStackIsNotEmpty /* связана с 0 <размер и размер <= вместимость * /    частный BlockingCondition theStackIsNotFull /* связана с 0 <= размер и размер <вместимость * /    публичный метод толкать(int ценить)    { если размер = емкость тогда ждать theStackIsNotFull утверждать 0 <= размер и размер <емкость A [размер]: = значение; размер: = размер + 1 утверждать 0 <размер и размер <= емкость сигнал theStackIsNotEmpty и вернуться    }    публичный метод int pop () { если size = 0 тогда ждать theStackIsNotEmpty утверждать 0 <размер и size <= емкость size: = size - 1; утверждать 0 <= размер и размер <емкость сигнал theStackIsNotFull и вернуться A [размер]}}

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

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

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

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

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

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

введите монитор: введите метод если монитор заблокирован, добавьте эту тему, чтобы заблокировать эту тему еще        заблокировать монитор оставить монитор: расписание возвращаться из методаждать c: добавить эту тему в c.q расписание заблокировать этот потокуведомлять c: если есть поток, ожидающий c.q выбрать и удалить один поток t из c.q (t называется "поток уведомлений") переместить t в eуведомить всех c: переместить все ожидающие потоки c.q исключить из расписания: если есть поток на e, выберите и удалите один поток из e и перезапустите его еще        разблокировать монитор

Как вариант этой схемы, уведомленный поток может быть перемещен в очередь с именем ш, который имеет приоритет перед е. См Ховарда[4] и Бур и другие.[5] для дальнейшего обсуждения.

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

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

пока нет( п ) делать    ждать c

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

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

класс монитора Счет {    частный int баланс: = 0 инвариантный баланс> = 0 частный Неблокирующее условие balanceMayBeBigEnough публичный метод снять со счета(int количество) предварительное условие amount> = 0 { пока баланс <сумма делать ждать balanceMayBeBigEnough утверждать баланс> = сумма баланс: = баланс - сумма} публичный метод депозит (int количество) предварительное условие сумма> = 0 {баланс: = баланс + сумма уведомить всех balanceMayBeBigEnough}}

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

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

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

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

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

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

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

ждать п:    предварительное условие я    изменяет состояние монитора постусловие п и я

История

Бринч Хансен и Хоар разработали концепцию монитора в начале 1970-х, основываясь на собственных и более ранних идеях. Эдсгер Дейкстра.[6] Бринч Хансен опубликовал первое обозначение монитора, приняв учебный класс идея Симула 67,[1] и изобрел механизм очередей.[7] Хоар уточнил правила возобновления процесса.[2] Бринч Хансен создал первую реализацию мониторов в Параллельный Паскаль.[6] Хоар продемонстрировал их эквивалентность семафоры.

Мониторы (и Concurrent Pascal) вскоре стали использоваться для структурирования синхронизации процессов в Сольная операционная система.[8][9]

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

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

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

Примечания

  1. ^ а б Бринч Хансен, Пер (1973). «7.2 Концепция класса» (PDF). Принципы операционной системы. Прентис Холл. ISBN  978-0-13-637843-3.
  2. ^ а б Хоар, К.А.Р. (Октябрь 1974 г.). «Мониторы: концепция структурирования операционной системы». Comm. ACM. 17 (10): 549–557. CiteSeerX  10.1.1.24.6394. Дои:10.1145/355620.361161. S2CID  1005769.
  3. ^ Хансен, П. Б. (Июнь 1975 г.). «Язык программирования Concurrent Pascal» (PDF). IEEE Trans. Софтв. Англ. SE-1 (2): 199–207. Дои:10.1109 / TSE.1975.6312840. S2CID  2000388.
  4. ^ а б Ховард, Джон Х. (1976). «Сигнализация в мониторах». ICSE '76 Труды 2-й международной конференции по программной инженерии. Международная конференция по программной инженерии. Лос-Аламитос, Калифорния, США: Издательство компьютерного общества IEEE. С. 47–52.
  5. ^ а б Бур, Питер А .; Фортье, Мишель; Гроб, Майкл Х. (март 1995 г.). «Классификация мониторов». Опросы ACM Computing. 27 (1): 63–107. Дои:10.1145/214037.214100. S2CID  207193134.
  6. ^ а б Хансен, Пер Бринч (1993). «Мониторы и параллельный Паскаль: личная история». HOPL-II: Вторая конференция ACM SIGPLAN по истории языков программирования. История языков программирования. Нью-Йорк, Нью-Йорк, США: ACM. С. 1–35. Дои:10.1145/155360.155361. ISBN  0-89791-570-4.
  7. ^ Бринч Хансен, Пер (июль 1972 г.). «Структурированное мультипрограммирование (Приглашенный доклад)». Коммуникации ACM. 15 (7): 574–578. Дои:10.1145/361454.361473. S2CID  14125530.
  8. ^ Бринч Хансен, Пер (апрель 1976 г.). «Операционная система Solo: параллельная программа на языке Pascal» (PDF). Программное обеспечение - практика и опыт.
  9. ^ Бринч Хансен, Пер (1977). Архитектура параллельных программ. Прентис Холл. ISBN  978-0-13-044628-2.

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

  • Мониторы: концепция структурирования операционной системы, К. А. Р. Хоар - Коммуникации ACM, т.17, п.10, с. 549–557, октябрь 1974 г. [1]
  • Классификация монитора П.А. Бур, М. Фортье, М. Гроб - Опросы ACM Computing, 1995 [2]

внешняя ссылка