利用AJAX技术实现Web开发中的互斥技术(1)

一、简介

借助于AJAX技术，一个浏览器页面能够实现在后台向服务器发出数据请求的同时，前端用户接口继续保持活动状态。这导致一种典型问题的出现―前面两种活动同时存取普通JavaScript和DOM数据结构。传统情况下，对于这种并发编程问题的解决方案并不是使用JavaScript提供的。本文正是描述一种改进的经过证明的互斥机制―它能够使用JavaScript实现并发编程，从而有效地克服JavaScript所存在的局限性。

二、为什么会存在互斥？

在任何时候，只要程序中存在要求同时存取相同数据的多线程逻辑，那么就会存在互斥问题。正常情况下，这些程序都假定它们所与之交互的数据是不会发生改变的。存取这些共享数据结构的代码部分称作“临界区”，而每次仅允许一个执行的操作称为互斥操作。当异步地处理来自于XMLHttpRequest响应的代码要求同时操作用户接口代码部分使用的数据时，这种情形也出现在AJAX应用程序中。这种共享数据可能是实现一种MVC数据模型的JavaScript变量，也可能是web页面本身的DOM。如果任何一方对共享数据作了不当修改，那么双方逻辑都会中断。

你可能会问：“为什么我没有遇到过这种情况呢？”遗憾的是，这种类型的问题往往是时间依赖性的（也叫作“竞态条件”）；因此，它们不会总是出现，而是根据多种因素接一定的概率出现。为了实现健壮性，RIA（丰富的互联网应用程序）必须通过一定措施来预防这种情况的发生。

因此，我们需要建立一种互斥机制以确保每次操作中仅有一个临界区开始和结束（不能交叉）。大多数主流计算机语言和执行框架都提供了若干种互斥机制；然而，遗憾的是，这种互斥机制却并不存在于浏览器端JavaScript语言中。尽管目前已经存在一些杰出的不要求特殊语言或环境支持的互斥算法，但即使这些算法也要求实现一些JavaScript和浏览器（例如Internet Explorer）所不支持的功能。最后，不得不对这些算法加以改编才克服这些浏览器和语言限制。

三、Bakery算法

在计算机科学的几种著名的互斥算法中，一种著名的算法就是Lamport发明的Bakery算法。该算法适用于，当任何两个线程之间的通讯是共享存储时，控制多个线程之间的共享存储竞争。在这种算法中，以“面包店”形象地比作一个信号量，顾客为了购买面包必须按序号等待，直到他们的号码被调用为止。列表1是这个算法的大致框架（来自于Wikipedia）。该算法能够使得每一个线程都可以毫无冲突地进入和退出临界区。

//声明全局变量并对之赋初值
Enter，Number:array [1..N] of integer = {0};
//由每一个线程所使用的逻辑...
//下面描述的“(a， b)<(c，d)”
//意味着“(aThread(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) {
//等待，直到线程j收到它的编号为止
}
while ((Number[j]!=0)
&& ((Number[j]，j) < (Number[i]，i))) {
//等待，直到小于或等于该编号的且具有更高优先权的线程出现，然后才能执行其相应的工作
}
}
//临界区...
Number[i] = 0;
//非临界区...
}
}

列表1.Lamport的Bakery算法伪码

由上所示，该算法假定每一个线程都了解它自己的线程号（i）以及当前活动的线程总数目（N）。它还假定存在一种实现等待（或睡眠）的方法；也就是说，存在一种能够把CPU控制权暂时让予其它线程的方法。遗憾的是，Internet Explorer上的JavaScript并不具有任何这其中之一的能力。不过，如果运行在同一个实际线程上的代码的多个部分“假装”每个子部分都运行在一个独立的虚拟线程上时，那么这个Bakery算法并不会终断执行。而且，JavaScript确实实现了一种机制―在经过指定的延迟之后调度一个函数。因此，我们有可能经过巧妙地修改Bakery算法来满足以上条件。

四、Bakery算法的Wallace改进

用JavaScript实现Lamport的Bakery算法的主要障碍在于，没有线程级API―没有办法知道当前正运行哪个线程，或有多少线程是活动的；没有办法把CPU使用权让予另外的等待线程；并且没有方法来创建一个新线程以便管理其它线程。由于这些原因，我们甚至无法验证如何把特定的浏览器事件（例如，按钮点击，可用的XML响应等）指派给线程。

一种克服这些障碍的方法是利用Command设计模式。通过把一个Command对象（连同所有需要初始化该逻辑的数据）放到所有应该在一个临界区中实现的逻辑中，我们就可以把Bakery算法“加工”成一个管理命令的类。只有在其它临界区不执行时，这个互斥类才进行临界区（封装为独立的命令对象方法）调用，好象每个临界区都处于其自己的虚拟线程中。为此，我们使用了JavaScript的setTimeout()机制以便把CPU控制权让予另外的等待命令。
通过定义这些命令对象的一个简单的基类Command（见列表2中的Command），我们可以定义一个新类（见列表3中的Mutex）―由它实现Bakery算法的Wallace改进算法。注意，尽管在JavaScript中存在许多种方法来实现基于类的对象概念(为了紧凑起见，这里采用了一种简单的方法)，但是，任何面向对象设计都可以使用这里所介绍的技术，只要每个Command对象都有一个唯一的id，并且整个临界区被封装进单个方法中。

1 function Command() {
2 if (!Command.NextID) Command.NextID = 0;
3 this.id = ++Command.NextID;
4 //非同步API
5 this.doit = function(){ alert("DOIT called"); }
6 this.undo = function(){ alert("UNDO called"); }
7 this.redo = function(){ this.doit(); }
8 //同步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 }

列表2.包装命令对象的Command类

上面的Command类正好实现了三个临界区方法（第5～7行）；只要一个方法调用包装到一个Mutex对象中（就象第9～11行所示)，那么就可以使用这个方法。应该注意，在正常的方法调用（例如调用非同步方法）和同步方法调用之间的关键区别：具有讽刺意味的是，我们必须假定同步方法不能同步运行。换句话说，当调用sDoIt()时，我们必须假定doit()还没有运行，尽管sDoIt()已经返回。doit()方法可以已经运行结束，或者它再等待一段时间后才启动。也就是说，可以把一个Mutex实例看作是启动一个新线程。

1 function Mutex( cmdObject， methodName ) {
2 //定义静态域和方法
3 if (!Mutex.Wait) Mutex.Wait = new Map();
4 Mutex.SLICE = function( cmdID， startID ) {
5 Mutex.Wait.get(cmdID).attempt( Mutex.Wait.get(startID) );
6 }
7 //定义实例方法
8 this.attempt = function( start ) {
9 for (var j=start; j; j=Mutex.Wait.next(j.c.id)) {
10 if (j.enter
11 || (j.number && (j.number < this.number ||
12 (j.number == this.number
13 && j.c.id < this.c.id))))
14 return setTimeout
15 ("Mutex.SLICE("+this.c.id+"，"+j.c.id+")"，10);
16 }
17 //以互斥存取方式运行
18 this.c[ this.methodID ]();
19 //释放互斥存取权
20 this.number = 0;
21 Mutex.Wait.remove( this.c.id );
22 }
23 //构造器逻辑
24 this.c = cmdObject;
25 this.methodID = methodName;
26 //在此，enter和number都为false
27 Mutex.Wait.add(this.c.id，this );
28 this.enter =true;
29 this.number=(new Date()).getTime();
30 this.enter=false;
31 this.attempt( Mutex.Wait.first() );
32 }

列表3.创建Mutex类来实现Wallace改进算法