5. Примитивы синхронизации

Вопрос№26 5.1. Блокировка потоков

Примитив синхронизации – это программное или аппаратное средство (механизм, инструмент) высокого уровня для решения задач синхронизации потоков. Примитивы синхронизации обычно реализованы как объекты ядра ОС.

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

Спецификация очереди блокированных потков

class ThreadQueue

{

Thread* tp; //список потоков

public:

ThreadQueue():tp(NULL){}

~ThreadQueue(){...}//здесь нетривиально

void unqueueThread(Thread&t);

bool dequeueThread();

};

void ThreadQueue::enqueueThread(Thread&t)

{ includeThreadToList(t);

t.suspendThread();

}

bool ThreadQueue::dequeueThread()

{

Thread t;

if (!tp)

return false;

else

{

t = excludeThreadFromQueue();

t.resumeThread();

return true;

}

}

Вопрос№27 5.2. Примитив синхронизации Lock (замок)

Схема реализации примитива синхронизации Lock

class Lock

{

bool free;

ThreadQueue tq; //очередь потоков

public:

Lock():free(true){}

~Lock(){…}

void acquire(); //закрываем замок

void release(); //открываем замок

};

void Lock::acquire() //закрываем замок

{

disableInterrupt();

if (!free)

tq.enqueueThread(currentThread());

else

free = false;

enableInterrupt();

}

void Lock::release() //открываем замок

{

disableInterrupt();

if (!tq.dequeueThread())

free = true;

enableInterrupt();

}

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

Lock lock;

void thread_1()

{

…

lock.acquire():

if (n%2==0)

n=a;

else

n=b;

lock.release();

…

}

void thread_2()

{

…

lock.acquire();

++n;

lock.release();

…

}

В ОС Windows аналогами примитива синхронизации Lock являются примитивы синхронизации CRITICAL_SECTION и Mutex.

Вопрос№28 5.3. Примитив синхронизации Condition (условие)

Схема реализации примитива синхронизации Condition

class Condition

{

bool event;

ThreadQueue tq; //очередь потоков

public:

Condition():event(false){}

~Condition(){…}

void wait(); //ждем выполнения условия

void signal(); //сигнализируем о выполнении условия

};

//ждем выполнения условия

void Condition::wait()

{

disableInterrupt();

if (event)

event = false;

else

tq.enqueueThread(currentThread());

enableInterrupt();

}

//сигнализируем о выполнении условия

void signal()

{

disableInterrupt();

if (!tq.dequeueThread())

event = true;

enableInterrupt();

}

Покажем, как с помощью примитива синхронизации Condition можно решить проблему условной синхронизации. Для этого рассмотрим следующие потоки.

Condition c; //начальное состояние несигнальное

void thread_1()

{

…

c.wait();

if (n%2==0)

n=a;

else

n=b;

…

}

void thread_2()

{

…

n++;

c.signal();

…

}

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

Condition c; //начальное состояние несигнальное

с.signal(); //устанавливаем в сигнальное состояние

void thread_1()

{

…

c.wait();

if (n%2==0)

n=a;

else

n=b;

…

}

void thread_2()

{

…

с.wait();

n++;

c.signal();

…

}

В OС Windows аналогом примитива синхронизации Сondition является примитив синхронизации Event.

Вопрос№29 5.4. Семафоры Дейкстры

Cемафор – это неотрицательная целочисленная переменная, значение которой может изменяться только при помощи атомарных операций.

Семафор считается свободным, если его значение больше нуля, в противном случае семафор считаетсязанятым.

Пусть s – семафор, тогда над ним можно определить следующие атомарные операции:

P(s) //захватить семафор

{

если s>0

то s = s-1; //поток продолжает работу

иначе

ждать освобождения s; //поток переходит в состояние ожидания

}

V(s) //освободить семафор

{

если потоки ждут освобождения s

то освободить один поток

иначе s = s+1;

}

Cемафор с операциями P и V называется семафором Дейкстры, голландского математика, который первым использовал семафоры для решения задач синхронизации.

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

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

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

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

Семафор, значение которого может быть больше 1, обычно называют считающим семофором.

Решение проблемы взаимного исключения с помощью семафора

Semaphor s=1; //семафор свободен

void thread_1()

{

…

P(s);

if (n%2==0)

n=a;

else

n=b;

V(s);

…

}

void thread_2()

{

…

P(s);

n++;

V(s);

…

}

Решение проблемы условной синхронизации с помощью семафора

Semaphor s=0; //семафор свободен

void thread_1()

{

…

P(s);

if (n%2==0)

n=a;

else

n=b;

…

}

void thread_2()

{

...

n++;

V(s);

…

}

Вопрос№30 5.5. Примитив синхронизации Semaphore (семафор)

Схема реализации примитива синхронизации семафор

class Semaphore

{

int count; //счетчик

ThreadQueue tq; // очередь потоков

public:

Semaphore(int&n):count(n){}

~Semaphore(){…}

void wait(); //закрыть семафор

void signal(); //открыть семафор

}

void Semaphore::wait() //закрыть семафор

{

disableInterrupt();

if (count>0)

--count;

else

tq.enqueueThread(currentThread());

enableInterrupt();

}

void Semaphore::signal() //открыть семафор

{

disableInterrupt();

if (!tq.dequeueThread())

++count;

enableInterrupt();

}

Вопрос№31 5.6. Объекты синхронизации и функции ожидания в Windows

Объекты синхронизации

В ОС Windows объектами синхронизации называются объекты ядра, которые могут находиться в одном из двух состояний:

- сигнальном (signaled);

- несигнальном (nonsignaled).

Объекты синхронизации могут быть разбиты на 3 класса:

- собственно объекты синхронизации, которые служат только для решения проблемы синхронизации параллельных потоков. К таким объектам синхронизации в Windows относятся:

- мьютекс (mutex);

- событие (event);

- семафор (semaphore);

- ожидающий таймер (waitable timer);

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

Функции ожидания

Функции ожидания в Windows это такие функции, которые используются для блокировки исполнения потоков в зависимости от состояния объекта синхронизации, который является параметром функции ожидания. При этом блокировка потоков выполняется следующим образом:

- если объект синхронизации находится в несигнальном состоянии, то поток, вызвавший функцию ожидания, блокируется до перехода этого объкта синхронизации в сигнальное состояние;

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

Функции ожидания в Windows:

- WaitForSingleObject- ждет перехода в сигнальное состояние одного объекта синхронизации;

- WaitForMultipleObjects – ждет перехода в сигнальное состояние одного или нескольких объектов из массива объектов синхронизации

Вопрос№32 5.7. Критические секции в Windows

Для решения проблемы взаимного исключения для параллельных потоков, выполняемых в контексте одного процесса, в ОС Windows предназначены объекты типа CRITICAL_SECTION. Объект типа CRITICAL_SECTION не является объектом ядра ОС, так как предполагается его использование только в контексте одного процесса. Это повышает скорость работы этого примитива синронизации, так как не требуется обращаться к ядру ОС для доступа к памяти другого процесса.

Для работы с объектами типа CRITICAL_SECTION используются следующие функции:

- InitializeCriticalSection – инициализация объекта;

- EnterCriticalSection – вход в критическую секцию;

- TryEnterCriticalSection – попытка входа в критическую секцию;

- LeaveCriticalSection – выход из критической секции;

- DeleteCriticalSection – завершение работы с объектом

Вопрос№33 5.8. Мьютексы в Windows

Для решения проблемы взаимного исключения для параллельных потоков, выполняющихся в контексте разных процессов, в ОС Windows предназначен объект ядра мьютекс (mutex).

Мьютекс находится в сигнальном состоянии, если он не принадлежит ни одному потоку. В противном случае мьютекс находится в несигнальном состоянии. Одновременно мьютекс может принадлежать только одному потоку.

Для работы с мьютеками используются следующие функции:

- CreateMutex – создание мьютекса;

- OpenMutex – получение доступа к существующему мьютексу;

- ReleaseMutex – освобождение мьютекса (переход мьютекса в сигнальное состояние);

- WaitForSingleObject или

- WaitForMultipleObjects – захват мьютекса (ожидание сигнального состояния мьютекса).

Вопрос№34 5.9. События в Windows

В ОС Windows события описываются объектами ядра Event. При этом различают два типа событий:

- события с ручным сбросом;

- события с автоматическим сбросом.

Что лучше: +2 или -2?

Событие с ручным сбросом можно перевести в несигнальное состояние только посредством вызова функции ResetEvent. Событие с автоматическим сбросом переходит в несигнальное состояние как при помощи функции ResetEvent, так и при помощи функций ожидания WaitForSingleObject и WaitForMultipleObjects. Если события с автоматическим сбросом ждут несколько потоков, используя функцию WaitForSingleObject, то из состояния ожидания освобождается только один из этих потоков.

Для работы с событиями используются следующие функции:

- CreateEvent – создания события;

- OpenEvent – получение доступа к существующему событию;

- SetEvent – перевод события в сигнальное состояние;

- ResetEvent – перевод события в несигнальное состояние;

- PulseEvent – освобождение нескольких потоков, ждущих сигнального состояния события с ручным сбросом;

- WaitForSingleObject или WaitForMultipleObjects – ожидание наступления события (перехода события в сигнальное состояние)

Вопрос№35 5.10. Семафоры в Windows

Семафоры в ОС Windows описываются объектами ядра Semaphore. Семафор находится в сигнальном состоянии, если его значение больше нуля. В противном случае семафор находится в несигнальном состоянии.

Для работы с семафорами используются следующие функции:

- CreateSemaphore – создание семафора;

- OpenSemaphore – получение доступа к существующему семафору;

- ReleaseSemaphore – увеличение значения семафора на положительное число;

- WaitForSingleObject или WaitForMultipleObjects – ожидание перехода семафора в сигнальное состояние.