Поэлементная непротиворечивость

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

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

Формально хранилище данных обеспечивает поэлементную непротиворечи­вость, если оно удовлетворяет трем условиям.

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

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

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

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

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

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

Рассмотрим пример. Процесс P1 осуществляет захват х, изменяет х, после чего захватывает у. Процесс Р2 захватывает х, но не у, после чего считывает из х значение для а, но для у может считать только нуль (NIL). Поскольку процесс РЗ сначала захватывает у, он может прочитать значение b после того, как элемент у будет освобожден процессом Р1.

Р1: Acq(Lx) W(x)a Acq(Ly) W(y)b Rel(Lx) Rel(Ly)

P2: Acq(Lx) R(x)a R(y) NIL

P3: Acq(Ly) R(y)b

Дата добавления: 2015-08-18