嵌入式实时数据库系统的接纳控制机制

5　接纳控制机制

本章提出的接纳控制机制IACM（Integration Admission Control Mechanism）需要内存数据库技术支持（在事务执行过程中无I/O延迟），IACM综合考虑事务的执行需求和价值，通过减少被系统接纳执行而过后又夭折的事务数量减少资源浪费。IACM的第一个特点是：与传统的依赖于事务优先级的抢占处理不同，在IACM中，当系统超载时，只有高优先级事务的价值不小于被抢占事务的价值总和时该事务才被接纳，其总体目标是使系统获得的价值最大。在前面的章节中，我们论述了基于功能替代的实时事务模型适用于嵌入式实时数据库系统，IACM就是建立在该事务模型上，因此，它适用于嵌入式实时数据库系统，这是它的第二个特点。

5.1　支持替代的接纳控制机制IACM

5.1.1　研究现状

嵌入式实时数据库系统必须具有较高的成功率，为此，大量的并发控制协议致力于尽可能地满足事务的截止期，将超过截止期的事务减至最少。但是这些协议只有当系统超载时才能体现出优势，而当系统超载时，超过截止期的事务数量却大幅度上升，从这个角度来看，并发控制机制是系统超载时提高成功率的补救方法；无论事务成功与否，处理这些夭折的事务都需要花费系统资源和CPU时间。但是，如果这些事务一开始就不被系统接纳，系统就不会在这些事务上浪费资源，会有更多的事务因此获得更多的成功机会，系统性能会更好，这就是接纳控制和负载管理要达到的目的。

接纳控制和负载管理通过减少被系统接纳执行而过后又不能满足截止期的事务来保留系统资源，有效控制系统负载，使系统资源能被合理分配、有效利用。S．Nagy和A．Bestavros提出的接纳控制协议将事务分为主任务和补偿任务两个部分，系统一旦接纳硬实时事务，则该事务必定在其截止期前结束：成功提交（主任务执行完成）或安全结束（执行补偿任务）。而软实时事务和固实时事务的补偿任务可以在截止期后执行，它们不考虑事务的WCET和资源需求，不能预计阻塞。S．Chakravarthy等人设置装载因子并与调度相结合，将系统负载控制在一定的范围内，系统的资源利用率较低。

接纳控制机制IACM采用内存数据库技术，它综合事务的执行需求和价值使系统资源得到高效利用的同时，其总体目标是最大化系统收益，适用于嵌入式实时数据库系统。

5.1.2　IACM系统模型

IACM涉及的属性有：

HRT：已接纳但没提交的硬实时事务集

SRT：已接纳但没提交的软实时事务集

RT：已接纳但没提交的全体实时事务集

NRT：非实时事务集

Ti：实时事务

eti：实时事务Ti的估算执行时间

etrFXij：实时事务Ti的替代FXij的分执行时间

SF：事务的松弛因子

Di：实时事务Ti的截止期

Vi（t）：事务Ti在时刻t的价值函数

cti：事务的临界点

t0：系统当前时间

ati：事务Ti的到达时间

rti：事务Ti的剩余执行时间

tendi：事务Ti的结束时间

tui：事务的已执行时间

由于我们的事务模型支持功能替代，一个实时事务可以包含功能等价的若干个替代，其中，任何一个替代成功执行则该事务提交，只有所有的替代都不能成功执行时该事务才夭折。因此，事务执行时间具有与传统意义不同的定义。在一个实时事务中，每个替代的执行时间都有可能是该事务的执行时间，这与系统调度的结果有关，每个替代的执行时间对应于传统意义下的事务执行时间。现在，实时事务的执行时间是由一组替代执行时间组成的向量。

定义5．1：对于实时事务Ti的任意替代FXij的估算执行时间，称为该实时事务的分执行时间，记做：etrFXij。

事务的分执行时间由前述的时间预测方法得到，需要注意的是，估算这些替代的执行时间需要在同样的环境下用同样的方法进行。

定义5．2：实时事务Ti的估算执行时间eti定义为一个时间向量：

eti＝［etrFXi1，etrFXi2，…，etrFXim］

由于实时事务的估算执行时间是一个向量，在实际运行中，是一个（或多个）替代在执行，如果运行着的替代能一次成功，则在运行过程中该事务的剩余执行时间就是该替代的剩余执行时间。但是，如果运行着的当前替代最终夭折，系统可能选择该事务的其他替代继续执行，此时，事务的剩余执行时间不能以被夭折替代的剩余执行时间为依据进行计算。然而，在事务成功执行并提交之前，很难断定该事务到底将运行几个替代？会以哪个替代为结束？可见，由于事务结构的复杂性，除了传统实时事务所涉及的因素外，嵌入式实时事务又增加了不确定因素，要精确计算事务的剩余执行时间是很难的。

通常而言，可采取以下策略计算嵌入式实时事务的剩余执行时间：

策略1：rti＝max（etrFXi1，etrFXi2，，etrFXim）－tui

取该事务最大分执行时间为此次事务执行时间，其隐含条件是：事务中只有一个替代参与执行，要么成功提交，要么该事务夭折，即在该替代夭折后没有时间选择其他替代继续执行。在很多情况下，空余时间只能使一个替代执行，一旦该替代失败，根本没有机会再执行其他替代，此时，为了放宽时间预测的幅度，策略1是很适用的。

策略2：rti＝min（etrFXi1，etrFXi2，…，etrFXim）

该策略的隐含条件如上所述，不同的是：在不考虑数据资源竞争的前提下，具有最小分执行时间的替代被调度的可能性较大，调度器往往会选择具有最小分执行时间的替代参与执行。策略2适用此种情况，从时间上来看，策略2是最优的。

策略3：rti＝（etrFXi1，etrFXi2，…，etrFXim）/m－tui

策略1和策略2代表了两种极端情况，策略3是策略1和策略2的折中，调度器既不选择分执行时间最大的替代，也不选择分执行时间最短的替代，这种情况最为普遍，因此，策略3使用频率最高。

由于存在系统资源的竞争，冲突在所难免，当前调度的替代有可能因被抢占或其他原因而夭折，在事务截止期之前，只要空余时间满足基本条件，调度器会选择该事务的其他替代继续执行。但是，这种转换到底要发生几次却是难以预测的，只能根据经验确定所调度替代的平均次数β，于是产生了策略4。

策略4是对策略3的扩展，在时间充裕的情况下，适用策略4。

策略4：rti＝β＊（etrFXi1，etrFXi2，…，etrFXim）/m－tui

在嵌入式实时数据库系统中，如果不能满足实时事务的截止期，则硬实时事务会给系统造成灾难，固实时事务的价值在截止期后变为零，软实时事务的价值在其截止期后也会降低，非实时事务的价值不随时间变化，已提交事务的价值保持最高状态。因此，如果给每个事务设置一个价值函数，则各种事务的价值函数为：

Ti∈HRT 则：

这样，我们可以用一致的观点看待所有事务。

定义5．3：对于具有价值函数Vi（t）的事务Ti，其有效临界点cti满足条件：Vi（cti）＝0。

硬实时事务和固实时事务的临界点等于其截止期，非实时事务没有临界点。

实现接纳控制的体系结构如图5．1所示。当事务到达系统，首先由分析器根据事务的有关信息和系统当前环境，判定该事务是否能被系统接纳，如果可以被接纳，则接纳控制器进行接纳处理，同时调用事务登录部件在事务接纳表中登录该事务，并将接纳信息传送给接纳控制器，最后，接纳控制器将该事务传送到调度器做进一步处理；否则，反馈器做拒绝接纳的处理。

说明：①事务到达接纳机制；②经过预分析，提取有关运行信息（如截止期、运行时间等）；③事务登录部件将事务的有关信息登录到事务登录表；④接纳控制器对事务登录表中的事务进行处理；⑤经过接纳控制器处理后将信息反馈给事务登录部件；⑥将接纳结果传给反馈器，准备向事务来源报告。

图5.1　接纳控制体系结构

5.1.3　接纳控制策略

定义5．4：对于事务集RT＝｛T1，T2，…，Ti，…，Tn｝，如果一个调度Sche－tab在无外部干扰（包括设备错误）下满足条件（commit（Ti）），则称Sche－tab为满调度。

满调度表示被接纳的事务在无意外或外部干扰下都能在其截止期内被调度并正常完成，即被接纳的事务不会因为资源冲突而超过截止期。满调度是一个理想的结果，要达到满调度需要接纳控制、并发控制和调度等一系列机制的联合作用。这里提出满调度只是从运行时间控制上给出一个标准，没有考虑其他的资源冲突，所以，这里的满调度是一个虚拟目标。

IACM的接纳控制策略分做基本接纳策略、抢占接纳策略和空隙接纳策略三大类，其中，基本接纳策略根据新事务的执行需求和系统当前负载决定是否接纳该新事务；抢占接纳策略应用于系统超载时，其总体思路是：即使系统容量饱和，也必须及时响应某些紧急事务（一般是硬实时事务），但决定是否接纳该紧急事务的标准不仅仅是优先级，还要衡量系统为此得到的收益是否大于损失；空隙接纳策略充分体现了实时事务的优越性，只有当系统负载小于阈值，CPU有空隙时，才能接纳非实时事务。

（1）基本接纳策略

第一，乐观无冲突策略ONCP（Optimism Non－conflict Protocol）。系统接纳新到达事务Ti的条件是：Di≥ati＋SF＊eti

这是一个比较传统的接纳条件，该策略假设事务在系统中与其他事务不发生冲突，独占资源，是一种比较理想化的策略。在不考虑资源竞争的前提下，到达的事务在其截止期前有足够的运行时间。

由于只要有一个替代成功执行，则该实时事务可以提交，所以，此时的接纳条件修正如下：Efxij∈Ti（Di≥（ati＋SF＊etrfxij））

该策略在多事务并发执行的系统中效果比较差，原因是：针对CPU而言，事务在微观上还是串行的，只有在CPU能在事务的截止期前为事务服务该事务才有可能完成，这种事务才能被接纳。

第二，价值有效策略VP（Value Efficiency Protocol）。如果系统接受降低了的价值，则超过截止期的实时事务依然可以继续执行，因此，系统接纳事务Ti的条件为：cti≥ati＋SF＊eti

对于具有替代的实时事务而言，条件修正如下：Efxij∈Ti（cti≥（ati＋SF＊etrfxij））

该策略对硬实时事务和固实时事务没有实质性作用，因为它们的临界点就是截止期。

第三，乐观串行策略OSP（Optimism Serialization Protocol）。以上策略保证：只要系统立即执行该事务，则该事务可能成功完成而提交。但正常情况下，大多数嵌入式实时数据库系统中活跃着多个事务，它们彼此竞争包括CPU在内的系统资源，因此即使不考虑其他对象（主要数据对象）上的冲突，也要求CPU时间总量足够分配给所有的实时事务。

扩展上述策略的条件，OSP策略规定被系统接纳的事务Ti同时满足以下条件：

①Di≥ati＋SF＊eti

②

其中，条件①是事务到达系统时，如果立即执行而且没有因资源冲突而延迟或阻塞，则为该事务成功执行需要满足的自身条件；条件②表示：系统中被接纳的所有事务的剩余执行时间之和小于最大截止期与当前时间的差距，在适当的调度策略下，有可能所有的事务都成功执行。

如果支持替代，则被系统接纳的事务Ti同时满足以下条件：①Efxj∈Ti（Di≤（ati＋SF＊etrfxij））

②

其中，条件①表示在事务中存在这样的替代：当事务到达系统时，如果立即执行该替代并且没有因资源冲突而延迟或阻塞，则为该事务成功执行需要满足的条件；条件②同上，但是在计算事务的剩余执行时间时应与条件①中的替代相呼应。

第四，价值有效乐观串行策略VOSP（Value Optimism Serialization Protocol）。如果系统接受降低了的价值，则被系统接纳的Ti满足条件：

①cti≥tai＋SF＊eti

②

其中，条件①表示事务到达系统时，如果立即执行而且没有因资源冲突而延迟或阻塞，则该事务执行完毕后能对系统产生正效益需要满足的自身条件；条件②表示：系统中被接纳的所有事务的剩余执行时间之和小于最大临界点与当前时间的差距，在适当的调度策略下，有可能所有的事务都执行完毕并给系统带来正效益。

如果支持功能替代，则被系统接纳的事务Ti同时满足以下条件：

①Efxij∈Ti（Di≥（ati＋SF＊etrfxij））

②

其中，条件①表示事务中存在这样的替代，当事务到达系统时，如果立即执行该替代而且没有因资源冲突而延迟或阻塞，则该替代执行完毕后能对系统产生正效益需要满足的自身条件；条件②同上。

第五，悲观串行策略PSP（Pessimism Serialization Protocol）。上述策略都没有考虑CPU以外的资源竞争，即没有涉及数据对象上的冲突，事实上，在嵌入式实时数据库系统中，事务不可避免地会发生资源冲突，此时，调度器往往根据事务的优先级决定调度次序，关于这部分内容已在相关章节讲述，这里，假设采取HP－2PL策略，如果低优先级事务持有资源，则高优先级的事务可以抢占低优先级事务的资源，低优先级事务因此而夭折；如果高优先级事务持有资源，则低优先级事务等待。为了适应嵌入式实时数据库系统中的事务特点、并发控制特点及调度特点，我们在接纳控制中引入优先级的信息，又由于事务的截止期往往与其级别相关，截止期越小其优先级越高，因此，我们直接使用事务的截止期信息。(www.xing528.com)

满足OSP和VOSP的事务可能出现图5．2所示的情况，由于T1的优先级较低，被T2抢占，导致T1因超时而夭折。要解决这种问题，系统通常是先运行紧急事务（优先级高的事务），方法是将事务按截止期进行排队，截止期紧急的事务先执行（注意：在调度时依然是并发执行），此时，被接纳事务满足下列条件：

图5.2　调度示意图

①Di≥ati＋SF＊eti

②

③对于被接纳的实时事务，存在这样的序列RT，满足条件：

将条件①改变为Efxij∈Ti（Di≥（ati＋SF＊etrfxij）），则支持功能替代。

其中，条件①和条件②的含义同上，条件③表示每个事务都有足够的时间运行，这是比较理想化的条件，非常严格。

将事务按其截止期升序排序，得到事务序列TT：T1，T2，…，Tj，…，Tn，当新的事务Ti加入到TT后保持升序不变产生新的事务序列RT。

定理5．1：是在事务集RT＝（T1，T2，…，Ti，…，Tn）上具有满调度的充分条件。

证明：设commit（Ti）表示事务Ti成功提交，end（Ti）表示事务Ti结束。成立，则下列命题同时成立：

i＝1时，rti＊SF≤D1－ati，即：rt1＊SF＋t0≤D1，

则commit（T1）；

i＝2时rt1＊SF＋rt2＊SF≤D2－ati，即：（rt1＊SF＋rt2＊SF－ati）≤D2

则tend1≤D2，tend2≤D2 有commit（T2）；

……

同理：i＝n时，

则：tendn≤Dn，有commit（Tn）。

根据定义4，在RT有满调度，定理得证。

第六，价值有效悲观串行策略VPSP（Value Pessimism Serialization Protocol）。如果系统接受降低了的价值，则扩展PSP中的条件③，被系统接纳的事务满足条件：

①Di（ati＋SF＊eti）

③对于被接纳的实时事务，存在这样的序列RT，满足条件：

将上述条件①改变为Efxij∈Ti（Di≥（ati＋SF＊etrfxij）），则支持功能替代。

在上述接纳控制策略中，乐观无冲突策略、价值有效策略的条件最宽松，保守串行策略的条件最严格，它们都没有明确提及系统超载时接纳控制机制的处理策略，或者自由抢占或者不允许抢占。由于嵌入式实时数据库系统往往同时接受多个事务，难以避免超载现象，系统又是在无人工干预下运行，必须具备处理超载的一套自我调节和控制机制，不允许抢占会使某些重要事务被错过截止期，给系统造成灾害；自由抢占又有可能导致级联抢占，一个事务刚被抢占了其他事务又被另外的事务抢占，造成资源浪费；更有甚者，一个紧急事务可能抢占了一批事务，系统因此损失了被抢占事务的总和，而该紧急事务带给系统的收益并没有大于该总和。后一种情况一直以来都被传统的接纳控制机制所忽视。

（2）抢占接纳策略

当紧急事务到达时，传统的方法是接纳该紧急事务并在调度阶段以适当的策略调度它，使它抢占低优先级事务，不管被抢占的事务数量有多少，价值有多少，由于上述的原因，这种盲目的抢占可能降低系统收益。

为了说明这个问题，请看下面的实例。

例5．1：假设优先级的级别按数值由大到小逐渐降低，有一组已被接纳的事务，其优先级和价值如下图所示。现在有一个新的紧急事务T8与现有事务发生资源冲突，其优先级和价值分别为2和50，在传统的方法下，系统接纳新事务T8并使它抢占事务T2、T3和T4，此时，T2、T3和T4可能因为被抢占而夭折，最终，系统因接纳T8获得收益50而失去收益78。这种情况在实际应用中常常发生。比如，在银行业中，假设T2、T3、T4和T8分别代表A、B、C和D公司的拨款请求，得到款项后的收益如表5．1所示。其中，D公司是一个小公司，如果不及时得到款项就会倒闭，倒闭带来的损失是50，A、B 和C公司不得到款项虽然不会倒闭但是会错过交易机会，失去如表5．1所示的相应收益，由于事关公司的生死存亡，T8的优先级高，如果按传统的方式来处理，势必牺牲A、B和C公司的利益而满足D公司的请求，结果是因小失大，从收益上来说，当然是宁愿放弃D公司。

表5.1　事务收益

上述问题的关键在于传统的处理方式基于事务的优先级，而事务的优先级又基于事务的紧迫性，有些方案也考虑了事务的价值，但是，事务的价值和其紧迫性是两个指标，不能保证它们总是一致的，一旦事务的紧迫性和价值发生错位，则一个优先级难以准确表示事务的两个特性，或者，优先级级别的划分不足以精细描述两个事务之间的区别。根据这种现象，提出下面的抢占接纳策略。

第一，乐观价值优势抢占策略OVPP（Optimism Priority of Value Preempt Protocol）。如果紧急事务Ti到达系统，即使系统满负荷，也应允许有条件地接纳高优先级的事务。其条件是被抢占的事务的总价值小于该事务的价值，即：Ti满足条件：

①Di≥ati＋SF＊eti

其中，条件①同上，条件②表示在现有的事务集TT中存在一个子集TS，TS中事务的价值总和小于Ti的价值。

第二，悲观价值优势抢占策略PVPP（Pessimism Priority of Value Preempt Protocol）。系统能提供足够的CPU时间处理紧急事务Ti，但是如果Ti被系统接纳后，其优先级不足以使它在截止期之前得到所需的时间，则此抢占是无意义的，因此，加强OVPP条件后，接纳Tj必须同时满足以下条件：

①Di≥ati＋SF＊eti

其中，条件①和条件②同上，条件③表示TS中事务的剩余执行时间大于的Ti执行时间，并且TS中所有事务的截止期都在Ti之前，这样就能保证在原有调度策略下在本该执行TS事务的时间内执行事务Ti。

基本接纳策略与抢占接纳策略结合，生成以下策略：

ONCP－OVPP、ONCP－PVPP、VP－OVPP、VP－PVPP、OSPOVPP、OSP－PVPP、VOSP－OVPP、VOSP－PVPP、PSP－OVPP、PSP －PVPP、VPDP－OVPP、VPSP－PVPP。

（3）空隙接纳策略

嵌入式实时数据库中除了实时事务外，还可能要处理非实时事务，系统优先处理实时事务，只有当CPU有足够空闲时，才接纳非实时事务。系统接纳非实时事务Ti的条件是：

5.2　支持补偿的接纳控制机制ACACM

事务模型2．9支持的实时事务由主任务和补偿任务组成，相应的接纳控制机制具有新的特点。实时事务即使在其截止期内也有可能因各种原因夭折。对于硬实时事务而言，为了避免造成系统灾难，系统应尽可能避免夭折的硬实时事务到达其临界点，换言之，在其临界点前有足够的时间运行相应的补偿事务，由此，接纳控制机制考虑的事务运行时间不仅包含事务主任务的执行时间，还应包含补偿事务的执行时间。接纳控制机制ACACM（Integration Alternative and compensation Admission Control Mechanism）支持这些要求。

为了说明ACACM，我们有以下约定：

实时事务ETi的主体执行时间定义为其主任务的执行时间，即：

tpi＝［etrFXi1，etrFXi2，etrFXij，…，etrFXim

实时事务ET的扩展执行时间定义为其主任务和补偿任务执行时间之和。即：

te－xi＝［tFXxi1，tFXxi2，tFXxij，…，tFXxim］

5.2.1　事务执行特点及控制原则

系统中的硬实时事务一旦超过其截止期就会给系统造成较大的损失甚至灾难，这是我们应尽力避免的，通常使硬实时事务具备可补偿性。

（1）事务执行特点

支持补偿的实时事务在系统中的执行特点如下：

①实时事务在其临界点前完全执行，成功提交。

②实时事务不能在其临界点前完成，若该实时事务是可补偿事务，则运行其补偿任务。

③系统超载时有紧急实时事务进入，接纳该事务则势必使其他实时事务受阻，则系统在获得该事务带来的收益时，会因此而遭受一定的损失。

④由于硬实时事务在其截止期前就得提交，一旦到达截止期则损失已难以挽回，因此，补偿任务实际上在其截止期之前就需开始执行，即补偿任务的执行需占用一部分CPU时间，在一定程度上影响着该事务主任务的成功。

⑤由于补偿任务的特殊性，系统应保证它能顺利执行，不被抢占。

⑥补偿任务不能在其原始开始时间（没有被调整的首次被释放时间）之后开始运行，否则该补偿任务不能完成。

（2）事务执行控制原则

根据以上特点，ACACM应遵循以下原则：

①价值正效应原则。系统一旦接纳一个可补偿的硬实时事务，则保证该事务结束，要么完成主任务而成功提交，要么完成补偿任务而安全结束。

②及时补偿原则。当预测实时事务在其临界点前无充分时间完成主任务时，必须保留执行其补偿任务的时间。

③价值权衡原则。当系统超载时，是否接纳紧急任务由系统获得的收益决定，只有当收益大于损失时，才接纳该事务，该损失不是负收益，而是系统所放弃的执行其他事务的收益。

④补偿时间单向移动原则。由于补偿任务的开始时间不能超过其原始开始时间，当不同的补偿任务发生冲突时，只能将原始开始时间较小的补偿任务向前推进，使其开始时间提前，而不能推迟其开始时间。当然，开始时间前移有可能导致主任务过早结束，造成虚假失败。

⑤无冲突补偿原则。一个补偿任务应与其他事务的补偿任务无冲突。

5.2.2　控制策略

ACACM的接纳控制遵从5．1所述的条件和策略，根据其采用的执行时间不同，ACACM又分为乐观控制策略和悲观控制策略。

（1）乐观控制策略

假设硬实时事务不需启动其补偿事务，使eti＝tpi，则只需根据主任务的执行时间进行接纳控制，该策略的优点是尽可能多的接纳实时事务，接纳那些可能顺利执行的硬实时事务；缺点是没有考虑补偿任务的执行时间，一旦某硬实时事务夭折，难以保证在其临界点前做出补偿。

（2）悲观控制策略

假定所有的硬实时事务都有可能启动其补偿任务，使eti＝te－xi，则需要同时考虑主任务和补偿任务的执行时间，只有满足扩展执行时间要求的硬实时事务，才能被系统接纳。该策略的优点是可靠性高，有效地防止系统灾难的发生；缺点是系统可能拒绝了某些满足主体执行时间、不满足扩展执行时间却能够顺利执行的硬实时事务，造成成功率下降。