Диссертация (1148255), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

работы [36, 46], а также работу [43] с более детальнойразновидностью той же нотации), подходящую и в данном случае. Пусть –процесс номер . При этом подразумеватся, что каждый процесс выполняетсяна отдельном узле. Операции чтения и записи будем обозначать соответственно и (от англ. read и write). Тройка () будет обозначать операцию1«Any read to a memory location returns the value stored by the most recent write operation to ». [46]25над памятью, где – вид операции ( или ), – обозначение адресуе­мого объекта (например, переменной), а – значение, являющееся входнымдля операции записи или же выходным в случае операции чтения.

Примемначальное значение всех переменных за 0. Расположим процессы системы повертикали, а шкалу времени по горизонтали (рис. 1.5).1 : ()12 :1 : ()1()1(а) Корректный вариант2 :()0 ()1(б ) Некорректный вариантРисунок 1.5 – Модель строгой консистентностиСлева (рис. 1.5, а) мы видим ситуацию, допустимую в модели строгойконсистентности: первый процесс записывает значение 1 в переменную , поз­же второй процесс считывает из переменной это значение. Однако справа(рис. 1.5, б ) ситуация уже иная – несмотря на то, что первый процесс уже за­писал в переменную значение 1, второй процесс сначала считывает из неезначение 0, и лишь затем, выполняя еще одну операцию чтения вдруг обнару­живает значение 1. Описанная ситуация на первый взгляд может показатьсяабсурдной и не соответствующей строгой модели консистентности (см.

опреде­ление 1 на стр. 24), однако далее будет показано, что в более слабых моделяхтакая ситуация оказывается допустимой. Более того, система может оставатьсяпри этом вполне предсказуемой и удобной для программирования.1.4.2. Последовательная консистентностьХотя, как было показано выше, строгой консистентности практическиневозможно достичь в распределённых системах, в параллельном программи­ровании она не используется даже в случае многопоточного программированияна единственном ядре.

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

При этом данная модель – самаястрогая из практически применимых в распределённых системах. Рассмотримопределение:Определение 2. Система соответствует модели последовательной конси­стентности в том случае, если результат любого выполнения системы все­гда такой же, как если бы операции со всех процессоров системы выполнялисьв некотором порядке, формируя общую последовательность операций, причемоперации каждого отдельно взятого процессора должны встречаться в этойобщей последовательности операций именно в том порядке, который опреде­лен программой этого процессора.1Из определения 2 следует, что операции могут выполняться в целом в лю­бой последовательности и с любыми задержками, однако операции каждого изпроцессоров должны сохранять свою последовательность, а операции всех уз­лов с общей памятью должны быть видны всем узлам упорядоченными в однуи ту же последовательность.

Хотя, от запуска к запуску, эта последователь­ность может выглядеть по-разному. На рисунке 1.6 представлено два вариантавыполнения одной и той же программы, причем оба варианта соответствуютопределению 2.Заметим, что рис. 1.5, б и 1.6, а совпадают – поведение, неприемлемоедля модели строгой консистентности оказывается допустимым в последователь­1«The result of any execution is the same as if the operations of all the processors were executed in somesequential order, and the operations of each individual processor appear in this sequence in the order specified byits program». [31]271 : ()12 :1 : ()1()0 ()12 :(а) Вариант 1()1 ()1(б ) Вариант 2Рисунок 1.6 – Модель последовательной консистентностиной модели.

Не важно, когда «реально» произошла операция записи на про­цессоре 1 – процессор 2 может «увидеть» её как до своих операций чтения(рис. 1.6, б ), так и в любой другой момент времени, например, между двух сво­их операций чтения (рис. 1.6, а). Главное, что все узлы в системе должны иметьединое видение последовательности этих операций – таким образом, недопусти­ма ситуация, когда один узел воспринимает происходящее как на рисунке 1.6, а,а другой – как на рисунке 1.6, б . Такая недопустимая ситуация изображена нарисунке 1.7.1 : ()12 :()0 ()13 :()1 ()1Рисунок 1.7 – Ситуация, недопустимая в модели последовательной консистентностиДалее обзорно ознакомимся с другими «глобальными» моделями и перей­дем к моделям, основанным на синхронизирующих операциях, позволяющимзаметно повысить производительность, поддерживая консистентность толькона определенных участках выполняющейся программы.1.4.3.

Другие глобальные моделиТак как ослабление модели (введение в нее новых ограничений и допу­щений) позволяет добиться более высокой производительности, было созданомножество альтернативных моделей, применимых в каких-либо частныхслучаях. Наиболее известны следующие модели:28– Причинная– PRAM– ПроцессорнаяПричинная модель акцентирует наше внимание на том, что не имеет смыс­ла контролировать порядок всех обращений к общей памяти, важна лишь по­следовательность операций, потенциально влияющих друг на друга.

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

Такую модель легкореализовать, но разрабатывать конечное ПО в такой модели – задача нетриви­альная.Процессорная модель добавляет к условиям PRAM модели еще одно – по­рядок операций записи в общую память должен все-же видеться на всех узлаходинаково.Тем не менее, модель последовательной консистентности остается самой«понятной» и использовалась наиболее широко вплоть до появления нового под­хода к ослаблению модели, основанного на операциях синхронизации. Данныйподход породил группу моделей, описанных ниже, и внимание современных ис­следователей сместилось к ним. Данные модели необходимо рассмотреть болеевнимательно, так как именно на них основано новое решение, выработанное висследовании, которому посвящена данная диссертация.291.4.4.

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

В остальных же участках кода такой гарантии не будет, как не будет инакладных расходов на пересылку данных между узлами. Строгое определениебыло сформулировано следующим образом:Определение 3.1Система соответствует модели слабой консистентно­сти, если выполняются следующие условия:1. Доступ к синхронизационным переменным осуществляется в модели по­следовательной консистентности.2. Доступ к синхронизационной переменной выполняется только послеокончания операций записи в общую память во всех других узлах.3. Доступ к общей памяти выполняется только после завершения теку­щих операций с синхронизационной переменной.Таким образом, через обращение к глобальной (распределённой) синхрони­зационной переменной можно обозначить начало и конец критической секции,входя в которую, процесс должен быть уверен в актуальности распределённых1Основано на определении из работы [20]:1. accesses to global synchronizing variables are strongly ordered and if2.

no access to a synchronizing variable is issued in a processor before all previous global data accesses havebeen performed and if3. no access to global data is issued by a processor before a previous access to a synchronizing variable hasbeen performed.30данных, и, в свою очередь, гарантируя актуальность распределённых данныхпосле своей работы с ними по выходу из критической секции. Состояние общейпамяти вне критической секции не определено.

При этом только один процессодновременно может находиться в критической секции.За счет кардинального сокращения обмена данными (теперь он стал требо­ваться только при входе в критическую секцию и выходе из нее), модель оказа­лась гораздо эффективнее модели последовательной консистентности. Тем неменее, новую модель всё-таки можно рассматривать именно как модель последо­вательной консистентности, лишь с одним дополнением: модель выдерживаетсятолько в пределах критических секций.1.4.5. Консистентность по выходуСлабая консистентность была существенным шагом в задаче повышенияпроизводительности, однако не разделяла ситуации «вход в критическую сек­цию» и «выход из секции», требуя в любом случае завершения всех активныхопераций с общей памятью (распространения информации о них по всем узламвычислительной системы).

Модель консистентности по выходу усовершенство­вала слабую модель, разграничив эти две ситуации, соответствующие операциинад синхронизационной переменной были названы «захват» и «освобождение»(англ. acquire и release соответственно). Впервые модель была предложена вработе [35], и определена следующими правилами:Определение 4.1Система соответствует модели консистентности повыходу, если выполняются следующие условия:1Основано на определении из работы [35]:1.

Характеристики

Список файлов диссертации