嵌入式实时数据库系统的事务模型及其处理技术

4　事务预分析

如前所述，实时应用包含了丰富的数据、事务语义及复杂结构，具有许多与传统应用不同的特征。主动实时事务的处理必须考虑到：

①数据和资源的冲突：它使各事务的执行时间长度难以事先估算。

②事务间的相互依赖性：嵌套或合作事务间的结构依赖关系、不同事务对同一数据的排他控制要求以及事务之间在定时限制方面的相互依赖性使事务的处理变得极为复杂。

③新活动（事务）的动态“产生”：主动事务在执行过程中动态地（甚至递归地）触发新的活动（事务），再加上②中的各种依赖性，使活动（事务）的执行无法事先确定。

④事务的夭折：事务夭折引起的回滚和重启造成系统资源的巨大浪费，影响系统性能，甚至危及事务的定时性，而且有的实时主动事务是不可回滚和重启的。

由于这些因素，事务的实际执行时间和估算的最坏情况下执行时间的误差很大，故系统必须要有一定的预测和处理能力，能进行“可调度性”分析与预测，事先知道一个事务满足其定时限制特别是截止时间的可能性，是否有“危险”性而要采取专门措施，以便保证它正常完成。

事务的预分析应包含以下内容：

①在事务到达系统（或在系统生成）时对其进行预分析，提取关于事务的替代集、数据集、操作逻辑（类型与顺序）、定时性要求、紧迫性与关键性、运行时间估算、可能触发的活动/事务等的信息，以及各事务间在结构、行为、数据和定时等方面的相关性信息。

②在系统运行的适当时机，采用一定算法对当前活跃事务进行相关性分析，以支持和辅助调度算法与并发控制策略的实施。

③在执行调度与并发控制前，动态地进行“可调度性”预测，确定它们能正常完成的可能性或程度，以便采取相应的措施来尽可能保证其实现。

④必要时采取相应措施，如动态调整优先级与调度算法、执行“功能替代”或“补偿”活动等。

总之，为了提高实时事务的成功率和系统运行效率，应对实时事务进行预分析处理，显式地获得替代集；并对各替代进行分析，提取有关结构、行为、时限、资源等方面的信息，进而分析替代成功执行的可能性，使系统能直接选取一个（或多个）成功率较高的替代参与系统总体调度，投入运行。预分析可以静态进行，不影响系统性能。预分析算法的基本步骤为：

Pre－analyse（T）

输入：实时事务T

输出：T的替代集

步骤：

①生成任务树TK－Tree，并提取有关结构、行为、资源请求、时限的知识。

②分解TK－Tree，产生调度树。/＊得到替代FXi＊/

③进行各调度树的可调度性分析。

④生成弱调度树和强调度树。

4.1　截止期的确定

截止期是实时事务的一个重要特性，原因在于：一是截止期直接表示了事务的时间约束；二是截止期是实时调度的重要参数。鉴于此，确定事务的截止期是事务预分析的首要工作。

从确定方式来说，截止期有以下几种：

（1）赋值截止期

如果实时事务的截止期由用户或应用程序直接赋值，则该截止期为赋值截止期。该截止期是一个绝对时间，不可被系统中的任何部件更改。

换言之，对于事务Ti，其截止期Di＝t，如果t是一个绝对时刻，且来自于外部输入，则Di是事务Ti的赋值截止期。

（2）演绎截止期

实时事务Tj的截止期Dj不是赋值截止期，对于一个实时事务集Trset（Tj∈/Trset），其成员事务对应的截止期集合为D＝｛D1，D2，…，Di，…｝，如果存在一个函数f：Dj＝f（∑Di），则称Dj为事务Tj的演绎截止期。

演绎截止期的存在是源于实时系统中事务之间存在时间相关性，这些时间相关表明事务执行的顺序或紧迫度。刘云生教授总结了事务之间的时间相关性，用BEGINi，COMMITi和ABORTi分别表示事务Ti的开始、提交和夭折事件的发生时刻，两个事务Ti和Tj的时间相关性用以下模型描述：

EXP（TEi，TEj，RO，LO）

TEx≤｛BEGINx，COMMITx，ABORTx｝（X＝i，j）

RO≤｛＝，≤，≥，＜，＞｝

LO≤｛∧，∨，↑｝

其中，Exp（）为“时间关系”表达式，TEi、TEj为其运算对象，≤为“包含于”，LO为一般逻辑运算符，＝，≤，≥，＜，＞为“时间关系”运算符，分别表示“at”、“not－after”、“not－before”、“before”和“after”。

事务间按相对关系有7种最基本的时序相关，这些时序相关可按上述模型表示为：

（A）Tiafter Tj：BEGINi＞ej，ej∈｛COMMITj，ABORTj｝

（B）Timeets Tj：BEGINj＝ei

（C）Tioverlaps Tj：（BEGINi＞BEGINj）∧（BEGINi＜ej）∧（ei＞ei），ei∈｛COMMITi，ABORTi｝

（D）Tiequals Tj：（BEGINi＝BEGINj）∧（ej＝ei）

（E）Tistarts Tj：BEGINj＝BEGINi

（F）Tifinishes Tj：ei＝ej

（G）Tidueing Tj：（BEGINi＞BEGINj）∧（ei＜ej）

上述表达式只是表明了两个事务间的顺序关系，我们还可以说明事务间的精确时间关系。

例4．1：事务Ti必须在事务Tj开始后10秒提交，则它们的时间关系为：

（BEGINj＜COMMITi）∧（COMMITi＜BEGINj＋10s）

在周期性事务中，假设该周期性事务的实例序列为：…，Ti－1，Ti，Ti＋1，…，则一个事务实例Ti的截止期往往就是后续事务实例的起点。

（3）隐式截止期

如前所述，嵌入式实时数据库系统中的数据具有时间约束，处理这些数据对象的事务只有在数据对象的有效期内完成，其结果才可能正确。系统必须将数据的时间约束转嫁到事务上，这又分两种情况：

①事务Ti本身是非实时事务，没有截止期，其时间约束完全来自于所处理的数据对象，则系统将数据对象的时态一致性转化为事务的时间约束，最简单的方法就是将数据对象的有效期结束点作为事务的截止期。

②事务Ti本身是实时事务，有显示截止期或演绎截止期Di，同时，它所处理的数据对象也有时间约束，则为了保证事务的正确性，必须同时考虑事务和数据对象的时间约束。在这种情况下，最简单的方法就是取事务的原始截止期（赋值截止期或演绎截止期）和数据对象截止期的最小值作为该事务的最终截止期。

Di＝min（Di，te）

其中，Di是事务最终的实际截止期。

总体上，有两种可能的方法维护实时数据对象的时态一致性：静态的和动态的。在静态方法中，时态一致性需求被转换为事务的时间约束。系统只需要在时间上提供保证，因为只要相关事务满足了截止期则数据的时态一致性自动满足。在动态方法中，系统在运行过程中一直检测时态一致性并试图满足它们，通过运用多版本数据对象或延迟一些事务以利于更紧急的事务。Young－Kuk Kim和Sang H．Son于1996年对此问题进行了研究，他们提出了一套强制满足数据对象时态一致性的方法。

4.2　替代的生成

实时事务T及其同构的替代都具有层次结构，可以用树表示，前者称为任务树，后者称为调度树。图3．3和图3．4表示实时事务T由任务树分解为调度树。

定义4．1：设有实时事务T＝＜TS，R，＜t，C＞，称树TK－tree＝（D，Q）为T的任务树，它满足条件：

D＝｛TKi＜Cφi，Rγi）｜TKi∈TS，Cφi为TKi的时限约束，Rγi为TKi的资源需求约束，1≤i≤Dg（T）｝

Q＝｛TKi→TKj｜Ei≠j（TKi＜tTKj），1≤i，j≤Dg（T）｝

可见，任务树是有向树，其顶点为事务的任务，有向边表示任务间的时序。

定义4．2：对于实时事务Ti，其替代FXij的调度树S－treei＝（D′i，Q′i）为满足下列条件的树：

D′＝｛stk（FCij，Frij）｜stk∈FXij，FCij为stk的时限约束，，Frij为stk的资源需求信息，1≤k≤Dg（T）｝｝

Q′＝｛stk→sth｜stk＜itsth，1≤k．h≤Dg（T）｝

调度树是有向树，其顶点为事务的子事务，携带表示时间的信息（如执行时间，截止期等）、资源请求、对数据库的操作类型，以及访问对象等信息，有向边表示子事务间的时序，一个调度树对应于实时事务的一个替代。

实时事务的任务树与调度树是同构的，由任务树得到其调度树的过程就是将实时事务分解为对应的替代的过程。

典型的分解算法如下：设有实时事务的任务树TA－tree，分解算法就是在搜索TA－tree的过程中生成调度树，并不断复制已有的替代集，生成新的同构的调度树，直到完成。算法首先产生一个标识为Zs的树，Zs与TA－tree的结构类似，但在每个结点上多了一个字段fz，其含义是如果该结点上的任务包含的功能等价的子事务数为n，则fz＝n－1。此外，还用到一个队列H，其中放置中间结果（树）的根结点，这些调度树中一定存在fz≥1的结点。队列HH放置生成的最终结果。该算法的形式说明为：

prod－tree（TA－tree）

输入：TA－tree——实时事务任务树

输出：S（T）＝｛S－treei｜1≤i≤q｝——实时事务的调度树的集合

步骤：

S（T）：＝?；S1（T）：＝?；

以深度优先策略访问TA－tree，并生成ZS；S1（T）：＝S1（T）∪ZS；

WHILE S1（T）≠?DO

｛Get the next tree S－treeifrom S1（T）；S1（T）：＝S1（T）－S－treei；

getnode（first）；/＊找到S－treei的第一个满足条件fz≥1的结点nodej＊/

WHILE nodej．fz≥1DO

｛S－treei；＝create（tree）；/＊复制S－tree1，但在对应nodej处用stm＋1代替stm＊/nodej．fz＝fz－1；｝

IFEnodei∈S－tree1（nodei．fz≥1）THEN S1（T）：＝S1（T）∪S－ tree1

ELSE S（T）：＝S（T）∪S－tree1｝

END．

例如：对于图3．3描述的实时事务，经过逐步分解得到4个替代调度树（见图4．1）。

图4.1　实时事务分解示意图

4.3　事务执行时间预分析

在嵌入式实时数据库系统中，精确的事务调度策略涉及事务的截止期和执行时间。与截止期一样，程序的执行时间成为事务预分析要解决的又一重要难题。一直以来，虽然专家们尽力寻找精确计算程序执行时间的方法，但是，程序的真实执行时间涉及到太多的可变因素，如硬件平台的性能、系统的负载、程序的真实执行路径、程序的输入参数等，使得这一问题非常棘手。据我们所知，现有的分析方法集中于分析程序执行时间的一个上界，即：说明程序的执行在x秒内完成，调度的精确性依赖于此区间的紧密性。但即使如此，WCET （Worst Case Execution Time）依然是一个静态的估算值，其分析方法将所分析的程序孤立起来，没有考虑系统负载的影响。事实上，嵌入式实时数据库系统乃至所有的实时系统中都不可能只处理一个程序，而是有多个程序并行，这些程序竞争包括CPU和数据对象在内的资源，有些程序由于竞争而等待，其真实的执行结果与WCET可能有很大出入。

这里提出一种新的程序执行时间估算方法，将执行时间估算分为两步：

①静态地WCET估算；

②利用灰色系统理论，得到动态的执行时间估算。

针对于本书前面提出的支持替代的实时事务模型，首先估算事务替代的执行时间，再估算事务的执行时间。

4.3.1　静态最坏执行时间估算

最坏执行时间WCET是事务在系统中的最高执行时间，由于它关系到实时调度的正确实施，成为嵌入式实时数据库系统中一个重要且基本的研究课题，在最近十年成为焦点。它与事务在系统中消耗的CPU时间有关，是可调度性工具的输入。

在WCET研究中，主要涉及以下几个问题：

（1）WCET分析的范围

明确代码的最大消耗时间是分析嵌入式实时数据库系统中程序WCET和确认事务时态正确性的先决条件，一段代码的执行时间定义为执行该代码所花费的CPU时间，则WCET计算给定应用代码的执行时间上限。值得注意的是：

①WCET分析计算上限。即它不能保证代码真实的执行时间正好是WCET，并且该定义不保证WCET分析的质量，WCET也许是一个比真实执行时间大很多的值。

②代码的WCET是依赖于应用的。即一个独立的代码段可能有不同的WCET，所以WCET在不同的应用中有不同的界限。

③WCET估算处理器在理想环境下分析代码段的执行时间，即假设无抢占、等待阻塞，以及其他干扰，WCET不包含等待时间。

④WCET分析是依赖于硬件的。现代微处理器体系结构中充分利用了CACHE和管道提高程序的处理速度，同一代码段在不同的硬件平台上的执行时间是不同的。

（2）WCET分析的目标

为了使嵌入式实时数据库系统可预测并保证尽可能低的系统响应代价，WCET必须满足以下要求：

①安全界限的储备。WCET常常用于确认实时系统的正确性，所估算的执行时间必须是安全可靠的，即所估算的WCET必须不低于最坏情形下的程序执行时间。

②所估算的WCET必须保证紧密性。任务的WCET决定了CPU时间的分配，WCET分析的结果越悲观，为任务保留的CPU时间越多，资源浪费的机会越大。例如，假设某程序真实的最坏执行时间是x秒，而估算的WCET 为y秒：y＞＞x，而系统的调度器根据y为该程序预留CPU时间，则此调度的结果浪费了CPU资源。高质量的WCET分析应避免悲观的结果以及为补偿该悲观结果而引起的代价。

（3）WCET分析中存在的问题

无论在程序代码的源代码级和机器语言级，特定应用程序的WCET由以下因素决定：

①应用中程序活动的可能序列。

②在每个序列中每个活动需要的时间。

现在，很多WCET估算方法要求程序提供可能的执行路径，该路径表现在高级界面，但是，WCET的真正执行发生在机器语言级，在机器语言级，程序的执行时间可以被精确地建模，两者之间似乎存在鸿沟，为了填平两个级别之间的鸿沟，专家们注意到要将源代码级的路径转换为机器语言级的路径。

（4）WCET研究的内容

综上所述，WCET估算从大的方面要做三项工作：

①分析程序的执行路径。程序的控制语句决定了可能的执行路径，很多专家研究程序描述方法和程序的构造，他们提出的策略和方法描述程序的执行频率、程序各部分的执行序列和它们的依赖关系，更多的近期研究工作用语义分析方法来分析程序的路径。

②源语言和机器语言的转换。将高级源语言的路径信息转换为机器语言的路径信息决不是微不足道的。编译器（特别是优化编译器）重新排列代码并完成转换以取得有效的代码达到优化的目的，比如，使代码段具有较高的执行速度和较低的存储消耗等，通过转换，这些代码在结构上可能有所改变，这使重新确定在源代码中已确定的路径成为很困难的事。

一种方法是让编译器转换路径信息与代码翻译并行。在某些情况下，由于代价太高以及其他原因，调试和编写一个编译器是不可接受的和不可能的，因此，寻找独立于编译器的或仅需要有限的编译器协助的方法来完成这个工作；另一种完全不同的方法是从机器或汇编代码中自动驱动路径信息。

③硬件级执行时间分析。WCET分析在每个可能的程序路径上每个程序段活动的执行时间，由于关于程序活动的执行只有在机器代码级是精确的，在这个级别上更容易计算程序的执行时间，因此，精确计算WCET需要在硬件级实施。

硬件级执行时间分析的目的是导出在给定硬件上一个指令的每个实例需要的时间，以及从单个指令执行时间来计算给定代码段的WCET。该分析必须估算指令的可能执行序列，以及在每个可能的序列中每个指令的执行时间，其复杂性依赖于目标硬件的特性。在很多现代体系结构中，一个指令的执行时间不仅依赖于所完成的操作和操作码，而且依赖于指令执行时的硬件状态（cache的容量、管道等）。

（1）用图的方法计算程序的最大执行时间

不考虑硬件问题，假设每个程序代码片的执行时间是不变的，PETER P．PUSCHNER和ANTON V．SCHEDL于1997年提出一种新颖的分析程序执行时间的方法，最大执行时间的计算映射为一个图论问题——在有向图中生成一个最大代价环路。程序用类似于流程图的时间图（T图）表示，这些图反映了代码的结构和时间行为，相关的容量约束限制边上的流，表达了用户提供的关于不可行路径的信息。为了计算最大执行时间，在T图中搜索那些相应的最大代价环路的执行路径，此搜索被转换成线性程序问题，线性程序问题的结果生成MAXT。

此方法的优点如下：

①用简明的符号描述程序的静态结构和可能的执行路径。

②用符号描述可行的程序路径，程序代码上有附加的信息，可以计算最大执行时间，而不是仅仅界定区域。

③线性程序不仅解决最大执行时间，而且生成关于执行时间和最坏情况下每个单个程序的执行数量的细节信息。

该图论方法有以下假设：

①MAXT计算的代码片有一个始点和一个终点，终点不同于开始点。该假设并不限制一般性，任意多始点和终点的代码片可以转化而成一个始点和一个终点的代码片，最简单的方法是，在开始处插入附加的分支，加入新的点，从代码的原始片的所有终点跳过该终点。

②每个执行可以被表示成不同代码部分（如指令、语句、块）的序列。这些代码部分的执行时间是已知的，即使代码部分的执行时间不精确而只是有上界，此方法也能适用。当然，MAXT是一个悲观的上界。(www.xing528.com)

③代码的静态结构是已知的。

④每个代码部分的最大重复次数是已知的。

⑤程序或程序部分的动态特性（即给定应用的执行路径）依赖于输入数据和调用时刻的程序状态，并假设这些动态信息是可变的、完整的。即所有关于可行/不可行路径行为的信息对于MAXT分析都是可变的。

显然，后一种假设并不总是成立，该问题超出了本书讨论范围。

T图的边代表代码的组成，边由这些代码的执行时间赋予权值。结点代表这样的代码点：程序可能分裂或连接的点的控制流。

依赖于代码描述语言或编程语言，边可以表示机器语言、高级语言序列等。图4．2说明了典型高级语言结构可以被转换成T图。

T图的性质如下：G有一个顶点，s没有入边（始点）；G有一个顶点，t没有出边（终点）；对每个边e，存在至少一个边序列，这些序列包含s、t和边e0；每个边有非负权值（执行时间）。

（2）通过分离CACHE分析和路径分析确定WCET

CACHE用于提高高速微处理器的访问时间并相应地减慢主存速度，通过快速访问存储器当前相关区域的信息，它可以降低处理器等待数据的周期数。

图4.2　T图

具有硬实时约束的程序必须做可调度分析，以确认其时间约束是否能被满足。该时间确认的成功度依赖于精确的WCET估算。例如，对于有CACHE的硬件，典型的最坏情形假设是所有的访问都错过了CACHE，这是一种极端悲观的假设，将导致硬件资源的浪费。所以，在分析WCET时一定要考虑CACHE，较早的研究成果用抽象解释器（AI）实现CACHE分析。

现代高性能实时系统不仅使用了CACHE，而且使用了管道处理器，基于与CACHE同样的原因，为了得到精确的WCET，我们也必须考虑管道的行为。

CACHE和管道的分析结果必须综合到程序的最坏路径分析中去，多数方法要么忽视现代硬件，要么非常复杂以至不能用于大型程序。HENRIK THEILING在2000年提出了一种预测WCET的方法，该方法充分考虑现代硬件平台的特性，重视CACHE和管道对程序执行时间的影响，但是将CACHE分析和路径分析分离。该方法通过AI生成一个整数线性问题（ILP）来寻找最坏程序路径，它考虑了CACHE和管道的作用。

程序分析是一种广泛用于确定给定程序运行时间的机制，程序分析员将程序作为AI的输入并力图得到感兴趣的信息，AI给出正确性标准和程序分析的结束条件，一个程序分析被当做程序设计语言的标准语义的抽象。

用抽象值代替固定值的一个原因是可计算性：保证在有限的时间内得到分析结果；另一个原因是获得可能的输入集合上的计算结果。

程序的行为（包括CACHE和管道）由程序的语义给定。一种语言的标准（可操作的）语义由一个数据域和一组函数表述，这些函数描述语言的语句如何转换数据。为了预测程序的实时行为，近似估算它的“收集语义”，收集语义给出特定程序点的所有程序状态，这些信息与路径分析结合在一起得到了WCET区域。该方法的步骤如下：

第一步：定义程序的确定语义。简述程序中感兴趣的方面而忽视执行的细节。即在分析CACHE时，固定的CACHE语义仅仅确定程序中一个给定路径的CACHE状态，但是忽视寄存器的值，这样，每一个真实的状态由一个固定值来表示。

第二步：定义一个抽象语义。它收集了所定义的每个程序点的所有可能的固定值。抽象语义由一个抽象域和一个抽象语义函数（转换函数）集组成，程序语句在抽象域上进行计算。它们说明了语句怎样转换抽象数据，必须单调以保证结束，抽象域的一个成员表示该固定域的成员的集合，在固定语句集上的子集关系决定该抽象域的编序，该编序更精确，更有价值。

为了结合抽象值，需要进行JOIN操作，该操作用于联合源于不同资源的信息，即从不同的控制流到一个程序点。

4.3.2　动态执行时间估算

在嵌入式实时数据库系统中，调度器必须考虑所有实时事务的时限，特别是在系统过载时，如何保证满足尽可能多的实时事务的截止期是调度的主要目的。事务的执行时间是实时调度的重要参数之一。由于系统环境因素的复杂性，某些因素难于定量分析。如前所述，人们在分析事务执行时间时只能撇开系统动态环境而孤立地进行研究静态分析程序的执行路径，确定事务的最坏执行时间。这种分析方法效果不佳，因为事务的执行路径往往需要在动态执行时才能确定。对同样的执行路径而言，在不同的系统运行环境中其执行时间也是不同的，其执行时间的分析更加复杂。

为了提高调度的精确度，应尽可能准确地估算事务的真实执行时间，即程序在真实的动态环境下的“动态执行时间”，而不是静态的最坏执行时间。同时，基于替代的实时事务具有更加复杂的执行路径，每条路径的执行时间差异可能很大，精确地估算执行时间显得尤其重要。

我们还没有发现满足以上要求的动态执行时间研究成果的报告，所幸的是灰色系统理论正好解决了这个问题，在部分信息不明的情况下，通过分析灰色信息找出规律，从而预测事务的执行时间。

本章首先研究替代对事务执行时间的影响，用同样的方法，可以研究具有特定WCET的程序在不同动态环境下的表现。

下面就利用灰色系统理论结合实时事务的特性，建立时间估算模型，研究在动态环境下具有功能替代特性的实时事务的实际执行时间。

事务在系统中的处理过程如图4．3所示，嵌入式实时数据库系统首先根据事务的紧迫程度、截止期和执行时间进行优先级分派，然后按优先级从高到低的顺序进行并发控制，使通过并发控制的事务进入就绪队列，否则进入等待队列，就绪队列中的事务由操作系统具体执行。实时调度必须以事务的动态执行时间为依据。

事务的生命周期如图4．4所示。

定义4．3：事务动态执行时间，指该事务从被系统调度而开始使用CPU到提交所耗费的时间。

之所以要强调事务的动态执行时间，是为了区别于事务的静态执行时间WCET，事务的静态执行时间只与程序有关，是在静态环境下按事务的最长执行路径估算的执行时间，它假设事务在系统中无阻塞、无等待。

WCET用于实际调度是不精确的，因为在事务的具体执行过程中，它实际经过的路径很可能与最长执行路径不同，并且，同样的执行路径在动态环境里由于资源竞争会有不同的执行时间。

事务的实际执行时间是动态的，事务每一次执行时其执行时间都可能不同，因为它除了与程序本身有关外，还与系统的环境紧密相关，这正是调度器需要获取的重要信息。

图4.3　事务处理过程

图4.4　事务生存周期

在动态环境中，事务的执行时间与两类因素有关：第一类是程序本身，包括程序的执行路径，变量数量等；另一类是环境因素，包括系统中并发执行的事务个数、所操作的数据库的个数、数据库的长度、CPU的处理速度、网络传输能力等。由于CPU处理能力、网络带宽相对稳定，并且在前期WCET研究中已经考虑了这些因素的作用，这里，可以将它们作为基本平台。

根据有关灰色理论，设计事务动态执行时间为系统的主行为，受系统中并发执行的其他事务、事务访问数据库的页面数、事务的替代数等因素的影响。通过分析实验数据，建立主行为和这些影响因素的函数联系，从而推测程序在任意环境下的动态运行时间。

设X1表示事务执行时间；X2表示事务数；X3表示事务的平均替代数；X4表示事务访问数据库的平均页面数。

建立灰色模型需要运用累加生成技术，设原始数据序列可以表示为：

令为系统的主行为，为行为因子，它们的AGO（Acumulated Generating Operation）数据序列可以表示为：

假设数据序列和的每个成员包含n个元素，建立模型GM（1， N），则其灰微分方程为：

â＝［a，b1，b2，…，bN］T 为GM（1，N）的参数列，矩阵B和向量矩阵Y为：

参数列的最小平方估算：＾a＝（BT B）－1BTY（4．5）

对于我们的系统，建立模型GM（1，4），其灰微分方程为：

其中，），aij是状态xj对状态xi的影响，是预测值，以上方程也叫系统预测的状态模型。

为了确定估算事务动态执行时间的灰色模型，我们建立了测试环境，测试系统中包括1个数据库专用服务器，9个客户机，客户机上的数据库请求全部传送到服务器，由服务器集中处理。我们的测试在5个等价间隔时间上进行。原始测试数据如表4．1所示。

表4.1原始测试值

确立模型参数的步骤为：

第三步：计算常数系数。

根据公式（4．5），有：

有：a11＝－4．8966，a12＝－2．7397，a13＝2．0324，a14＝0．8717

由此，估算事务执行时间的模型为：

根据方程（4．7）得到预测值，并与之比较，由此可检验模型的精度，比较结果如表4．2所示。

表4.2　事务执行时间的预测值及其误差

在传统的预测方法中，正是因为不能估算并发事务对被估算事务的影响，不能确定数据库长度对事务执行时间的影响，只能孤立地估算事务的静态执行时间，这个静态执行时间在动态环境下的变动可能很大（甚至长期等待或死锁）。在系统中并发执行的事务数量较少时，事务间的冲突不大，可以将静态执行时间作为调度的参考，但随着系统中并发事务数量的增大，事务执行时间与其静态执行时间之间的偏差会大，此时，不能将静态执行时间作为调度的参考信息。从表4．2可见，采用灰色系统理论，预测值和实际值之间的误差随k值的增大而渐小，即随着系统中并发执行事务数的增加，以及数据库长度的增加，预测的精度也增高，系统越复杂，灰色建模的优势越明显。从实验看出，最大误差在毫秒级，适合实时数据库事务的一般要求。

考察特定WCET在动态环境下的表现，这只需要采用上述同样的方法，将程序的动态执行时间作为主行为，程序WCET作为影响因素即可。

4.4　替代的资源需求分析

当事务经过预编译而到达系统或经命令解释而在系统中生成时，不难提取关于事务的下列特性：

①事务中的各替代是否有可能触发新的活动。计算主动事务的截止期及优先级的分派都应考虑事务所可能触发的活动。

②定时限制及紧迫性、关键性等知识，包括事务的价值函数，软、硬实时特性等。

③资源要求、操作逻辑等。包括事务各替代访问的数据集、执行时间估算和各替代读写数据库的类型（是只读操作还是既读又写），操作的顺序。

④可能触发的活动的相关信息。

显然，上述有关事务的信息能为事务处理（包括调度、优先级分派、并发控制等）提供必要的支持。如对于时间要求紧迫的硬实时事务可分派高的优先级，先调度运行而满足其截止期；上述提取的知识存放在系统相关的表中，例如：

①事务表的结构如下：

struct tt（Trid，Trdt，Trtype，Tratime，Trbtime，Trrtime，oprtype，Trfreq）

其中，Trid为事务标识符，Trdt为事务截止期，Trtype为事务类型，它可以为硬实时事务，也可以为软实时事务；Tratime为事务到达时间，Trbtime为事务的开始执行时间，oprtype表示事务对数据库的操作类型，如仅执行插入操作（数据接收事务），对数据库仅执行读操作（执行控制事务），对数据库既读又写（数据处理事务）；Trfreq为访问数据库的频率。

②存取过程执行顺序表。该表记录一个事务中所有存取过程被执行的顺序。其结构如下：

struct Orderrstruct（procrid，successorrid，tranrid）

其中，procrid为存取过程标识符，successorrid为其后继存取过程标识符，tranrid为事务标识符。

4.5　替代的可调度性分析

嵌入式主动实时数据库系统的主要性能指标是成功率，为了更好地满足事务的定时限制，要求系统具有一定的“可调度性”预测的能力。所谓“可调度性”或称“可行性”预测就是在系统的当前状况下（包括系统负载量、资源使用情况），对当前系统中要调度的事务满足其定时限制的可能性程度进行分析。

在一事务被调度（再调度）或并发控制时，进行“可调度性”预测以辅助调度：

若预报“绝无可能”，即该事务无论如何都不能按时正常完成，则进行以下处理：

①不调度硬实时事务，因为无论如何该硬实时事务都不能完成，系统损失不可避免，消耗CPU只是无谓的牺牲。

②不调度固实时事务，因为固实时事务在其截止期后提交则价值为零。

③如果系统接受降低了的价值，可以调度软实时事务。

若预测有“危险性”，即该事务可能违反定时限制，则进行以下处理：

①动态调整优先级，或让它（尤其是硬实时事务）进入“紧迫”状态处理，必要时甚至牺牲（严格的）一致性以确保硬实时限制的满足。

②如果事务具备补偿性，则准备补偿以备不测。

对于一个实时事务，由于各个替代的性能不同，它们的可调度性也存在差异，系统应分析各替代的可调度性，再得到事务的可调度集。

定义4．4：在不考虑资源竞争时，如果实时事务T能满足相应约束而执行，则称该实时事务是可调度的，表示为：SC（T）。

定义4．5：事务T的一个任务TKi是可调度的，乃指：（stij（SUB （TKi）SC（stij）

定理4．1：当且仅当实时事务的所有任务（步）是可调度的，则该实时事务是可调度的。

即：

定义4．6：如果任务中的一个子事务是可调度的，则该任务是可调度的。

即Ej∈［1，Dg（TKi）］stij∈TKi∩SC（stij）→SC（TKi）

推理4．1：如果一个任务是可调度的，则其中至少包含了一个可调度的子事务。

由于实时事务的成功率与系统的实时环境有关，并不是每个替代都能成功执行，因此，我们必须结合替代本身的特点及系统的因素，排除那些不具备可调度性的替代，使得最后交给系统的替代都是具有较高成功可能性的替代，将内部调度得到的方案缩小到一个较小的有效范围，从而避免系统盲目地从实时事务中选取一个替代投入运行，提高实时事务的成功率。

定理4．2：当且仅当实时事务中存在可调度的替代时，该实时事务是可调度的。

证明：设实时事务T：：＝｛FXi｜1≤i≤Dg（GT）｝

当Ed FXd∈T SC（FXd）时，

由定义3．10可知，组成T的一个替代FXi，替代是一个特殊的实时事务，其中每个任务步包含了一个子事务。

根据定理4．1得：SC（FXi）

定义4．7：设有基于替代FXr的调度树S－treer，若有Ast∈FXr（t0＋etst≤dst）成立，则称S－treer为弱调度树，记为WS－Tree，其中t0为当前时间，etst和ds分别为子事务st在无资源竞争情况下的执行时间估算和截止期。

弱调度树表示的替代具有弱可调度性，在系统能满足其资源请求的理想状态下，该替代可以被调度执行。

定义4．8：对于一棵弱调度树WS－tree，当且仅当树中每个子事务都能在实时事务截止时间之前得到所申请的资源时，该调度树为强调度树SS－tree。它满足条件：

其中，Rδ为系统可以为sti提供的资源，resi为sti申请的资源集。

强调度树表示的替代具有强可调度性。由于实时系统的状态变幻莫测，很难预测是否能满足资源请求（特殊情况除外，比如，某些特殊的专用系统，不接受其他干扰信息，只处理专门事务，或者采用资源可强占策略，某些事务可随时强占系统资源，这样，只要系统中具有这些资源，就能保证满足事务的资源请求），因此，事务的强可调度性需要在系统调度到该事务时才能确认。

如果我们进行可调度性分析，能使系统有意识地选取成功率高的替代，就能提高系统的执行效率。可调度性分析算法如下：

S－Analysis（T）

输入：S（T）＝｛S－treei｜1≤i≤q｝—实时事务的调度树集，RM—系统资源占用矩阵。

输出：Ss（T）—T的强调度树集，Sw（T）—T的弱调度树集，Su （T）—T的不可调度树集。

步骤：

在生成强调度树时，必须结合系统的当时资源状况检验每个子事务的资源申请，如果发现某个子事务不可能得到所需资源，则删除之，并且删除所在的子树。在最坏情况下，所得到的结果是一个空的调度树，它说明该实时事务不能在其截止时间之前完全执行。

定义4．9：实时事务调度集由该事务所有的可调度替代组成。定义4．10：实时事务强调度集由其具有强调度性的替代组成。由此，可以判定实时事务的可调度性如表4．3所示。

表4.3　调度性能表