Программное обеспечение и параллельная революция (Часть 3)

Херб Саттер (Herb Sutter) и Джэймс Лэрус (James Larus), Microsoft.

Часть 3. Блокировки

Проблема разделяемого состояния, и почему блокировки не являются решением

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

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

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

Проблема композирования вызвана главным образом возможностью наступления клинча (deadlock). Простейший вариант клинча наступает, когда две задачи пытаются получить две блокировки во встречном порядке: задача Т1 получает блокировку L1, задача T2 получает блокировку L2, затем, задача T1 пытается получить блокировку L2, а задача T2 пытается получить блокировку L1. Обе задачи блокируются. Поскольку такая ситуация может произойти в любой момент времени, и две блокировки могут быть вызваны во встречном порядке, вы не можете контролировать когда удерживаемая в вашем коде блокировка может стать причиной клинча.

Именно это постоянно происходит в расширяемых средах (frameworks), когда они вызывают виртуальные функции удерживая в это время блокировки (Прим. переводчика. Имеется ввиду, что в переопределенной в наследнике виртуальной функции может быть попытка взять ту же самую блокировку и это станет причиной клинча). Все лучшие на сегодня коммерческие среды не лишены этого недостатка, включая .Net Framework и стандартные библиотеки Java. Мы до сих пор не выбросили их на свалку лишь потому, что разработчики еще не начали писать на них большого количества параллельных приложений. Для решения проблемы клинчей предлагалось множество сложных моделей, например backoff-and-retry протокол, но все они требуют строгой дисциплины при кодировании, а некоторые порождают собственные проблемы (напр., livelocks (активные тупики)).

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

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

Попытки локализовать синхронизацию никогда не удаются. Рассмотрим такое популярное решение как Java synchronized methods. Любой метод класса может получить блокировку на экземпляр объекта так, что никакие два потока не смогут изменять состояние объекта одновременно. До тех пор пока состояние объекта изменяется только посредством вызова его методов, и программист не забывает добавлять к методам объявление synchronized, этот подход работает.

Но существует по крайней мере три проблемы, связанные с синхронизированными методами. Первое, они не подходят для типов, методы которых вызывают виртуальные методы других объектов (напр., Vector в Java, или SyncHashTable в .Net), потому что вызов стороннего кода, в то время как удерживается блокировка, открывает возможность появления клинча. Второе, синхронизированные методы могут выполнять слишком много блокировок, запрашивая их для всех экземпляров объектов, несмотря на то, что большинство из них никогда не разделяют своего состояния между несколькими потоками. Третье, синхронизированные методы могут выполнять слишком короткие блокировки, которые не обеспечивают атомарного изменения состояния при вызове нескольких методов объекта или нескольких объектов. В качестве простого примера, иллюстрирующего последнее утверждение, рассмотрим банковский перевод:

account1.Credit(amount); account2.Debit(amount);

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

Альтернативы блокировкам

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

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