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

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

БАБИЧЕВ Сергей Леонидович

Статический анализ проблем синхронизации параллельных алгоритмов в вычислительных системах

с общей памятью

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

АВТОРЕФЕРАТ

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

Г л г-о

Москва-2012

005020305

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

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

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

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

Тормасов Александр Геннадьевич

доктор физико-математических наук кафедра теоретической и прикладно" информатики Московского физико технического института, заведующий кафедрой

Прохоров Сергей Петрович

кандидат физико-математических наук, доцент, Институт системного

программирования РАН, ведущий научный сотрудник

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

Вычислительный центр им. А. А. Дородницына РАН

Защита состоится

2012

г.в У час. ин.

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

С диссертацией можно ознакомиться в библиотеке МФТИ Автореферат разослан " ^¿и^/О ^^ 2012 г.

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

Федько Ольга Сергеевна

Общая характеристика работы

Актуальность проблемы

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

Цель исследований

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

В соответствии с поставленной целью основными задачами являются:

1. Исследование существующих подходов и моделей анализа параллельных алгоритмов и их применимости на практике.

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

3. Реализация оригинальных высокоэффективных верифицированных алгоритмов для применения в библиотеках программ и комплексах программ.

Методы исследований

Для решения поставленных задач применялись методы теории вероятностей, теория массового обслуживания, теория сетей Петри, теория

формальных языков, теория множеств и комплектов, теория графов, линейная алгебра.

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

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

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

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

Апробация работы

Научные и практические результаты диссертации доложены, обсуждены и получили одобрение специалистов на:

- IL, L, LI, LU, LUI научных конференциях МФТИ (Москва, 2007-2011)

- научных семинарах кафедры информатики МФТИ (Москва, 2007-2011)

- научных семинарах кафедры математических и информационных технологий МФТИ (Москва, 2007-2011)

- научном семинаре ВЦ РАН (Москва, 2012)

- семинаре группы сопровождения переносной вычислительной техники ОАО Альфа-Банк (Москва, 2008)

- научном семинаре отдела безопасности ОАО БИНБАНК (Москва, 2007)

- научно-практическом семинаре Департамента защиты информации ОАО «ТНК-BP Менеджмент» (Москва, 2010)

- семинаре административного отдела ООО «Прогресстех» (Москва, 2011)

- семинаре отдела защиты информации «ОАО ЛУКОЙЛ» (Москва, 2009)

- научно-технических семинарах Департамента системной интеграции ОАО «Форт-Диалог» (Набережные Челны, 2009-2011)

- семинаре отдела ЭВТ ООО «Татнефть» (Нурлат, 2008) и других.

Публикации

По теме диссертации опубликовано 9 работ, в том числе две [8,9] - из списка изданий, рекомендованных ВАК РФ.

Личный вклад автора

Лично соискателем в опубликованных работах выполнено:

• теоретическая разработка методов верификации параллельных программ;

• построение, исследование и оптимизация математических моделей параллельных вычислений;

• разработка и реализация основных алгоритмов;

• вычислительные эксперименты;

Структура работы

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

Содержание работы

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

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

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

Понятие сетей Петри

Обычная сеть Петри есть С = где Р - множество позиций,

Т есть множество переходов, /гс(Рх7,)и(7'хР) - множество направленных дуг и //0:Р—- начальная маркировка, где е[0,оо) Множество входных переходов из позиции р обозначается как 'р, множество выходных переходов из позиции р, соответственно, как р'. Подобно этому, множество входных (соответственно, выходных позиций) для перехода / обозначается как 7 (соответственно /'). Для любого подмножества позиций 5, '5 обозначает множество переходов, содержащих по крайней мере одну выходную позицию, принадлежащую 5.

Соответственно, 5' обозначает множество переходов, содержащих по меньшей мере одну входную позицию, принадлежащую 51.

Переход / разрешён или запускаем в //0 если для всех р > 1.

При запуске перехода / новая маркировка /л производится удалением одного маркера из и помещением одного маркера в Этот

процесс обозначается как Расширение запуска обозначается как

3(/л,сг)> р', где ¡л - маркировка, а - последовательность переходов, переводящих ц в //. Множество допустимых в данной маркировке ц переходов обозначим как £)(//), количество таких переходов как | £>(//) |. Множество всех маркировок, достижимых из обозначается как Я(/иа). Если из маркировки ц все переходы г; неразрешены, то | О(р) |= О

Матрица инцидентности С = [с^] такова, что сц = 1, если tJ ер,\р1'; Су = -1, если tj е р. ~'\р,; сь. = 0 в остальных случаях. Для любого ц такого, что 8{рй,а) > //, // = //0 + Со, где а называется вектором количества запусков - таким вектором, в котором /-й элемент обозначает количество вхождений в а. Вектор неотрицательных целых уф О такой, что С = О

называется /-инвариантом. ?-инвариант у называется минимальным, если не существует ! -инвариант х такой, что х<у. Подобно, вектор неотрицательных целых х * 0 такой, что х'С = 0 называется р — инвариантом.

Свойства сетей Петри как средства анализа исполнительных потоков многопоточных программ. 1. Последовательное исполнение

~Ц !—

\___у

Рг

1, «,

Переход ¿2 может быть запущен только после запуска перехода /, 2. Синхронизация

Переход может быть разрешён только при условии наличия маркеров в позициях р[ и р2 3. Слияние

> -

Маркеры из нескольких позиций участвуют в переходе. 4. Параллельное исполнение

г, I © ;

Л Р<

1/1Л

Переходы 1г и г3 исполняются параллельно. 5. Моделирование конфликтов

Р1

(О]

с )

ф'] <1

Совершение любого из переходов и /2 делает невозможным совершение другого перехода

Определение наличия тупиков в сети Петри сводится к задаче определения одной из характеристик сети Петри — активности (Пуепезз).

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

Для анализа тупиков в сети С с начальной маркировкой //0 применяется следующая классификация:

Активность уровня 0 имеет переход I], который никогда не может

быть запущен.

Активность уровня 1 имеет переход iy., который потенциально

запустим, то есть существует такая допустимая и достижимая маркировка // с R(/u0), в которой данный переход разрешён.

Активность уровня 2 имеет переход tj, если для всякого целого и существует последовательность запусков, в котором Г присутствует по крайней мере п раз.

Активность уровня 3 имеет переход t}, если существует бесконечная

последовательность запусков, в которой tj присутствует неограниченно часто.

Активность уровня 4 имеет переход tj, если для всякой /л е К(м0) существует такая последовательность запусков <х, что Г разрешён в <5(р',<т)

Наличие в сети переходов с активностью 0 с определённостью подтверждает наличие тупиков в моделируемой системе.

Сеть Петри не содержит тупиков, если для любой достижимой маркировки имеется по крайней мере один разрешённый переход.

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

Подмножество позиций S называется сифоном (syphon), если любой входящий переход в S является также выходящим переходом в S, то есть 'ScS'. Соответственно, 5 есть ловушка (trap), если S' c'S1. Сифон (ловушка) называется минимальным, если он не содержит других сифонов (ловушек).

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

Метод дерева достижимости заключается в рекурсивном применении алгоритма добавления узла в дерево достижимости.

Метод сведения к задаче математического целочисленного программирования основывается на следующем:

Введём две функции от сифона S:

f(S) = min{v(S)\v£R(vо)]} (О

где ju(S) есть общее количество маркеров в S, то есть, //(5) =

peS

F(S) = min{p(S) \p = /u + CY,/j>0,Y>0} (2)

где С есть матрица инцидентности сети Петри, ц - маркировка сети, и Y есть вектор.

/л = pa + CY называется уравнением состояния сети. Из базовой теории сетей Петри следует, что любая достижимая маркировка ц удовлетворяет уравнению состояния, но обратное неверно.

Сифон S есть потенциальный тупик тогда и только тогда, когда f(S) = 0.

Это подразумевает, что F(S)> f(s). Следовательно, любой сифон S такой, что F(S) > 0, не является потенциальным тупиком. Таким образом, сеть Петри не содержит тупиков, если каждый сифон S данной сети либо содержит маркированную ловушку, либо F(S) > О.

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

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

Пусть {SpiSj,...,^} есть множество минимальных сифонов, которые не содержат маркированных ловушек. Сеть Петри не содержит тупиков, если F > 0, где

F = min {¿z,//(*,)\M = Mo+CY,±zi = \,v>0,Y> 0,z, > 0} (3) i=i i-i

Во избежание явного перечисления предпочтительнее использовать выражение F(S), определённое следующим образом:

F(S) = min{fi{S) | fi = Mo + CY, ц > 0, Y > 0} (4)

где С есть матрица инцидентности сети Петри, а ¡1 и Y есть вектора чисел. Любой сифон S такой, что F(S) > 0 не является потенциальным тупиком.

(4) - задача линейного программирования и может быть разрешена за полиномиальное время. Использование линейного программирования требует проверки всех минимальных сифонов и эффективность данного метода зависит от их количества.

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

Пусть

Т- множество переходов сети Петри, F œ(PxT)kj(TxP) есть множество направленных дуг,

vp = l ,{ptS},

z,>Ev„-ri|+l .Vier,

Pst

vpZz„V(t,p)eF,

M = V0+CY, fi> 0, Г>0,

= M/iJ vp ,

peP

Сеть Петри не содержит тупиков, если =| Р |.

Поскольку оптимизация ведётся по двоично определённым векторам индикаторов v и z, становится возможным использовать методы бинарного целочисленного программирования.

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

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

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

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

Общая идея алгоритма состоит в следующем:

1. Найти простой сифон.

2. Найти минимальный сифон, содержащийся в простом сифоне

3. Применить условия ограничения для декомпозиции задачи и для

каждой подзадачи (содержащей подсети и некоторые ограничения по позициям) применить процедуру, начиная с шага 1. Условия ограничения определяются следующей леммой:

Лемма ограничения

Пусть G = (P,T,F) есть сеть Петри и P = {pl,p2,...,pn}czP. Множество сифонов G, не содержащее Р равно и"=1, где Z, есть множество сифонов редуцированной сети G¡=red(G,P-{pi}),i~\,...,n, содержащих {px,p2,...,p¡A}.

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

Пусть G = (P,T,F) есть сеть Петри. Следующая функция, FindSiphon{G,P) может быть использована для нахождения сифонов в G, которые содержат специфическое множество позиций Р. Точнее говоря, она возвращает пустое множество если в G не имеется таких сифонов или простой, не обязательно минимальный сифон, если G содержит искомое множество.

Алгоритм 1 - FindSiphon{G,P)

1. если Бр е Рс\ Р такая, что 31 е'p,t € Р , тогда return 0

2. если 3реР-Р такая, что 3/ е'p,t i. Р', тогда идти к шагу 3 иначе return Р

3. G = red(G,P-{p}), идти к шагу 1

Алгоритм 2 - FindMinimalSiphon(G,S ,Р)

1. если 3\pe(P—P)niS такая, что или t n5 = 0,Ví ер' идти к шагу 2 иначе идти к шагу 3

2. S = S - {р}; идти к шагу 1

3. если S <zP тогда G = red(G,S)

4. Pim =P-P

5. если P)lm = 0 тогда return S

6. Gp=red(G,P-{p}-),pePm

7- Pm = Pm-{p})

8. Sp = FindSiphon(Gp, P)

9. если S & 0 тогда S = S , идти к шагу 3 иначе идти к шагу 5

Следующая функция, FindAUMinSiphons(G,P) реализует алгоритм, неформально введённый в начале раздела и находит все минимальные сифоны в G, содержащие специфическое множество позиций Р, если они существуют. Функция возвращает пустое множество, если таких сифонов нет.

Алгоритм 3 - FindAUMinSiphons(G,P) 1. 2 = 0

2. если Р = 0 и 3реР такая, что '/7 = 0, тогда идти к шагу 3 иначе идти к шагу 4

3. S = {р); £ = Е vj {S}; G = red(G, Р - {р}); идти к шагу 2

4. S = FindSiphon(G, Р)

5. если S =0 то returnl, 6.5 = FindMinSiphon(G, S, Р) 7. E = Eu{5}

8- P„=S-?;PM = 0

9. если P„ew=0 то returnX 10 .Gp = red(G,P-{P}),PePnew

11. Zp = FindAllMinSiphons(Gp,P u PnU)

12.E = SuZ

P

13 • = P„nv - {p}, РоИ = Р,м u {p}; идти к шагу 8

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

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

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

Примитив типа Mutex

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

WaitAndLock - ожидать освобождения с немедленным захватом Release - освобождение

,о

WaitAndLock

Рис. 1. Схема сети Петри примитива Mutex

Примитив Mutex можно представить в виде сети Петри - см. рис. 1.

Наличие в позиции Р1 маркера показывает, что Mutex находится в свободном состоянии. Эта позиция должна использоваться совместно несколькими вычислительными потоками. При появлении маркера в позиции РО и наличии маркера в позиции Р1 становится возможным переход ТО, маркер в позиции РО теперь не присутствует, что делает невозможным осуществление переходов, зависящих от наличия маркера в позиции Р1.

После захвата маркера вычислительный поток исполняет код критической секции (позиция Р2), исполняется переход Т1, который передаёт маркер в позицию Р1, делая тем самым возможным осуществление связанных с наличием маркера в этой позиции переходов.

Данная сеть Петри соответствует общепринятой семантике примитива Mutex.

Примитив типа Event

Примитив типа Event используется для установления факта возникновения какого-либо события, может находиться в двух состояниях -сигнальном и несигнальном и к нему применимы следующие операции:

Set - установить объект в сигнальное состояние

Reset - установить объект в несигнальное состояние

Wait - ожидать наступления сигнального состояния.

В настоящей работе рассматривается вариант объектов типа Event, требующий ручного перевода состояния в несигнальное после того, как-ровно один из вычислительных потоков получил к нему доступ. Учитывается следующий факт: если примитив Event находится в сигнальном состоянии, то

любое количество последующих исполнений операции Set оставляет объект в сигнальном состоянии. Если примитив Event находится в несигнальном состоянии, то любое количество последующих исполнений операции Reset оставляет объект в несигнальном состоянии. Данные условия приводят к более точной и более сложной модели, чем в литературе.

Рис. 2. Схема сети Петри примитива Event

На рис. 2 изображена сеть Петри для примитива Event.

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

Операция Reset в данной модели начинается помещением маркера в позицию Р6, входную позицию операции. Завершение операции Reset определяется появлением маркера в позиции Р8. Эта операция переводит объект Event в несигнальное состояние в независимости от первоначального состояния объекта.

Позиция РЗ является входной позицией для операции Wait. Если в позиции РЗ уже имеется маркер, то метод Wait завершается успехом немедленно. Если в позиции РЗ маркера не имеется, то исполнение операции Wait задерживается до появления маркера в этой позиции.

В работе доказана теорема о том, что представленная сеть Петри для примитива Event соответствует семантике данного примитива.

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

Совокупная сеть Петри вычислительной модели может формироваться как вручную, так и автоматизированным способом. Автоматизированный

Evenl

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

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

Грамматический анализ осуществляется с помощью LALR(l) автомата, генерируемого программой bison по описанию синтаксических правил входного языка. При грамматическом анализе создаются структуры данных, требуемые как для семантического анализа, так и для генерации кода -таблица символов и синтаксическое дерево. После построения синтаксического дерева для построения совокупной сети Петри модели по таблице символов строится скелетная часть создаваемой сети Петри а по синтаксическому дереву добавляются необходимые связи переходами и позициями а так же добавляются необходимые для этого переходы и позиции. Для этого используется оригинальный алгоритм реперных точек, описанный в диссертации.

Этап оптимизации анализирует сгенерированную сеть Петри и удаляет из неё избыточные фрагменты. Алгоритм этапа оптимизации описан в диссертации.

Классический пример задачи, содержащей тупики, представлен на формализованном языке описания модели следующим образом:

shared mutex ml;

shared mutex m2;

shared thread firstThread { forever { ml.wait; @workl; m2 .wait; @work2; m2. release; ml. release;

}

>

shared thread secortdThread { forever { m2.wait; @workl; ml.wait; (8work2; ml.release; m2.release;

}

}

По данному исходному коду сформирована сеть Петри, показанная на

рис. 3.

Рис. 3. Сеть Петри, сформированная по описанию задачи на формализованном языке описания модели.

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

Были проверены на наличие или отсутствие тупиков большое количество известных примеров, в том числе Apache deadlock bug #42031, i проблема обедающих философов и другие. Результаты проверки подтвердили соответствие результатов верификации теоретическим.

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

Пул вычислительных потоков (ЛВП)

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

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

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

Требования, накладываемые на реализацию ПВП:

1. должны быть поддержаны языки программирования С и С++;

2. время, затрачиваемое на накладные расходы, должно быть как можно более малым;

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

4. не должно быть значительных периодов активного ожидания;

5. должна быть возможность использования механизма в ядре операционной системы.

Организация ПВП и методы работы с пулом

Возможны два принципиально разных методов организации ПВП - со статическим планированием и с динамическим планированием.

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

В данной работе принят механизм статического планирования.

Оптимизация использования ПВП

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

Описание алгоритма функционирования обработки запросов ввода/вывода

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

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

Главный поток

Поток пула

Рис. 3. Синтезированная сеть Петри для задачи пула облегчённых вычислительных потоков с одним дополнительным потоком.

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

shared mutex DataLockMutex; shared event DataReadyEvent; shared event ResultReadyEvent; thread mainThread { forever {

DataLockMutex.wait; DataReadyEvent.set; (iiworkl;

ResultReadyEvent.wait; DataLockMutex.release; ResultReadyEvent.reset;

}

}

thread PoolThreadl { forever {

DataReadyEvent.wait; @work2;

DataReadyEvent.reset; ResultReadyEvent.set;

}

}

Данная модель была транслирована в сеть Петри, результат показан на рис. 3.

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

Апробация модели.

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

Типичная обработка запросов ввода-вывода

Рис. 4. Схема преобразования операций ввода-вывода.

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

Оптимизированная обработка запросов ввода-вывода

сС ш

Т~|______

I_1 ^^-зоваіще—^

сі

ш

§ б

Рис. 5. Оптимизированная схема преобразований ввода/вывода.

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

Результаты

Для различных криптографических алгоритмов была измерена скорость криптографического преобразования и использованием ПВП с тремя дополнительными вычислительными потоками на вычислительной

системе, состоящей из процессора Intel ¡5-2500К, работающего на тактовой частоте 4000 мегагерц с отключенным механизмом TurboBoost.

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

В заключении сформулированы основные результаты диссертационной работы.

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

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

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

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

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

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

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

7. Предложенные алгоритмы реализованы в виде комплекса программ.

Публикации по теме диссертации:

1. Бабичев С. Л., Головатский М. А., Коньков А. К., Царин А. А., Коньков

К. А. Защита информации в операционной среде Microsoft Windows. //

Современные проблемы фундаментальных и прикладных наук. Часть

VII. Прикладная математика и экономика: Труды XLVIII конференции МФТИ./ М.- Долгопрудный, 2005- С. 151.

2. Семененко В. Л., Бабичев С. Л., Бобьяков А. С., Коньков А. К, Коньков К. А., Телиг{ын М. А. Защита корпоративной информации от внутренних угроз на основе метода доверенной загрузки системы // Современные проблемы фундаментальных и прикладных наук: Труды 50-й научной конференции МФТИ/ М.- Долгопрудный, 2007- С. 174175.

3. Бабичев С. Л., Коньков А. К, Коньков К. А. Дополнительная защита ресурсов операционной системы методом криптографической защиты данных // Сборник научных трудов МФТИ. Моделирование процессов обработки информации/ М.:МФТИ, - 2007- С. 251-259.

4. Бабичев С. Л., Бобьяков А. С., Коньков А. К, Коньков К. А. Математическая модель защищенной компьютерной системы под управлением Windows// Современные проблемы фундаментальных и прикладных наук: Труды 51-й научной конференции МФТИ./ М.Долгопрудный, 2008- Т 2. С. 56-57.

5. Бабичев С. Л., Бобьяков А. С., Коньков А. К, Коньков К А. Эффективное использование ресурсов вычислительных систем при решении задач информационной безопасности.// Современные проблемы фундаментальных и прикладных наук. Часть VII Управление и прикладная математика: Труды 52-й научной конференции МФТИ./ М.-Долгопрудный, 2009- Т 3. С.7-8.

6. Бабичев С. Л., Коньков А. К., Коньков К. А. Об оптимальном использовании ресурсов вычислительной системы для реализации модифицированной защищенной среды.// Современные проблемы фундаментальных и прикладных наук. Часть VII Управление и прикладная математика.: Труды 53-й научной конференции МФТИ./ М.-Долгопрудный, 2010- Т 2, С. 11-13

7. Бабичев С. Л., Коньков А. К, Коньков К. А. Автоматизированный анализ проблем синхронизации параллельных алгоритмов в вычислительных системах с общей памятью.// Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе. Управление и прикладная математика: Труды 54-й научной конференции МФТИ./ М.Долгопрудный-Жуковский. 2011-Т2. С.48-49.

8. Бабичев С. Л., Коньков А. К, Коньков К. А. Использование пула вычислительных потоков со статическим планированием для оптимизации подсистемы защищенных виртуальных носителей модифицированной защищенной среды.// Труды МФТИ, 2012- Т. 4, № 15(3)- С. 10-19.

9. Бабичев С. Л., Коньков А. К, Коньков К. А. Применение сетей Петри для диагностирования проблем синхронизации в вычислительных системах с общей памятью.// Труды МФТИ, 2012- Т. 4, № 14(2)- С. 1320.

Бабичев Сергей Леонидович

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

АВТОРЕФЕРАТ

Подписано в печать 11.03.2012 Формат 60 ' 84 1/16. Усл. печ. л. 1,0. Тираж _80_ экз. Заказ № 727. Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

61 12-1/741

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

УДК 519.713

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

БАБИЧЕВ СЕРГЕИ ЛЕОНИДОВИЧ

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

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

и комплексы программ

ДИССЕРТАЦИЯ

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

Научный консультант:

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

доцент К. А. Коньков

ДОЛГОПРУДНЫЙ - 2012

Содержание

Стр.

Список сокращений 5

ВВЕДЕНИЕ 6

Глава 1. ОБЗОР ОСНОВНЫХ МЕТОДОВ И МОДЕЛЕЙ 10

1.1. Развитие современных вычислительных систем и его влияние на архитектуру программ..........................10

1.2. Обзор работ по теме...........................15

1.3. Сети Петри как инструмент моделирования дискретных систем . . 21

1.4. Терминология сетей Петри.......................21

1.5. Свойства сетей Петри как средства анализа исполнительных потоков многопоточных программ......................22

1.5.1. Последовательное исполнение ....................23

1.5.2. Синхронизация.............................23

1.5.3. Слияние.................................24

1.5.4. Параллельное исполнение.......................24

1.5.5. Моделирование конфликтов .....................24

1.6. Классификация сетей Петри......................25

1.6.1. Классификация активностей.....................26

1.6.2. Сифоны и ловушки..........................27

1.6.3. Применимость сифонов и ловушек в задачах определения тупиков 27

1.7. Резюме ..................................29

Глава 2. МЕТОДЫ АНАЛИЗА СЕТЕЙ ПЕТРИ 30

2.1. Методы анализа активности сетей Петри...............30

2.2. Метод дерева достижимости......................30

2.2.1. Алгоритм построения дерева достижимости............30

2.3. Метод сифонов и ловушек .......................32

2.3.1. Теорема о минимальных сифонах..................32

2.3.2. Теорема о задаче квадратичного программирования........33

2.3.3. Метод математического программирования.............36

2.3.4. Метод минимальных сифонов ....................38

2.4. Сравнение методов............................42

2.5. Резюме ..................................44

Глава 3. СИНТЕЗ СОВОКУПНОЙ МОДЕЛИ 46

3.1. Примитивы синхронизации.......................46

3.1.1. Соглашения о терминологии.....................46

3.1.2. Примитив типа Mutex.........................47

3.1.3. Примитив типа Event.........................49

3.1.4. Действие типа Thread.........................56

3.1.5. Точка исполнения Action.......................57

3.2. Синтез совокупной сети Петри.....................58

3.2.1. Формализованный язык описания модели..............59

3.2.2. Лексический анализ..........................59

3.2.3. Грамматический анализ ФОЯМ...................60

3.2.4. Структуры данных грамматического анализа...........62

3.2.5. Построение синтаксического дерева.................62

3.2.6. Оптимизация..............................63

3.2.7. Исследование свойств совокупной сети Петри...........64

3.3. Примеры использования.........................64

3.3.1. Классический пример тупика........................64

3.3.2. Проблема синхронизации Apache deadlock bug #42031 ............68

3.3.3. Проблема обедающих философов..................70

3.4. Резюме ..................................72

Глава 4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МЕТОДОВ АНАЛИЗА 73

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

4.2. Пул вычислительных потоков (ПВП) .................73

4.2.1. Требования, накладываемые на реализацию ПВП.........74

4.2.2. Организация ПВП и методы работы с пулом............74

4.2.3. Оптимизация использования ПОВП.................76

4.2.4. Операции ПОВП............................78

4.2.5. Использование ПОВП для обработки запросов ввода-вывода ... 79

4.3. Апробация модели - драйвер-фильтр ввода/вывода.........84

4.4. Апробация модели - решение задачи целочисленного математического программирования ........................89

4.5. Резюме ..................................95

ЗАКЛЮЧЕНИЕ 97

СПИСОК ИСПОЛЬЗОВАННЫХ МАТЕРИАЛОВ 100

Список сокращений

ЗВН — защищённые виртуальные носители

МЗС — модифицированная защищённая среда

ПОВП — пул облегчённых вычислительных потоков

ПВП — пул вычислительных потоков

ФЯОМ — формализованный язык описания модели

ЯВУ — язык высокого уровня

ВВЕДЕНИЕ

Актуальность

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

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

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

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

В работе:

1. разработана новая конкретизация сети Петри для модели примитива синхронизации Event;

2. доказана теорема о маркировках, содержащих специальное значение счётчика маркеров

3. доказана теорема о соответствии предложенной сети Петри семантике примитива синхронизации Event;

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

5. реализованы три алгоритма обнаружения тупиков в синтезированных транслятором сетях Петри, проведены вычислительные эксперименты для сравнения применимости методов;

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

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

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

Апробация работы.

Научные и практические результаты диссертации доложены, обсуждены и получили одобрение специалистов на:

• 48,49,50,51,52,53 научных конференциях МФТИ (Москва, 2007-2011);

• научных семинарах кафедры информатики МФТИ (Москва, 2007-2011);

• научных семинарах кафедры математических и информационных технологий МФТИ (Москва, 2007-2011);

• семинаре группы сопровождения переносной вычислительной техники ОАО Альфа-Банк (Москва, 2008)

• семинаре отдела безопасности ОАО БИНБАНК (Москва, 2007)

• научно-практическом семинаре Департамента защиты информации ОАО "ТНК-ВР Менеджмент"(Москва, 2010)

• семинаре административного отдела ООО "Прогресстех" (Москва, 2011)

• семинаре отдела защиты информации "ОАО ЛУКОЙЛ "(Москва, 2009)

• научно-технических семинарах Департамента системной интеграции ОАО "Форт-Диалог"(Набережные Челны, 2009-2011)

• семинаре отдела ЭВТ ООО "Татнефть"(Нурлат, 2008) и других.

По теме диссертации опубликовано 9 печатных работ, из них в реферируемых журналах — 2.

Объем и структура диссертации.

Диссертация изложена на 106-х страницах машинописного текста и состоит из введения, обзора литературы, основных методов и моделей исследования, трёх глав собственных исследований, заключения, библиографического указателя. Работа иллюстрирована 20-ю рисунками, 3-мя таблицами. Библиография включает 19 отечественных и 44 иностранных источников. Весь материал, представленный в диссертации, получен, обработан и проанализирован автором лично.

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

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

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

Глава 1

ОБЗОР ОСНОВНЫХ МЕТОДОВ И МОДЕЛЕЙ

1.1. Развитие современных вычислительных систем и его влияние на архитектуру программ

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

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

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

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

Таким образом, тенденция развития вычислительных систем ставит нас

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

Внесение многопоточности в программы приводит к тому, что становятся актуальными проблемы, связанные с синхронизацией вычислительных потоков между собой. Все такие проблемы связаны с недетерминизмом поведения вычислительных потоков и к ним относятся условия гонок (race conditions), тупики (deadlocks) и потеря сигналов (signals lost).

Условия гонок возникают, если набор активности процесса недетермини-рован, то есть, при исполнении одного и того же набора входных данных процесс может давать разные результаты в зависимости от взаимного порядка исполнения. Для борьбы с возникновением условия гонок применяются примитивы синхронизации. Типичным сценарием использования ресурса являются так называемые критические секции, в которых использование ресурса ограждено использованием примитива синхронизации.

Таким образом при использовании совместного ресурса возникают следующие фазы: фаза блокировки, фаза использования, фаза разблокировки.

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

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

ситуация не может быть изменена.

Условия возникновения тупиков [14]:

1. Условие взаимоисключения. Одновременно использовать ресурс может только один поток.

2. Условие ожидания ресурсов. Потоки удерживают выделенные им ресурсы и могут запрашивать другие ресурсы.

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

4. Условие кругового ожидания. Существует кольцевая цепь потоков, в которой каждый поток ждёт доступа к ресурсу, удерживаемому другим потоком цепи.

Для образования тупика необходимым и достаточным является выполнение всех четырёх условий.

Третья основная проблема синхронизации - потеря сигналов - возникает, например, в том случае, когда процесс В ожидает какого-либо события, процесс А посылает процессу В сигнал о завершении этого события, но процесс В завершается до момента приёма события.

Примитивы синхронизации можно разделить на примитивы с активным ожиданием и с ожиданием события.

Первый тип примитивов синхронизации (к ним относятся, в частности, spinlock и interlocked операции) основывается на возможности потока совершать атомарные транзакции с памятью, например, atomic_increment или atomic_exchange. Несколько потоков используют одну и ту же переменную для синхронизации между собой. Если первый поток захватил примитив синхронизации, связанный с этой переменной, то второй поток будет исполнять операцию ожидания в цикле до тех пор, пока первый поток на освободит её. Из этого факта следует несколько выводов:

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

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

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

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

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

• обязательно происходит переключение контекста, на это затрачивается значительное время, которое не может быть отнесено на счёт продук-

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

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

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

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