On earliest deadline first scheduling for temporal consistency maintenance

A real-time object is one whose state may become invalid with the passage of time. A temporal validity interval is associated with the object state, and the real-time object is temporally consistent if its temporal validity interval has not expired. Clearly, the problem of maintaining temporal consistency of data is motivated by the need for a real-time system to track its environment correctly. Hence, sensor transactions must be able to execute periodically and also each instance of a transaction should perform the relevant data update before its deadline. Unfortunately, the period and deadline assignment problem for periodic sensor transactions has not received the attention that it deserves. An exception is the More-Less scheme, which uses the Deadline Monotonic (DM) algorithm for scheduling periodic sensor transactions. However, there is no work addressing this problem from the perspective of dynamic priority scheduling. In this paper, we examine the problem of temporal consistency maintenance using the Earliest Deadline First (EDF) algorithm in three steps: First, the problem is transformed to another problem with a sufficient (but not necessary) condition for feasibly assigning periods and deadlines. An optimal solution for the problem can be found in linear time, and the resulting processor utilization is characterized and compared to a traditional approach. Second, an algorithm to search for the optimal periods and deadlines is proposed. The problem can be solved for sensor transactions that require any arbitrary deadlines. However, the optimal algorithm does not scale well when the problem size increases. Hence, thirdly, we propose a heuristic search-based algorithm that is more efficient than the optimal algorithm and is capable of finding a solution if one exists.

DESH: overhead reduction algorithms for deferrable scheduling

Although the deferrable scheduling algorithm for fixed priority transactions (DS-FP) has been shown to be a very effective approach for minimizing real-time update transaction workload, it suffers from its on-line scheduling overhead. In this work, we propose two extensions of DS-FP to minimize the on-line scheduling overhead. The proposed algorithms produce a hyperperiod from DS-FP so that the schedule generated by repeating the hyperperiod infinitely satisfies the temporal validity constraint of the real-time data. The first algorithm, named DEferrable Scheduling with Hyperperiod by Schedule Construction (DESH-SC), searches the DS-FP schedule for a hyperperiod. The second algorithm, named DEferrable Scheduling with Hyperperiod by Schedule Adjustment (DESH-SA), adjusts the DS-FP schedule in an interval to form a hyperperiod. Our experimental results demonstrate that while both DESH-SC and DESH-SA can reduce the scheduling overhead of DS-FP, DESH-SA outperforms DESH-SC by accommodating significantly more update transactions in the system. Moreover, DESH-SA can also achieve near-optimal update workload.     

Real-time update of access control policies

Access control policies are security policies that govern access to resources. The need for real-time update of such policies while they are in effect and enforcing the changes immediately, arise in many scenarios. Consider, for example, a military environment responding to an international crisis, such as a war. In such situations, countries change strategies necessitating a change of policies. Moreover, the changes to policies must take place in real-time while the policies are in effect. In this paper we address the problem of real-time update of access control policies in the context of a database system. Access control policies, governing access to the data objects, are specified in the form of policy objects. The data objects and policy objects are accessed and modified through transactions. We consider an environment in which different kinds of transactions execute concurrently some of which may be policy update transactions. We propose algorithms for the concurrent and real-time update of security policies. The algorithms differ on the basis of the concurrency provided and the semantic knowledge used.     

基于遍历有向非循环图的实时事务调度算法

移动环境下实时数据库系统负载的不可预测,以及实时事务争夺有限的系统资源经常导致实时事务重启或夭折。传统的实时事务调度算法已不适应,在用有向非循环图表示数据相互间的导出关系的基础上,提出一种基于遍历这种图的实时事务调度算法。结合实时数据对象的时间域和值域有效性,系统适当地丢弃一些低价值的更新事务以减轻系统负载。仿真实验表明：算法一定程度上降低了事务错过截止期比率并提高了数据新鲜度。     

基于可延迟调度提升实时数据对象时序一致性服务质量算法

针对保证实时数据对象时序一致性调度算法在软实时数据库系统环境下的应用问题,提出了一种基于概率统计的可延迟优化(SDS-OPT)算法。首先,分析和比较了现有算法在可调度性、服务质量(QoS)以及工作负载方面的特征与不足,指出优化现有算法的必要性;然后,利用最速下降法提升作业的执行时间筛选基准值,进而增加实时更新事务可调度的作业数量,以确保实时数据对象的时序一致性服务质量(QoS)最大化;最后,从工作负载和服务质量两个方面对所提算法和现有算法的性能进行对比分析。仿真实验结果表明,相对于已有的针对固定优先级可延迟调度算法(DS-FP)和统计性的非确定性可延迟调度算法(DS-PS),所提算法能够保证实时数据对象的时序一致性,同时降低工作负载,服务质量提升明显。     

Maintaining data temporal consistency in distributed real-time systems

Previous works on maintaining temporal consistency of real-time data objects mainly focuses on real-time database systems in which the transmission delays (jitters) of update jobs are simply ignored. However, this assumption does not hold in distributed real-time systems where the jitters of the update jobs can be large and change unpredictably with time. In this paper, we examine the design problems when the More-Less (ML) approach (Xiong and Ramamritham in Proc. of the IEEE real-time systems symposium 1999; IEEE Trans Comput 53:567?C583, 2004), known to be an efficient scheme for maintaining temporal consistency of real-time data objects, is applied in a distributed real-time system environment. We propose two new extensions based on ML, called Jitter-based More-Less (JB-ML) and Statistical Jitter-based More-Less (SJB-ML) to address the jitter problems. JB-ML assumes that in the system the jitter is a constant for each update task, and it provides a deterministic guarantee in temporal consistency of the real-time data objects. SJB-ML further relaxes this restriction and provides a statistical guarantee based on the given QoS requirements of the real-time data objects. We demonstrate through extensive simulation experiments that both JB-ML and SJB-ML are effective approaches and they significantly outperform ML in terms of improving schedulability.     

Concurrency control strategies for ordered data broadcast in mobile computing systems

Although data broadcast has been shown to be an efficient method for disseminating data items in mobile computing systems, the issue on how to ensure consistency and currency of data items provided to mobile transactions (MT), which are generated by mobile clients, has not been examined adequately. While data items are being broadcast, update transactions may install new values for them. If the executions of update transactions and the broadcast of data items are interleaved without any control, mobile transactions may observe inconsistent data values. The problem will be more complex if the mobile clients maintain some cached data items for their mobile transactions. In this paper, we propose a concurrency control method, called ordered update first with order (OUFO), for the mobile computing systems where a mobile transaction consists of a sequence of read operations and each MT is associated with a time constraint on its completion time. Besides ensuring data consistency and maximizing currency of data to mobile transactions, OUFO also aims at reducing data access delay of mobile transactions using client caches. A hybrid re-broadcast/invalidation report (IR) mechanism is designed in OUFO for checking the validity of cached data items so as to improve cache consistency and minimize the overhead of transaction restarts due to data conflicts. This is highly important to the performance of the mobile computing systems where the mobile transactions are associated with a deadline constraint on their completion times. Extensive simulation experiments have been performed to compare the performance of OUFO with two other efficient schemes, the multi-version broadcast method and the periodic IR method. The performance results show that OUFO offers better performance in most aspects, even when network disconnection is common.     

Secure one snapshot protocol for concurrency control in real-time stock trading systems

To prevent any data from being accessed by unauthorized users, it is necessary for stock trading systems (STS) to use multilevel secure database management systems in controlling concurrent executions among multiple transactions. In STS, analytical transactions as well as mission critical transactions are executed concurrently, which makes it difficult to use traditional secure real-time transaction management schemes for STS environment. In this paper, we propose the read-down relationship-based secure one snapshot protocol (SOS) that is devised for the secure real-time transaction management in STS. By maintaining an additional one snapshot as well as working database, SOS blocks covert-channels without causing the priority inversion phenomenon. We introduce the process of SOS protocol with some examples, present the proofs of devised protocol, and then evaluate the performance gains by means of simulation method.     

移动实时嵌套事务的并发控制

在移动计算环境中，事务移动性和无线网络固有的缺陷使得传统分布式实时事务管理机制不足以支持移动实时事务的执行，故有必要为移动实时事务研究新的事务处理机制以提高其成功率．该文着重研究移动实时事务的并发控制机制．首先，该文给出了一个考虑事务定时限制以及移动性的嵌套事务模型．然后，为减少移动分布式环境中解决数据冲突的开销，该文研究了一种结合优先级夭折和优先级继承的基于封锁的并发控制协议PAI-2PL．当高优先级事务被低优先级事务阻塞时，对于相同家族事务，采用优先级继承方法解决冲突；而对于不同家族事务，则夭折重启低优先级事务．另外，为减少由于断接所引起的无效阻塞，PAI-2PL允许低优先级事务夭折处于断接状态的高优先级事务．通过性能测试，表明所提出的事务模型及并发控制机制能提高实时事务的成功率．     

Maintaining temporal consistency: pessimistic vs. optimisticconcurrency control

We study the performance of concurrency control algorithms in maintaining temporal consistency of shared data in hard real time systems. In our model, a hard real time system consists of periodic tasks which are either write only, read only or update transactions. Transactions may share data. Data objects are temporally inconsistent when their ages and dispersions are greater than the absolute and relative thresholds allowed by the application. Real time transactions must read temporally consistent data in order to deliver correct results. Based on this model, we have evaluated the performance of two well known classes of concurrency control algorithms that handle multiversion data: the two phase locking and the optimistic algorithms, as well as the rate monotonic and earliest deadline first scheduling algorithms. The effects of using the priority inheritance and stack based protocols with lock based concurrency control are also studied     

移动环境下支持实时事务处理的数据预取

随着移动通信技术的迅速发展,人们提出了新的应用要求:在移动环境下处理实时事务.而移动通信带宽有限性引起较大的数据访问延迟,有时甚至由于网络传输的断接使得事务得不到所需要的数据,数据预取能够很好地解决这个问题.已有的移动环境下数据预取没有考虑到数据的流行性和事务的时间特性.该文分析影响实时事务数据预取的因素,首先考虑数据易变性、活跃性等因素,获得高价值预取数据集合;然后考虑访问预取数据的事务优先级、数据流行性等因素,构造预取数据的选择函数,通过该函数在前面选取的集合中筛选出对满足实时事务截止期更有价值的数据对象进行预取.实验表明,该数据预取策略能降低移动实时事务满足截止期的比率,更好地支持移动实时事务处理.     

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.     

基于多片FPGA的双优先级动态调度算法

针对单片现场可编程门阵列(FPGA)在处理高速网络中海量数据时存在效率低下的问题,结合多处理器的双优先级调度算法,在所构建的多片FPGA并行处理的高速数据采集和处理模型上,提出一种基于多片FPGA的双优先级动态调度算法,并对处于低优先级段的强实时周期任务提出一种最早截止期临界松弛调度(EDCL)算法。根据任务的松弛度确定任务的优先级,若提升时间到达时仍未完成,则将其提升到高优先级段; 对软实时周期任务,设置在中优先级段,通过延长当前任务截止期至动态模糊阈值进行调度。实验结果表明,该算法能很好地调度强实时周期任务,保证重要任务的优先执行,并能降低由于抢占造成的软实时周期任务错失率。     

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.     

Proximity-based k-partitions clustering with ranking for document categorization and analysis

As one of the most fundamental yet important methods of data clustering, center-based partitioning approach clusters the dataset into k subsets, each of which is represented by a centroid or medoid. In this paper, we propose a new medoid-based k-partitions approach called Clustering Around Weighted Prototypes (CAWP), which works with a similarity matrix. In CAWP, each cluster is characterized by multiple objects with different representative weights. With this new cluster representation scheme, CAWP aims to simultaneously produce clusters of improved quality and a set of ranked representative objects for each cluster. An efficient algorithm is derived to alternatingly update the clusters and the representative weights of objects with respect to each cluster. An annealing-like optimization procedure is incorporated to alleviate the local optimum problem for better clustering results and at the same time to make the algorithm less sensitive to parameter setting. Experimental results on benchmark document datasets show that, CAWP achieves favorable effectiveness and efficiency in clustering, and also provides useful information for cluster-specified analysis.     

On-line schedulability tests for adaptive reservations in fixed priority scheduling

Adaptive reservation is a real-time scheduling technique in which each application is associated a fraction of the computational resource (a reservation) that can be dynamically adapted to the varying requirements of the application by using appropriate feedback control algorithms. An adaptive reservation is typically implemented by using an aperiodic server (e.g. sporadic server) algorithm with fixed period and variable budget. When the feedback law demands an increase of the reservation budget, the system must run a schedulability test to check if there is enough spare bandwidth to accommodate such increase. The schedulability test must be very fast, as it may be performed at each budget update, i.e. potentially at each instance of a task; yet, it must be as efficient as possible, to maximize resource usage. In this paper, we tackle the problem of performing an efficient on-line schedulability test for adaptive resource reservations in fixed priority schedulers. In the literature, a number of algorithms have been proposed for on-line admission control in fixed priority systems. We describe four of these tests, with increasing complexity and performance. In addition, we propose a novel on-line test, called Spare-Pot algorithm, which has been specifically designed for the problem at hand, and which shows a good cost/performance ratio compared to the other tests.     

基于差分图像分块的视频背景提取算法

为了降低背景提取算法的时间复杂度和空间复杂度,提出一种结合差分图像分块、背景减除和帧间差法的背景提取方法。对差分图像进行分块分类,提出了一种统计像素值的子块分类法,对不同类的块用不同的更新策略进行背景实时更新。该算法有效解决了背景更新过程中运动目标逗留、背景物体移入移出等问题的影响。实验结果表明该算法运算速度快、鲁棒性高、能准确地提取实时背景。     

Holistic analysis of asynchronous real-time transactions with earliest deadline scheduling

In distributed real-time systems, an application is often modeled as a set of real-time transactions, where each transaction is a chain of precedence-constrained tasks. Each task is statically allocated to a processor, and tasks allocated on the same processor are handled by a single-processor scheduling algorithm. Precedence constraints among tasks of the same transaction are modeled by properly assigning scheduling parameters as offsets, jitters and intermediate deadlines.In this paper we address the problem of schedulability analysis of distributed real-time transactions under the earliest deadline first scheduling algorithm. We propose a novel methodology that reduces the pessimism introduced by previous methods by explicitly taking into account the offsets of the tasks. Moreover, we extend the analysis to account for blocking time due to shared resources. In particular, we propose two kinds of schedulability tests, CDO-TO and MDO-TO, and show, with an extensive set of simulations, that they provides improved schedulability conditions with respect to classical algorithms. Finally, we apply the methodology to an important class of systems: heterogeneous multiprocessor systems, with a general purpose processor and one or more coprocessors (DSPs).     

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.