This paper presents implementation of the original Lamport's Bakery algorithm [1] in JavaScript language. Our goal was to implement clear and simple rewrite of the original pseudo-code [1] to JavaScript, with maximum stress to similarity. With this in mind, the algorithm can be verified using the original proof of correctness [1]. We also provide test case showing that "synchronization" may be necessary in certain browsers and our bakery implementation can be used as possible solution. We believe that implemented solution is much more elegant, readable and correct than the existing Wallace variation [2] widelly spread in the web.
/**
generate rundom number C
increment top.shared variable C times,
decrement top.shared variable C times
value of top.shared should be the same before and after the method was stared.
**/
function longTaskUnsafe(window,strMethod)
{
var c=Math.random()* 10000;
top.Log.append(window,"S "+strMethod+" longTask:"+top.shared);
for(var i=0;i<c;i++)
{
top.shared++;
}
for(var i=0;i<c;i++)
{
top.shared--;
}
top.Log.append(window,"E "+strMethod+" longTask:"+top.shared);
}
Let's have FRAMESET containing 5 FRAMEs. Each FRAME loads page with onload event handler h2(),
plus FRAMESET itself has onload handler h1 defined.
0 ?f1 : S h2 longTask:0
36 ?f1 : E h2 longTask:0
38 ?f2 : S h2 longTask:0
44 ?f2 : E h2 longTask:0
46 ?f3 : S h2 longTask:0
47 ?f3 : E h2 longTask:0
49 ?f4 : S h2 longTask:0
174 ?f4 : E h2 longTask:0
182 ?f5 : S h2 longTask:0
182 ?f5 : E h2 longTask:0
182 ?fs : S h1 longTask:0
255 ?fs : E h1 longTask:0
Now, let's introduce window.confirm between increment and decrement parts of the function:
function longTaskUnsafe(window,strMethod)
{
var c=Math.random()* 10000;
top.Log.append(window,"S "+strMethod+" longTask:"+top.shared);
for(var i=0;i<c;i++)
{
top.shared++;
}
window.confirm(location.search+":"+strMethod);
for(var i=0;i<c;i++)
{
top.shared--;
}
top.Log.append(window,"E "+strMethod+" longTask:"+top.shared);
}
This, introduces interesting results in some browsers:
0 ?f1 : S h2 longTask:0
24 ?f2 : S h2 longTask:2043
80 ?f3 : S h2 longTask:8850
123 ?f4 : S h2 longTask:13941
156 ?f5 : S h2 longTask:17602
1534 ?f5 : E h2 longTask:17602
1862 ?f4 : E h2 longTask:13941
2112 ?f3 : E h2 longTask:8850
2294 ?f2 : E h2 longTask:2043
2443 ?f1 : E h2 longTask:0
2444 ?fs : S h1 longTask:0
2629 ?fs : E h1 longTask:0
Log shows, that while h2() in frame f1 was waiting for confirm,
browser started execution of h2() in different frame f2. Which started with non zero value (proving that f1.h2() has not finished yet).
Conclusion: Let's have two function f() and f'(). Under "certain circumstances", f'() can start execution even if f() has not finished yet.
We believe, this observation (with none explanation) can be used as motivation to implement mutual exclusion implementation at the level of JavaScript functions.
Bakery.js code, creates synchronization mechanism, that allows us to turn original functions f,f' into synchronized functions. Synchronized in this context means, that if "f synchronized over bakery instance b" is running, no other f' synchronized over the same bakery instance b will run. Second function f' will wait until there is no other synchronized method over b running. This is achieved by defering the execution of second function f' using setTimeout.
Critical sections of original algorithm are represented by whole functions f and f'. Processes are rougly represented by logical threads, executing the method.
Gained effect is similar to synchronized methods in Java language, with explicit synchronization over specific monitor b (this is just for illustration, we have not reached the semantics of synchronized in Java).
There are several ways to register a handler, and several types of functions used as handlers.
Sample shows some of the combinations and challenges to be solved, when making function synchronized.
In short, if the original handler was passed certain arguments and was called with certain context this,
the same arguments and this context must be available in synchronized handler.
Our style emphases nondestructive coding, which means
we try to keep the original functions intact, create synchronized wrappers
and change handler registration from original function to synchronized version.
// before:
function f1(obj,arg1,arg2)
{
Log.append(window,"f1:"+obj.nodeName+","+arg1+","+arg2);
}
<img id="img1" width=100 height=100 src="sample.png" onload="f1(this,'a1','a2');">
// after:
var f1s=b.createSynchronizedDelegate(f1);
<img id="img1" width=100 height=100 src="sample.png" onload="f1s(this,'a1','a2');">
That was demonstration of old style (DHTML) registration where user enters the name
of handler with optional parameters as part of the HTML structure.
Newer approaches uses onload property (traditional) or addEventListener DOM API to register handler.
In the second case, the scoping and this must be kept.
// before
<img id="img2" width=100 height=100 src="sample.png">
<script>
(function()
{
var scope="s1";
function f2()
{
Log.append(window,"f2:"+this.nodeName+","+scope);
}
document.getElementById("img2").onload=f2;
})();
// after
// note that this can be done outside of original f2 scope
document.getElementById("img2").onload=b.createSynchronizedDelegate(
document.getElementById("img2").onload);
As seen, our Bakery.js implementation allows to concert existing code regardless on the registration or handler type without change to the original methods code and with minimal lines of extra code required.
Of course, when writing new code from scratch, selected methods can be easily defined as synchronized without exposing the unsafe function.
Note: We limited the scope to functions without return value. Which is typical to hanlers and is not considered an issue.
Call to bakery.createSynchronizedDelegate takes reference to original function originalFunction, and returns reference to new function newFunction. This new function should be used as new event handler. When creating the newFunction,"process" is registered with bakery, but without performing "choosing phase". When newFunction is called for the first time by browser (event occured), the "choosing" phase executes,original context (this) and arguments (args) are stored. Waiting loop is encapsulated by attemp function defined inside the scope of newFunction which means it can access that,args and j variables. Finally call to newFunction also executes attempt(). Attempt itself performes checks labeled L2 and L3 in the original pseodo-code. If those are not satisfied, attemp defers itself with setTimeout and exists. If l2 is satisfied it is marked as done, and attemt defered again to perform L3 check. Next "defered loop" does not check for L2 again. When both L2+l3 are satisfied for j, j is incremented (L2 flag cleared), and loop is repeated for next j. When all values of j are checked, original method is called by applying original context (that) and arguments (args). Critical section is left.
// modified version with choosing in creation or first call
// introduced parameter explicitNumber
// allows user to specify explicit number, not 1+max number generated by bakery.
Bakery.prototype.createSynchronizedDelegate=function(originalFunction,explicitNumber)
{
var b=this;
var i=b.choosing.length;
b.choosing[i]=0;
b.number[i]=0;
if(explicitNumber!=null) //extra optional choosing block in creation
{
b.choosing[i]=1;
b.number[i]=explicitNumber;
b.choosing[i]=0;
}
function newFunction()
{
// store original context and params of method call
var that=this;
var args=Array.prototype.slice.call(arguments);
if(explicitNumber==null) // if chosen in creation, skip
{
// original choosing block in run
b.choosing[i]=1;
b.number[i]=1+Math.max.apply(null,b.number);
b.choosing[i]=0;
}
.....
0 ?f4 : S h2 longTask:0
968 ?fs : S h1 longTask:178
1703 ?fs : E h1 longTask:178
2203 ?f4 : E h2 longTask:0
2250 ?f5 : S h2 longTask:0
2718 ?f5 : E h2 longTask:0
2718 ?f1 : S h2 longTask:0
3203 ?f1 : E h2 longTask:0
3203 ?f2 : S h2 longTask:0
3625 ?f2 : E h2 longTask:0
3687 ?f3 : S h2 longTask:0
4047 ?f3 : E h2 longTask:0
Both handlers synchronized
0 ?f1 : S h2 longTask:0
1282 ?f1 : E h2 longTask:0
1282 ?f2 : S h2 longTask:0
1688 ?f2 : E h2 longTask:0
1688 ?f3 : S h2 longTask:0
2047 ?f3 : E h2 longTask:0
2047 ?f4 : S h2 longTask:0
2454 ?f4 : E h2 longTask:0
2469 ?f5 : S h2 longTask:0
2797 ?f5 : E h2 longTask:0
2797 ?fs : S h1 longTask:0
3204 ?fs : E h1 longTask:0