Диссертация (1148255), страница 6
Текст из файла (страница 6)
before an ordinary LOAD or STORE access is allowed to perform with respect to any other processor,all previous acquire accesses must be performed, and2. before a release access is allowed to perform with respect to any other processor, all previous ordinaryLOAD and STORE accesses must be performed, and3. special accesses are processor consistent with respect to one another.311. Перед осуществлением доступа к общей памяти все предшествующиеоперации данного процессора по захвату синхронизационной переменнойдолжны быть завершены.2.
Операция освобождения синхронизационной переменной должна бытьвыполнена только после того, как все предшествующие операции данного процессора над общей памятью будут завершены.3. Операции захвата и освобождения синхронизационной переменнойдолжны подчиняться модели процессорной консистентности.В работе [35] показано, что требования процессорной консистентности вданном случае достаточно, при этом операции внутри критической секции можно считать упорядоченными согласно модели последовательной консистентности.При этом, операция захвата не гарантирует того, что локально произведенные операции над общей памятью будут немедленно распространены по всемузлам сети (лишь гарантирует то, что операции других узлов в данный моментбудут обнаружены).
А опреация освобождения также не гарантирует моментального получения информации об операциях, произведенных на других машинах (зато обеспечивает распространение информации о произведенных внутрикритической секции операциях).Интересно, что данная модель позволяет «защищать» критической секцией не всю общую память, а только ту её часть, с которой производится работа всекции (таким образом, критических секций может быть много). Соответственно, нет необходимости пересылать между узлами все изменения – достаточноизменений, затрагивающих конкретную критическую секцию. Кроме того, различные узлы получают возможность одновременного нахождения в критических секциях, что еще более повышает производительность системы за счетминимизации ожиданий – требуется лишь чтобы в этих секциях работа веласьс непересекающимися данными распределённой памяти.32За счет привнесения дополнительной информации о ходе исполнения программы (вход или выход из критической секции), реализация модели получается более эффективной, чем для предыдущей модели.
Однако эту дополнительную информацию должен предоставить разработчик, явным образом помечаяначало и конец критических секций – либо через операции захвата и освобождения одной и той же синхронизационной переменной, либо через выполнениеодной и той же операции над двумя разными, специально выделенными синхро-переменными.1.4.6. Ленивая консистентность по выходуМодель ленивой консистентности по выходу (англ. lazy release consistency)была предложена в работе [30]. В отличие от изначальной модели консистентности по выходу (которую, во избежание путаницы, стали часто называть моделью активной консистентности по выходу, англ.
eager release consistency), новаямодель не требовала немедленной рассылки информации об обновленных данных по выходу из критической секции. Лишь узлы, входящие в критическуюсекцию (иными словами, осуществляющие захват синхронизационной переменной), гарантированно получали эти данные в момент захвата.Такой подход позволил еще более сократить обмен информацией между узлами – ведь если данные ни одному узлу сейчас «не нужны», то и пересылатьсяв новой модели они не будут.1.4.7. Консистентность по входуМодель консистентности по входу (англ.
entry release consistency) потребовала [15], чтобы каждая переменная из распределённой памяти была закрепленаза какой-либо синхронизационной переменной. Это позволило легко контролировать, какие именно данные нуждаются в обновлении при входе и выходе изкритической секции. Модель консистентности по выходу при вхождении в кри33тическую секцию была вынуждена «догадываться» о том, какие данные необходимо обновить. Возможности модели по выходу были таким образом усилены,количество передаваемых между узлами данных уменьшилось, а возможностипо параллелизму возросли (за счет возросшей способности разных узлов одновременно находиться в разных критических секциях). Также было введенопонятие эксклюзивной и неэксклюзивной блокировки синхронизационной переменной, что позволило отделить операции чтения общих переменных от операций записи.
Очевидно, что в случае отсутствия эксклюзивной блокировки, внеэксклюзивной секции может находиться несколько узлов одновременно. Формулировка правил модели по входу выглядит так:Определение 5.1Система соответствует модели консистентности повходу в том случае, если выполняются следующие условия:1. Операция захвата синхронизационной переменной может быть завершена только после того, как все операции записи других узлов в защищаемые ей переменные общей памяти также будут завершены.2. Операция эксклюзивного захвата синхронизационной переменной может быть завершена только после того, как все узлы освободят даннуюпеременную (даже если она была захвачена неэксклюзивно).3.
По завершении эксклюзивного доступа к синхронизационной переменнойдругой узел может захватить переменную неэксклюзивно, но такая1Основано на определении из работы [15]:1. An acquire access of is not allowed to perform with respect to processor until all updates to havebeen performed with respect to . An update to a memory location is said to perform with respect toprocessor at a point in time when a subsequent read of that location by returns the value written bythe update.2. Before an exclusive mode access to a synchronization variable by processor is allowed to perform withrespect to , no other processor may hold in non-exclusive mode.3.
After an exclusive mode access to has been performed, any processor’s next non-exclusive mode accessto may not be performed until it is performed with respect to the owner of .34операция захвата может быть завершена только после того, как будут учтены результаты операций над соответствующими общими переменными владельца этой синхронизационной переменной.Вместе с разделением захвата синхронизационной переменной на эксклюзивный и неэксклюзивный, было введено понятие владельца этой переменной.Владелец – тот, кто последним осуществлял её захват. Процесс, являющийсяв данный момент владельцем переменной, не обязан осуществлять какой-либоинформационный обмен с другими узлами сети при многократном входе и выходе из соответствующей критической секции до тех пор, пока другой узел непопробует осуществить захват этой переменной – в таком случае информацияо новых значениях соответствующих общих переменных будет передана на запрашивающий узел.1.4.8.
ЗаключениеИсследования в данной области продолжаются: создаются новые модели(например, view-based consistency model [49]), обобщаются все существующие ивыводятся общие закономерности [43], а некоторые исследователи считают, чтомы дошли до рубежа, за которым нужно подумать о принципиально новых аппаратных и программных идеологиях [11].
Тем временем, описанные выше моделиактивно используются, адаптируясь к тому или иному программно-аппаратному окружению и воплощаясь в различных реализациях. Краткий обзор этихреализаций мы рассмотрим ниже. Но сначала необходимо рассмотреть алгоритмы, лежащие в основе – принципиальные подходы к реализации моделейконсистентности.1.5. АлгоритмыВ основе любого DSM механизма лежит некоторая модель консистентности, основные модели были разобраны в разделе 1.4. Однако одна и та же35модель может быть реализована множеством разнообразных способов, сильноотличающихся между собой по критериям производительности, надежности идругим. В данном разделе рассмотрим основные известные алгоритмы с целью выбора или формирования собственного в последующих главах.
Алгоритмы детально рассмотрены в работах [44] и [45] (в текущей работе использованы минимально адаптированные изображения из них), причем в первой работерассматриваются их базовые версии, а во второй – возможные усовершенствования с целью обеспечения устойчивости к отказам отдельных узлов. Однакоавторы данных работ не разделяли понятия модели консистентности и алгоритмов реализации, представляя вторые самодостаточно, не выделяя модель вкачестве базового соглашения по правилам использования общей памяти между программистом и «оборудованием». Мы же рассматриваем именно модельконсистентности в качестве основы DSM системы, а алгоритмы – как способболее или менее эффективной реализации конкретной модели.
Такой подходпозволяет оперировать в каждом случае только существенными для данногослучая деталями, отделяя принципиальные требования и свойства модели отчастных решений и алгоритмов, направленных на повышение эффективностив заданных моделью рамках.1.5.1. Алгоритм с центральным серверомНаиболее очевидное решение задачи управления распределёнными данными – выбрать один из узлов так называемым сервером, и производить все операции через него (рис. 1.8). Например, когда модель консистентности требуетот некоторого узла (скажем, №2) обновить у себя те или иные общие данные –обращаться за этими данными следует именно к серверу (узел №1). И наоборот– если модель требует от узла (например, №2) распространить его измененияобщих данных по всем остальным узлам – узлу нужно делегировать эту задачу серверу (№1), передав ему и постановку задачи, и данные для неё.
Серверже самостоятельно свяжется с остальными узлами (№3 и №4) и передаст им36нужную информацию.Обособление в распределённой системе какого-то узлаСерверпотенциально опасно, так как1выделенный узел становитсяслабым местом системы – вы2ход из строя лишь одного данКлиент43Клиентного узла может привести кКлиенттому, что вся система выйдетРисунок 1.8 – Алгоритм с центральным серверомиз строя.
Воспрепятствоватьэтому можно, например, через резервирование узла-сервера (рис. 1.9).В систему вводится новый узелСерверКопия(или данные функции возлагаются на11aодин из уже существующих узлов), являющийся «зеркалом» узла-сервера.2Клиент3Клиент4И теперь, при выполнении любой опеКлиентрации записи сервер (узел №1) сначала информирует о ней свою копиюРисунок 1.9 – Отказоустойчивый алгоритм с (узел №1а), и только получив от копиицентральным серверомответ, продолжает свою работу. Есливыйдет из строя узел-копия, узел-сервер это заметит по срабатыванию таймаутов на операции, с которыми серверобращается к копии, и выделит другой узел в качестве своей копии. Заметитьвыход из строя самого сервера несколько сложнее – для этого необходим ввод всистему дополнительного сервиса, регулярно опрашивающего сервер (корректное функционирование данного сервиса, в свою очередь, также нужно регулярно проверять), в частности, с этой задачей может справиться и узел-копия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
