|
|
|
移动计算中断连操作性能的改善方法 夏 涛
陶
洋（重庆邮电大学软件技术中心
重庆 400065） 【摘要】在移动计算环境中，断连后，移动客户机根据缓存的数据在本地执行事务;重新连接后，客户机中的事务作为暂态事务提交给固定主机重新执行。采用该方法，如果移动客户机与固定主机的读/写、写/写冲突机率很高，则暂态事务在固定主机上成功提交的概率就很低，大量的暂态事务就会夭折，这将浪费大量的服务器资源和通信资源，降低了整个系统的性能。为了提高暂态事务重提交的成功概率，我们提出按概率提交暂态事务的方法。该方法在冲突频率非常高的场合，能够节省移动客户机的传送开销、减轻固定主机的负担，提高事务的吞吐量。 【关键词】暂态事务
冲突频率 移动客户机 固定主机 1
引言 计算机技术和无线通讯技术的发展与结合使得一种全新的计算环境——移动计算成为现实。在移动计算环境中，移动客户机为了节省电源和通信费用或者由于网络故障等原因，可能经常处于断接状态[1]。为了能够支持客户机的断连操作，移动客户机在断接前必须要对主机服务器的部分或全部数据进行缓存。断连后，移动客户机根据缓存的数据在本地执行事务，重新连接后，移动客户机中的事务作为暂态事务提交给固定主机重新执行。如果没有数据冲突，则暂态事务就成功提交；如果有数据冲突，则暂态事务就夭折。 采用该方法，如果移动客户机与固定主机的读/写、写/写冲突机率很高，则暂态事务在固定主机上成功提交的机率就很低。大量的暂态事务夭折，就会浪费大量的服务器资源和通信资源，降低了整个系统的性能[2]。为了对移动计算断连操作这方面的性能作出改善，本文提出了一种按概率提交暂态事务的方法。 2
改善断连操作性能的算法 2.1
算法的基本思想 我们为服务器上每个发生冲突的数据项都设置一个冲突计数器，对每次发生冲突的数据项进行加1计数；为了准确反映近期内每个冲突数据项的冲突次数，应周期性地对冲突计数器减1。根据每个冲突数据项的冲突计数器的值，我们就可计算出它们各自的冲突概率[3]，我们把冲突概率高于某一设定值（高频率更新的门槛值）的数据项存放到高频冲突数据项集合中；把冲突概率小于某设定值的数据项从高频冲突数据项集合中删除。移动客户机在固定主机中缓存数据时，连同高频冲突数据项集合一起缓存。在断连时，移动客户机在本地执行事务；重连机后，移动客户机在向固定主机重提交暂态事务之前，首先计算暂态事务读和写的数据集合中有多少属于高频冲突的数据项，然而然后再计算暂态事务在固定主机中成功提交的概率；只有成功提交概率大于某一设定值时，才向固定主机提交和重执行该暂态事务，否则在移动客户机中就夭折该暂态事务。这样，既节省了上传该暂态事务的费用和时间，节省网络通信资源，同时固定主机也不必重新执行将要夭折的暂态事务，提高了执行效率。 2.2
算法的实现方法 为了便于更新数据的查找，我们设计了三级目录表。 被更新的关系名称表RL，
RL表中包含关系名[R1,R2…Ri…Rn]，其中每一个Ri都包含一个相应的指针项用于指向其对应的属性名称表Ali； 关系名Ri中被更新的属性名称表ALi
，ALi表中包含属性名[Ai1,Ai2…Aij…Ain],，其中每一个Aij都包含一个相应的指针项用于指向其对应的关系Ri中属性Aj列中被更新的记录表TLij；关系Ri中属性Aj列中被更新的记录表Tlij，Tlij表中包含主键名[Tij1,Tij2…Tijk…Tijp]，表中还包含计数值项UL。 为了能够支持向后删除操作，ALi和TLij两类表的表头中保存有后向指针。为了记录更新频率较高的数据项，还设置了一个数据高频率更新记录表，其结构为（Ri·Attrj·Keyk，UL）。其中：Ri表示被更新的数据项所在的关系名称；Attrj表示被更新数据项对应的属性名；Keyk表示被更新数据项所在记录的主键号码；UL表示该数据项被更新的次数。为了提高重连后的暂时事务成功提交率，服务器必须完成以下任务。 (1)当有数据项更新时，将它的计数值
UL加1，如果 UL>高频率更新的门槛值，则将该数据项插入到数据高频率更新记录表中；如果数据高频率更新记录表中已有该数据项的记录，则只需用现有UL代替原来的UL。 (2)周期性地将所有更新数据项中的UL减1，如果UL≤
高频率更新的门槛值，则将该数据项从高频更新表中删除；如果UL=0，则将该数据项从TLij表中删除；如果TLij表为空，将TLij表删除，同时还沿后向指针删除ALi中的Aij记录项；如果ALi表为空，将ALi删除，同时沿后向指针删除RL中的Ri记录项；这些删除操作可保证RL、ALi和TLij三种表中只记录近期内的更新项，因而它们的记录量都不会很大。在移动用户收集数据时，服务器不仅将满足条件的数据发送到移动用户，而且将满足条件的更新数据的计数值从数据高频率更新记录表中发送到移动客户机。 客户机上应完成的任务有：判断在断连时期暂态事务更新的数据项与高频率更新记录表子集中的数据项是否有冲突以及冲突的数量多少来决定在重连后是提交给服务器重新执行还是就地夭折。 2.3
算法的具体描述 在算法描述之前，首先定义如下函数。 ·find（Lab，X）：在列表Lab中查找指定的X项，如果成功则将X项的前向指针X﹒Pointer作为返回值，否则返回0值。 ·delete（Lab，X）：删除列表Lab中的X所在的记录项，同时判断列表Lab是否为空，如果为空，返回该列表头中保存的后向指针，同时删除Lab列表；如果不为空，返回0值。 ·insert1（Lab，X）：首先创建一个新列表，再将新列表的首地址和X项一起插入到指定的Lab列表中，Lab=RL表或AL表 ·insert2（Lab，X，1）：在列表Lab中插入X项和计数值1，Lab=TL表或AL表。 ·updata（Ri·Aij·Tijp，X）：把数据高频率更新记录表中的Ri·Aij·Tijp项的UL值修改为X，或把Ri·Aij·Tijp和X插入到数据高频率更新记录表中。 ·compare（X，数据高频率更新记录表）：在数据高频率更新记录表（或其子集）中查找与X匹配的记录项，如成功，返回该项中UL的值，如不成功，返回0值。 设服务器中n个关系，近期被更新的个数为n，每个关系最多有m个属性列，近期被更新的属性更个数为m，每个关系中最多有k个记录项，近期内被更新的记录项个数为k。 更新时计数值加1算法：设更新的数据项名为
Ri·Aij·Tijk ALi=find(RL，Ri) if
ALi≠0 then TLij=find(ALi，Aij) if
TLij≠0 then UL=find(TLij，Tijk) if
UL≠0 then UL=UL+1 else
insert2 (TLij,，Tijk,，1) if
UL>高频率更新的门槛值 then updata (Ri·Aij·Tijk，UL) else
insert1 (ALi,，Aij)
else
insert1 (RL，Ri)
周期性计数值减1算法：设n表示列表RL的记录数量，AL[i]表示列表ALi记录数量，TL[ij]表示列表TLij记录数量。 for
i=1 to n for
j=1 to AL[i] for
k=1 to TL[ij] UL=UL—1
if UL=0 then Aij=delete(TLij,
Tijk)
if
Aij≠0 then Ri=delete (ALi, Aij) if
Ri≠0 then delete (RL,Ri) next next next 客户机上的数据更新时的比较算法：设客户机更新的数据项名称存放在A[i]数值中。 for
i=1 to n X=compare
(A[i], 数据高频率更新记录表) UW=UW+X next if
UW≥设定值 then
重连机时，移动客户机不向服务器发送此暂时事务，作夭折处理。 else
重连机时，移动客户机向服务器发送此暂时事务，准备在服务器上重新执行。 2.4
性能比较 如果暂态事务的存取集合与冲突数据项集合的交集中的数据项数为k，则固定主机中的每个数据项发生冲突的概率为l
，暂态事务Ti将发生冲突的概率为P(Ti)=1―(1―l)k[4]
。 设每个暂态事务的传送开销为Ca，在固定主机上重新执行的开销为Cb。 ·直接提交总共开销ST1：
①
每个暂态事务的传送开销为Ca；
②
在固定主机上重新执行的开销为Cb；
③
直接提交的总共开销 ST1= Ca+Cb。 ·采用概率提交总共开销ST2：因为事务Ti将以P(Ti)的概率就地夭折，所以ST2总共开销ST2=[1—P(Ti)]·(Ca+Cb)。 则ST2比ST1节省的开销比为(ST1—ST2)∕ST1=
P(Ti)= 1―(1―l)k 该方法在冲突频率非常高的场合，能够节省重连时移动客户机的传送开销和时间，同时也避免了必将夭折的暂态事务在固定主机上不必要的重新执行，减轻了固定主机的负担和提高了事务的吞吐量。 从上述分析可知，在冲突频率非常高的场合，可以采用按概率提交暂态事务的方法。该算法提高了暂态事务重新提交的成功概率，节省了重连时移动客户机的通信费用和时间，同时也避免了将要夭折的暂态事务在固定主机上不必要的重新执行，减轻了固定主机的负担和提高事务的吞吐量，从而提高了断连操作性能。 (收稿日期：2007-05-10；Email：cjqft@163.com) 参考文献 [1]
G.H.Forman and J.Zahorjan. The Challenges of Mobile Computing. IEEE
Computer,1994,17(4):38~47 [2]
E.Pitoura and B.Bhargava. Maintaining Consistency of Data in Mobile
Distributed Environments. In: Proceedings.of International Conference on
Distributed Computing Systems, 1995. 404~413 [3]
D.Barbara and T.Imielinski. Sleepers and Workaholics: Caching Strategies in
Mobile Environments. In: Proceedings of ACM SIGMOD Conference, 1994. 1~12 [4]
陈希孺著.
概率论与数理统计. 中国科学技术大学,
1992. 44~104 The Improving Method With Mobile Computing After disconnection Tao-Xia
Yang-Tao (Software
Centre of Chongqing University of Posts and Telecommunications,ChongQing400065,China) Abstract:
With mobile computing, After disconnection, mobile clients execute
transactions locally based on the cached data , After reconnection, the
transactions in the mobile clients will be submitted as the tentative
transactions to the stable hosts to re-execute. Using this method, if
there’s a high probability of read/write and write/write conflicts between
mobile clients and stable hosts, the probability of successful submitting of
the tentative transactions will be very low. Lots of abortion of tentative
transactions will waste server and communication resources, reduce the
performance of the whole system. In order to increase success probability
for the re-submitting of tentative transactions, we provide a method to
submit tentative transactions according to probability. If used in the
environments with high conflicting probability, this method can save the
costs of transmission on mobile clients, reduce the load on the stable hosts
and improve the number of transactions the system can process. Key words: tentative transactions; probability of conflicts; mobile clients; stable hosts |