基于元对象协议实现原子数据类型的研究

### 基于元对象协议实现原子数据类型的研究 #### 1. 背景与概念 在并发且不可靠的环境中维护数据一致性是许多应用系统的重要问题。为支持一致性，使访问数据对象的并发活动具有原子性是很有用的，这些原子活动被称为事务。事务通常由多个操作组成，其特性确保事务能原子性地执行。也就是说，如果一个事务提交，对外部世界而言，构成该事务的所有操作应是连续执行的，没有其他事务的操作介入，也不会执行到一半停止。事务通过减少需要考虑的情况数量，简化了维护系统一致性的问题。 为提高并发级别，许多研究人员建议使用应用程序的语义进行并发控制。基于语义的并发控制协议大致可分为两类，取决于它们是基于事务语义还是对象语义。在数据库领域，这方面的工作主要集中在事务上。Lamport 提出使用事务语义来提高数据库系统的并发性，Gray 展示了传统事务模型的局限性，Weikum 引入了多级事务模型，利用不同级别操作的语义来提高并发性。 更面向对象的方法是通过定义抽象数据类型，利用数据的语义进行特定类型的并发控制。Schwarz 和 Spector 提出了基于抽象数据类型操作可交换性概念的锁定协议，Herlihy、Liskov 和 Weihl 引入了原子数据类型的概念。 原子数据类型是具有同步和恢复属性的抽象数据类型。原子数据类型的实例称为原子对象，负责确保自身的原子性。已经有很多关于实现原子数据类型所产生的不同问题的研究，并且已经构建了许多支持使用原子数据类型进行事务处理的系统，如 Argus、Clouds、Arjuna、TABS 和 Camelot/Avalon 等。这些系统虽然在细节上有所不同，但都采用显式或混合方法来实现原子数据类型，其缺点在之前的讨论中已指出。 FIDE 项目提出了在面向对象数据库语言中添加用户定义的并发控制的建议。该建议允许程序员声明性地指定原子数据类型的并发行为，可用于支持隐式方法，但它在恢复方面处理不足，特别是要求事务按启动顺序提交，且未解决级联中止的问题。 Atkins 描述了一个支持原子数据类型的自适应服务器，它可以根据状态信息、遇到的冲突历史或使用预设的事务优先级选择合适的并发控制策略。 最近，Guerraoui 提出使用 o - 原子性来支持原子数据对象的组合，并概述了基于抽象 AtomicObject 类的 o - 原子性实现。其思想是特定应用的原子数据类型应从使用特定并发控制协议来保证 o - 原子性的 AtomicObject 子类派生。虽然这种方法与我们的方法有一些相似之处，但 Guerraoui 要求每次事务对原子数据对象调用操作时都要在内部调用访问操作，而我们使用元级别编程实现相同效果。此外，Guerraoui 使用混合方法支持原子数据类型，而我们使用隐式方法。 在并发面向对象编程语言领域，大量工作关注于实现同步代码与实现对象操作的代码之间的清晰分离（即所谓的“继承异常”）。我们使用元对象协议支持原子数据类型的动机与此类似，只是我们处理的是事务并发问题，而不仅仅是进程并发问题。 #### 2. 原子数据类型的隐式方法 为简化构建原子数据类型的任务，我们提出了一种隐式方法来定义原子数据类型，并在持久化编程语言 PC++ 中实现了该方法。 ##### 2.1 定义原子数据类型 在 PC++ 中，原子数据类型的串行规范和并发规范有明确的区分。串行规范描述了在没有并发和故障的情况下，该类型实例的允许行为；并发规范描述了实例应如何响应并发和故障。程序员只需做很少的额外工作就能使对象类型具有原子性。除了声明性地指定操作的并发语义外，原子数据类型的定义就像在顺序、可靠环境中实现的普通抽象数据类型一样。 PC++ 开发了一种小语言，让用户以无效关系（invalidates relation）的形式声明性地指定对象操作的并发语义。PC++ 使用这种无效关系自动生成特定类型的同步和恢复代码。 无效关系描述了同一类型实例上操作之间可能的冲突，这些冲突会限制并发性。对于同一类型的两个操作 p 和 q，如果存在某个对象 d，使得在 d 上执行 q 的结果可能与先执行 p 再执行 q 的结果不同，则称 p 使 q 无效。这里的结果指操作返回的结果，而不是操作对对象状态的影响。 在指定无效关系时，每个操作由其名称和结果表示。操作的结果简单地分为失败或成功（用 OK 表示），因为通常只有这种区分对无效关系有显著影响。如果合适，操作的第一个参数也可以考虑在内，两个参数之间的关系可以分类为“=”或“#”。 例如，假设有两个操作 oper1 和 oper2，如果 oper1 仅在它们的第一个参数相同且都成功时使 oper2 无效，则这种冲突可以表示为：((oper1, OK) (oper2, OK) =)。 为了在 PC++ 中定义一个原子类，程序员只需在普通 C++ 类定义前放置预处理器指令 atomic，并添加无效关系部分。例如，考虑一个 Account 类，它有一组相关操作：向账户存入资金、从账户支取资金和检查账户余额。可以在 Account 的 C++ 类定义中添加适当的无效关系，以定义一个 PC++ 原子数据类型，如下所示： ```cpp atomic class Account { private: Money amount; public: Account(); Status credit(Money); Status debit(Money); Money check(); invalidates relation: ((credit, OK) (check, OK)) ((debit, OK) (check, OK)) ((debit, OK) (debit, OK)) ((credit, OK) (debit, failed)); }; ``` 在这个例子中，无效关系描述了四种可能的冲突：成功的存入操作使成功的检查操作无效；成功的支取操作使成功的检查操作无效；成功的支取操作使另一个成功的支取操作无效；成功的存入操作使失败的支取操作无效。并发控制机制对无效关系的解释由 PC++ 自动处理，因此实现 Account 类的应用代码不包含显式的同步代码（尽管需要使用特殊形式的返回语句来指示操作是否成功）。 ##### 2.2 构造事务 程序员可以使用 PC++ 系统提供的 Transaction 类来构造访问原子数据类型实例的事务。构成事务主体的计算由与该事务关联的 Transaction 对象实例控制。 Transaction 类提供了三个基本操作来声明和控制事务：begin - transaction、commit - transaction 和 abort - transaction。begin - transaction 操作启动一个事务，该事务可以由 commit - transaction 或 abort - transaction 操作终止。由 abort - transaction 操作终止的事务肯定会被中止，其部