| 主权项 |
1.一种基于多线程的长事务并行执行方法，其特征在于：并行执行长事务包括以下步骤：（1）、将长事务描述为一个扩展的有向图。长事务可以形式化表示为一个扩展的有向图LT=(T，E，R)，其中T ={t1,t2,…,tn}是原子事务集合，且每个原子事务且都具有ACID特性；E={e1,e2,…em}是原子事务间依赖关系集合，如ei=ti→tk表示原子事务tk的开始由ti的执行结果决定，若ti提交时tk开始执行，则称为提交依赖，若ti回滚时tk开始执行，则称为回滚依赖；R＝{r1,r2,…,rn}是逻辑关系的集合，如ri表示一个以ti为终点的事务之间的“与”、“或”逻辑表关系。（2）、将长事务LT分割为若干个可以并行执行的子事务LT’。LT’是长事务的一个子集，可以包含一个或多个原子事务，即子事务LT’=(T’，E’，R’)，其中T’<img file="FDA0000266088341.GIF" wi="38" he="66" />T，E’<img file="FDA0000266088342.GIF" wi="47" he="66" />E，R’<img file="FDA0000266088343.GIF" wi="47" he="66" />R。通过将长事务划分为若干个子事务，当子事务之间不存在依赖关系时即可并行执行。其分割过程包括以下步骤：（2.1）、分析长事务中所包含的原子事务、原子事务之间的依赖关系、原子事务直接的逻辑关系实现，建立长事务扩展有向图（EDG）。（2.2）、根据长事务扩展有向图(EDG)，合并有环子图，生成扩展有向无环图（EDAG）。（2.3）、循环查找EDAG中的顺序事务。若当前事务只有唯一的孩子事务并且该孩子事务的父事务也是唯一的，则将它们是顺序事务，合并它们。（2.4）、如果EDAG中仅包含一个子事务，则说明该长事务无法并行执行，否则输出并行结果，该结果是包含多个可并行执行的子事务。（3）、基于POSIX线程库（OpenM语言或者Windows线程API）派生若干个子线程并行执行长事务。长事务被划分为若干个子事务之后，其执行过程如下：（3.1）、在长事务开始执行时，只生成一个线程（称为主线程），由它负责执行。（3.2）如果遇到可以并行执行的子事务时，则根据子事务的数量派生(Fork)出若干个子线程（称为辅助线程）并行执行。（3.3）、在并行子事务执行过程中，如果又遇到可以并行执行的子事务，则继续派生新的辅助线程来执行新的并行子事务，此即为并行嵌套，可派生的辅助线程数目依赖于多核处理器的核数。（3.4）、当辅助线程执行完毕后，则与主线程会和（Join），由主线程单独执行长事务，如果又遇到可并行的子事务，则转到（3.2），否则直到长事务执行完毕。（4）、长事务并行执行的硬件环境是多核处理器(或多CPU处理器)，这些平台为TLP技术提供了平台支撑。 |
