I&C School of Computer and Communication Sciences
Ecole Polytechnique Fédérale de Lausanne    
   
Another project

Multithreading for Javascript

Claude Petitpierre
Abstract
This page presents a way to execute a multithreaded-like Javascript program in any standard browser. The definition of the processes and their synchronization uses a few new statements based on the theories aimed at the analysis of mutithreaded applications and has thus a sound background. The "processes" are emulated by splitting the execution code of the method that implements the thread into the cases of a switch statement, and having a scheduler call the next case when the event it waits for is ready.
The translation of the processes to standard Javascript is made with the help of a compiler based on Javacc, the source of which is freely available.
Try it now on a simple example!

The kernel offers debugging features

Preliminary remarks

The goal of this approach is not the improvement of performance, which is anyway impossible with a single processor, but to provide an alternative to the event driven or listener based approach. Realtime programming is often seen as a very risky adventure that may lead to the most serious troubles. However, when used correctly, it may be safer than listeners. When using the latter, it is very difficult to determine which operations have already been executed when a new operation is requested and the program must rely on the sequencing performed by the user or on flags spread over all listeners. A process is a sequencial path through a set of statements (a thread!). When it arrives at a some location, it is sure that it has executed the code that leads to this location, but unlike a normal program, it may wait for an event without blocking all the application.

Actually, programs based on listeners/events and programs based on threads can be considered as dual of each other. The translation from one version to the other is called program inversion

Documentation: IEEE Computer article, similar approaches: Wotug database, the sC++ book (English version.ps / with its index), book about Software Engineering

Transparencies

Three Javascript processes: a Generator, a Channel and a Consumer

This example shows three processes. The first one sends parcels to a channel that stores them in a fifo. The second one is the channel itself and the third one is a consumer that gets the parcels, shows them for a little while and finally drops them.

The channel is thus a process (synchronous object in the next section), which makes it easy to introduce the code that displays the parcels located in the fifo into the channel.

Both the generator and the consumer can be stoped and restarted by clicking buttons. These buttons are linked to the real processes by pseudo-processes that control the connection between the two worlds: threads and listeners.

A schema of the application is given below. Here are the files required: compiled code, (its source), page of example, the kernel, an image, a second image and a third one. You can store these files in your Web site and load Plant2.html to run the application.

The development environment is still under development, and currently the do while() loops, the switch and the continue statement are not implemented. Neither is the break label statement. I can give no guarantees on the generated code, but as all the generated code is visible, it is possible to find and correct the errors.

You can use one switch($J_state) at the top level, introduced immediately within the for(;;) loop. If you define one there, the compiler will not generate its own one. You must however take care not to use the same case IDs (ID>10000) as the compiler. Look at the compiled code.

Synchronous Object

First of all, remember that you cannot use local variables in method run, if they must keep their values over a synchronous point. For example, if you use for (i=0; i<n; i++), declare var i as attribute of the object (unless there are no blocking statement inside, but be sure it will not appear later on). See the following explanations. The compiler writes a warning for all local variables it finds in a run method.

The inter-process communication concept is based on method calls, synchronized by select statements that implement the schema of CCS (Calculus of comunicating systems), a theory aimed at the analysis of mutithreaded applications. This approach merges seamlessly the concepts of an object, a thread, and CCS. There is no semaphores, no locks, no mutex, although they could easily be created, but with architectures based on synchronous objects, they are not needed, which eliminates the greatest source of troubles.

The two figures below illustrate two ways of looking at the synchronization of objects. In each figure, two objects run until they arrive at a select statement. In the first figure, we think of the synchronization as a rendezvous between the two objects, which is met as soon as they have both entered their select statement . During the rendezvous, the method of the second object is executed. In the second figure, the first object calls the second object, which may be slow in accepting the call (because it may busy on some other task), but otherwise the call functions exactly as a standard (passive) call. Which view is best depends on what aspects a developer wants to examine.

     

The first case that finds its complement is fired, and like in a switch statement, once a case has been executed, the other ones are discarded. If two cases are ready at the time the program arrives in a select one is selected in an unspecified way.

The trick to replace multithreading

The processes are created as objects with a run() method. The latter method is split by the compiler at every point where the thread is supposed to wait for some event, and each part, spanning from one waiting point to the next one, is stored in the case of a switch statement. A scheduler calls then the cases in the original statement sequence, as soon as the awaited events have occured. The for, the while and the block statements are themselves recursively split if they contain waiting statements.

Although this may seem weird at first, the use of these object-processes is very close to the use of real threads. The only difference is that the run() method cannot use local variables that carry values over several cases, because they are not saved between the calls. However, as there is only one thread per process and the thread never terminates, they would anyway play the same role as the attributes of the object!

A Program

Examples of processes are available in the file.js previously mentioned. The first process defines the channel. It is specified exactly like an object, but with the symbol function replaced by process, which tells the compiler to perform the adaptation required to run it in parallel with the other objects.

The function run contains a for (;;) infinite loop, which is usual for process, as they usually do not terminate. The loop contains a select statement that is converted to standard Javascript by the compiler. The generated code uses this for (;;). The compiler thus checks if it is available and adds it if it is not. It also adds a switch statement within this for (;;) loop. Actually, one could write the program directly in the target language, but it would be cumbersome and not very reliable.

Pseudo-processes: In this same file, Button is a pseudo-process. It starts with symbol process, but it does not contain any run method. The compiler does not include the blocking statements in the select nor in the accept statements of such objects (synchronous calls are forbidden in these objects). It assumes it to be a listener and the synchronization with the caller to occur later (not a rendezvous). Take care, as it may happen that the pseudo-process is called a second time before the previous synchronization offer has been accepted, the pseudo-process must check with

if (this.$J_inSyncList)
    return

that the previous synchronization entry is not in the queue any more, before entering the new accept proposition.

The select is similar to the one used by Ada, which has the same origin, CSP, but Ada's cannot contain calls, which makes a big difference.

All the New Statements

Remember that you cannot use local variables in method run. For example, if you use for (i=0; i<n; i++), declare var i as attribute of the object. (see the following explanations)

Here are examples of the use of the statements offered by synchronous objects. A select can contain several cases (the first case symbol is optional). The first statement of a case must be a trigger statement: either a call to another synchronous object, an accept of a local method or a waituntil. The statements that follow this trigger statement can be of any kind, even a new select statement. If a trigger statement (a synchronous call, an accept or a waituntil) is on its own, it is not necessary to store it in a select statement .

      select {
      case
       b = startStop.clicked() // synchronous call
       ON = !ON
      case
       when (ON) // possible in every case
           waituntil(now()+1000) // only executed when ON is true
      case
           accept method
      }
          . . . 
      waituntil(now()+1000)
          . . . 
      accept localMethod
          . . . 
      syncObj.m(45) // syncObj is a synchronous object
          . . . 
      x[0] = aaa[8].b.meth("sss") // aaa[8].b is resolved to a synchronous object

 

The synchronous statements must be defined within a within run methods inside process blocks. The compiler decide that a single call is synchronous if it finds a method with the same name in any synchronous objects in the file it is compiling. These names must thus be different from the standard methods (for simplification reasons), but two synchronous objects may define the same method names .

The synchronous statements can only be introduced in the run method, not in the methods of a synchronous object.

If a when clause (guard) is placed before the first statement of a case, the case is ignored when the condition of the when is false. The condition is computed only when the select is entered. If it changes later, the select is not reevaluated. This is not a problem, because if the OOP encapsulation rule is respected, an object only accesses the attributes of another object through method calls, and if a guard only depends on local variables, the guard can only change if a method is called, which can only occur if the select has authorized it. All calls thus trigger the select, which automatically recomputes the guards on its next execution.

An example of the function that defines a process (or synchronous object or active object) is shown below. The symbol function has been replaced by process, but otherwise it is a normal function definition. It contains a method called run, without parameters, which will be executed as if it would be running on a thread. The methods of the object can only be called from other synchronous objects and they are only executed when the local run method accept that they be called. The parameter of the function defining the object must have a single parameter, which must receive the name of the process at its instantiation. The instantiation of the object starts its execution.

In order to terminate the execution of a synchronous object, just use a return statement

The calls that are stored in select statements are automatically considered as synchronous calls. The bare calls that are defined within some process in the same file are considered as synchronous calls as well. Thus, if you want to split a program into several files, you could nest the single synchronous calls within select { b = startStop.clicked() }, but it is safer to proceed in the following way, as you could forget to do that for some call. Define a dummy process with an empty run as well as the methods defined in the other files. These methods need no parameters nor bodies, they just tell the compiler that these methods are synchronous.Then compile and import the files independently into your application.
It is possible to have synchronous and usual methods in an object (for example to include the method such as postRequest defined in the last paragraph) by compiling the object, rearranging the resulting code and defining the methods in the aforementioned dummy object. Of course this should be made parsimoniously, for example to create user-friendly libraries.

Synchronous Object Compiler

Last version: 29.7.2010

You may use this page to compile simple synchronous objects.

The compiler is also available as a service on the Web. Follow the indications on this page and you will get the compiled code back in your browser.

The binary of the compiler is available as a jar-file. In order to compile a program containing synchronous objects in your environment, use the following command:

java -jar   SyncCompiler.jar   Plant.sjs

The output is automatically named Plant.js. The produced code is part of an application managed from this html-file. It calls methods defined in kernel.js, and accesses the images: parcel.jpg, pink.jpg and empty.jpg.

Compiling on Eclipse can then be performed by calling compile.xml. Store -Dresource_loc=${resource_loc} -Dworkspace_loc=${workspace_loc} in the argument list and SyncCompiler.jar at the root of the workspace. Note that just after you have edited a .js file, it remains selected. If you then click the package arrow in the menu, it is compiled with a single click (provided you already called the compiler the last time)!

The version of the compiler can be printed by calling (to get the version use -cp and to compile, -jar):

java -cp SyncCompiler.jar Version

Source of the compiler

The source code of the compiler is also available. It is based on Javacc. An introduction to Javacc is available in Software Engineering. Here are all the steps that must be performed to load and call the compiler:

jar xf script.jar
cd script
jjtree Javascript.jjt
javacc Javascript.jj
cd ..
javac -classpath . script/*.java
java -cp . JavascriptMain File.js
  (the main within JavaScript is similar to the one in JavascriptMain, but it prints an unmodified tree and the latter is easier to modify during the development)

The file named OriginalJavascript.jjt in script.jar contains a parser for the standard Javascript, without the select statement. Javascript.jjt includes the synchronous statements. The compiler uses the visitor pattern to implement the new statements. Method childrenAccept of SimpleNode.java calls the current node by jjtAccept(visitor, data);, with visitor defined in SplitStatements.java. This visitor modifies the tokens to split the code that contains synchronous statements. Each node is called once before its children with flag goingDown (down the tree) true and once after its children with the same flag set to false. A preliminary walk through the whole tree is performed with visitor RunSearch.java to determine if the object has a run method or not.

This file available with the sources of the compiler contains some additional information.

The Kernel

The kernel computes and schedules the inter-process synchronizations.

The kernel (web-formatted, 307 lines, current version = 7.12.09) contains three lists defined by function List:

Three variables are of interest: startTime indicates the time at which the whole program has been started (the times stored in the timerList refer to that time), currentThread points to the current thread and lastTimer keeps the id of the timer that is going to starts the scheduler next.

The processes inherit from TaskControlBlock. This subclass contains the list of the calls proposed by the caller and the list of the methods it accepts. It is mainly used in relation with syncList. The compiler inserts calls to method syncWait at the places of the select statements. This method evaluates if the current caller wants to perform a call to a method that is already waiting in this list, in which case the acceptor is extracted from the syncList list and triggered by the caller after it has called the method. If there is no complementary acceptor, the syncWait method checks for an external caller that would call one locallly accepted method, in which case the current process is put on hold, the complementary caller is stored in the ready list and the method returns. If none of these tests is successful, the process is stored in syncList and the scheduler is restarted with the help of the Javascript timer.

More precisely, the syncWait method returns true whenever the process that has called has proposed a call to a ready method, in which case, the execution of the process continues. If there is no further execution possible, it returns false and the process that called it returns and control is passed to function scheduler. This function scans first the readyList and calls method run of the next process, which will execute the case of the main switch indicated in $J_state. If no process is available, it scans the timerList to see if the time of the first process has elapsed, in which case it is executed. If none of these situations is present, the scheduler is restarted by setTimeout after a delay that corresponds to the time at which the next process of the timerList must be reexecuted. If there are no processes in this list no new event is scheduled, and the progam will be restarted by the click on a button. Finally, if there are no such event, the program is deadlocked!

Note that a process is simultaneously present in the syncList and in the timerList in case it has a waituntil statement in a select statement. When it is extracted from one list, it must simultaneously be extracted from the other one if it is present there too.

Debugging

The debug version can display the trace of the last few synchronizations in the HTML element with id "display"

The table below can be cut/pasted from comments in the debug kernel. The latter offers the following features (which you could easily extend or adapt to your needs)

Debugging
Process state, name:
Evaluate expression:
Results...
Another Example: Connection with a Server (In progress)

Test application: http://lti.epfl.ch/AJAX/SynchronousServerCall.html

This application gets data from a server and displays them on the page. It is composed of the following files:

The main process, Tester, loops on the following statements:

process Tester (name) {
  this.run = function() {
    for (;;) {
      startStop.clicked()
      postRequest("GetData", "", serverListener) // create the request (normal call)
      res = serverListener.getData() // wait for the response (could be in a select)
      clearDisplay()
      display(res)
    }
  }
}

postRequest is the AJAX method that handles the connection with the server. It is passive, namely is executed as soon as it is called. This method receives a listener that is used for the synchronization of the process with the response. On the subsequent line, the process waits for the response from the server, which it could do within a select statement have it ready to catch other events (such as a cancel command).

When the response is received, the AJAX object calls a methods in the server listener. This method decodes the data and accepts the call from the process. It is the way the process gets the result. This mechanism could be structured differently, but a listener is required between the method called by the AJAX object and the process.

The servlet should run within Tomcat or JBoss (see our project about J2EE).

 
Lausanne, July 29, 2010