Кодирование без блокировок с помощью разделяемых
классов Теория синхронизации, основанной на
блокировках, сформировалась в 1960-х. Но уже к 1972
году [23] исследователи стали искать пути исключения из
многопоточных программ медленных, неуклюжих мьютексов,
насколько это возможно. Например, операции присваивания
с некоторыми типами можно было выполнять атомарно, и
программисты осознали, что охранять такие присваивания
с помощью захвата мьютексов нет нужды. Кроме того,
некоторые процессоры стали выполнять транзакционно и
более сложные операции, такие как атомарное увеличение
на единицу или «проверить- и-установить ». Около
тридцати лет спустя, в 1990 году, появился луч надежды,
который выглядел вполне определенно: казалось, должна
отыскаться какая- то хитрая комбинация регистров для
чтения и записи, позволяющая избежать тирании
блокировок. И в этот момент появилась полная
плодотворных идей работа, которая положила конец
исследованиям в этом направлении, предложив другое.
Статья Мориса Херлихи «Синхронизация без ожидания »
(1991) [3] ознаменовала мощный рывок в развитии
параллельных вычислений. До этого разработчикам и
аппаратного, и программного обеспечения было одинаково
неясно, с какими примитивами синхронизации лучше всего
работать. Например, процессор, который поддерживает
атомарные операции чтения и записи значений типа int,
интуитивно могли счесть менее мощным, чем тот, который
помимо названных операций поддерживает еще и атомарную
операцию +=, а третий, который вдобавок предоставляет
атомарную операцию *=, казался еще мощнее. В общем, чем
больше атомарных примитивов в распоряжении
пользователя, тем лучше. Херлихи разгромил эту теорию,
в частности показав фактическую бесполезность
казавшихся мощными примитивов синхронизации, таких как
«проверить- и-установить », «получить- и-сложить » и
даже глобальная разделяемая очередь типа FIFO. В свете
этих парадоксов мгновенно развеялась иллюзия, что из
подобных механизмов можно добыть маги13.16. Кодирование
без блокировок с помощью разделяемых классов 511 ческий
эликсир для параллельных вычислений. К счастью, помимо
получения этих неутешительных результатов Херлихи
доказал справедливость выводов об универсальности:
определенные примитивы синхронизации могут теоретически
синхронизировать любое количество параллельно
выполняющихся потоков. Поразительно, но реализовать
«хорошие » примитивы ничуть не труднее, чем «плохие »,
причем на невооруженный глаз они не кажутся особенно
мощными. Из всех полезных примитивов синхронизации
прижился лишь один, известный как сравнение с обменом
(compare-and-swap). Сегодня этот примитив реализует
фактически любой процессор. Семантика операции
сравнения с обменом: // Эта функция выполняется
атомарно
bool cas(T)(shared(T) * here, shared(T) ifThis, shared(T) writeThis)
{ if (*here == ifThis)
{
*here = writeThis; return true;
}
return false;
}
В переводе на обычный язык операция cas атомарно
сравнивает данные в памяти по заданному адресу с
заданным значением и, если значение в памяти равно
переданному явно, сохраняет новое значение; в противном
случае не делает ничего. Результат операции сообщает,
выполнялось ли сохранение. Операция cas целиком
атомарна и должна предоставляться в качестве примитива.
Множество возможных типов T ограничено целыми числами
размером в слово той машины, где будет выполняться код
(то есть 32 и 64 бита). Все больше машин предоставляют
операцию сравнения с обменом для аргументов размером в
двойное слово (double-word compare-and-swap), иногда ее
называют cas2. Операция cas2 автоматически обрабатывает
64-битные данные на 32-разрядных машинах и 128-битные
данные на 64-разрядных машинах. Ввиду того что все
больше современных машин поддерживают cas2, D
предоставляет операцию сравнения с обменом для
аргументов размером в двойное слово под тем же именем
(cas), под которым фигурирует и перегруженная
внутренняя функция. Так что в D можно применять
операцию cas к значениям типов int, long, float,
double, любых массивов, любых указателей и любых ссылок
на классы.