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

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

semaphore mutex = 1; semaphore next = 0; int next-count = 0;

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

wait (mutex);

... тело F;

...

if (next-count > 0) {

signal next;

} else {

signal mutex;

}

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

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

semaphore x-sem = 0; int x-count = 0;

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

x-count++; if (next-count > 0) {

signal (next);

} else {

signal (mutex);

} wait(x-sem); x-count--;

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

if (x-count > 0) {

next-count++; signal (x-sem); wait (next);

next-count--;

}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Конкуренция за общие данные (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().

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

Краткие итоги

Синхронизация процессов – актуальная задача, исследование которой началось с работ Э. Дейкстры в 1960-х гг. Совместный доступ процессов к общим данным (race condition) может привести к нарушению их целостности, поэтому необходима их синхронизация.

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

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

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

Алгоритм булочной – еще один подход к решению проблемы критических секций.

Использует присвоение уникального номера в очереди (приоритета) каждому процессу.

Алгоритмы синхронизации более просты, если они используют аппаратную поддержку атомарных операций – проверка и установка (test-and-set) и перестановка значений двух переменных (swap). Приведена реализация синхронизации процессов с использованием обеих операций.

Общий семафор (по Э. Дейкстре) – синхронизирующий примитив: целая переменная, над которой определены семафорные операции wait и signal. Приведено решение проблемы критических секций с помощью семафоров. Семафор реализуется в виде структуры из двух полей: счетчик и ссылка на список ждущих процессов. Для реализации операций над семафором достаточно двух примитивов: block – блокировка текущего процесса, wakeup(P) – разблокировка процесса P.

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

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

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

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

Монитор (по Ч. Хоару) – высокоуровневая конструкция для синхронизации: многовходовый модуль, содержащий описание общих данных и операций над ними в виде процедур. Обеспечивается взаимное исключение исполнения мониторных операций. Монитор может также содержать условные переменные, для которых определены операции wait и signal для организации дополнительных очередей процессов. Рассмотрено решение задачи "обедающие философы" с использованием монитора. Описана реализация монитора и условных переменных с помощью семафоров.

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

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

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: