Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
5. Примитивы синхронизации
Содержание
- 1. 5. Примитивы синхронизации
- 2. 5.1. Примитив синхронизации и блокировка потоков
- 3. Определение примитива синхронизацииПримитив синхронизации это программное средство
- 4. Блокировка потоковРассмотрим реализацию примитивов синхронизации только для
- 5. Очередь потоковДля этого с каждым примитивом синхронизации свяжем очередь заблокированных потоков, ждущих освобождения этого примитива синхронизации.
- 6. Спецификация очереди блокированных потоковclass ThreadQueue{ Thread *tp;
- 7. void ThreadQueue::enqueueThread(Thread& t){ includeThreadToList(t); t.suspendThread();}bool ThreadQueue:: dequeueThread(){ Thread t; if(!tp) return false; else { t = excludeThreadFromList(); t.resumeThread(); return true; }}
- 8. 5.2. Примитив синхронизации Lock (замок)
- 9. Схема реализации примитива синхронизации Lockclass Lock{ bool free; ThreadQueue
- 10. void Lock::acquire() // закрываем замок{ disableInterrupt(); if (!free) tq.enqueueThread(currentThread()); else free = false; enableInterrupt();}
- 11. void Lock::release() // открываем замок{ disableInterrupt(); if (!tq.dequeueThread()) free = true; enableInterrupt();}
- 12. Решение проблемы взаимного исключения для двух потоков
- 13. Аналоги примитива Lock в WindowsВ операционной системе
- 14. 5.3. Примитив синхронизации Condition (условие)
- 15. Схема реализации примитива синхронизации Conditionclass Condition{ bool event; ThreadQueue
- 16. // ждем выполнения условияvoid Condition::wait(){ disableInterrupt(); if (event) event = false; else tq.enqueueThread(currentThread()); enableInterrupt(); }
- 17. // сигнализируем о выполнении условияvoid signal(){ disableInterrupt(); if (!tq.dequeueThread()) event = true; enableInterrupt(); }
- 18. Решение задачи условной синхронизации для двух потоков
- 19. Решение при помощи примитива синхронизации Condition проблемы
- 20. Аналог примитива Condition в WindowsВ операционной системе Windows аналогом примитива синхронизации Condition является примитив синхронизации Event.
- 21. 5.4. Семафоры Дейкстры
- 22. Определение семафораСемафор – это неотрицательная целочисленная переменная,
- 23. Операции над семафоромПусть s – семафор, тогда
- 24. Из определения операций над семафором видно, что
- 25. Определение семафора ДейкстрыСемафор с операциями P и
- 26. Сильный и слабый семафорыПотоки, ждущие освобождения семафора,
- 27. Двоичный и считающий семафорыСемафор, который может принимать
- 28. Решение проблемы взаимного исключения для двух потоков
- 29. Решение проблемы условной синхронизации для двух потоков
- 30. 5.5. Примитив синхронизации Semaphore (семафор)
- 31. class Semaphore{ int count;
- 32. void Semaphore::wait() // закрыть
- 33. void Semaphore::signal() // открыть семафор {
- 34. 5.6. Объекты синхронизации и функции ожидания в Windows
- 35. Объекты синхронизацииВ операционных системах Windows объектами синхронизации
- 36. Классификация объектов синхронизацииОбъекты синхронизации могут быть разбиты
- 37. Функции ожиданияФункции ожидания в Windows это такие
- 38. Функции ожидания в WindowsWaitForSingleObject – ждет перехода
- 39. 5.7. Критические секции в Windows
- 40. Назначение объекта критическая секцияДля решения проблемы взаимного
- 41. Функции для работы с объектами типа CRITICAL_SECTIONInitializeCriticalSection
- 42. 5.8. Мьютексы в Windows
- 43. Назначение мьютексовДля решения проблемы взаимного исключения для
- 44. Функции для работы с мьютексамиCreateMutex – создание
- 45. 5.9. События в Windows
- 46. Назначение событийВ операционных системах Windows события описываются
- 47. Типы событийВ Windows различают два типа событий:события с ручным сбросом;события с автоматическим сбросом.
- 48. События с ручным сбросомСобытие с ручным сбросом
- 49. События с автоматическим сбросомСобытие с автоматическим сбросом
- 50. Функции для работы с событиямиCreateEvent – создание
- 51. 5.10. Семафоры в Windows
- 52. Назначения семафоровСемафоры в операционных системах Windows описываются
- 53. Состояния и значения семафораСемафор находится в сигнальном
- 54. Функции для работы с семафорамиCreateSemaphore – создание
- 55. Скачать презентанцию
5.1. Примитив синхронизации и блокировка потоков
Слайды и текст этой презентации
Слайд 3Определение примитива синхронизации
Примитив синхронизации это программное средство (механизм, инструмент) высокого
уровня для решения задач синхронизации потоков.
реализованы как объекты ядра ОС.
Слайд 4Блокировка потоков
Рассмотрим реализацию примитивов синхронизации только для однопроцессорных компьютеров.
При этом
предположим, что микропроцессор имеет только одно ядро.
В этом случае атомарность
действий можно обеспечить посредством запрещения прерываний.Чтобы избежать активного ожидания, будем блокировать исполнение потока в случае доступа к примитиву синхронизации, занятому другим потоком.
Слайд 5Очередь потоков
Для этого с каждым примитивом синхронизации свяжем очередь заблокированных
потоков, ждущих освобождения этого примитива синхронизации.
Слайд 6Спецификация очереди блокированных потоков
class ThreadQueue
{
Thread *tp;
// список потоков
public:
ThreadQueue(): tp(NULL) { }
~ThreadQueue() { . . .
} // здесь нетривиальноvoid enqueueThread(Thread& t);
bool dequeueThread();
};
Слайд 7void ThreadQueue::enqueueThread(Thread& t)
{
includeThreadToList(t);
t.suspendThread();
}
bool ThreadQueue:: dequeueThread()
{
Thread t;
if(!tp)
return false;
else
{
t = excludeThreadFromList();
t.resumeThread();
return true;
}
}
Слайд 9Схема реализации примитива синхронизации Lock
class Lock
{
bool free;
ThreadQueue tq; // очередь
потоков
public:
Lock(): free(true) { }
~Lock() { . . . }
void acquire()
; // закрываем замокvoid release(); // открываем замок
};
Слайд 10void Lock::acquire() // закрываем замок
{
disableInterrupt();
if (!free)
tq.enqueueThread(currentThread());
else
free = false;
enableInterrupt();
}
Слайд 11void Lock::release() // открываем замок
{
disableInterrupt();
if (!tq.dequeueThread())
free = true;
enableInterrupt();
}
Слайд 12Решение проблемы взаимного исключения для двух потоков при помощи примитива
синхронизации Lock
Для этого рассмотрим следующие потоки:
Lock lock;
void thread_1( ) void thread_2(
){ {
beforeCriticalSection_1(); beforeCriticalSection_2();
lock.acquire(); lock.acquire();
criticalSection_1(); criticalSection_2();
lock.release(); lock.release();
afterCriticalSection_1(); afterCriticalSection_2();
} }
Слайд 13Аналоги примитива Lock в Windows
В операционной системе Windows аналогами примитива
синхронизации Lock являются примитивы синхронизации CRITICAL_SECTION и Mutex.
Слайд 15Схема реализации примитива синхронизации Condition
class Condition
{
bool event;
ThreadQueue tq; // очередь потоков
public:
Condition
(): event(false) { }
~Condition () { . . . }
void
wait(); // ждем выполнения условияvoid signal(); // сигнализируем о выполнении условия
};
Слайд 16// ждем выполнения условия
void Condition::wait()
{
disableInterrupt();
if (event)
event = false;
else
tq.enqueueThread(currentThread());
enableInterrupt();
}
Слайд 17// сигнализируем о выполнении условия
void signal()
{
disableInterrupt();
if (!tq.dequeueThread())
event = true;
enableInterrupt();
}
Слайд 18Решение задачи условной синхронизации для двух потоков при помощи примитива
синхронизации Condition
Для этого рассмотрим следующие потоки.
Condition c; // начальное состояние
несигнальноеvoid thread_1( ) void thread_2( )
{ {
beforeCondition_1(); beforeCondition_2(); c.wait(); c.signal();
afterCodition_1(); afterCondition_2();
} }
Слайд 19Решение при помощи примитива синхронизации Condition проблемы взаимного исключения для
двух потоков
Для этого рассмотрим следующие потоки:
Condition c; // начальное состояние
несигнальноеc.signal(); // устанавливаем в сигнальное состояние
void thread_1( ) void thread_2( )
{ {
beforeCriticalSection_1(); beforeCriticalSection_2();
c.wait(); c.wait();
criticalSection_1(); criticalSection_2();
c.signal(); c.signal();
afterCriticalSection_1(); afterCriticalSection_2();
} }
Слайд 20Аналог примитива Condition в Windows
В операционной системе Windows аналогом примитива
синхронизации Condition является примитив синхронизации Event.
Слайд 22Определение семафора
Семафор – это неотрицательная целочисленная переменная, значение которой может
изменяться только при помощи атомарных операций.
Семафор считается свободным, если его
значение больше нуля, в противном случае семафор считается занятым.
Слайд 23Операции над семафором
Пусть s – семафор, тогда над ним можно
определить следующие атомарные операции:
P(s) // захватить семафор
{
если s >0
то
s = s – 1; // поток продолжает работуиначе
ждать освобождения s; // поток переходит в состояние ожидания
}
V(s) // освободить семафор
{
если потоки ждут освобождения s
то освободить один поток;
иначе
s = s + 1;
}
Слайд 24Из определения операций над семафором видно, что если поток выдает
операцию P и значение семафора больше нуля, то значение семафора
уменьшается на 1 и этот поток продолжает свою работу, в противном случае поток переходит в состояние ожидания до освобождения семафора другим потоком.Вывести из состояния ожидания поток, который ждет освобождения семафора, может только другой поток, который выдает операцию V над этим же семафором.
Слайд 25Определение семафора Дейкстры
Семафор с операциями P и V называется семафором
Дейкстры, голландского математика, который первым использовал семафоры для решения задач
синхронизации.
Слайд 26Сильный и слабый семафоры
Потоки, ждущие освобождения семафора, выстраиваются в очередь
к этому семафору.
Дисциплина обслуживания очереди зависит от конкретной реализации.
Очередь может
обслуживаться как по правилу FIFO, так и при помощи более сложных алгоритмов, учитывая приоритеты потоков.Если очередь семафора обслуживается по алгоритму FIFO, то семафор называется сильным, иначе - слабым.
Слайд 27Двоичный и считающий семафоры
Семафор, который может принимать только значения 0
или 1, называется двоичным или бинарным семафором.
Семафор, значение которого может
быть больше 1, обычно называют считающими семафором.
Слайд 28Решение проблемы взаимного исключения для двух потоков при помощи семафора
Semaphor s = 1; // семафор свободен
void
thread_1( ) void thread_2( ){ {
beforeCriticalSection_1(); beforeCriticalSection_2();
P(s); // захватить P(s); // захватить
criticalSection_1(); criticalSection_2();
V(s); // освободить V(s); // освободить
afterCriticalSection_1(); afterCriticalSection_2();
} }
Слайд 29Решение проблемы условной синхронизации для двух потоков при помощи семафора
Semaphor
s = 0; // семафор занят
void thread_1(
) void thread_2( ){ {
beforeEvent_1(); beforeEvent_2();
P(s); // wait V(s); // signal
afterEvent_1(); afterEvent_2();
} }
Слайд 31class Semaphore
{
int count;
// счетчик
ThreadQueue tq; // очередь потоков
public:
Semaphore(int& n): count(n) {}
~Semaphore()
{ . . . }void wait(); // закрыть семафор
void signal(); // открыть семафор
};
Схема реализации примитива синхронизации семафор
Слайд 32 void Semaphore::wait() // закрыть семафор
{
disableInterrupt();
if (count > 0)
--count;else
tq.enqueueThread(currentThread());
enableInterrupt();
}
Слайд 33void Semaphore::signal() // открыть семафор
{
disableInterrupt();
if (!tq.dequeueThread())
++count;
enableInterrupt();}
Слайд 35Объекты синхронизации
В операционных системах Windows объектами синхронизации называются объекты ядра,
которые могут находиться в одном из двух состояний:
сигнальном (signaled);
несигнальном (nonsignaled).
Слайд 36Классификация объектов синхронизации
Объекты синхронизации могут быть разбиты на три класса:
собственно
объекты синхронизации, которые служат только для решения проблемы синхронизации параллельных
потоков. К таким объектам синхронизации в Windows относятся:мьютекс (mutex);
событие (event);
семафор (semaphore);
ожидающий таймер (waitable timer);
объекты, которые переходят в сигнальное состояние по завершении своей работы или при получении некоторого сообщения
Например, потоки и процессы. Пока эти объекты выполняются, они находятся в несигнальном состоянии. Если выполнение этих объектов заканчивается, то они переходят в сигнальное состояние.
Слайд 37Функции ожидания
Функции ожидания в Windows это такие функции, которые используются
для блокировки исполнения потоков в зависимости от состояния объекта синхронизации,
который является параметром функции ожидания.При этом блокировка потоков выполняется следующим образом:
если объект синхронизации находится в несигнальном состоянии, то поток, вызвавший функцию ожидания, блокируется до перехода этого объекта синхронизации в сигнальное состояние;
если объект синхронизации находится в сигнальном состоянии, то поток, вызвавший функцию ожидания, продолжает свое исполнение, а объект синхронизации, как правило, переходит в несигнальное состояние.
Слайд 38Функции ожидания в Windows
WaitForSingleObject – ждет перехода в сигнальное состояние
одного объекта синхронизации;
WaitForMultipleObjects – ждет перехода в сигнальное состояние одного
или нескольких объектов из массива объектов синхронизации. 
Слайд 40Назначение объекта критическая секция
Для решения проблемы взаимного исключения для параллельных
потоков, выполняемых в контексте одного процесса, в операционной системе Windows
предназначены объекты типа CRITICAL_SECTION.Объект типа CRITICAL_SECTION не является объектом ядра операционной системы, так как предполагается его использование только в контексте одного процесса.
Это повышает скорость работы этого примитива синхронизации, так как не требуется обращаться к ядру операционной системы.
Слайд 41Функции для работы с объектами типа CRITICAL_SECTION
InitializeCriticalSection – инициализация объекта;
EnterCriticalSection
– вход в критическую секцию;
TryEnterCriticalSection – попытка входа в критическую
секцию;LeaveCriticalSection – выход из критической секции;
DeleteCriticalSection – завершение работы с объектом;
Слайд 43Назначение мьютексов
Для решения проблемы взаимного исключения для параллельных потоком, выполняющихся
в контексте разных процессов, в операционной системе Windows предназначен объект
ядра мьютекс (mutex).Мьютекс находится в сигнальном состоянии, если он не принадлежит ни одному потоку.
В противном случае мьютекс находится в несигнальном состоянии.
Одновременно мьютекс может принадлежать только одному потоку.
Слайд 44Функции для работы с мьютексами
CreateMutex – создание мьютекса;
OpenMutex – получение
доступа к существующему мьютексу;
ReleaseMutex – освобождение мьютекса (переход мьютекса в
сигнальное состояние);WaitForSingleObject или WaitForMultipleObjects – захват мьютекса (ожидание сигнального состояния мьютекса).
Слайд 46Назначение событий
В операционных системах Windows события описываются объектами ядра Event.
Объекты
типа Event предназначены для решения задачи условной синхронизации.
Слайд 47Типы событий
В Windows различают два типа событий:
события с ручным сбросом;
события
с автоматическим сбросом.
Слайд 48События с ручным сбросом
Событие с ручным сбросом можно перевести в
несигнальное состояние только посредством вызова функции ResetEvent.
Слайд 49События с автоматическим сбросом
Событие с автоматическим сбросом переходит в несигнальное
состояние как при помощи функции ResetEvent, так и при помощи
функций ожидания WaitForSingleObject или WaitForMultipleObjects.Если события с автоматическим сбросом ждут несколько потоков, используя функцию WaitForSingleObject, то из состояния ожидания освобождается только один из этих потоков.
Слайд 50Функции для работы с событиями
CreateEvent – создание события;
OpenEvent – получение
доступа к существующему событию;
SetEvent – перевод события в сигнальное состояние;
ResetEvent
– перевод события в несигнальное состояние;PulseEvent – освобождение нескольких потоков, ждущих сигнального состояния события с ручным сбросом;
WaitForSingleObject или WaitForMultipleObjects – ожидание наступления события (перехода события в сигнальное состояние).
Слайд 52Назначения семафоров
Семафоры в операционных системах Windows описываются объектами ядра Semaphore.
При
помощи семафоров может решаться как задача взаимного исключения, так и
задача условной синхронизации.Поэтому семафор часто называют универсальным примитивом синхронизации.
Слайд 53Состояния и значения семафора
Семафор находится в сигнальном состоянии, если его
значение больше нуля.
В противном случае семафор находится в несигнальном состоянии.
Слайд 54Функции для работы с семафорами
CreateSemaphore – создание семафора;
OpenSemaphore – получение
доступа к существующему семафору;
ReleaseSemaphore – увеличение значения семафора на положительное
число;WaitForSingleObject или WaitForMultipleObjects – ожидание перехода семафора в сигнальное состояние.
