Cooperative Multithreading

Multithreading is the capacity to execute simultaneously multiple executions independently from each other. This feature is essential in distributed systems for many reasons. For example, threads can be used to service different clients requesting the same service independently, so they do not interfere with each other. In this section, we present the multithreading support of OiL and how it is used.

Coroutines

Lua does not provide standard support for multithreading. However, it provides the concept of coroutines, which can be used to implement a cooperative multithreading infrastructure. Unlike preemptive multithreading, as provided by Java or POSIX Threads, the execution switch between threads does not occur automatically. Instead the code executed by the coroutine must explicitly signal for execution switch by invocation of operation coroutine.yield().

Lua coroutines are created by operation coroutine.create(function). The function passed as parameter is the code executed by the coroutine. Every time the coroutine executes function coroutine.yield() the coroutine yields the execution to the function that initiated its execution by calling operation coroutine.resume(coroutine). For further information about Lua coroutines, check the chapter on Coroutines of the book Programming in Lua

Scheduler

Coroutines provide means to create independent execution threads, however it is up to the application to manage the execution of these threads. To perform this management, OiL uses a coroutine scheduler. The scheduler keeps a collection of all the threads of the system. These threads are then scheduled for execution, in such way that whenever a coroutine yields its execution, the scheduler chooses another coroutine for execution following a round-robin algorithm.

Since the coroutine scheduler is not part of the standard virtual machine of Lua, it must be created and started by the application. This can be done by operation oil.main(mainbody) that creates and initiates the execution of the scheduler with a single thread registered that executes the function mainbody provided as parameter. After this operations is called, other threads can be created with operation oil.newthread(function, ...) that register new coroutines to execute the function informed as the first parameter, and starts its execution immediately. The scheduler also provides other operations to register or unregister as described here.

Synchronization

Cooperative multithreading is far more simple to understand and use. For example, the implementation of synchronization mechanisms is far more simple to be implemented. In OiL, to implement these mechanisms, we use only operations oil.tasks:suspend() and oil.tasks:resume(thread, ...) provided by the scheduler as illustrated in the example below.

To implement mutual exclusion between a set of cooperative threads that access a shared resource, we can use global variables or other shared memory space to indicate when a thread is using the shared resource and also to register the threads waiting for their turn to use the resource. For example, consider the following implementation.

local Mutex = { waiting = {} }
  
function Mutex:enter()
  local thread = oil.tasks.current
  if self.inside then
    self.waiting[thread] = true
    oil.tasks:suspend()
  else
    self.inside = thread
  end
end

function Mutex:leave()
  assert(self.inside == oil.tasks.current)
  local waiting = next(self.waiting)
  if waiting then
    self.waiting[waiting] = nil
    self.inside = waiting
    oil.tasks:resume(waiting)
  else
    self.inside = nil
  end
end

A similar approach can be used to provide other synchronization mechanisms to common problems like Producers and Consumers

Limitations

The multithreading model used by OiL presents two strong limitations. The first one is due to a limitation of the coroutines in Lua, which cannot yield execution inside some special places, like metamethods, for interators or C functions exported to Lua. A particular case for this is that coroutines cannot yield execution inside a pcall(function, ...). Therefore, you usually cannot invoke a remote operation inside such functions because OiL will most likely generate an yield to allow other threads to execute while it waits for the reply of the remote invocation. To alleviate the problem of the pcall function, OiL provides the alternative implementation oil.pcall(function, ...), which can be used inside threads.

The other limitation is that the thread scheduler is not integrated to the underlying operating system. Therefore, any blocking system call performed by a thread will eventually suspend the execution of the application as a whole since the coroutine does not yield the execution back to the scheduler. This is particularly true for file operations that suspend the entire execution of the application regardless of the number of other independent threads that might be ready to execute. For socket operations in particular, OiL provides a cooperative API similar to the one provided by LuaSocket, as described here. This cooperative socket API is provided by field oil.tasks.sockets.

Copyright (C) 2004-2008 Tecgraf, PUC-Rio

This project is currently being maintained by Tecgraf at PUC-Rio.