Оглавление
Журнал Communications of the ACM когда-то (лет 30 тому назад) был одним из лучших журналов в области аппаратуры и программного обеспечения компьютеров. В нем печатались статьи, которые оказывали огромное влияние на специалистов, преподавателей и студентов. Достаточно вспомнить статью Питера Деннинга об алгоритме управления виртуальной памятью на основе концепции рабочих наборов (P.J. Denning. The working set model for program behavior. Communications of the ACM, Volume 11, № 5, 1968) и основополагающую статью Дениса Ритчи и Кена Томпсона об операционной системе UNIX (D. M. Ritchie, K. Thompson. The Unix Time-Sharing System. Communications of the ACM, Volume 17, № 7, 1974). Начиная примерно с середины 1980-х журнал становился все скучнее и скучнее, и в новом тысячелетии в нем вообще стало трудно найти что-нибудь интересное. Однако ACM нашла в себе силы возродить журнал. С июля 2008-го года Communications of the ACM выходит в новом формате и наполнен интересными статьями.
Одну из этих статей я решил пересказать. По всей видимости, авторы статьи правы, утверждая, что транзакционная память может оказаться именно тем подходом, которого не хватает программистам для создания программ, эффективно использующим возможности многоядерных процессоров. Не могу об этом судить авторитетно, поскольку не являюсь специалистом в области параллельного программирования. Но мне кажется (и здесь мое мнение совпадает с мнением Майкла Стоунбрейкера, см. мой пересказ статьи OLTP в Зазеркалье), что технология транзакционной памяти может оказаться очень полезной для реализации систем управления базами данных в основной памяти в многоядерных архитектурах.
Транзакционная память пока не заняла свое место на коммерческом рынке, но я считаю, что интересно познакомиться с теми подходами к ее организации, которые существуют в настоящее время. Следует иметь в виду, что статья Ляруса и Казиракиса является кратким обзором достаточно сложных методов, для полного понимания которых нужно читать соответствующие полные статьи. Мне удалось найти в открытом доступе в Internet большую часть статей, на которые ссылаются Лярус и Казиракис, и я рекомендую вам обратить на них внимание.
Сергей Кузнецов
Предисловие
По мере развития компьютеров меняется и программирование. В последние несколько лет начался переход от последовательных к параллельным вычислениям в процессорах, используемых в большинстве серверов, персональных и мобильных компьютеров. Этот переход означает конец замечательного 30-летнего периода, в котором достижения полупроводниковой технологии и компьютерной архитектуры позволяли ежегодно повышать производительность последовательных процессоров на 40-50%. Постоянный рост производительности шел на пользу всему программному обеспечению, и этот прогресс являлся ключевым фактором, влиявшим на распространение программного обеспечения во всех областях современной жизни.
Эта замечательная эпоха подошла к концу, когда практические ограничения на рассеяние мощности микропроцессоров сделали невозможным постоянное повышение тактовой частоты, и ограниченный параллелизм на уровне команд перестал оправдывать непрерывно возрастающую сложность архитектур процессоров. Эра закончилась не потому, что перестал действовать закон Мура. Технология полупроводников все еще в состоянии удваивать число транзисторов в кристалле через каждые два года. Однако теперь это все возрастающее количество транзисторов приводит к увеличению числа независимых процессоров на кристалле, а не ускоряет работу отдельного процессора. Результирующая архитектура компьютера, получившая название многоядерной, состоит в том, что на кристалле располагается несколько независимых процессоров (ядер), которые общаются через общую основную память. Сегодня общераспространенными являются двухядерные кристаллы, на рынок поступают черырехядерные процессоры, и имеются все основания полагать, что в течение ряда поколений кристаллов число ядер будет продолжать удваиваться.
С одной стороны, хорошо, что пиковая производительность многоядерного компьютера удваивается при каждом удвоении числа ядер. С другой стороны, для достижения этой производительности требуется, чтобы программа распараллеливалась и масштабировалась при возрастании числа процессоров. Сегодня существует не так уж много программ, способных к эффективному распараллеливанию. Частично это объясняется тем, что у большинства программистов не было доступа к параллельным компьютерам, распространенность которых была ограничена прикладными областями с крупными, естественным образом параллельными рабочими нагрузками. Параллельные компьютеры использовались, главным образом, для выполнения вычислений огромного масштаба. Поскольку основным течением было последовательное программирование, в большинстве существующих языков программирования, библиотек, паттернов проектирования и учебных курсов проблемы параллельного программирования просто не затрагивались. Очевидно, эта ситуация должна измениться до того, как программисты в массовом порядке начнут писать параллельные программы для многоядерных процессоров.
Основная проблема состоит в том, чтобы найти лучшие абстракции для выражения параллельных вычислений и написания параллельных программ. Параллельному программированию свойственны все трудности последовательного программирования, но к ним добавляется трудная проблема координации взаимодействия параллельно выполняемых задач. Сегодня в большинстве параллельных программ используются низкоуровневые программные конструкции, которые являются всего лишь тонкой облицовкой используемых аппаратных средств. В чисто этих конструкций входят потоки управления (thread), представляющие собой абстрактные процессоры, и явная синхронизация (например, блокировки, семафоры и мониторы) для координации выполнения потоков. Опыт прошлых лет показывает, что параллельные программы, написанные с использованием этих конструкций, трудно разрабатывать, кодировать, отлаживать, сопровождать, и, в добавление ко всему этому, они часто не очень хорошо работают.
Транзакционная память (transactional memory, TM), предложенная Ломе (Lomet) [19] и впервые практически реализованная Херлихи (Herlihy) и Моссом (Moss) [13], – это новая программная конструкция, обеспечивающая высокоуровневую абстракцию для написания параллельных программ. В последние несколько лет она привлекает значительный интерес, поскольку транзакции в течение долгого времени используются в системах баз данных для изоляции параллельных активностей. TM предоставляет механизм, позволяющий частям программы выполняться в изоляции, не обращая внимания на другие параллельно выполняемые задачи. Программист может обосновывать корректность кода внутри транзакции и не вынужден заботиться в сложных взаимодействиях с другими, параллельно выполняемыми частями транзакции. TM обеспечивает многообещающий, но еще не проверенный механизм для совершенствования параллельного программирования.
Что такое транзакционная память?
Транзакция – это некоторая форма выполнения программ, перенятая от сообщества баз данных [8]. Параллельно исполняемые запросы конфликтуют, когда они читают и изменяют некоторый элемент базы данных, и возникающий конфликт может привести к ошибочному результату, который не мог бы получиться при последовательном выполнении этих запросов. Транзакции гарантируют, что все запросы произведут тот же самый результат, как если бы они выполнялись последовательно в некотором порядке (serially, «сериально»; это свойство называют «сериализуемостью» (serializability)). Декомпозиция семантики транзакции приводит к четырем требованиям, обычно называемым свойствами ACID: атомарность (atomicity), согласованность (consistency), изоляция (isolation) и долговечность (durability).
TM обеспечивает механизм легковесных транзакций для потоков управления, выполняемых в общем адресном пространстве. TM гарантирует атомарность и изолированность параллельно выполняемых задач. (Вообще говоря, согласованность и долговременность не обеспечиваются.) Атомарность гарантирует, что изменения состояния программы, производимые кодом, который выполняется в некоторой транзакции, являются невидимыми с точки зрения других, параллельно выполняемых транзакций. Другими словами, хотя код, выполняемый внутри транзакции, может изменять отдельные переменные посредством присваивания, в других вычислениях может наблюдаться состояние программы только либо непосредственно до, либо непосредственно после выполнения данной транзакции. Изолированность гарантирует, что параллельно выполняемые задачи не влияют на результат транзакции, так что транзакция производит один и тот же результат, как если бы не выполнялась никакая другая задача. Транзакции обеспечивают основу для построения параллельных абстракций, являющихся строительными блоками, которые можно комбинировать без знания их внутренних деталей, во многом подобно тому, как процедуры и объекты обеспечивают пригодные для компоновки абстракции для последовательного кода.
Программная модель TM. Программная модель обеспечивает логическое обоснование конструкций языков программирования и методологические принципы конструирования программ. Подобно многим другим аспектам TM, ее программная модель все еще является предметом активных исследований. В большинстве систем TM обеспечиваются простые атомарные операторы, выполняющие блок кода (и вызываемые в нем подпрограммы) как транзакцию. Атомарный блок изолирует код от параллельно выполняемых нитей, но блок не заменяет общую синхронизацию, обеспечиваемую, например, семафорами или условными переменными [2]. В частности, атомарные блоки сами по себе не обеспечивают средства для координации кода, выполняемого в параллельных потоках управления.
В отличие от этого, автоматическое взаимное исключение (automatic mutual exclusion, AME) выворачивает транзакционную модель «на изнанку» за счет выполнения большей части программы в транзакциях [15]. AME поддерживает асинхронное программирование, в котором при вызове любой функции начинается одно или несколько асинхронных вычислений, и затем для получения результатов этих вызовов требуются рандеву. Эта программная модель часто применяется для решения проблемы непредвиденных задержек в управляемых пользователями и распределенных системах. Атомарность, обеспечиваемая транзакциями, гарантирует, что асинхронное вычисление, выполняемое с непредсказуемой скоростью, не мешает выполнению других асинхронных вычислений.
Преимущества транзакционной памяти. При параллельном программировании приходится сталкиваться со многими трудностями, но одной из наиболее серьезных проблем при написании корректного кода является координация доступа к данным, совместно используемым в нескольких потоках управления. Последствиями попыток обеспечить взаимное исключение со слишком слабой или слишком сильной синхронизацией являются конфликты при доступе к данным (data race), синхронизационные тупики (deadlock) и плохая масштабируемость. TM обеспечивает более простую альтернативу взаимного исключения, снимая ношу корректной синхронизации с программиста и возлагая ее на систему TM [9]. Теоретически от разработчика программы требуется только обозначить последовательность операций, которая должна будет выполняться атомарно по отношению к другим параллельно выполняющимся потокам управления. Это обеспечивается системой TM на основе многочисленных механизмов, описываемых в этой статье.
Харрис (Harris) и Пейтон-Джонс (Peyton-Jones) [11] утверждают, что, помимо обеспечения улучшенной программной абстракции, транзакции также делают синхронизацию компонуемой, что позволяет конструировать абстракции параллельного программирования. Программная абстракция является компонуемой, если ее можно корректно комбинировать с другими абстракциями без потребности понимания ее функционирования.
Простая схема блокировок не является компонуемой. Рассмотрим, например, класс, реализующий набор банковских счетов. В этом классе имеются две безопасные для потоков управления операции Deposit и Withdraw, предназначенные для зачисления денег на счет и снятия их со счета соответственно. Предположим, что требуется произвести композицию этих операций в безопасную для потоков операцию Transfer, которая переводит деньги с одного счета на другой. Промежуточное состояние, когда деньги сняты с одного счета и не зачислены на другой счет, не должно быть видимым для других потоков управления (т.е. перевод должен быть атомарным). Поскольку в операциях Deposit и Withdraw счет блокируется только на время их выполнения, для правильной реализации операции Transfer требуется понять дисциплину блокировок, используемую в данном классе, и изменить ее путем добавления метода для блокировки всех счетов или какого-нибудь одного счета. Последний подход позволяет выполнять параллельно операции переводов с разными счетами, но при этом появляется возможность синхронизационного тупика, если выполнение операции перевода со счета A на счет B перекрывается во времени с выполнением операции перевода со счета B на счет A.
TM позволяет прямо компоновать операции. Каждая из операций Deposit и Withdraw выполняется в некоторой транзакции, чтобы защитить их работу с общими данными. Операция Transfer также выполняется в некоторой транзакции, которая превращает используемые в ней исходные операции Deposit и Withdraw в единое атомарное действие.
Ограничения транзакционной памяти. Транзакции сами по себе не могут заменить всю синхронизацию в параллельной программе [2]. Кроме взаимного исключения, синхронизация часто используется для координации независимых задач, например, путем обеспечения средств, позволяющих одной задаче дожидаться окончания другой задачи или ограничивающих число потоков управления, в которых исполняется некоторая программа.
Сами по себе транзакции не слишком помогают в координации независимых задач. Например, рассмотрим взаимосвязь программ «производитель-потребитель», когда одна задача пишет значения, которые читаются другой задачей. Транзакции могут гарантировать, что задачи, обращающиеся к одним и тем же ресурсам, не помешают друг другу. Однако схема, требуемая в данном случае, слишком дорого реализуется с использованием транзакций, назначением которых является как раз предотвращение взаимодействия задач. Если транзакция-потребитель обнаруживает, что читать еще нечего, она может только лишь аварийно завершиться и повторить попытку чтения позже. Активное ожидание (busy waiting) с использованием аварийного завершения транзакции неэффективно, поскольку при аварийном завершении транзакции «откатываются» (roll back) все проделанные ей вычисления. Было бы лучше, если бы производитель мог подать сигнал потребителю, когда значение станет готовым для чтения. Однако, поскольку в соответствии с семантикой транзакций сигнал, поданный в одной транзакции, является невидимым в других транзакциях, во многих системах TM обеспечивается механизм предохранителей (guard), который не дает транзакции начаться до тех пор, пока соответствующий ей предикат не примет значение true.
В Haskell TM поддерживаются конструкции retry и orElse, первая из которых позволяет транзакции дождаться возникновения некоторого события, а вторая – упорядочить выполнение двух транзакций [11]. Выполнение оператора retry приводит к аварийному завершению включающей его транзакции. Она не может быть выполнена повторно до тех пор, пока не изменится значение переменной, прочитанной перед выполнением retry. Это позволяет избежать использования наиболее грубой формы активного ожидания, при котором транзакция повторно считывает неизменившееся значение и аварийно завершается. Конструкция orElse обеспечивает возможность компоновать две транзакции, позволяя второй транзакции выполняться только в том случае, когда первая завершается аварийно. Этот распространенный сценарий трудно реализовать каким-либо другим способом, поскольку аварийное завершение и повторное выполнение транзакции происходят прозрачно для всех остальных частей программы.
Плюсы и минусы программной модели TM, а также ее прагматика все еще до конца не понятны. Например, активные споры ведутся относительно вложенных транзакций. Предположим, что в коде, выполняемом в транзакции O, вызывается библиотечная подпрограмма, в которой начинается собственная транзакция I. Должны ли иметься какие-то способы взаимодействия этих транзакций, и как это влияет на реализацию TM и методику построения модульного программного обеспечения и библиотек? Пусть транзакция I успешно завершается. Должны ли ее результаты быть видимы только коду транзакции O, или и другим потокам управления тоже (открытая вложенность)? При выборе второго варианта, что произойдет, если транзакция O завершится аварийным образом? Аналогично, если аварийно завершится транзакция I, должно ли это привести к завершению и транзакции O, или же внутренняя транзакция должна откатиться и перезапуститься независимым образом?
Наконец, производительность систем TM пока еще не слишком высока для их широкого использования. Программные системы TM (software TM system, STM) существенно нагружают код, выполняемый внутри транзакции, что уменьшает преимущества по производительности параллельных компьютеров. Аппаратные системы TM (hardware TM systems, HTM) могут снизить накладные расходы, но их коммерческие образцы только начинают появляться, и большинство систем HTM не справляется с обработкой крупных транзакций. Применение более совершенных методов реализации, вероятно, позволит улучшить оба вида систем, и в этой области ведутся активные исследования.
Виртуальные VPS серверы в РФ и ЕС
🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях
