JavaScript: a concurrent language with shared mutable state

A little while ago, I saw @jdanbrown tweet the following “OH: ‘So I did a search for “node.js lock”, and then I was like, “I’m dumb”.'”. Now that’s funny–everyone knows that JavaScript’s event-loop concurrency model means that you don’t have the problems of threads with shared memory, locks, deadlocks, data races, etc that you have in languages like C or Java.

Except that’s not right. JavaScript’s concurrency model is cooperative, which means that you don’t get descheduled if you don’t want to be, but everything else about shared memory concurrency is still there. As a demonstration, here’s some shared-memory concurrency in JS:

var x = 1;
setTimeout(function() { x = 2; }, 2);
setTimeout(function() { console.log(x); }, 0);

What value of x gets logged? Well, that depends on when the two different callbacks get inserted into the event queue, just like the semantics of a shared-memory program with threads.

For a more involved example, here’s a lock in JavaScript:

// a lock with exponential backoff

function Lock() {
    this.state = 0;
    return this;
}

Lock.prototype.acquire = function(cb) { 
    var self = this;
    var check = function(N) {
	if (self.state === 0) {
	    self.state = 1;
	    cb(); }
	else { 
	    console.log("backing off to ", 2*N);
	    setTimeout(check,N,2*N);
	}
    }
    setTimeout(check,1,1);
}

Lock.prototype.tryAcquire = function() { 
    if (this.state === 0) {
	this.state = 1;
	return true;
    }
    return false;
}

Lock.prototype.release = function() { this.state = 0; }

This code isn’t perfect (you can release someone else’s lock, for example), but it demonstrates all the relevant issues. Now we can code up dining philosophers:

var N = 5;
var forks = [];
for (var i = 0; i < N; i++) {
    forks.push(new Lock());
}

function deadlock () {
    for (var i = 0; i < 5; i++) {
	console.log("starting philosopher", i);
	forks[i].acquire(function(i){
 	    console.log("philosopher", i, "picked up fork", i);
	    return function() {
		forks[(i+1)%N].acquire(function() {
		    console.log("philosopher ", i, " eating");
		    forks[i].release();
		    forks[(i+1)%N].release();
		})}}(i));
    }
}

Running deadlock() deadlocks in my version of Firefox, just like you’d expect. We can adopt a lock ordering solution, as described in the Wikipedia article:

function work () {
    for (var i = 0; i < 5; i++) {
	console.log("starting philosopher", i);
	var j1 = Math.min(i,(i+1)%N);
	var j2 = Math.max(i,(i+1)%N);
	forks[j1].acquire(function(i,j1,j2){
	    console.log("philosopher", i, "picked up fork", i);
	    return function() {
		forks[j2].acquire(function() {
		    console.log("philosopher ", i, " eating");
		    forks[j2].release();
		    forks[j1].release();
		})}}(i,j1,j2));
    }
}

Most of the time in JavaScript, you don’t need to write locks explicitly like this. However, you shouldn’t think that event-based concurrency eliminates synchronization, or shared memory, or anything other than preemption.

Of course, JavaScript is in good company here: even Erlang (message sending is arbitrarily-ordered mutation of process inboxes, see also Mnesia) and Haskell (the M in MVar stands for “mutable”) are languages with concurrency and shared mutable state.

About these ads
6 comments
  1. gasche said:

    Note that you don’t need shared mutable state to get deadlocks, they can happen purely during synchronization. You can get deadlocks with Erlang without Mnesia, or, trivially, with just any concurrency paradigm where you can block waiting for something to happen.

    Shared mutable state is one way to implement locking, and shared state manipulations often require synchronization, so may introduce deadlocks. Otherwise, I think the main effect of shared mutable state is to make it easy to observe non-determinism, as you noted in your first code example. Deterministic concurrency models are possible when we remove shared state mutation.

    I think the LtU discussion on “The Problem with Threads” touches some of these points:
    http://lambda-the-ultimate.org/node/1481

  2. Lon Ingram said:

    First, great post! I remember the strange look I got the first time I told someone their JS code was racing.

    I do think, however, that it’s worth pointing out that the semantics of setting two timeouts to fire within a short period of time* is “Do these two things, I don’t care which one you do first.” If you care about the order of the two operations, use a setTimeout chain.

    I know this was a contrived example meant to serve your larger point, but wanted to make sure that random google refugees don’t wind up walking away from this post with the impression that locks are the solution to setTimeout non-determinism.

    * Where ‘short period of time’ means close to the minimum timeout the browser supports

    • Right, if you want to do things in sequence, do them in sequence. But if you have a critical section that lasts through more than one event-loop turn, you need to use a lock, or some other synchronization construct.

  3. Event loop concurrency is not vulnerable to deadlock at least, which is very difficult to debug. It is vulnerable to a less insidious variant called “data-lock” wherein a program stops making progress toward a solution but the event loop remains responsive.

    http://www.erights.org/talks/thesis/

    • I disagree with this characterization of deadlock. The Wikipedia article [1] defines it as: “A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does.” This is exactly what is occurring in the dining philosophers code I gave, which is why the post describes it as deadlock.

      The event loop remaining responsive is not an accomplishment — operating systems remain responsive when some of their threads deadlock as well.

      [1] http://en.wikipedia.org/wiki/Deadlock

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.