实时事务调度(数据库)

时间：2022-11-11 22:30:01 | 来源：信息时代

时间：2022-11-11 22:30:01 来源：信息时代

    实时事务调度 : 对于任一给定事务集各事务活动的执行排序。关于RTDB事务有两级调度: 事务级(CPU使用)和操作级(数据使用),后者就是通常的并发控制,这里指的是前者。
1.决定调度策略的基本因素
决定调度策略设计或选择的基本因素有:
(1)脱机与联机: 脱机调度基于事务的预分析,在系统未运行前产生一个事务执行的调度表或调度计划。联机调度则在系统运行时才执行调度算法来实现对事务执行的指派。
(2)静态与动态:静态调度乃指调度策略与算法(包括优先分派)不考虑动态变化情况,故一旦确定,不会根据当时的情况而动态地变更。动态调度在运行时动态地进行事务的“可行性”和“可调度性”分析,然后产生一个事务能否及何时执行的调度决策。注意,脱机调度当然是静态的,但静态调度不一定是脱机的,所以它们属于调度描述的两个不同维。
(3)可调度性分析: 即事务满足其定时限制(特别是截止期)的可能性或概率分析,对当前事务进行“可行性”检验和预测。一般,实时调度应有一定的可调度性分析能力。
(4)冲突避免与冲突解决:系统中存在着事务间潜在的资源使用冲突。调度这种冲突的方法可以分成两类: 一类是事务被放行以前进行潜在冲突的探测与解决,不让有潜在冲突的事务同时运行,故称为避免冲突的调度。另一类是允许有潜在冲突的事务同时执行,动态地进行冲突的探测与解决。当要发生冲突时,采用一定的协议来解决,典型的就是封锁(等待)或剥夺两个冲突事务之一的执行,这种封锁与剥夺都以其优先级的高低为依据。
(5)抢占与不抢占:所谓抢占就是高优先级事务抢占低优先级事务的CPU,而低优先级的事务则被挂起(不被夭折),当该高优先级事务结束时,它恢复执行。不抢占调度,则一个事务一旦开始执行,就直至结束而不让出它已获得且仍然需要的任何资源。抢占调度可避免“优先级颠倒”,但也可能带来负面作用。因为被挂起的事务若不让出它已占有的数据,则数据的占有时间延长,就会形成等待事务的“护航队”(convoy),这种“护航队”一旦形成,可能会持续很长的时间,进而导致事务延长时间的不确定性,不利于其定时限制的满足。
(6)超载与非超载:非超载调度假定系统的事务集始终备有足够的资源,每一可能的事务集都是可调度的。它不能处理“不可调度”(即不能满足定时限制)的事务,而是简单地将其抛弃。超载调度进行超载情况(即存在定时限制不满足的可能性)的探测,当探测到这种情况时,则使用各种策略来解决。
2.优先级分派策略
作为实时事务调度基础的优先级分派策略是一个函数,可用于两类不同对象: 单个事务或一个事务组。当用于单个事务时,函数结果是该事务的优先级; 当用于事务组时,结果是这些事务的一个排序表。
以下为典型的实时事务优先级分派策略:
(1)最早放行优先(earliest release first,ERF):将最高优先级给具有最早“放行”时间的事务。所谓放行时间就是事务可以开始执行的最早时间(不一定是事务的到达时间)。
(2) 最早截止期优先(earliest deadline first,EDF): 即具有最早截止期者优先级最高。其主要缺点是已过或几乎要过截止期者将获得最高优先级,这显然不合适。
(3) 最早可达截止期优先(earliest feasible deadline first,EFDF): 具有最早的“可达”截止期者优先级最高。一个事务T的截止期相对于当前时间是“可达到”的,乃指t+(E-P)≤d。这里t为当前时间,E、P分别为T的执行时间估算和已执行时间,d为其截止期。这样,具有不可达截止期的事务可不必立即夭折,因为它还有机会(当系统没有可达截止期的事务时)获得服务,这对软实时事务很有用。该策略显然是EDF的改进版本。
(4)最短空余时间优先(least slack first,LSF):事务T的空余时间S=d-(t+E-P),即推迟T的执行而仍然满足其截止期的可推迟时间量估算。LSF考虑了当前时间与剩余执行时间估算E—F,若事务在执行,则当前时间t与已执行时间P同步增加而使S不变,因而优先级也不变。但随事务的停止执行,其优先级动态上升。所以,它是一种动态策。
(5)最高价值优先(highest value first,HVF):每一事务有一价值函数,其值最大者最优先。问题是如何合理地构造价值函数,例如: V(T)=k(w₁(t-t_s)-w₂d+w₃P-w₄S),其中,t、d、P、S的意义同上,k、t_s分别为事务T的危急度、开始时间,w_i为加权因子。
(6) 最大价值密度优先(greatest value density first,GVDF): 下列价值密度函数最大者最优先为:

(v为价值函数)
3. 典型的调度方法
(1)静态表驱动调度: 它执行静态可调度性分析,产生一种调度表,在运行时按调度表决定一个事务何时执行。这种方法较适用于周期性事务。
(2)优先级驱动可抢占调度:它强调“最高优先者”。每一事务被指派一优先级,按优先级高低执行;在执行过程中,若有更高优先级的事务到达,则让位给它执行。
(3)动态计划式调度:它对到达的事务进行动态可调度性分析或可行性检验,仅当断定它是可行的,才放行,并产生一个各事务执行的计划或调度。它提供了事务可行性预报,凡放行的事务都保险会满足其时间限制。但问题是,如何使事务的执行时间估算、资源需求、定时限制、截止期或周期、执行次序约束等诸多因素的假定成立,从而使这“保险算法”有效,这很难实现。
(4)动态尽力式调度:基于事务的特征为每一指派一优先级,然后就按其优先级来调度。其可靠度通过优先级动态调整的深入模拟仿真来获得。它不进行可行性检验,尽最大努力去满足多个事务的截止时间,但不保险,事务在执行期间可能被夭折。