diff options
Diffstat (limited to 'docs/comm/rts-libs/multi-thread.html')
| -rw-r--r-- | docs/comm/rts-libs/multi-thread.html | 445 |
1 files changed, 445 insertions, 0 deletions
diff --git a/docs/comm/rts-libs/multi-thread.html b/docs/comm/rts-libs/multi-thread.html new file mode 100644 index 0000000000..67a544be85 --- /dev/null +++ b/docs/comm/rts-libs/multi-thread.html @@ -0,0 +1,445 @@ +<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN"> +<html> +<head> + <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1"> +<title>The GHC Commentary - Supporting multi-threaded interoperation</title> +</head> +<body> +<h1>The GHC Commentary - Supporting multi-threaded interoperation</h1> +<em> +<p> +Authors: sof@galois.com, simonmar@microsoft.com<br> +Date: April 2002 +</p> +</em> +<p> +This document presents the implementation of an extension to +Concurrent Haskell that provides two enhancements: +</p> +<ul> +<li>A Concurrent Haskell thread may call an external (e.g., C) +function in a manner that's transparent to the execution/evaluation of +other Haskell threads. Section <a href="#callout">Calling out"</a> covers this. +</li> +<li> +OS threads may safely call Haskell functions concurrently. Section +<a href="#callin">"Calling in"</a> covers this. +</li> +</ul> + +<!---- *************************************** -----> +<h2 id="callout">The problem: foreign calls that block</h2> +<p> +When a Concurrent Haskell(CH) thread calls a 'foreign import'ed +function, the runtime system(RTS) has to handle this in a manner +transparent to other CH threads. That is, they shouldn't be blocked +from making progress while the CH thread executes the external +call. Presently, all threads will block. +</p> +<p> +Clearly, we have to rely on OS-level threads in order to support this +kind of concurrency. The implementation described here defines the +(abstract) OS threads interface that the RTS assumes. The implementation +currently provides two instances of this interface, one for POSIX +threads (pthreads) and one for the Win32 threads. +</p> + +<!---- *************************************** -----> +<h3>Multi-threading the RTS</h3> + +<p> +A simple and efficient way to implement non-blocking foreign calls is like this: +<ul> +<li> Invariant: only one OS thread is allowed to +execute code inside of the GHC runtime system. [There are alternate +designs, but I won't go into details on their pros and cons here.] +We'll call the OS thread that is currently running Haskell threads +the <em>Current Haskell Worker Thread</em>. +<p> +The Current Haskell Worker Thread repeatedly grabs a Haskell thread, executes it until its +time-slice expires or it blocks on an MVar, then grabs another, and executes +that, and so on. +</p> +<li> +<p> +When the Current Haskell Worker comes to execute a potentially blocking 'foreign +import', it leaves the RTS and ceases being the Current Haskell Worker, but before doing so it makes certain that +another OS worker thread is available to become the Current Haskell Worker. +Consequently, even if the external call blocks, the new Current Haskell Worker +continues execution of the other Concurrent Haskell threads. +When the external call eventually completes, the Concurrent Haskell +thread that made the call is passed the result and made runnable +again. +</p> +<p> +<li> +A pool of OS threads are constantly trying to become the Current Haskell Worker. +Only one succeeds at any moment. If the pool becomes empty, the RTS creates more workers. +<p><li> +The OS worker threads are regarded as interchangeable. A given Haskell thread +may, during its lifetime, be executed entirely by one OS worker thread, or by more than one. +There's just no way to tell. + +<p><li>If a foreign program wants to call a Haskell function, there is always a thread switch involved. +The foreign program uses thread-safe mechanisms to create a Haskell thread and make it runnable; and +the current Haskell Worker Thread exectutes it. See Section <a href="#callin">Calling in</a>. +</ul> +<p> +The rest of this section describes the mechanics of implementing all +this. There's two parts to it, one that describes how a native (OS) thread +leaves the RTS to service the external call, the other how the same +thread handles returning the result of the external call back to the +Haskell thread. +</p> + +<!---- *************************************** -----> +<h3>Making the external call</h3> + +<p> +Presently, GHC handles 'safe' C calls by effectively emitting the +following code sequence: +</p> + +<pre> + ...save thread state... + t = suspendThread(); + r = foo(arg1,...,argn); + resumeThread(t); + ...restore thread state... + return r; +</pre> + +<p> +After having squirreled away the state of a Haskell thread, +<tt>Schedule.c:suspendThread()</tt> is called which puts the current +thread on a list [<tt>Schedule.c:suspended_ccalling_threads</tt>] +containing threads that are currently blocked waiting for external calls +to complete (this is done for the purposes of finding roots when +garbage collecting). +</p> + +<p> +In addition to putting the Haskell thread on +<tt>suspended_ccalling_threads</tt>, <tt>suspendThread()</tt> now also +does the following: +</p> +<ul> +<li>Instructs the <em>Task Manager</em> to make sure that there's a +another native thread waiting in the wings to take over the execution +of Haskell threads. This might entail creating a new +<em>worker thread</em> or re-using one that's currently waiting for +more work to do. The <a href="#taskman">Task Manager</a> section +presents the functionality provided by this subsystem. +</li> + +<li>Releases its capability to execute within the RTS. By doing +so, another worker thread will become unblocked and start executing +code within the RTS. See the <a href="#capability">Capability</a> +section for details. +</li> + +<li><tt>suspendThread()</tt> returns a token which is used to +identify the Haskell thread that was added to +<tt>suspended_ccalling_threads</tt>. This is done so that once the +external call has completed, we know what Haskell thread to pull off +the <tt>suspended_ccalling_threads</tt> list. +</li> +</ul> + +<p> +Upon return from <tt>suspendThread()</tt>, the OS thread is free of +its RTS executing responsibility, and can now invoke the external +call. Meanwhile, the other worker thread that have now gained access +to the RTS will continue executing Concurrent Haskell code. Concurrent +'stuff' is happening! +</p> + +<!---- *************************************** -----> +<h3>Returning the external result</h3> + +<p> +When the native thread eventually returns from the external call, +the result needs to be communicated back to the Haskell thread that +issued the external call. The following steps takes care of this: +</p> + +<ul> +<li>The returning OS thread calls <tt>Schedule.c:resumeThread()</tt>, +passing along the token referring to the Haskell thread that made the +call we're returning from. +</li> + +<li> +The OS thread then tries to grab hold of a <em>returning worker +capability</em>, via <tt>Capability.c:grabReturnCapability()</tt>. +Until granted, the thread blocks waiting for RTS permissions. Clearly we +don't want the thread to be blocked longer than it has to, so whenever +a thread that is executing within the RTS enters the Scheduler (which +is quite often, e.g., when a Haskell thread context switch is made), +it checks to see whether it can give up its RTS capability to a +returning worker, which is done by calling +<tt>Capability.c:yieldToReturningWorker()</tt>. +</li> + +<li> +If a returning worker is waiting (the code in <tt>Capability.c</tt> +keeps a counter of the number of returning workers that are currently +blocked waiting), it is woken up and the given the RTS execution +priviledges/capabilities of the worker thread that gave up its. +</li> + +<li> +The thread that gave up its capability then tries to re-acquire +the capability to execute RTS code; this is done by calling +<tt>Capability.c:waitForWorkCapability()</tt>. +</li> + +<li> +The returning worker that was woken up will continue execution in +<tt>resumeThread()</tt>, removing its associated Haskell thread +from the <tt>suspended_ccalling_threads</tt> list and start evaluating +that thread, passing it the result of the external call. +</li> +</ul> + +<!---- *************************************** -----> +<h3 id="rts-exec">RTS execution</h3> + +<p> +If a worker thread inside the RTS runs out of runnable Haskell +threads, it goes to sleep waiting for the external calls to complete. +It does this by calling <tt>waitForWorkCapability</tt> +</p> + +<p> +The availability of new runnable Haskell threads is signalled when: +</p> + +<ul> +<li>When an external call is set up in <tt>suspendThread()</tt>.</li> +<li>When a new Haskell thread is created (e.g., whenever +<tt>Concurrent.forkIO</tt> is called from within Haskell); this is +signalled in <tt>Schedule.c:scheduleThread_()</tt>. +</li> +<li>Whenever a Haskell thread is removed from a 'blocking queue' +attached to an MVar (only?). +</li> +</ul> + +<!---- *************************************** -----> +<h2 id="callin">Calling in</h2> + +Providing robust support for having multiple OS threads calling into +Haskell is not as involved as its dual. + +<ul> +<li>The OS thread issues the call to a Haskell function by going via +the <em>Rts API</em> (as specificed in <tt>RtsAPI.h</tt>). +<li>Making the function application requires the construction of a +closure on the heap. This is done in a thread-safe manner by having +the OS thread lock a designated block of memory (the 'Rts API' block, +which is part of the GC's root set) for the short period of time it +takes to construct the application. +<li>The OS thread then creates a new Haskell thread to execute the +function application, which (eventually) boils down to calling +<tt>Schedule.c:createThread()</tt> +<li> +Evaluation is kicked off by calling <tt>Schedule.c:scheduleExtThread()</tt>, +which asks the Task Manager to possibly create a new worker (OS) +thread to execute the Haskell thread. +<li> +After the OS thread has done this, it blocks waiting for the +Haskell thread to complete the evaluation of the Haskell function. +<p> +The reason why a separate worker thread is made to evaluate the Haskell +function and not the OS thread that made the call-in via the +Rts API, is that we want that OS thread to return as soon as possible. +We wouldn't be able to guarantee that if the OS thread entered the +RTS to (initially) just execute its function application, as the +Scheduler may side-track it and also ask it to evaluate other Haskell threads. +</li> +</ul> + +<p> +<strong>Note:</strong> As of 20020413, the implementation of the RTS API +only serializes access to the allocator between multiple OS threads wanting +to call into Haskell (via the RTS API.) It does not coordinate this access +to the allocator with that of the OS worker thread that's currently executing +within the RTS. This weakness/bug is scheduled to be tackled as part of an +overhaul/reworking of the RTS API itself. + + +<!---- *************************************** -----> +<h2>Subsystems introduced/modified</h2> + +<p> +These threads extensions affect the Scheduler portions of the runtime +system. To make it more manageable to work with, the changes +introduced a couple of new RTS 'sub-systems'. This section presents +the functionality and API of these sub-systems. +</p> + +<!---- *************************************** -----> +<h3 id="#capability">Capabilities</h3> + +<p> +A Capability represent the token required to execute STG code, +and all the state an OS thread/task needs to run Haskell code: +its STG registers, a pointer to its TSO, a nursery etc. During +STG execution, a pointer to the capabilitity is kept in a +register (BaseReg). +</p> +<p> +Only in an SMP build will there be multiple capabilities, for +the threaded RTS and other non-threaded builds, there is only +one global capability, namely <tt>MainCapability</tt>. + +<p> +The Capability API is as follows: +<pre> +/* Capability.h */ +extern void initCapabilities(void); + +extern void grabReturnCapability(Mutex* pMutex, Capability** pCap); +extern void waitForWorkCapability(Mutex* pMutex, Capability** pCap, rtsBool runnable); +extern void releaseCapability(Capability* cap); + +extern void yieldToReturningWorker(Mutex* pMutex, Capability* cap); + +extern void grabCapability(Capability** cap); +</pre> + +<ul> +<li><tt>initCapabilities()</tt> initialises the subsystem. + +<li><tt>grabReturnCapability()</tt> is called by worker threads +returning from an external call. It blocks them waiting to gain +permissions to do so. + +<li><tt>waitForWorkCapability()</tt> is called by worker threads +already inside the RTS, but without any work to do. It blocks them +waiting for there to new work to become available. + +<li><tt>releaseCapability()</tt> hands back a capability. If a +'returning worker' is waiting, it is signalled that a capability +has become available. If not, <tt>releaseCapability()</tt> tries +to signal worker threads that are blocked waiting inside +<tt>waitForWorkCapability()</tt> that new work might now be +available. + +<li><tt>yieldToReturningWorker()</tt> is called by the worker thread +that's currently inside the Scheduler. It checks whether there are other +worker threads waiting to return from making an external call. If so, +they're given preference and a capability is transferred between worker +threads. One of the waiting 'returning worker' threads is signalled and made +runnable, with the other, yielding, worker blocking to re-acquire +a capability. +</ul> + +<p> +The condition variables used to implement the synchronisation between +worker consumers and providers are local to the Capability +implementation. See source for details and comments. +</p> + +<!---- *************************************** -----> +<h3 id="taskman">The Task Manager</h3> + +<p> +The Task Manager API is responsible for managing the creation of +OS worker RTS threads. When a Haskell thread wants to make an +external call, the Task Manager is asked to possibly create a +new worker thread to take over the RTS-executing capability of +the worker thread that's exiting the RTS to execute the external call. + +<p> +The Capability subsystem keeps track of idle worker threads, so +making an informed decision about whether or not to create a new OS +worker thread is easy work for the task manager. The Task manager +provides the following API: +</p> + +<pre> +/* Task.h */ +extern void startTaskManager ( nat maxTasks, void (*taskStart)(void) ); +extern void stopTaskManager ( void ); + +extern void startTask ( void (*taskStart)(void) ); +</pre> + +<ul> +<li><tt>startTaskManager()</tt> and <tt>stopTaskManager()</tt> starts +up and shuts down the subsystem. When starting up, you have the option +to limit the overall number of worker threads that can be +created. An unbounded (modulo OS thread constraints) number of threads +is created if you pass '0'. +<li><tt>startTask()</tt> is called when a worker thread calls +<tt>suspendThread()</tt> to service an external call, asking another +worker thread to take over its RTS-executing capability. It is also +called when an external OS thread invokes a Haskell function via the +<em>Rts API</em>. +</ul> + +<!---- *************************************** -----> +<h3>Native threads API</h3> + +To hide OS details, the following API is used by the task manager and +the scheduler to interact with an OS' threads API: + +<pre> +/* OSThreads.h */ +typedef <em>..OS specific..</em> Mutex; +extern void initMutex ( Mutex* pMut ); +extern void grabMutex ( Mutex* pMut ); +extern void releaseMutex ( Mutex* pMut ); + +typedef <em>..OS specific..</em> Condition; +extern void initCondition ( Condition* pCond ); +extern void closeCondition ( Condition* pCond ); +extern rtsBool broadcastCondition ( Condition* pCond ); +extern rtsBool signalCondition ( Condition* pCond ); +extern rtsBool waitCondition ( Condition* pCond, + Mutex* pMut ); + +extern OSThreadId osThreadId ( void ); +extern void shutdownThread ( void ); +extern void yieldThread ( void ); +extern int createOSThread ( OSThreadId* tid, + void (*startProc)(void) ); +</pre> + + + +<!---- *************************************** -----> +<h2>User-level interface</h2> + +To signal that you want an external call to be serviced by a separate +OS thread, you have to add the attribute <tt>threadsafe</tt> to +a foreign import declaration, i.e., + +<pre> +foreign import "bigComp" threadsafe largeComputation :: Int -> IO () +</pre> + +<p> +The distinction between 'safe' and thread-safe C calls is made +so that we may call external functions that aren't re-entrant but may +cause a GC to occur. +<p> +The <tt>threadsafe</tt> attribute subsumes <tt>safe</tt>. +</p> + +<!---- *************************************** -----> +<h2>Building the GHC RTS</h2> + +The multi-threaded extension isn't currently enabled by default. To +have it built, you need to run the <tt>fptools</tt> configure script +with the extra option <tt>--enable-threaded-rts</tt> turned on, and +then proceed to build the compiler as per normal. + +<hr> +<small> +<!-- hhmts start --> Last modified: Wed Apr 10 14:21:57 Pacific Daylight Time 2002 <!-- hhmts end --> +</small> +</body> </html> + |