Меню

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



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

Процессом (process) называется экземпляр программы, загруженной в память. Этот экземпляр может создавать нити (thread), которые представляют собой последовательность инструкций на выполнение. Важно понимать, что выполняются не процессы, а именно нити.

Причем любой процесс имеет хотя бы одну нить. Эта нить называется главной (основной) нитью приложения.

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

В зависимости от ситуации нити могут находиться в трех состояниях. Во-первых, нить может выполняться, когда ей выделено процессорное время, т.е. она может находиться в состоянии активности. Во-вторых, она может быть неактивной и ожидать выделения процессора, т.е. быть в состоянии готовности. И есть еще третье, тоже очень важное состояние — состояние блокировки. Когда нить заблокирована, ей вообще не выделяется время. Обычно блокировка ставится на время ожидания какого-либо события. При возникновении этого события нить автоматически переводится из состояния блокировки в состояние готовности. Например, если одна нить выполняет вычисления, а другая должна ждать результатов, чтобы сохранить их на диск. Вторая могла бы использовать цикл типа «while( !isCalcFinished ) continue;», но легко убедиться на практике, что во время выполнения этого цикла процессор занят на 100 % (это называется активным ожиданием). Таких вот циклов следует по возможности избегать, в чем оказывает неоценимую помощь механизм блокировки. Вторая нить может заблокировать себя до тех пор, пока первая не установит событие, сигнализирующее о том, что чтение окончено.

Синхронизация нитей в ОС Windows

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

Все нити, принадлежащие одному процессу, разделяют некоторые общие ресурсы — такие, как адресное пространство оперативной памяти или открытые файлы. Эти ресурсы принадлежат всему процессу, а значит, и каждой его нити. Следовательно, каждая нить может работать с этими ресурсами без каких-либо ограничений. Но. Если одна нить еще не закончила работать с каким-либо общим ресурсом, а система переключилась на другую нить, использующую этот же ресурс, то результат работы этих нитей может чрезвычайно сильно отличаться от задуманного. Такие конфликты могут возникнуть и между нитями, принадлежащими различным процессам. Всегда, когда две или более нитей используют какой-либо общий ресурс, возникает эта проблема.

Пример. Несинхронизированная работа нитей: если временно приостановить выполнение нити вывода на экран (пауза), фоновая нить заполнения массива будет продолжать работать.

Именно поэтому необходим механизм, позволяющий потокам согласовывать свою работу с общими ресурсами. Этот механизм получил название механизма синхронизации нитей (thread synchronization).

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

Объектов синхронизации существует несколько, самые важные из них — это взаимоисключение (mutex), критическая секция (critical section), событие (event) и семафор (semaphore). Каждый из этих объектов реализует свой способ синхронизации. Также в качестве объектов синхронизации могут использоваться сами процессы и нити (когда одна нить ждет завершения другой нити или процесса); а также файлы, коммуникационные устройства, консольный ввод и уведомления об изменении.

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

Работа с объектами синхронизации

Чтобы создать тот или иной объект синхронизации, производится вызов специальной функции WinAPI типа Create. (напр. CreateMutex). Этот вызов возвращает дескриптор объекта (HANDLE), который может использоваться всеми нитями, принадлежащими данному процессу. Есть возможность получить доступ к объекту синхронизации из другого процесса — либо унаследовав дескриптор этого объекта, либо, что предпочтительнее, воспользовавшись вызовом функции открытия объекта (Open. ). После этого вызова процесс получит дескриптор, который в дальнейшем можно использовать для работы с объектом. Объекту, если только он не предназначен для использования внутри одного процесса, обязательно присваивается имя. Имена всех объектов должны быть различны (даже если они разного типа). Нельзя, например, создать событие и семафор с одним и тем же именем.

Читайте также:  Как синхронизировать яндекс карты с iphone

По имеющемуся дескриптору объекта можно определить его текущее состояние. Это делается с помощью т.н. ожидающих функций. Чаще всего используется функция WaitForSingleObject. Эта функция принимает два параметра, первый из которых — дескриптор объекта, второй — время ожидания в мсек. Функция возвращает WAIT_OBJECT_0, если объект находится в сигнальном состоянии, WAIT_TIMEOUT — если истекло время ожидания, и WAIT_ABANDONED, если объект-взаимоисключение не был освобожден до того, как владеющая им нить завершилась. Если время ожидания указано равным нулю, функция возвращает результат немедленно, в противном случае она ждет в течение указанного промежутка времени. В случае, если состояние объекта станет сигнальным до истечения этого времени, функция вернет WAIT_OBJECT_0, в противном случае функция вернет WAIT_TIMEOUT. Если в качестве времени указана символическая константа INFINITE, то функция будет ждать неограниченно долго, пока состояние объекта не станет сигнальным.

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

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

Объект-критическая секция помогает программисту выделить участок кода, где нить получает доступ к разделяемому ресурсу, и предотвратить одновременное использование ресурса. Перед использованием ресурса нить входит в критическую секцию (вызывает функцию EnterCriticalSection). Если после этого какая-либо другая нить попытается войти в ту же самую критическую секцию, ее выполнение приостановится, пока первая нить не покинет секцию с помощью вызова LeaveCriticalSection. Используется только для нитей одного процесса. Порядок входа в критическую секцию не определен.

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

Пример. Синхронизация нитей с помощью критических секций.

Взаимоисключения

Объекты-взаимоисключения (мьютексы, mutex — от MUTual EXclusion) позволяют координировать взаимное исключение доступа к разделяемому ресурсу. Сигнальное состояние объекта (т.е. состояние «установлен») соответствует моменту времени, когда объект не принадлежит ни одной нити и его можно «захватить». И наоборот, состояние «сброшен» (не сигнальное) соответствует моменту, когда какая-либо нить уже владеет этим объектом. Доступ к объекту разрешается, когда нить, владеющая объектом, освободит его.

Две (или более) нити могут создать мьютекс с одним и тем же именем, вызвав функцию CreateMutex. Первая нить действительно создает мьютекс, а следующие — получают дескриптор уже существующего объекта. Это дает возможность нескольким нитям получить дескриптор одного и того же мьютекса, освобождая программиста от необходимости заботиться о том, кто в действительности создает мьютекс. Если используется такой подход, желательно установить флаг bInitialOwner в FALSE, иначе возникнут определенные трудности при определении действительного создателя мьютекса.

Несколько нитей могут получить дескриптор одного и того же мьютекса, что делает возможным взаимодействие между процессами. Можно использовать следующие механизмы такого подхода:

  • Дочерний процесс, созданный при помощи функции CreateProcess может наследовать дескриптор мьютекса в случае, если при создании мьютекса функцией CreateMutex был указан параметр lpMutexAttributes.
  • Нить может получить дубликат существующего мьютекса с помощью функции DuplicateHandle.
  • Нить может указать имя существующего мьютекса при вызове функций OpenMutex или CreateMutex.

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

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

Пример. Синхронизация нитей с помощью мьютексов.

События

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

Функция CreateEvent создает объект-событие, SetEvent — устанавливает событие в сигнальное состояние, ResetEvent — сбрасывает событие. Функция PulseEvent устанавливает событие, а после возобновления ожидающих это событие нитей (всех при ручном сбросе и только одной при автоматическом), сбрасывает его. Если ожидающих нитей нет, PulseEvent просто сбрасывает событие.

Пример. Синхронизация нитей с помощью событий.

Семафоры

Объект-семафор — это фактически объект-взаимоисключение со счетчиком. Данный объект позволяет «захватить» себя определенному количеству нитей. После этого «захват» будет невозможен, пока одна из ранее «захвативших» семафор нитей не освободит его. Семафоры применяются для ограничения количества нитей, одновременно работающих с ресурсом. Объекту при инициализации передается максимальное число нитей, после каждого «захвата» счетчик семафора уменьшается. Сигнальному состоянию соответствует значение счетчика больше нуля. Когда счетчик равен нулю, семафор считается не установленным (сброшенным).

Функция CreateSemaphore создает объект-семафор с указанием и максимально возможного начального его значения, OpenSemaphore – возвращает дескриптор существующего семафора, захват семафора производится с помощью ожидающих функций, при этом значение семафора уменьшается на единицу, ReleaseSemaphore — освобождение семафора с увеличением значения семафора на указанное в параметре число.

Читайте также:  Синхронизация вандерлист и календаря гугла

Пример. Синхронизация нитей с помощью семафоров.

Защищенный доступ к переменным

Существует ряд функций, позволяющих работать с глобальными переменными из всех нитей, не заботясь о синхронизации, т.к. эти функции сами за ней следят – их выполнение атомарно. Это функции InterlockedIncrement, InterlockedDecrement, InterlockedExchange, InterlockedExchangeAdd и InterlockedCompareExchange. Например, функция InterlockedIncrement атомарно увеличивает значение 32-битной переменной на единицу, что удобно использовать для различных счетчиков.

Для получения полной информации о назначении, использовании и синтаксисе всех функций WIN32 API необходимо воспользоваться системой помощи MS SDK, входящей в состав сред программирования Borland Delphi или CBuilder, а также MSDN, поставляемым в составе системы программирования Visual C.

Источник

Национальная библиотека им. Н. Э. Баумана
Bauman National Library

Персональные инструменты

Синхронизация процессов

Синхронизация процессов (от древне-греч. σύγχρονος — одновременный) — приведение двух или нескольких процессов к такому их протеканию, когда определённые стадии разных процессов совершаются в определённом порядке, либо одновременно.

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

Содержание

Необходимость в синхронизации

Необходимость в синхронизации возникает не только в многопроцессорных системах, но для любого вида параллельных процессов; даже в системах с одним процессором. Некоторые из основных предпосылок для введению синхронизации:

  • Ветвление — Задача разбивается на n-подзадач, которые выполняются n-заданиям. После выполнения, каждая подзадача ждет пока остальные завешат вычисления, затем происходит слияние.
  • Производитель-потребитель — в отношениb производитель-потребитель, процесс-потребитель а зависит от процесса-производителя и ожидает пока необходимые данные будут произведены.
  • Эксклюзивное использование ресурсов — В случае, когда несколько процессов зависят от некоего ресурса и должны получить доступ в одно и то же время, [[Операционная система|ОС должна гарантировать, что только один процесс обращается к ней в данный момент времени, что снижает параллелизм.

Трудности

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

Некоторые другме трудности, которые предстоит решить при синхронизации процессов:

  • Порядок совершения действий;
  • Взаимная блокировка;
  • Ресурсный голод;
  • Инверсия приоритетов;
  • Нагруженное ожидание.

Порядок совершения действий

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

Взаимная блокировка

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

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

Практически об устранении взаимных блокировок надо заботиться ещё на этапе проектирования системы — это единственный более-менее надежный способ с ними бороться. В крайнем случае, когда основная концепция не допускает возможности избежать взаимных блокировок, следует хотя бы строить все запросы ресурсов так, чтобы такие блокировки безболезненно снимались. Жизненный пример такой ситуации: двое встречаются лицом к лицу. Каждый из них пытается посторониться, но они не расходятся, а несколько секунд сдвигаются в одну и ту же сторону.

Ресурсный голод

ситуация, в которой некий процесс ждет, чтобы получить доступ к ресурсу, который монопольно занят другим процессом (постоянный отказ в необходимых ресурсах). Причиной отказа в ресурсах может быть: • ошибка в алгоритме распределения ресурсов; • утечка ресурсов ; • DoS-атака . Часто причиной отказа в ресурсах может быть слишком простой алгоритм распределения ресурсов. Например, если планировщик всегда предоставляет ресурс потока с высоким приоритетом, то при достаточной нагрузке потоки с низким приоритетом не получат ресурс никогда. И, если поток с более высоким приоритетом зависит от результата работы потока с низким приоритетом, то он не сможет завершить задачу несмотря на свой приоритет. Это называется инверсия приоритетов .

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

Инверсия приоритетов

Менее приоритетное задание блокирует совместные ресурсы необходимые более приоритетной задаче. Это приводит к блокировке более приоритетных задач до тех пор, пока задача с более низким приоритетом не разблокирует ресурсы, происходик как бы инверсия относительных приоритетов этих двух задач. Если же в это время попытается исполниться другая средне приоритетная задача, не зависаящая от общего ресурса, то она получит преимущество и над менее и над более приоритетными задачами. Способы решения:

  • Отключение всех прерываний для защиты критических секций
  • Максимизация приоритетов. (A priority ceiling)
  • Наследование приоритетов
Читайте также:  Синхронизация времени по интернету windows 7 при включении

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

Нагруженное ожидание

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

Классические проблемы синхронизации

Некоторые классические проблемы синхронизации:

  • Задача поставщика-потребителя;
  • Взаимная блокировка (т.н. deadlock и livelock);
  • задача о читателях-писателях;
  • Проблема обедающих философов;

Задача поставщика-потребителя

Задача поставщика-потребителя ( англ. Producer-consumer problem), также известная как задача ограниченного буфера ( англ. Bounded-buffer problem ) — это классический пример задачи синхронизации нескольких процессов . Задача описывает два процесса, поставщик и потребитель, которые совместно используют буфер установленного размера. Задачей поставщика является создание фрагмента данных, запись его в буфер и повторение этих действий раз за разом. Одновременно с этим потребитель потребляет данные (то есть, удаляет их из буфера) по одному фрагменту за раз. Задача состоит в том, чтобы не дать поставщику записать данные, когда буфер полон, а потребителю не дать удалить данные из пустого буфера.

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

Задача может быть обобщена на случай многих поставщиков и потребителей.

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

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

« Есть область памяти, позволяющая чтение и запись. Несколько потоков имеют к ней доступ, при этом одновременно могут читать сколько угодно потоков, но писать — только один. Как обеспечить такой режим доступа? »

Первая задача о читателях-писателях (приоритет читателя)

« Пока память открыта на чтение, давать читателям беспрепятственный доступ. Писатели могут ждать сколько угодно. »

Вторая задача о читателях-писателях (приоритет писателя)

« Как только появился хоть один писатель, читателей больше не пускать. При этом читатели могут простаивать. »

Третья задача о читателях-писателях (честное распределение ресурсов)

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

Задача обедающих философов

Задача обедающих философов (англ. Dining philosophers problem) — классический пример, используемый в информатике для иллюстрации проблем синхронизации при разработке параллельных алгоритмов и техник решения этих проблем. Сформулирована в 1965 году Эдсгером Дейкстрой как экзаменационное упражнение для студентов. В качестве примера был взят конкурирующий доступ к ленточному накопителю. Вскоре проблема была сформулирована Ричардом Хоаром в том виде, в каком она известна сегодня.

Постановка задачи

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

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

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

Аппаратная синхронизация

Многие системы обеспечивают аппаратную поддержку для критических секций кода.

Источник