This AJAX from Scratch series of articles describes fundamental techniques needed to develop AJAX Rich Internet Applications in JavaScript from scratch. Each article focuses on a particular (usually little-covered) aspect of developing browser-side functionality without the use of commercial or server-based frameworks. The techniques described are additionally illustrated in Gravy, a small, but real-world, example JavaScript library and application.
Introduction
Any time there are multiple threads8 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 sections5, and the practice of letting only one run at a time is known as mutual exclusion4. This situation arises in AJAX applications when the code, asynchronously handling the reply from an XMLHttpRequest17, manipulates data that is also being used by the user interface code. This common data could be JavaScript variables implementing an MVC15 data model and/or the DOM16 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 (also known as race conditions7), so they don't always (or even ever) occur. They are probabilistic based on a number of factors. To be robust, Rich Internet Applications2 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. Although 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 such as Internet Explorer. The classic algorithm that follows then will be 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 algorithm6 works for multiple competing threads of control when the only communication between them is shared memory (in other words, no special mechanisms such as semaphores, atomic set-and-test, and so forth 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 Listing 1; 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 }
Listing 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"; in other words, 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 particular browser events (for example, button-click, XML-reply-available) are assigned to threads.
An approach that overcomes these obstacles springboards off the Command design pattern9. By putting all the logic that should go into a critical section into a command object, along with all 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) to implement the Wallace variation of the Bakery algorithm. Note that, while there are many approaches to implement 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 }
Listing 2. Simple base class for Command objects
The Command class happens to demonstrate three critical section methods (lines 5-7), but any method be 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 }
Listing 3. The Wallace variation implemented as the class Mutex
IE 7
Firefox 2.0
