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

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

{\ displaystyle i}

{\ displaystyle i + 1}

{\ displaystyle i + 1}

В информатике , взаимное исключение является собственностью управления параллелизмом , который возбуждается в целях предотвращения гонки условий . Это требование, чтобы один поток выполнения никогда не входил в критический раздел, в то время как параллельный поток выполнения уже обращается к критическому разделу, что относится к интервалу времени, в течение которого поток выполнения обращается к общему ресурсу , например [Shared data objects , общие ресурсы, общая память].

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

Требование взаимного исключения было впервые идентифицировано и решено Эдсгером В. Дейкстра в его основополагающей статье 1965 года «Решение проблемы управления параллельным программированием» ^[1]^[2], которая считается первой темой в исследовании параллельных алгоритмов. . ^[3]

Простой пример того, почему взаимное исключение важно на практике, можно наглядно представить, используя односвязный список из четырех элементов, из которых следует удалить второй и третий. Удаление узла, который находится между двумя другими узлами, выполняется путем изменения следующего указателя предыдущего узла, чтобы он указывал на следующий узел (другими словами, если узел удаляется, то следующий указатель узла изменяется, чтобы указывать на node , тем самым удалив из связанного списка любую ссылку на node ). Когда такой связанный список используется несколькими потоками выполнения, два потока выполнения могут пытаться удалить два разных узла одновременно, причем один поток выполнения меняет следующий. ${\ displaystyle i}$ ${\ displaystyle i-1}$ ${\ displaystyle i + 1}$ ${\ displaystyle i}$ указатель узла, чтобы указать на узел , в то время как другой поток выполнения изменяет следующий указатель узла, чтобы указать на узел . Хотя обе операции удаления завершаются успешно, желаемое состояние связанного списка не достигается: узел остается в списке, потому что следующий указатель узла указывает на узел . ${\ displaystyle i-1}$ ${\ displaystyle i + 1}$ ${\ displaystyle i}$ ${\ displaystyle i + 2}$ ${\ displaystyle i + 1}$ ${\ displaystyle i-1}$ ${\ displaystyle i + 1}$

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

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

Описание проблемы [ править ]

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

Успешное решение этой проблемы должно обладать как минимум этими двумя свойствами:

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

Свободу тупиковых ситуаций можно расширить, реализовав одно или оба этих свойства:

Свобода блокировки гарантирует, что любой процесс, желающий войти в критическую секцию, в конечном итоге сможет это сделать. Это отличается от предотвращения тупиковых ситуаций, которое требует, чтобы некоторый ожидающий процесс мог получить доступ к критическому разделу, но не требует, чтобы каждый процесс получил свою очередь. Если два процесса постоянно обмениваются ресурсами между собой, третий процесс может быть заблокирован и испытывать нехватку ресурсов , даже если система не находится в тупике. Если в системе нет блокировок, это гарантирует, что каждый процесс в какой-то момент в будущем может быть изменен.
Свойство ожидания к-ограниченные дает более точную приверженность , чем локаут-свобода. Свобода блокировки гарантирует, что каждый процесс в конечном итоге сможет получить доступ к критической секции: она не дает никаких гарантий относительно того, как долго будет ждать. На практике процесс может быть перехвачен произвольным или неограниченным числом раз другими процессами с более высоким приоритетом, прежде чем он дойдет до своей очереди. При условии k -ограниченного ожидания каждый процесс имеет конечное максимальное время ожидания. Это работает, устанавливая ограничение на количество раз, когда другие процессы могут врезаться в очередь, так что ни один процесс не может войти в критическую секцию более k раз, пока другой ожидает. ^[4]

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

цикл разделов единого процесса

Некритическая секция: Эксплуатация вне критического участка; процесс не использует и не запрашивает общий ресурс.

Пытающийся: Процесс пытается войти в критическую секцию.

Критический раздел: В этом разделе процессу разрешен доступ к общему ресурсу.

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

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

Обеспечение взаимного исключения [ править ]

Аппаратные решения [ править ]

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

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

Некоторые другие атомарные операции могут использоваться для обеспечения взаимного исключения структур данных; наиболее заметным из них является сравнение и замена (CAS). CAS можно использовать для достижения взаимного исключения без ожидания для любой совместно используемой структуры данных путем создания связанного списка, в котором каждый узел представляет желаемую операцию, которую нужно выполнить. Затем CAS используется для изменения указателей в связанном списке ^[6] во время вставки нового узла. Только один процесс может быть успешным в его CAS; всем остальным процессам, пытающимся одновременно добавить узел, придется повторить попытку. Затем каждый процесс может сохранить локальную копию структуры данных и после обхода связанного списка может выполнять каждую операцию из списка в своей локальной копии.

Программные решения [ править ]

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

Алгоритм Деккера
Алгоритм Петерсона
Алгоритм пекарни Лампорта ^[7]
Алгоритм Шиманского
Алгоритм черно-белой выпечки Таубенфельда ^[2]
Алгоритм Маэкавы

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

Часто предпочтительнее использовать средства синхронизации, предоставляемые библиотекой многопоточности операционной системы , которая будет использовать преимущества аппаратных решений, если это возможно, но будет использовать программные решения, если аппаратных решений не существует. Например, когда используется библиотека блокировки операционной системы и поток пытается получить уже полученную блокировку, операционная система может приостановить поток с помощью переключателя контекста и заменить его другим потоком, готовым к запуску, или может поставить этот процессор в состояние низкого энергопотребления, если нет другого потока, который может быть запущен. Таким образом, большинство современных методов взаимного исключения пытаются уменьшить задержку.и ожидание занятости с использованием очередей и переключений контекста. Однако, если время, затрачиваемое на приостановку потока, а затем на его восстановление, может быть доказано, всегда больше, чем время, которое необходимо подождать, пока поток не станет готовым к запуску после блокировки в конкретной ситуации, то спин-блокировки являются приемлемыми. решение (только для этой ситуации). ^{[ необходима цитата ]}

Связано с проблемой взаимного исключения [ править ]

Одного двоичного регистра тестирования и установки достаточно для решения проблемы взаимного исключения без тупиков. Но решение, построенное с использованием регистра тестирования и установки, может привести к остановке некоторых процессов, которые попадут в раздел попыток. ^[4] Фактически, во избежание блокировки требуются различные состояния памяти. Чтобы избежать неограниченного ожидания, требуется n различных состояний памяти. ^[9] ${\ displaystyle \ Omega ({\ sqrt {n}})}$

Восстанавливаемое взаимное исключение [ править ]

Большинство алгоритмов взаимного исключения разработаны с предположением, что сбой не происходит, пока процесс выполняется внутри критической секции. Однако на самом деле такие сбои могут быть обычным делом. Например, внезапная потеря питания или неисправное межсоединение может привести к тому, что процесс в критическом разделе испытает неисправимую ошибку или не сможет продолжить работу по иным причинам. Если происходит такой сбой, обычные, не отказоустойчивые алгоритмы взаимного исключения могут блокировать или иным образом приводить к отказу ключевых свойств живучести. Для решения этой проблемы было предложено несколько решений, использующих механизмы восстановления после сбоя. ^[10]

Типы устройств взаимного исключения [ править ]

Решения, описанные выше, можно использовать для создания примитивов синхронизации ниже:

Замки (мьютексы)
Читатели-писатели замки
Рекурсивные блокировки
Семафоры
Мониторы
Передача сообщений
Пространство кортежа

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

Многие исследования направлены на устранение вышеуказанных эффектов, часто с целью гарантировать неблокирующий прогресс . Совершенной схемы не известно. Блокировка системных вызовов, используемых для засыпания всего процесса. До тех пор, пока такие вызовы не стали потокобезопасными , не существовало надлежащего механизма для ожидания одного потока внутри процесса (см. Опрос ). ^{[ необходима цитата ]}

См. Также [ править ]

Атомарность (программирование)
Контроль параллелизма
Проблема обедающих философов
Эксклюзивный или
Взаимоисключающие события
Реентерабельный мьютекс
Семафор
Spinlock

Ссылки [ править ]

Перейти ↑ Dijkstra, EW (1965). «Решение задачи управления параллельным программированием». Коммуникации ACM . 8 (9): 569. DOI : 10,1145 / 365559,365617 . S2CID 19357737 .
^ а б Таубенфельд, "Алгоритм черно-белого пекарни" . В Proc. Распределенные вычисления, 18-я международная конференция, DISC 2004. Том 18, 56-70, 2004
^ «PODC Influential Paper Award: 2002» , Симпозиум ACM по принципам распределенных вычислений , получено 24 августа 2009 г.
^ а б Аттия, Хагит; Уэлч, Дженнифер (25 марта 2004 г.). Распределенные вычисления: основы, моделирование и дополнительные темы . ISBN компании John Wiley & Sons, Inc. 978-0-471-45324-6.
^ Лэмпорт, Лесли (26 июня 2000 г.), Проблема взаимного исключения, часть II: Постановление и решения (PDF)
^ https://timharris.uk/papers/2001-disc.pdf
^ Лэмпорт, Лесли (август 1974). «Новое решение проблемы параллельного программирования Дейкстры». Коммуникации ACM . 17 (8): 453–455. DOI : 10.1145 / 361082.361093 . S2CID 8736023 .
^ Хольцманн, Джерард Дж .; Боснацкий, Драган (1 октября 2007 г.). «Дизайн многоядерного расширения средства проверки модели SPIN» (PDF) . IEEE Transactions по разработке программного обеспечения . 33 (10): 659–674. DOI : 10.1109 / TSE.2007.70724 . S2CID 9080331 .
^ Бернс, Джеймс Э .; Пол Джексон, Нэнси А. Линч (январь 1982 г.), Требования к данным для реализации взаимного исключения N-процессов с использованием единой общей переменной (PDF)
^ Голаб, Войцех; Рамараджу, Адитья (июль 2016 г.), Излечимое взаимное исключение

Дальнейшее чтение [ править ]

Мишель Рейналь: алгоритмы взаимного исключения , MIT Press, ISBN 0-262-18119-3
Сунил Р. Дас, Прадип К. Шримани: Распределенные алгоритмы взаимного исключения , IEEE Computer Society, ISBN 0-8186-3380-8
Томас В. Кристофер, Джордж К. Тируватукал: высокопроизводительные вычисления на платформе Java , Prentice Hall, ISBN 0-13-016164-0
Гади Таубенфельд, алгоритмы синхронизации и параллельное программирование , Pearson / Prentice Hall, ISBN 0-13-197259-6

Внешние ссылки [ править ]

Общие темы: объяснение потоков POSIX - мелочи, называемые мьютексами » Дэниела Роббинса
Взаимное исключение сети Петри на машине обратного пути (архивировано 2 июня 2016 г.)
Взаимное исключение с блокировками - введение
Варианты взаимного исключения в OpenMP
Алгоритм черно-белой выпечки

[1] Перейти ↑ Dijkstra, EW (1965). «Решение задачи управления параллельным программированием». Коммуникации ACM . 8 (9): 569. DOI : 10,1145 / 365559,365617 . S2CID 19357737 .

[Taubenfeld:2004-2] а б Таубенфельд, "Алгоритм черно-белого пекарни" . В Proc. Распределенные вычисления, 18-я международная конференция, DISC 2004. Том 18, 56-70, 2004

[3] «PODC Influential Paper Award: 2002» , Симпозиум ACM по принципам распределенных вычислений , получено 24 августа 2009 г.

[Distributed_computing:_fundamentals,_simulations,_and_advanced_topics-4] а б Аттия, Хагит; Уэлч, Дженнифер (25 марта 2004 г.). Распределенные вычисления: основы, моделирование и дополнительные темы . ISBN компании John Wiley & Sons, Inc. 978-0-471-45324-6.

[5] Лэмпорт, Лесли (26 июня 2000 г.), Проблема взаимного исключения, часть II: Постановление и решения (PDF)

[6] ttps://timharris.uk/papers/2001-disc.pdf

[7] Лэмпорт, Лесли (август 1974). «Новое решение проблемы параллельного программирования Дейкстры». Коммуникации ACM . 17 (8): 453–455. DOI : 10.1145 / 361082.361093 . S2CID 8736023 .

[8] Хольцманн, Джерард Дж .; Боснацкий, Драган (1 октября 2007 г.). «Дизайн многоядерного расширения средства проверки модели SPIN» (PDF) . IEEE Transactions по разработке программного обеспечения . 33 (10): 659–674. DOI : 10.1109 / TSE.2007.70724 . S2CID 9080331 .

[9] Бернс, Джеймс Э .; Пол Джексон, Нэнси А. Линч (январь 1982 г.), Требования к данным для реализации взаимного исключения N-процессов с использованием единой общей переменной (PDF)

[10] Голаб, Войцех; Рамараджу, Адитья (июль 2016 г.), Излечимое взаимное исключение

[1]