Still improving manual.
authorJosh Yelon <jyelon@uiuc.edu>
Thu, 26 Jun 1997 05:16:20 +0000 (05:16 +0000)
committerJosh Yelon <jyelon@uiuc.edu>
Thu, 26 Jun 1997 05:16:20 +0000 (05:16 +0000)
doc/converse/cmi.tex
doc/converse/cpvmacros.tex
doc/converse/msgmgr.tex
doc/converse/threads.tex

index 4f8a39f58379502bca4af5362896786ff4d1653d..7041fa614259e0da65dfc281172817c54e6b99d1 100644 (file)
@@ -76,6 +76,27 @@ registration techniques.  One may use all three registration methods
 in a program.  The system guarantees that no numbering conflicts will
 occur as a result of this combination.
 
+\section{Writing Handler Functions}
+
+A message handler function is just a C function that accepts a void
+pointer (to a message buffer) as an argument, and returns nothing.  The
+handler may use the message buffer until it returns, at which time
+Converse will automatically free the message buffer.  This behavior
+can be overrided using CmiGrabBuffer:
+
+\function{void CmiGrabBuffer(void **pbuf)}
+\index{CmiGrabBuffer}
+\desc{A handler function receives a pointer to a message buffer
+as an argument.  Normally, it is supposed to copy the data out of the
+message buffer before it returns, at which time Converse automatically
+frees the message buffer.  However, a handler function may use
+CmiGrabBuffer to claim ownership of the message buffer (and therefore
+prevent Converse from freeing it).  Assuming, for example, that the
+handler function called its argument {\tt msg}, it would call {\tt
+CmiGrabBuffer(\&msg)}.  Afterward, {\tt msg} contains a pointer to the
+message, or a copy of it.  From that point forward, it is the user's
+responsibility to free the message using \param{CmiFree.}}
+
 \section{Building Messages}
 
 To send a message, one first creates a buffer to hold the message.
@@ -122,72 +143,73 @@ handler number.}
 \desc{This call returns the handler of a message in the form of a
 function pointer.}
 
-\function{void CmiGrabBuffer(void **pbuf)}
-\index{CmiGrabBuffer}
-\desc{A handler function receives a pointer to a message buffer
-as an argument.  Normally, it is supposed to copy the data out of the
-message buffer, and then return, at which time Converse automatically
-frees the message buffer.  However, a handler function may use
-CmiGrabBuffer to claim ownership of the message buffer (and therefore
-prevent Converse from freeing it).  Assuming, for example, that the
-handler function called its argument {\tt msg}, it would call {\tt
-CmiGrabBuffer(\&msg)}.  Afterward, {\tt msg} contains a pointer to the
-message, or a copy of it.  From that point forward, it is the user's
-responsibility to free the message using \param{CmiFree.}}
-
 \section{Sending Messages}
 
-The following functions allow you to send messages:
+The following functions allow you to send messages.  Our model is that
+the data starts out in the message buffer, and from there gets
+transferred ``into the network''.  The data stays ``in the network''
+for a while, and eventually appears on the target processor.  Using
+that model, each of these send-functions is a device that transfers
+data into the network.  None of these functions wait for the data to
+be delivered.
+
+On some machines, the network accepts data rather slowly.  We don't
+want the process to sit idle, waiting for the network to accept the
+data.  So, we provide several variations on each send function:
+
+\begin{itemize}
+
+\item{{\bf sync}: a version that is as simple as possible, pushing the
+data into the network and not returning until the data is ``in the
+network''.  As soon as a sync function returns, you can reuse the
+message buffer.}
+
+\item{{\bf async}: a version that returns almost instantaneously, and then
+continues working in the background.  The background job transfers the
+data from the message buffer into the network.  Since the background job
+is still using the message buffer when the function returns, you can't
+reuse the message buffer immediately.  The background job sets a flag
+when it is done and you can reuse the message buffer.}
+
+\item{{\bf sync and free}: a version that returns almost instantaneously,
+and then continues working in the background.  The background job
+transfers the data from the message buffer into the network.  When the
+background job finishes, it {\tt CmiFree}s the message buffer.  In
+this situation, you can't reuse the message buffer at all.  Of course,
+to use a function of this type, you must allocate the message buffer
+using {\tt CmiAlloc}.}
+
+\end{itemize}
 
 \function{void CmiSyncSend(unsigned int destPE, unsigned int size, void *msg)}
 \index{CmiSyncSend}
-
 \desc{Sends \param{msg} of size \param{size} bytes to processor
-\param{destPE}.  The call does not return until the data has been
-copied from the user-provided message buffer into system buffers.
-Therefore, once this call returns, you are free to reuse the
-message buffer immediately.}
+\param{destPE}.  When it returns, you may reuse the message buffer.}
 
 \function{void CmiSyncSendAndFree(unsigned int destPE, unsigned int size, void *msg)}
 \index{CmiSyncSendAndFree}
 \desc{Sends \param{msg} of size \param{size} bytes to processor
-\param{destPE} and then {\tt CmiFree}s the message buffer \param{msg}.
-Caution: the message buffer {\em must} have been allocated using {\tt
-CmiAlloc}.}
+\param{destPE}.  When it returns, the message buffer has been freed
+using {\tt CmiFree}}
 
 \function{CmiCommHandle CmiAsyncSend(unsigned int destPE, unsigned int size, void *msg)}
 \index{CmiAsyncSend}
-\desc{Sends a message of size \param{size} bytes to processor
-\param{destPE}.  This function returns before the data has even been
-copied out of the user's message buffer.  Therefore, the Converse
-user must leave the message buffer alone for a time after calling
-this function.  This function returns a communication handle which
-can be tested to determine whether or not the buffer can be reused
-yet.}
-
-\function{int CmiAsyncMsgSent(CmiCommHandle handle)}
-\index{CmiAsyncMsgSent}
-\desc{Returns true if the communication specified by the given
-CmiCommHandle has proceeded to the point where the message buffer can
-be reused.}
-
-\function{void CmiReleaseCommHandle(CmiCommHandle handle)}
-\index{CmiReleaseCommHandle}
-\desc{Releases the communication handle \param{handle} and
-associated resources. It does not free the message buffer.}
+\desc{Sends \param{msg} of size \param{size} bytes to processor
+\param{destPE}.  It returns a communication handle which can be
+tested using CmiAsyncMsgSent: when this returns true, you may reuse
+the message buffer.}
 
 \function{void CmiSyncVectorSend(int destPE, int len, int sizes[], char *msgComps[])}
-\desc{Synchronous send of data to processor
+\desc{Concatenates several pieces of data and sends them to processor
 \param{destPE}.  The data consists of \param{len} pieces residing in
 different areas of memory, which are logically concatenated.  The
 \param{msgComps} array contains pointers to the pieces; the size of
 \param{msgComps[i]} is taken from \param{sizes[i]}. 
-\param{sizes}, \param{msgComps} and the message components specified in
-\param{msgComps} could be reused after the function call returns.
-}
+When it returns, \param{sizes}, \param{msgComps} and the message
+components specified in \param{msgComps} can be immediately reused.}
 
 \function{void CmiSyncVectorSendAndFree(int destPE, int len, int sizes[], char *msgComps[])}
-\desc{Synchronous send of data to processor
+\desc{Concatenates several pieces of data and sends them to processor
 \param{destPE}.  The data consists of \param{len} pieces residing in
 different areas of memory, which are logically concatenated.  The
 \param{msgComps} array contains pointers to the pieces; the size of
@@ -198,16 +220,27 @@ allocated using \param{CmiAlloc()}.  However, the \param{sizes} and
 \param{msgComps} array themselves are not freed.}
 
 \function{CmiCommHandle CmiAsyncVectorSend(int destPE, int len, int sizes[], char *msgComps[])}
-\desc{Initiates an asynchronous send of data to processor
+\desc{Concatenates several pieces of data and sends them to processor
 \param{destPE}.  The data consists of \param{len} pieces residing in
 different areas of memory, which are logically concatenated.  The
 \param{msgComps} array contains pointers to the pieces; the size of
 \param{msgComps[i]} is taken from \param{sizes[i]}. 
-This function returns a communication handle which could be used to enquire
-about the status of communication using \param{CmiAsyncMsgSent()}.
-Individual pieces of data as well as the arrays \param{sizes} and
+The individual pieces of data as well as the arrays \param{sizes} and
 \param{msgComps} should not be overwritten or freed before the
-communication is complete.}
+communication is complete.  This function returns a communication
+handle which can be tested using CmiAsyncMsgSent: when this returns
+true, the input parameters can be reused.}
+
+\function{int CmiAsyncMsgSent(CmiCommHandle handle)}
+\index{CmiAsyncMsgSent}
+\desc{Returns true if the communication specified by the given
+CmiCommHandle has proceeded to the point where the message buffer can
+be reused.}
+
+\function{void CmiReleaseCommHandle(CmiCommHandle handle)}
+\index{CmiReleaseCommHandle}
+\desc{Releases the communication handle \param{handle} and
+associated resources. It does not free the message buffer.}
 
 \section{Broadcasting Messages}
 
@@ -256,6 +289,7 @@ could be used to check the status of this send using
 freed before the communication is complete.}
 
 \section{Scheduling Messages}
+\label{schedqueue}
 
 The scheduler queue is a powerful priority queue.  The following
 functions can be used to place messages into the scheduler queue.
@@ -264,24 +298,95 @@ they reach the front of the queue, they trigger handler functions,
 just like messages transmitted with Cmi functions.  Note that unlike
 the Cmi send functions, these cannot move messages across processors.
 
+Every message inserted into the queue has a priority associated with
+it.  Converse priorities are arbitrary-precision numbers between 0 and
+1.  Priorities closer to 0 get processed first, priorities closer to 1
+get processed last.  Arbitrary-precision priorities are very useful in
+AI search-tree applications. Suppose we have a heuristic suggesting
+that tree node N1 should be searched before tree node N2. We therefore
+designate that node N1 and its descendants will use high priorities,
+and that node N2 and its descendants will use lower priorities. We
+have effectively split the range of possible priorities in two. If
+several such heuristics fire in sequence, we can easily split the
+priority range in two enough times that no significant bits remain,
+and the search begins to fail for lack of meaningful priorities to
+assign. The solution is to use arbitrary-precision priorities, aka
+bitvector priorities.
+
+These arbitrary-precision numbers are represented as bit-strings: for
+example, the bit-string ``0011000101'' represents the binary number
+(.0011000101).  The format of the bit-string is as follows: the
+bit-string is represented as an array of unsigned integers. The most
+significant bit of the first integer contains the first bit of the
+bitvector.  The remaining bits of the first integer contain the next
+31 bits of the bitvector.  Subsequent integers contain 32 bits
+each. If the size of the bitvector is not a multiple of 32, then the
+last integer contains 0 bits for padding in the least-significant bits
+of the integer.
+
+Some people only want regular integers as priorities.  For
+simplicity's sake, we provide an easy way to convert integer
+priorities to Converse's built-in representation.
+
+In addition to priorities, you may choose to enqueue a message
+``LIFO'' or ``FIFO''.  Enqueueing a message ``FIFO'' simply pushes it
+behind all the other messages of the same priority.  Enqueueing a
+message ``LIFO'' pushes it in front of other messages of the same
+priority.
+
+Messages sent using the CMI functions take precedence over everything
+in the scheduler queue, regardless of priority.
+
 \function{void CsdEnqueueGeneral(void *Message, int strategy, int priobits, int *prioptr)}
 \index{CsdEnqueueGeneral}
-\desc{This call enqueues a message to the scheduler's queue, to be processed in 
-accordance with the queueing \param{strategy}. \param{priobits} and
-\param{prioptr} specify information about priority associated with the message
-if prioritized queueing strategies are used. \param{strategy} can take values 
-defined in {\tt converse.h} depending upon the queueing strategy (FIFO or LIFO)
-and the nature of priority information used (none, integer or bit-vector).
-These predefined constants are: 
-{\tt CQS\_QUEUEING\_FIFO}, {\tt CQS\_QUEUEING\_LIFO},
-{\tt CQS\_QUEUEING\_IFIFO}, {\tt CQS\_QUEUEING\_ILIFO},
-{\tt CQS\_QUEUEING\_BFIFO}, and\\  {\tt CQS\_QUEUEING\_BLIFO}.
-This call is usually made from
-a message handler when the message is not to be processed immediately,
-but may be processed later (e.g. depending on the message's priority).
-Also, it is used to enqueue local ready entities, such as threads.
-\note{It is necessary to grab the ownership of the message buffer before queuing
-because on returning from the handler, the system can reuse the buffer.}}
+\desc{This call enqueues a message to the scheduler's queue, to
+be sorted according to its priority and the queueing \param{strategy}.
+The meaning of the \param{priobits} and \param{prioptr} fields depend
+on the value of \param{strategy}, which can be any of the following:
+
+\begin{itemize}
+\item{{\tt CQS\_QUEUEING\_BFIFO}: the priobits and prioptr point to
+a bit-string representing an arbitrary-precision priority.  The message
+is pushed behind all other message of this priority.}
+
+\item{{\tt CQS\_QUEUEING\_BLIFO}: the priobits and prioptr point to
+a bit-string representing an arbitrary-precision priority.  The message
+is pushed in front all other message of this priority.}
+
+\item{{\tt CQS\_QUEUEING\_IFIFO}: the prioptr is a pointer to a
+signed integer.  The integer is converted to a bit-string priority,
+normalizing so that the integer zero is converted to the bit-string
+``1000...'' (the ``middle'' priority).  To be more specific, the
+conversion is performed by adding 0x80000000 to the integer, and then
+treating the resulting 32-bit quantity as a 32-bit bitvector priority.
+The message is pushed behind all other messages of this priority.}
+
+\item{{\tt CQS\_QUEUEING\_ILIFO}: the prioptr is a pointer to a
+signed integer.  The integer is converted to a bit-string priority,
+normalizing so that the integer zero is converted to the bit-string
+``1000...'' (the ``middle'' priority).  To be more specific, the
+conversion is performed by adding 0x80000000 to the integer, and then
+treating the resulting 32-bit quantity as a 32-bit bitvector priority.
+The message is pushed in front of all other messages of this
+priority.}
+
+\item{{\tt CQS\_QUEUEING\_FIFO}: the prioptr and priobits are ignored.
+The message is enqueued with the middle priority ``1000...'', and is
+pushed behind all other messages with this priority.}
+
+\item{{\tt CQS\_QUEUEING\_FIFO}: the prioptr and priobits are ignored.
+The message is enqueued with the middle priority ``1000...'', and is
+pushed in front of all other messages with this priority.}
+
+\end{itemize}
+
+Caution: the priority itself is {\em not copied} by the scheduler.
+Therefore, if you pass a pointer to a priority into the scheduler, you
+must not overwrite or free that priority until after the message has
+emerged from the scheduler's queue.  It is normal to actually store
+the priority {\em in the message itself}, though it is up to the user
+to actually arrange storage for the priority.
+}
 
 \function {void CsdEnqueue(void *Message)}
 \index{CsdEnqueue}
@@ -295,7 +400,6 @@ provided here for backward compatibility.}
 {\tt CsdEnqueueGeneral(Message, CQS\_QUEUEING\_FIFO,0, NULL)} 
 provided here for backward compatibility.}
 
-
 \function{void CsdEnqueueLifo(void *Message)}
 \index{CsdEnqueueLifo}
 \desc{This macro is a shorthand for
@@ -330,19 +434,16 @@ to wait for: it does not allow any other event to occur.
 \index{CsdScheduler}
 \desc{This call invokes the Converse scheduler, which repeatedly
 delivers messages to their handlers (i.e. invokes the handler for each
-message it selects).  Each message header encodes a pointer to its
-handler as described in the next chapter. 
-In each iteration, the scheduler first looks for any
-message that  has arrived from another processor, and delivers it.
+message it selects).  In each iteration, the scheduler first looks for
+any message that has arrived from another processor, and delivers it.
 If there isn't any, it selects a message from the locally enqueued
-messages (see below), and delivers it.
-The {\tt NumberOfMessages}
-parameter specifies how many messages should be processed (i.e. delivered
-to their handlers). If set to -1, the scheduler continues delivering
+messages, and delivers it.  The {\tt NumberOfMessages} parameter
+specifies how many messages should be processed (i.e. delivered to
+their handlers). If set to -1, the scheduler continues delivering
 messages until CsdExitScheduler() is called from a message handler.
-if {\tt NumberOfMessages} is 0, the scheduler continues delivering messages
-until it exhausts its supply of messages (i.e. becomes idle) or some 
-handler calls CsdExitScheduler().}
+if {\tt NumberOfMessages} is 0, the scheduler continues delivering
+messages until it exhausts its supply of messages (i.e. becomes idle)
+or some handler calls CsdExitScheduler().}
 
 \function{int CmiDeliverMsgs(int MaxMsgs)}
 \index{CmiDeliverMsgs}
@@ -351,26 +452,20 @@ corresponding handler functions for arrived messages. This function
 returns after either the network message queue becomes empty or after
 \param{MaxMsgs} messages have been retrieved and their handlers called. 
 It returns the difference between total messages delivered and \param{MaxMsgs}.
-The handler is given a pointer to the message as  its parameter.
-Normally, the delivered message is owned by CMI,  and so the handler
-should not free it, or store it for later use.  
-If the handler wishes to  use the message later (for example, by
-enqueueing the message with the scheduler), it must call
-\param{CmiGrabBuffer()} to
-acquire the  ownership of the message buffer.}
+The handler is given a pointer to the message as  its parameter.}
 
 \function{void CmiDeliverSpecificMsg(int HandlerId)}
 \index{CmiDeliverSpecificMsg}
-\desc{Retrieves messages from the network queue and delivers the first message
-with its handler field equal to \param{HandlerId}. This functions queues
-the remaining messages retrieved from the network. It returns after the 
-invoked handler function returns.}
+\desc{Retrieves messages from the network queue and delivers the first
+message with its handler field equal to \param{HandlerId}. This functions
+leaves alone all other messages. It returns after the invoked handler
+function returns.}
 
 \function {void CsdExitScheduler(void)}
 \index{CsdExitScheduler}
-\desc{This call causes the scheduler
-to stop processing messages when control has returned back to it.
-The scheduler then returns to its calling routine.}
+\desc{This call causes CsdScheduler to stop processing messages when
+control has returned back to it. The scheduler then returns to its
+calling routine.}
 
 \internal{
 \section{Global Pointer}
index c83f1988c67dcc208486d594a7d1d5246b7c9fa3..efb66c9b75f1197b0e0367d05cdae52a650db6b8 100644 (file)
 % REVISION HISTORY:
 %
 % $Log$
-% Revision 1.6  1997-06-25 06:53:48  jyelon
+% Revision 1.7  1997-06-26 05:16:22  jyelon
+% Still improving manual.
+%
+% Revision 1.6  1997/06/25 06:53:48  jyelon
 % Just trying to make this whole manual make more sense.
 %
 % Revision 1.5  1995/11/16 22:11:11  milind
 
 \chapter{Machine Model and Global Variables}
 
-The machine model assumed by Converse consists of a collection of
-nodes, where each node comprises of a number of processors that
-share memory. In addition, each of the processors could have multiple
-threads running on them which share code and data but have different
-stacks. On networks of workstations or distributed memory MIMD
-machines, number of processors in each node is assumed to be one and on
-machines that do not have native thread support, there is only one
-thread per processor. Converse provides functions to determine rank of
-a processor within a node and a consistent access/modification
-mechanism to manipulate global variables.
+Converse treats the parallel machine as a collection of nodes, where
+each node comprises of a number of processors that share memory.  In
+some cases, the number of processors per node may be exactly one.  In
+addition, each of the processors may have multiple threads running on
+them which share code and data but have different stacks.
+
+Different vendors are not consistent about how they treat global and static
+variables.  Most vendors write C compilers in which global variables are
+shared among all the processors in the node.  A few vendors write C
+compilers where each processor has its own copy of the global variables.
+In theory, it would also be possible to design the compiler so that
+each thread has its own copy of the global variables.
+
+The lack of consistency across vendors, makes it very hard to write a
+portable program.  The fact that most vendors make the globals shared
+is inconvenient as well, usually, you don't want your globals to be
+shared.  For these reasons, we added ``pseudoglobals'' to Converse.
+These act much like C global and static variables, except that you have
+explicit control over the degree of sharing.
 
-\section{Global Variables}
+\section{Converse PseudoGlobals}
 
-Global variables are allowed in Converse via specific macros.  These macros 
-ensure that the program runs portably on various parallel machines. 
-Three classes of global variables are supported: node-private,
-process-private, and thread-private variables. 
+Three classes of pseudoglobal variables are supported: node-private,
+process-private, and thread-private variables.
 
 \begin{description}
 \item[Node-private global variables] are specific to a node. They are
@@ -63,16 +73,16 @@ process-private, and thread-private variables.
 \end{description}
 
 There are five macros for each class. These macros are for
-declaration, static declaration, extern declaration, initialization, and
-access. The declaration, static and extern specifications have the same
-meaning as in C. In order to support portability, however, the global
-variables must be installed properly, by using the initialization macros.
-For example, if the underlying machine is a simulator for the machine model 
-supported by Converse, then the thread-private variables must be turned into 
-arrays of variables.  Initialize and Access macros hide these details from 
-the user.  It is possible to use global variables without these macros, 
-as supported by the underlying machine, but at the expense of portability.
-
+declaration, static declaration, extern declaration, initialization,
+and access. The declaration, static and extern specifications have the
+same meaning as in C. In order to support portability, however, the
+global variables must be installed properly, by using the
+initialization macros.  For example, if the underlying machine is a
+simulator for the machine model supported by Converse, then the
+thread-private variables must be turned into arrays of variables.
+Initialize and Access macros hide these details from the user.  It is
+possible to use global variables without these macros, as supported by
+the underlying machine, but at the expense of portability.
 
 Macros for node-private variables:
 \begin{verbatim}
@@ -118,23 +128,23 @@ CtvAccess(variable)
 \index{CtvAccess}
 
 
-    A sample code to illustrate the usage of the macros is provided
-    in Figure~\ref{fig:cpv}.
-    There are a few rules that user must pay attention: The
-    {\tt type} and {\tt variable} fields of the macros must be a single
-    word. Therefore, structures or pointer types can be used by defining
-    new types with the {\tt typedef}. In the sample code, for example,
-    a {\tt struct point} type is redefined with a {\tt typedef} as {\tt Point}
-    in order to use it in the macros. Similarly,  the access macros contain
-    only the name of the global variable. Any indexing or member access
-    must be outside of the macro as shown in the sample code 
-    (function {\tt func1}). Finally, all the global variables must be
-    installed before they are used. One way to do this systematically is
-    to provide a module-init function for each file (in the sample code - 
-    {\tt ModuleInit()}. The module-init functions of each file, then, can be 
-    called at the beginning of execution to complete the installations of 
-    all global variables.
-    
+A sample code to illustrate the usage of the macros is provided
+in Figure~\ref{fig:cpv}.
+There are a few rules that user must pay attention: The
+{\tt type} and {\tt variable} fields of the macros must be a single
+word. Therefore, structures or pointer types can be used by defining
+new types with the {\tt typedef}. In the sample code, for example,
+a {\tt struct point} type is redefined with a {\tt typedef} as {\tt Point}
+in order to use it in the macros. Similarly,  the access macros contain
+only the name of the global variable. Any indexing or member access
+must be outside of the macro as shown in the sample code 
+(function {\tt func1}). Finally, all the global variables must be
+installed before they are used. One way to do this systematically is
+to provide a module-init function for each file (in the sample code - 
+{\tt ModuleInit()}. The module-init functions of each file, then, can be 
+called at the beginning of execution to complete the installations of 
+all global variables.
+
 \begin{figure}
 \begin{verbatim}
 File Module1.c
index 5af884af5a8ea5804bd003548e3db9b7dadfbe90..3d7b5d19234ddbf6dfb6bf2975d49f45ffe05034 100644 (file)
@@ -1,12 +1,8 @@
-\chapter{Tag Matching and Message Storage}
+\chapter{Tag Matching and the Message Manager}
 
-The calls in this chapter can be used to put together runtime systems
-for languages that support tag-based message retrieval.
-
-\section{Message Manager Calls}
-
-To use the message manager, you must include {\tt converse.h} and
-link with the converse library.
+The message manager is a data structure that can be used to put together
+runtime systems for languages that support tag-based message
+retrieval.
 
 The purpose of the message manager is to store, index, and retrieve
 messages according to a set of integer tags.  It provides functions to
@@ -15,6 +11,10 @@ their tags), and functions to selectively retrieve messages from
 tables according to their tags.  Wildcard tags can be specified in
 both storage and retrieval.
 
+
+To use the message manager, you must include {\tt converse.h} and
+link with the converse library.
+
 In actuality, the term ``message manager'' is unnecessarily specific.
 The message manager can store and retrieve arbitrary pointers
 according to a set of tags.  The pointers do {\em not} necessarily
index d6ddf3e395593ea332672226eec4a779d82a8148..4fa00ade23f53301a8370d783e312f1db83df9dc 100644 (file)
@@ -2,50 +2,19 @@
 
 The calls in this chapter can be used to put together runtime systems
 for languages that support threads.
+This threads package, like most thread packages, provides basic
+functionality like creating threads, destroying threads, yielding, 
+suspending, and awakening a suspended thread. In
+addition, it provides facilities whereby you can write your own thread
+schedulers.  
 
-To use the threads package, you must include {\tt converse.h} and link
-with the converse library.  Note: threads are not implemented on all
-hardware platforms.  Although a program that calls thread-functions
-will {em link} on all platforms, it won't necessarily {\tt execute}.
-Attempting to initialize the threads package on a machine that does
-not support threads will result in an error message.
-
-This threads package, like most thread packages, provides a function
-for creating threads, one for destroying threads, one for explicitly
-transferring control to another thread, and one for retrieving the
-currently-executing thread.  Note that these functions do not include
-any intelligent strategy for choosing which thread executes when: in
-other words, they provide no scheduler.
-
-However, though the threads package does not provide an actual
-scheduler, it does assume that the user is going to need one.
-Therefore, it defines an interface to which all schedulers can comply.
-This makes it possible for users to write blocking code (eg, locks,
-barriers, etc) without knowing exactly how the scheduler will work.
-The scheduler interface consists of an awaken function and a suspend
-function, provided by whomever implements the scheduler.  The awaken
-function is called by the thread user to notify the scheduler that a
-particular thread wants the CPU.  The scheduler is expected to respond
-to this by inserting the thread into a ready-queue or something
-similar.  The suspend function tells the scheduler that the current
-thread no longer wants the CPU, whereupon the scheduler must choose
-another thread to execute instead.  No stipulation is made about how
-the scheduler chooses the thread to execute next, except that the
-thread must want the CPU. (Eg, somebody must have declared that the
-thread wants the CPU using the awaken-function.)
-
-The threads-package makes it possible to associate private data
-with a thread.  To this end, we provide functions for storing and
-retrieving arbitrary user data in the thread-object.
-
-Finally, as a convenience to converse users, we provide a function
-that causes a thread to be automatically scheduled by the converse
-scheduler {\tt CsdScheduler}.
-
-\function{int CthImplemented()}
-\index{CthImplemented}
-\desc{Returns true if the current hardware platform supports the threads
-functions described below.}
+\section{Basic Thread Calls}
+
+Note: in this section, we refer to the ready-queue.  By default, this
+means the central scheduler queue previously described in section
+\ref{schedqueue}.  There are hooks that enable you to change which
+ready-queue a thread uses, but unless you've taken explicit action,
+you can assume the threads are all using the main ready-queue.
 
 \function{typedef struct CthThreadStruct *CthThread;}
 \index{CthThread}
@@ -63,12 +32,6 @@ a function that returns nothing.}
 \desc{This is a type defined in {\tt threads.h}.  It represents
 a function that returns a CthThread.}
 
-\function{void CthInit()}
-\index{CthInit}
-\desc{Caution: you must call either {\tt ConverseInit} {\tt or} {\tt
-CthInit} before calling any of the thread functions described below,
-but you must {\tt not} call both.}
-
 \function{CthThread CthSelf()}
 \index{CthSelf}
 \desc{Returns the currently-executing thread.  Note: even the initial
@@ -76,29 +39,16 @@ flow of control that inherently existed when the program began
 executing {\tt main} counts as a thread.  You may retrieve that thread
 object using {\tt CthSelf} and use it like any other.}
 
-\function{void CthResume(CthThread t)}
-\index{CthResume}
-\desc{Immediately transfers control to thread {\tt t}.  Note:
-normally, the user of a thread package wouldn't explicitly choose
-which thread to transfer to.  Instead, the user would rely upon a
-scheduler to choose the next thread.  Therefore, this routine is
-primarily intended for people who are implementing schedulers, not for
-end-users.  End-users should probably call {\tt CthSuspend} or {\tt
-CthAwaken} (see below).  Likewise, programmers implementing locks,
-barriers, and other synchronization devices should also probably
-rely on {\tt CthSuspend} and {\tt CthAwaken}.}
-
 \function{CthThread CthCreate(CthVoidFn fn, void *arg, int size)}
 \index{CthCreate}
 \desc{Creates a new thread object.  The thread is not given control
-yet.  The thread is not passed to any scheduler.  When (and if) the
-thread eventually receives control, it will begin executing the
-specified function {\tt fn} with the specified argument.  The {\tt size}
+yet.  To make the thread execute, you must push it into the
+ready-queue, using CthAwaken below.  When (and if) the thread
+eventually receives control, it will begin executing the specified
+function {\tt fn} with the specified argument.  The {\tt size}
 parameter specifies the stack size in bytes, 0 means use the default
-size.
-
-Caution: almost all threads are created with CthCreate, but not all.
-In particular, the one initial thread of control that came into
+size.  Caution: almost all threads are created with CthCreate, but not
+all.  In particular, the one initial thread of control that came into
 existence when your program was first {\tt exec}'d was not created
 with {\tt CthCreate}, but it can be retrieved (say, by calling {\tt
 CthSelf} in {\tt main}), and it can be used like any other {\tt
@@ -114,45 +64,91 @@ thread suspends.  This is how a thread terminates itself: it calls
 
 \function{void CthSuspend()}
 \index{CthSuspend}
-\desc{This is part of the scheduler-interface.  When a scheduler is
-being used, threads should call {\tt CthSuspend} when they wish to
-give up control of the CPU.  {\tt CthSuspend} will then automatically
-transfer control to some other thread that wants the CPU.  {\tt
-CthSuspend} will select the thread to transfer control to by calling a
-user-supplied ``choose-next'' function (see {\tt CthSetStrategy}
-below).}
+\desc{Causes the current thread to stop executing, and control to be
+transferred to some other thread in the ready-queue.  The suspended
+thread will not start executing again until somebody pushes it into 
+the ready queue again, using CthAwaken below.}
 
 \function{void CthAwaken(CthThread t)}
 \index{CthAwaken}
-\desc{This is part of the scheduler-interface.  When a scheduler is
-being used, this function should be used to notify the scheduler that
-thread {\tt t} wants the CPU.  This will enable the scheduler to
-select thread {\tt t} for execution at some point in the future.
-In actuality, {\tt CthAwaken} simply calls the user-supplied ``awaken''
-function (see {\tt CthSetStrategy} below).  It is illegal to call
-{\tt CthAwaken} on a thread which has already been awakened, unless
-the thread has been scheduled since the last awaken.}
+\desc{Pushes a thread into the ready queue.  Caution: a thread must only
+be in the ready-queue once.  Pushing it in twice is a crashable error.}
+
+\function{void CthYield()}
+\index{CthYield}
+\desc{This function is part of the scheduler-interface.  It simply
+executes {\tt \{ CthAwaken(CthSelf()); CthSuspend(); \} }.  This combination
+gives up control temporarily, but ensures that control will eventually
+return.}
+
+\section{Thread Scheduling Hooks}
+
+Normally, when you CthAwaken a thread, it goes into the primary
+ready-queue: namely, the main Converse queue described in section
+\ref{schedqueue}.  However, it is possible to hook a thread to make
+it go into a different ready-queue.  That queue doesn't have to be
+priority-queue: it could be FIFO, or LIFO, or in fact it could handle
+its threads in any complicated order you desire.  This is a powerful
+way to implement your own scheduling policies for threads.
+
+To achieve this, you must first implement a new kind of ready-queue.
+You must implement a function that inserts threads into this queue.
+The function must have this prototype:
+
+{\bf void awakenfn(CthThread t);}
+
+When a thread suspends, it must choose a new thread to transfer control
+to.  You must implement a function that makes the decision: which thread
+should the current thread transfer to.  This function must have this
+prototype:
+
+{\bf CthThread choosefn();}
+
+Typically, the choosefn would choose a thread from your ready-queue.
+Alternately, it might choose to always transfer control to a central
+scheduling thread.
+
+You then configure individual threads to actually use this new
+ready-queue.  This is done using CthSetStrategy:
 
 \function{void CthSetStrategy(CthThread t, CthVoidFn awakenfn, CthThFn choosefn)}
 \index{CthSetStrategy}
-\desc{This is part of the scheduler-interface.  It should be used by
-the creator of thread {\tt t} to specify the scheduling functions to
-be used for thread {\tt t}.  The scheduling functions must have the
-following prototypes:
-\begin{itemize}
+\desc{Causes the thread to use the specified \param{awakefn} whenever
+you CthAwaken it, and the specified \param{choosefn} whenever you
+CthSuspend it.}
+
+CthSetStrategy alters the behavior of CthSuspend and CthAwaken.
+Normally, when a thread is awakened with CthAwaken, it gets inserted
+into the main ready-queue.  Setting the thread's {\tt awakenfn} will
+cause the thread to be inserted into your ready-queue instead.
+Similarly, when a thread suspends using CthSuspend, it normally
+transfers control to some thread in the main ready-queue.  Setting the
+thread's {\tt choosefn} will cause it to transfer control to a thread
+chosen by your {\tt choosefn} instead.
+
+You may reset a thread to its normal behavior using CthSetStrategyDefault:
+
+\function{void CthSetStrategyDefault(CthThread t)}
+\index{CthSetStrategyDefault}
+\desc{Restores the value of \param{awakefn} and \param{choosefn} to
+their default values.  This implies that the next time you CthAwaken
+the specified thread, it will be inserted into the normal ready-queue.}
 
-\item{{\tt void awakenfn(CthThread t);}}
+Keep in mind that this only resolves the issue of how threads get into
+your ready-queue, and how those threads suspend.  To actually make
+everything ``work out'' requires additional planning: you have to make
+sure that control gets transferred to everywhere it needs to go.
 
-\item{{\tt CthThread choosefn();}}
+Scheduling threads may need to use this function as well:
 
-\end{itemize}
-These functions must be provided on a per-thread basis.  (Eg, if you
-{\tt CthAwaken} a thread {\tt X}, then {\tt X}'s {\tt awakenfn} will
-be called.  If a thread {\tt Y} calls {\tt CthSuspend}, then thread
-{\tt Y}'s {\tt choosefn} will be called to pick the next thread.)  Of
-course, you may use the same functions for all threads (the common
-case), but the specification on a per-thread basis gives you maximum
-flexibility in controlling scheduling.
+\function{void CthResume(CthThread t)}
+\index{CthResume}
+\desc{Immediately transfers control to thread {\tt t}.  This routine is
+primarily intended for people who are implementing schedulers, not for
+end-users.  End-users should probably call {\tt CthSuspend} or {\tt
+CthAwaken} (see below).  Likewise, programmers implementing locks,
+barriers, and other synchronization devices should also probably rely
+on {\tt CthSuspend} and {\tt CthAwaken}.}
 
 A final caution about the {\tt choosefn}: it may only return a thread
 that wants the CPU, eg, a thread that has been awakened using the {\tt
@@ -169,17 +165,10 @@ done, and the {\tt choosefn} should call {\tt exit}.
 
 There is one minor exception to the rule stated above (``the scheduler
 may not resume a thread unless it has been declared that the thread
-wants the CPU using the {\tt awakefn}'').  If a thread {\tt t} is
-part of the scheduling module, it is permitted for the scheduling
-module to resume {\tt t} whenever it so desires: presumably, the
-scheduling module knows when its threads want the CPU.}
-
-\function{void CthYield()}
-\index{CthYield}
-\desc{This function is part of the scheduler-interface.  It simply
-executes {\tt \{ CthAwaken(CthSelf()); CthSuspend(); \} }.  This combination
-gives up control temporarily, but ensures that control will eventually
-return.}
+wants the CPU using the {\tt awakefn}'').  If a thread {\tt t} is part
+of the scheduling module, it is permitted for the scheduling module to
+resume {\tt t} whenever it so desires: presumably, the scheduling
+module knows when its threads want the CPU.
 
 \internal{
 \function{void CthSetVar(CthThread t, void **var, void *val)}
@@ -222,14 +211,3 @@ other.}
 {\tt CthSetVar} when {\tt t} is {\it not} executing.  Returns the value
 that {\tt var} will be set to when {\tt t} is running.}
 }
-
-\function{void CthSetStrategyDefault(CthThread t)}
-\index{CthSetStrategyDefault}
-\desc{This the simple scheduler provided to converse users as a
-convenience.  Calling this function on a thread {\tt t} causes thread
-{\tt t} to be scheduled by the built-in converse scheduler {\tt
-CsdScheduler}.  Awakening thread {\tt t} will cause it to be inserted
-into the {\tt CsdScheduler} queue, and it will then be resumed when it
-gets to the head of the queue.  If it then suspends, it will return
-control to the thread running the {\tt CsdScheduler}.}
-