The major obstacle to implementing Lamport's bakery algorithm in JavaScript is that there is no thread API. There is no way to know on which thread one is running, or how many threads are active; no way to yield the CPU to other threads; and no way to create a new thread to manage other threads. Because of this, one cannot even verify how particular browser events (e.g., button click, XML reply available) are assigned to threads.
An approach that overcomes these obstacles springboards off of the Command design pattern. By putting into a command object all of the logic that should go into a critical section, along with all of the data needed to initiate that logic, the bakery algorithm can be reworked into a class that manages commands. This mutual exclusion class will invoke critical sections (encapsulated as separate command object methods) only when other critical sections are not executing, as if each were in its own virtual thread. JavaScript's setTimeout() mechanism is used to yield the CPU to other waiting commands.
Given a simple base class for command objects (Command in Listing 2), a class can be defined (Mutex in Listing 3) that implements the Wallace variation of the bakery algorithm. Note that, while there are many approaches to implementing class-based objects in JavaScript (and for compactness, a simple approach is used here), any object scheme will work with this technique as long as each command object has some unique id, and entire critical sections are encapsulated in single methods.
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 }
Listing 2. Simple base class for Command objects
The Command class happens to demonstrate three critical section methods (lines 5-7), but any method can be used as long as its invocation is wrapped in a Mutex object (as in lines 9-11). It's important to note a key difference between normal method calls (such as invoking the unsynchronized methods) and synchronized method calls: ironically, one must assume that synchronized methods are not run synchronously. In other words, when sDoIt() is called, one must assume that doit() has not run yet, even though sDoIt() has returned. The doit() method may have finished, or it may not even start until some arbitrary time in the future. In still other words, think of a Mutex instantiation as starting a new thread.
1 function Mutex( cmdObject, methodName ) {
2 // define static field and method
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 // define instance method
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 //run with exclusive access
18 this.c[ this.methodID ]();
19 //release exclusive access
20 this.number = 0;
21 Mutex.Wait.remove( this.c.id );
22 }
23 // constructor logic
24 this.c = cmdObject;
25 this.methodID = methodName;
26 //(enter and number are "false" here)
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 }
Listing 3. Wallace variation implemented as the class Mutex
The basic logic of the Mutex class is to place each new Mutex instance into a master wait list and start it waiting in line. Each attempt (until the final one) to get to the "head of the line" requires waiting, so setTimeout is used to schedule each new attempt which starts where the current attempt has left off. When the head has been reached (at line 17), exclusive access has been achieved; therefore, the critical section method can be invoked. When the critical section is done, exclusive access is released and the Mutex instance is removed from the wait list (lines 20-21).