主动实时数据库事务的优先级分派

主动实时数据库（ARTDB）的事务处理尚未得到太多的研究．本文论述ARTDB事务处理的一个重要方面，即事务的优先级分派问题．我们给出为主动（触发）事务及立即和推迟子事务（被触发事务）分派优先级的各种策略，并按不同情况对这些策略的性能进行评价．     

读／写优先级上界协议

本文介绍了一种基于两阶段加锁协议的多任务并发控制方法——读/写优先级上界协议。采用此方法可避免系统中因多任务竞争共享资源产生的死锁,又可使高优先级事务被低优先级事务耽搁不超过一个套事务的执行,保证高优先级事务的按时完成。     

RTOS优先级反转问题分析

本文从RTOS的多任务和实时性特点出发，介绍了优先级反转问题，分析了发生优先级反转的基本原因．介绍了防止优先级反转的两种基本方法：优先级极限法和优先级继承法，并对两种方法进行分析和比较，在此基础上，提出了改进方法：优先级交换法。     

关于实时事务调度中的优先级反转

分析了基于优先级的调度策略中优先级反转产生的原因,并且给出了RTDBS中实时平淡事务和实时嵌套事务的并发控制中优先级反转的解决方法。主要有优先级继承,高优先级夭折,优先级顶,避免优先级反转的多版本协议,基于优先级的时标排序及一些求精的算法。     

基于动态优先级的分布式同步机制

本文提出了一种新颖的分布式同步机制,此机制利用动态优先级来协调事务的数据操作,与各种解决此类问题的现有方法比较具有如下优点:事务的无用撤除运算较少且不会产生死锁。     

基于价值密度的替代与事务优先级分派策略

针对基于替代/补偿的实时事务模型中的优先级分派问题,提出基于价值密度的替代与事务优先级分派策略PBAC。在PBAC中,替代优先级基于替代的价值密度,并与替代的执行时间和紧迫性相关,事务优先级继承自替代的优先级,并受事务执行度的影响。仿真实验结果证明,该策略使系统可以更好地对基于替代/补偿的事务模型进行调度。     

基于优先级继承协议解决μC/OS优先级逆转问题

针对μC/OS的特点给出了一种基于优先级继承协议解决优先级逆转问题的方案.μC/OS作为一种应用广泛的嵌入式实时操作系统,是基于优先级的可抢占的调度方案的,不可避免地存在优先级逆转的问题.解释了优先级逆转发生的原因,简单分析了解决该问题的方案,并在分析μC/OS运作原理的基础上,针对μC/OS的特点实现了基于优先级继承协议的互斥向量,为解决μC/OS优先级逆转问题提出了另外一种可行的方案.最后通过2个简单的实验,在S3CA510平台验证了该方案的正确性与可行性.     

优先级反转和死锁的资源管理模式研究与实现

为了抑制优先级反转现象,采用优先级继承协议来解决优先级反转现象,在此协议中不能避免系统死锁现象的发生。分析了死锁现象产生的原因的,在优先级继承协议基础上提出了优先级反转和死锁问题的资源管理模式,采用排序锁定共享资源的方法,使共享资源按照SourceID由低到高的共享顺序依次被访问。理论证明该方法在一定程度上抑制优先级反转且避免了死锁现象的发生,通过实验结果表明了解决优先级反转和死锁的资源管理模式的正确性与可行性。     

一种改进型优先级天花板协议设计与实现

分析了嵌入式操作系统μC/OS-II产生的优先级反转问题及缺陷,提出了一种改进型优先级天花板协议,给出了协议的原理,该协议可以解决优先级反转问题,具有预防系统死锁等特点,并介绍了“修改μC/OS-II内核以实现改进型优先级天花板协议”的思想和方法。     

在μC/OS-Ⅱ中消除优先级反转

使用实时内核,优先级反转是实时系统中出现最多的问题。为了防止这种现象的发生,内核必须能够自动变换任务的优先级．目前比较有效的方法有优先级继承和优先级顶置等。而作为一个优秀而应用广泛的实时内核,μC／OS-Ⅱ没有防优先级反转的机制。基于此,首先分析了优先级反转及解决方法,然后提出如何对μC／OS—Ⅱ的调度算法进行扩展．使其支持优先级顶置协议,从而良好解决了该实时系统中的优先级反转问题．提高了系统的实时性能。     

Priority assignment in real-time active databases

Active databases and real-time databases have been important areas of research in the recent past. It has been recognized that many benefits can be gained by integrating real-time and active database technologies. However, not much work has been done in the area of transaction processing in real-time active databases. This paper deals with an important aspect of transaction processing in real-time active databases, namely the problem of assigning priorities to transactions. In these systems, time-constrained transactions trigger other transactions during their execution. We present three policies for assigning priorities to parent, immediate and deferred transactions executing on a multiprocessor system and then evaluate the policies through simulation. The policies use different amounts of semantic information about transactions to assign the priorities. The simulator has been validated against the results of earlier published studies. We conducted experiments in three settings: a task setting, a main memory database setting and a disk-resident database setting. Our results demonstrate that dynamically changing the priorities of transactions, depending on their behavior (triggering rules), yields a substantial improvement in the number of triggering transactions that meet their deadline in all three settings. Edited by Henry F. Korth and Amith Sheth. Received November 1994 / Accepted March 20, 1995     

基于耦合模式的主动实时并发控制算法

主动实时数据库中触发事务与被触发事务在执行上具有多种耦合模式,传统的并发控制无法对具有复杂耦合模式的事务进行有效调度。通过对不同耦合模式实时要求及事务间冲突关系的分析,提出了新的主动实时并发控制算法(ARTCC-CM),采用时戳区间策略,在验证阶段检测冲突事务触发度及执行时间,动态调整串行化顺序。理论分析与实验证明,在保证可串行性同时减少了不必要的事务重启,提高了系统性能。     

Scheduling Value-Based Nested Transactions in Distributed Real-Time Database Systems

Many noticeable studies have focussed on scheduling flat transactions in a distributed real-time database system (RTDBS). However, a nested transaction model has been widely adopted in many real-life applications such as Internet stock trading systems and telecommunications. This work concerns efficiently scheduling real-time nested transactions in a distributed RTDBS. A new real-time scheduler called flexible high reward for nested transactions (FHRN) is proposed. FHRN consists of (1) FHRN_p ¹ policy to schedule real-time nested transactions and (2) 2PL_HPN to resolve the concurrent data-accessing problem among interleaved nested transactions. Simulation results show that FHRN outperforms these existent real-time schedulers such as random priority (RP), earliest deadline (ED), highest value (HV), hierarchical earliest deadline (HED), and highest reward and urgency (HRU) when an application requires a nested transaction model.     

基于级联深度的主动实时乐观并发控制协议

主动实时数据库因结合了时间限制与主动机制而使系统事务的并发控制变得更为复杂。主动规则的引入使事务触发新的事务且在执行上具有多种耦合方式,传统的实时并发控制策略无法对具有复杂执行模式的事务进行有效调度,而基于主动数据库的并发控制机制也没有考虑事务的实时性问题。通过对事务不同耦合方式的实时要求及事务间冲突关系进行分析,提出了新的主动实时数据库乐观并发控制方法,对不同事务级联深度进行评估,结合事务执行的时间信息对冲突事务进行动态调整串行化顺序。理论分析与实验证明,能在保证事务可串行性的同时降低了不必要事务重启个数,更好地满足系统的实时性。     

基于组合优先级的自适应实时调度算法研究

在嵌入式实时操作系统中,由单个特征参数作为实时任务优先级的调度依据,并不能较好地描述系统中任务的关键性和紧迫性.提出一种基于组合优先级的自适应实时调度算法(SREDF),综合任务的截止期和CPU运行期设计任务的优先级,使截止期越早且CPU运行期越短的任务拥有最高优先级.处理器能有效地调度相同截止期的实时任务,并提前分析和预测任务能否完成.实验表明,该算法降低了任务调度的截止期错失率(MDP),并提高了任务调度的速度和效率.     

一种混合优先级的防危调度算法

为增强实时系统任务过载时的防危性,提出一种混合优先级的防危调度算法,其优先级由相对截止期优先级和相对松弛度优先级组成,通过相对松弛度预测任务的可完成性,并采用完全抢占方式防止处理器资源的竞争抖动。仿真结果表明,该算法可充分利用处理器资源,能在发生瞬时过载时有效降低任务的截止期错失率。     

Optimistic priority-based concurrency control protocol for firm real-time database systems

This paper presents an optimistic priority-based concurrency control protocol that schedules active transactions accessing firm deadline real-time database systems. This protocol combines the forward and backward validation processes in order to control concurrent transactions with different priorities more effectively. For a transaction in the validation phase, it can be committed successfully if the serialization order is adjusted in favour of the transactions with higher priority and aborted otherwise. Thus, this protocol establishes a priority ordering technique whereby a serialization order is selected and transaction execution is forced to obey this order. This priority-based protocol addresses the problem of satisfying data consistency, with the goal being to increase the number of transactions that commit by their deadlines. In addition, for desirable real-time conflict resolution, this protocol intends to meet more deadlines of higher priority transactions then lower priority transactions.     

一种任务优先级的综合设计方法

提出了一种基于优先级表设计的调度算法.将任务的相对截止期和空闲时间这两个特征参数结合起来,综合设计任务的优先级表,使得截止期越早或空闲时间越短,任务的优先级越高,而且任务的优先级由相对截止期和空闲时间惟一确定.对于任意一个任务,可通过对设计的优先级表进行二元多点插值获得相应任务的惟一优先级.与传统的EDF和LSF算法进行仿真比较,仿真结果表明,通过优先级表设计方法来确定任务的优先级,提高了任务调度的成功率,降低了任务截止期的错失率.该方法可应用于实时系统中实时任务的动态调度中.     

Real-time transaction scheduling in database systems

A database system supporting a real-time application, which can be called “a real-time database system (RTDBS)”, has to provide real-time information to the executing transactions. Each RTDB transaction is associated with a timing constraint, usually in the form of a deadline. Efficient resource scheduling algorithms and concurrency control protocols are required to schedule the transactions so as to satisfy both timing constraints and data consistency requirements. In this paper,^† we concentrate on the concurrency control problem in RTDBSs. Our work has two basic goals: real-time performance evaluation of existing concurrency control approaches in RTDBSs, and proposing new concurrency control protocols with improved performance. One of the new protocols is locking-based, and it prevents the priority inversion problem^{, †} by scheduling the data lock requests based on prioritizing data items. The second new protocol extends the basic timestamp-ordering method by involving real-time priorities of transactions in the timestamp assignment procedure. Performance of the protocols is evaluated through simulations by using a detailed model of a single-site RTDBS. The relative performance of the protocols is examined as a function of transaction load, data contention (which is determined by a number of system parameters) and resource contention. The protocols are also tested under various real-time transaction processing environments. The performance of the proposed protocols appears to be good, especially under conditions of high transaction load and high data contention.     

Value-based scheduling in real-time database systems

In a real-time database system, an application may assign avalue to a transaction to reflect the return it expects to receive if the transaction commits before its deadline. Most research on real-time database systems has focused on systems where all transactions are assigned the same value, the performance goal being to minimize the number of missed deadlines. When transactions are assigned different values, the goal of the system shifts to maximizing the sum of the values of those transactions that commit by their deadlines. Minimizing the number of missed deadlines becomes a secondary concern. In this article, we address the problem of establishing a priority ordering among transactions characterized by both values and deadlines that results in maximizing the realized value. Of particular interest is the tradeoff established between these values and deadlines in constructing the priority ordering. Using a detailed simulation model, we evaluate the performance of several priority mappings that make this tradeoff in different, but fixed, ways. In addition, a bucket priority mechanism that allows the relative importannce of values and deadlines to be controlled is introduced and studied. The notion of associating a penalty with transactions whose deadlines are not met is also briefly considered.When this work was done he was with the Computer Sciences Department, University of Wisconsin-Madison.