一种基于软件事务内存的并发缺陷规避系统及方法

摘要

本发明公开了一种基于软件事务内存的并发缺陷规避系统及方法，所述系统由事务自动划分模块、可回滚内存模块、可回滚I/O模块、条件变量处理模块和加锁解锁处理模块5个模块构成，所述方法为：一、实现对目标程序的自动事务划分；二、实现内存事务化；三、实现执行流的可回滚化；四、实现I/O事务化；五、实现对死锁、数据竞争、原子性违背和顺序违背的有效规避。本发明能够自动事务化C/C++多线程程序、合理处理条件变量、支持普通文件和字符文件在系统层面、C语言层面和C++语言层面的事务化I/O和消除包括死锁、数据竞争、原子性违背和顺序违背在内的多种并发缺陷。

说明书

技术领域

本发明属于软件工程和并行计算技术领域，涉及一种新的基于软件事务内存的并发缺陷规避系统及方法。

背景技术

软件事务内存（Software Transactional Memory, STM）是一种并发控制机制。借助于这种机制，程序员可以对程序源码进行事务划分并保证作为事务的代码段的原子性和隔离性执行：一个事务要么成功执行，要么与其他事务存在冲突而撤销自身对共享内存的所有更改、回滚到事务开始点并重新执行。软件事务内存用事务代替锁，通过简化数据保护、允许事务顺序推理、消除死锁风险和支持事务可组合性，可大幅降低并发程序的设计难度；通过乐观执行，可提升并发程序的并发度与执行效率。尽管软件事务内存有望提高并发程序的并发度并消除并发缺陷，但目前在实际并发程序中并没有得到广泛应用，因为它仍然存在以下3个缺点：

（1）对遗产代码兼容性低，将现有基于锁机制的并发程序改造为基于软件事务内存的并发程序需要修改大量代码；

（2）不支持在事务中使用I/O操作和系统调用，影响较大的开源STM库和商业STM库一般都禁止在事务中调用I/O函数和系统函数；

（3）不能合理处理条件变量操作，一般STM库都禁止在事务中调用条件变量函数。

由于缺点（2）和（3），现有软件事务内存方法不能正确规避绝大部分涉及到I/O操作、系统调用和条件变量操作的并发缺陷，这严重影响了人们对软件事务内存的接纳程度和使用意愿。

发明内容

为了解决传统软件事务内存机制人工参与度高和并发缺陷规避能力弱的问题，本发明提出了一种新的基于软件事务内存的并发缺陷规避系统及方法。

本发明的目的是通过以下技术方案实现的：

一种基于软件事务内存的并发缺陷规避系统，由5个模块构成：事务自动划分模块（Transaction Partition Module, TPM）、可回滚内存模块（Revocable Memory Module,RMM）、可回滚I/O模块（Revocable I/O Module, RIOM）、条件变量处理模块（ConditionVariable Handling Module, CVHM）和加锁解锁处理模块（Lock/Unlock HandlingModule, LUHM），其中：

所述事务自动划分模块用于劫持线程间操作，利用它们动态地对目标程序进行自动事务划分，并调用可回滚执行模块（Revocable Execution Module, REM）和事务执行模块（Transaction Execution Module, TEM）来对事务进行管理；

所述事务执行模块用于执行在启动、提交和撤销事务时需要执行的逻辑；

所述可回滚执行模块用于在事务启动/撤销时保存/恢复事务所在线程的栈帧和CPU寄存器；

所述可回滚内存模块用于劫持所有内存访问操作，并综合利用进程继承机制、内存映射机制、进程层面的内存保护机制和信号处理机制来使得这些操作具有可回滚化的执行效应；

所述可回滚I/O模块用于劫持所有常用的操作系统级别和C语言级别的I/O操作，并利用虚拟文件系统和文件流到文件描述符映射使得这些操作具有可回滚化的执行效应；

所述条件变量处理模块CVHM用于劫持所有条件变量操作，在用户空间重新实现条件变量信号发送和等待逻辑；

所述加锁解锁处理模块用于劫持所有加锁解锁操作，劫持所有关于锁的初始化/销毁操作和属性设置/获取操作，并将它们置为空操作。

一种基于软件事务内存的并发缺陷规避方法，包括如下步骤：

一、通过劫持每个线程的线程间操作并将它们之间的代码划分为事务，实现对目标程序的自动事务划分；

二、通过替代线程以进程、利用进程间虚拟内存保护机制并定制内存分配回收逻辑，实现内存事务化；

三、通过在启动/撤销事务时保存/恢复当前线程的栈帧和CPU寄存器，实现执行流的可回滚化；

四、通过建立和维护虚拟文件系统，并将I/O操作重定向到它们上，实现I/O事务化；

五、通过置空加锁解锁操作、定制条件变量操作和事务性地提交内存与I/O变更，实现对死锁、数据竞争、原子性违背和顺序违背的有效规避。

本发明能够自动事务化C/C++多线程程序、合理处理条件变量、支持普通文件和字符文件在系统层面、C语言层面和C++语言层面的事务化I/O和消除包括死锁、数据竞争、原子性违背和顺序违背在内的多种并发缺陷。

附图说明

图1是本发明的框架图。

图2是全局内存可回滚化机制示意图。

图3是堆内存管理机制示意图。

图4是可回滚I/O机制示意图。

图5是条件变量内存页组织结构示意图。

具体实施方式

下面结合附图对本发明的技术方案作进一步的说明，但并不局限于此，凡是对本发明技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围，均应涵盖在本发明的保护范围中。

具体实施方式一：本实施方式提出了一种基于软件事务内存的并发缺陷规避系统，如图1-5所示，主要由5个模块构成：事务自动划分模块（Transaction PartitionModule, TPM）、可回滚内存模块（Revocable Memory Module, RMM）、可回滚I/O模块（Revocable I/O Module, RIOM）、条件变量处理模块（Condition Variable HandlingModule, CVHM）和加锁解锁处理模块（Lock/Unlock Handling Module, LUHM），其中事务划分模块又调用可回滚执行模块（Revocable Execution Module, REM）和事务执行模块（Transaction Execution Module, TEM）来对事务进行管理。

所述事务自动划分模块TPM用于劫持线程间操作，利用它们动态地对目标程序进行自动事务划分并在事务执行模块和可回滚执行模块的帮助下对事务进行管理。

所述事务执行模块TEM用于执行在启动、提交和撤销事务时需要执行的逻辑。具体表现为：

（1）事务tx在启动时，首先检查是否有其他事务发送来的未接收信号；如果有的话，就接收并根据信号类型做相应处理；tx然后保存栈帧和CPU寄存器、创建关于全局内存区域和全局堆内存区域的私有拷贝、创建私有版本号数组、创建私有虚拟文件系统和创建私有文件流到文件描述符映射（Stream-to-Descriptor>

（2）事务tx在提交时，先进行内存一致性检查，然后进行文件一致性检查；如果tx能通过所有检查，则它原子性地提交所有内存更改和文件更改。

（3）事务tx在撤销时，丢弃所有对内存和版本号数组的更改，丢弃所有缓存在私有虚拟文件系统的文件更改，清空进程间文件操作列表，删除或者关闭执行过程中在真实文件系统中创建或者打开的文件，释放进程间锁，如果目前正占据该锁的话，恢复tx在启动时保存的栈帧和CPU寄存器值并回滚到tx开始点重新执行。

所述可回滚执行模块REM用于在事务启动/撤销时保存/恢复事务所在线程的栈帧和CPU寄存器。

所述可回滚内存模块RMM用于劫持所有内存访问操作，并综合利用进程继承机制、内存映射机制、进程层面的内存保护机制和信号处理机制来使得这些操作具有可回滚化的执行效应。具体表现为：

（1）在启动事务tx时，RMM将tx的全局内存私有映射和堆内存私有映射中的每个内存页的访问权限置为不可访问，即PROT_NONE。

（2）在事务tx执行时，RMM在页粒度上跟踪并记录目标程序的内存访问。对于一个访问权限为PROT_NONE的受保护页p，tx对p的首次访问会让RMM将p添加到tx的访问集中并将将p的访问权限置为PROT_READ。如果tx对p的接下来的访问是写访问，则RMM将p添加到tx的写集和访问集中，并将访问权限置为PROT_READ|PROT_WRITE。

（3）在事务tx提交时，RMM检查它读取过的数据是否仍然是最新的。如果是的话，则tx通过冲突检查，RMM提交其内存更改。否则RMM丢弃tx缓存在写集中的内存更改，令其回滚到开始点并重新执行。

（4）重写所有基本C/C++内存分配回收操作，使得RMM能够像回滚任何对堆内存或者全局内存的内存访问操作那样回滚内存分配操作。

所述可回滚I/O模块RIOM用于劫持所有常用的操作系统级别和C语言级别的I/O操作，并利用虚拟文件系统和文件流到文件描述符映射使得这些操作具有可回滚化的执行效应。通过令普通文件和字符文件的系统级别和C级别I/O操作具有可回滚化的执行效应，RIOM能免费地使得C++语言级别的、与普通文件和字符文件相关的I/O操作也居于可回滚化的执行效应。具体表现为：

（1）创建并维护一个线程间的全局虚拟文件系统和一个全局文件流到文件描述符映射SDM。

（2）在事务tx启动时，RIOM为tx建立一个关于全局虚拟文件系统的快照和一个关于全局SDM的快照。

（3）在事务tx执行时，RIOM将所有的I/O操作直接或者间接地通过私有SDM定向到其私有虚拟文件系统上。

（4）在事务tx提交时，RIOM通过分别比较事务的私有文件系统和私有SDM与相应的全局文件系统和全局SDM是否一致来判断tx是否与其他已提交事务存在冲突。如果有任何I/O冲突纯在，则RIOM撤销tx并令其重新执行。

所述条件变量处理模块CVHM用于劫持所有条件变量操作，在用户空间重新实现条件变量信号发送和等待逻辑。当事务tx执行条件变量signal/wait操作时，CVHM会以提交事务的方式来结束当前事务tx，然后执行一个定制化的信号发送或者等待逻辑。一旦等到该定制化信号发送/等待逻辑执行完毕，CVHM就创建一个新的事务来执行tx中的剩余部分。

所述加锁解锁处理模块LUHM用于劫持所有加锁解锁操作，劫持所有关于锁的初始化/销毁操作和属性设置/获取操作，并将它们置为空操作，因为关键区现在在事务的保护下就能得到原子性执行。

具体实施方式二：本实施方式提出了一种基于软件事务内存的并发缺陷规避方法，具体实施步骤如下：

一、通过劫持每个线程的线程间操作并将它们之间的代码划分为事务，实现对目标程序的自动事务划分，能够在无需任何人工干预的情况下自动事务化目标程序。具体步骤如下：

（1）为降低对目标程序实施软件事务内存的人工参与度，通过指派线程间操作作为事务的边界来自动进行事务划分（见图1）；

（2）通过将事务内的所有内存访问都视为共享访问来自动确定哪些访问是共享访问；

（3）通过置加锁解锁操作为空操作与定制条件变量wait/signal操作来自动改变代码的控制结构。

二、通过替代线程以进程、利用进程间虚拟内存保护机制并定制内存分配回收逻辑，实现内存事务化。具体步骤如下：

（1）在启动事务tx时，RMM将tx的全局内存私有映射和堆内存私有映射中的每个内存页的访问权限置为不可访问，即PROT_NONE。

（2）在事务tx执行时，RMM在页粒度上跟踪并记录目标程序的内存访问。对于一个访问权限为PROT_NONE的受保护页p，tx对p的首次访问会让RMM将p添加到tx的访问集中并将p的访问权限置为PROT_READ。如果tx对p的接下来的访问是写访问，则RMM将p添加到tx的写集和访问集中，并将访问权限置为PROT_READ|PROT_WRITE。

（3）在事务tx提交时，RMM检查它读取过的数据是否仍然是最新的。如果是的话，则tx通过冲突检查，RMM提交其内存更改。否则RMM丢弃tx缓存在写集中的内存更改，令其回滚到开始点并重新执行。

（4）重写所有基本C/C++内存分配回收操作（见图3），使得RMM能够像回滚任何对堆内存或者全局内存的内存访问操作那样回滚内存分配操作。

三、通过在启动/撤销事务时保存/恢复当前线程的栈帧和CPU寄存器，实现执行流的可回滚化。具体步骤如下：

（1）在事务tx启动时，保存事务所在线程的栈帧和CPU寄存器；

（2）在事务tx撤销时，恢复事务所在线程的栈帧和CPU寄存器。

四、通过建立和维护虚拟文件系统，并将I/O操作重定向到它们上，实现I/O事务化。如图4所示，具体步骤如下：

（1）创建并维护一个线程间的全局虚拟文件系统和一个全局文件流到文件描述符映射SDM。

（2）在事务tx启动时，RIOM为tx建立一个关于全局虚拟文件系统的私有快照和一个关于全局SDM的私有快照。

（3）在事务tx执行时，RIOM将所有的I/O操作直接或者间接地通过私有SDM定向到其私有虚拟文件系统上。

（4）在事务tx提交时，RIOM通过分别比较事务的私有文件系统和私有SDM与相应的全局文件系统和全局SDM是否一致来判断tx是否与其他已提交事务存在冲突。如果有任何I/O冲突纯在，则RIOM撤销tx并令其重新执行。

五、通过置空加锁解锁操作、定制条件变量操作和事务性地提交内存与I/O变更，实现对死锁、数据竞争、原子性违背和顺序违背的有效规避。

如图5所示，实施条件变量定制操作的具体步骤如下：

（1）在用户空间重新实现条件变量的数据结构；

（2）在事务tx执行条件变量signal/wait操作时，CVHM会以提交事务的方式来结束当前事务tx，然后执行一个定制化的信号发送或者等待逻辑。一旦等到该定制信号发送/等待逻辑执行完毕，CVHM就创建一个新的事务来执行tx中的剩余部分。

实施置空加锁解锁操作的具体步骤如下：

（1）劫持所有加锁解锁操作；

（2）劫持所有关于锁的初始化/销毁操作和属性设置/获取操作；

（3）将劫持到的操作置为空操作。