Из Википедии, бесплатной энциклопедии
  (Перенаправлено из переменной Condition )
Перейти к навигации Перейти к поиску

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

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

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

Взаимное исключение [ править ]

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

класс монитора  Account { private  int balance: = 0 неизменный баланс> = 0 публичный метод  логический вывод ( int amount) precondition amount> = 0 { if balance <amount { return false } else { баланс: = баланс - сумма вернуть истину } } депозит публичного метода ( int amount) precondition amount> = 0 { баланс: = баланс + сумма }}

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

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

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

class  Account { private  lock myLock private  int balance: = 0 инвариантный баланс> = 0 публичный метод  логический вывод ( int amount) precondition amount> = 0 { myLock.acquire () попробуйте { if balance <amount { return false } else { баланс: = баланс - сумма вернуть истину } } finally { myLock.release () } } депозит публичного метода ( int amount) precondition amount> = 0 { myLock.acquire () попробуйте { баланс: = баланс + сумма } finally { myLock.release () } }}

Переменные условия [ править ]

Формулировка проблемы [ править ]

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

в то время как  не ( P ) действительно  пропустить

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

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

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

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

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

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

глобальная  очередь RingBuffer  ; // Небезопасный для потоков кольцевой буфер задач. // Метод , представляющий поведение каждого производителя потока: публичный  метод  производителя ()  { в  то время  ( правда )  {  задача  myTask  =  ...;  // Продюсер добавляет новую задачу.  while  ( queue . isFull ())  {}  // Занят - ждем, пока очередь не  заполнится . очередь . enqueue ( myTask );  // Добавляем задачу в очередь.  } }// Метод, представляющий поведение каждого потребительского потока: public  method  consumer ()  {  while  ( true )  {  while  ( queue . IsEmpty ())  {}  // Ожидание занятости, пока очередь не станет пустой.  myTask  =  очередь . dequeue ();  // Снимаем задачу из очереди.  doStuff ( myTask );  // Уходим и делаем что-нибудь с задачей.  } }

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

Ожидание вращения [ править ]

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

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

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

(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 не требуют ожидания определенного условия для параллельных данных.

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

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

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

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

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

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

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

глобальная  энергозависимая  очередь RingBuffer  ; // Небезопасный для потоков кольцевой буфер задач. global Lock queueLock ; // Мьютекс для кольцевого буфера задач. (Не спин-блокировка.) Global CV queueEmptyCV ; // Переменная условия для потребительских потоков, ожидающих, пока // очередь не станет пустой. // Связанная с ним блокировка - "queueLock". глобальный CV queueFullCV ; // Переменная условия для потоков-производителей, ожидающих // заполнения очереди . Связанная с ним блокировка также называется queueLock.           // Метод , представляющий поведение каждого производителя потока: публичный  метод  производителя ()  { в  то время  ( правда )  {  задача  myTask  =  ...;  // Продюсер добавляет новую задачу. queueLock . получить ();  // Получение блокировки для начальной проверки предиката.  while  ( queue . isFull ())  {  // Проверяем, не заполнена ли очередь.  // Заставить систему потоковой передачи атомарно освободить queueLock,  // поставить этот поток в очередь на queueFullCV и засыпать этот поток.  ждать ( queueLock ,  queueFullCV );  // Затем "wait" автоматически повторно получает "queueLock" для повторной  //  проверки условия предиката. }  // Критический раздел, требующий неполного заполнения очереди.  // NB: у нас есть queueLock.  очередь . enqueue ( myTask );  // Добавляем задачу в очередь. // Теперь очередь гарантированно непуста, поэтому сигнализируем потоку-потребителю  // или всем потокам-потребителям, которые могут быть заблокированы в ожидании непустой очереди:  signal ( queueEmptyCV );  -  ИЛИ  -  notifyAll ( queueEmptyCV );  // Конец критических секций, относящихся к очереди.  queueLock . release ();  // Снимаем блокировку очереди, пока она нам снова не понадобится для добавления следующей задачи.  } }// Метод, представляющий поведение каждого потребительского потока: открытый  метод  consumer ()  {  while  ( true )  {  queueLock . получить ();  // Получение блокировки для начальной проверки предиката.  while  ( queue . isEmpty ())  {  // Проверяем, не пуста ли очередь.  // Заставляем систему потоков атомарно освободить queueLock,  // поставить этот поток в очередь в queueEmptyCV и засыпать этот поток.  ждать ( queueLock ,  queueEmptyCV ); // Затем "wait" автоматически повторно получает "queueLock" для повторной  //  проверки условия предиката. }  // Критический раздел, требующий, чтобы очередь была непустой.  // NB: у нас есть queueLock.  myTask  =  очередь . dequeue ();  // Снимаем задачу из очереди.  // Теперь очередь гарантированно не заполнена, поэтому сигнализируйте потоку производителя  // или всем потокам производителя, которые могут быть заблокированы в ожидании  неполного заполнения очереди: signal ( queueFullCV );  -  ИЛИ  -  notifyAll ( queueFullCV ); // Конец критических секций, относящихся к очереди.  queueLock . release ();  // Снимаем блокировку очереди, пока она нам снова не понадобится для выполнения следующей задачи. doStuff ( myTask );  // Уходим и делаем что-нибудь с задачей.  } }

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

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

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

глобальная  энергозависимая  очередь RingBuffer  ; // Небезопасный для потоков кольцевой буфер задач. global Lock queueLock ; // Мьютекс для кольцевого буфера задач. (Не спин-блокировка.) Global CV queueFullOrEmptyCV ; // Единая переменная условия для случаев, когда очередь не готова для какого-либо потока // - т.е. для потоков-производителей, ожидающих, пока очередь не заполнится, // и потоков-потребителей, ожидающих, пока очередь не станет непустой. // Связанная с ним блокировка - "queueLock". // Небезопасно использовать обычный «сигнал», потому что он связан с // несколькими условиями предиката (утверждениями).            // Метод , представляющий поведение каждого производителя потока: публичный  метод  производителя ()  { в  то время  ( правда )  {  задача  myTask  =  ...;  // Продюсер добавляет новую задачу. queueLock . получить ();  // Получение блокировки для начальной проверки предиката.  while  ( queue . isFull ())  {  // Проверяем, не заполнена ли очередь.  // Заставить систему потоковой передачи атомарно освободить queueLock,  // поставить этот поток в очередь на CV и приостановить этот поток.  ждать ( queueLock ,  queueFullOrEmptyCV );  // Затем "wait" автоматически повторно получает "queueLock" для повторной  //  проверки условия предиката. }  // Критический раздел, требующий неполного заполнения очереди.  // NB: у нас есть queueLock.  очередь . enqueue ( myTask );  // Добавляем задачу в очередь. // Теперь очередь гарантированно  непуста , поэтому сигнализируйте обо всех заблокированных потоках // чтобы поток-потребитель принял задачу:  notifyAll ( queueFullOrEmptyCV );  // Не используйте "сигнал" (вместо этого он может разбудить другого производителя).  // Конец критических секций, относящихся к очереди.  queueLock . release ();  // Снимаем блокировку очереди, пока она нам снова не понадобится для добавления следующей задачи.  } }// Метод, представляющий поведение каждого потребительского потока: открытый  метод  consumer ()  {  while  ( true )  {  queueLock . получить ();  // Получение блокировки для начальной проверки предиката.  while  ( queue . isEmpty ())  {  // Проверяем, не пуста ли очередь.  // Заставить систему потоковой передачи атомарно освободить queueLock,  // поставить этот поток в очередь на CV и приостановить этот поток.  ждать ( queueLock ,  queueFullOrEmptyCV ); // Затем "wait" автоматически повторно получает "queueLock" для повторной  //  проверки условия предиката. }  // Критический раздел, требующий неполного заполнения очереди.  // NB: у нас есть queueLock.  myTask  =  очередь . dequeue ();  // Снимаем задачу из очереди. // Теперь очередь гарантированно не заполнена, поэтому сигнализируйте обо всех заблокированных потоках  // чтобы поток-производитель принял задачу:  notifyAll ( queueFullOrEmptyCV );  // Не используйте «сигнал» (вместо этого он может разбудить другого потребителя). // Конец критических секций, относящихся к очереди.  queueLock . release ();  // Снимаем блокировку очереди, пока она нам снова не понадобится для выполнения следующей задачи. doStuff ( myTask );  // Уходим и делаем что-нибудь с задачей.  } }

Примитивы синхронизации [ править ]

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

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

// Основные части системы потоковой передачи: // Предположим, что ThreadQueue поддерживает произвольный доступ. общедоступный  изменчивый  ThreadQueue  readyQueue ;  // Потоково-небезопасная очередь готовых потоков. Элементами являются (Thread *). публичный  изменчивый  глобальный  поток *  currentThread ;  // Предположим, что эта переменная рассчитана на ядро. (Остальные - общие.)// Реализует спин-блокировку только для синхронизированного состояния самой потоковой системы. // Используется с test-and-set в качестве примитива синхронизации. public  volatile  global  bool  threadingSystemBusy  =  false ;// Подпрограмма обслуживания прерывания переключения контекста (ISR): // На текущем ядре ЦП превентивно переключиться на другой поток. открытый  метод  contextSwitchISR ()  {  если  ( testAndSet ( threadingSystemBusy ))  {  возврат ;  // Невозможно переключить контекст прямо сейчас.  } // Убедитесь, что это прерывание не может повториться снова, что приведет к нарушению переключения контекста:  systemCall_disableInterrupts (); // Получить все регистры текущего процесса.  // Для программного счетчика (ПК) нам понадобится расположение инструкции  // метки «возобновить» ниже. Получение значений регистров зависит от платформы и может включать  // чтение текущего кадра стека, инструкций JMP / CALL и т. Д. (Подробности выходят за рамки этой области.)  CurrentThread -> registers  =  getAllRegisters ();  // Сохраняем регистры объекта "currentThread" в памяти.  currentThread -> регистры . ПК  =  возобновить ;  // Устанавливаем следующий компьютер на метку «возобновить» ниже в этом методе. readyQueue . enqueue ( currentThread );  // Помещаем этот поток обратно в очередь готовности для последующего выполнения.  Тема *  otherThread  =  readyQueue . dequeue ();  // Удаляем и запускаем следующий поток из очереди готовности.  currentThread  =  otherThread ;  // Заменим значение глобального указателя текущего потока, чтобы оно было готово для следующего потока. // Восстанавливаем регистры из currentThread / otherThread, включая переход к сохраненному ПК другого потока  // (в «возобновлении» ниже). Опять же, подробности того, как это делается, выходят за рамки этой области.  restoreRegisters ( otherThread . регистры ); // *** Теперь выполняется "otherThread" (который теперь является "currentThread")! Исходный поток теперь "спит". *** возобновить :  // Здесь другой вызов contextSwitch () должен установить ПК при переключении контекста обратно сюда. // Вернуться туда, где остановился otherThread. threadingSystemBusy  =  false ;  // Должно быть атомарное присвоение.  systemCall_enableInterrupts ();  // Включаем упреждающее переключение снова на этом ядре. }// Метод ожидания потока : // На текущем ядре ЦП синхронное переключение контекста на другой поток без помещения // текущего потока в очередь готовности. // Должен содержать "threadingSystemBusy" и отключенные прерывания, чтобы // этот метод не прерывался таймером переключения потоков, который вызвал бы contextSwitchISR (). // После возврата из этого метода необходимо очистить "threadingSystemBusy". public  method  threadSleep ()  {  // Получить все регистры текущего процесса.  // Для программного счетчика (ПК) нам понадобится расположение инструкции  // метки «возобновить» ниже. Получение значений регистров зависит от платформы и может включать // чтение текущего кадра стека, инструкций JMP / CALL и т. д. (подробности выходят за рамки этой области.)  currentThread -> registers  =  getAllRegisters ();  // Сохраняем регистры объекта "currentThread" в памяти.  currentThread -> регистры . ПК  =  возобновить ;  // Устанавливаем следующий компьютер на метку «возобновить» ниже в этом методе. // В отличие от contextSwitchISR (), мы не будем помещать currentThread обратно в readyQueue.  // Вместо этого он уже был помещен в очередь мьютекса или условной переменной.  Тема *  otherThread  =  readyQueue . dequeue ();  // Удаляем и запускаем следующий поток из очереди готовности.  currentThread  =  otherThread ;  // Заменим значение глобального указателя текущего потока, чтобы оно было готово для следующего потока. // Восстанавливаем регистры из currentThread / otherThread, включая переход к сохраненному ПК другого потока  // (в «возобновлении» ниже). Опять же, подробности того, как это делается, выходят за рамки этой области.  restoreRegisters ( otherThread . регистры ); // *** Теперь выполняется "otherThread" (который теперь является "currentThread")! Исходный поток теперь "спит". *** возобновить :  // Здесь другой вызов contextSwitch () должен установить ПК при переключении контекста обратно сюда. // Вернуться туда, где остановился otherThread. }public  method  wait ( Mutex  m ,  ConditionVariable  c )  {  // Внутренняя блокировка вращения, в то время как другие потоки на любом ядре обращаются к  // "удерживаемым" и "threadQueue"  этого объекта , или "readyQueue". while  ( testAndSet ( threadingSystemBusy ))  {}  // NB: "threadingSystemBusy" теперь истинно.  // Системный вызов для отключения прерываний на этом ядре, чтобы threadSleep () не прерывался  // таймером переключения потоков на этом ядре, который вызвал бы contextSwitchISR ().  // Выполняется вне threadSleep () для большей эффективности, чтобы этот поток  //  переходил в спящий режим сразу после перехода в очередь условных переменных. systemCall_disableInterrupts ();  утверждать  м . проведен ;  // (В частности, этот поток должен быть тем, кто его держит.)  м . release ();  c . waitThreads . enqueue ( currentThread );  threadSleep ();  // Поток засыпает ... Поток просыпается от сигнала / трансляции.  threadingSystemBusy  =  false ;  // Должно быть атомарное присвоение.  systemCall_enableInterrupts ();  // Включаем упреждающее переключение снова на этом ядре.  // Стиль Mesa:  // Здесь могут происходить переключения контекста, в результате чего предикат вызывающего клиента становится ложным.  м . получить (); } сигнал общедоступного метода  ( ConditionVariable c ) { // Внутренняя блокировка вращения, в то время как другие потоки на любом ядре обращаются к // этому объекту "hold" и "threadQueue" или "readyQueue". while ( testAndSet ( threadingSystemBusy )) {} // NB: "threadingSystemBusy" теперь истинно.          // Системный вызов для отключения прерываний на этом ядре, чтобы threadSleep () не прерывался  // таймером переключения потоков на этом ядре, который вызвал бы contextSwitchISR ().  // Выполняется вне threadSleep () для большей эффективности, чтобы этот поток  //  переходил в спящий режим сразу после перехода в очередь условных переменных. systemCall_disableInterrupts ();  если  ( ! c . waitThreads . isEmpty ())  {  wokenThread  =  c . waitThreads . dequeue ();  readyQueue . enqueue ( wokenThread );  }  threadingSystemBusy  =  false ;  // Должно быть атомарное присвоение.  systemCall_enableInterrupts ();  // Включаем упреждающее переключение снова на этом ядре.  // Стиль Mesa:  // Пробужденному потоку не дается никакого приоритета. }публичный  метод  трансляции ( ConditionVariable  c )  {  // Внутренняя блокировка вращения, в то время как другие потоки на любом ядре обращаются к  //  этому объекту "hold" и "threadQueue" или "readyQueue". while  ( testAndSet ( threadingSystemBusy ))  {}  // NB: "threadingSystemBusy" теперь истинно.  // Системный вызов для отключения прерываний на этом ядре, чтобы threadSleep () не прерывался  // таймером переключения потоков на этом ядре, который вызвал бы contextSwitchISR ().  // Выполняется вне threadSleep () для большей эффективности, чтобы этот поток  //  переходил в спящий режим сразу после перехода в очередь условных переменных. systemCall_disableInterrupts ();  в то время как  ( ! c . waitThreads . isEmpty ())  {  wokenThread  =  c . waitThreads . dequeue ();  readyQueue . enqueue ( wokenThread );  }  threadingSystemBusy  =  false ;  // Должно быть атомарное присвоение.  systemCall_enableInterrupts ();  // Включаем упреждающее переключение снова на этом ядре.  // Стиль Mesa:  // Пробужденным потокам не дается никакого приоритета. }class  Mutex  {  защищенный  изменчивый  логический  тип удерживается  =  false ;  частный  изменчивый  ThreadQueue  blockingThreads ;  // Небезопасная очередь заблокированных потоков. Элементами являются (Thread *).  public  method  acqu ()  {  // Внутренняя блокировка вращения, в то время как другие потоки на любом ядре обращаются к  //  этому объекту "удерживается" и "threadQueue" или "readyQueue". while  ( testAndSet ( threadingSystemBusy ))  {}  // NB: "threadingSystemBusy" теперь истинно.  // Системный вызов для отключения прерываний на этом ядре, чтобы threadSleep () не прерывался  // таймером переключения потоков на этом ядре, который вызвал бы contextSwitchISR ().  // Выполняется вне threadSleep () для большей эффективности, чтобы этот поток  //  переходил в спящий режим сразу после перехода в очередь блокировок. systemCall_disableInterrupts (); утверждать  ! blockingThreads . содержит ( currentThread ); if  ( hold )  {  // Поместите "currentThread" в очередь этой блокировки, чтобы он  // считался "спящим" на этой блокировке.  // Обратите внимание, что "currentThread" по-прежнему должен обрабатываться threadSleep ().  readyQueue . удалить ( currentThread );  blockingThreads . enqueue ( currentThread );  threadSleep ();  // Теперь мы проснулись, что должно быть потому, что "hold" стало ложным.  утверждать  ! проведен ;  утверждать  ! blockingThreads . содержит ( currentThread );  }  держится  =  правда ;  threadingSystemBusy  =  false ;  // Должно быть атомарное присвоение.  systemCall_enableInterrupts ();  // Включаем упреждающее переключение снова на этом ядре.  }   public  method  release ()  {  // Внутренняя блокировка вращения, в то время как другие потоки на любом ядре обращаются к  // "удерживаемой" и "threadQueue"  этого объекта или "readyQueue". while  ( testAndSet ( threadingSystemBusy ))  {}  // NB: "threadingSystemBusy" теперь истинно.  // Системный вызов для отключения прерываний на этом ядре для повышения эффективности.  systemCall_disableInterrupts ();  утверждать  состоявшееся ;  // (Освобождение должно выполняться только при удержании блокировки.) удерживается  =  ложь ;  if  ( ! blockingThreads . isEmpty ())  {  Thread *  unblockedThread  =  blockingThreads . dequeue ();  readyQueue . Enqueue ( unblockedThread );  }  threadingSystemBusy  =  false ;  // Должно быть атомарное присвоение.  systemCall_enableInterrupts ();  // Включаем упреждающее переключение снова на этом ядре.  } }struct  ConditionVariable  {  изменчивый  ThreadQueue  waitThreads ; }

Семафор [ править ]

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

класс монитора  Semaphore{ private  int s: = 0 инвариант s> = 0 private  Condition sIsPositive / * связанный с s> 0 * / общедоступный метод P () { в то время как s = 0: подождите sIsPositive assert s> 0 s: = s - 1 } общедоступный метод V () { s: = s + 1 assert s> 0 signal sIsPositive }}

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

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

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

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

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

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

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

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

Переменные условия блокировки [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

wait  c : предварительное условие  I  изменяет состояние постусловия монитора P cПредварительное  условие сигнала c ( not empty ( c ) и P c ) или (empty ( c ) и I ) изменяет состояние постусловия монитора I.

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

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

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

класс монитора  SharedStack { private const capacity: = 10 private  int [capacity] a private  int size: = 0 инвариант 0 <= размер и размер <= емкость частный  BlockingCondition theStackIsNotEmpty / * связанный с 0 <размер и размер <= емкость * /  частный  BlockingCondition theStackIsNotFull / * связано с 0 <= size и size <capacity * / общедоступный метод push ( значение int ) { если размер = емкость затем  ждать theStackIsNotFull утверждают , 0 <= размер и размер <емкость A [размер]: = значение; размер: = размер + 1 assert 0 <size and size <= capacity signal theStackIsNotEmpty и return } публичный метод  int pop () { если size = 0, то  подождите, пока StackIsNotEmpty подтвердит 0 <размер и размер <= емкость размер: = размер - 1; assert 0 <= size и size <capacity signal theStackIsNotFull и вернуть A [размер] }}

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

Неблокирующие переменные условия [ править ]

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

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

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

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

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

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

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

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

в то время как  не ( P ) делать  ожидание гр

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

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

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

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

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

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

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

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

Неявная сигнализация [ править ]

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

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

История [ править ]

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

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

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

  • Ада начиная с Ады 95 (как защищенные объекты)
  • C # (и другие языки, использующие .NET Framework )
  • Параллельный Евклид
  • Параллельный Паскаль
  • D
  • Delphi (Delphi 2009 и выше, через TObject.Monitor)
  • Java (через методы ожидания и уведомления)
  • Идти
  • Меса
  • Модула-3
  • Python (через объект threading.Condition )
  • Рубин
  • Писк Smalltalk
  • Тьюринг , Тьюринг + и объектно-ориентированный Тьюринг
  • µC ++
  • Визуальный пролог

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

См. Также [ править ]

  • Взаимное исключение
  • Связь последовательных процессов - более поздняя разработка мониторов CAR Hoare
  • Семафор (программирование)

Заметки [ править ]

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

Дальнейшее чтение [ править ]

  • Мониторы: концепция структурирования операционной системы, 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]

Внешние ссылки [ править ]

  • Мониторы Java (ясное объяснение)
  • " Мониторы: концепция структурирования операционной системы ", CAR Hoare
  • « Сигнализация в мониторах » Джона Х. Ховарда (ученый-компьютерщик)
  • « Проверка мониторов » Джона Х. Ховарда (ученого-информатика)
  • Батлер В. Лэмпсон и Дэвид Д. Ределл " Опыт работы с процессами и мониторами в Мезе "
  • pthread_cond_wait - описание из выпуска 6 базовых спецификаций Open Group, IEEE Std 1003.1
  • « Блокировка переменной состояния » Дэйва Маршалла (ученый-компьютерщик)
  • « Стратегии реализации переменных условий POSIX в Win32 » Дугласа К. Шмидта и Ирфана Пьярали
  • Подпрограммы переменных условий из переносимой библиотеки времени выполнения Apache
  • wxCondition description
  • Справочник по переменным условий повышения
  • Описание класса условия ZThread
  • Wefts :: Описание класса Condition
  • Справочник по шаблону класса ACE_Condition
  • Описание класса QWaitCondition
  • Общая справка по условным классам C ++
  • at :: Описание класса ConditionalMutex
  • thread :: shared - расширение Perl для разделения структур данных между потоками
  • http://msdn.microsoft.com/en-us/library/ms682052(VS.85).aspx
  • Мониторы в Visual Prolog .