Multithreading in Lua

Question

I was having a discussion with my friend the other day. I was saying how that, in pure Lua, you couldn't build a preemptive multitasking system. He claims you can, because of the following reason:

Both C and Lua have no inbuilt threading libraries [OP's note: well, Lua technically does, but AFAIK it's not useful for our purposes]. Windows, which is written in mostly C(++) has pre-emptive multitasking, which they built from scratch. Therefore, you should be able to do the same in Lua. The big problem i see with that is that the main way preemptive multitasking works (to my knowledge) is that it generates regular interrupts which the manager uses to get control and determine what code it should be working on next. I also don't think Lua has any facility that can do that.

My question is: is it possible to write a pure-Lua library that allows people to have pre-emptive multitasking?

Answer 1

I can't see how to do it, although without a formal semantics of Lua (like the semantics of yield for example), it's really hard to come up with an ironclad argument why it can't be done. (I've been wanting a formal semantics for ages, but evidently Roberto and lhf have better things to do.)

If I wanted pre-emptive multitasking for Lua, I wouldn't even try to do it in pure Lua. Instead I'd use an old trick I first saw 20 years ago in Standard ML of New Jersey:

• Interrupt sets a flag in the lua_State saying "current coroutine has been preempted".

• Alter the VM so that on every loop and every function call, it checks the flag and yields if necessary.

This patch would be easy to write and easy to maintain. It doesn't solve the problem of the long-running C function that can't be pre-empted, but if you have to solve that problem, you are wandering into much harder territory, and you may as well do all your threading at the C level, not the Lua level.

Answer 2

Not that I know of, no. It would almost be absurdly simple if you could yield from hooks set on coroutines with debug.sethook though, but it doesn't work. You can yield from C hooks set from C (lua_sethook), but I couldn't figure out exactly to do that, and it's not pure Lua anyways.

Even if it were possible, it wouldn't be true threading. Everything would still run within the same operating system thread, for example. Your hook would take a variety of factors into account (such as time, perhaps memory, etc.) and then determine whether to yield. The yielded-to coroutine then would decide which child coroutine to run next. You'd also need to decide on when the hook should be called. Most frequent would be on every Lua instruction, but that carries a performance penalty. And if the coroutine calls into a C function, Lua has no jurisdiction. If that C call takes a long time, there's nothing you can do about it.

Here's a related thread from the Lua-L mailing list which you might find interesting.

Answer 3

No. It's not possible to write a preemptive scheduler in pure Lua. At some point a preemptive scheduler needs some mechanism like an interrupt service routine to take control away from the current thread and give it to the scheduler which can then give it to another thread. Pure Lua doesn't have this mechanism.

You mention that Windows is written in mostly C/C++. The keyword is mostly. You can't write a preemptive scheduler in pure ANSI C/C++. Usually, part of the interrupt service routine is written in assembly language. Or, the C/C++ compiler implements a non-standard extension that allows interrupt service routines to be written in C/C++. Some compilers allow you to declare a functions with an __interrupt modifier that that causes the compiler to generate a prolong / epilog that allows the function to be used as an interrupt service routine.

Also, code that sets up the interrupt service routine fiddles with CPU registers with memory mapped IO, or a IO instructions. None of this code is portable ANSI C/C++. And, depends on the CPU architecture.