ParrotTheory: Green Threads
02 Jun 2010This summer I'm mentoring GSoC student Chandon in his project to bring Hybrid Threads to Parrot. Today I'm going to talk a little bit about that, and maybe give some information about what Parrot needs to do to properly support a full and robust threading system in the long term. I've written about threads previously on this blog, so I won't cover all the nitty-gritty details again.
At the risk of over simplicity there are basically two types of threads to consider: OS Threads and Green Threads. OS Threads or "native threads" are what most people are probably familiar with: These are the threads managed by your operating system kernel. Native threads represent a flow of execution of native machine code on a single processor core, and multiple native threads can run simultaneously on multiple processor cores. On a single core, they run sequentially but in time slices so short it appears to the human observer that things are happening at the same time. This appearance of simultaneity is extremely important for computer users, especially for graphical interfaces, because people don't like waiting and don't like it when the computer "freezes" or "locks up" during periods of heavy computation.
A native thread represents a system context: A separate call stack and a snapshot of the processor state at any given time. By saving the processor state and call stack away, we can switch to a different task and later resume our original task as if nothing has happened.
I don't know where they were originated, although Green Threads were probably most famously implemented in early versions of the JVM. Instead of being managed by the OS, they are managed by the VM. Green threads are scheduled onto OS threads in the same way that OS threads are scheduled onto processor hardware. The VM saves it's current state into a VM context object, moves to a different task, and then reinvokes that context object to resume the original task.
Green threads are very interesting tools, when they are available. They tend to be extremely inexpensive compared to native OS threads. They are managed by the VM, and if they all execute sequentially on a single OS thread the risk of lock contention and data corruption drops almost to zero. The down-side to green threads is that they are all multiplexed onto a single OS thread, so they each get a smaller share of the processor's time.
To help enforce that green threads in the VM may only execute on a single OS thread at a time, the VM may implement a global interpreter lock (GIL). Famous examples of this occur in Python and Ruby. A GIL helps with integration to C libraries which are not thread-safe, and also helps to prevent things like callback functions from executing in a different OS thread and causing unprotected data corruption. The downside to the GIL approach is that extra overhead must be spent to perform locking/unlocking and checking of the GIL.
Chandon's Hybrid Threads idea tries to combine the two models of OS and Green threads. Parrot will maintain a pool of OS "worker" threads, based on user settings and the number of available processor cores. Parrot will then be able to schedule a queue of green threads onto the available OS threads. Yesterday on his blog he actually posted an example of using Parrot's existing continuations to form a system of cooperative green threads. Instead of happening at any time, green thread switches in his example are manually triggered by calling the functon th_resched(). If we move the call to th_resched into the interpreter's scheduler object so it can be called when the scheduler runs, we gain a proper preemptive green threads system without too much effort.
There are some difficulties with this model, especially since Parrot currently has no mechanism to manage data contention across OS threads, and also considering that each OS thread ill have it's own interpreter object, which will need to be created at some runtime expense. Parrot is also going to need to add new mechanisms and policies for dealing with data which is considered "global": namespaces and class definition metaobjects, etc.
We're also going to need to start answering some very difficult questions: If a continuation created in interpreter A is passed to interpreter B and invoked, what do we do? If an exception is thrown by interpreter A and is caught by a handler defined in interpreter B, what do we do? If an object's vtable override is preempted by a green thread switch and the object is in an inconsistent state when it is attempted to be accessed in a different green thread, what do we do? How do we even detect when any of these things happen? What mechanism are we going to need to write to allow sharing PMCs between OS threads? Do we use STM again? If so, do we write STM ourselves or try to use a pre-existing and proven library? Considering that we now have immutable strings (which don't need to be locked because they can't be written), do we maybe want to consider a system where shared PMCs are either read-only in other threads or maybe are COW to prevent corruption? How do we deal with long-running operations, such as blocking IO and calls to long-running library functions?
For Chandon's project to be a success I think we need just two things: a robust green threads system, and a prototype OS threads system with a scheduler that can intelligently assign green threads to OS threads. Once we have that system in place, along with some rules or algorithms against sharing writable data until we sort out the details for how that becomes possible, we can add new mechanisms piece-wise to enable new features and functionality. If he has time sure he can do more, but if we can get the basics in place we will be in a much better state than we were before he started.
This entry was originally posted on Blogger and was automatically converted. There may be some broken links and other errors due to the conversion. Please let me know about any serious problems.