|
|
Лекция: Методы синхронизации процессовСтр 1 из 3Следующая ⇒ Лекция: Методы синхронизации процессов
В лекции рассмотрена синхронизация процессов: критические секции; алгоритмы решения проблемы взаимного исключение критических секций; двоичные и общие семафоры; решение проблем "ограниченный буфер", "читатели-писатели", "обедающие философы"; мониторы; синхронизация в Solaris и Windows 2000. Содержание
Введение В лекции рассматривается синхронизация процессов – одна из интереснейших и наиболее актуальных тем, в связи с широким распространением параллельных вычислительных систем и параллельных алгоритмов решения задач, требующих синхронизации параллельных процессов и потоков по общим ресурсам и событиям. В лекции рассмотрены следующие вопросы:
 Проблема критической секции Аппаратная поддержка синхронизации Семафоры Классические проблемы синхронизации
Мониторы Синхронизация в Solaris и в Windows. История синхронизации Методы синхронизации процессов рассматривались еще в 1960-х гг. в пионерской работе Э. Дейкстры [17]. Было отмечено, что совместный доступ параллельных процессов к общим данным может привести к нарушению их целостности. Поддержание целостности общих данных требует реализации и использования механизмов упорядочения работы взаимодействующих процессов (или потоков). Синхронизация на основе общих семафоров Мы уже начали рассматривать семафоры Дейкстры как средство синхронизации в обзорной части курса. Здесь мы рассмотрим их более подробно в общем виде. Общий семафор (counting semaphore), по Э. Дейкстре, - это целая переменная S, над которой определены две атомарных семафорных операции wait (S) и signal (S) со следующей семантикой: wait (S): while (S <= 0) do no-op; S--; signal (S): S++; Фактически, если начальное значение общего семафора равно n (> 0), то это число задает количество процессов, которые могут беспрепятственно выполнить над семафором операцию wait. Синхронизация по критическим секциям с помощью общего семафора осуществляется следующим образом: /* общие данные */ semaphore mutex = 1; do { wait (mutex); критическая секция signal (mutex); остальная часть кода } while (1) Реализация семафоров Семафор, по существу, является структурой из двух полей – целого значения и указателя на список ждущих процессов: typedef struct { int value; struct process * L; } semaphore; При реализации операций над семафором будем предполагать наличие в системе следующих простейших примитивов, и использовать их: block - задерживает исполнение процесса, выполнившего эту операцию; wakeup (P) – возобновляет исполнение приостановленного процесса P. Определим семафорные операции следующим образом: wait (S): S.value--; if (S.value < 0) { добавление текущего процесса к S.L; block; } signal (S): S.value++; if (S.value <= 0) { удаление процесса P из S.L; wakeup (P); } Общие и двоичные семафоры Из рассмотренного ясно, что имеется два вида семафоров: общий - целая переменная с теоретически неограниченным значением - и двоичный - целая переменная, значениями которой могут быть только 0 или 1. Преимуществом двоичного семафора является его возможная более простая аппаратная реализация. Например, в системах "Эльбрус" и Burroughs 5000 реализованы команды атомарного семафорного считывания с проверкой семафорного бита. Очевидно, что общий семафор может быть реализован с помощью двоичного семафора. Критические области Критические области (critical regions) – более высокоуровневая и надежная конструкция для синхронизации, чем семафоры. Общий ресурс описывается в виде особого описания переменной: v: shared T Доступ к переменной v возможен только с помощью специальной конструкции: region v when B do S где v – общий ресурс; B – булевское условие, S – оператор (содержащий действия над v). Семантика данной конструкции следующая. Пока B ложно, процесс, ее исполняющий, должен ждать. Когда B становится истинным, процесс получает доступ к ресурсу v и выполняет над ним операции S. Пока исполняется оператор S, больше ни один процесс не имеет доступа к переменной v. Решение с помощью критических областей задачи "ограниченный буфер" Опишем буфер как структуру: struct buffer { int pool [n]; int count, in, out } buf: shared buffer; Алгоритм процесса-производителя: region buf when (count < n) { pool [in] = nextp; in = (in+1) % n; count++; } Заметим, что проверка переполнения буфера выполняется при входе в конструкцию region, и потребитель ждет, пока в буфере освободится хотя бы один элемент. Алгоритм процесса-потребителя: region buf when (count > 0) { nextc = pool [out]; out = (out+1) % n; count--; } Нельзя не отметить, насколько проще и надежнее оказывается решение задачи с использованием данной конструкции, по сравнению с использованием семафоров. Мониторы Конструкция монитор предложена в 1974 г. Ч. Хоаром [18]. Она является более высокоуровневой и более надежной конструкцией для синхронизации, чем семафоры. Описание монитора имеет вид: monitor monitor-name { описания общих переменных procedure body P1 (…) { ... } procedure body P2 (…) { ... } ... procedure body Pn(…) { ... } { код инициализации монитора } } Монитор является многовходовым модулем особого рода. Он содержит описания общих для нескольких параллельных процессов данных и операций над этими данными в виде процедур P1, …, Pn. Пользователи монитора – параллельные процессы – имеют доступ к описанным в нем общим данным только через его операции, причем в каждый момент времени не более чем один процесс может выполнять какую-либо операцию монитора; остальные процессы, желающие выполнить операцию монитора, должны ждать, пока первый процесс закончит выполнять мониторную операцию. По сути дела, концепция монитора явилась развитием предложенной также Ч. Хоаром концепции абстрактного типа данных (АТД) – определения типа данных как совокупности описания его конкретного представления и абстрактных операций над ним (в виде процедур). Концепция монитора добавляет к АТД возможность синхронизации процессов по общим данным. Для реализации ожидания внутри монитора по различным условиям, вводятся условные переменные (condition variables) – переменные с описаниями вида condition x,y, доступ к которым возможен только операциями wait и signal: например, x.wait(); x.signal(). Операция x.wait() означает, что выполнивший ее процесс задерживается до того момента, пока другой процесс не выполнит операцию x.signal(). Операция x.signal() возобновляет ровно один приостановленный процесс. Если приостановленных процессов нет, она не выполняет никаких действий. Схематическое изображение монитора приведено на рис. 12.2.
Рис. 12.2. Схематическое изображение монитора. Схема монитора с условными переменными приведена на рис. 12.3.
Рис. 12.3. Монитор с условными переменными. Решение задачи "обедающие философы" с помощью мониторов Реализуем решение задачи "обедающие философы" (см. Решение с помощью семафоров задачи "обедающие философы") с помощью монитора. Для каждого философа определим состояния (голодный, обедает, думает), и для их хранения будем использовать массив state. Для управления переходом философа из состояния в состояние используем массив условных переменных self. Для каждого философа определим операции pickup – взять палочку; putdown – освободить палочку; test – проверить состояние философа и, если это возможно и если он голоден, перевести его в состояние eating. Код монитора, реализующего решение задачи: monitor dp { enum {thinking, hungry, eating} state [5]; condition self [5]; void pickup (int i) { state [i] = hungry; test (i); if (state[i]!= eating) { self[i].wait (); } } /* pickup */ void putdown (int i) { state [i] = thinking; test ((i+4) % 5)); test ((i-1) % 5)); /* когда палочка свободна, проверить соседей */ } /* putdown */ void test (int i) { if (state((i+4)%5)!= eating && state [i] = hungry && state((i+1)%5)!= eating)) { state[i] = eating; self[i].signal;
void init () { for (int i = 0; i < 5; i++) { state[i] = thinking; } } Синхронизация в ОС Solaris Система Solaris предоставляет разнообразные виды блокировщиков для поддержки многозадачности, многопоточности (включая потоки реального времени) и мультипроцессирования. Используются адаптивные мюьтексы (adaptive mutexes) – эффективное средство синхронизации доступа к данным при их обработке короткими сегментами кода. Для более длинных сегментов кода используются условные переменные и блокировщики читателей-писателей (reader-writer locks; rwlocks). Для синхронизации потоков используются "вертушки" (turnstiles) – синхронизирующие примитивы, которые позволяют использовать либо adaptive mutex, либо rwlock. Ключевые термины 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 (счетчик числа элементов в буфере) играет роль общего ресурса дл я производит еля и потребителя, по которому необходима их синхронизация. Если ее не В общем случае, если имеется n процессов, у каждого из них есть своя критическая секция – фрагмент кода, работающий с общим ресурсом, и н еобходи мо обеспечить взаимное исключение исполнения критических секций. Для
Использует присвоение уникального номера в очереди (приоритета) каждому процессу. Алгоритмы синхронизации более просты, если они используют аппаратную поддержку атомарных операций – проверка и установка (test-and-set) и перестановка значений двух переменных (swap). Приведена реализация синхронизации процессов с использованием обеих операций. Общий семафор (по Э. Дейкстре) – синхронизирующий примитив: целая переменная, над которой определены семафорные операции wait и signal. Приведено решение проблемы критических секций с помощью семафоров. Семафор реализуется в виде структуры из двух полей: счетчик и ссылка на список ждущих процессов. Для реализации операций над семафором достаточно двух примитивов: block – блокировка текущего процесса, wakeup(P) – разблокировка процесса P. Семафоры могут использоваться как общее средство синхронизации по ресурсам и по событиям. Используются две разновидности семафоров – общие (с целым значением) и двоичные (значениями могут быть только 0 и 1). Общий семафор может быть реализован с помощью двоичных семафоров. Имеются при классических задачи (схемы) синхронизации процессов – ограниченный буфер, читатели-писатели и обедающие философы. Рассмотрены решения этих задач с использованием семафоров. Критические области – высокоуровневая конструкция для синхронизации, основанная на описаниях разделяемых ресурсов (shared) и конструкции region, обеспечивающей взаимное исключение критических секций более удобным и надежным способом, чем семафоры. Рассмотрено решение задачи "ограниченный буфер" с помощью критических областей. Рассмотрена схема реализации критических областей с использованием семафоров. Монитор (по Ч. Хоару) – высокоуровневая конструкция для синхронизации: многовходовый модуль, содержащий описание общих данных и операций над ними в виде процедур. Обеспечивается взаимное исключение исполнения мониторных операций. Монитор может также содержать условные переменные, для которых определены операции wait и signal для организации дополнительных очередей процессов. Рассмотрено решение задачи "обедающие философы" с использованием монитора. Описана реализация монитора и условных переменных с помощью семафоров. В системе Solaris для синхронизации используются адаптивные мьютексы, блокировщики читателей-писателей, условные переменные и "вертушки" (turnstiles), позволяющие сочетать применение адаптивных мьютексов и блокировщиков читателей писателей. В системе Windows 2000 для синхронизации используются вертящиеся замки (spinlocks) и объекты-диспетчеры, генерирующие события (аналогичные условным переменным). Лекция: Методы синхронизации процессов
В лекции рассмотрена синхронизация процессов: критические секции; алгоритмы решения проблемы взаимного исключение критических секций; двоичные и общие семафоры; решение проблем "ограниченный буфер", "читатели-писатели", "обедающие философы"; мониторы; синхронизация в Solaris и Windows 2000. Содержание
Введение В лекции рассматривается синхронизация процессов – одна из интереснейших и наиболее актуальных тем, в связи с широким распространением параллельных вычислительных систем и параллельных алгоритмов решения задач, требующих синхронизации параллельных процессов и потоков по общим ресурсам и событиям. В лекции рассмотрены следующие вопросы:
Проблема критической секции Аппаратная поддержка синхронизации Семафоры Классические проблемы синхронизации
Мониторы Синхронизация в Solaris и в Windows. История синхронизации Методы синхронизации процессов рассматривались еще в 1960-х гг. в пионерской работе Э. Дейкстры [17]. Было отмечено, что совместный доступ параллельных процессов к общим данным может привести к нарушению их целостности. Поддержание целостности общих данных требует реализации и использования механизмов упорядочения работы взаимодействующих процессов (или потоков).   Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...  Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
Введение
Краткие итоги
