Lightweight concurrency

This page contains information about the design, implementation, problems and potential solutions for building user-level concurrency primitives in GHC.

Introdution

All of GHC's concurrency primitives are written in C code and is baked in as a part of the RTS. This precludes extensibility as well as making it difficult to maintain. Ideally, the concurrency libraries will be implemented completely in Haskell code, over a small subset of primitive operations provided by the RTS. This will provide a Haskell programmer the ability to build custom schedulers and concurrency libraries. For an earlier attempt at this problem, please look at Peng Li's paper [1].

Substrate primitives

Substrate primitives are the primitives exposed by the RTS, on top of which user-level concurreny libraries are built.

data PTM a -- Primitive transactional memory
instance Monad PTM
unsafeIOToPTM :: IO a -> PTM a
atomically :: PTM a -> IO a

data PVar a -- Primitive transactional variable
newPVar :: a -> PTM (PVar a)
newPVarIO :: a -> IO (PVar a)
readPVar :: PVar a -> PTM a
writePVar :: PVar a -> a -> PTM ()

data SCont -- One-shot continuations
data ThreadStatus = Blocked | Completed -- | Running. Running is set implicitly.
newSCont :: IO () -> IO SCont
switch   :: (SCont -> PTM (SCont, ThreadStatus)) -> IO ()
{- For switch, target thread's status must be Blocked. Otherwise, raises runtime error. 
 - After switching, target thread's status is implicitly set to Running, and current 
 - thread's status is set to ThreadStatus that was passed.
 -}
getSCont :: PTM SCont
switchTo :: SCont -> ThreadStatus -> PTM ()

Concurrency libraries

In order to support the construction of extensible user-level schedulers in GHC, special care has to be taken about blocking concurrency actions. When there is no default scheduler, the user-level scheduler must be made aware of the blocking action, and more interestingly, the blocking action of the user-level scheduler.

Motivation

The interaction between user-level schedulers and blocking actions is motivated through actions on MVars.The semantics of takeMVar is to block the calling thread if the MVar is empty, and eventually unblock and return the value when the MVar becomes full. Internally, when a thread blocks on an MVar, it switches to the next runnable thread. This assumes that the takeMVar has knowledge about the scheduler. In particular, the current implementation of takeMVar knows how to perform the following:

• Block action: blocking the current thread on a condition, and switching to another runnable thread.
• Unblock action: placing the unblocked thread back into the scheduler data structure.

Proposal

The new, scheduler agnostic version of takeMVar (say takeMVarPrim), will have the type:

takeMVarPrim :: PTM () -> PTM () -> MVarPrim a -> IO a

where the first and second arguments are the block and unblock actions. If the blocking and unblocking actions are known, takeMVar with its usual type can be obtained simply by partial application:

takeMVar :: MVarPrim a -> IO a
takeMVar = takeMVarPrim blockAct unblockAct

Since the MVar implementation is independent of the schedulers, even threads from different schedulers can perform operations on the same MVar. The knowledge of schedulers is completely embedded in the block and unblock actions. A typical implementation of blockAct and unblockAct for a scheduler might look like

data Scheduler

getBlockUnblockPair :: Scheduler -> (PTM (), PTM ())
getBlockUnblockPair sched = do
  thread <- Substrate.getSCont
  let blockAction = do {
    nextThread <- -- get next thread to run from sched
    switchTo nextThread Substrate.Blocked
  }
  let unblockAction = -- enque thread to sched
  return (blockAction, unblockAction)

Interaction with RTS

In the current GHC implementation, runtime manages the threading system entirely. By moving the threading system to the user-level, several subtle interactions between the threads and the RTS have to be handled differently. This section goes into details of such interactions, lists the issues and potential solutions.

Interaction with GC

In the vanilla GHC implementation, each capability maintains a list of runnable Haskell threads. Each generation in the GC also maintains a list of threads belonging to that generation. At the end of generational collection, threads that survive are promoted to the next generation. Whenever a new thread is created, it is added to generation0's thread list. During a GC, threads are classified into three categories:

• Runnable threads: Threads that are on the runnable queues. These are considered to be GC roots.
• Reachable threads: Threads that are reachable from runnable threads. These threads might be blocked on MVars, STM actions, etc., complete or killed.
• Unreachable threads: Threads that are unreachable. Unreachable threads might be blocked, complete or killed.

At the end of a GC, all unreachable threads that are blocked are prepared with BlockedIndefinitely exception and added to their capability's run queue. Note that complete and killed reachable threads survive a collection along with runnable threads, since asynchronous exceptions can still be invoked on them.

In the lightweight concurrency implementation, each capability has just a single runnable thread. Each generation still maintains a list of threads belonging to that generation. During a GC, threads are classified into reachable and unreachable. RTS knows whether a thread is blocked or complete since this is made explicit in the switch primitive.

Problem

In the LWC implementation, since there is no notion of a runnable queue of threads for a capability, how do we raise BlockedIndefinitely exception?

Proposal

Let us first assume each thread has its blockAction and unblockAction saved on the TSO structure, such that RTS can pick it off the TSO structure and evaluate it. Secondly, We need to distinguish between BlockedOnMVar and BlockedOnScheduler.

Blocked on an unreachable MVar

If the MVar is unreachable, the scheduler might still be reachable, and some runnable thread is potentially waiting pull work off this scheduler. Hence, we can prepare the blocked thread for raising the asynchronous exception as we do in the vanilla implementation. Subsequently, RTS evaluates the blocked threads unblock action, which enqueues the blocked thread on its scheduler. Thus, we can raise BlockedIndefinitelyOnMVar exception.

Blocked on a unreachable scheduler

If a thread is blocked on an unreachable scheduler, we need to find a scheduler for this thread to execute. We might fall back to the current solution here, which is to prepare the blocked thread for asynchronous exception and add it to the current capability's queue of threads blocked on scheduler. At the end of GC, RTS first raises BlockedIndefinitelyOnScheduler exception on all the threads blocked on scheduler, and finally switches to the actual computation (current thread).

Notes

• What is the type of TSO->blockAction and TSO->unblockAction? In the user-level block and unblock actions are of type PTM (). RTS versions of the actions should be IO () so that we can utilize RTS functions for evaluating IO () for evaluating the scheduler actions.
• RTS version of scheduler actions should be traced by the GC.

Bound threads

Bound threads [2] are bound to operating system threads (tasks), and only the task to which the haskell thread is bound to can run it. Under vanilla GHC, every capability has a pool of tasks (workers), only one of which can own the capability at any give time. Ideally, there is one-to-one mapping between capabilities and cores. If the next Haskell thread to be run is a bound thread, and if the bound thread is bound to:

• the current task, run it.
• a task belonging to the current capability, add the thread to the front of the run queue, and pass the current capability to the bound thread's task (which is currently suspended). This suspends the current task, and wakes up the target task.
• a task belonging to a different capability, add the thread to that capability's run queue, and switch to next task.

Problem

Under lightweight concurrency implementation, the first two cases can be handled just like in the vanilla implementation. For the last case, since there is no notion of run queues per capability, we are stuck.

Proposal (Partial)

Expose the notion of boundedness to the programmer and put the onus on the programmer to not switch to a bound thread that belongs to a different capability. Additional substrate primitives would be,

newBoundSCont :: IO () -> IO SCont -- new SCont will be bound to the current capability

data Capability deriving Eq
getMyCapability :: IO Capability
getCapability :: SCont -> IO Capability

On scheduler which could potentially hold bound threads, programmer can check whether it is safe to run the next thread. If the bound thread belongs to a different capability, we put it back into the scheduler, with the hope that it will be picked up by the capability to which the SCont is bound to. The solution is partial since we don't know if there are schedulers running on the correct capability, which will pick up the bound thread. Or, is it programmer's responsibility to make sure all the threads that were created on the scheduler are run to completion?

Safe foreign calls

A safe foreign calls does not impede the execution of other Haskell threads on the same scheduler, if the foreign call blocks, unlike unsafe foreign calls. A safe foreign call is typically more expensive than its unsafe counterpart since it potentially involves switching between Haskell threads. At the very least, a safe foreign call involves releasing and re-acquiring capability.

Anatomy of a safe foreign call

Every capability, among other things, has a list of tasks (returning_tasks) that have completed their safe foreign call. The following are the steps involved in invoking a safe foreign call:

• Before the foreign call, release the current capability to another worker task.
• Perform the foreign call.
• Add the current task to returning_tasks list.
• Reacquire the capability.
• Resume execution of Haskell thread.

The first action performed by the worker task that acquired the capability is to check if returning_tasks is not empty. If so, the worker yields the capability to the first task in the returning_task list (fast path). Otherwise, the worker proceeds to run the next task from the run queue (slow path). Thus, in the fast path, the haskell thread never switches.

Problem

In the LWC implementation, the worker does not have the reference to the scheduler to pick the next task from. And for the same reason, when the task returns from the foreign call, it needs to know what to do with the Haskell thread, whether to switch to it (fast path) or add it to the scheduler data structure, to which it does not have a reference to. Even if the RTS had a reference to the scheduler data structure, it must be implemented in such a way that it is operable by both C and Haskell code.

Proposal

Rather than manipulating the scheduler, we might build on top of solutions for implementing concurreny primitives. In particular, for a safe foreign call, let us assume RTS has references to block and unblock actions for the thread making the foreign call. The steps involved in a safe foreign call would be:

• Before the foreign call, release the current capability to a worker, along with the blockAction.
• Perform the foreign call.
• Add the current task to returning_tasks list.
• Reacquire the capability.
• If I am on the fast path (i.e, worker did not get to executing blockAction), resume execution of Haskell thread.
• Otherwise (slow path), execute unblockAction to enque the Haskell thread to the scheduler.

At the worker:

• Try to acquire the capability.
• If the returning_tasks list is not empty, yield capability to the task from the head of the list (fast path).
• Otherwise (slow path), execute the blockAction, which will switch control to the next Haskell thread.