<<Title>>

Implementing Mutual Exclusion for AJAX
How to keep your XMLHttpRequests from colliding with your Rich Internet Application

<<Author>>

Bruce Wallace
President, PolyGlot, Inc.
http://www.PolyGlotInc.com/
bruce.wallace@acm.org

<<Abstract>>

With the increasingly popular AJAX paradigm_[1], a browser page can make requests for server data “in the background” while the user interface continues to be active “in the foreground” (hence the Asynchronous in AJAX). However, the problem exists that these two activities are typically accessing common JavaScript and DOM data structures simultaneously. The classic solutions to this concurrent programming_[3] problem are not supplied by JavaScript. This article describes an implementation of a mutual exclusion_[4] mechanism that works around the limitations of JavaScript as implemented in modern browsers.

<<Body>>

Any time there are multiple threads_[8] of program logic that access the same data, and execute at the same time, problems arise. Programs normally assume that the data with which they are interacting is not changing underneath them. The portions of code that access these shared data structures are known as critical sections_[5], and the practice of only letting one run at a time is known as mutual exclusion_[4]. This situation arises in AJAX applications when the code, asynchronously handling the reply from an XMLHttpRequest, manipulates data that is also being used by the user interface code. This common data could be JavaScript variables implementing an MVC_[15] data model and/or the DOM_[16] of the web page itself. The logic of each will break if either is making uncoordinated changes to shared data.

“Wait”, you say, “why haven’t I run into this problem?” Unfortunately, these kinds of problems are timing dependent (a.k.a. race conditions_[7]), so, they don’t always (or even ever) occur. They are probabilistic based on a number of factors. To be robust, Rich Internet Applications_[2] need to prevent this situation thus insuring that these problems can’t occur.

So, a mutual exclusion mechanism is needed to ensure that only one critical section will start and finish before another is started. In most mainstream computer languages and execution frameworks, there are (often several) mutual exclusion mechanisms provided, but alas, not in browser-side JavaScript. While there are classic algorithms that implement mutual exclusion without requiring special support from the language or environment, even these expect some basics that are missing from JavaScript and browsers like Internet Explorer. The solution presented in this article implements one of these classic algorithms that has been adapted to work around these browser and language limitations.

The Bakery Algorithm

Of the several mutual exclusion algorithms in the computer science literature, one known as Lamport's bakery algorithm_[6] works for multiple competing threads of control when the only communication between them is shared memory (i.e. no special mechanisms like semaphores, atomic set-and-test, etc. are required). The metaphor for this algorithm is a bakery that requires customers to take a number and wait till their number is called. The skeleton of the algorithm is in Fig. 1 and it enables each thread to go into and out of critical sections without conflict.

// declaration and initial values of global variables
0 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))”
1 Thread(i) {
2   while (true) {
3     Enter[i] = 1;
4     Number[i] = 1 + max(Number[1], ..., Number[N]);
5     Enter[i] = 0;
6     for (j = 1; j <= N; j++) {
7       while (Enter[j] != 0) {
8         // wait until thread j receives its number
9       }
10       while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) {
11         // wait until threads with smaller numbers or with the same
12         // number, but with higher priority, finish their work
13       }
14    }
15     // critical section...
16     Number[i] = 0;
17     // non-critical section...
18   }
19 }
Figure 1. Lamport’s Bakery Algorithm pseudocode (from Wikipedia)

As shown, the algorithm assumes that each thread knows its own thread number (constant i) and how many total threads are currently active (constant N). It also assumes that there is a way to “wait” or “sleep”; i.e. a way to give up control of the CPU to other threads temporarily. Unfortunately, JavaScript on Internet Explorer doesn’t have any of these capabilities. However, the Bakery algorithm doesn’t break if multiple portions of code running on the same actual thread pretend that each is running on a separate virtual thread. Also, JavaScript does have a mechanism to schedule a function to run after some specified delay, so, the Bakery algorithm can be finessed to use these alternatives.

The Wallace Variation

The major obstacle to implementing Lamport’s Bakery algorithm in JavaScript is that there is no Thread API. So, 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 a particular browser assigns events (e.g. button-click, XML-reply-available) to threads.

An approach that overcomes these obstacles springboards off the Command design pattern_[9]. By putting into a command object all the logic that should go into a critical section, along with all the data needed to initiate that logic, the Bakery algorithm can be reworked into a class that manages commands. This class will invoke specified methods of specified command objects only when other critical sections are not executing, as if each command 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 Fig. 2), a class can be defined (Mutex in Fig. 3) which 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 number, and entire critical sections are encapsulated in single methods.

1 function Command() {
2   if (!Command.NextID) Command.NextID = 0; //define class variable
3   this.id = ++Command.NextID;              //define instance variable
4   // unsynchronized API
5   this.doit = function(){ alert("DOIT called"); /*override me*/ }
6   this.undo = function(){ alert("UNDO called"); /*override me*/ }
7   this.redo = function(){ this.doit();          /*override me*/ }
8   // synchronized API
9   this.syncDoIt = function(){ new Mutex(this,"doit"); }
10   this.syncUnDo = function(){ new Mutex(this,"undo"); }
11   this.syncReDo = function(){ new Mutex(this,"redo"); }
12 }
Figure 2. Simple base class for Command objects

The Command class happens to demonstrate three critical section methods (lines 5-7), but any method can used as long as its invocation is wrapped in a Mutex object (as in lines 9-11). NOTE: A key difference between normal method calls (such as invoking the methods defined in lines 5-7) and “synchronized” method calls is that, ironically, one must assume that synchronized methods are NOT run synchronously. In other words, when syncDoIt() is called, one must assume that doit() has not run yet even though syncDoIt() 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 variable 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 || (j.number && (j.number < this.number ||
11            (j.number == this.number && j.c.id < this.c.id) ) ) )
12        return setTimeout("Mutex.SLICE("+this.c.id+","+j.c.id+")",10);
13     }
14     this.c[ this.methodID ](); //run with exclusive access
15     this.number = 0;           //release exclusive access
16     Mutex.Wait.remove( this.c.id );
17   }
18   // constructor logic
19   this.c        = cmdObject;
20   this.methodID = methodName;
21   Mutex.Wait.add( this.c.id, this ); //enter and number are “false”
22   this.enter    = true;
23   this.number   = (new Date()).getTime();
24   this.enter    = false;
25   this.attempt( Mutex.Wait.first() );
26 }
Figure 3. The 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, and so setTimeout is used to schedule a new attempt that starts where the current attempt has left off. When the head has been reached (at line 14), 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 15-16).

The Mutex constructor (lines 19-25) records its Command object and method name parameters and then registers itself into a sparse array of critical-sections-in-progress (Mutex.Wait) which is implemented via the Map class shown in Fig. 4. It then gets the “next number” and starts waiting at the end of the line. Since there is not a problem with gaps or duplicates in the wait numbers, the current timestamp is actually used as the “next” number.

The attempt() method combines the two wait loops in the original pseudocode into a single loop that doesn’t fall thru to line 14 until it is at the head of the line. This loop is a form of busy-wait polling_[11] which can be throttled by the amount of delay specified in the setTimeout() call on line 12. Since setTimeout requires a “flat function” to be called rather than an object method, a static helper method (Mutex.SLICE) is defined in lines 4-6. SLICE locates the specified Mutex object in the master wait list and calls its attempt() method with the start parameter specifying how far thru the wait list it has gotten so far. Each SLICE() call is like getting a “slice of CPU”. This cooperative approach_[13] of yielding the CPU (via setTimeout) is reminiscent of coroutines_[14].

1 function Map() {
2   this.map = new Object();
3   // Map API
4   this.add     = function(k,o){ this.map[k] = o;    }
5   this.remove = function( k ){ delete this.map[k]; }
6   this.get     = function( k ){ return k==null ? null : this.map[k]; }
7   this.first   = function(   ){ return this.get( this.nextKey( ) ); }
8   this.next    = function( k ){ return this.get( this.nextKey(k) ); }
9   this.nextKey = function( k ){ for (i in this.map) {
10                                   if (!k) return i;
11                                   if (k==i) k=null; /*tricky*/
12                                 }
13                                 return null;
14                               }
15 }
Figure 4. A sparse array implemented as a Map data structure

Rich Internet Application Integration

Since Mutex handles a dynamic number of threads (virtual or not), one can get around the fact that an actual thread ID isn't known, by acting as if the browser assigns a separate thread to each browser event. A similar simplifying assumption is that each complete event handler constitutes a complete critical section. Given these, each event handler function can be converted into a command object, and Mutex used to invoke and manage them. Of course, if the code is not already cleanly organized into event handling functions then refactoring will be needed. I.E. Rather than logic being encoded directly in HTML event attributes (e.g. onclick='++var'), define and invoke event handling functions (onclick='FOO()' and function FOO(){++var;}).

1 <html>
2 <script language="JavaScript">
3 function RequestData(){
4    ...set up asynchronous XML request...
5    XMLreq.ondataavailable    = ProcessReply;
6    XMLreq.onreadystatechange = NewState;
7    ...launch XML request...
8 }
9 function ProcessReply(){
10    var transformedData = ...process received data into HTML...
11    OutputArea.innerHTML = transformedData + "<br>";
12 }
13 function ClearArea(){ OutputArea.innerHTML = "cleared<br>"; }
14 function NewState (){ if (XMLreq.readyState==4) ProcessReply(); }
15 </script>
16 <body onload="RequestData();">
17   <input type="button" value="clear" onclick="ClearArea()">
18   <div id="OutputArea"/>
19 </body>
20 </html>
Figure 5. Example web page with unsynchronized event handlers

For example, suppose there are three event handler functions that manipulate common data as shown in Fig. 5. They handle a page-load event, a button-clicked event and a reply-received-from-XML-request event. The page-load event handler launches some asynchronous request for data. It specifies the request-reply event handler which processes the received data and loads it into a common data structure. The button-click handler also affects the common data structure. To keep these event handlers from conflicting, they can be converted to commands and invoked via Mutex as shown in Fig. 6. [Assume that Map and Mutex are contained in the JavaScript include file mutex.js.] Note that, while elegant class inheritance mechanisms can be used to implement Command subclasses, this code illustrates the other end of the spectrum, requiring only the global variable NEXT_CMD_ID.

1 <html>
2 <script src="mutex.js"></script>
3 <script language="JavaScript">
4   function RequestData (){ new Mutex(new RequestDataCmd(),"go"); }
5   function ProcessReply(){ new Mutex(new ProcessReplyCmd(),"go"); }
6   function ClearArea   (){ new Mutex(new    ClearAreaCmd(),"go"); }
7   function NewState    (){ if (XMLreq.readyState==4) ProcessReply(); }
8   var NEXT_CMD_ID = 0;
9   function RequestDataCmd(){ this.id = ++NEXT_CMD_ID;
10     this.go = function(){
11       ...set up asynchronous XML request...
12       XMLreq.ondataavailable    = ProcessReply;
13       XMLreq.onreadystatechange = NewState;
14      ...launch XML request...
15    }
16 }
17 function ProcessReplyCmd(){ this.id = ++NEXT_CMD_ID;
18    this.go = function(){
19      var transformedData = ...process received data into HTML...
20      OutputArea.innerHTML = transformedData + "<br>";
21    }
22 }
23 function ClearAreaCmd(){ this.id = ++NEXT_CMD_ID;
24    this.go = function(){ OutputArea.innerHTML = "cleared<br>"; }
25 }
26</script>
27<body onload="RequestData();">
28 <input type="button" value="clear" onclick="ClearArea()">
29 <div id="OutputArea"/>
30</body>
31</html>
Figure 6. Web page converted to synchronized event handlers

The three event handler functions have been changed to invoke their original logic (which has been wrapped in command classes) via Mutex. The command classes define a unique ID and a method containing the critical section logic, thus fulfilling the command interface requirements.

Conclusion

With AJAX and RIA, the impetus to build complicated dynamic user interfaces is driving developers to use the same design patterns (e.g. Model-View-Controller) formerly tied to "fat" GUI clients. With Views and Controllers being defined modularly, each with their own events and event handlers, but sharing common data models, the potential for conflicts explode. By encapsulating logic into Command classes, not only can the Wallace variation be employed, but the stage is also set to provide rich undo/redo functionality and cleanly separate event handling logic from HTML tags.

<<Examples>>

An example JavaScript framework (known as Gravy) that uses the MVC, AJAX, and Undo/Redo techniques mentioned in this article, is located at http://www.polyglotinc.com/Gravy/ complete with JsDoc documentation. It can be viewed and/or downloaded from there. Gravy supports placing all application functionality in the (IE6) browser in JavaScript. Applications need only access the server for REST-style_[12] requests for data CRUD_[10] operations.

<<References>>

1. http://en.wikipedia.org/wiki/AJAX

2. http://en.wikipedia.org/wiki/Rich_Internet_Application

3. http://en.wikipedia.org/wiki/Concurrent_programming

4. http://en.wikipedia.org/wiki/Mutual_exclusion

5. http://en.wikipedia.org/wiki/Critical_section

6. http://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm

7. http://en.wikipedia.org/wiki/Race_condition

8. http://en.wikipedia.org/wiki/Thread_%28computer_science%29

9. http://en.wikipedia.org/wiki/Command_pattern

10. http://en.wikipedia.org/wiki/CRUD_%28acronym%29

11. http://en.wikipedia.org/wiki/Busy_wait

12. http://en.wikipedia.org/wiki/Representational_State_Transfer

13. http://en.wikipedia.org/wiki/Cooperative_multitasking

14. http://en.wikipedia.org/wiki/Coroutines

15. http://en.wikipedia.org/wiki/Model-view-controller

16. http://en.wikipedia.org/wiki/Document_Object_Model

<<About the Author>>

As principal consultant of PolyGlot, Inc., Bruce Wallace has provided consulting and custom computer software development services around the world. Projects have been completed in Sydney Australia, Perth West Australia, "Silicon Valley", "Route 128" MA, Austin TX, Atlanta GA, and Charlotte NC.