Implementing Mutual Exclusion for AJAX

With the increasingly popular AJAX paradigm, 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 problem are not supplied by JavaScript. This article describes the author's new adaptation of a proven mutual exclusion mechanism that works around the limitations of JavaScript.

Why Mutual Exclusion?

Any time there are multiple threads 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, and the practice of only letting one run at a time is known as mutual exclusion. 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 data model and/or the DOM 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), so they don't always (or even ever) occur. They are probabilistic based on a number of factors. To be robust, rich internet applications need to prevent this situation by ensuring 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 classic algorithm that follows will then 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 algorithm 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 until their number is called. The skeleton of the algorithm (from Wikipedia) is in Listing 1 and it enables each thread to go into and out of critical sections without conflict.

// 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...

  }

}

Listing 1. Lamport's bakery algorithm pseudocode

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.