处理嵌套事务的错误地破坏的父事务转让专利
申请号 : CN200880022416.6
文献号 : CN101689138A
文献日 : 2010-03-31
发明人 : M·M·马格鲁德 , D·德特勒夫 , J·J·达菲 , G·格雷费 , V·K·格罗弗
申请人 : 微软公司
摘要 :
权利要求 :
1.一种用于在事务存储器系统中避免嵌套子事务的错误地破坏的父事 务的方法，所述方法包括以下步骤：在回退嵌套事务时，在每次释放写锁定时跟踪释放计数(206)；以及在父事务的确认期间，使用所述释放计数来确定使确认失败的乐观读 取实际上是否是有效的(216)。
2.如权利要求1所述的方法，其特征在于，如果版本号差与所述释放 计数正好匹配，则所述失败的确认实际上是有效的(320)。
3.如权利要求1所述的方法，其特征在于，在写异常中止补偿映射中 跟踪所述释放计数(274)。
4.如权利要求3所述的方法，其特征在于，为所述嵌套事务中的每一 个创建所述写异常中止补偿映射(272)。
5.如权利要求4所述的方法，其特征在于，在所述嵌套事务中的相应 一个事务第一次回退并释放写锁定时，为该相应事务创建所述写异常中止 补偿映射(272)。
6.如权利要求4所述的方法，其特征在于，将所述嵌套事务中的每一 个的所述写异常中止补偿映射聚集到聚集的写异常中止补偿映射中(312)。
7.如权利要求6所述的方法，其特征在于，在处理所述父事务的事务 日志时使用所述聚集的写异常中止补偿映射来确定所述失败的乐观读取实 际上是否是有效的(312)。
8.如权利要求7所述的方法，其特征在于，所述父事务的事务日志是 以逆序来处理的(312)。
9.一种具有用于使得计算机执行如权利要求1所述的步骤的计算机可 执行指令的计算机可读介质(200)。
10.一种具有用于使得计算机执行以下步骤的计算机可执行指令的 计算机可读介质，所述步骤包括：为嵌套事务创建写异常中止补偿映射(206)；
在所述写异常中止补偿映射中记录所述嵌套事务释放写锁定的次数 (208)；以及在父事务的确认期间使用所述写异常中止补偿映射来确定失败的乐观 读取实际上是否是有效的(216)。
11.如权利要求10所述的计算机可读介质，其特征在于，在所述嵌 套事务第一次回退并释放写锁定时创建所述写异常中止补偿映射(272)。
12.如权利要求10所述的计算机可读介质，其特征在于，如果版本 号差与所述嵌套事务释放所述写锁定的次数正好匹配，则所述失败的乐观 读取实际上是有效的(320)。
13.如权利要求10所述的计算机可读介质，其特征在于，所述写异 常中止补偿映射保持在所述父事务的事务日志中(276)。
14.如权利要求13所述的计算机可读介质，其特征在于，在所述父 事务所进行的所有乐观读取之后在所述嵌套事务开始时，对所述写异常中 止补偿映射进行排序(276)。
15.如权利要求10所述的计算机可读介质，其特征在于，在父事务 回退期间，将所述写异常中止补偿映射与遭遇到的其它嵌套子事务的其它 写异常中止补偿映射聚集在一起，以形成聚集的写异常中止补偿映射 (294)。
16.如权利要求15所述的计算机可读介质，其特征在于，将所述聚 集的写异常中止补偿映射置于所述父事务的事务日志中(294)。
17.如权利要求16所述的计算机可读介质，其特征在于，在以逆序 处理所述父事务的事务日志时，将所述聚集的写异常中止补偿映射置于所 述父事务的事务日志中(312)。
18.一种用于在事务确认期间使用写异常中止补偿映射来避免错误 地破坏嵌套事务的父事务的方法，所述方法包括以下步骤：在处理父事务日志时，将在嵌套子事务中所看到的任何写异常中止补 偿映射聚集到聚集的写异常中止补偿映射中(312)；
如果乐观读取由于版本号不匹配而未能确认(314)，则咨询所述聚集 的写异常中止补偿映射来检索所述嵌套子事务的写锁定释放计数(316)； 以及如果版本号差与所述嵌套子事务的写锁定释放计数正好匹配(320)， 则所述乐观读取是有效的(322)。
19.如权利要求18所述的方法，其特征在于，如果所述版本号差不 与所述嵌套子事务的写释放计数正好匹配，则所述乐观读取是无效的 (324)。
20.一种具有用于使得计算机执行如权利要求18所述的步骤的计算 机可执行指令的计算机可读介质(200)。
说明书 :
背景
软件事务存储器(STM)是类似于数据库事务的、用于在并发计算中 控制对共享存储器的访问的并发控制机制。事务存储器的上下文中的事务 是对共享存储器执行一系列读取和写入的一段代码。STM用作传统锁定机 制的替换。STM允许更简单地编写并发程序。事务指定应当如同其隔离地 执行一样的代码序列。这一隔离错觉可以通过对象的细粒度锁定，以及通 过以在发现事务与某一其它事务相冲突的情况下允许回退该事务的副作用 的模式执行来实现。如果对于数据访问所生成的代码被修改成包括对这些 锁定和回退机制的支持，则可以说该访问被“事务化”。
许多STM系统支持嵌套事务，从而允许高效地合成使用事务所创作的 不同组件。如果嵌套事务的影响是与其包含(即，父)事务相同的隔离边 界的一部分，则认为它是封闭的。在封闭的嵌套事务提交时，其影响不对 系统的其余部分变得可见。相反，其影响变成父事务的一部分，仍然在进 行中，并且只有在父事务最终提交时才变得对系统的其余部分可见。在嵌 套事务回退时，其临时影响被撤消并且父事务的状态恢复到该嵌套事务开 始的点处。
使用就地写入和乐观读取的STM系统使用与每一可锁定存储器区域 相关联的版本号来指示何时对共享数据作出更改。读取事务将乐观地记录 存储器(对象、高速缓存行等)的版本号而不锁定该数据。在版本号在事 务的整个生命周期不改变的情况下，该事务可以提交。在释放其写锁定时， 写入事务递增版本号以用于提交或回退。版本号在回退期间必须增加，因 为写入事务临时就地更新了数据。这些更新对读取事务是可见的，并且必 须通知该事务不能提交，因为可能读取了不一致的数据。
在回退时，写入尚未被父事务写入的数据的嵌套事务必须递增版本号， 如同非嵌套(最高级)事务一样。然而，考虑其中父事务乐观地读取变量 X并且嵌套子事务第一次写入变量X的情况。父事务将在其日志中记录X 的版本号，如版本V1。嵌套事务将开始并取得对X的写锁定。如果嵌套事 务提交，则没有问题：写锁定未释放并被转移到父事务，并且父事务保持 一致，能够提交。然而，如果嵌套事务出于任何原因而回退，则它必须释 放写锁定并将X的版本号递增成V2。父事务将在提交时表现得不一致。X 的版本号是V2，但父事务在X是V1的时候读取了它，并且没有是谁将该 版本号更改成V2的记录。看起来父事务与另一事务冲突，但实际上是嵌套 子事务使得版本号增加，因而这实际上不是冲突。父事务被其子事务的回 退操作所破坏。这一问题使得STM系统经历父事务谬误的重新执行。
概述
公开了用于在事务存储器系统中检测嵌套子事务的错误地破坏 (doom)的父事务的各种技术和方法。在回退嵌套事务时，在给定嵌套事 务每一次释放写锁定时跟踪释放计数。例如，可以使用写异常中止补偿映 射来跟踪回退的每一嵌套事务所释放的每一锁定的释放计数。嵌套事务释 放写锁定的次数被记录在它们相应的写异常中止补偿映射中。可以在父事 务的确认期间使用释放计数来确定明显无效的乐观(optimistic)读取实际 上是否是有效的。
在一个实现中，在处理父事务日志时，所看到的对于嵌套子事务的任 何写异常中止补偿映射被聚集到父事务中的聚集的写异常中止补偿映射 中。如果乐观读取由于版本号不匹配而未能确认，则咨询聚集的写异常中 止补偿映射来检索嵌套子事务对特定变量的写锁定释放计数。如果版本号 差与嵌套子事务的写锁定释放计数正好匹配，则乐观读取是有效的。
提供本概述以便以简化形式介绍将在以下详细描述中进一步描述的一 些概念。本概述不旨在标识所要求保护的主题的关键特征或必要特征，也 不旨在用于帮助确定所要求保护的主题的范围。
附图简述
图1是一个实现的计算机系统的图示。
图2是在图1的计算机系统上操作的一个实现的事务存储器应用程序 的图示。
图3是图1的系统的一个实现的高级处理流程图。
图4是图1的系统的一个实现的处理流程图，其示出在创建和维护写 异常中止补偿映射时所涉及的各阶段。
图5是图1的系统的一个实现的处理流程图，其示出在事务回退期间 聚集的写异常中止补偿映射时所涉及的各阶段。
图6是图1的系统的一个实现的处理流程图，其示出在事务回退期间 使用写异常中止补偿映射来避免嵌套事务的错误地破坏的父事务时所涉及 的各阶段。
详细描述
此处的技术和方法可以在事务存储器系统的一般上下文中描述，但本 系统也用作除此之外的其它目的。在一个实现中，此处所描述的一个或多 个技术可被实现为诸如微软.NET框架等框架程序内的、或来自为开发者 提供开发软件应用程序的平台的任何其它类型的程序或服务的特征。在另 一实现中，此处所描述的一个或多个技术被实现为涉及开发在并发环境中 执行的应用程序的其它应用程序的特征。
在一个实现中，提供了允许检测和避免嵌套子事务对父事务的错误破 坏的事务存储器系统。此处使用的术语“破坏”旨在包括因为它们执行了 对后来被其它事务写入的一个或多个变量的一个或多个乐观读取而稍后将 被回退的事务。在尝试提交这样的事务时，失败的乐观读取将使得该事务 回退和重新执行。此处使用的术语“错误地破坏”旨在包括由于失败的乐 观读取而表现得被破坏、但归因于嵌套事务所执行的操作该乐观读取实际 上是有效的因此其实际上未被破坏的任何事务。此处使用的术语“嵌套事 务”旨在包括其影响被封闭在另一事务的隔离边界之内的任何事务。封闭 嵌套事务的事务被称为该嵌套事务的“父事务”，并且嵌套事务通常被称 为“子事务”。以按锁定释放计数来跟踪每一嵌套子事务释放写锁定的次 数。在一个实现中，在写异常中止补偿映射中跟踪这些计数。此处使用的 术语“写异常中止补偿映射”旨在包括存储每一嵌套子事务释放的每一锁 定的按锁定释放计数的数据结构。在事务确认或回退期间，多个写异常中 止补偿映射可以聚集到聚集映射中。
在确认父事务时，如果乐观读取使确认失败，则咨询当前聚集的写异 常中止补偿映射来查看事务存储器字中的版本号差是否与嵌套子事务对于 该对象或存储器区域的聚集释放计数正好匹配。如果是，则乐观读取实际 上是有效的，并且父事务不应被错误地破坏。此处使用的术语“事务存储 器字(TMW)”旨在包括提供给每一事务的、跟踪关于给定事务的诸如锁 定状态和版本号等各种信息的数据结构。例如，TMW可包括版本号和读取 者的列表/计数和/或指示符。在一个实现中，读取者的列表/计数和/或指示 符可包括在给定时间点访问特定值的读取者的数量的计数。在另一实现中， 读取者的列表/计数和/或指示符可包括在给定时间点访问特定值的特定读 取者(例如，悲观)的列表。在又一实现中，读取者的列表/计数和/或指示 符仅仅是指示在给定时间点存在访问特定值的一个或多个读取者(例如， 悲观)的标志或其它指示符。这些仅是示例，并且此处对术语TMW的使 用旨在涵盖用于跟踪事务状态的各种机制。
如图1所示，用于实现本系统的一个或多个部分的示例性计算机系统 包括诸如计算设备100等计算设备。在其最基本的配置中，计算设备100 通常包括至少一个处理单元102和存储器104。取决于计算设备的确切配置 和类型，存储器104可以是易失性的(如RAM)、非易失性的(如ROM、 闪存等)或是两者的某种组合。该最基本配置在图1中由虚线106来示出。
另外，设备100还可具有附加特征/功能。例如，设备100还可包含附 加存储(可移动和/或不可移动)，包括但不限于磁盘、光盘或磁带。这样 的附加存储在图1中由可移动存储108和不可移动存储110示出。计算机 存储介质包括以用于存储诸如计算机可读指令、数据结构、程序模块或其 它数据等信息的任何方法或技术来实现的易失性和非易失性、可移动和不 可移动介质。存储器104、可移动存储108和不可移动存储110都是计算机 存储介质的示例。计算机存储介质包括但不限于，RAM、ROM、EEPROM、 闪存或其它存储器技术、CD-ROM、数字多功能盘(DVD)或其它光存储、 磁带盒、磁带、磁盘存储或其它磁存储设备、或者可用于存储所需信息并 且可由设备100访问的任何其它介质。任何这样的计算机存储介质都可以 是设备100的一部分。
计算设备100包括允许计算设备100与其它计算机/应用程序115进行 通信的一个或多个通信连接114。设备100还可以具有诸如键盘、鼠标、笔、 语音输入设备、触摸输入设备等输入设备112。还可以包括诸如显示器、扬 声器、打印机等输出设备111。这些设备在本领域中公知且无需在此处详细 讨论。在一个实现中，计算设备100包括事务存储器应用程序200。事务存 储器应用程序200将在图2中更详细地描述。
现在转向图2并继续参考图1，示出了在计算设备100上操作的事务 存储器应用程序200。事务存储器应用程序200是驻留在计算设备100上的 应用程序中的一个。然而，可以理解，事务存储器应用程序200可另选地 或另外地被具体化为一个或多个计算机上的计算机可执行指令和/或与图1 所示的不同的变型。另选地或另外地，事务存储器应用程序200的一个或 多个部分可以是系统存储器104的一部分、可以在其它计算机和/或应用程 序115上、或可以是计算机软件领域的技术人员能想到的其它此类变型。
事务存储器应用程序200包括负责执行在此描述的技术中的一些或全 部的程序逻辑204。程序逻辑204包括用于在嵌套事务第一次回退并释放写 锁定时创建写异常中止补偿映射(WACM)的逻辑206(如以下参考图4 描述的)；用于在WACM的每一条目中在给定事务存储器字中记录嵌套事 务释放写锁定的次数的逻辑208(如以下参考图4描述的)；用于在父事务 日志中保持WACM的逻辑210(如以下参考图4描述的)；用于在特定嵌 套事务重新执行并再次回退的情况下使用并更新同一WACM的逻辑212 (如以下参考图4描述的)；用于在适当时聚集WACM的逻辑214(如以 下参考图5描述的)；用于在事务确认期间使用WACM来确定失败的乐观 读取真正有效还是无效的逻辑216(如以下参考图6描述的)；以及用于操 作该应用程序的其它逻辑220。
现在转向图3-6并继续参考图1-2，更详细地描述了用于实现事务存储 器应用程序200的一个或多个实现的各阶段。在某些实现中，图3-6的过 程至少部分地在计算设备100的操作逻辑中实现。图3是事务存储器应用 程序200的高级处理流程图。该过程在起始点240处开始。在嵌套事务回 退期间所释放的任何写锁定都有可能破坏父事务(阶段242)。在回退事务 时，记忆对版本号进行递增的每一次(阶段244)。系统针对回退的每一嵌 套事务来跟踪这一信息(阶段246)。在事务确认期间，系统使用这一信息 来确定使确认失败的特定乐观读取是否因为重新执行嵌套子事务所造成的 差异而实际上是有效的(阶段248)。这些阶段在图4-6中更详细地描述。 该过程在结束点250处结束。
图4示出在创建和维护写异常中止补偿映射时所涉及的各阶段的一个 实现。该过程在起始点270处开始，在那里在嵌套事务第一次回退并释放 写锁定时创建由唯一锁定标识符键控的写异常中止补偿映射(WACM)(阶 段272)。该WACM中的每一条目在给定事务存储器字上记录嵌套事务释 放写锁定的次数(阶段274)。
WACM保持在父事务的日志中，并且在父事务所进行的所有乐观读取 之后在嵌套事务开始时被排序(阶段276)。如果特定嵌套事务重新执行并 再次回退，则系统使用同一WACM并用任何新写锁定释放来更新它(阶段 278)。如果嵌套事务再次得到其在先前执行时所得到的锁定，则在WACM 中递增对于该事务存储器字的计数(阶段280)。该过程在结束点282处结 束。
图5示出在事务回退期间在聚集WACM时所涉及的各阶段的一个实 现。该过程在起始点290处开始，在那里还作为许多嵌套子事务的父事务 的嵌套事务随时间可能在其日志中散布有多个WACM(阶段292)。如果 在事务回退期间遭遇多个WACM，则将归因于嵌套子事务的所有WACM 聚集到单个WACM并将其置于父事务的日志中(阶段294)。该过程在结 束点296处结束。
图6示出在事务确认期间使用WACM来避免错误地破坏嵌套事务的父 事务时所涉及的各阶段的一个实现。该过程在起始点310处开始，在那里 在逆序处理父事务的日志时，在处理乐观读取条目时，将所看到的任何 WACM聚集到临时WACM以用于确认过程(阶段312)。如果乐观读取 由于版本号不匹配而未能确认(判定点314)，则使用TMW地址作为键来 咨询临时WACM(阶段316)。如果存在关于该TMW地址的匹配条目(判 定点318)，则系统计算与该条目相关联的计数是否与版本号差正好匹配(判 定点320)。如果计数与版本号差正好匹配(判定点320)，则乐观读取是 有效的并且差仅仅是由于重新执行嵌套子事务所造成的(阶段322)。如果 否，则乐观读取是无效的并且是由于其它事务的提交/回退所造成的(阶段 324)。对整个父事务日志重复这些阶段(判定点326)。该过程在结束点 328处结束。
尽管用对结构特征和/或方法动作专用的语言描述了本主题，但可以理 解，所附权利要求书中定义的主题不必限于上述具体特征或动作。相反， 上述具体特征和动作是作为实现权利要求的示例形式公开的。落入在此所 述和/或所附权利要求所描述的实现的精神的范围内的所有等效方案、更改 和修正都期望受到保护。
例如，计算机软件领域普通技术人员将认识到，此处所讨论的示例可 以在一个或多个计算机上不同地组织来包括比这些示例中所描绘的更少或 更多选项或特征。