MDBS中一种改进的并发事务调度算法

MDBS中并发事务的调度策略必须满足可串行化准则,论文主要分析以事务提交图为中心的调度算法TM2,虽然保证了全局事务提交顺序的可串行化,但在提交时才进行冲突检测方式存在缺点,提出改进后的事务调度算法TM3不仅保证了全局事务的可串行化和防止了全局死锁的发生,还提高了全局事务执行的并发度。最后通过实验在数据库加速引擎中进行模拟,对比了两种调度算法的性能。     

多数据库事务并发调度算法优化技术研究

研究优化调度数据库中事务问题,为保证多数据库中事务提交顺序,提高事务执行及提交的并发度,研究了事务提交图的调度算法TM2,针对算法TM2中事务管理器无法检测到全局事务与局部事务的间接冲突,提出了优化算法TMO,采用ticket算法在全局事务的每个子事务之间增加数据操作,以便在每个成员数据库的全局子事务之间创造直接冲突,并通过添加保存点恢复中止事务代替重做事务,保持了多数据库中事务的可串行化.通过仿真,对比了两种调度算法的性能.得出算法TMO解决了事务的可串行化问题,提高了事务的并发度,保证了事务的一致性.     

两阶段封锁可串行化强制性的实现

数据库的共享性是建立在多个共享事务的并发执行基础之上的。为了保证多个事务的并发执行,并发控制器对各事务动作的调度应当是可串行化的。然而,在实际调度过程中,并非所有的调度都是可串行化的。为了确保事务之间的可串行性关系,可使用两阶段封锁将非可串行化调度强制实现为可串行化调度。     

基于优先图冲突可串行化判断

在对数据库同时进行读写的多个事务调度中,为了保证所有事务的并发执行,一个重要条件就是各个事务之间是否可串行化或冲突可串行化。然而,当事务较多较复杂时,要准确判断事务调度是否满足这些条件,难度较大。优先图通过事务内部的本征关系表征各个事务之间的逻辑顺序,根据优先图内有环或无环可准确判断调度是否可串行化或冲突可串行化。     

基于Sagas模型的改进事务工作流模型

Sagas模型要求所有子事务都要有对应的补偿子事务,任何子事务失败必须强制其它所有子事务失败,不能很好支持多事务多实例的并发执行。这三个缺陷使得Sagas模型至今不能运用到商业工作流系统中。针对Sagas模型的缺陷,提出一种改进的Sagas事务工作流模型,对子事务属性进行了分类并通过构造子事务间的关联关系使得可补偿子事务失败时无需强制所有子事务失败;引入补偿服务完善了工作流模型的语义;给出了基于事务实例锁集和后继子事务类型集的多事务多实例并发运行算法。该模型解决了Sagas模型存在的问题。     

拓扑排序在并发控制可串行化算法中的应用

并发控制是分布式数据库管理系统的重要组成部分，并发控制用来控制多个事务的并发运行，避免它们之间的相互干扰，保证每个事务都产生正确的结果。该文从构造并发控制可串行化的前趋图出发，利用拓扑排序进一步研究了并发控制可串行化的算法，详细阐述了冲突可串行和状态可串行化的测试算法并运用在实例中。该算法可以作为并发控制可串行化的正确性准则，在实际中，应结合其它算法共同运用。     

基于冲突率预测的自适应并发控制算法

并发控制算法能够保证数据库事务集并发执行的正确性和一致性。为了提高并发事务的执行效率,提出了一种基于冲突率预测的自适应并发控制算法(ACC-PRC)。该算法将并发控制过程分为信息收集和策略选择两个阶段。信息收集阶段利用先验事务队列保证事务执行的可串行化,并且利用循环冲突队列收集系统的事务执行状态。策略选择阶段在循环冲突队列上运用改进的加权移动平均法预测下一阶段冲突率,并根据双向阈值决策下一阶段的并发策略。所提算法在事务到达率较高时能保持良好的事务执行效率,同时能够准确及时地感知冲突率的变化。对比实验表明ACC-PRC算法的综合性能优于HCC算法和ADCC算法。     

数据库并发操作的可串行化调度与死锁检测算法

封锁与可串行化调度是数据库并发操作采取的两种主要措施。判断一个调度是否可串行化调度的最有效方法是两段锁协议。但是,一方面,事务遵守两段锁协议只是可串行化调度的充分条件而不是必要条件;另一方面,遵守两段锁协议的事务仍可能发生死锁。文中给出了一种算法,利用该算法,不仅可判断出一个调度是否为可串行化调度,而且可判断出该调度是否会发生死锁。     

基于两层模式的Web服务工作流失效恢复算法

现有的Web事务工作流恢复算法通常未考虑用户的个性需求,也没有考虑恢复时的连锁恢复情况.为此,定义全局事务工作流模式和执行事务模式2种失效恢复粒度,并提出基于这2种粒度的失效恢复算法.通过细粒度的执行事务模式进行事务实例级的层次式递归恢复,采用粗粒度的全局事务工作流模式进行模型级的恢复,并用来满足客户的个性需求.该算法...     

视图事务经历的串行化调度分祈

提出用依赖图方法判断数据仓库实例化视图调度是否可串行化。对传统的２ＰＬ协议冲突操作概念加以扩展,就可构造出依赖图。如果依赖图无环,实例化视图事务调度就是串行化调度。还设计了事务调度的数据仓库新结构和Ｓｅｒｉ－Ｓｃｈｅ算法。     

事务工作流的建模和分析

事务工作流由若干个事务组成，其执行满足松弛原子性．只有良构的事务工作流才能保证所有执行均满足松弛原子性．事务具有不同的可补偿特性和可重复特性，在包含多种控制结构的复杂事务工作流中，事务之间组合失配问题可能造成事务工作流的非良构性．该文给出了事务工作流模型及良构性的形式化定义，提出了一个良构性判断定理，通过一种构造性的方法来有效地验证事务工作流的良构性，还设计了事务工作流的描述语言ISWDL并实现了良构性验证器．     

工作流事务性研究综述

阐述了工作流中事务性的起源和发展,讨论了事务工作流在建模阶段将业务模型与事务性相结合所采用的主要方法,总结了事务工作流中并发控制机制和采用的各种调度算法,研究了事务工作流的错误恢复机制,概括了广泛应用的补偿机制的研究现状,论述了面向Web服务工作流事务性的特点及相关研究,并展望工作流事务性未来的研究方向.     

Chronological scheduling of transactions with temporal dependencies

Database applications often impose temporal dependencies between transactions that must be satisfied to preserve data consistency. The extant correctness criteria used to schedule the execution of concurrent transactions are either time independent or use strict, difficult to satisfy real-time constraints. On one end of the spectrum, serializability completely ignores time. On the other end, deadline scheduling approaches consider the outcome of each transaction execution correct only if the transaction meets its real-time deadline. In this article, we explore new correctness criteria and scheduling methods that capture temporal transaction dependencies and belong to, the broad area between these two extreme approaches. We introduce the concepts ofsuccession dependency andchronological dependency and define correctness criteria under which temporal dependencies between transactions are preserved even if the dependent transactions execute concurrently. We also propose achronological scheduler that can guarantee that transaction executions satisfy their chronological constraints. The advantages of chronological scheduling over traditional scheduling methods, as well as the main issues in the implementation and performance of the proposed scheduler, are discussed.     

基于隔离域的事务工作流并发控制

事务工作流系统中存在多个流程的多个实例同时并发执行的情况,所以多个活动同时访问共享资源时出现访问冲突.为保证流程的正确执行和提高活动的并发度,基于事务的隔离性特征,提出了隔离域的概念和相关属性,并在建模阶段采用业务流程和事务需求分开定制的方式,通过设置隔离域的隔离属性来控制各流程实例并发活动的执行,并且给出了基于隔离域的并发控制算法,从而有效地提高了流程和活动的并发度,并避免丢失修改等现象的发生.     

Cloud-aware data intensive workflow scheduling on volunteer computing systems

Volunteer computing systems offer high computing power to the scientific communities to run large data intensive scientific workflows. However, these computing environments provide the best effort infrastructure to execute high performance jobs. This work aims to schedule scientific and data intensive workflows on hybrid of the volunteer computing system and Cloud resources to enhance the utilization of these environments and increase the percentage of workflow that meets the deadline. The proposed workflow scheduling system partitions a workflow into sub-workflows to minimize data dependencies among the sub-workflows. Then these sub-workflows are scheduled to distribute on volunteer resources according to the proximity of resources and the load balancing policy. The execution time of each sub-workflow on the selected volunteer resources is estimated in this phase. If any of the sub-workflows misses the sub-deadline due to the large waiting time, we consider re-scheduling of this sub-workflow into the public Cloud resources. This re-scheduling improves the system performance by increasing the percentage of workflows that meet the deadline. The proposed Cloud-aware data intensive scheduling algorithm increases the percentage of workflow that meet the deadline with a factor of 75% in average with respect to the execution of workflows on the volunteer resources.     

Towards the Scheduling of Multiple Workflows on Computational Grids

The workflow paradigm has become the standard to represent processes and their execution flows. With the evolution of e-Science, workflows are becoming larger and more computational demanding. Such e-Science necessities match with what computational Grids have to offer. Grids are shared distributed platforms which will eventually receive multiple requisitions to execute workflows. With this, there is a demand for a scheduler which deals with multiple workflows in the same set of resources, thus the development of multiple workflow scheduling algorithms is necessary. In this paper we describe four different initial strategies for scheduling multiple workflows on Grids and evaluate them in terms of schedule length and fairness. We present results for the initial schedule and for the makespan after the execution with external load. From the results we conclude that interleaving the workflows on the Grid leads to good average makespan and provides fairness when multiple workflows share the same set of resources.     

满足工作流执行时限的可抢占虚拟机实例配置和调度方法研究

随着云计算的迅速发展,将工作流部署到云计算平台已经成为了常见的选择。相比于传统的本地工作流,云工作流不仅要考虑计算时长等要求,还要考虑其产生的经济开销。而云计算服务商为了提高资源利用率,提供了可抢占虚拟机实例这种非常廉价但是不稳定的资源。针对工作流在云计算中的调度和执行问题,提出一种满足工作流执行时限的可抢占虚拟机实例配置和调度方法。该方法使用马尔科夫模型和动态规划方法,对可抢占虚拟机实例的价格进行预测,并得到成本最低的出价策略。同时,结合工作流的执行时限要求,在估计的出价策略下对工作流中使用的实例进行配置。实验结果显示,相比于全部使用按需付费虚拟机实例,该方法在满足工作流执行时限的前提下最高可以节省89.9%的计算成本。     

事务工作流模型定义及完全性分析

事务工作流模型可被视为扩展的事务模型和通用工作流模型的交汇点，提出将工作流的模型定义同其事务属性的定义独立开来，尽管在此方法中区分了多重的事务属性。提出了直观的注解符来定义原子性，提供了一个通用规则——放宽的完全性准则，以适应现实运行中事务管理的需要，以一个网上电子书店工作流应用为例来阐明这种思路。     

Selective dynamic serialization for reducing energy consumption in hardware transactional memory systems

In the search for new paradigms to simplify multithreaded programming, Transactional Memory (TM) is currently being advocated as a promising alternative to deadlock-prone lock-based synchronization. In this way, future many-core CMP architectures may need to provide hardware support for TM. On the other hand, power dissipation constitutes a first class consideration in multicore processor designs. In this work, we propose Selective Dynamic Serialization (SDS) as a new technique to improve energy consumption without degrading performance in applications with conflicting transactions by avoiding wasted work due to aborted transactions. Our proposal, which is implemented on top of a hardware transactional memory (HTM) system with an eager conflict management policy, detects and serializes conflicting transactions dynamically (at run-time). In its simplest form, in case of conflict, one transaction is allowed to continue whilst the rest are completely stalled. Once the executing transaction has finished, it wakes up several of the stalling transactions. More elaborated implementations of SDS try to delay this behavior until serialization of transactions is profitable, achieving the best trade-off between performance, energy savings and network traffic. SDS implementations differ from each other in the condition that triggers the serialization mode. We have evaluated several SDS schemes using GEMS, a full-system simulator implementing the LogTM-SE Eager–Eager HTM system, and several benchmarks from the STAMP suite. Results for a 16-core CMP show that SDS obtains reductions of 6 % on average in energy consumption (more than 20 % in high contention scenarios) in a wide range of benchmarks without affecting, on average, execution time. At the same time, network traffic level is also reduced by 22 %.