Критические секции и состязания. Семафоры, Мьютексы. Задача о читателях и писателях. Предотвращение критических ситуаций и средства синхронизации процессов

Возникновение гонок (состязаний)

Два процесса хотят получить доступ к общей памяти в одно и тоже время

Если процессу требуется вывести на печать файл, он помещает имя файла в специальный каталог спулера.

Другой процесс, “демон печати”, периодически проверяет наличие файлов, которые нужно печатать, печатает файл и удаляет его имя из каталога.

Представим, что каталог спулера состоит из большого числа сегментов, нумерованных 0,1, 2…, в каждом из которых может храниться имя файла. Также есть две совместно используемые переменные: out, указывающая на следующий файл для печати, и in, указывающая на следующий свободный сегмент.

Эти две переменные можно хранить в одном файле, доступном для всех процессов. Пусть в данный момент времени сегменты с 0 по 3 пусты (файлы уже напечатаны), а сегменты 4-6 заняты (файлы ждут печати).

Более или менее одновременно процессы A и B решают поставить файл в очередь на печать.

Возможна следующая ситуация:

1. Процесс A считывает значение (7) переменной in и сохраняет его в локальной переменной next_free_slot. После этого происходит прерывание по таймеру, и процессор переключается на процесс B. Процесс B, в свою очередь, считывает значение переменной in и сохраняет его (опять 7) в своей локальной переменной next_free_slot.

2. Теперь оба процесса считают, что следующий свободный сегмент – седьмой.

3. Процесс B сохраняет в каталоге спулера имя файла и заменяет значение in на 8, затем продолжает заниматься своими задачами, не связанными с печатью.

4. Наконец управление переходит к процессу A, и он начинает с того места, на котором остановился. Он обращается к переменной next_free_slot, считывает ее значение и записывает в седьмой сегмент имя файла (удаляя значение, записанное процессом B).

5. В результате файл процесса B не напечатается.

Критические секции

Важным понятием синхронизации потоков для решения проблемы состязаний является понятие «критической секции» программы.

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

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

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

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

Условия исключения гонок

Два процесса не должны одновременно находиться в критической секции

В программе не должно быть предположений о скорости или количестве процессоров

Процесс вне критической секции не может блокировать другие процессы

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

Взаимное исключение с использованием критических секций

Семафоры

Дийкстра (Dijkstra) предложил использовать переменные, которые могут принимать целые неотрицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, получили название семафоров.

Семафор - неотрицательная целая переменная S >= 0, которая может изменяться и проверяться только посредством двух примитивов:

V(S): переменная S увеличивается на 1 единым неделимым действием. К переменной S нет доступа другим потокам во время выполнения этой операции.

P(S): уменьшение S на 1, если это возможно. Если S=0 и невозможно уменьшить S, оставаясь в области целых неотрицательных значений, то в этом случае поток, вызывающий операцию Р, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также являются неделимой операцией.

Иллюстрация работы семафора

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

Создание семафора

HANDLE CreateSemaphore(

LPSECURITY_ATTRIBUTE psa,

LONG lInitialCount,

LONG lMaximumCount,

LPCTRTR pszName);

HANDLE OpenSemaphore(

DWORD fdwAccess,

BOOL bInheritHandle,

LPCTSTR pszName);

Параметр lMaximumCount сообщает системе максимальное состояние семафора.

Управление семафором

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

BOOL ReleaseSemaphore(

HANDLE hSem,

LONG lReleaseCount,

PLONG plPreviousCount);

Если Wait- функция определяет, что счетчик текущего числа ресурсов равен 0 (семафор занят), система переводит вызывающий поток в состояние ожидания Когда другой поток увеличит значение этого счетчика, система вспомнит о ждущем потоке и снова начнет выделять ему процессорное время (а он, захватив ресурс, уменьшит значение счетчика на 1).

Поток увеличивает значение счетчика текущего числа ресурсов, вызывая функцию ReleaseSemaphore.

Она просто складывает величину lReleaseCount со значением счетчика текущего числа ресурсов. Обычно в параметре lReleaseCount передают 1.

Функция возвращает исходное значение счетчика ресурсов в *plPreviousCount.

Мьютексы

Иногда используется упрощенная версия семафора – мьютекс (mutex, mutual exclusion – взаимное исключение). Иногда называют еще двоичным семафором.

Мьютекс – переменная, которая может находиться в одном из двух состояний: блокированном или неблокированном.

Если процесс хочет войти в критическую секцию – он вызывает примитив блокировки мьютекса.

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

Использование мьютекса

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

Создание мьютекса

HANDLE CreateMutex(

LPSECURITY_ATTRIBUTES psa,

BOOL fInitialOwner,

LPCTSTR pszName);

HANDLE OpenMutex(

DWORD fdwAccess,

BOOL fInheritHandle,

LPCTSTR pszName);

Параметр fInitialOwner определяет начальное состояние мьютекса:

Если в нем передается FALSE (что обычно и бывает), объект-мьютекс не принадлежит ни одному из потоков и поэтому находится в свободном состоянии. При этом его идентификатор потока и счетчик рекурсии равны 0

Если же в нем передается TRUE, идентификатор потока, принадлежащий мьютексу, приравнивается идентификатору вызывающего потока, а счетчик рекурсии получает значение 1. Поскольку теперь идентификатор потока отличен от 0, мьютекс изначально находится в занятом состоянии.

Управление мьютексом

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

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

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

BOOL ReleaseMutex (HANDLE hMutex);

Задача о читателях и писателях

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

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

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

Введем два семафора: е – число пустых буферов, и f – число заполненных буферов, причем в исходном состоянии е =N, a f =0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом.

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

Критические секции и состязания. Семафоры, атомарные операции, CRITICAL_SECTION. Задача о читателях и писателях. Предотвращение критических ситуаций и средства синхронизации процессов

Возникновение гонок (состязаний)

Два процесса хотят получить доступ к общей памяти в одно и тоже время

Если процессу требуется вывести на печать файл, он помещает имя файла в специальный каталог спулера.

Другой процесс, “демон печати”, периодически проверяет наличие файлов, которые нужно печатать, печатает файл и удаляет его имя из каталога.

Представим, что каталог спулера состоит из большого числа сегментов, нумерованных 0,1, 2…, в каждом из которых может храниться имя файла. Также есть две совместно используемые переменные: out, указывающая на следующий файл для печати, и in, указывающая на следующий свободный сегмент.

Эти две переменные можно хранить в одном файле, доступном для всех процессов. Пусть в данный момент времени сегменты с 0 по 3 пусты (файлы уже напечатаны), а сегменты 4-6 заняты (файлы ждут печати).

Более или менее одновременно процессы A и B решают поставить файл в очередь на печать.

Возможна следующая ситуация:

1. Процесс A считывает значение (7) переменной in и сохраняет его в локальной переменной next_free_slot. После этого происходит прерывание по таймеру, и процессор переключается на процесс B. Процесс B, в свою очередь, считывает значение переменной in и сохраняет его (опять 7) в своей локальной переменной next_free_slot.

2. Теперь оба процесса считают, что следующий свободный сегмент – седьмой.

3. Процесс B сохраняет в каталоге спулера имя файла и заменяет значение in на 8, затем продолжает заниматься своими задачами, не связанными с печатью.

4. Наконец управление переходит к процессу A, и он начинает с того места, на котором остановился. Он обращается к переменной next_free_slot, считывает ее значение и записывает в седьмой сегмент имя файла (удаляя значение, записанное процессом B).

5. В результате файл процесса B не напечатается.

Критические секции

Важным понятием синхронизации потоков для решения проблемы состязаний является понятие «критической секции» программы.

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

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

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

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

Условия исключения гонок

Два процесса не должны одновременно находиться в критической секции

В программе не должно быть предположений о скорости или количестве процессоров

Процесс вне критической секции не может блокировать другие процессы

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

Взаимное исключение с использованием критических секций

Семафоры

Дийкстра (Dijkstra) предложил использовать переменные, которые могут принимать целые неотрицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, получили название семафоров.

Семафор - неотрицательная целая переменная S >= 0, которая может изменяться и проверяться только посредством двух примитивов:

V(S): переменная S увеличивается на 1 единым неделимым действием. К переменной S нет доступа другим потокам во время выполнения этой операции.

P(S): уменьшение S на 1, если это возможно. Если S=0 и невозможно уменьшить S, оставаясь в области целых неотрицательных значений, то в этом случае поток, вызывающий операцию Р, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также являются неделимой операцией.

Иллюстрация работы семафора

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

Создание семафора

HANDLE CreateSemaphore(

LPSECURITY_ATTRIBUTE psa,

LONG lInitialCount,

LONG lMaximumCount,

LPCTRTR pszName);

HANDLE OpenSemaphore(

DWORD fdwAccess,

BOOL bInheritHandle,

LPCTSTR pszName);

Параметр lMaximumCount сообщает системе максимальное состояние семафора.

Управление семафором

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

BOOL ReleaseSemaphore(

HANDLE hSem,

LONG lReleaseCount,

PLONG plPreviousCount);

Если Wait- функция определяет, что счетчик текущего числа ресурсов равен 0 (семафор занят), система переводит вызывающий поток в состояние ожидания Когда другой поток увеличит значение этого счетчика, система вспомнит о ждущем потоке и снова начнет выделять ему процессорное время (а он, захватив ресурс, уменьшит значение счетчика на 1).

Поток увеличивает значение счетчика текущего числа ресурсов, вызывая функцию ReleaseSemaphore.

Она просто складывает величину lReleaseCount со значением счетчика текущего числа ресурсов. Обычно в параметре lReleaseCount передают 1.

Функция возвращает исходное значение счетчика ресурсов в *plPreviousCount.

Атомы это очень простой и доступный путь IPC. Идея состоит в том, что процесс может поместить строку в таблицу атомов и эта строка будет видна другим процессам. Когда процесс помещает строку в таблицу атомов, он получает 32-х битное значение (атом), и это значение используется для доступа к строке. Система не различает регистр строки.

Набор атомов собирается в таблицу (atom table). Система обеспечивает несколько таблиц атомов для разных задач. По типу доступа их два типа:

Локальные (доступны только из приложения)

Глобальные (доступны из всех приложений)

Функции WIN 32 API для атомов

GlobalAddAtom

GlobalGetAtomName

GlobalFindAtom

GlobalDeleteAtom

Сообщение WM_COPYDATA

Отправитель:

COPYDATASTRUCT cds;

cds.cbData = (DWORD) nSize;

cds.lpData = (PVOID) pBuffer;

SendMessage (hWndTarget, WM_COPYDATA, (WPARAM) hWnd, (LPARAM) &cds);

Получатель:

PCOPYDATASTRUCT pcds = (PCOPYDATASTRUCT) lParam;

PBYTE pBuffer = (PBYTE) pcds -> lpData;

Критические секции

В составе API ОС Windows имеются специальные и эффективные функции для организации входа в критическую секцию и выхода из нее потоков одного процесса в режиме пользователя.

Они называются EnterCriticalSection и LeaveCriticalSection и имеют в качестве параметра предварительно проинициализированную структуру типа CRITICAL_SECTION.

Примерная схема программы может выглядеть следующим образом.

CRITICAL_SECTION cs;

DWORD WINAPI SecondThread()

{

InitializeCriticalSection(&cs); EnterCriticalSection(&cs);

//…критический участок кода LeaveCriticalSection(&cs);

}

Функции EnterCriticalSection и LeaveCriticalSection реализованы на основе атомарных Interlocked-функций.

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

Задача о читателях и писателях

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

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

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

Введем два семафора: е – число пустых буферов, и f – число заполненных буферов, причем в исходном состоянии е =N, a f =0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом.

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