Tkkastur.ru

Авто Бан
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

C часть 3: синхронизация потоков в ресторане

[C++] часть 3: синхронизация потоков в ресторане

Андрей Шагин

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

Вспомним фильм «Убить Билла». У нас действие тоже происходит в роскошном ресторане. В ролях: поток-официант и поток-повар и кнопка вызова официанта — примитив синхронизации condition variable . Кстати, суровые персонажи из «Убить Билла» тоже могут появиться: заглянут на кухню, если им не понравится стрепня повара, а с официантом разберутся прямо на месте, если он будет не слишком расторопен.

Пр е дставьте, что вы в кухне ресторана. Повар ждёт, когда принесут новый заказ. Наконец, официант принимает заказ, и повар начинает готовить. Их коммуникация осуществляется благодаря общей переменной orderStatus , защищаемой мьютексом. Эта переменная может иметь следующие значения:

Теперь представьте, что было бы, если бы официант через каждые две минуты заходил на кухню и спрашивал повара, не готов ли заказ. Верно: это была бы пустая трата времени и нервных клеток. Это называется поллингом: поток-официант всё время захватывает мьютекс и проверяет условие в цикле, что приводит к необязательным потерям цикла и батареи.

Было бы лучше, если бы официант ставил будильник на 10 минут (используя std::this_thread::sleep_for() ), прежде чем в очередной раз спрашивать у повара о готовности заказа.

Так-то оно, конечно, лучше. Но в случае, если заказ будет готов на 11 минуте, пройдут ещё девять минут, прежде чем будильник зазвонит в следующий раз. За это время блюда успеют остыть и официанту придётся иметь дело с недовольными посетителями. А ведь это суровые персонажи из фильма Тарантино!

Читайте так же:
Регулировка плавного пуска электродвигателя

Идеальной была бы такая ситуация: повар нажимает на кнопку вызова официанта, как только заказ будет готов, а официант дремлет в ожидании сигнала от повара. В роли кнопки вызова в C++ выступает примитив синхронизации condition variable , позволяющий блокировать один или несколько потоков до поступления сигнала.

Операционные системы — аспекты параллелизма

Монитор – это конструкция языка программирования, поддерживающая управляемый доступ к разделяемым данным. Монитор инкапсулирует:

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

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

Монитор

Таким образом, монитор по определению решает задачу взаимного исключения – достаточно для работы с критическими данными использовать только методы монитора.

Однако, возможны ситуации, в которых использование монитора приводит к некорректным результатам. Например, предположим, что разделяемыми данными является некоторый буфер, над которым определены операции добавления элемента и изъятия элемента. Изначально буфер пуст. Что произойдет, если первым будет выполнен запрос на изъятия элемента?

Тупиковая ситуация при использовании монитора

Поток, выполнивший функцию изъятия, будет бесконечно ожидать появления данных, поскольку поток, добавляющий данные, не сможет войти в монитор. Для преодоления подобных ситуаций вводятся условные переменные (conditional variable). Условная переменная символизируют ожидание потоком, выполняющим метод монитора, наступления некоторого события (суть события не определяется средствами языка программирования). Над условными переменными определены три операции.

  • wait(cv) – выполняется потоком, который хочет подождать наступления события. Снимает блокировку монитора, после чего другой поток может войти в него; ожидает, пока какой-либо другой поток не подаст условный сигнал.
  • signal(cv) – выполняется потоком, сигнализирующем о наступлении события. Пробуждает максимум один ожидающий поток; если отсутствуют потоки, ожидающие события, информация о приходе сигнала теряется.
  • broadcast(cv) – также выполняется потоком, сигнализирующем о наступлении события. Пробуждает все ожидающие события потоки.
Читайте так же:
Регулировка карбюратора briggs and stratton

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

Существует два типа мониторов, различным образом обрабатывающих поступление сигнала о произошедшем событии: мониторы Хоара и мониторы Меса.

Мониторы Хоара обрабатывают вызов signal(cv) следующим образом:

  • немедленно запускается поток, ожидавший сигнала;
  • поток, пославший сигнал, блокируется и остается блокированным все время, пока выполняется поток, которого он вывел из состояния ожидания.

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

Мониторы Меса обрабатывают вызов signal(cv) несколько другим способом:

  • ожидающий поток переводится в состояние «готов к выполнению», а поток, пославший сигнал, продолжает исполнение;
  • ожидавший поток запускается при выходе потока, пославшего сигнал, из монитора или его перехода в состояние ожидания.

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

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

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

Читайте так же:
Регулировка корректора фар на королле

3.5.3. Синхронные сообщения

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

Обычно реализуются два типа доставки сообщений: синхронная и асинхронная.

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

Сообщения позволяют организовать синхронизацию выполнения потоков.

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

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

3.6. Типовые задачи синхронизации

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

3.6.1. Задача «Производители-потребители»

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

Два потока, обменивающихся информацией через циклический буфер

Функциональность потоков производителя и потребителя можно записать следующим образом.

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

Читайте так же:
Регулировка развала колес легкового автомобиля

Задача «Производители-Потребители» заключается в обеспечении согласованного доступа нескольких потоков к разделяемому циклическому буферу. Корректное решение должно удовлетворять следующим условиям:

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

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

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

Решение задачи «Производитель-Потребитель», использующее семафоры

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

Решение задачи «Производитель-Потребитель», использующие мониторы

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

голоса
Рейтинг статьи
Читайте так же:
Мир матизов регулировка сцепления daewoo matiz
Ссылка на основную публикацию
Adblock
detector