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

Синхронизация Механизм операционной системы, обеспечивающий согласованное во времени выполнение нескольких процессов и/или потоков

Типы процессов Синхронные – действия процессов во времени строго согласованы; действия любого синхронного потока строго обусловлены действиями других синхронных с ним потоков Несинхронные – процессы, выполняющиеся абсолютно независимо друг от друга Асинхронные – независимые процессы, действия которых необходимо синхронизировать на некоторых этапах их выполнения

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

Пример несинхронного обращения к критическому ресурсу Переменная х – критический ресурс Процессы Р1 и Р2 выполняются строго параллельно и не синхронно Каждый процесс должен добавить к значению переменной х единицу В результате работы процессов значение х должно быть увеличено на 2, но по факту оно увеличится только на 1 х = 8 Р1Р2 tmp = x tmp++ x = tmp tmp = x tmp++ x = tmp х = 10 tmp=8 tmp=9 x=9

Взаимоисключение (mutual exclusion) Механизм операционной системы, позволяющий реализовать синхронный вход процессов (потоков) в свои критические секции

Пример обращения к критическому ресурсу с использованием механизма взаимоисключения Переменная х – критический ресурс Процессы Р1 и Р2 выполняются асинхронно Перед обращением к критическому ресурсу процессы выполняют примитив взаимоисключения start_exclusion По завершению критической секции выполняется примитив end_exclusion Каждый процесс должен добавить к значению переменной х единицу х = 8 Р1Р2 start_exclusion tmp = x tmp++ x = tmp end_exclusionstart_exclusion tmp = x tmp++ x = tmp end_exclusion х = 10 tmp=8 tmp=9 x=9 tmp=9 tmp=10 x=10 процесс Р2 ожидает завершения критической секции процесса Р1

Правила по работе с критическими секциями Никакие два процесса не могут одновременно войти в свои критические секции В каждый момент времени только один процесс может находится в своей критической секции Никакой процесс не может находиться в своей критической секции бесконечно Никакой процесс не должен бесконечно ждать входа в свою критическую секцию Операции входа в критическую секцию должны выполняться в ОС как атомарные, чтобы исключить возможность параллельного выполнения этих операций Разработка приложений с критическими секция не должна вестись с учетом особенностей дисциплины планирования, операционной системы и/или вычислительной системы Вся ответственность за корректную/некорректную работу приложений с взаимоисключениями лежит на программисте

Примитивы и механизмы синхронизации Примитивы взаимоисключения (объект CRITICAL_SECTION в ОС Windows) Примитивы ожидания Семафоры Mutex События и условные (сигнальные) переменные Средства языков параллельного программирования (мониторы и механизм рандеву языка ADA)

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

Использование CRITICAL_SECTION Определить переменную типа CRITICAL_SECTION как глобальную переменную процесса CRITICAL_SECTION cs ; Перед запуском асинхронных потоков инициализировать критическую секцию InitializeCriticalSection(&cs); После завершения асинхронных потоков удалить критическую секцию DeleteCriticalSection(&cs); В потоке, перед входом в критическую секцию, проверить, свободна ли она, и заблокировать вход в критическую секцию для других потоков EnterCriticalSection(&cs); После завершения критической секции разрешить вход другим потокам LeveCriticalSection(&cs);

Пример использования критических секций Функция main() запускает n потоков, каждый из которых должен увеличить значение глобальной переменной x на 1 Для синхронизации потоков используется глобальный объект CRITICAL_SECTION Каждый из n потоков выполняет функцию thread_func() Полный листинг находится в файле critical_section.cpp

Примитивы ожидания в ОС Windows Ожидание завершения одного потока WaitForSingleObject(дескриптор_потока, время_ожидания) Ожидание завершения нескольких потоков WaitForMultipleObjects( количество_потоков, массив_дескрипторов,дожидаться_всех (true/false), время_ожидания)

Объекты Mutex (mutual exclusion) Объект ядра операционной системы, обеспечивающий взаимоисключения потоков В ОС Linux mutex не является объектом ядра ОС, что не позволяет ему синхронизировать работу процессов и потоков в разных процессах Принимает два значения Открыт – поток может войти в свою критическую секцию Закрыт – поток не может войти в критическую секцию Если mutex закрыт, то поток пытающийся войти в критическую секцию блокируется

Использование mutex в Windows Создание mutex CreateMutex(параметры_безопасности, собственность_потока, имя) Поименованный mutex может использоваться для синхронизации процессов Открытие mutex OpenMutex(параметры_безопасности, собственность_потока, имя) Ожидание и захват mutex WaitForSingleObject(дескриптор_mutex, время_ожидания) Освобождение mutex ReleaseMutex(дескриптор_mutex)

Использование mutex в Linux Mutex в Linux – это объект для синхронизации потоков в рамках одного процесса Описание mutex pthread_mutex_t mutex; Инициализация mutex pthread_mutex_init (&mutex, NULL); Перед входом в критическую секцию поток должен попытаться захватить mutex. Если это не удается, то поток блокируется до освобождения mutex pthread_mutex_lock(&mutex); При выходе из критической секции поток должен освободить mutex pthread_mutex_unlock(&mutex);

Семафоры Семафоры – это объекты синхронизации, которые могут находиться в двух состояниях – открыт и закрыт. Бинарные семафоры только открывают или закрывают вход в критическую секцию. По своему поведению похожи на mutex. Считающие семафоры позволяют определить, сколько процессов могут одновременно войти в свою критическую секцию Если счетчик = 0, то вход в критическую секцию не возможен Если счетчик > 0, то процесс может войти в свою критическую секцию В отличии от mutex, семафоры реализуют активное ожидание – процесс на семафоре не блокируется, а продолжает проверять, не открылся ли семафор

Операции с семафорами Операция понижения Используется процессами при входе в критическую секцию If (semaphore > 0) then dec(semaphore) else while (semaphore = 0) do; Операция повышения Используется процессами при выходе из критической секции Inc(semaphore)

Использование семафоров в Windows Создание семафора CreateSemaphore(параметры_безопасности, начальное_значение, максимальное_значение, имя) При входе в критическую секцию поток должен захватить семафор или войти в стадию активного ожидания (операция понижения) WaitForSingleObject(дескриптор_семафора, время ожидания) При выходе из критической секции поток должен повысить значение счетчика семафора ReleaseSemaphore(дескриптор_семафора, добавляемое_значение, место_для_предыдущего_значения)

Использование семафоров для потоков в Linux Для работы с семафорами потоков необходимо подключить модуль semaphore.h #include Описание переменной семафора sem_t semaphore; Инициализация семафора sem_init(&semaphore,0,начальное_значение); Перед входом в критическую секцию необходимо дождаться освобождения семафора и понизить значение его счетчика sem_wait(&semaphore); По окончании критической секции необходимо повысить значение счетчика семафора sem_post(&semaphore);

Использование семафоров процессов в UNIX/Linux Для работы с семафорами процессов необходимо подключить следующие модули #include Описать структуру, используемую для инициализации семафоров union semun { int val; struct semid_de * buf ; unsigned short int * array; struct seminfo * __buf; }; Описать целую переменную для хранения идентификатора группы семафоров int sem_id;

Использование семафоров процессов в UNIX/Linux Создать группу семафоров sem_id = semget(ключ_группы, количество_семафоров, флаги_создания); Если указан ключ существующей группы, то будет возвращен ее идентификатор. В этом случае второй параметр может быть равен нулю. Инициализировать семафоры созданной группы (задать начальные значения) Подготовить структуру типа union semun unsigned short int start_values[количество_семафоров]; Каждому элементу массива start_values присвоить начальное значение конкретного семафора union semun sem_values; sem_values.array = start_values; semctl(sem_id,0,SETALL,sem_values);

Использование семафоров процессов в UNIX/Linux Изменение значений семафоров Создать массив элементов типа struct sembuf struct sembuf oper[количество_семафоров]; Заполнить каждый элемент массива oper значениями операций: oper[номер_семафора].sem_num = номер_семафора; oper[номер_семафора].sem_op = целое_значение; Если целое_значение < 0, то значение семафора должно уменьшиться (операция понижения). Если после предполагаемого уменьшения значение семафора станет меньше нуля, то процесс блокируется и ждет, пока уменьшение не станет приводить к получению отрицательного результата Если целое_значение = 0, то семафор не меняется Если целое_значеие > 0, то семафор увеличивается (операция повышения) oper[номер_семафора].sem_flg = 0; Выполнить функцию semop semop(sem_id, oper, количество_семафоров);

Использование семафоров процессов в UNIX/Linux В конце работы с семафорами их необходимо уничтожить, т.к. они являются объектами ядра системы и могут существовать независимо от того, существует создавший их процесс или нет semctl(sem_id, количество_семафоров, IPC_RMID, NULL);

Задача «Читатели-писатели» В системе имеется n писателей, которые производят некоторые данные В системе имеется m читателей, которые потребляют произведенные данные Обмен данными между читателями и писателями ведется через общий буфер Писатели могут писать в буфер, только если в буфере есть пустые ячейки Читатели могут читать из буфера, только если в буфере есть какие-либо данные. Прочитав данные из буфера, читатель освобождает одну ячейку

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

Средства синхронизации в задаче «Читатели – писатели» Mutex (или простой бинарный семафор) для блокирования одновременного обращения нескольких процессов (потоков) к буферу Семафор empty – считающий семафор, максимальное значение которого равно количеству ячеек в буфере. Если значение семафора free = 0, то в буфере нет свободных ячеек, и все писатели должны быть заблокированы. Создается с начальным значением равным n. Семафор full – считающий семафор, максимальное значение которого равно количеству ячеек в буфере. Если значение семафора full = 0, то в буфере нет данных, и все читатели должны быть заблокированы. Создается с начальным значением равным 0.

События в Windows События – средства условной синхронизации потоков и процессов Для создания события необходимо выполнить функцию CreateEvent(атрибуты_безопасности, режим_переключения, начальное_значение,имя); Для сообщения о том, что событие произошло, необходимо выполнить функцию SetEvent(дескриптор_события); Поток, ожидающий наступления события, должен выполнить функцию WaitForSingleObject(дескриптор_события, время_ожидания);

Режимы переключения события Автоматический Второй параметр функции CreateEvent равен false Событие переходит в состояние «не произошло» сразу после того, как хотя бы один поток дождался этого события на функции WaitForSingleObject Сразу после того, как один поток прошел ожидание события, другой поток так же может выйти из состояния ожидания Ручной Второй параметр функции CreateEvent равен true Чтобы перевести событие в состояние «не произошло» поток должен выполнить функцию ResetEvent(дескриптор) Только один поток может войти в критическую секцию после завершения ожидания наступления события на функции WaitForSingleObject

Задача «Производитель – потребитель» Производитель – поток, который генерирует данные Потребитель – поток, которые использует данные Производитель может сгенерировать новые данные только после того, как потребитель обработал предыдущую порцию Потребитель может обрабатывать каждую порцию данных только один раз, поэтому вынужден ожидать, когда производитель сгенерирует следующий набор данных

Принципиальная реализация задачи «Производитель – потребитель» Производитель Дождаться момента, когда потребитель обработает данные Захватить буфер Сгенерировать новые данные Освободить данные Сообщить о том, что новые данные сгенерированы Потребитель Дождаться момента, когда будут сгенерированы новые данные Захватить буфер Обработать данные Освободить буфер Сообщить о том, что данные обработаны, и потребитель ждет новых данных

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

Условные (сигнальные) переменные в Linux Условная (сигнальная) переменная – это средство условной синхронизации потоков в Linux Условная переменная сообщает потоку о том, что произошло событие, которого поток ожидал Условная переменная всегда связана с некоторым mutex, т.к. сама является критической переменной

Использование условных (сигнальных) переменных Описать переменную сигнальной переменной pthread_cond_t cond; Инициализировать сигнальную переменную pthread_cond_init(&cond,NULL); Поток ожидает наступления события при помощи функции pthread_cond_wait(&cond,указатель_на_mutex); Перед проверкой наступления события mutex, с которым связана переменная, уже должен быть захвачен функцией pthread_mutex_lock(указатель_на_mutex) Сигнализировать об изменении переменной поток может функцией pthread_cond_signal(&cond); При этом разблокируется один из потоков, ожидающих наступления события

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

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

Схема рандеву Вызывающая задачаОбслуживающая задача Собственные действия вызывающей задачи Собственные действия обслуживающей задачи Блок вызова (call) Блок приема (accept) Рандеву Собственные действия вызывающей задачи Собственные действия обслуживающей задачи

Использование рандеву – получение параметров, отложенным вычислением Вызывающая задача – процесс, который выполняет обработку случайным образом сгенерированного массива Обслуживающая задача – процесс, генерирующий массив по запросу Массив – критический ресурс, доступ к которому регулируется mutex Когда вызывающая задача достигает блока вызова, она генерирует событие call Когда обслуживающая задача достигает блока приема она генерирует событие accept

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

Примеры программ critical_section.cppИспользование критических секций для синхронизации потоков в Windows mutex_win.cppИспользование mutex в Windows bin_semaphore_win.cppИспользование бинарных семафоров в Windows rw_win.cppРеализация задачи «читатели – писатели» для Windows (mutex и считающие семафоры) pc_win.cppРеализация задачи «производитель – потребитель» для Windows (mutex и события) rendezvous_win.cppЭмуляция механизма рандеву (mutex и события)

Примеры программ mutex_linux.cppИспользование mutex в Linux bin_sem_linux.cppИспользование семафоров для потоков в Linux bin_sem_unix.cppИспользование бинарных семафоров в стиле UNIX rw_linux.cppРеализация задачи «читатель- писатель» для Linux (mutex и считающие семафоры для потоков)