occasional threading in lua

["Russ Cox" <rsc@...>]

I like Lua's coroutine model a lot.
But sometimes you just need to run on multiple CPUs.
I couldn't find any interfaces that were very satisfying.
In particular, I don't want to give up the simplicity of
cooperative scheduling.  I'd like to be able to have certain
C calls run in parallel with the VM, but otherwise keep
the VM single-threaded.  So I can offload I/O and computation
into these parallel C calls but keep the usual Lua model.

 static int luaT_sleep (lua_State *L) {
   int i = luaL_checkint(L, 1);
   luaT_vm_unlock(L);
   sleep(i);
   luaT_vm_lock(L);
   return 0;
 }

While sleep is executing some other pthread is taking care of
running the other coroutines in the Lua VM.

The new pthreads that are allocated as necessary run the global
Lua function "scheduler", which is expected to find a coroutine
waiting to run, run one, and repeat.  If scheduler runs out of coroutines
to run, it returns and the pthread goes away.

Given a simple scheduler like:

 runqueue = { }

 function ready(co)
   table.insert(runqueue, co)
 end

 function scheduler()
   while 1 do
     local co = table.remove(runqueue, 1)
     if co then
       coroutine.resume(co)
     else
       return
     end
   end
 end

a program that runs two coroutines each calling sleep is:

 function sleepy()
   thread.sleep(1)
   while 1 do
     print("sleepy")
     thread.sleep(2)
   end
 end

 function dopey()
   while 1 do
     print("dopey")
     thread.sleep(2)
   end
 end

 ready(coroutine.create(sleepy))
 dopey()

This program ends up using just two pthreads.

A variation is:

 function sleepy()
   thread.sleep(1)
   print("sleepy")
 end

 function dopey()
   while 1 do
     print("dopey")
     ready(coroutine.create(sleepy))
     thread.sleep(2)
   end
 end

 dopey()

This one ends up using a lot of pthreads
in sequence, but only ever two at a time.

The C implementation of the thread module is below.
Note that *nothing* in the rest of the Lua interpreter
had to change (except that I added luaopen_thread to
the table in linit.c), so making this a loadable module
should be straightforward.

I'd be happy to hear comments or suggestions for even
simpler ways to accomplish this.

Russ


/* Written by Russ Cox, November 2006 */

#include "lua.h"
#include "lauxlib.h"
#include "lualib.h"
#include "ldebug.h"
#include "lthread.h"
#include <pthread.h>
#include <unistd.h> // for sleep

static pthread_mutex_t vm_mutex = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t sched_mutex = PTHREAD_MUTEX_INITIALIZER;
static int vm_waiting;
static void *luaT_scheduler(void*);

static int luaT_sleep (lua_State *L) {
 int i = luaL_checkint(L, 1);
 luaT_vm_unlock(L);
 sleep(i);
 luaT_vm_lock(L);
 return 0;
}

static const luaL_Reg t_funcs[] = {
 {"sleep", luaT_sleep},
 {NULL, NULL},
};

static void settable(lua_State *L, void *v) {
 lua_pushlightuserdata(L, &vm_mutex);
 lua_gettable(L, LUA_REGISTRYINDEX);
 lua_pushlightuserdata(L, v);
 lua_pushvalue(L, -3);
 lua_settable(L, -3);
 lua_pop(L, 2);
}

/*
* Initialize tlua.
*/
LUALIB_API int luaopen_thread(lua_State *L) {
 /* Create table of running VM threads. */
 lua_pushlightuserdata(L, &vm_mutex);
 lua_newtable(L);
 lua_settable(L, LUA_REGISTRYINDEX);
 luaT_vm_lock(L);
 luaL_register(L, LUA_THREADLIBNAME, t_funcs);
 return 0;
}

/*
* Grab exclusive use of the Lua VM.
*/
LUAI_FUNC void luaT_vm_lock (lua_State *L) {
 pthread_mutex_lock(&vm_mutex);
}

/*
* Release exclusive use of the Lua VM,
* in order to do some long-running operation
* like a big computation or I/O.
* The calling coroutine will be paused
* during the operation but a new Lua instance
* will be started if needed so that other
* coroutines can continue to run.
*/
LUAI_FUNC void luaT_vm_unlock (lua_State *L) {
 pthread_t pid;
 lua_State *new_vm = 0;

 pthread_mutex_lock(&sched_mutex);
 if (vm_waiting == 0) {
   vm_waiting++;
   new_vm = lua_newthread(L);
   settable(L, new_vm);	/* save thread to avoid GC */
 }
 pthread_mutex_unlock(&sched_mutex);
 pthread_mutex_unlock(&vm_mutex);
 if (new_vm) {
   if(pthread_create(&pid, 0, luaT_scheduler, new_vm) < 0)
     luaG_runerror(new_vm, "failed to create new vm thread");
 }
}

static int traceback (lua_State *L) {
 lua_getfield(L, LUA_GLOBALSINDEX, "debug");
 if (!lua_istable(L, -1)) {
   lua_pop(L, 1);
   return 1;
 }
 lua_getfield(L, -1, "traceback");
 if (!lua_isfunction(L, -1)) {
   lua_pop(L, 2);
   return 1;
 }
 lua_pushvalue(L, 1);  /* pass error message */
 lua_pushinteger(L, 2);  /* skip this function and traceback */
 lua_call(L, 2, 1);  /* call debug.traceback */
 return 1;
}

static void *luaT_scheduler (void *v) {
 lua_State *L = v;
 luaT_vm_lock(L);
 pthread_mutex_lock(&sched_mutex);
 vm_waiting--;
 pthread_mutex_unlock(&sched_mutex);

 lua_pushcfunction(L, traceback);

 lua_pushliteral(L, "scheduler");
 lua_gettable(L, LUA_GLOBALSINDEX);

 if (lua_isfunction(L, -1)) {
   lua_pcall(L, 0, 0, 1);
 }

 /*
  * Scheduler returned: there are no coroutines
  * left to run.  Could sleep here and get woken up
  * by luaT_vm_unlock, but for now it is simpler just
  * to have this pthread exit.  If another one is needed
  * it will be created as necessary.
  */

 /* pop everything off stack */
 lua_pop(L, lua_gettop(L));

 /*
  * remove reference to L - is it safe if we
  * are the ones to remove the last reference
  * to ourselves?  if not, could save the lua_States
  * in a cache and reuse them.
  */
 lua_pushnil(L);
 settable(L, L);

 pthread_mutex_unlock(&vm_mutex);
 return 0;
}