Алгоритмы синхронизации - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Алгоритмы синхронизации. Доклад-сообщение содержит 54 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Алгоритмы синхронизации Судаков А.А. “Параллельные и распределенные вычисления” Лекция 15

Слайд 2

Описание слайда:

План Необходимость синхронизации Синхронизация в системах с общей памятью Спин-блокировки Секвентные блокировки Семафоры Условные переменные Синхронизация в системах с распределенной памятью Барьер

Слайд 3

Описание слайда:

Литература Лекции по параллельным и распределенным вычислениям

Слайд 4

Описание слайда:

Необходимость синхронизации Синхронизация – обеспечение того, что взаимодействующие процессы находятся в строго определенном состоянии Синхронизация необходима для того, чтобы гарантировать непротиворечивость (консистентность данных)‏

Слайд 5

Описание слайда:

Пример: файл данных Процесс 1 Записывает данные расчета в файл Процесс 2 Считывает из файла данные, записанные процессом 1 и работает с ними Проблема Чтобы процесс 2 нормально отработал, необходимо, чтобы перед считыванием данных данные уже были в файле Как решить Обеспечить гарантию, что процесс 2 начнет считывать данные только после того, как процесс 1 их запишет

Слайд 6

Описание слайда:

Пример 2: общая переменная a=1 Поток1 : считываем a a=1 Поток2 : увеличивает a на 1 a=2 Поток1 : записывает a назад a=2 Поток2 : считываем a a=2 Поток2 : увеличивает a на 1 a=3 Поток2: записывает a назад a=3 Результат - правильный

Слайд 7

Описание слайда:

Критические участки Критический участок – это код, который оперирует с совместно используемыми данными Состояние конкуренции за ресурс (race condition) – ситуация в которой параллельный доступ к данным может привести к тому, что данные окажутся в неопределенном или разрушенном состоянии

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Атомарные операции Атомарные операции – операции, которые выполняются не прерываясь и не перекрываясь. Две атомарные операции с одними и теми же данными могут выполняться строго последовательно

Слайд 10

Описание слайда:

Пример: вставка в связанный список Поток 1 Вставляет элемент new перед элементом 2 Поток 2 Удаляет элемент 2 Проблема Если не принять соответствующих мер, то элемент new может остаться указывать на удаленный элемент Решение – все операции вставки-удаления элементов должны быть атомарными

Слайд 11

Описание слайда:

Синхронизация в системах с общей памятью Память общая –> возможность доступа к общим данным –> возможность конкуренции за ресурс Очень часто необходима синхронизация доступа к данным Удобство и скорость доступа к общим данным компенсируется необходимостью использования синхронизации

Слайд 12

Описание слайда:

Атомарные операции с общей памятью Часть операций обеспечивается аппаратными инструкциями Целочисленное сложение в ячейке памяти Битовые операции Для сложных операций необходимо использовать программные средства синхронизации блокировки связанного списка Для RISC процессоров часто даже для простых операций приходится использовать программные средства

Слайд 13

Описание слайда:

Блокировки Блокировка – ресурс (переменная), который обеспечивает к себе взаимоисключающий доступ Блокировки Обязательные (mandatory) – при обращении к ресурсу блокировка захватывается обязательно Рекомендуемые (advisory) – при обращении к ресурсу блокировка захватывается по желанию разработчика

Слайд 14

Описание слайда:

Захват и освобождение блокировок С блокировками возможны две операции Захват Освобождение В захваченном состоянии блокировку может удерживать только один поток (процесс)‏ После освобождения блокировку снова можно захватывать

Слайд 15

Описание слайда:

Обеспечение атомарности с помощью блокировки lock – общая переменная List – общий связанный список Поток 1 Захватить(lock)‏ Если захват успешный, то все остальные будут ждать захвата Вставка (list)‏ Освободить(lock)‏

Слайд 16

Описание слайда:

Предотвращение состояний конкуренции Доступ к совместно используемым ресурсам необходимо блокировать В критических участках необходимо использовать блокировки Блокировать необходимо данные, а не код! Блокировки необходимо связывать с совместными данными

Слайд 17

Описание слайда:

Взаимоблокировка (deadlock)‏ Общие блокировки Lock_a, lock_b Процесс 1 Захватить (lock_a)‏ Захватить (lock_b)‏ Вечно ожидаем освобождения lock_b lock_b не может быть освобождена, процесс 2 застрял на lock_a

Слайд 18

Описание слайда:

Самоблокировка Блокировка lock Процесс Захватить (lock)‏ .. Захватить (lock)‏ Попытка захватить уже захваченную и никогда не освобождаемую блокировку приведет к зависанию

Слайд 19

Описание слайда:

Предотвращение взаимоблокировок На каждую операцию захвата любой блокировки необходима операция освобождения Разные блокировки в разных процессах необходимо захватывать в строго определенном порядке Освобождать желательно в обратном порядке (хотя и не обязательно)‏

Слайд 20

Описание слайда:

Еще раз о состоянии конкуренции Лишняя операция освобождения может привести к состоянию конкуренции Процесс Захват()‏ … Освобождение()‏ Освобождаем захваченную нами блокировку (ресурс свободен)‏ Освобождение()‏ Освобождаем захваченную кем-то другим блокировку Предоставляем конкурентный доступ к ресурсу кому-то третьему

Слайд 21

Описание слайда:

Спин-блокировки Спин-блокировка – использование бесконечного цикла (вращения) для проверки условия возможности доступа к ресурсу Самый быстрый тип блокировки Используется, когда время выполнения критической секции мало Постоянно занимают процессор

Слайд 22

Описание слайда:

Спин блокировка с атомарными операциями Test-and-set lock Атомарная машинная инструкция tas(addr,val)‏ Атомарно считывает предыдущее значение из области памяти addr и устанавливает значение этой области памяти в val

Слайд 23

Описание слайда:

Блокировки без атомарных операций Используются последовательные операции записи, чтения, проверки нескольких переменных Алгоритм Петерсона Два процессора 0 и 1 me() – номер текущего процессора Три общих переменных Flag[2] – кто ожидает Victim – кто захватывает

Слайд 24

Описание слайда:

Свойства Алгоритм Петерсона обеспечивает взаимоисключающий доступ к критическому разделу Алгоритм Петерсона гарантирует отсутствие бесконечного ожидания

Слайд 25

Описание слайда:

Доказательство взаимоисключения Запишем последовательность действий обоих процессоров Запись0(flag[0]=1)->запись0(victim=0) ->чтение0(flag[1])->чтение0(victim)‏ Запись1(flag[1]=1)->запись1(victim=1) ->чтение1(flag[0])->чтение1(victim)‏ Допустим, что оба процессора вошли в критический раздел Пусть для определенности процессор 0 записал значение переменной victim последним Все значения flag[] уже записаны Тогда последовательность записи этой переменной была следующей запись1(victim=1)->запись0(victim=0)‏ Раз процессор 0 вошел в критический раздел, то он прочитал flag[1]=0, victim=0 Значит последовательность операций была запись0(victim=0)-> чтение1(flag[1]==0)‏ Учитывая первые 3 уравнения Запись1(flag[1]=1)->запись1(victim=1) ->запись0(victim=0)->чтение1(flag[1]==0)‏ Получается, что значение переменной flag[1] поменялось после записи victim, а такого не может быть

Слайд 26

Описание слайда:

Доказательство отсутствия бесконечного ожидания Пусть процессор 0 бесконечно ожидает в цикле, тогда flag[1]=1 и victim=0 Такая ситуация может возникнуть только когда процессор 1 выполнил команду flag[me()]=1; и еще не выполнил команду victim = me(); Эти две команды идут подряд, поэтому, если выполнилась первая, то вторая тоже скоро выполнится

Слайд 27

Описание слайда:

Алгоритмы для N процессоров Более сложные Используется следующий принцип: Каждому процессору, которые ожидают на захват блокировки назначается уникальная комбинация его номера и целочисленной метки Только для одного процессора его комбинация номер-метка позволяет войти в критический раздел

Слайд 28

Описание слайда:

Блокировка в состоянии конфликта Спин-блокировка - сложный алгоритм, который выполняется несколькими процессами одновременно Когда за захват блокировки состязаются потоки – блокировка находится в состоянии конфликта (contended)‏ Различные алгоритмы требуют разного количества операций при обработке состояния конфликта при большом количестве потоков

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

Спин-блокировки для реальных систем Атомарные операции – медленные Запись в общую память может выполняться не сразу, а буферизироваться процессором Компилятор может пытаться оптимизировать код и изменять порядок операций Необходимо использовать барьеры памяти, компилятора Существует множество библиотечных функций для обеспечения блокировок

Слайд 31

Описание слайда:

Блокировки чтения-записи Несколько операций чтения могут выполняться параллельно с одной и той же переменной Операции записи должны быть строго последовательными При записи чтение должно запрещаться Такую возможность обеспечивает блокировка чтения-записи

Слайд 32

Описание слайда:

Пример использования блокировки чтения-записи //Общая переменная rw_lock lock; //общий связанный список Llist list; Поток 1 write_lock(&lock); //эксклюзивный //доступ на запись insert(list); write_unlock(&lock);

Слайд 33

$Пример реализации rw блокировки int readers=0; int writes=0; Spinlock l; void read_lock(){ while(1){ lock(l); if(!writers) { readers++; unlock();...$

Описание слайда:

Пример реализации rw блокировки int readers=0; int writes=0; Spinlock l; void read_lock(){ while(1){ lock(l); if(!writers) { readers++; unlock(); break; } unlock(l); } } Void read_unlock(){ lock(l); readers--; unlock(l) }

Слайд 34

Описание слайда:

Отказ обслуживания записи при обслуживании чтения Пример: 1 поток записи 1000 потоков чтения Один поток чтения захватывает блокировку Все потоки чтения ею пользуются 1 поток записи ждет долго! Реальный пример Системный таймер 1 поток записывает значение времени в общую переменную Остальные потоки читают это значение В нашем случае часы будут отставать

Слайд 35

Описание слайда:

Блокировки чтения-записи с приоритетом на запись Секвентная блокировка (seq_lock)‏ Вводится счетчик Перед началом каждой операции записи значение счетчика увеличивается на 1 После окончания записи значение счетчика снова увеличивается на 1 Вначале и в конце чтения значение счетчика проверяется Если они четные, то новый акт записи закончен Если значения одинаковы, то акт записи в процессе чтения не начинался

Слайд 36

Описание слайда:

Использование секвентных блокировок //Общая переменная time_t time; //Блокировка Seqlock lock; Поток записи write_seqlock(lock); time=…; write_sequnlock(lock);

Слайд 37

$Реализация seqlock Spinlock l; Counter c; write_seqlock(){ lock(l); c++ } write_sequnlock(){ c++ unlock(l); }$

Описание слайда:

Реализация seqlock Spinlock l; Counter c; write_seqlock(){ lock(l); c++ } write_sequnlock(){ c++ unlock(l); }

Слайд 38

Описание слайда:

Недостатки spinlock Занимают процессорное время Не могут использоваться для длительного времени ожидания

Слайд 39

Описание слайда:

Семафоры Семафоры – целочисленные переменные с которыми возможно выполнять атомарные операции увеличения/уменьшения на 1 Если значение семафора становится меньшем нуля, то процесс, который выполнил такую операцию блокируется, пока значение семафора не станет большим или равным нулю Процессы, ожидающие освобождения семафора не занимают процессорное время

Слайд 40

Описание слайда:

Операции с семафорами Присвоение значения Подъем (увеличение на 1) – up()‏ Опускание (уменьшение на 1) – down()‏ Требование нулевого значение (есть не во всех реализациях) test()‏ Считывание значение read()‏ Все операции атомарные

Слайд 41

Описание слайда:

Mutex Mutex – семафор с начальным значение 1 Используется для взаимоисключающего доступа

Слайд 42

Описание слайда:

Пример: //Общий связанный список List l; Поток записи Semaphore mutex(1); down(mutex); // mutex=0 insert(list); up(mutex);

Слайд 43

Описание слайда:

Счетный семафор Семафор со значением большим 1 может использоваться в качестве атомарного счетчика Semaphore a(1); Поток 1 Поток 2 Up(a); read(a);

Слайд 44

Описание слайда:

Реализация семафоров Блокировка с помощью очереди Счетчик семафора Очередь процессов, которые захватывают семафор Очередь защищается спин-блокировкой Как только семафор становится меньшим нуля, процессы при захвате добавляются в очередь При отпускании семафора процессы извлекаются из очереди

Слайд 45

Описание слайда:

Пример реализации семафора Spinlock l; Int count; Queue q; //текущий процесс current down(){ lock(l)‏ if(count>0) { count--; unlock(l); } else { queue.insert(current); unlock(l); stop(current) } }

Слайд 46

Описание слайда:

Семафоры чтения записи По аналогии со спин блокировками чтения записи

Слайд 47

Описание слайда:

Особенности семафоров Семафоры обычно реализуются операционными системами По сравнению со спин-блокировкой семафор – «тяжелая» операция, требующая много времени

Слайд 48

Описание слайда:

Условные переменные Условная переменная – вид блокировки, которая позволяет информировать процессы о наступлении некоторого события Пример – срабатывание будильника

Слайд 49

Описание слайда:

Пример использование Event e; Потоки, ожидающие на события e.wait(); //ожидаем, пока событие не наступит

Слайд 50

Описание слайда:

Мониторы Монитор – объект Данные+методы безопасного доступа к этим данным Обеспечивает обязательную блокировку в отличие от всех предыдущих способов Counter{ int c; semaphore s; public: int operator ++(){…} int operator --(){…} }

Слайд 51

Описание слайда:

Барьер Барьер – коллективная синхронизация Гарантия того, что те или иные операции выполнены всеми потоками, процессами

Слайд 52

Описание слайда:

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