Cours gratuit: Exploring lua for concurrent programming

Introduction

Regardless of its growing importance, concurrent programming is still mostly based on dated models. Constructions like semaphores [Dijkstra 1983], conditional critical regions [Hoare 1972], guards [Dijkstra 1975], and monitors [Hansen1974, Hoare 1973] were all originally designed for operating systems and are ad-mittedly complex for higher-level programming. Moreover, they do not scale well for massive concurrency. This scenario has stimulated the proposal of alternative models and constructions for concurrent programming, such as Erlang [Arm- strong 1996], Polyphonic C# [Benton, Cardelli and Fournet 2002], Sequential.

Concurrent Programming in Lua

Programming with preemptive multithreading and shared memory demands synchronization constructions to ensure mutual exclusion and conditional synchronization [Andrews and Schneider 1983]. Unfortunately, the synchronization burden, the difficulty to debug code, and the lack of determinism during execution make development with preemptive multithreading and shared memory admittedly complex [Lee 2006].
Moreover, as argued by Ousterhout [Ousterhout 1996], the criticism of multithreading is not limited to development complexity. It is often difficult to obtaingood performance when using preemptive multithreading with sharedmemory. A too coarse locking reduces the opportunities for concurrency, while a fine-grained locking may add too much overhead to the program.

Model Implementation

In its standard configuration, Lua includes concurrent programming support through the use of coroutines. Each coroutine represents a different execution flow in user space. Execution control relies on a cooperative model and can be accomplished through calls to thecoroutine.yieldandcoroutine.resumefunctions. Calls to thecoroutine.yieldfunction suspend the coroutine’s execution, while calls to thecoroutine.resumeresume it. Once a coroutine starts running, it runs until it finishes or yields.
The API that Lua offers to C includes a function to create coroutines, as well as functions to suspend and resume their execution. This facility, allied to the flexibility offered by the API for interaction with the Lua interpreter from C code and to the dissociation between coroutines and kernel threads, makes Lua particularly well suited for the exploration of our chosen model for concurrent programming.

Lua Processes
Using Lua code from within C code is normally preceded by the creation of a Lua state, represented in C by a variable of type luaState. A Lua state defines the interpreter’s state and keeps track of functions and global variables, among other information related to the interpreter.
Once Lua code has been loaded in a Lua state, it is possible to control its execution through functions provided by the C API for Lua. Control takes place as if the Lua code was executed as a coroutine. Therefore, even if the Lua code does not include explicit calls to Lua’s standard coroutine handling functions, it is possible to suspend and resume its execution through C functions. This feature is essential to allow control over Lua processes execution.

Scheduler
The scheduler is automatically initialized when our concurrent programming library is loaded. During its initialization, which occurs in the context of the operating system thread responsible for executing the code that loads our library, a worker is created. he scheduler manages a single ready queue (FIFO), which holds Lua processes ready for execution. The scheduler itself is responsible for adding newly created Lua processes to the end of the ready queue. Workers execute the Lua code associated with each Lua process.

Inter-process Communication
Lua uses a virtual stack to pass values to and from C. Each element in this stack represents a Lua value. Calls from Lua to functions implemented in C use the virtual stack to pass function arguments. Likewise, these C functions use the virtual stack to pass results back to Lua. Therefore, passing messages in our library simply implies copying data from the sender’s virtual stack to the receiver’s virtual stack.

Blocking Strategy
In our library, a Lua process can only have its execution blocked in two distinct situations:
1. when it calls the blocking receive function with a channel where there are no processes waiting to send, that is, when an attempt to receive a mes
sage occurs without a previous corresponding attempt to send to the same channel.
2. when it calls the send function with a channel where there are no processes waiting to receive, that is, when an attempt to send a message occurs without a previous corresponding attempt to receive from the same channel.

….