Параллельное программирование, взаимное исключение: различия между версиями

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

В 1968 году Эдсгер Вибе Дейкстра опубликовал свою знаменитую статью «Взаимодействие последовательных процессов», с которой началась эпоха параллельного программирования. Задача о взаимном исключении была впервые сформулирована и решена Дейкстрой в работе [6], в которой были изложены первое решение для двух процессов, предложенное Деккером, и первое решение для n процессов, разработанное Дейкстрой. В работе [ ] приводится обзор некоторых ранних алгоритмов взаимного исключения. В [15] представлены десятки алгоритмов для решения задач о взаимном исключении и широкого спектра других задач синхронизации и проведен анализ их эффективности относительно точных мер сложности.