Синхронизация параллельных процессов. Критические ресурсы

Атомарная операция – это неделимая операция в рассматриваемом контексте.

P:a b c R(P).

Q:d e f W(P)

a b c d e f

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

Его можно безбоязненно выполнять в режиме разделения времени. Существует так называемые условия Бернстайна, к-е определяют насколько набор активностей детерминирован. R(P)и W(P) – наборы вх.и вых данных прог-мы или активности P.

P: х=u*w

Y=a+u

W(P)={x,y}

R(P)= {a,u,w}

Условия:

1.для двух активностей P и Q: W(P)(знак пересечения – перевернутая буква U) W(Q)=0 - непересекаются

W(P)(тот же знак) R(Q)=0 – непер. наборы вых.данных

R(P)(тот же знак)W(Q)=0 – не должны пересекаться вых.д.активностей.

Если выполняется 1-3 то P и Q детерминированы.

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

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

While(some condition)

 { entry section

Critical section

Exit section

Remainder section}

Критические ресурсы.

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

Определим два уровня собственной сигналобезопасности программ.

1. Безусловная сигналобезопасность. Обеспечивается повторно-входимыми программными компонентами, обращение к которым может происходить в любой момент времени без каких-либо конфликтов. Такие программы должны выполняться независимо от любой другой программы, включая самою себя. Это достигается несколькими способами:

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

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

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

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