实时数据库系统服务质量管理研究

郭里城



实时数据库系统服务质量管理研究

郭里城

（漳州职业技术学院 计算机工程系，福建 漳州 363000）

以实时数据库事务调度为典型应用背景，研究和分析了不精确性计算方法，给出了一个基于不精确性计算的事务模型，并基于该事务模型提出了一种基于反馈控制的实时事务调度体系结构以及建模方法，为最终提高在超载环境下实时数据库系统的服务质量提供了有效的解决方案。

实时数据库；服务质量；事务调度；反馈控制；不精确计算

引言

随着实时数据库系统在电子商务、工厂生产过程控制和证券交易等软实时应用领域的推广，这些应用中数据的时间限制性也逐步凸显，对于数据库系统需用新鲜的数据去反映物理世界对象状态的最新变化也有了进一步的要求。同时由于实时数据库系统中的事务有着严格的时间限制，事务必须在其截止期内提交，否则系统会产生极大损失甚至带来灾难。

负载的不可预测甚至可能的超载以及资源的有限性，是实时数据库系统应用中面临的又一难题。近来，基于反馈控制的实时调度方法应用于软实时系统的研究取得了较大的进展。反馈控制实时调度把反馈控制理论和调度算法结合在一起，采用控制理论分析和建立实时系统的调度模型及实时系统的性能评价体系，通过连续地调整控制器来保持最优的性能。然而这些文献很少对系统处于超载情况下的调度进行研究。

本文以实时数据库事务调度为典型应用背景，研究和分析了不精确性计算方法，给出了一个基于不精确性计算的事务模型，并基于该模型提出了一种基于反馈控制的事务调度体系结构以及建模方法，为最终提高在超载环境下实时数据库系统的服务质量提供了有效的解决方案。

1 不精确性计算实时数据库事务模型

实时数据库系统必须能够并发地处理包括硬实时事务、固实时事务与软实时事务，而这些事务又可分为更新事务和用户事务。文中假设更新事务周期性到达，往数据库中写入从传感器采集来的数据；用户事务非周期地到达并且可以读时序数据和读/写非时序数据（“有效期”是任意长的数据）。然而，当系统超载运行时，系统无足够的时间来调度每个事务的实时执行，就会导致一些实时事务超过截止期，经典的RM，EDF，LLF等算法都无法直接处理这种超载情况。

文中把不精确计算方法之一的里程碑方法[1]应用到事务的不精确调度服务中，根据该方法将一个事务分割成若干子事务。假定事务Ti有一个关键子事务（Mi）和n个可选子事务Oi,j（0≤j≤n）组成。ti∈{Mi,Oi,1,…,Oi,n}表示事务Ti的子事务。同时假设事务Ti的所有子事务在同一时刻到达，当其关键子事务Mi完成时，第一个可选子事务Oi,1才执行。通常，一个可选子事务Oi,j在Oi,j-1（2≤j≤|Oi|）完成的时候才执行。设定每个子事务ti的截止期为事务Ti的截止期。如果一个子事务已经完成或者错过它的截止期那么这个子事务就终止。一个事务Ti终止的条件是当子事务Oi,|Oi|完成或者事务Ti中的一个子事务错过它的截止期。

2 反馈控制调度体系结构

由于实时数据库更新一个数据对象的时间总有一定的延迟，并且系统的负载难以预知，因此系统可能出现超载的情况。先前的一些研究通过采用反馈控制调度[2]和动态更新策略[3]，用户事务和更新事务能够得到一个动态的平衡。在这些方法中，侧重点在于保持用户事务具有低的错失率上。然而，当负载比较小时，需要把精力用在保持数据的新鲜度和一致性上。因此，文中提出了一种适应不精确事务模型的反馈控制调度体系结构FCS，见图1。

图1 反馈控制调度体系结构

2.1 准入控制器

准入控制器决定用户事务是否可以提交给系统。工程技术人员设定一个总估计请求利用率（UE），当提交的子事务的估计利用率之和EETi≤UE时，准入控制器接受该用户事务Ti并插入到就绪队列中。

2.2 事务处理器

事务处理器由一个新鲜度管理器（FM）、并发控制器（CC）和基本的调度器（BS）组成，用来处理一个事务的执行。

新鲜度管理器决定用户事务是否使用不新鲜的数据；并发控制器使用高优先级（具有更早截止期的事务）两阶段锁（2PL-HP）的并发控制方法解决冲突；基本调度器根据一个调度策略（例如，EDF和RM）调度已提交的事务。

2.3 精确度控制器

精确度控制器用来决定是丢弃还是执行一个更新事务。如果DEi≤MDE，（DEi是将要被事务Tj更新的数据对象di的当前数据误差），那么这个更新事务将被丢弃；如果di的数据误差大于MDE，那么就执行这个更新事务。同时在这两种情况下，di的时间戳也被更新，保证数据的外部（或绝对）一致性不被违背。

2.4 监视器

2.5 QoD控制器

QoD管理器根据受控变量M（k）、U（k）与性能参考值MrM、MrO和Ur进行比较后得到的△U调整数据质量等级MDE，然后基于该MDE调度更新事务的执行。

3 受控系统的建模

实时数据库系统通常是一个非线性的和时变的系统，由于PI控制器方法的健壮性，因此可以用PI控制器来模拟一个以控制为目的的线性化模型的系统。受控系统模型如图2。

图2 受控系统模型

从控制输入开始，第k＋1个周期的估计请求利用率可用下式表示，它是在第k个周期中的估计请求利用率（UE（k））和估计利用率调整量△U（k）的和。

UE（k+1）= UE（k）+△U（k） (1)

由于受控系统可能存在未知的事务和数据冲突的执行时间，因此，实际CPU利用率UA（k）可能和估计CPU利用率UE（k）不同。所以UA（k）根据下式来计算：

Ga(k)表示执行时间因子，它是一个时变的变量，表示总请求利用率的负载变化范围。由于Ga(k)是时变的，为了保证系统的稳定性，文献[2]采用Ga(k)的最大值GA=max{ Ga(k)}=2来替代系统模型Ga(k)。

由于饱和原因，UA和U之间的关系是非线性的。当UA>100%（CPU超载）时，即使△U改变了，U也不会有变化。等式（4）描述了这样的一种关系：

GMM和GMO分别表示关键子事务和可选子事务的错失率因子。因此，在可调度利用率极限附近，有

从等式(1)－(8)，可以进一步得出每一个受控变量在饱和区外时的传递函数：

利用率控制器： PU=GA/z-1，UA≤100%；关键子事务错失率控制器： PMM= GAGMM/z-1，UA>UthM；可选子事务错失率控制器：PMO= GAGMO/z-1，UA>UthO。模拟最坏情况下的系统[6]，可以获得错失率因子GMM和GMO。

文中的实验设置采用在事务负载到达率的范围从5tps～70tps，并以5tps递增，并且用户事务包含的可选子事务个数满足1≤NOi≤3。图3表示了在不同负载情况下的错失率。

从图3中可以看出可选子事务和关键子事务的可调度极限分别为UthO=15tps、UthM=45tps。因此，当负载在50tps～55tps和25tps～30tps之间增加时，可以根据公式（5）和公式（6）可以推导出GMM=1.66和GMO=2.23。

因此，根据上面得出的GMM、GMO从而可以得出利用率控制器、关键子事务控制器、可选子事务控制器在各自线性区域内的传递函数：PU、PMM和PMO。

图3 实际负载与错失率关系

4 反馈控制器算法设计和调整

由于PI调整器并不需要一个受控系统的精确模型，因此，文中采用PI控制器来调整系统性能。文献[2]中已经有一些FCS策略，像FC－U，FC－M和FC－UM。文中的反馈控制器的算法，使用FC－M和FC－UM来控制数据和用户事务的质量。图4显示了错失率（含关键子事务和可选子事务控制器）和利用率控制器的概况。

图4 错失率、利用率控制器结构

采用同一个标记E（k）来表示EM（k）和EUtil三个性能误差。文中使用PI控制函数来计算控制输入△U（k），同时加入积分控制器来改善系统的稳态性能[7]。

△U(k)=△U(k-1)+KP((KI+1)E(k)-E(k-1)) (9)

对等式（9）进行z变换后得到：

C(Z)=g(z-r)/z-1 其中：g=(KP(KI+1)),r=1/KI+1

4.1 控制器参数的调整

用C（z）来表示关键子事务控制器、可选子事务控制器和利用率控制器，M（z）和Mr（z）分别来表示实际错失率的z函数和错失率参考值的z函数。那么每个反馈控制环的传递函数就能得出：

从而，可以根据等式(10)得出错失率和利用率的闭环传递函数为：

可以根据公式（9）和（11），采用根轨迹法在matlab7.1中手动调整各个控制器的P参数和I参数。调整P、I参数的过程中，设定系统的性能参数为：稳定时间Ts≤30s、超调量Mp≤20。

图5 调整关键子事务控制器后的阶跃响应曲线

图6 调整关键子事务控制器后的根轨迹图

图5显示了关键子事务错失率控制器的阶跃响应图，从图中可以看到overshoot＝18.9％，settletime＝14.2s，满足系统的性能要求。从图6可看出极点在单位圆内，因此系统是稳定的[7]。从图6中还可以得出KP=0.9738，KI=0.541；获取可选子事务的和利用率控制器的KP和KI的方法同上。表1给出了最后调整的结果。

表1 控制器参数

4.2 算法描述

使用FC-U调度算法使用一个利用率控制回路控制利用率U（k），如图4中控制决策选择利用率回路，断开错失率回路；FC-M调度算法使用一个错失率回路控制错失率M（k）（含关键子事务MM（k）和可选子事务MO（k）），断开利用率回路。由于单纯采用FC-U和FC-M控制，实时数据库系统均会不同程度的进入非线性饱和区[8]，因此提出如下调度解决方案FCS-UM。

获取每个采样周期MM（k）、MO（k）和U（k）的值

If △UM（k）<0∧△UO（k）<0 then

△UMP=△UM+△UO

Else △UMP=min（△UM，△UO）；

△U（k）=min（△UMP，△UUtil）；

If (△U（k）>0∧MDE（k）>0) then

升级QoD；

把调整后的信息提供给准入控制器；

Else

If (△U（k）<0∧MDE（k）

降级QoD；

把调整后的信息提供给准入控制器；

Else

If (△U（k）<0∧MDE（k）=MDEr×MP) then

拒绝事务的进入；

End If

5 结语

基于反馈控制的实时事务调度框架提供了一个通用的软件架构，通过将实时系统映射成反馈系统的结构，进而采用控制理论较容易对实时系统进行分析和设计。然而在运用这些理论时，有些并不能完全适合实时数据库系统的事务调度。本文将不精确性计算引入实时数据库事务的模型构造中，并基于该模型将反馈控制理论加入实时数据库事务调度的分析中，给出了一个基于反馈控制的实时事务调度体系结构及其建模方法，这将有助于完善反馈控制实时事务调度框架理论的设计分析。

[1] K.J.Lin,et a1.Imprecise results:utilizing partial computation in real-time systems[J].Proc.Real-Time Systems Symp.Dec, 1987:210-217.

[2] C. Lu, J.A. Stankovic, G. Tao, and S.H. Son.Feedback Control Real-Time Scheduling: Framework, Modeling and Algorithms[J]. Real-Time Systems, Vol.23, nos. 1/2, July/Sept. 2002:85-126

[3] K.Kang, S.H.Son, J.A.Stankovic, and T.F.Abdelzaher. A qossensitive approach for timeliness and freshness guarantees in real-time databases[C].14th Euromicro Conference on Real-time System, June 19-21,2002.

[4] Abdul, J.Jerri.The Shannon Sampling theorem-Its Various extension and applications: A tutoral review[J].Proc.of the IEEE, Vol.66,NO.11,Nov,1977:1565-1596.

[5] 王荣辉,王战铎.计算机控制系统中采样周期的选择方法[J].陕西工学院学报,1997(2):39-44.

[6] Joseph L. Hellerstein, Yixin Diao, Sujay Parekh, Dawn M.Tilbury. Feedback Control of Computing Systems[M].Publisher: Wiley, John & Sons, Incorporated. August 2004.

[7] 王翼.现代控制理论[M].北京:机械工业出版社,2005.

[8] 魏立峰,马卫国,于海斌.反馈控制实时调度中采样周期的研究[J].自动化仪表,2002,23(9):25-29.

Study on QoS in the real-time database system

GUO Li-cheng

(Computer Department of Zhangzhou Technical Institute, Fujian Zhangzhou 363000, China)

With the scheduling of real-time database transaction as typical application background, we study and analyze on imprecise computing thesis and present the real-time transaction model based on imprecise computing. Based on this transaction model structure of scheduling of real-time database and method of modeling scheduling structure of real-time transaction based on feedback control thesis was presented, which improve the QoS of real-time database system in the overload environment.

Real-time database; Quality of service; Scheduling of transaction; Feedback control;Imprecise computing

2012－09－25

郭里城（1979－），男，福建漳州人，助教，硕士。

TP392

A

1673-1417（2012）04-0001-06

（责任编辑：季平）