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

Обновлено: 04.07.2024

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

Содержание

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

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

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

Трудности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существуют в основном две проблемы взаимодействия процессов, это:

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

Любое взаимодействие процессов связано с их синхронизацией, ко­торая заключается в согласовании их скоростей путем приостановки процесса до наступления некоторого события и последующей его активизации при наступ­лении этого события.

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

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

Часто нужна также синхронизация с событиями, внешними по отношению к вычислительной системе, например реакции на нажатие комби­нации клавиш .

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

Во многих ОС эти средства называются средствами межпроцессного взаимодействия — Inter Process Communication (IРС). Обычно к средствам IРС относят не только средства межпроцессной синхрони­зации, но и средства межпроцессного обмена данными.

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

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

Возникновение гонок при доступе к разделяемым данным

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

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

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


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

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

-поток А заносит в базу данных информацию о заказах, поступивших от клиентов, и

-поток В фиксирует в базе данных сведения об оплате клиентами выставленных счетов.

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

1. Считать из файла базы данных в буфер запись о клиенте с заданным иденти-фикатором.

2. Внести новое значение в поле Заказ (для потока А) или Оплата (для потока В).

3. Вернуть модифицированную запись в файл базы данных.

Обозначим соответствующие шаги для потока А как А1, А2 и А3, а для потока В как В1, В2 и В3.

Предположим, что в некоторый момент поток А обновляет поле Заказ записи о клиенте N. Для этого он считывает эту запись в свой буфер (шаг А1), модифицирует значение поля Заказ (шаг А2), но внести запись в базу данных (шаг А3) не успевает, так как его выполнение прерывается, например, вследствие завершения кванта времени.

Предположим также, что потоку В потребовалось внести сведения об оплате относительно того же клиента N. Когда подходит очередь потока В, он успе­вает считать запись в свой буфер (шаг В1) и выполнить обновление поля Оплата (шаг В2), а затем прерывается. В буфере у потока В находится запись о клиенте N, в которой поле Заказ имеет прежнее, не измененное значение.

Когда в очередной раз управление будет передано потоку А, то он, продолжая свою работу, сохранит запись о клиенте N с модифицированным полем Заказ в базу данных (шаг А3). После прерывания потока А и активизации потока В последний запишет в базу данных поверх только что обновленной записи о клиен­те N свой вариант записи, в которой обновлено значение поля Оплата. Таким образом, в базе данных будут зафиксированы сведения о том, что клиент N произвел оплату, но информация о его заказе окажется потерянной .

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

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

Проблема гонок может решаться:

1) приостановкой и активизацией процессов,

2) организацией очередей,

3) блокированием и освобождением ресурсов.

Предположим, что несколько процессов конкурируют за обладание конечным числом ресурсов. Если запрашиваемый процессом ресурс недоступен, ОС переводит данный процесс в состояние ожидания. В случае, когда требуемый ресурс удерживается другим ожидающим процессом, первый процесс не сможет сменить свое состояние. Такая ситуация называется тупиком (deadlock). Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ожидает события, которое никогда не произойдет. Системная тупиковая ситуация, или "зависание системы", является следствием того, что один или более процессов находятся в состоянии тупика. Иногда подобные ситуации называют взаимоблокировками.

Пусть например, имеются два процесса Р1 и Р2 и два ресурса- R1, R2. Предположим, что каждому процессу для выполнения части своих функций требуется доступ к общим ресурсам. Тогда возможно возникновение следующей ситуации:ОС выделяет ресурс R1 процессу Р2, а ресурс R2 – процессу Р1. В результате каждый процесс ожидает получения одного из двух ресурсов. При этом ни один из них не освобождает уже имеющийся ресурс, ожидая получения второго ресурса для выполнения функций, требующих наличия двух ресурсов. В результате процессы оказываются взаимно заблокированными.

Очень удобно моделировать условия возникновения ткпиков, используя напрвленные графы. Графы имеют 2 вида узлов:процессы – кружочки, ресурсы – квадратики.

Ребро, направленное от квадрата (ресурса) к кружку (процессу), означает, что ресурс был запрошен, получен и используется. В нашем примере будем иметь

Исходное распределение ресурсов

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

В нашем случае получим следующий граф

Цикл в графе означает наличие взаимной блокировки процессов.

В общем случае проблема тупиков эффективного решения не имеет.


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


Возникновение взаимных блокировок при выполнении программы

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

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

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

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

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

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

Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.

1. Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.

3. Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобожден он может только процессом, который их удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.

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

Основные направления борьбы с тупиками:

- игнорирование данной проблемы;

- распознавание тупиков и восстановление системы после тупиков.

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

Критическая секция - это часть программы, в которой осуществляется доступ к разделяемым ресурсам. Критическая секция всегда определяется по отношению к определенным критическим данным, при несогласованном изменении которых могут возникнуть нежелательные эффекты. В нашем примере такими критическими данными являлись записи файла базы данных. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находилось не более одного процесса. Этот прием называют взаимным исключением. Простейший способ обеспечить взаимное исключение - позволить процессу, находящемуся в критической секции, запрещать все прерывания на время его нахождения в критической секции. Однако этот способ непригоден, так как опасно доверять управление системой пользовательскому процессу; он может надолго занять процессор, а при крахе процесса в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены.ОС использует разные способы взаимного исключения:

- антидедлоки и т.д.

Вопрос 18.

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

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

Вопрос 20.

Алгоритм Петерсона

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

shared int ready[2] = ;

shared int turn;

while (some condition)

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

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

Удовлетворение требований 1 и 2 очевидно.

Докажем выполнение условия взаимоисключения методом от противного. Пусть оба процесса одновременно оказались внутри своих критических секций. Заметим, что процесс Pi может войти в критическую секцию, только если ready[1-i] == 0 или turn == i. Заметим также, что если оба процесса выполняют свои критические секции одновременно, то значения флагов готовности для обоих процессов совпадают и равны 1. Могли ли оба процесса войти в критические секции из состояния, когда они оба одновременно находились в процессе выполнения цикла while? Нет, так как в этом случае переменная turn должна была бы одновременно иметь значения 0 и 1 (когда оба процесса выполняют цикл, значения переменных измениться не могут). Пусть процесс P0 первым вошел в критический участок, тогда процесс P1 должен был выполнить перед вхождением в цикл while по крайней мере один предваряющий оператор (turn = 0;). Однако после этого он не может выйти из цикла до окончания критического участка процесса P0, так как при входе в цикл ready[0] == 1 и turn == 0, и эти значения не могут измениться до тех пор, пока процесс P0 не покинет свой критический участок. Мы пришли к противоречию. Следовательно, имеет место взаимоисключение.

Докажем выполнение условия прогресса. Возьмем, без ограничения общности, процесс P0. Заметим, что он не может войти в свою критическую секцию только при совместном выполнении условий ready[1] == 1 и turn == 1. Если процесс P1 не готов к выполнению критического участка, то ready[1] == 0, и процесс P0 может осуществить вход. Если процесс P1готов к выполнению критического участка, то ready[1] == 1 и переменная turn имеет значение 0 либо 1, позволяя процессу P0 либо процессу P1 начать выполнение критической секции. Если процесс P1 завершил выполнение критического участка, то он сбросит свой флаг готовности ready[1] == 0, разрешая процессу P0 приступить к выполнению критической работы. Таким образом, условие прогресса выполняется.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

По имеющемуся дескриптору объекта можно определить его текущее состояние. Это делается с помощью т.н. ожидающих функций. Чаще всего используется функция 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.

Механизм синхронизации процесса операционной системы

Каталог статей

1. Основные концепции

1. Понятие механизма синхронизации процессов.

Механизм взаимосвязи между несколькими процессами (потоками) в порядке выполнения называется механизмом синхронизации процессов.

2. Зачем вводить механизм синхронизации процессов

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

3. Важные ресурсы

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

4. Критическая зона

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

2. Синхронизация процессов и отношения взаимного исключения

1. Синхронизация

2. Взаимоисключающие

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

3. Четыре основных принципа механизма синхронизации процессов.

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

2. Подождите, пока занят

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

3. Ограниченное время ожидания

4. Пусть власть подождет

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

4. Программно-аппаратный метод синхронизации.

1. Программный метод


Хотя этот метод определяет, осуществляется ли доступ к критическому ресурсу, два процесса могут войти в критическую область одновременно.

2. Аппаратный метод


5. Семафорный механизм

Обзор

Таким образом, механизм семафоров - это инструмент для синхронизации процессов.

1. Целочисленный семафор

2. Записанный семафор

Его псевдокод выглядит следующим образом:

3. И введите семафор

Когда процессу необходимо получить несколько ресурсов одновременно, он должен использовать семафор типа AND

4. Набор семафоров

Когда одновременно требуются n ресурсов и ресурс Si применяется для ресурсов di, а доступное количество ресурсов этого типа меньше определенного нижнего предела ti, он не будет выделен, поэтому механизм семафоров типа AND необходимо расширить. для формирования механизма набора семафоров:

Читайте также: