用数量锁提高电子商务服务系统资源利用率的方法

技术领域

本发明涉及电子商务服务(如Web服务)系统集成的协调技术领域，特别是在电子商务 服务系统中，提高事务的并发性和死锁解除的方法。

背景技术

目前，电子商务中对服务进行集成是一个新的研究热点，以Web服务为例，对Web服务 的集成主要是通过工作流的方式实现的，主要的技术有基于XML的业务流程语言Business Process Execution Language for Web Services Version 1.1，05 May 2003和Web Services Flow Language(WSFL)1.0等。在对Web服务进行集成时，需要通过一定的方法保证其一致 性和可靠性。由IBM和Microsoft提出的Web Services Coordination(WS-Coordination) 和Web Services Transaction(WS-Transaction)，9 August 2002框架提供了保证单个事务 执行的一致性和完整性的机制。但是，在Web服务环境中，多个事务并发执行时，会出现与 传统的事务环境，如操作系统，数据库等相同的问题，如死锁问题。但是，WS-Coordination 和WS-Transaction提供的框架中并没有提供这个问题的解决方法。

现有电子商务中的Web服务，为了实现多个事务对资源的并发处理，通常采用对资源加 锁的方法，以提高事务的并发性。即：当有事务需要某种资源时，便在存储器保存的资源锁 表后生成一个事务等待列表，对该资源加锁，使用之后，便释放该资源上的锁。

在现有的事务列表中，不含有该事务要求资源的数目，而且加锁的类型也只有共享锁和 排他锁。因此，现有的电子商务中的Web服务系统，存在以下缺陷：

1、当有事务进行写操作时，须对所有资源加排他锁，这虽然可以避免事务冲突，但没有 考虑资源地数量，使系统资源和用户的资源得不到充分利用，同时也降低了事务请求的并发 性。

2、当系统发生死锁时，由于不能考虑各事务要求资源的数量，只有通过随机选择一个或 多个事务回滚，而无法考虑资源的利用率和用户的经济利益。

发明内容

本发明所要解决的技术问题是：提供一种用数量锁提高电子商务服务系统资源利用率的 方法，该方法可为系统的以下性能的改善创造条件：1、提高事务处理的并发度；2、可充分 利用系统资源；3、在死锁发生时，可考虑资源的利用率和用户的经济利益，选择性地回滚代 价小的事务。

本发明解决上述技术问题所采用的技术方案是：

用数量锁提高电子商务服务系统资源利用率的方法，它包括：

用于对服务器中的资源申请加锁的步骤、

用于对服务器中的资源进行加锁和解锁的步骤、

上述加的锁为数量锁，它的类型包括：读量锁、增量锁、减量锁；

用于对服务器中的资源申请加锁的步骤为：

(1)利用存储器保存一个资源锁表，该资源锁表表头中至少包括：该资源的名称、该资 源的数目、目前该资源上锁的组模式类型；

(2)在资源锁表中为每一个资源节点生成一个事务等待列表，每个事务对资源提出加锁 申请，就在等待列表中加上一个新的条目，等待列表的表头中至少包括：要求该资源事务的 名称、该事务申请加锁的类型、该事务的等待状态；当该事务申请加锁的类型为增量锁或减 量锁时，等待列表的表头还包括：该事务涉及资源的数目；

(3)对事务等待列表中的加锁申请进行判断；

当事务得到锁时，该条目表头中的等待状态置为非等待，进行下一步加锁和解锁的步骤；

当事务不能得到锁时，该条目表头中的等待状态置为等待。

本发明对事务等待列表中的加数量锁申请进行判断的方法包括：

(1)当资源锁表中的组模式类型为读量锁，且事务申请的锁模式也为读量锁时，将该事 务条目表头中的等待状态置为非等待；

(2)当资源锁表中的组模式类型为减量锁或增量锁，且事务申请的锁模式为减量锁时， 将事务申请的资源个数与资源锁表中该资源的数目进行比较，

a、当申请的资源个数不大于该资源的数目时，将该事务的等待状态置为非等待，并将资 源锁表中该资源的数目减去事务所申请的资源个数；

b、当申请的资源个数大于该资源的数目时，将该事务的等待状态置为等待；

(3)当资源锁表中的组模式类型为减量锁或增量锁，且事务申请的锁模式为增量锁时， 将该事务的等待状态置为非等待，并在该事务执行后，将资源锁表中的该资源的数目加上事 务增加的资源个数。

本发明用于对服务器中的资源进行解锁的步骤为：

(1)当需要解除的事务锁模式的类型为读量锁，扫描等待列表，看等待列表中是否有别 的事务在读取该资源，

a、如果有，组模式不变，删除需解除锁的事务条目；

b、如果没有，判断等待列表中的第一个事务的等待状态为等待的事务能否得到该资源上 的锁，

(a)若能得到，就修改资源的组模式，并将该事务的等待状态改为非等待；

(b)若不能得到，依次往下扫描事务等待列表中的等待事务；

(2)当解除的事务锁模式减量锁，组模式的类型为减量锁或增量锁，扫描等待列表，看 等待列表中是否有别的非等待事务的锁的类型为增量锁或减量锁，

a、如果有，组模式不变，删除需解除锁的事务条目；

b、如果没有，判断等待列表中的第一个事务的等待状态为等待的事务能否得到该资源上 的锁，

(a)若能得到，就修改资源的组模式，并将该事务的等待状态改为非等待；

(b)若不能得到，依次往下扫描事务等待列表中的等待事务；

(3)当解除的事务锁模式为增量锁，组模式的类型为减量锁或增量锁，扫描等待列表， 看等待列表中是否有别的非等待事务的锁的类型为增量锁或减量锁，

a、如果有，组模式不变，并做以下操作：

(a)删除需解除锁的事务条目；

(b)更新资源锁表中的该资源数目；

(c)再次扫描等待列表，看等待列表中是否有别的等待事务的锁的类型为减量锁，如果 有，判断该事务请求资源数是否不大于更新后的资源锁表中的该资源数目，

i、如果是，将该事务的等待状态改为非等待。

ii、如果不是，该事务的等待状态不变；

b、如果没有，判断等待列表中的第一个事务的等待状态为等待的事务能否得到该资源上 的锁，

(a)若能得到，就修改资源的组模式，并将该事务的等待状态改为非等待；

(b)若不能得到，依次往下扫描事务等待列表中的等待事务。

本发明方法提出一种电子商务服务系统中的数量锁模式，在等待列表的表头中包括了： 要求该资源事务的名称、该事务申请加锁的类型、该事务的等待状态、该事务涉及资源的数 目，且在电子商务服务系统服务器中的资源进行加锁和解锁的步骤的前面增加了用于对Web 服务器中的资源申请加锁的步骤，这样，由于可考虑事务涉及资源的数目和数量锁模式，能 够为系统的以下性能的改善创造条件：1、提高事务处理的并发度；2、可充分利用系统资源； 3、在死锁发生时，可考虑资源的利用率和用户的经济利益，选择性地回滚代价小的事务。

另外，本发明方法提供的用于对服务器中的资源申请加锁的步骤、用于对服务器中的资 源进行加锁和解锁的步骤，更能提高事务处理的并发度，且死锁解除时可充分利用系统资源。

附图说明

图1为资源锁表与事务等待列表的结构图

图2为数量锁兼容矩阵图

图3为加入Lock Service后的WS-Coordination框架

图4为加数量锁申请进行判断的方法流程框图

图5为对服务器中的资源进行解锁的步骤流程框图

具体实施方式

本发明方法的实施例1，它为用数量锁提高电子商务服务系统(用WS-Coordinaton提供 的协调服务的、在Web服务环境中的、对单个资源提出要求的订票系统)的资源利用率的方 法。

在WS-Coordinaton提供的协调服务中加入一个锁服务(Lock Service)，用来对Web服 务中的资源进行加数量锁、解数量锁以及进行死锁的检测，如图3。将这些算法用于 WS-Coordination框架的Lock Service中。Lock Service也是基于Web服务规范的，它与其 它Web服务之间的消息传递方式也是基于SOAP。这个服务负责对Web服务进行加数量锁，解 数量锁以及进行死锁的检测。

本发明方法的实施例1方法包括：

用于对服务器中的资源申请加锁的步骤、

用于对服务器中的资源进行加锁和解锁的步骤、

上述加的为锁的数量锁，数量锁的类型包括：读量锁S、增量锁INC、减量锁DEC；

用于对服务器中的资源申请加锁的步骤为：如图1，

(1)利用存储器保存一个资源锁表，该资源锁表表头中包括：该资源的名称(Resource Name)、资源编号(Resource ID)，资源的价格(Price)、该资源的数目(Resource Number)、 目前该资源上锁的组模式类型(Group Mode)；

(2)在资源锁表中为每一个资源节点生成一个事务等待列表，每个事务对资源提出加锁 申请，就在等待列表中加上一个新的条目，等待列表的表头中至少包括：要求该资源事务的 名称(Transaction ID)、该事务申请加锁的类型(Lock Mode)、该事务的等待状态(Waiting)； 当该事务申请加锁的类型为增量锁或减量锁时，等待列表的表头还包括：该事务要求资源的 数目(Num)；

(3)对事务等待列表中的加锁申请进行判断；

当事务得到锁时，该条目表头中的等待状态(Waiting)置为非等待(No)，进行下一步 加锁和解锁的步骤；

当事务不能得到锁时，该条目表头中的等待状态(Waiting)置为等待(Yes)。

本发明方法的实施例1中，当需要执行只读操作，如GetTotalCount操作时，需要对订 票Web服务中的Ticket资源加上读量锁S锁。当需要执行增量操作，即将Web服务中的资源 数增加，如ReturnTicekt(U)操作时，需要对Web服务中的资源加上增量锁INC(U)锁， INC(U)锁表示将资源数增加U。当需要执行减少操作，即将Web服务中的资源数减少，如 BookTicket(V)操作时，需要对Web服务中的资源加上减量锁DEC(V)锁，DEC(V)锁表 示将资源数减少V。

根据增量锁的定义，我们用INC(A，c)表示包含下列步骤的原子操作：READ(A，t)；t：＝t+c； WRITE(A，t)，这个原子性是比事务的原子性更高层次的原子性。

我们用sli(X)表示Ti向资源X申请一个S锁，用ili(X，U)表示Ti向资源X申请 一个将X的值增加U的增量锁，用dli(X，V)表示Ti向资源X申请一个将X的值减少V的 减量锁。ui(X)表示Ti释放X上的所有锁。

为了保证事务执行的正确性和事务之间的可串行化，需满足如下条件：

(1)事务的一致性。

当需要对Web服务内的资源X进行S操作时，必须申请该资源上的S锁。当需要对Web 服务内的资源X进行dli(X，U)操作时，必须先申请该资源上的DEC(U)锁。当需要对Web 服务内的资源X进行ili(X，V)操作时，必须先申请该资源上的INC(V)锁。在任何一个 事务Ti内部：

(a)在读操作Ri(X)之前，必须有sli(X)操作，且这两个操作之间不存在ui(X)。

(b)在增加操作INC(X，U)之前，必须有ili(X，U)操作，且这两个操作之间不存 在ui(X)。

(c)在减少操作DEC(X，V)之前，必须有dli(X，V)操作，且这两个操作之间不存 在ui(X)。

(d)在所有的加锁操作后面，必须要有一个针对加锁操作中元素的解锁操作。

(2)事务的两段锁(Two-phase locking)协议，在一个事务内部，所有的加锁操作必 须在解锁操作之前。即在事务Ti中，所有的加锁操作sli(X)、ili(X，U)、dli(X，V) 必须在ui(X)的前面。

(3)事务之间数量锁的冲突关系。

(a)由于读操作在增量操作之前还是在增量操作之后，与传统的增量锁模式相同，在数 量锁模式中，读量锁S与增量锁INC(U)和DEC(V)之间是冲突的，读量锁和读量锁之间是 兼容的。即，如果在一个事务调度中出现sli(X)，如果sli(X)后没有ui(X)操作，那 么其后面就不能出现dlj(X，U)和ilj(X，V)操作。反之如果在调度中出现dlj(X，U) 和ilj(X，V)操作，如果dlj(X，U)和ilj(X，V)操作后没有出现uj(X)操作，那么 其后就不能出现sli(X)操作。

(b)无论U和V为何值，INC(U)锁模式与INC(U)和DEC(V)锁模式之间是不冲突 的。即无论ilj(X，U)操作和dlj(X，V)操作的后面是否有uj(X)，ili(X，U)操作可 以出现在ilj(X，U)操作和dlj(X，V)的后面。

(c)当资源上没有锁，且事务要将资源的个数减少V2时，如果要减少的资源个数V2小 于或者等于Web服务中的资源个数N，那么就可以得到DEC(V2)锁，即当V2≤N时，R1＝Y， 否则R1＝N。即只有当要申请的资源个数V2不大于Web服务中的资源个数N时，才能执行dli (X，V2)操作。

(d)当事务T1已经持有资源上的增量锁INC(U1)时，若事务T2要申请资源上的DEC (V2)锁，那么为了保证DEC(V2)操作的成功，当要减少的资源个数V2小于或者等于Web 服务中的资源个数N时，就可以得到DEC(V2)上的锁，即当V2≤N时，R2＝Y，否则R2＝N。 即只有当要申请的资源个数V2不大于Web服务中的资源个数N时，才能在ili(X，U1)之 后执行dlj(X，V2)操作。

(e)当事务T1已经持有资源上的减量锁DEC(V1)时，若事务T2要申请资源上的DEC (V2)锁，那么为了保证DEC(V2)操作的成功，当要减少的资源个数V2小于或者等于N， 即V2≤N时，R3＝Y，否则R3＝N。即只有当要申请的资源个数V2不小于资源个数N时，才能 在dli(X，V1)之后执行dlj(X，V2)操作。

参看图2所示的数量锁兼容矩阵，对事务等待列表中的加数量锁申请进行判断的方法(如 图4)包括：

(1)当资源锁表中的组模式类型为读量锁，且事务申请的锁模式也为读量锁时，将该事 务条目表头中的等待状态置为非等待；

(2)当资源锁表中的组模式类型为减量锁或增量锁，且事务申请的锁模式为减量锁时， 将事务申请的资源个数与资源锁表中该资源的数目进行比较，

a、当申请的资源个数不大于该资源的数目时，将该事务的等待状态置为非等待，并将资 源锁表中该资源的数目减去事务所申请的资源个数；

b、当申请的资源个数大于该资源的数目时，将该事务的等待状态置为等待；

(3)当资源锁表中的组模式类型为减量锁或增量锁，且事务申请的锁模式为增量锁时， 将该事务的等待状态置为非等待，并在该事务执行后，将资源锁表中的该资源的数目加上事 务增加的资源个数。

本发明方法的实施例1中，用于对服务器中的资源进行解锁的步骤(如图5)为：

(1)当需要解除的事务锁模式的类型为读量锁，扫描等待列表，看等待列表中是否有别 的事务在读取该资源，

a、如果有，组模式不变，删除需解除锁的事务条目；

b、如果没有，判断等待列表中的第一个事务的等待状态为等待的事务能否得到该资源上 的锁，

(a)若能得到，就修改资源的组模式，并将该事务的等待状态改为非等待；

(b)若不能得到，依次往下扫描事务等待列表中的等待事务；

(2)当解除的事务锁模式为减量锁，组模式的类型为减量锁或增量锁，扫描等待列表， 看等待列表中是否有别的非等待事务的锁的类型为增量锁或减量锁，

a、如果有，组模式不变，删除需解除锁的事务条目；

b、如果没有，判断等待列表中的第一个事务的等待状态为等待的事务能否得到该资源上 的锁，

(a)若能得到，就修改资源的组模式，并将该事务的等待状态改为非等待；

(b)若不能得到，依次往下扫描事务等待列表中的等待事务；

(3)当解除的事务锁模式为增量锁，组模式的类型为减量锁或增量锁，扫描等待列表， 看等待列表中是否有别的非等待事务的锁的类型为增量锁或减量锁，

a、如果有，组模式不变，并做以下操作：

(a)删除需解除锁的事务条目；

(b)更新资源锁表中的该资源数目；

(c)再次扫描等待列表，看等待列表中是否有别的等待事务的锁的类型为减量锁，如果 有，判断该事务请求资源数是否不大于更新后的资源锁表中的该资源数目，

i、如果是，将该事务的等待状态改为非等待。

ii、如果不是，该事务的等待状态不变；

b、如果没有，判断等待列表中的第一个事务的等待状态为等待的事务能否得到该资源上 的锁，

(a)若能得到，就修改资源的组模式，并将该事务的等待状态改为非等待；

(b)若不能得到，依次往下扫描事务等待列表中的等待事务。

本发明方法的实施例2，它为用数量锁提高电子商务服务系统(用WS-Coordinaton提供 的协调服务的、在Web服务环境中的、对多个资源提出要求的订票系统)的资源利用率的方 法。

本发明方法的实施例2方法包括：

用于对服务器中的资源申请加锁的步骤、

用于对服务器中的资源进行加锁和解锁的步骤、

用于死锁检测的步骤；

用于死锁解除的步骤；

上述加的锁为数量锁，数量锁的类型包括：读量锁S、增量锁INC、减量锁DEC；

用于对服务器中的资源申请加锁的步骤(如图1)为：

(1)利用存储器保存多个资源锁表(一个资源一个资源锁表)，每个资源锁表表头中包 括：该资源的名称(Resource Name)、资源编号(Resource ID)，资源的价格(Price)、该 资源的数目(Resource Number)、目前该资源上锁的组模式类型(Group Mode)；

(2)在每一个资源锁表中为资源节点生成一个事务等待列表，每个事务对资源提出加锁 申请，就在等待列表中加上一个新的条目，等待列表的表头中至少包括：要求该资源事务的 名称(Transaction ID)、该事务申请加锁的类型(Lock Mode)、该事务的等待状态(Waiting)； 当该事务申请加锁的类型为增量锁或减量锁时，等待列表的表头还包括：该事务要求资源的 数目(Num)；

(3)对事务等待列表中的加锁申请进行判断；

当事务得到锁时，该条目表头中的等待状态(Waiting)置为非等待(No)，进行下一步 加锁和解锁的步骤；

当事务不能得到锁时，该条目表头中的等待状态(Waiting)置为等待(Yes)。

当一个事务中的任何一个条目表头中的等待状态(Waiting)置为等待(Yes)时，该事 务中的其它条目表头中的等待状态(Waiting)置为等待(Yes)。

本发明方法的实施例2方法中的用于对服务器中的资源申请加锁的步骤、用于对服务器 中的资源进行加锁和解锁的步骤同本发明方法的实施例1。

对事务等待列表中的加锁申请进行判断的方法如：

当事务调用Activation Service中CreateCoordinationContext操作后，所产生的 CoordinationContext中，必须包含如下的信息：该资源事务的名称(Transaction ID)、该事 务中请加锁的类型(Lock Mode)、该事务要求资源的数目(Num)等等。例如，一个要订2个 房间，2辆车，3张票的事务进行激活后，产生的CoordinationContext如下：

         xmlns：wsu＝”http：//schemas.xmlsoap.org/ws/2002/07/utility”

         xmlns：wscoor＝”http：//schemas.xmlsoap.org/ws/2003/09/wscoor”

         xmlna：myApp＝”http：//fabrikam124/myApp”

         s：mustUnderstand＝”true”>

               2002-06-30T13：20:00.000-05:00

               http：//Fabrikam123/SS/1234

               http：//schemas.xmlsoap.org/ws/2003/09/wstx

               http：//Business456/mycoordinationservice/registration

         Room

         2

         Car

         2

         Ticket

         3

本发明方法的实施例2中的用于死锁检测的步骤，可以用传统的分布式环境中的死锁检 测算法对Web服务环境中的死锁进行检测。

本发明方法的实施例2中的用于死锁解除的步骤，能够在死锁发生后，根据数量锁中提 供的数量信息进行最优的死锁解除。下面进行具体说明：

当某个节点的Lock Service检测到死锁后，就向死锁环中的各个事务发送检测到死锁的 消息，接收到消息的事务将它的加锁信息发送给检测到死锁的节点的Lock Service，然后由 该Lock Service判断出哪个或哪些事务是最佳的牺牲者，即将这些事务回滚后，企业(如旅 行社)能够最大限度地减少经济损失。

检测到死锁的Web服务的Lock Service将死锁环路中所有进程的业务量信息及加锁信息 搜集起来，然后根据这些信息进行最优化的死锁解除，这些信息主要包括：事务的ID，事务 的加锁情况，其中包括事务对哪些资源加锁，以及申请多少个资源。这些信息可以根据 CoordinationContext中的信息获得。

假设死锁中涉及到的事务有T1，T2，…Tk，涉及到的资源有R1，R2，…Rm，假设每种资源 的个数分别为N1，N2，…Nm，而对应于每种资源的权值分别为W1，W2，…Wm。另外T1，T2，…Tk 的资源请求分别为：

T1：DEC(R1，a11)；DEC(R2，a12)；…DEC(Rm，a1m)；

T2：DEC(R1，a21)；DEC(R2，a22)；…DEC(Rm，a2m)；

…

Tk：DEC(R1，ak1)；DEC(R2，ak2)；…DEC(Rm，akm)；

其中，aij为事务Ti申请资源Rj的个数。

设Ti的业务量为Bi，则可得

B1＝a11W1+a12W2+…+a1mWm；

B2＝a21W1+a22W2+…+a2mWm；

…

Bk＝ak1W1++ak2W2+…+akmWm；

这样我们将问题转换为：

求B1x1+B2x2+…+Bkxk的最大值，需要满足的条件如下：

a11x1+a21x2+…+ak1xk≤N1；

a12x1+a22x2+…+ak2xk≤N2；

…

a1mx1++a2mx2+…+akmxk≤Nm；

其中x1，x2，…xm的值都为0或1。当xi为0时，表示将Ti回滚，当xi为1时，表示让 Ti完成。

这是个典型的最大值问题。求解后可以得到能够取得的业务量的最大值，以及能使得业 务量最大的各个xi的值，当xi为0时，将Ti回滚，即可解除死锁，并使企业能够获得最大 的经济效益。

该问题的解法如下：将x1，x2，…xm值从00…0(m个0，x1，x2，…xm的值都是0)开始 到11…1(m个1，x1，x2，…xm的值都是1)中的每个值代入到不等式组中，将能够满足不等 式组的值组合保存到一个有效集中，然后将有效集中的值代入到需要求最大值的表达式中， 保存最大值，并记录该值为最大时的x1，x2，…xm值。

例如，假设业务流程执行前有4个房间，5张票，6辆车，T1要求定2个房间，4张票， 3辆车，T2要求定3个房间，2张票，2辆车，T3要求定1个房间，2张票，2辆车，另外， 我们假设一个房间的价格为10，一张票的价格为20，一辆车的价格为30。那么当这三个业 务流程执行可能会出现死锁，即在这三个事务之间产生死锁循环。当检测到死锁后，我们需 要选择一个合适的事务进行回滚，使得剩下的事务能够继续往下执行，且执行后对于旅行社 来说，获得的经济效益应该最大。根据资源的数目以及各个事务完成的业务量可知：

(1)如果让T1回滚，让T2和T3继续往下执行，那么T2和T3的总业务量为4个房间， 4张票，4辆车，T2和T3都可成功完成。

(2)如果让T2回滚，让T1和T3继续往下执行，那么T1和T3的总业务量为3个房间， 6张票，5辆车。由于总共只有5张票，因此不能满足T1和T3的要求，需要在T1和T3中 选择一个业务量最小的事务进行回滚。

(3)如果让T3回滚，让T1和T2继续往下执行，那么T1和T2的总业务量为5个房间， 6张票，5辆车。由于总共只有4个房间，5张票，因此不能满足T1和T2的要求，需要在 T1和T2中选择一个业务量最小的事务进行回滚。

根据计算我们可以得出T1的业务量B1＝10*2+20*4+30*3＝190，T2的业务量 B2＝10*3+20*2+30*3＝160，T3的业务量B3＝10*1+20*2+30*2＝110。我们需要求下面表达式的最 大值：190x1+160x2+110x3，而为了保证资源数目能够满足允许继续执行的事务的需求，我们 需要满足如下的条件：

           2x1+3x2+x3≤4；

           4x1+2x2+2x3≤5；

           3x1+2x2+2x3≤6；

其中x1，x2，x3的值均为0或者1。

解线性方程得190x1+160x2+110x3的最大值为270，此时x1＝0，x2＝1，x3＝1。即发生死锁后， 将T1回滚，让T2和T3继续往下执行，此时能够在Web服务中的资源数满足业务需求的情况 下，达到最大的经济效益。