автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математическое моделирование алгоритмов, работающих на разделяемой памяти

На правах рукописи

Кудрин Максим Юрьевич

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ АЛГОРИТМОВ, РАБОТАЮЩИХ НА РАЗДЕЛЯЕМОЙ ПАМЯТИ

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

- 3 ДЕН И09

Москва - 2009

003486044

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета)

Научный руководитель:

доктор физико-математических наук

ТОРМАСОВ Александр Геннадьевич.

Официальные оппоненты:

доктор физико-математических наук, профессор ДИКУСАР Василий Васильевич,

кандидат технических наук ДРОЗДОВ Александр Юльевич.

Ведущая организация:

Институт автоматизации проектирования РАН.

Защита состоится $ декабря 2009 года в

¿О

часов па заседании

диссертационного совета Д 212.156.05 при Московском физико-техническом ииституте (государственном университете) по адресу: 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан У ^ ноября 2009

года.

Ученый секретарь диссертационного совета Д 212.156.05

Федько О.С.

Общая характеристика работы Актуальность темы

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

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

В основе статического и динамического подходов лежит одна общая идея -выявление и контроль за ключевыми моментами, такими, как захват или освобождение блокировок. Но методы детектирования состояний гонки — разные. Статический анализ — это анализ кода без исполнения программы. В случае параллельных приложений статический анализ крайне сложен, и часто невозможно предсказать поведение программы, так как неизвестен допустимый набор входных значений для различных функций и способ их вызова. Эти значения можно прогнозировать па основе остального кода, но крайне ограниченно, так как возникает огромное пространство возможных состояний, и объем проверяемой информации (вариантов) увеличивается до недопустимых значений. Также средства статического анализа часто дают большое количество ложных сообщений о потенциальных ошибках и требуют немалых усилий для их минимизации. При динамическом анализе ведется поиск ошибок по результатам конкретного запуска приложения. В этом случае симптомы наличия состояний гонки могут проявиться только тогда, когда два потока получают доступ к некорректно защищенной области памяти почти в одно и тоже время, то сеть программа может корректно работать в течение долгих месяцев пока не проявится состояние гонки. Это обстоятельство объясняет тот факт, что если речь заходит о проверке программы на многопроцессорной машине, то положительные отчеты динамических анализаторов воспринимаются с большим скепсисом.

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

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

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

Цель работы, задачи исследования

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

Задачи исследования:

• Моделирование многопоточных алгоритмов, работающих на разделяемой памяти.

• Разработка критериев наличия состояний конкурентного доступа к памяти, приводящих к некорректной работе алгоритма.

• Разработка методики автоматизированного тестирования, определяющей наличие состояний конкурентного доступа к памяти, приводящих к некорректной работе многопоточной программы.

• Оценка сложности методики автоматизированного тестирования в различных случаях.

Научная новизна

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

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

Практическая ценность

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

Положения, выносимые на защиту:

1. Математическая модель процесса исполнения мпогопоточных алгоритмов путем анализа инструкций потоков на платформах архитектуры х86.

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

3. Анализ задач параллельного программирования па основе предложенной методики автоматизированного тестирования.

Публикации и апробация результатов

По теме диссертации опубликовано 14 работ, в том числе две [1,4] - в изданиях, рекомендованных ВАК РФ. В работах с соавторами соискателем лично выполнено следующее: построение математической модели исполнения многопоточных алгоритмов, разработка метода нахождения состояний гонки в потоках, работающих на разделяемой памяти, анализ задач параллельного программирования с помощью данного метода.

Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных семинарах и конференциях:

• XXXV международная молодежная научная конференция «Гагаринские чтения», Москва, 2009 г.,

• I международная научно-техническая конференция "Компьютерные науки и технологии", Белгород, 2009 г.,

• Международная научно-техническая конференция "Многопроцессорные вычислительные и управляющие системы 2009", Дивпоморское, 2009 г.,

• XI, XIII Всероссийские научно-практические конференции «Научное творчество молодежи», Кемерово, 2007,2009 гг.,

• ХЬУН, ХЬУШ научные конференции МФТИ, - Москва: МФТИ, 20042005 гг.,

• Научные семинары кафедры информатики МФТИ, 2007-2009 гг.

Структура и объем работы

Диссертация состоит из введения, шести глав, заключения и списка использованных источников, включающего 91 наименование. Общий объем работы составляет 112 страниц текста.

Краткое содержание работы

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

Первая глава

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

Вторая глава

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

Выбор архитектуры х86 объясняется ее широким распространением. В данной архитектуре существуют инструкции для атомарных операций с памятью, реализующие примитив CAS - compare and swap (сравнение и замена). Например, инструкция CMPXCHG, которая позволяет атомарно выполнять сравнение значения ячейки памяти с его обменом — новое значение записывается, только если предыдущее совпало с заданным, предыдущее значение запоминается. Данная инструкция широко используется при реализации неблокирующихся алгоритмов на платформах архитектуры х86.

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

Вводится понятие графа совместного исполнения потоков G := (V,A), путям в котором сопоставляются всевозможные варианты поведения миогопоточного алгоритма. Ключевым отличием от графа потока управления (control flow graph), описывающего исполнение одного потока, является представление в виде одного графа процесса одновременного исполнения двух и более потоков. Дугам V в таком графе сопоставляются атомарные команды различных потоков.

Вводится понятие булевой функции корректности р, как меры определения того, что при конкретном варианте совместного исполнения потоков многопоточный алгоритм работает корректно. Эта функция определяется для каждого рассматриваемого алгоритма с учетом того, что именно считается

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

Вводится понятие состояния исполнения потоков Я. В общем случае под этим понимается совокупность значений ячеек разделяемой памяти и значений локальных переменных потоков.

Проводится разбиение операций, выполняемых потоками, па группы в зависимости от отношения к ячейкам разделяемой памяти. Рассматривается изменение состояния исполнения потоков 5 под действием операций из различных групп. Рассматривается вопрос об определении значения функции корректности р по состояниям исполнения потоков.

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

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

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

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

Третья глава

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

совершить 0(C"„)~0(-j=) действий, чтобы найти всевозможные состояния Vn

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

В зависимости от отношения к общим ячейкам памяти, разобьем выполняемые потоками операции натри группы:

• Операции чтения. Поток считывает значение одной из общих ячеек памяти. Обозначение одной операции - R.

• Операции записи. Поток записывает значение в одну из общих ячеек памяти. Обозначение одной операции — W.

• Другие операции. Операции, не входящие ни в один из вышеописанных классов. Обозначение одной операции - X.

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

Предположим, что первый поток совершает некоторую операцию А], а во второй поток - операцию В*. Возможны два варианта: операция А{ будет выполнена раньше операции В*, и операция Aj будет выполнена позже операции

в;.

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

• A=R, B=W (первый поток считывает значение ячейки памяти, а второй пишет туда же)

• А=\Л/, В=Р? (второй поток считывает значение ячейки памяти, первый поток записывает в эту же ячейку)

• А=\Л/, В=\Л/ (оба потока выполняют операцию записи в одну ячейку) Определение 1. Если существует хотя бы одна общая ячейка памяти, что

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

Пусть первый поток совершает к операций, а второй - п операций. Под графом совместного исполнения двух потоков будем понимать ориентированный граф С:=(\/,А), \/= и V1., А= и и ,,,)• Пример подобного графа

/■|,»И /I.» / 1,4+1 ' '

представлен на рис. 1.

Рис. 1. Пример графа совместного исполнения потоков при к=4, п=3

В таком графе существует только одна вершина в которую не входит ни одной дуги. Будем называть её начальной вершиной. Вершину единственную, из которой не исходит ни одной дуги, назовём конечной. Для произвольной вершины назовем се уровнем число, равное ¡+]. Начальная вершина имеет минимальный уровень в графе, конечная вершина -максимальный. Кроме того, нетрудно заметить, что для любых двух смежных вершин в данном графе уровни различаются на единицу, причем меньше уровень той вершины, откуда исходит дуга. Отсюда, в частности, следует, что в таком графе нет циклов. В дальнейшем, рассматривая графы совместного исполнения потоков, будем опускать изображения стрелок на дугах. Интерес к подобному графу обусловлен следующим утверждением.

Лемма 2. Назовем ориентированный путь из начальной вершины в конечную полным путем. Существует взаимно-однозначное соответствие между вариантами

совместного исполнения потоков и полными путями в соответствующем графе совместного исполнения потоков.

Определение 2. Будем говорить, что дуги (у'у,уу!), где / = I представляют ¡-ую операцию, выполняемую первым потоком. Дуги где

¡ = \,к + \, представляют j-yю операцию, выполняемую вторым потоком. Полный путь представляет соответствующий ему вариант совместного исполнения потоков.

Для любых двух пекоммутирующих операций 1 и ] поставим знак + в области, ограниченной дугами (у),У**), и На рис. 2 такими

операциями являются и Щ.

Определение 3. Числом пекоммутирующих операций на ^ом уровне р, назовем количество вершин уровня I, таких что операции, представляемые дугами (ч)У^) и (ч)Ун{) являются некоммутирующими.

Рис. 2. Пример указания пекоммутирующих операций на графе Рассмотрим два различных пути на графе совместного исполнения потоков из вершины V* в конечную вершину у^,'. Проделаем следующее: будем двигаться по дугам графа вдоль каждого из путей и преобразовывать состояние исполнения потоков согласно операциям, которые эти дуги представляют. Если мы можем гарантировать, что дойдя до вершины V*',1, мы получим одинаковые состояния, то будем считать эти пути эквивалентными. Таким образом, все пути из у* в у',1' разбиваются на классы эквивалентности.

Утверждение 1. Два пути из вершины у* в вершину V*,*,', которые

отличаются друг от друга только парой дуг - (у^У/1), в одном и

в другом, принадлежат одному классу эквивалентности, если 1-я операция первого потока и )-я операция второго коммутируют между собой (в области, ограниченной этими дугами (у"1,^'),^,,^,), (у,,у)+|), на графе

совместного исполнения потоков не указан знак +).

Нас, прежде всего, интересуют классы эквивалентности полных путей. Определим для графа совместного исполнения потоков следующую функцию /(/,7), 1 </'<¿ + 1,1 <7 <л +1. Здесь к - число операций, выполняемых первым потоком, а п - число операций, выполняемых вторым потоком.

1- Л'.У) = 1 при/ = £ + 1,у = 1,..,л + 1

2- /(и) = 1 ПРИ 7 = л + 1,/ = 1,..,А

/(',7') = /(' + 1.7') + /(',/ + 1), если ¡-я операция первого потока и ¡-я операция второго потока являются некоммутирующими, в противном случае /(', 7) = /('■ +1, Л + Д<\ 7+ !)-/('+ 1,7 + 1)

Теорема 1. Число классов эквивалентности полных путей равно /(1,1) и может быть вычислено за 0(к*п) операций.

Предположим, что классы эквивалентности занумерованы числами от 1 до /(1,1). Знание значений функции /(/',/), 1 </'<к +1,1 </<п+1 позволяет построить представителей классов эквивалентности, двигаясь от начальной вершины графа совместного исполнения потоков к конечной. Находясь в вершине V*,

принимается решение о включении в выстраиваемый путь вершины Vх", либо

вершины в зависимости от значений /(х,у), /(х + 1,у) и /(х,у+1). В работе

представлен алгоритм построения пути, принадлежащего классу эквивалентности с заданным номером, и доказывается следующая теорема:

Теорема 2. Описанный алгоритм позволяет построить представителей всех классов эквивалентности, требуя при этом 0(к+п) действий для нахождения одного пути.

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

м

виде к = + и>,' + х,'. Здесь М— число общих ячеек памяти, для /-ой ячейки г', и;1,.г1 (=1

- количество операций чтения, записи и других соответственно. Для второго

м

потока п = ]>] г/ + + х). Используя лемму 1, можно найти число 1=1

некоммутирующих операций (число "плюсов" на графе):

м

1' = ^ г' * щ] + г,2 * ь и; * п). Исходя из определения 3, это число может также быть

1=1

и+/+2

представлено в виде Р= р,.

1=2

Теорема 3. Для числа классов эквивалентности полных путей С справедлива

л(Н2

оценка \ + Р<С<\\ р, + 1 <2''. 1=2

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

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

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

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

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

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

a. Не существует соседних некоммутирующих операций из разных потоков, где операция первого потока предшествует операции второго. С учетом предыдущего условия, получается, что все операции второго потока предшествуют операциям первого. Значит мы получили вариант совместного исполнения потоков, когда сначала выполняется второй поток, затем первый. В этом случае алгоритм заканчивает работу.

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

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

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

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

Четвертая глава

Четвертая глава посвящена анализу задач параллельного программирования с помощью описанной методики с целью выявления неразрешенных состояний гонки.

Рассматриваются следующие задачи:

1. Задача об изменении значения ячейки в двух потоках.

2. Задача о транзакционном изменении значений двух ячеек памяти.

3. Алгоритм спин-блокировки.

4. Неблокирующаяся реализация алгоритма очереди.

5. Алгоритм Петерсона для случая двух потоков.

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

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

Задача об изменении значения ячейки в двух потоках

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

• Считать значение ячейки памяти.

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

• Записать вычисленное значение в ячейку памяти.

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

Мы рассмотрим случай, когда функция /(*) = *+! одинакова для обоих потоков. Первый поток выполняет операции К, У,(/)Щ,/(х) = х+\. Второй поток выполняет операции Я2 \/2(/) Щ, /(*) = *+!.

("V,-)

(ш+1+в,,ш+1+а5а3,ш+1+о5а3)

Рис. 3. Вычисление результирующего состояния исполнения потоков

На рис. 3 жирной линией обозначены дуги редуцированного графа. Двигаясь от начальной вершины к конечной, будем вычислять состояние исполнения в каждой из вершин редуцированного графа. В итоге мы получим, что значение ячейки памяти после работы двух потоков будет равно т + \ + а3. Очевидно, что существует два набора неопределенных коэффициентов, подстановка которых даст различный результат (в одном наборе а3 = 0, в другом а, = I), а это означает, что неразрешенное состояние гонки может возникать.

Задача о транзакционном изменении значений двух ячеек памяти

Дано два потока, две ячейки памяти и некоторое число к. Первый поток выполняет следующую транзакцию:

• Считывает значение первой ячейки памяти

• Вычитает из считанного значения к

• Записывает результат в первую ячейку памяти

• Считывает значение второй ячейки памяти

• Прибавляет к считанному значению к

• Записывает результат во вторую ячейку памяти

Второй поток контролирует значения ячеек памяти. Он делает следующее:

• Считывает значение первой ячейки памяти

• Считывает значение второй ячейки памяти

Необходимо найти значения, считанные вторым потоком. Исходя из требования константности данных значений функцией корректности, определить, возможно ли возникновение неразрешенного состояния гонки. Первый поток выполняет операции ^У^^УЛ/! К* У?(£)\М?,/(х) = х-к,£(х) = х+к. Второй поток выполняет операции И2.

(ш, -1с,т, -к,т, -а4к)(т2,ш2 + к,-)

(т, -к,т, -к,т, -а4к)(т2,т2,-)

(т, -к,т, -к,т|-а4к)(ш2,-,-)

(т,,т,-к,-)(т2,-,-)

(т,,т,,-)(т2,-,-)

(т,Л-)(т2,-,-)

а

Рис. 4. Вычисление результирующего состояния исполнения потоков

Итак, мы получили, что второй поток считает из первой ячейки значение m,-a4k, а из второй - m2 + ar8k. Сумма считанных значений равна m,+m2+(a8-a4)k. Существуют наборы значений неопределенных коэффициентов, подстановка которых даст различный результат (например, as = ],аА =0 и as = 0,a4 = 1), а значит возможно неразрешенное состояние гонки. Относительно данной задачи это означает, что наблюдатель может увидеть результат транзакции в некотором промежуточном состоянии, когда сумма значений ячеек памяти не равна сумме значений ячеек до исполнения потоков.

Алгоритм спин-блокировки

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

Л1(В1): while( !CAS(&mem, 0,1));

А2(В2): //действие в критической секции

АЗ(ВЗ): mem=0;

Для данной задачи функцией корректности является требование о невозможности одновременного выполнения действий в критической секции двумя потоками.

Э2

Переход из состояния 81 в состояние в случае, если значение ячейки памяти в состоянии 31 равно х, в противном случае переход в Э2.

Рис. 5. Граф совместного исполнения потоков для алгоритма спин-блокировки

На рис. 5 жирной линией обозначены достижимые дуги редуцированного графа. Ни одна из них не ведет в вершину С, что означает сё недостижимость. А значит функция корректности будет верна при любом варианте совместного исполнения потоков.

Неблокирующаяся реализация алгоритма очереди Пусть определен массив int q[N] и две переменные int tail и int head. Здесь N - некоторое заранее заданное число, а массив и переменные расположены в

разделяемой памяти. В массиве хранятся числа, добавляемые в очередь, переменная head содержит номер первого элемента в очереди, a tail - помер свободной ячейки, следующей за последним элементом очереди. Мы рассматриваем случай очереди с числами, чтобы не углубляться в исследование ЛВЛ проблемы.

Процедуры добавления и удаления элемента из очереди выглядят следующим образом:

bool Enqueue( int х) {

int t;

while (1) {

Л1(В1) А2(В2) АЗ(ВЗ) А4(В4)

А5(В5): Л6(В6):

}

}

t=tail;

if (t = N) return 0; if (q[t] !=NULL) { CAS(tail, t, t+1); continue;} if (CAS(q[t], NULL, x)) { CAS(tail, t, t+1); return 1;}

int Dequeue( void ) {

int h;

while (1) {

if (h == tail) return 0; result = q[h]; if (result == NULL) { CAS(head, h, h+1); continue;} if (CAS(q[h], result, NULL)) CAS(head, h, h+1); return result;}

}

Пусть требуется определить, всегда ли алгоритм будет работать правильно при следующих начальных значениях N > 2, q|0] = с, q[l| = 0, q|2] = 0, head = 0, tail = 1. Существуют различные комбинации операций над очередью, выполняемых потоками. Рассмотрим случай двух потоков, которые добавляют элементы в очередь. Пусть первый поток добавляет а, второй поток добавляет Ь. Существуют разнообразные варианты определения функции корректности для данной задачи. Выберем предельно конкретную функцию корректности с учетом знания о внутреннем представлении очереди - после завершения работы потоков должно быть выполнено следующее:

1. head=0, tail = 3

2. q|0]=c, q|l|=a, q[2]=b, либо q[0]=c, q[l]=b, q|2]=a

Это означает, что в очередь были успешно добавлены два указанных выше элемента.

(1.-,-)

(0,0)

Рис, 6. Граф совместного исполнения потоков для алгоритма очереди

На рис. 6 жирной линией обозначены достижимые дуги редуцированного графа. В каждой вершине указаны возможные состояния исполнения потоков. Значения переменных head и q[0J опущены, так как они не изменяются. Для наглядности не указываются неопределенные коэффициенты, вместо этого значения записаны через логическое "или". Итак, мы получили, что состояние исполнения потоков в конечной вершине графа может быть одним из двух

1. hcad=0, tail = 3, tA = 1, tB=2, q[0]=c, q[l]=a, q[2]=b

2. hcad=0, tail = 3, tA = 2, tB=l, q[0]=c, q[lj=b, q[2]=a

Нетрудно заметить, что условия функции корректности выполнены в обоих случаях.

Последним в четвертой главе рассматривается алгоритм Петерсона для случая двух потоков. Для него также проведено исследование с помощью предложенной методики.

В заключении описываются основные результаты и выводы работы.

Основные результаты работы

1. Разработана математическая модель процесса исполнения многопоточных алгоритмов путем анализа инструкций потоков на платформах архитектуры х86.

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

3. Разработана методика автоматизированного тестирования, выявляющая наличие состояний конкурентного доступа к памяти в многопоточных алгоритмах, удовлетворяющих ряду условий.

4. Проведено исследование ряда задач параллельного программирования посредством анализа их математических моделей с помощью предложенной методики.

Список публикаций по теме диссертации

1. Кудрин М.Ю., Соколов Е.В., Тормасов А.Г. Выявление состояний гонки с помощью графа совместного исполнения потоков // Научно-технические ведомости СПбГПУ, Серия "Информатика, телекоммуникации, управление." - СПб.: Изд-во Политехи, ун-та, 2009. - № 5 (83). - С. 125-134.

2. Кудрин М.Ю., Прокопенко A.C., Тормасов А.Г. Метод нахождения состояний гонки в потоках, работающих на разделяемой памяти // Сборник научных трудов МФТИ. - М.: МФТИ, 2009.-№4. -Том 1. - С. 181-201.

3. Кудрин М.Ю., Петров В.Н., Прокопенко A.C., Тормасов А.Г. Математическое моделирование структур, работающих на разделяемой памяти // Материалы международной научно-технической конференции "Многопроцессорные вычислительные и управляющие системы 2009". -Таганрог: Изд-во ТТИ ЮФУ, 2009. - Том 1. - С. 73-74.

4. Соколов Е.В., Кудрин М.Ю., Тормасов А.Г. Модель организации снимка памяти на основе nk-схемы при наложении ограничения типа темпа доступа // Научно-технические ведомости СПбГПУ, Серия "Информатика, телекоммуникации, управление." - СПб.: Изд-во Политехи, ун-та, 2009. -№4 (82).-С. 131-136.

5. Кудрин М.Ю. Выявление состояний гонки с помощью графа совместного исполнения потоков // Материалы международной научно-технической конференции "Компьютерные науки и технологии" - Белгород: Изд-во БелГУ, 2009. - С. 45-46.

6. Кудрин М.Ю., Петров В.П., Прокопенко A.C. Обнаружение состояний гонки в потоках, работающих на разделяемой памяти // Модели и методы обработки информации, сборник научных трудов - М.: МФТИ, 2009. - С. 93-98.

7. Соколов Е.В., Кудрин М.Ю. Модель организации снимка памяти на основе nk-схемы при наложении ограничения типа темпа доступа // Модели и методы обработки информации, сборник научных трудов - М.: МФТИ, 2009,- С. 197-205.

8. Кудрин М.Ю., Соколов Е.В. Выявление состояний гонки с помощью аппарата атрибутных грамматик // Научное творчество молодежи. Материалы XIII Всероссийской научно-практической конференции. -Кемерово: Кемеровский гос. универ-т, 2009. - С. 112.

9. Соколов Е.В., Кудрин М.Ю. Алгоритмы енэпшота основанные на ограничении темпа доступа к памяти // Научное творчество молодежи. Материалы XIII Всероссийской научно-практической конференции. -Кемерово: Кемеровский гос. универ-т, 2009. - С. 125.

Ю.Кудрин М.Ю., Петров В.Н., Прокопенко A.C. Математическое моделирование структур, работающих на разделяемой памяти // XXXV Международная молодежная научная конференция "Гагаринские чтения", секция "Ипфотелекоммуникационные технологии" - Москва: МАТИ, 2009. -С. 24-25.

И.Соколов Е.В., Кудрин М.Ю. Примеление (л, к)-схемы для реализации алгоритмов енэпшота памяти // XXXV Международная молодежная научная конференция "Гагаринские чтения", секция "Информационные системы и прикладные информационные технологии в социально-экономической сфере" - Москва: МАТИ, 2009. - С. 155.

12.Кудрин М.Ю., Гилимьянов Р.Ф., Кобец А.Л., Луковников В.В. Сравнение цепочечной модели с существующими распределёнными объектными моделями // Научное творчество молодежи. Часть IV. Материалы XI Всероссийской научно-практической конференции. - Кемерово: Кемеровский гос. универ-т, 2007. - С. 7-8

И.Кудрин М.Ю., Гилимьянов Р.Ф. Сравнение цепочечной модели с существующими распределёнными моделями // Совр. проблемы

фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды ХЬУШ научной конференции. / МФТИ, - М.Долгопрудный, 2005. - С. 42.

14.Кудрин М.Ю. Исследование цепочечных объектов // Совр. проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды \LVII научной конференции. / МФТИ, - М.Долгопрудный, 2004. - С. 74.

Кудрин Максим Юрьевич

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ АЛГОРИТМОВ, РАБОТАЮЩИХ НА РАЗДЕЛЯЕМОЙ ПАМЯТИ

Автореферат

Подписано в печать 30.10.2009 Формат 60x90/16. Уел печ л 1.0. Тираж 80 экз. Заказ No 570. Московский физико-технический институт (государственный университет)

Печать на аппарате Rex-Rotary Copy Printer 1280. НИЧ МФТИ.

141700, г Долгопрудный Московской обл, Институтский пер, 9, тел.: (095) 4088430, факс (095) 5766582

Оглавление.

Введение.

Актуальность темы.

Цель работы, задачи исследования

Научная новизна.

Практическая ценность.

Краткое содержание работы.

Обзор существующих систем.

Динамический анализ

Общие принципы.

Инструменты динамического анализа.

Средства статического анализа.

Основные принципы.

Вычисления при помощи набора состояний.

Анализ части кода.

Использование псевдонимов.

Точность и время работы.

Алгоритмы.

Анализаторы.

Синхронизация в многопоточных алгоритмах.

Архитектуры параллельных систем.

Моделирование и методика анализа.

Алгоритмы анализа.

Постановка задачи для двух потоков.

Представление работы потоков

Построение графа совместного исполнения потоков.

Определение классов эквивалентности.

Построение представителей классов эквивалентности

Оценка числа классов эквивалентности.

Построение редуцированного графа и анализ результатов.

Анализ трех и большего числа потоков.

Ветвления в алгоритмах.

Допустимость перестановки операций одного потока.

Примеры исследования многопоточных алгоритмов.

Задача об изменении значения ячейки в двух потоках

Граф совместного исполнения потоков.

Классы эквивалентности.

Редуцированный граф.

Вычисление результата работы потоков.

Задача о транзакционном изменении двух ячеек памяти

Представление работы потоков.

Граф совместного исполнения потоков.

Классы эквивалентности.

Редуцированный граф.

Вычисление результата работы потоков.

Алгоритм спин-блокировки.

Неблокирующаяся реализация алгоритма очереди.

Алгоритм Петерсона для случая двух потоков.

1. Serebryany К. Data race test. -(http://c0de.g00gle.c0m/p/data-race-test)

2. Herlihy M., Shavit N. The Art of Multiprocessor Programming. Elsevier, 2008.

3. Rahul V. Patil, George B. Concurrency: Tools And Techniques to Identify Concurrency Issues. MSDN Magazine, June 2008

4. S. Qadeer, D. Wu. KISS: keep it simple and sequential. -PLDI, 2004.

5. E. Bodden, K. Havelund. Racer: effective race detection using Aspectj. ISSTA, 2008.

6. M. Naik, A. Aiken, J. Whaley. Effective Static Race Detection for Java. PLDI, 2008.

7. Robert O'Callahan, Jong-Deok Choi. Hybrid Dynamic Data Race Detection. PPoPP'03, San Diego, California, USA, 2003.

8. Карпов А. Тестирование параллельных программ. (http://www.software-testing.ru/library/testing/functional-testing/5 81 -parallelprogramtesting)

9. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A dynamic data race detector for multithreaded programs. ACM Trans, on Computer Systems, 15(4), 1997.

10. Brian Davies. Whither Mathematics? Notices of the American Mathematical Society, dec. 2005, vol. 52, №11.

11. P. Emanuelsson, U. Nilsson A Comparative Study of Industrial Static Analysis Tools. Elsevier Science Publishers В. V. Amsterdam, The Netherlands, The Netherlands, 2008.

12. A. Deutsch. Interprocedural May-Alias Analysis for Pointers: Beyond k-limiting. In Proe. Programming Language Design and Implementation. ACM Press, 1994.

13. B. Steensgaard. Points-to Analysis in Almost Linear Time. In ACM POPL, 1996.

14. Калугин А. Верификатор программ на языке Си LINT. (http://www. viva64. com/go. php?url=224)

15. Карпов А. Что такое "Parallel Lint"? (http: //software, intel. com/ru-ru/articles/parallel-lint/)

16. Static Source Code Analysis Tools for C. (http://www.spinroot.com/static/)

17. Каличкин С.В. Обзор средств статической отладки. Новосибирск. С.-22. 2004.

18. Christian Terboven. Comparing Intel Thread Checker and Sun Thread Analyze. Center for Computing and Communication RWTH Aachen University, Germany. 2007.

19. Использование Thread Analyzer для поиска конфликтов доступа к данным (http://ru.sun.com/developers/sunstudio/articles/thausingru. html)

20. Anne Dinning and Edith Schonberg. An empirical comparison of monitoring algorithms for access anomaly detection. In Proceedings of the Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 1990. C. 1-10.

21. J. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Proceedings of the 1991 ACM/IEEE conference on Supercomputing, ACM Press, 1991. C. 24-33.

22. D. Perkovic and P. Keleher. Online data-race detection via coherency guarantees. In Proceedings of the 2nd Symposium on Operating Systems Design and Implementation (OSDI'96), 1996. C. 47-57.

23. T. Ball and S. Rajamani. The SLAM project: debugging system software via static analysis. In Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'02), ACM Press, 2002. C. 1-3.

24. M. Das. Unification-based pointer analysis with directional assignments. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI'00), ACM Press, 2000. C. 35-46.

25. David R. Chase, Mark Wegman, and F. Kenneth Zadeck. Analysis of pointers and structures. In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, June 1990. C. 296-310.

26. Mark Orlovich. On flow-insensitive points-to analyses. (http://www.cs.cornell.edu/eourses/es71 l/2005fa/slides/sepl3 .pdf)

27. Кудрин М.Ю., Прокопенко А.С., Тормасов А.Г. Метод нахождения состояний гонки в потоках, работающих на разделяемой памяти // Сборник научных трудов МФТИ. -М.: МФТИ, 2009. № 4. - Том 1. - С. 181-201.

28. Кудрин М.Ю. Выявление состояний гонки с помощью графа совместного исполнения потоков // Материалы международной научно-технической конференции "Компьютерные науки и технологии" Белгород: Изд-во БелГУ, 2009. - С. 45-46.

29. Кудрин М.Ю., Петров В.Н., Прокопенко А.С. Обнаружение состояний гонки в потоках, работающих на разделяемой памяти 11 Модели и методы обработки информации, сборник научных трудов М.: МФТИ, 2009. - С. 93-98.

30. Соколов Е.В., Кудрин М.Ю. Модель организации снимка памяти на основе nk-схемы при наложении ограничения типа темпа доступа // Модели и методы обработкиинформации, сборник научных трудов М.: МФТИ, 2009. - С. 197-205.

31. Кудрин М.Ю., Соколов Е.В. Выявление состояний гонки с помощью аппарата атрибутных грамматик // Научное творчество молодежи. Материалы XIII Всероссийской научно-практической конференции. Кемерово: Кемеровский гос. универ-т, 2009. - С. 112.

32. Соколов Е.В., Кудрин М.Ю. Алгоритмы снэпшота основанные на ограничении темпа доступа к памяти // Научное творчество молодежи. Материалы XIII Всероссийской научно-практической конференции. Кемерово: Кемеровский гос. универ-т, 2009. С. 125.

33. Кудрин М.Ю. Исследование цепочечных объектов // Совр. проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLVII научной конференции. / МФТИ, Долгопрудный, 2004.C. 74.

34. Chris Purcell, Tim Harris, Non-blocking hashtables with open addressing. University of Cambridge, 2005.

35. Intel Architecture Software Developer's Manual. Volume 13.

36. Акишев И. P. Разработка и анализ параллельных поисковых структур данных, нечувствительных к размеру кеша, бакалаврская работа, кафедра компьютерных технологий, СПбГУИТМО, 2008.

37. Philip N. Klein, Hsueh Lu, Robert Netze, Detecting Race Conditions in Parallel Programs that Use Semaphores. -Lecture Notes in Computer Science, Springer Berlin/Heidelberg, 2008.

38. Keir Fraser, Practical lock-freedom. University of Cambridge, 2004.

39. Slonneger K., Kurtz B, Formal syntax and semantics of programming languages. Addison-Wesley, 1995.

40. Серебряков В.А., Галочкин М.П., Гончар Д.P., Фуругян М.Г, Теория и реализация языков программирования. М.: МЗ Пресс, 2006.

41. Herlihy M. Impossibility and Universality Results for Wait-Free Synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, 1988. C. 276-290.

42. Peter M. Hines Symmetries and transitions of bounded Turing machines. CoRR , 1998.

43. Kohtaro Tadaki, Tomoyuki Yamakami, Jack C.H. Lin Theory of One Tape Linear Time Turing Machines Elsevier Science Publishers В. V., 2009.

44. Michiel Ronsse, Koen De Bosschere, Non-Intrusive on-the-Fly Data Race Detection Using Execution Replay, Automated And Algorithmic Debugging: Proceedings. Germany, 2000.

45. Lomet, D.B. Process structuring, synchronization, and recovery using atomic actions, In Proceedings of the ACM Conference on Language Design for Reliable Software . -ACM, NY, 1977. C. 128-137.

46. Shavit, N., Touitou, D. Software transactional memory, In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing. ACM, NY, 1995. - C. 204-213.

47. Herlihy, M., Moss, J.E.B. Transactional memory: Architectural support for lock-free data structures, In Proceedings of the 20th International Symposium on Computer Architecture. ACM, 1993. - C. 289-300.

48. Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal The combined power of conditions and failure detectors to solve asynchronous set agreement, Proceedings of Symposium on Principles of Distributed Computing. ACM, Germany, 2005.

49. G. Kliot, E. Petrank, B. Steensgaard, A lock-free, concurrent, and incremental stack scanning for garbage collectors, Proceedings of the 2009 ACM SIGPLAN/SIGOPSinternational conference on Virtual execution environments. -Washington, DC, USA, 2009.

50. Greg Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures. Velen, Germany, 1993. - C. 261-270.

51. H. Gao , W. H. Hesselink, A general lock-free algorithm using compare-and-swap. — Information and Computation, February, 2007. C. 225-241.

52. M. Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), November, 1993. C. 745-770.

53. E.H. Jensen, G.W. Hagensen, J.M. Broughton, A new approach to exclusive data access in shared memory multiprocessors, Technical Report of Lawrence Livemore National Laboratory, January, 1987.

54. Victor Luchangco , Mark Moir , Nir Shavit, Nonblocking k-compare-single-swap, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, San Diego, California, USA, 2003.

55. Nancy A. Lynch, Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996.

56. John D. Valois, Lock-free linked lists using compare-and-swap, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing. Ontario, Canada, 1995. - C. 214-222.

57. V. Balasundaram , K. Kennedy, Compile-time detection of race conditions in a parallel program, Proceedings of the 3rd international conference on Supercomputing. Crete, Greece, 1989. - C. 175-185.

58. Robert H. B. Netzer , Barton P. Miller, What are race conditions?: Some issues and formalizations. ACM Letters on Programming Languages and Systems (LOPLAS), 1992. -C. 74-88.

59. M. L. Scott. Non-blocking timeout in scalable queue-based spin locks. In PODC '02: Proc. of the Twenty-first Annual Symposium on Principles of Distributed Computing. ACM Press, NY, USA, 2002. - C. 31-40.

60. Карпов А., Рыжков E. Применение технологии статического анализа кода при разработке параллельных программ, (http://www.viva64.com/art-3-l-441110260.html)

61. L. Wang, S. D. Stoller. Run-time analysis for atomicity, Electronic Notes in Theoretical Computer Science, 89(2), 2003.

62. S. V. Adve, K. Gharachorloo. Shared memory consistency models: A tutorial. Computer, 29(12), 1996.

63. Т. Е. Anderson. The performance of spin lock alternatives for sharedmoney multiprocessors, IEEE Transactions on Parallel and Distributed Systems, 1(1):6-16, 1990.

64. N. S. Arora, R. D. Blumofe, and C. G. Plaxton. Thread scheduling for multiprogrammed multiprocessors. In Proc. of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures. ACM Press, USA, 1998. - C. 119-129.

65. H. Gao, J. F. Groote, W. H. Hesselink. Lock-free dynamic hash tables with open addressing, Distributed Computing, 18(1), 2005. C. 21-42.

66. D. Hendler, N. Shavit, L. Yerushalmi. A scalable lock-free stack algorithm. In SPAA '04: Proc. of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. ACM Press, NY, USA, 2004. - C. 206-215.

67. M. Herlihy, Y. Lev, N. Shavit. A lock-free concurrent skiplist with wait-free search. Unpublished Manuscript, Sun Microsystems Laboratories, Burlington, Massachusetts, 2007.

68. M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free data structures. In Proc. of the Twentieth Annual International Symposium on Computer Architecture. ACM Press, San Diego, California, 1993. - C. 289-300.

69. M.Bach. The design of the UNIX operating system. -Prentice Hall, Englewood Cliffs, N.J., 1986.

70. Intel Corporation. Pentium Processor User's Manual. Intel Books, 1993.http://www.intel.com/design/Pentium4/documentation.htm)

71. M. Li, J. Tromp, and P. M. B. Vit'anyi. How to share concurrent wait-free variables. Journal of the ACM, 43(4). -ACM Press, 1996. C. 723-746.

72. P. E. McKenney. Selecting locking primitives for parallel programming. Communications of the ACM, 39(10) ACMPress, 1996. С. 75-82.http://portal.acm.org/citation.cfm?id=236156.236174)

73. M. M. Michael, М. L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proc. of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing. ACM Press, 1996. - C. 267275.

74. M. Raynal. Algorithms for Mutual Exclusion. The MIT Press, Cambridge, MA, 1986.

75. P. Marginean, Lock-Free Queues, Dr. Dobb's Journal, July 2008.

76. Карпов В.E., Коньков К.А. Основы операционных систем. М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий», 2005.

77. Т. Кормен, Ч. Лейзерсон. Р. Ривест Алгоритмы: построение и анализ -М.: Москва, 2004.

78. Н. Sutter, The Trouble With Locks, C/C++ Users Journal, March 2005.

79. Herb Sutter, Lock-Free Code: A False Sense of Security, Dr. Dobb's Journal, 33(9), 2008.