Wednesday, October 25, 2006

JavaScript in IE is not Multithreaded

After coding up my mutex and experimenting with it, I've discovered that Internet Explorer isn't multi-threaded. Instead, it has something worse. Much, much worse.

In any case, here's my mutex code:


function Mutex(maxThreads)
{
// This mutex is based on the paper "Tight Bounds for Shared Memory Symmetric
// Mutual Exclusion Problems" by Eugene Styer and Gary L. Peterson.
if (maxThreads < 2)
alert('Mutex is configured incorrectly');
this.waiting = new Array(maxThreads);
this.locks = new Array(maxThreads);
for (var n = 0; n < maxThreads; n++)
{
this.waiting[n] = null;
this.locks[n] = null;
}
this.maxThreads = maxThreads;
this.whoInCriticalSection = null;
this.turn = null;
this.get_visible = function(level, retry, me) { // This is private
if (level == -1)
{
this.waiting[0] = me;
level = 0;
retry = true;
}
else if (this.waiting[level] != me)
{
// Don't write if we can make progress
if (this.turn != me)
{
if (retry)
{
// Assume mistake, once
retry = false;
}
else
{
level = level + 1;
retry = true;
}
// Make visible again
this.waiting[level] = me;
}
}
return [level, retry];
}
this.enter = function() {
var me = new Object(); // generate a unique id for this thread
var level = -1;
var retry = false;
while (true)
{
// See if lock is available, or if it assigned to me
while (this.turn != null && this.turn != me)
{
var ret = this.get_visible(level, retry, me);
level = ret[0];
retry = ret[1];
}
this.turn = me;
var locked;
while (true)
{
// Try to get all locks
for (var pos = 0; pos < this.maxThreads; pos++)
{
if (this.locks[pos] == null)
this.locks[pos] = me;
}
// Do we have all the locks?
locked = true;
for (var pos = 0; pos < this.maxThreads; pos++)
{
if (this.locks[pos] != me)
locked = false;
}
if (this.turn != me locked) break;
}
if (this.turn != me)
{
// Lost, release locks
for (var pos = 0; pos < this.maxThreads; pos++)
{
if (this.locks[pos] == me)
this.locks[pos] = null;
}
var ret = this.get_visible(level, retry, me);
level = ret[0];
retry = ret[1];
}
else
{
break;
}
}
// Acquired lock
if (this.level > -1 && this.waiting[this.level] == me)
this.waiting[this.level] = null;
this.whoInCriticalSection = me; // Save our id for later
}
this.leave = function() {
var me = this.whoInCriticalSection; // Get our saved id
this.whoInCriticalSection = null;
// Find ID of top waitier or 0 if nobody
var next = null;
for (var pos = this.maxThreads - 1; pos >= 0; pos--)
{
if (this.waiting[pos] != null) {
alert('handoff');
next = this.waiting[pos];
break;
}
}
// Let them continue, release locks
this.turn = next;
for (var pos = 0; pos < this.maxThreads; pos++)
{
if (this.locks[pos] == me)
this.locks[pos] = null;
}
}
}
So back to the original point. In the end, JavaScript in Internet Explorer isn't multi-threaded. There's only one thread, but it can be interrupted by callbacks or signals, and the thread won't regain control until after the signal/callback handler completes.

So if you look at this chunk of JavaScript code
var image = new Image();
image.onload = function() {
alert('a0');
alert('a1');
};
image.src = 'blank.gif';
alert('0');
alert('1');

you'll notice that the alerts you get are for a0, a1, 0, and then 1. The onload callback does not give up control back to the main thread until after it finishes giving its two alerts. This means that mutexes and critical sections can't be used in JavaScript because if one thread is inside a critical section and becomes interrupted, the other thread cannot yield to the other thread to let it exit its critical section. So basically, you can't use locks or critical sections or other standard programming techniques to protect important parts of code.

I don't know what the best way to fix this is. It's just messy...very, very messy.

Monday, October 23, 2006

JavaScript Mutexes 2

Actually, I started thinking some more about symmetric mutual exclusion, and I realize that I was actually mistaken. You don't actually need to use any randomization. Although in a real system, the only way to generate unique thread ids would be to use randomization, JavaScript does have one operation that is guaranteed to generate unique keys--just use new to create a new Object since new is atomic. You can then use this object as your thread id. And since it's an object, JavaScript will automatically take care of cleaning it away once you're finished with it.

So, in conclusion, JavaScript mutexes are possible if you use a shared memory symmetric mutual exclusion algorithm and if you are able to put a bound on the number of threads that may attempt to enter a mutex at any one time. This is the best approach to the problem. There are no unacceptable trade-offs that need to be taken into account (beyond the whole messiness of needing to implement your own mutexes in JavaScript in the first place).

Mutual Exclusion in JavaScript

I started reading up on some papers, and I've found that the type of mutual exclusion being attempted by Wallace in JavaScript is actually impossible. Totally anonymous mutual exclusion using atomic RW registers cannot be done.

That leaves two choice:

1. One can hand-out thread ids in advance (i.e. assign one to each possible callback) during a stage when one knows the code will have only one thread running

2. Use randomized mutual exclusion algorithms

Personally, I think option #1 is very hard to implement correctly, so option #2 is probably the most feasible. Basically, you randomly generate a thread id for yourself at any time (in fact, you can randomly generate a thread id every time you want to enter a mutex). Then, you can run a symmetric mutual exclusion protocol using atomic RW registers.

I found a paper that seems to give one such algorithm:

"Tight Bounds for Shared Memory Symmetric Mutual Exclusion Problems" by Eugene Styer and Gary L. Peterson.

Thursday, October 19, 2006

JavaScript is Multi-Threaded

I was doing some JavaScript programming where I hooked a bunch of image onload() callbacks with functions that would generate alerts, when I noticed that various alerts were firing before I had finished hooking up all my callbacks. This caused me a lot of consternation. JavaScript does not come with any threading primitives. As such, it's very hard to do any synchronization. Yet clearly, my version of Internet Explorer was triggering these callbacks asynchronously, in threads other than my main thread, resulting in various race conditions in my code.

Firefox seems to use a more sensible model. It seems like it has only one JavaScript thread (much like the single UI thread in most GUI systems), and asynchronous events queue up and are only fired when your JavaScript thread isn't doing anything (of course, that's brings up the other problem of the fact that Firefox seems to discard events if too many get queued up--but at least that's easier to handle than race conditions).

I went looking around for various mutex code to solve this problem, but nothing seems quite right. Some Bruce Wallace person created a JavaScript version of mutex, but I don't have much confidence in it. First of all, he replaced a fixed size array from Lamport's Bakery algorithm with a Map. The whole point of the fixed size array was that you could perform atomic reads and writes on it--a reasonable assumption. Once you use a Map, you're assuming atomic adds, atomic removes, and atomic iteration, which are much larger assumptions. In any case, if you had an atomic add operation, then you wouldn't need to implement the Bakery algorithm because you could use atomic add to create a mutex. His assignment of thread ids also has a race condition in it. I suppose I could just assign a separate thread id to each callback in advance, thereby avoiding the race condition, but if I did that, then I wouldn't need this Map nonsense and I could use a fixed size array because I would know how many threads there are in advance.

Instead, I simply reshaped my code so as to minimize the race condition to an atomic increment instruction. It seems unsatisfactory though. Personally, I think JavaScript should not be multi-threaded, but if it is multi-threaded, they should at least supply something like Array atomic_add() and atomic_remove() methods so that users at least have the proper primitives available for building synchronization primitives. And I'm not sure whether JavaScript engines are themselves thread-safe. I know that Mozilla's Rhino claims that it is thread-safe (I vaguely remember them stating that get and put operations were atomic), but I don't know about the engines in FireFox and IE.

Update 2011-3-31: I was going through my blog stats for the first time, and I noticed that people seem to read this post occasionally. This is an old blog post, and I explore the situation in more detail in later blog posts. Actually, JavaScript is NOT multi-threaded. In IE6, you do get some weird non-sequential behaviour, but that's due to nested asynchronous callbacks.