基于挖掘具有时态限制数据语义的实时事务调度算法

在实时数据库中,事务对时态数据对象的访问在很多领域的应用日益广泛。目前实时数据库中的事务调度算法大多仅考虑数据的逻辑一致性,而忽略了满足时态的一致性。论文提出了新的实时数据库中具有时态限制的事务调度算法PSBA(PredictionandSimilarity-BasedAlgorithm)。首先提出了临时数据截止期的概念,以定理的形式证明了低成本地预测算法的可行性,尽可能早地终止或推迟无法满足时态一致性要求的事务的执行,节省了计算资源以供其它事务执行。继而通过挖掘数据语义,利用数据相似性,结合预测算法,进一步提高了调度性能。与目前所知的有效算法比较,该算法在性能指标上(事务失败率、浪费的CPU时间)明显优于这些算法。     

实时数据库中具有时态限制的事务调度算法

在实时数据库中，事务对时态数据对象的访问在很多领域的应用日益广泛．目前实时数据库中的事务调度算法大多仅考虑数据的逻辑一致性，而忽略了满足时态的一致性．本文提出了临时数据截止期的概念，以定理的形式证明了低成本的预测算法的可行性，尽可能早地终止或推迟无法满足时态一致性要求的事务的执行，节省了计算资源以供其它事务执行．在此基础上提出了新的实时数据库中具有时态限制的事务调度算法TDDBPA(Temporary Data Deadline—Based Predictive Algorithm)．通过与目前所知的有效算法比较，本算法在性能指标上(事务失败率、浪费的CPU时间)明显优于这些算法．     

实时数据库系统中时态一致性的维护

实时数据库系统(RTDBS)的一个重要问题是维护实时事务和时态数据时态一致性.讨论了实时数据库中事务和数据的时间特性,给出了事务的绝对时态一致性和相对时态一致性的定义;探讨了时态数据给实时事务调度策略带来的影响;提出了一种既保证事务的时态一致性,又减少更新事务执行数量的方法.     

基于数据时态特性的实时事务并发控制

通过对数据时态特性及其对事务调度的影响进行分析,提出了基于数据时态特性的实时事务并发控制算法.该算法根据数据截止期及事务的执行时间估算,改进了事务的验证规则,对事务的提交顺序进行调整,提高了系统的实时性能.理论分析与实验结果表明:该算法降低了事务重启个数及超截止期百分率,性能要优于已有的实时并发控制算法.     

一种动态调整串行化顺序的实时并发控制协议

实时并发控制协议用来控制并发事务间的相互作用,已满足实时数据库的一致性.本文提出一种四阶段实时并发控制协议HTRCC-DASO,协议在读或等待阶段基于事务优先级动态调整串行化顺序,通过阻塞或及早重启低优先级事务,使高优先级事务率先提交并降低事务重启开销.在验证阶段检查事务读写集合的外部一致性和相互一致性并调整活动事务的时间戳间隔,确保满足事务时态一致性和调度冲突可串行化.通过引入相似性概念,提出了HTRCC-DASO的改进版本:SHTRCC-DASO,性能测试结果显示,SHTRCC-DASO协议能保证良好的实时性能.     

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

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

非对称多核处理器上的操作系统集成调度

相对于对称多核处理器,非对称多核处理器具有更高的效能,将成为未来并行操作系统中的主流体系结构.对于非对称多核处理器上操作系统的并行任务调度问题,现有的研究假设所有核心频率恒定,缺乏理论分析,也没有考虑算法的效能和通用性.针对该问题,该文首先建立非线性规划模型,分析得出全面考虑并行任务同步特性、核心非对称性以及核心负载的调度原则.然后,基于调度原则提出一个集成调度算法,该算法通过集成线程调度和动态电压频率调整来提高效能,并通过参数调整机制实现了算法的通用性.提出的算法是第一个在非对称多核处理器上结合线程调度和动态电压频率调整的调度算法.实际平台上的实验表明:该算法可适用于多种环境,且效能比其他同类算法高24%～50%.     

无线传感器网络动态电压调度算法

针对无线传感器网络的节点在运行状态提出了动态电压调度(DVS)算法。DVS是通过改变处理器的工作电压和工作频率来减少处理器的消耗能量。该方法首先必须对节点各部分发出的信号进行分析和预测,并根据预测后的信号对处理器设定处理速率,最后,设定合适的工作电压和工作频率。     

一种面向非对称多核处理器的虚拟机集成调度算法

在计算机体系结构领域,非对称多核处理器将成为未来的主流.对于非对称多核处理器上的虚拟处理器调度问题,现有研究缺乏理论分析,且没有考虑虚拟处理器的同步特性.针对该问题,文中首先建立非线性规划模型,分析得出全面考虑虚拟处理器同步特性、核心非对称性以及核心负载的调度原则.然后,基于调度原则提出一个集成调度算法,该算法定义了效用因子、比例系数、比例资源的概念,结合虚拟处理器的同步特性和核心的非对称性对资源和负载进行全面度量;同时通过运行队列分解降低调度开销.提出的算法是第一个在非对称多核处理器上利用虚拟处理器同步特性的调度算法.实际平台上的实验表明:该算法实现了公平调度,并且性能比其他同类算法提高19%~48%.     

一种任务类型敏感的J2EE事务调度算法

J2EE(Java 2 platform enterprise edition)是构建分布式企业应用的基础中间件平台,当前的J2EE事务对资源的访问调度仍然是简单的先来先服务策略,导致服务器负载很重时,次要任务和关键任务争夺有限的资源,降低了关键任务的性能与成功率.为此,有必要识别任务类型,在资源不足时优先保证关键任务事务的执行.但提交给J2EE的事务基于交互方式执行,且缺乏必要的调度信息,因而不能简单地沿用已有的优先级驱动调度算法.提出一种新的事务调度算法TMPBP(threaded multi-queue priority-based protocol),该算法能够安全、有效地提高系统重负载情况下关键事务的服务质量,防止饥饿和优先级倒置.TMPBP包含了一种新的启发式优先级分派算法HRS(heuristic resource statistics),可以在调度信息缺乏的J2EE环境下动态识别关键事务.结果表明,通过合理地选择参数,TMPBP算法能够显著地提高关键事务的服务质量.     

Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors

The scheduling of systems of periodic tasks upon multiprocessor platforms is considered. Utilization-based conditions are derived for determining whether a periodic task system meets all deadlines when scheduled using the earliest deadline first scheduling algorithm (EDF) upon a given multiprocessor platform. A new priority-driven algorithm is proposed for scheduling periodic task systems upon multiprocessor platforms: this algorithm is shown to successfully schedule some task systems for which EDF may fail to meet all deadlines.     

Optimizing layer‐based scheduling algorithms for parallel tasks with dependencies

Programming with parallel tasks leads to task graphs with dependencies representing a parallel program. Scheduling algorithms are employed to find an efficient execution order of the parallel tasks. A large variety of scheduling algorithms exist, including layer‐based scheduling algorithms for homogeneous target platforms that build consecutive layers of independent parallel tasks and schedule each layer separately. Although these scheduling algorithms provide good results in terms of scheduling algorithm runtime and schedule execution time, the resulting schedules leave room for optimization. This article proposes an optimization for arbitrary layer‐based scheduling algorithms, which is called Move‐blocks algorithm. Given a layer‐based schedule of the parallel tasks, this algorithm moves blocks of parallel tasks into preceding layers in order to reduce the overall execution time of a task‐based application. Suitable blocks of parallel tasks are identified by the algorithm Find‐blocks, which is employed together with the Move‐blocks algorithm. The algorithm Move‐blocks is applied to four well‐known scheduling algorithms. A detailed evaluation for a wide range of test cases is given. Copyright © 2010 John Wiley & Sons, Ltd.     

基于实数编码免疫算法的分布式任务调度

任务调度问题是一个NP难题,其算法是一个重要研究方向。该文通过对任务调度模型及已有免疫算法进行研究和比较,提出一种基于实数编码免疫算法的任务调度算法。讨论问题的编码方式、种群的生成及更新、记忆细胞的更新及部分参数的取值,探讨亲和度函数和浓度函数。采用VC++实现该算法,并通过实例分析对比,证明了其有效性和可行性。     

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.     

云环境下异构无线传感器网络节点调度改进算法

针对大规模传感器网络节点异构性突出、调度困难,传统节点调度算法在大规模传感器网络环境下效率低等问题,提出了基于云计算的节点调度模型,并设计了该模型下的节点调度改进算法。通过将节点算法的执行迁移至云端,由云端调度节点。通过OMnet＋＋对改进算法与云端融合数据处理进行仿真实验表明：改进算法可以有效地延长网络生存周期,并且随着数据量的增加,云端处理融合数据耗时相对平稳。相比较传统节点调度算法,改进算法在能量与耗时指标上表现更优。     

蚁群算法求解非等同并行机调度问题的研究

针对非等同并行机服务调度问题,以机场除冰调度服务为背景并以最小化旅客延误数为目标,提出了一种改进的蚁群算法。该算法根据调度模型的特点,充分考虑模型的约束条件并运用了一种改进的信息素更新策略求解并行机调度问题。仿真结果表明,改进的蚁群算法收敛速度快且结果较优,明显优于FIFO算法,适合求解非等同并行机调度问题。     

并行卡尔曼滤波器的多信道序列规划算法

针对基于卡尔曼滤波器的并行序列规划问题,本文提出了一种基于多信道的改进算法,在规划各进程所对应传感器的测量信息传输序列,以使相应滤波器的状态估计误差协方差满足给定指标的同时,尽可能减少通讯信道占用.文中论证了基于夹挤方法的周期算法,以提高计算进程传输周期的效率;改进了基于缓存的离线序列规划算法,以适应多信道传输的情景;设计了在线序列调整算法,利用空闲信道进行传输失败后的数据复发,快速调整序列以适应指标变化的需求.算法的运行效果将通过仿真实验进行验证与分析.     

入侵轨迹建模与WSN栅栏覆盖分段调度算法研究

无线传感器网络栅栏覆盖在入侵检测方面发挥着重要作用,如何调度栅栏并延长网络的生存时间已成为重点研究问题.在无线传感器网络中设计合理的调度算法,分时激活传感器节点从而延长网络生存时间是大多数研究的方向,然而仅仅通过分时调度传感器节点已很难大幅度提高网络的生存时间.因此设计了一种分时与分段相结合的无线传感器网络栅栏调度算法,该算法通过分析入侵目标穿越传感器网络部署区域的行为特征,建立入侵目标的轨迹模型,该模型在保证栅栏对入侵目标具有较高检测率的情况下预测入侵目标可能穿越栅栏的区域并分段激活栅栏从而大大减少了传感器节点的能量消耗.最后仿真实验验证了本文算法与传统的分时调度算法相比能大幅度提高网络的生存时间.     

WSNs中数据融合树的时隙分配算法

周期工作DC(Duty-Cycling)技术,即周期地开/关通信和感测能力,能够有效降低传感节点的活动时间,进而延长无线传感网络寿命.然而,此技术给数据融合提出了挑战.为此,提出免碰撞的数据融合树的时隙分配算法CF-DGSS(Collision-Free Data Aggregation Slots Scheduling Algorithm for Duty-Cycled Wireless Sensor Networks),进而解决基于DC的WSNs的数据融合时隙分配问题.为了解决碰撞问题,CF-DGSS算法给每个节点构建冲突集.每个节点在融合时隙分配过程中,保存自己的冲突集.在分配时隙时,传感节点应当确保与冲突集内节点的数据融合不干扰.仿真结果表明,与其他的分配算法相比,提出的CF-DGSS算法具有低的融合时延.     

Distributed scheduling with probabilistic and fuzzy classifications of processes

The classification of various types of processes is an important factor in large-scale distributed systems such as, grid and cloud platforms. Moreover, the coordination and control of distributed processes are research challenges in presence of unpredictable network partitioning and distributed semaphores. The process classification is important in order to allocate and schedule distributed processes enhancing overall resource utilization and throughput. The schedulers employ patterns of resource affinities of concurrent processes in order to make scheduling decisions affecting overall resource utilization in a system, where resource affinity patterns of a process may not be static. This paper proposes an estimation model and a classifier algorithm to queuing processes based on respective resource affinities. The kernel-level software architecture is designed to control scheduling of distributed processes based on classification for enhanced throughput. The classifier algorithm tracks the resource affinities of processes based on execution traces and the control algorithm performs process scheduling. Experimental results indicate that the classifier algorithm successfully manages process queues based on resource affinities of processes and, the control algorithm successfully monitors scheduler activation for a set of processes.