... | ... | @@ -27,14 +27,12 @@ Although implementing concurrency primitives as a library is hardly a novel idea |
|
|
|
|
|
For the high-level design principle for the current scheduler, see [ Scheduler](http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Scheduler).
|
|
|
|
|
|
## Design
|
|
|
|
|
|
### Concurrency Substrate
|
|
|
## Concurrency Substrate
|
|
|
|
|
|
|
|
|
The idea of the concurrency substrate is to provide a minimal set of primitives over which a variety of user-level concurrency libraries can be implemented. As such, the concurrency substrate must provide a way to create threads, a way to schedule them, and a synchronization mechanism in a multiprocessor context. Whereas, the Creation and maintenance of schedulers and concurrent data structures is the task of the concurrency library. Concurrency substrate resides at libraries/base/LwConc/Substrate.hs.
|
|
|
|
|
|
#### PTM
|
|
|
### PTM
|
|
|
|
|
|
|
|
|
The only synchronization mechanism exposed by the concurrency substrate is a primitive transactional memory (PTM). Locks and condition variables can be notoriously difficult to use, especially in an environment with user-level threads, where they tend to interfere with the scheduler. Moreover, they do not compose elegantly with lazy evaluation. PTM interface is shown below:
|
... | ... | @@ -53,7 +51,7 @@ atomically :: PTM a -> IO a |
|
|
|
|
|
A PTM transaction may allocate, read and write transactional variables of type `PVar a`. It is important to notice that PTM does not provide a blocking `retry` mechanism. Such a blocking action needs to interact with the scheduler, to block the current thread and resume another thread. We will see [later](lightweight-concurrency#) how to allow such interactions while not imposing any restriction on the structure of the schedulers.
|
|
|
|
|
|
#### One-shot continuations
|
|
|
### One-shot continuations
|
|
|
|
|
|
|
|
|
The concurrency substrate enables creation and scheduling of I/O-performing computations through *one-shot continuations*. An SCont (stack continuation) is a suspended I/O computation, which is in fact just a reference to a TSO object. Capturing the current continuation is just getting a reference to the current TSO, and hence is very fast. SCont interface is shown below:
|
... | ... | @@ -70,15 +68,56 @@ switchTo :: SCont -> PTM |
|
|
Given an I/O-performing computation `newSCont` returns a reference to an SCont which when scheduled, will perform the I/O action. The switch primitive is a bit unique. Switch takes a function which is applied to the current continuation. The result of the function is PTM transaction of type PTM SCont. This transaction can encapsulate the actions necessary for appending the current SCont to the scheduler and fetching the next SCont to switch to. The switch primitive performs this transaction atomically, and switches control to the resultant SCont.
|
|
|
|
|
|
|
|
|
Performing the body of switch atomically in a transaction avoids the nasty race conditions usually seen in multicore runtimes where one-shot continuations are used for modelling schedulers. In such systems, there are often cases where before the switch primitive has had a chance to return, another processor picks up the current continuation (appended to the scheduler) and tries to switch to it. It becomes necessary to go for complicated solutions such as releasing the scheduler locks after the target thread resumes execution to prevent races. In our case, PTM eliminates the need for such a mechanism - the other processor would not be able to access the current SCont, unless the transaction has committed and control has switched to the target SCont.
|
|
|
Performing the body of switch atomically in a transaction avoids the nasty race conditions usually seen in multicore runtimes where one-shot continuations are used for modelling schedulers. In such systems, there are often cases where before the switch primitive has had a chance to return, another processor picks up the current continuation (appended to the scheduler) and tries to switch to it. It becomes necessary to go for complicated solutions such as releasing the scheduler locks after the target thread resumes execution to prevent races. In our case, PTM eliminates the need for such a mechanism - the other processor would not be able to access the current SCont, unless the transaction has committed and control has switched to the target SCont. Primitive `getCurrentSCont` returns a reference to the current SCont under PTM. Primitive `switchTo` commits the current PTM transaction and switches to the given SCont. As we will see, these two primitives are necessary for [abstracting the scheduler](lightweight-concurrency#abstracting-the-scheduler).
|
|
|
|
|
|
#### Return value of a switching transaction
|
|
|
|
|
|
|
|
|
Since switchTo eagerly commits the transaction, the code that follows switchTo is not evaluated. This is a problem if the transaction that contains switchTo has a type different than PTM (). Consider the following code:
|
|
|
|
|
|
```wiki
|
|
|
s :: String <- atomically $ do {
|
|
|
sc <- getCurrentSCont;
|
|
|
-- save the current SCont somewhere
|
|
|
switchTo someSCont;
|
|
|
return "This is never evaluated!"
|
|
|
}
|
|
|
print s
|
|
|
```
|
|
|
|
|
|
|
|
|
The type of the transaction that contains switchTo is PTM string, and atomically performing the transaction is expected to return a String value. But the value returned when the current SCont resumes execution (after switchTo) is a (). Our solution is to make switchTo return a `error "Attempting to use return value of a switched transaction"`, and any attempt to use the return value of a switching transaction throws a runtime error.
|
|
|
|
|
|
### SCont Status
|
|
|
|
|
|
|
|
|
Of course, care must be taken to ensure that the control does not switch to an SCont that is either running, blocked on an MVar, or completed. But how do we know whether the given SCont is ready to run? We expect the scheduler writer or library implementer to indicate the status of SCont before switching. SCont status API is show below.
|
|
|
|
|
|
```wiki
|
|
|
data SContStatus = SContRunning | -- SCont is currently running
|
|
|
SContKilled | -- SCont was killed by an (asynchronous) exception
|
|
|
SContSwitched SContSwitchReason
|
|
|
data SContSwitchReason = Yielded | -- SCont has yielded, but runnable
|
|
|
BlockedInHaskell | -- SCont is blocked on a user-level concurrent data structure (MVars and such)
|
|
|
BlockedInRTS | -- SCont is blocked on a foreign call, blackhole, etc,.
|
|
|
Completed -- SCont has run to completion
|
|
|
|
|
|
setSContSwitchReason :: SContSwitchReason -> PTM ()
|
|
|
getSContStatus :: SCont -> PTM SContStatus
|
|
|
```
|
|
|
|
|
|
|
|
|
Any attempt to switch to an SCont with status other than `SContSwitched Yielded` throws an exception. Primitive `setSContSwitchReason` updates the status of current SCont. This prevents the programmer from modifying the status of other SConts. Since setSContSwitchReason is a PTM action, the effect of updating the status takes place when the transaction commits and the control has switched to another SCont. This avoids any race conditions that might be involved in reading the status of an SCont before it has switched.
|
|
|
|
|
|
|
|
|
Before a switch operation, we expect the programmer to indicate the reason for switching through setScontSwitchReason. Exception is raised by the switch primitives if a switch reason has not been provided. When a switched SCont resumes execution, its status is automatically updated to `SContRunning`.
|
|
|
|
|
|
Primitive `getCurrentSCont` returns a reference to the current SCont under PTM. Primitive `switchTo` commits the current PTM transaction and switches to the given SCont. As we will see, these two primitives are necessary for [abstracting the scheduler](lightweight-concurrency#).
|
|
|
## Abstracting the Scheduler
|
|
|
|
|
|
|
|
|
Of course, care must be taken to ensure that the control does not switch to an SCont that is either running or completed.
|
|
|
Concurrency substrate does not impose any structure on the user-level schedulers. The programmer might choose to implement a single scheduler for the entire system or a scheduler per capability. The schedulers might also be hierarchical, with pluggable load-balancing policies. However, we need a uniform interface such that STM, asynchronous exceptions, safe-foreign calls, blackholes and other such mechanisms can interact with the user-level scheduler.
|
|
|
|
|
|
### Capabilities and Tasks
|
|
|
## Capabilities and Tasks
|
|
|
|
|
|
|
|
|
Whatever be the concurrency model, we would like to retain the non-programmatic control over parallelism (using +RTS -N). Just like in the current system, this runtime parameter controls the number of capabilities. Cores are system resources and hence, the control over their allocation to different processes should be a property of the context under which the programs are run. For example, in a multi-programmed environment, it might be wiser to run the programs on a fewer cores than available to avoid thrashing. At the very least, this will avoid the cases where a poorly written concurrency library would not bring down the performance of the entire system.
|
... | ... | |