Порядок фиксации программных транзакций и управление конфликтами

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

 

УРОВЕНЬ ТЕХНИКИ

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

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

Одним из подходов для упрощения параллельного программирования является автоматическое распараллеливание последовательных программ способом, который гарантирует, что семантики программы неизменны. Другими словами, если последовательная программа работает правильно, то же самое происходит с распараллеленной версией. Две (отдельных) вариации этой идеи для распараллеливания последовательных программ названы, соответственно, безопасными перспективами (safe futures) и опережающим распараллеливанием цикла (speculative loop parallelization). В принципе "safe futures" последовательная версия программы могла бы выполнять "A; B" (то есть выполнить А, потом выполнить В). Программист может добавить примечание ("future"), указывающее, что он думает, что было бы возможно выполнить А и В параллельно без изменения семантики программы - что А не считывает никакие ячейки памяти, которые считывает В, или наоборот. Но система интерпретирует это строго как "рекомендацию", чью справедливость надо проверить. Она выполняет А и В в виде транзакций, и если они конфликтуют, она препятствует фиксации В, если оно было бы упорядочено до А. Это является "нежелательной" особенностью неопределенного порядка фиксации, упоминаемого выше.

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Фиг.1 - схематическое изображение компьютерной системы по одному варианту выполнения.

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

Фиг.3 - высокоуровневая схема технологического процесса по одному варианту выполнения системы по фиг.1.

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

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

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

Фиг.7 - последовательность операций для одного варианта выполнения системы по фиг.1, которая иллюстрирует этапы, участвующие в обеспечении процесса управления конфликтами, который управляет конфликтами с использованием информации о заданном порядке фиксации.

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

Фиг.9 - логическая схема, иллюстрирующая типовое дерево предшественников с предшественниками верхнего уровня, которые имеют общего предшественника.

Фиг.10 - логическая схема, иллюстрирующая типовое дерево предшественников с предшественниками верхнего уровня, которые не имеют общего предшественника.

Фиг.11 - схема технологического процесса для одного варианта выполнения системы по фиг.1, которая иллюстрирует этапы, участвующие в сокращении объема бесполезной работы путем использования арбитра фиксации в системе с программной транзакционной памятью.

Фиг.12 - схема технологического процесса для одного варианта выполнения системы по фиг.1, которая иллюстрирует этапы, участвующие в анализе всей цепочки предшественников в процессе управления конфликтами для определения надлежащего разрешения конфликтов.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

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

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

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

Как показано на фиг.1, типовая компьютерная система для использования в реализации одной или более частей системы включает в себя вычислительное устройство, например вычислительное устройство 100. В своей самой базовой конфигурации вычислительное устройство 100, как правило, включает в себя по меньшей мере один блок 102 обработки и запоминающее устройство 104. В зависимости от точной конфигурации и типа вычислительного устройства запоминающее устройство 104 может быть энергозависимым (например, RAM), энергонезависимым (например, ROM, флэш-память и так далее) или каким-нибудь сочетанием из двух типов. Самая базовая конфигурация иллюстрируется на фиг.1 с помощью пунктирной линии 106.

Более того, устройство 100 может также обладать дополнительными функциями/функциональными возможностями. Например, устройство 100 также может включать в себя дополнительное хранилище (съемное и/или несъемное), включая, но не ограничиваясь, магнитные или оптические диски или пленку. Такое дополнительное хранилище иллюстрируется на фиг.1 с помощью съемного запоминающего устройства 108 и несъемного запоминающего устройства 110. Компьютерные носители информации включают в себя энергозависимые и энергонезависимые, съемные и несъемные носители, реализованные по любому способу или технологии хранения информации, такой как машиночитаемые команды, структуры данных, программные модули и другие данные. Запоминающее устройство 104, съемное запоминающее устройство 108 и несъемное запоминающее устройство 110 являются примерами компьютерных носителей информации. Компьютерные носители информации включают в себя, не ограничиваясь, ОЗУ, ПЗУ, EEPROM (электрически стираемое и программируемое ПЗУ), флэш-память или другую технологию памяти, компакт-диск, универсальные цифровые диски (DVD) или другие накопители на оптических дисках, магнитные кассеты, магнитную ленту, накопитель на магнитных дисках или другие магнитные запоминающие устройства, или любой другой носитель, который может быть использован для хранения нужной информации и к которому можно обращаться с помощью устройства 100. Любые такие компьютерные носители информации могут быть частью устройства 100.

Вычислительное устройство 100 включает в себя одно или более соединений 114 связи, которые позволяют вычислительному устройству 100 обмениваться информацией с другими компьютерами/приложениями 115. Устройство 100 также может иметь устройство(а) 112 ввода, например клавиатуру, мышь, перо, устройство речевого ввода, устройство сенсорного ввода и так далее. Также может быть включено устройство(а) 111 вывода, например дисплей, динамики, принтер и так далее. Эти устройства общеизвестны в данной области техники и не нуждаются в детальном описании в данном документе. В одном варианте выполнения вычислительное устройство 100 включает в себя приложение 200 с программной транзакционной памятью. Приложение 200 с программной транзакционной памятью будет подробнее описано на фиг.2.

Обратимся к фиг.2, и по-прежнему ссылаясь на фиг.1, на которой иллюстрируется приложение 200 с программной транзакционной памятью, работающее на вычислительном устройстве 100. Приложение 200 с программной транзакционной памятью является одной из прикладных программ, которые постоянно находятся на вычислительном устройстве 100. Однако будет подразумеваться, что приложение 200 с программной транзакционной памятью в качестве альтернативы или дополнительно может быть осуществлено в виде исполняемых компьютером команд на одном или более компьютерах и/или в других вариациях, показанных на фиг.1. В качестве альтернативы или дополнительно одна или более частей приложения 200 с программной транзакционной памятью может быть частью системной памяти 104 на других компьютерах и/или приложениях 115, или других таких вариаций, которые могли бы быть предусмотрены специалистом в области компьютерного программного обеспечения.

Приложение 200 с программной транзакционной памятью включает в себя программную логику 204, которая ответственна за выполнение некоторых или всех методик, описываемых в настоящем документе. Программная логика 204 включает в себя логику 206 для обеспечения системы с программной транзакционной памятью (STM); логику 208 для обеспечения арбитра фиксации, который позволяет задавать определенный порядок фиксации, статически или динамически, для множества транзакций в системе с STM; логику 210, позволяющую арбитру фиксации использовать заданный порядок фиксации во время выполнения, чтобы помочь в определении порядка, в котором следует фиксировать множество транзакций в системе с программной транзакционной памятью; логику 212 для обеспечения процесса управления конфликтами, который вызывается, когда возникает конфликт между первой транзакцией и второй транзакцией; логику 214 для использования заданного порядка фиксации в процессе управления конфликтами, чтобы помочь в определении, какая из первой транзакции или второй транзакции должна выиграть в конфликте и быть допущена к выполнению (например, в зависимости от того, какая транзакция имеет меньший порядковый номер фиксации из двух транзакций в одной группе транзакций); логику 216, позволяющую арбитру фиксации функционировать для использования заданного упорядочения фиксации для отслеживания одного или более значений упорядочения (например, в полном упорядочении - поле «следующего для фиксации», которое представляет следующую транзакцию из множества транзакций, которую следует допустить к фиксации) и для сравнения одного или более значений упорядочения с конкретным порядковым номером фиксации у заданной транзакции, чтобы определить, является ли фиксация заданной транзакции правильно заданным упорядочением, которое следует принудительно выполнить; и другую логику 220 для работы приложения. В одном варианте выполнения программная логика 204 функционирует для вызова ее программным способом из другой программы, например с использованием одного обращения к процедуре в программной логике 204.

Обратимся теперь к фиг.3-10, по-прежнему ссылаясь на фиг.1-2, на которых более подробно описаны этапы реализации одного или более вариантов выполнения приложения 200 с программной транзакционной памятью. Фиг.3 - высокоуровневая схема технологического процесса для приложения 200 с программной транзакционной памятью. В одном виде процесс по фиг.3 по меньшей мере частично реализуется в исполнительной логике вычислительного устройства 100. Процедура начинается в начальной точке 240 с обеспечения системы с программной транзакционной памятью (этап 242). Обеспечена функция, позволяющая задавать определенный порядок фиксации (например, полное упорядочение или частичное упорядочение) для множества транзакций (например, назначаемый динамически или статически) (этап 244). В контексте настоящего документа подразумевается, что термин "заданный порядок фиксации" включает в себя определенный порядок, в котором следует фиксировать конкретную группу связанных транзакций, который определяется в любой момент времени перед тем, как транзакции начинают выполняться. Термин "группа" транзакций в контексте настоящего документа включает в себя конкретный набор (например, множество) транзакций, управляемых одним арбитром фиксации, а также вложенные потомки этих транзакций.

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

Фиг.4 иллюстрирует один вариант выполнения этапов, участвующих в использовании арбитра фиксации для принудительного выполнения заданного порядка фиксации. В одном виде процесс по фиг.4 по меньшей мере частично реализуется в исполнительной логике вычислительного устройства 100. Процедура начинается в начальной точке 270 с обеспечения одного или более арбитров фиксации для системы с программной транзакционной памятью, причем арбитр фиксации функционирует, позволяя задавать определенный порядок фиксации для множества транзакций (этап 272). В контексте настоящего документа подразумевается, что термин "арбитр фиксации" включает в себя любой тип программы, функции или процесса, который ответственен за управления одной или более группами транзакций, которые следует упорядочить относительно друг друга. В одном варианте выполнения может существовать один или более активных арбитров фиксации в программе в любое заданное время. Например, может быть создано столько арбитров фиксации, сколько нужно для управления разными группами транзакций. Арбитр фиксации отслеживает и обновляет одно или более значений упорядочения, которые используются для определения надлежащего упорядочения транзакций относительно друг друга (этап 274). В случае полного упорядочения поле «следующего для фиксации» может использоваться для представления следующей транзакции во множестве транзакций, которую следует фиксировать следующей (этап 274). В случае частичного упорядочения отслеживается ориентированный граф из разных возможных порядков с использованием значений упорядочения. При необходимости арбитр фиксации использует заданный порядок фиксации для предоставления порядкового номера фиксации каждой из множества транзакций (этап 276).

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

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

Фиг.5 иллюстрирует один вариант выполнения этапов, участвующих в использовании арбитра фиксации для принудительного выполнения полного упорядочения множества транзакций. В одном виде процесс по фиг.5 по меньшей мере частично реализуется в исполнительной логике вычислительного устройства 100. Процедура начинается в начальной точке 290 с обеспечения одного или более арбитров фиксации, функционирующих, позволяя задавать определенное полное упорядочение для множества транзакций (например, указывающих точный порядок, в котором следует фиксировать множество транзакций) (этап 292). Когда конкретная транзакция из множества транзакций подходит к ее моменту фиксации, для принудительного выполнения порядка фиксации этот порядок фиксации конкретной транзакции сравнивается с полем «следующего для фиксации» у арбитра фиксации (этап 296). В одном варианте выполнения, если система определяет, что принудительное выполнение полного упорядочения не является необходимым (например, потому что нет явного конфликта), то требование полного упорядочения может быть нарушено при необходимости (этап 294), тогда процесс завершается в конечной точке 302.

Если упорядочение фиксации нужно выполнить принудительно, и если порядок фиксации у конкретной транзакции имеет то же значение, что и поле «следующего для фиксации» у арбитра фиксации (точка 296 принятия решения), то конкретная транзакция фиксируется, и если фиксация успешна, поле «следующего для фиксации» получает приращение, и вызывается следующий последователь, если таковой существует (этап 298). Если порядок фиксации у конкретной транзакции не имеет того же значения, что и поле «следующего для фиксации» у арбитра фиксации (точка 296 принятия решения), то конкретная транзакция помещается в режим ожидания/бездействия, пока она не будет вызвана в более поздний момент времени, после того как фиксируется транзакция-предшественник (этап 300). В одном варианте выполнения в более поздний момент времени, если возникает конфликт с предшественником, то конкретная транзакция может быть запрошена на прекращение и откат, чтобы предшественник мог продвинуться вперед. В противном случае, если никакого такого конфликта не возникло, то конкретная транзакция должна иметь возможность фиксироваться, если удовлетворяются требования порядка фиксации, описываемые в настоящем документе. Процесс затем завершается в конечной точке 302.

Фиг.6 иллюстрирует один вариант выполнения этапов, участвующих в использовании арбитра фиксации для принудительного выполнения частичного упорядочения множества транзакций. В одном виде процесс по фиг.6 по меньшей мере частично реализуется в исполнительной логике вычислительного устройства 100. Процедура начинается в начальной точке 310 с обеспечения одного или более арбитров фиксации, функционирующих, позволяя задавать определенное частичное упорядочение для множества транзакций (например, задающих множество допустимых порядков, в котором следует фиксировать множество транзакций - например, в виде ориентированного графа) (этап 312). Когда конкретная транзакция из множества транзакций подходит к ее моменту фиксации, для принудительного выполнения порядка фиксации состояние транзакций-предшественников (например, одно или более значений упорядочения) принимаются во внимание для конкретной фиксирующейся транзакции (например, которое отслеживается арбитром фиксации) (этап 314). Если все предшественники конкретной транзакции зафиксированы (точка 316 принятия решения), то конкретная транзакция фиксируется (этап 318). Если фиксация успешна, то одно или более значений, отслеживаемых арбитром фиксации, обновляются при необходимости, и вызываются все возможные следующие последователи, если какие-нибудь существуют (этап 318).

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

Фиг.7 иллюстрирует один вариант выполнения этапов, участвующих в обеспечении процесса управления конфликтами, который управляет конфликтами с использованием информации о заданном порядке фиксации. В одном виде процесс по фиг.7 по меньшей мере частично реализуется в исполнительной логике вычислительного устройства 100. Процедура начинается в начальной точке 340 с обеспечения системы с программной транзакционной памятью, которая поддерживает заданный порядок фиксации для одной или более групп транзакций (этап 342). Обеспечен процесс управления конфликтами, который вызывается, когда возникает конфликт между первой транзакцией и второй транзакцией (этап 344). Заданный порядок фиксации используется в процессе управления конфликтами для помощи в определении, какая из первой транзакции или второй транзакции должна выиграть в конфликте и быть допущенной к выполнению (этап 346). Если первая транзакция и вторая транзакция не являются частью одной группы транзакций (точка 348 принятия решения), то заданный порядок фиксации не выполняется принудительно между этими двумя транзакциями (поскольку никакого не существует) (этап 350). В таком сценарии, поскольку две транзакции не находятся в одной группе транзакций, фактор упорядочения не используется для помощи в разрешении конфликта (этап 350).

Если первая транзакция и вторая транзакция являются частью одной группы транзакций (точка 348 принятия решения), то система сравнивает первый порядковый номер у первой транзакции и второй порядковый номер у второй транзакции (этап 352). Транзакция с меньшим порядковым номером допускается к выполнению (или с другим подходящим упорядочением приоритета) (этап 354). Процесс завершается в конечной точке 356.

Фиг.8 иллюстрирует один вариант выполнения этапов, участвующих в обеспечении процесса управления конфликтами, который управляет конфликтами с вложенными транзакциями с использованием информации о заданном порядке фиксации. В одном виде процесс по фиг.8 по меньшей мере частично реализуется в исполнительной логике вычислительного устройства 100. В одном варианте выполнения рассматривается вся цепочка предшественников для каждой транзакции перед фиксацией конкретной транзакции, чтобы принудительно выполнялось любое упорядочение, присутствующее в цепочке. Процедура начинается в начальной точке 370 с обеспечения процесса управления конфликтами, который вызывается, когда возникает конфликт между первой транзакцией и второй транзакцией (этап 372). Заданный порядок фиксации используется в процессе управления конфликтами для помощи в определении, какая из первой транзакции или второй транзакции должна выиграть в конфликте и быть допущенной к выполнению (этап 372). Если первая и вторая транзакции не являются частью одной группы транзакций (точка 376 принятия решения), то заданный порядок фиксации не выполняется принудительно между теми двумя транзакциями (поскольку никакого не существует) (этап 378), и процесс завершается в конечной точке 388. Если первая и вторая транзакции являются частью одной группы транзакций (точка 376 принятия решения), то система проверяет, участвуют ли вложенные транзакции (точка 380 принятия решения).

Если вложенные транзакции не участвуют (точка 380 принятия решения), то порядковый номер (или другой указатель упорядочения) первой транзакции сравнивается с порядковым номером (или другим указателем упорядочения) второй транзакции (этап 384). Транзакция с меньшим порядковым номером допускается к выполнению (или транзакция, определенная следующей по порядку, с использованием других подходящих критериев упорядочения) (этап 386).

Если вложенные транзакции участвуют (точка 380 принятия решения), то порядковый номер (или другой указатель упорядочения) предшественника верхнего уровня первой транзакции сравнивается с порядковым номером (или другим указателем упорядочения) предшественника верхнего уровня второй транзакции (этап 382). Термин "предшественник верхнего уровня" при использовании в данном документе предназначается для включения в себя прямых потомков общих предшественников, где участвуют общие предшественники, и предшественника верхнего уровня каждой транзакции, где нет участвующего общего предшественника. Эти сценарии вовлечения общих и необщих предшественников иллюстрируются более подробно на фиг.9 и 10. Транзакция с меньшим порядковым номером допускается к выполнению (например, транзакция, относящаяся к предшественнику, который имел меньший порядковый номер или другие подходящие критерии) (этап 386). Процесс завершается в конечной точке 388.

Фиг.9 - логическая схема, иллюстрирующая типовое дерево предшественников с предшественниками верхнего уровня, которые имеют общего предшественника. В показанном примере транзакция A является общим предшественником для D и E. В конфликтах, возникающих между D и E, порядковые номера транзакций B и C (прямые потомки общего предшественника A) анализируются для определения, какую транзакцию D или E следует допустить к выполнению (этап 382 на фиг.8).

Фиг.10 - логическая схема, иллюстрирующая типовое дерево предшественников с предшественниками верхнего уровня, которые не имеют общих предшественников. В показанном примере транзакция A является предшественником у транзакции C. Транзакция D является предшественником у транзакции F. В конфликтах, возникающих между транзакциями C и F, порядковые номера транзакций A и D (предшественник верхнего уровня у каждой) сравниваются для определения, какую транзакцию C или F следует допустить к выполнению (этап 382 на фиг.8).

Фиг.11 иллюстрирует один вариант выполнения этапов, участвующих в сокращении объема бесполезной работы путем использования арбитра фиксации в системе с программной транзакционной памятью. В одном виде процесс по фиг.11 по меньшей мере частично реализуется в исполнительной логике вычислительного устройства 100. Процедура начинается в начальной точке 400 с обеспечения одного или более арбитров фиксации для системы с программной транзакционной памятью, причем арбитр фиксации функционирует, позволяя задавать определенный порядок фиксации для множества транзакций (этап 402). Арбитр фиксации функционирует для помещения транзакции в режим бездействия/ожидания, чтобы блокировать эту транзакцию от повторного выполнения, когда транзакция-предшественник все еще выполняется (например, путем анализа заданного порядка фиксации для определения надлежащего порядка) (этап 404). Арбитр фиксации также функционирует для вызова транзакций, которые приостанавливались, как только транзакция(и)-предшественник завершена (например, путем повторного анализа заданного порядка фиксации для определения надлежащего порядка) (этап 406). С помощью обеспечения этих механизмов блокировки и вызова арбитр фиксации помогает сократить объем работы, которая тратится впустую, путем предотвращения выполнения операций, которые потребовалось бы отменить позднее (этап 408). Процесс завершается в конечной точке 410.

Фиг.12 иллюстрирует один вариант выполнения этапов, участвующих в анализе всей цепочки предшественников в процессе управления конфликтами для определения надлежащего разрешения конфликтов. В одном виде процесс по фиг.12 по меньшей мере частично реализуется в исполнительной логике вычислительного устройства 100. Процедура начинается в начальной точке 430 с обеспечения процесса управления конфликтами, который вызывается, когда возникает конфликт между первой транзакцией и второй транзакцией (этап 432). Заданный порядок фиксации используется в процессе управления конфликтами для помощи в определении, какая из первой транзакции или второй транзакции должна выиграть в конфликте и быть допущенной к выполнению (этап 434). Вся цепочка предшественников у заданного порядка фиксации анализируется, чтобы помочь определить надлежащее управление конфликтами (этап 436). Например, если имеются четыре транзакции, два родителя и два потомка, где B является вложенной в A, а D является вложенной в C. Предположим, что имеется отношение упорядочения между A и C, где A следует фиксировать перед C. Если B и D конфликтуют, то процессу управления конфликтами следует отдать предпочтение B, так как содействие D является бесполезным с учетом того, что A должно фиксироваться перед C (этап 436). Процесс завершается в конечной точке 438.

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

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

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

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

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

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

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

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

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

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

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

9. Способ по п.8, в котором при приготовлении конкретной транзакции из множества связанных транзакций к фиксации определяют, имеет ли порядковый номер фиксации для конкретной транзакции то же значение, что и поле «следующего для фиксации», отслеживаемое арбитром фиксации.

10. Способ по п.9, в котором, если порядковый номер фиксации для конкретной транзакции и поле «следующего для фиксации» имеют одинаковое значение, разрешают выполнение фиксации.

11. Способ по п.10, в котором, после того как происходит фиксация и она является успешной, арбитр фиксации увеличивает поле «следующего для фиксации» до следующего номера в последовательности.

12. Способ по п.9, в котором, если порядковый номер фиксации для конкретной транзакции и поле «следующего для фиксации» не имеют одинакового значения, помещают конкретную транзакцию в состояние ожидания, пока конкретная транзакция не будет вызвана в более поздний момент времени, после того как фиксируется транзакция-предшественник.

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

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

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

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

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

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