+++ /dev/null
-<!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>
-
projects / ghc-hetmet.git / blobdiff