Меню

Механизм синхронизации и семафоры



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

3.4.4. Использование специальных команд ЦП

Задача взаимного исключения была поставлено достаточно давно, и очень скоро была осознана ее важность и необходимость эффективного решения. Для поддержки решения были добавлены специальные команды в набор инструкций ЦП (различные в различны архитектурах). Мы рассмотрим решения, основанные на использовании команд Test&Set и Swap.

Принцип работы команды Test&Set может быть описан в виде следующей функции:

Однако, поскольку Test&Set является одной командой ЦП, ее выполнение не может быть прервано, то есть управление не может быть передано другому потоку до ее завершения. Благодаря этому, можно предложить следующее решение задачи взаимного исключения.

Решение основано на использовании для каждого критического ресурса специального признака блокировки (в примере – переменная lock ). Значение lock = 0 указывает, что ресурс в настоящий момент не используется, значение lock = 1 – что ресурс свободен. Проверка условия работает корректно, поскольку невозможно прервать выполнение инструкции.

Решение с использованием команды swap использует тот же подход.

Описание работы команды swap в виде функции.

Решение задачи взаимного исключения с использованием команды swap.

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

Таким образом, решение задачи взаимного исключения принимает следующий вид (см. рис. 3.5).

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

Данной проблемы можно избежать, если после выполнения каждой итерации цикла добровольно отдавать ЦП системе для передачи другому потоку (используя вызов yield() в UNIX, Sleep() в Win32); в этом случае при каждом получении ЦП поток выполняет только одну итерацию. Еще более эффективное решение инкапсулирует все операции над признаками блокировки в функции, и очередная итерация выполняется только при вызове функции, которая освобождает соответствующий признак блокировки.

Еще один важный момент заключается в том, что на уровне ЦП специализированные инструкции выполняются в виде последовательных операций на различных стадиях конвейера, то есть на уровне ЦП данные операции не являются атомарными. В случае однопроцессорной системы это не имеет значения, поскольку нельзя прервать выполнение потока в середине инструкции, а в многопроцессорной системе с общей памятью или в системе с NUMA-архитектурой (Non-Uniform Memory Access) при одновременном выполнении на двух процессорах специализированной команды для одного и того же признака блокировки мы получим тот же самый эффект гонок, который ранее наблюдали для потоков. Для решения данной проблемы существуют специальные команды или префиксы команд, которые позволяют временно блокировать доступ других процессоров к общей памяти.

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

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

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

3.5. Высокоуровневые механизмы синхронизации

Существует три высокоуровневых механизма синхронизации:

  • Семафоры
  • Мониторы
  • Синхронные сообщения

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

3.5.1. Семафоры

Семафоры – примитивы синхронизации более высокого уровня абстракции, чем признаки блокировки; предложены Дийкстрой (Dijkstra) в 1968 г. в качестве компонента операционной системы THE.

Семафор – это целая неотрицательная переменная sem, для которой определены 2 атомарные операции: P(sem) и V(sem).

  • P(sem) (wait/down) – ожидает выполнения условия sem > 0, затем уменьшает sem на 1 и возвращает управление
  • V(sem) (signal/up) увеличивает sem на 1

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

Читайте также:  Как отключить синхронизацию google на компьютере

Определение структуры семафора.

При вызове потоком P(sem) если sem>0 (семафор «свободен»), его значение уменьшается на 1, и выполнение потока продолжается; если sem S.value в данной реализации может принимать отрицательные значения, их нужно интерпретировать следующим образом: значение семафора равно 0, число потоков, ожидающих увеличения значения семафора, равно |S|.

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

  1. Двоичный семафор может принимать значения 0 и 1, инициализируется значением 1. Используется для обеспечения эксклюзивного доступа к ресурсу (например, при работе в критической секции).
  2. Счетный семафор может принимать значения от 0 до N и представляет ресурсы, состоящие из нескольких однородных элементов, где N – число единиц ресурса.

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

Семафоры первого вида часто оформляются в виде специального механизма синхронизации – мьютексов (mutex, от mutual exclusion). Мьютекс – двоичный семафор, обычно используемый для организации согласованного доступа к неделимому общему ресурсу. Мьютекс может принимать значения 1 (свободен) и 0 (занят). Над мьютексами определены следующие операции:

  • acquire(mutex) – уменьшить (занять) мьютекс;
  • release(mutex) – увеличить (освободить) мьютекс;
  • tryacquire(mutex) – часто реализуемая неблокирующая операция, выполняющая попытку уменьшить (занять) мьютекс, и всегда сразу возвращающая управление.

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

1. Запоминание потока-владельца.

Мьютекс, запоминающий владельца (то есть поток, успешно выполнивший операции acquire() или tryacquire()), освобождается только после вызова операции release() потоком-владельцем. Такие мьютексы удобно использовать для классической организации эксклюзивного доступа к разделяемому ресурсу, включающей следующие шаги: (1) захватить мьютекс, защищающий ресурс; (2) использовать ресурс; (3) освободить мьютекс, защищающий ресурс.

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

Поток может многократно захватить рекурсивный мьютекс (вызывать aquire()); для освобождения мьютекса поток должен соответствующее число раз вызвать release(). Рекурсивные мьютексы удобны в ситуациях, когда имеется множество функций, работающих с одним и тем же критическим ресурсом, каждая функция выполняет последовательность операций «захватить мьютекс, защищающий ресурс», «использовать ресурс», «освободить мьютекс», и функции вызывают друг друга.

3. Наследование приоритета.

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

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

Объединение механизмов синхронизации с защищаемым ресурсом выполнение в мониторах.

Источник

Методы синхронизации процессов

Реализация мониторов с помощью семафоров

Используем семафоры mutex – для взаимного исключения процессов, next – для реализации очереди входа в монитор ; переменную next-count – счетчик процессов в очереди на вход:

Каждую внешнюю процедуру монитора F реализуем следующим кодом:

Таким образом, будет обеспечено взаимное исключение внутри монитора.

Каждую условную переменную x реализуем следующим образом:

Реализация операции x.wait() :

Реализация операции x. signal () :

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

Дополнительная операция над монитором, обеспечивающая организацию очереди к условной переменной по приоритетам, — x.wait(с) ,где c – целочисленный параметр , играющий роль приоритета. При выполнении операции signal первым будет освобожден из очереди процесс с меньшим значением приоритета.

При реализации монитора необходимо проверять следующие условия:

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

Синхронизация в ОС Solaris

Система Solaris предоставляет разнообразные виды блокировщиков для поддержки многозадачности , многопоточности (включая потоки реального времени) и мультипроцессирования. Используются адаптивные мюьтексы (adaptive mutexes) – эффективное средство синхронизации доступа к данным при их обработке короткими сегментами кода. Для более длинных сегментов кода используются условные переменные и блокировщики читателей-писателей (reader-writer locks; rwlocks).Для синхронизации потоков используются «вертушки» (turnstiles) – синхронизирующие примитивы, которые позволяют использовать либо adaptive mutex , либо rwlock.

Читайте также:  Pc suite for android синхронизация пк и смартфона

Синхронизация в Windows 2000

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

Ключевые термины

Interleaving – одновременное выполнение нескольких машинных команд, работающих с общими данными.

Абстрактный тип данных (АТД) – определение типа данных как совокупности описания его конкретного представления и абстрактных операций над ним.

Адаптивный мюьтекс (adaptive mutex) – эффективное средство синхронизации доступа к данным при их обработке короткими сегментами кода в операционной системе Solaris.

Алгоритм булочной (bakery algorithm) – алгоритм синхронизации процессов (Л. Лампорт), основанный на присвоении каждому процессу уникального номера в очереди (приоритета).

Блокировщик читателей-писателей (reader-writer lock; rwlock) – средство синхронизации в ОС Solaris для поддержки схем синхронизации типа » читатели-писатели «.

«Вертушка» (turnstile) – синхронизирующий примитив в ОС Solaris, который позволяет использовать для синхронизации, при необходимости, либо адаптивный мьютекс, либо блокировщик читателей-писателей.

«Вертящийся замок» (spinlock) — средство синхронизации в ОС Windows 2000 , используемое в многопроцессорных системах .

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

жуж — В системе «Эльбрус»: «жужжать» на процессоре; Специализированная операция (для системных процессов) ожидания на закрытом семафоре без прерываний; занятие процессора, пока семафор не будет открыт операцией открыть(S).

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

Критическая область (critical region) – высокоуровневая конструкция для синхронизации, основанная на описаниях разделяемых (shared) ресурсов и конструкции region, обеспечивающей взаимное исключение при работе с общим ресурсом.

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

Обедающие философы (dining philosophers) – классическая задача синхронизации следующего содержания: имеется круглый стол, за которым пять философов. Перед каждым из них тарелка с едой, слева и справа – две китайские палочки. Философ может находиться в трех состояниях: проголодаться, думать и обедать. На голодный желудок философ думать не может. Начать обедать философ может, только если обе палочки слева и справа от него свободны.

Общий семафор (counting semaphore) — целая переменная S, над которой определены две атомарных семафорных операции wait (S) и signal (S).

Объект-диспетчер (dispatcher object) – средство синхронизации в ОС Windows 2000 , которое может функционировать как мьютекс и как семафор; генерирует события, семантика которых аналогична семантике условной переменной.

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

Семафорный бит – В вычислительных комплексах Burroughs 5000 и «Эльбрус»: особый бит слова, над которым выполняется команда семафорного считывания; по определенному значению бита (например, 1) происходит прерывание .

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

Условная переменная (condition variable) – часть конструкции монитор: Переменная с описанием вида condition x, доступ к которой возможен только операциями wait и signal ; операция x.wait() задерживает выполнивший ее процесс до момента, пока другой процесс не выполнит операцию x.signal().

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

Источник

Обзор примитивов синхронизации — Семафор и немного lockless-а

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

Но сначала — пара слов о случайных пробуждениях. (Спасибо xaizek, который мне об этом напомнил.) В принципе, строго реализованные механизмы синхронизации этим не страдают, но, тем не менее, опытный программист на это никогда не полагается.

Читайте также:  Центр синхронизации windows что это такое

Напомню фрагмент кода:

Здесь цикл вокруг wait_cond гарантирует нам, что даже если мы вернёмся из ожидания события случайно или по ошибке, ничего страшного не случится — проверка в while обеспечит нам уверенность, что нужное состояние проверяемого объекта достигнуто. Если нет — поспим ещё в ожидании.

Отметим ещё раз, что проверяем мы состояние объекта (total_free_mem Код и ещё кое-чем неверен

Не дело. Выходит, нужно «накрыть» зоны работы с буфером обычным mutex-ом или семафором «в режиме» мьютекса? Тогда в чём преимущество семафора перед обычным cond-ом?

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

Во-вторых, применим лё-ёгенький lockless алгоритм:

Здесь atomic_add атомарно выполняет rpos = read_pos++. Это гарантирует нам, что для двух нитей параллельное исполнение пройдёт правильно — каждая получит свой байт, хотя и неизвестно, в какой очерёдности.

Правда, останутся проблемы с read_pos %= sizeof(buf); — строго говоря, эту операцию нужно делать атомарно «внутри» atomic_add. То есть должна быть полная атомарная операция считывание-инкремент-ограничение.

Атомарной и переносимой операции считывание-инкремент-ограничение — нет. На некоторых процессорах (например, MIPS) её можно организовать, но мы пишем переносимый код.

Как можно исправить проблему? И, для начала, в чём она? Потенциальная ошибочная последовательность для нитей А и Б:

  • Стартовое значение read_pos = sizeof(buf)-1;
  • А: считывание и инкремент
  • Б: считывание и инкремент, при этом считанное значение = sizeof(buf), то есть выходит за границу массива.

Дальше последовательно сработают два read_pos %= sizeof(buf);, но уже поздно.

Здесь нам повезло. Достаточно простой корректировки:

Кроме того, операция read_pos %= sizeof(buf);, как справедливо отметил degs, тоже должна быть атомарной, что малореально — gcc не предлагает такой операции среди встроенных атомарных функций (здесь).

Однако, эту операцию можно просто исключить, если размер массива кратен степени двойки. Коль скоро мы ограничиваем размером массива считанное в atomic_add значение, сам read_pos можно уже не трогать — пусть растёт и оборачивается через 0xFFFFFFFF в ноль, остаток от его деления на размер массива всегда будет верным.

(Для полного взрыва мозга добавлю, что всё будет работать и для некратных размеров, если работа с адресом считывания и адресом записи организована идентично. Просто в момент переполнения счётчика код не задействует часть буфера. )

О семафорах на этом, пожалуй, всё.

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

Существует старая как мир проблема deadlock-а в теоретически верной программе из-за приоритетов нитей.

Предположим, у нас есть нити А, Б и В, приоритеты которых, соответственно, 3, 2 и 1, то есть у А — наивысший. Все приоритеты — класса реального времени, то есть если А есть что делать, то она получает процессор безусловно, а Б и В ждут.

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

В нормальной жизни А крутится в цикле — спит до окончания слота в 1 мсек, потом снимает показания и рулит стержнями. Б считает ворон нейтроны, и на следующие 5-6 сек у неё работа есть. Соответственно, нити В процессора вообще не перепадает. Б и А важнее.

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

Останавливается навсегда или, как минимум, на 5-6 секунд — В не получит процессора, пока Б не досчитает. В итоге нить А пропустит свой таймслот и реактор останется без контроля.

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

То есть, в нашем примере, В получит приоритет А и снесёт с процессора докучливого Б, чтобы А не ждал лишку.

Конечно, пример тенденциозен, но, надеюсь, суть он отразил.

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

Источник

Adblock
detector