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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 06:53, 29 декабря 2016.

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

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

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

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

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

Трудности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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