为AJAX实现互斥

作者：佚名来源：不详发布时间：2007-4-13 19:01:58

　　随着AJAX范例得到越来越广泛的应用，浏览器页面可以在向后台服务器请求数据的同时保持前端用户界面的活跃性（因此在AJAX中称为异步）。然而，当这两个活动同时访问共用的JavaScript和DOM数据结构时就会引发问题。JavaScript没有提供针对该并发程序问题的经典解决方案。本文描述了作者在互斥机制方面的新见解，该经过验证的互斥机制在JavaScript中能发挥良好的作用。

为什么需要互斥？

　　当多个程序逻辑线程同时访问相同数据的时候，问题便产生了。程序通常假定与其交互的数据在交互过程中不发生改变。访问这些共享数据结构的代码称为临界区，一次只允许一个程序访问的机制被称为互斥。在AJAX应用程序中，当对来自XMLHttpRequest的应答进行异步处理的代码同时操纵正在被用户界面使用的数据时，便会发生这种情况。这个共用的数据可能是用于实现MVC数据模型的JavaScript和/或web页面自身的DOM。如果二者中的任一个对共享数据做了不协调的更改，那么二者的逻辑都将中断。

　　也许您会说“等等，为什么我没有遇到过这种问题？”。遗憾的是，这种问题是同步依赖的（也叫做竞态条件），因此它们并不总是发生，或者也许从不发生。它们的或然性基于许多因素。基于健壮性考虑，富internet应用程序应该通过确保这些问题不会发生来阻止出现这种情况。

　　因此，需要一种互斥机制来确保同时只能打开一个临界区，并且在它结束之后才能打开另一个。在大多数主流计算机语言和执行框架中，都提供互斥机制（经常是几种），但是应用于浏览器端的JavaScript却没有提供这种互斥机制。虽然存在一些无需专门的语言或环境支持的经典互斥实现算法，但是即使这样还是需要一些JavaScript和浏览器（如Internet Explorer）所缺少的要素。接下来介绍的经典算法在这些浏览器和语言中能发挥良好的作用。

面包店算法

　　在计算机科学文献中的几种互斥算法中，所谓的Lamport面包店算法可以有效地用于多个相互竞争的控制线程，该算法中线程之间的通信只能在共享内存中进行（即，不需要诸如信号量、原子性的set-and-test之类的专门机制）。该算法的基本思想源于面包店，因为面包店需要先取号然后等候叫号。清单1给出了该算法的框架（引自Wikipedia），该算法可以使各线程进出临界区而不产生冲突。

　　清单1. Lamport面包店算法伪代码

// declaration & initial values of global variables
Enter, Number: array [1..N] of integer = {0};
// logic used by each thread...
// where "(a, b) < (c, d)"
// means "(a < c) or ((a == c) and (b < d))"
Thread(i) {
　while (true) {
　　Enter [i] = 1;
　　Number[i] = 1 + max(Number[1],...,Number[N]);
　　Enter [i] = 0;
　　for (j=1; j<=N; ++j) {
　　　while (Enter[j] != 0) {
　　　　// wait until thread j receives its number
　　　}
　　　while ((Number[j]!=0)
　　　　 && ((Number[j],j) < (Number[i],i))) {
　　　　// wait until threads with smaller numbers
　　　　// or with the same number, but with higher
　　　　// priority, finish their work
　　　}
　　}
　　// critical section...
　　Number[i] = 0;
　　// non-critical section...
　}
}

　　如上所示，该算法假定各线程清楚自己的线程编号（常量i）和当前正在活动的线程总数（常量N）。此外，还假定存在一种等待或休眠方式，例如：暂时将CPU释放给其他线程。遗憾的是，Internet Explorer中的JavaScript没有这种能力。虽然如此，如果实际运行在同一线程上的多个代码部分表现为各自运行在独立的虚拟线程上，那么该面包店算法不会中断。同样，JavaScript具有一种在指定延迟后调度函数的机制，所以，可以使用下面的这些方法来优化面包店算法。

[责任编辑:cndownzcom]

Wallace变体

　　在JavaScript中实现Lamport面包店算法的主要障碍在于缺少线程API。无法确定当前正在哪个线程上运行以及当前正在活动的线程数目，也无法将CPU释放给其他的线程，无法创建新的线程来管理其他线程。因此，无法查证如何将特定的浏览器事件（例如：单击按纽、可用的XML应答等）分配到线程。

　　克服这些障碍的一种方法是使用Command设计模式。通过将所有应该进入临界区的逻辑以及所有启动该逻辑所需的数据一起放入到command 对象中，可以在负责管理command的类中重写面包店算法。该互斥类仅在没有其他临界区（封装为独立的command对象方法）在执行时调用临界区，就像它们各自运行在不同的虚拟线程中一样。JavaScript的setTimeout()机制用于将CPU释放给其他正在等待的command。

　　为command对象假定一个简单的基类（见清单2中的Command），可以定义一个类（见清单3中的Mutex）来实现面包店算法的Wallace变体。注意，虽然可以通过很多方式在JavaScript中实现基类对象（为了简洁起见，这里使用一种简单的方式），但是只要各个command对象拥有某个惟一的id，而且整个临界区被封装在单独的方法中，那么任何对象模式都可以使用这种方法。

　　清单2. 用于 Command 对象的简单基类

1 function Command() {
2　if (!Command.NextID) Command.NextID = 0;
3　this.id = ++Command.NextID;
4　// unsynchronized API
5　this.doit = function(){ alert("DOIT called"); }
6　this.undo = function(){ alert("UNDO called"); }
7　this.redo = function(){ this.doit();　　　　　}
8　// synchronized API
9　this.sDoIt = function(){ new Mutex(this,"doit"); }
10　this.sUnDo = function(){ new Mutex(this,"undo"); }
11　this.sReDo = function(){ new Mutex(this,"redo"); }
12 }

　　Command类演示了三个临界区方法（见5-7行），但是只要预先将对该方法的调用封装在Mutex中（见9-11行），那么就可以使用任何方法。有必要认识到，常规方法调用（例如非同步的方法调用）与同步方法调用之间存在着重要的区别：具有讽刺意味的是，必须保证同步方法不同步运行。换句话说，当调用sDoIt()方法时，必须确保方法doit()还未运行，即使方法sDoIt()已经返回。doit()方法可能已结束，或者直到将来的某一时间才开始执行。也就是说，将对Mutex的实例化视为启动一个新的线程。

[责任编辑:cndownzcom]

　　Mutex类的基本逻辑是将每个新的Mutex实例放入主等待清单，然后将其在等待队列中启动。因为每次到达“队首”的尝试都需要等待（除了最后一次），所以使用setTimeout来调度每次在当前尝试停止的位置启动的新尝试。到达队首时（见17行），便实现了互斥性访问；因此，可以调用临界区方法。执行完临界区后，释放互斥性访问并从等待清单中移除Mutex实例（见20-21行）。

　　Mutex构造函数（见23-31行）记录其Command对象和方法名参数，然后寄存在一个运行中临界区的稀疏数组中（Mutex.Wait），这通过清单4中所示的Map类来实现。然后构造函数获得下一个编号，并在队尾开始排队。由于等待编号中的间隔或副本不存在问题，所以实际上使用当前的时间戳作为下一个编号。

　　attempt()方法将初始伪代码中的两个wait循环组合成一个单独的循环，该循环直到队首时才对临界区失效。该循环是一种忙碌-等待循环检测方式，可以通过在setTimeout()调用中指定延迟量来终止该循环。由