Initial revision
authorMilind Bhandarkar <milind@cs.uiuc.edu>
Thu, 21 Sep 1995 15:36:17 +0000 (15:36 +0000)
committerMilind Bhandarkar <milind@cs.uiuc.edu>
Thu, 21 Sep 1995 15:36:17 +0000 (15:36 +0000)
doc/converse/cmi.tex [new file with mode: 0644]
doc/converse/ldb.tex [new file with mode: 0644]
doc/converse/manual.tex [new file with mode: 0644]
doc/converse/queue.tex [new file with mode: 0644]
doc/converse/scheduler.tex [new file with mode: 0644]
doc/converse/threads.tex [new file with mode: 0644]

diff --git a/doc/converse/cmi.tex b/doc/converse/cmi.tex
new file mode 100644 (file)
index 0000000..37a352f
--- /dev/null
@@ -0,0 +1,259 @@
+\section{Converse Machine Interface}
+
+\internal{
+\subsection{Initialization and Wrap-Up}
+
+\function{void CmiInit(int argc, char *argv[])}
+\desc{ This function initializes the machine interface. It should be
+called prior to any other CMI functions. 
+Multiple calls to this function in a process should
+be avoided. \param{argc} and \param{argv} are in similar format as passed to
+\param{main()}. They would be utilized by \param{CmiInit()} to initialize
+machine specific parameters such as number of processors.}
+
+\function{void CmiExit(void)}
+\desc{This function frees the resources acquired by CMI and wraps up CMI. 
+Any other CMI function should not be called after a call to this function.
+\note{It does not terminate the calling
+process. A separate call to \param{exit()} is needed after \param{CmiExit()} to
+achieve this.}}
+}
+
+
+\subsection{Message Handler Calls}
+
+
+\function {int CmiMsgHeaderSizeBytes(void)}
+\desc{This call returns the size of the message header in bytes.}
+\function {void CmiSetHandler(int *MessageBuffer, int HandlerId)}
+\desc{This call sets the handler field of a message to {\tt HandlerId}.}
+\function {HANDLER CmiGetHandlerFunction(int *MessageBuffer)}
+\desc{This call returns the handler function pointer for a message. This
+usually involves looking up a table using the handler-id stored in
+the message header at the sending processor. HANDLER is defined as 
+{\tt typedef void (*HANDLER)(void *)} .}
+
+\function {int CmiRegisterHandler(HANDLER HandlerFunction)}
+\desc{This call registers a message handler with the CMI and returns a
+handler index which can be subsequently used to specify the handler
+for a message.}
+
+
+\subsection{Timer Calls}
+
+\function{double CmiTimer(void)}
+\desc{Returns current value of the timer in seconds. This is
+typically the time spent since the \param{CmiInit()} call.
+The precision of this timer is the best available on the particular machine,
+and usually has at least microsecond accuracy.}
+
+\subsection{Point-To-Point Communication}
+
+\function{void *CmiGetSpecificMsg(int HandlerId)}
+\desc{This call waits until a message for the specified handler is
+available, and returns a pointer to the message buffer. Ownership of
+the message buffer is maintained with the CMI (e.g. another call to
+\param{CmiGetMsg()} or \param{CmiSpecificMsg()} can overwrite the
+contents of this buffer.).  The message handler should explicitly call
+\param{CmiGrabBuffer()} to acquire ownership of the message buffer.}
+
+\internal{
+\function{void *CmiGetMsg(void)}
+\desc{Retrieves a message from the network's message queue and
+returns a pointer to the message buffer. If network's message queue is
+empty, this function returns \param{(void *) 0}. Ownership of the
+message buffer is maintained with CMI. Another call to \param{CmiGetMsg()}
+or \param{CmiSpecificMsg()} could overwrite the contents of buffer.
+The calling function should
+explicitly call \param{CmiGrabBuffer()} to acquire ownership 
+the message buffer.} 
+}
+
+\internal{
+\function{void CmiDeliverMsgs(void)}
+\desc{ Retrieves messages from the network message queue and invokes 
+corresponding handler functions for arrived messages. This function 
+returns after the network message queue becomes empty. Even after
+calling the handler functions, ownership of the message is kept with
+CMI and the handler function should call \param{CmiGrabBuffer()} to
+acquire the message buffer.}
+}
+
+\function{CommHandle CmiAsyncSend(unsigned int destPE, unsigned int size, void *msg)}
+\desc{ Initiates an asynchronous send of \param{msg} of length
+\param{size} bytes to processor \param{destPE} and returns a
+communication handle which could be used to enquire the status of this
+communication. Message buffer for \param{mesg} should not be reused or freed
+until communication is complete.}
+
+\function{void CmiSyncSend(unsigned int destPE, unsigned int size, void *msg)}
+\desc{ Sends \param{msg} of size \param{size} bytes to processor
+\param{destPE}. Message buffer for \param{msg} could be reused after
+the call returns.}
+
+\function{int CmiAsyncMsgSent(CommHandle handle)}
+\desc{Returns the status of asynchronous send specified by
+communication handle \param{handle}.}
+
+\function{void CmiReleaseCommHandle(CommHandle handle)}
+\desc{ Releases the communication handle \param{handle} and
+associated resources. It does not free the message buffer.
+\param{handle} could be reused by CMI for another communication after
+this call succeeds.}
+
+\function{CommHandle CmiVectorSend(int destPE, int HandlerId, int len, int sizes[], void *DataArray[])}
+\desc{Initiates an asynchronous send of data to processor
+\param{destPE}.  The data consists of \param{len} pieces residing in
+different areas of memory, which are logically concatenated.  The
+\param{DataArray} array contains pointers to the pieces; the size of
+\param{DataArray[i]} is taken from \param{sizes[i]}. \param{HandlerId}
+is inserted at the appropriate place in the combined message and the
+corresponding handler will be invoked on the receiving side. 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
+\param{DataArray} should not be overwritten or freed before the
+communication is complete.}
+
+\function{void CmiGrabBuffer(void **pbuf)}
+\desc{ Transfers the ownership of the buffer pointed to by
+\param{*pbuf} to the calling procedure. If \param{*pbuf} points to a
+system buffer, CMI copies the buffer contents to newly allocated user
+space and updates \param{*pbuf} to point to the new buffer.}
+
+\subsection{Global Pointer}
+
+\function{int CmiGptrCreate(GlobalPtr *gptr, void *lptr, unsigned int size)}
+\desc{This function creates a global pointer by initializing contents of
+\param{*gptr} to point to memory on the local processor pointed to by
+\param{lptr} of \param{size} bytes. \param{*gptr} could then be sent to other 
+processors, and could be used by \param{CmiGet()} and \param{CmiPut()}
+to read and write this memory by remote processors. This functions returns
+a positive integer on success.}
+
+\function{void *CmiGptrDref(GlobalPtr *gptr)}
+\desc{This function returns the address of local memory associated
+with global pointer \param{gptr}.}
+
+\function{int CmiSyncGet(GlobalPtr *gptr, void *lptr, unsigned int size)}
+\desc{Copies \param{size} bytes from 
+memory pointed to by global pointer \param{gptr}
+to local memory pointed to by \param{lptr}. 
+This is a synchronous operation and the calling processor blocks until
+the data is transferred to local memory. This function returns
+a positive integer on success.}
+
+\function{CommHandle CmiGet(GlobalPtr *gptr, void *lptr, unsigned int size)}
+\desc{Initiates copying of \param{size} bytes from 
+memory pointed to by global pointer \param{gptr}
+to local memory pointed to by \param{lptr}. 
+This function returns a  communication handle which could be used
+to  enquire about the status of this operation.}
+
+\function{CommHandle CmiPut(GlobalPtr *gptr, void *lptr, unsigned int size)}
+\desc{Initiates copying of \param{size} bytes from a processor's local
+memory pointed to by \param{lptr} to the memory pointed to by global
+pointer \param{gptr}.  This function returns a  communication handle
+which could be used to  enquire about the status of this operation.}
+
+\subsection{Group Communication}
+
+\function{void CmiSyncBroadcast(unsigned int size, void *msg)}
+\desc{Sends \param{msg} of length \param{size} bytes to all processors
+excluding the processor on which the caller resides. }
+
+\function{void CmiSyncBroadcastAllAndFree(unsigned int size, void *msg)}
+\desc{Sends \param{msg} of length \param{size} bytes to all processors
+including the processor on which the caller resides. This function
+frees the message buffer for \param{msg} before returning, so
+\param{msg} must point to a dynamically allocated buffer.}
+
+\function{void CmiSyncBroadcastAll(unsigned int size, void *msg)}
+\desc{Sends \param{msg} of length \param{size} bytes to all processors
+including the processor on which the caller resides. This function
+does not free the message buffer for \param{msg}.}
+
+\function{CommHandle CmiAsyncBroadcast(unsigned int size, void *msg)}
+\desc{ Initiates asynchronous broadcast of message \param{msg} of
+length \param{size} bytes to all processors excluding the processor on
+which the caller resides. It returns a communication handle which
+could be used to check the status of this send using
+\param{CmiAsyncMsgSent()}. \param{msg} should not be overwritten or
+freed before the communication is complete.}
+
+\function{CommHandle CmiAsyncBroadcastAll(unsigned int size, void *msg)}
+\desc{ Initiates asynchronous broadcast of message \param{msg} of
+length \param{size} bytes to all processors including the processor on
+which the caller resides. It returns a communication handle which
+could be used to check the status of this send using
+\param{CmiAsyncMsgSent()}. \param{msg} should not be overwritten or
+freed before the communication is complete.}
+
+\subsection{Processor Ids}
+
+\function{int CmiNumPe(void)}
+\desc{ Returns total number of processors in the machine on which the 
+parallel program is being run.}
+
+\function{int CmiMyPe(void)}
+\desc{ Returns the logical processor identifier of processor on which the 
+caller resides. A processor Id is between \param{0} and \param{CmiNumPe()-1}.}
+
+\subsection{Input/Output}
+
+\function{void CmiPrintf(char *format, arg1, arg2, ...)}
+\desc{This function does an atomic \param{printf()} on \param{stdout}. 
+On machine with host, this is implemented on top of the messaging 
+layer using asynchronous sends.}
+
+\function{void CmiScanf(char *format, void *arg1, void *arg2, ...)}
+\desc{This function performs an atomic \param{scanf} from \param{stdin}.
+The processor, on which the caller resides, blocks for input. On machines with
+host, this is implemented on top of the messaging layer using asynchronous
+send and blocking receive.}
+
+\function{void CmiError(char *format, arg1, arg2, ...)}
+\desc{This function does an atomic \param{printf()} on \param{stderr}. 
+On machine with host, this is implemented on top of the messaging 
+layer using asynchronous sends.}
+
+\subsection{Processor Groups}
+
+\function{void CmiPgrpCreate(Pgrp *group)}
+\desc{Creates a processor-group with calling processsor as the root processor.}
+
+\function{void CmiPgrpDestroy(Pgrp *group)}
+\desc{Frees resources associated with a processor group \param{group}.}
+
+\function{void CmiAddChildren(Pgrp *group, int penum, int size, int procs[])}
+\desc{Adds \param{size} processors from array \param{procs[]} to the
+processor-group \param{group} as children of processor penum. This function
+could be called only by the root processor of processor-group \param{group}.}
+
+\function{CommHandle CmiAsyncMulticast(Pgrp *group, unsigned int size, void *msg)}
+\desc{ Initiates asynchronous broadcast of message \param{msg} of
+length \param{size} bytes to all processors belonging to \param{group}
+excluding the processor on which the caller resides. It returns a
+communication handle which could be used to check the status of this
+send using \param{CmiAsyncMsgSent()}. \param{msg} should not be
+overwritten or freed before the communication is complete. \note{Caller
+need not belong to \param{group}.}} 
+
+\function{int CmiPgrpRoot(Pgrp *group)}
+\desc{Returns the processor id of root of processor-group \param{group}. }
+
+\function{int CmiNumChildren(Pgrp *group, int penum)}
+\desc{ Returns  number of children of processor \param{penum} 
+in the processor-group \param{group}.}
+
+\function{int CmiParent(Pgrp *group, int penum)}
+\desc{ Returns  processor id of parent of processor \param{penum} 
+in the processor-group \param{group}.}
+
+\function{void CmiChildren(Pgrp *group, int node, int *children)}
+\desc{Fills in array \param{children} with processor ids of all the
+children processor \param{node} in processor-group \param{group}. This
+array should atleast be of size \param{CmiNumChildren()}.}
diff --git a/doc/converse/ldb.tex b/doc/converse/ldb.tex
new file mode 100644 (file)
index 0000000..3811098
--- /dev/null
@@ -0,0 +1,39 @@
+
+\section{Load Balancer Calls}
+
+\internal{
+\function {void ClbInit(void)}
+Routine called at scheduler startup to allow the load balancer to
+register its own message handlers.
+}
+
+\function {void ClbEnqueue(Message *msg, FunctionPtr send\_func)}
+Function called by a handler to let the load balancer know about a
+``seed'' message. If the seed is to be processed locally, the
+load balancer will
+enqueue it in the scheduler's queue to be eventually executed.
+{\sf send\_func} specifies the function
+which should be used to send the seed to another processor
+if it is not to be processed locally.
+
+\function {void ClbEnqueuePrio(Message *msg, FunctionPtr send\_func,
+void *prio, int len)} 
+Same as {\sf ClbEnqueue()}, except that a priority {\sf prio} of length
+{\sf len} bytes is associated with the message.
+
+
+%The most general load balancing scheme will have three opportunities
+%to migrate load.  The first will be when {\sf ClbEnQueue()} is called.
+%This routine will either immediately send the message elsewhere for
+%processing, or enqueue it in a local data structure.  A token message
+%will then be enqueued with the scheduler to reactivate the load
+%balancing in order to execute the seed message at the appropriate
+%time.  The second opportunity for load balancing occurs when the load
+%balancing module receives a request from the load balancing module on
+%another processor for some work.  When this occurs, a message will be
+%delivered to the requesting node from the load balance queue, and the
+%token message in the scheduler queue will be marked as invalid.  The
+%third opportunity occurs when a token message is removed from the
+%scheduler queue.  Control will return to the load balancing module,
+%which could then choose to send seed messages to another host.
+
diff --git a/doc/converse/manual.tex b/doc/converse/manual.tex
new file mode 100644 (file)
index 0000000..ef27e14
--- /dev/null
@@ -0,0 +1,58 @@
+\documentstyle[11pt,epsf]{article}
+\setcounter{topnumber}{2}
+\def\topfraction{1}
+\setcounter{bottomnumber}{1}
+\def\bottomfraction{1}
+\setcounter{totalnumber}{3}
+\def\textfraction{0.2}
+\def\floatpagefraction{0.8}
+\setlength{\parindent}{0.4in}
+\setlength{\parskip}{0.1in}
+\setlength{\textwidth}{6.5in}
+\setlength{\itemindent}{1in}
+\setlength{\textheight}{9.5in}
+\addtolength{\oddsidemargin}{0in}
+\addtolength{\topmargin}{-0.4in}
+\parskip 0.05in
+\newcommand{\internal}[1]{ }
+\newcommand{\function}[1]{{\noindent{\sf {#1}}\\}}
+\newcommand{\param}[1]{{\tt {#1}}}
+\newcommand{\note}[1]{\noindent{(Note: {\em {#1}})}}
+%\newcommand{\desc}[1]{{\bf Description:}{#1}}
+\newcommand{\desc}[1]{{#1}}
+
+\newcommand{\basea}{\renewcommand{\baselinestretch}{1.0}}
+\newcommand{\baseb}{\renewcommand{\baselinestretch}{1.8}}
+\newcommand{\mycomment}[1]{} 
+\basea
+\input{psfig}
+\textwidth 6.4in
+\textheight 8.9in
+\topmargin -.4in
+\oddsidemargin 0.25in
+\evensidemargin 0.25in
+\parskip 0.1in
+
+\title{{\bf Converse API Reference}}
+
+\author{}
+
+\date{ }
+
+
+\begin{document}
+
+\maketitle
+
+\input{scheduler}
+\input{queue}
+\input{cmi}
+\input{threads}
+\input{ldb}
+
+\end{document}
diff --git a/doc/converse/queue.tex b/doc/converse/queue.tex
new file mode 100644 (file)
index 0000000..e69de29
diff --git a/doc/converse/scheduler.tex b/doc/converse/scheduler.tex
new file mode 100644 (file)
index 0000000..5f754ed
--- /dev/null
@@ -0,0 +1,45 @@
+
+\section{Initialization and Completion}
+
+
+\function {void ConverseInit(void)}
+This call initializes all Converse components, such as the scheduler,
+machine interface, and other libraries. This must be the first Converse
+call in the entire program.
+
+
+\function {void ConverseExit(void)}
+This call wraps up all Converse components. No Converse call may be made
+after this call.
+
+
+
+
+\section{Scheduler Calls}
+
+%These are the calls/macros provided by the Converse scheduler.
+%All declarations are in converse.h.
+
+\internal{
+\function {void CsdInit(void)}
+This call initializes the Converse scheduler, it is called from
+ConverseInit().
+}
+
+\function {void CsdScheduler(int NumberOfMessages)}
+This call invokes the Converse scheduler. The {\tt NumberOfMessages}
+parameter specifies how many messages should be processed (i.e. delivered
+to their handlers). If set to -1, the scheduler continues processing
+messages until CsdExitScheduler() is called from a message handler.
+
+\function {void CsdExitScheduler(void)}
+This call causes the scheduler
+to stop processing messages when control has returned back to it.
+The scheduler then returns to its calling routine.
+
+\function {void CsdEnqueue(void *Message)}
+This call enqueues a message in the scheduler's queue, to be processed
+in accordance with the queueing strategy. 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.
diff --git a/doc/converse/threads.tex b/doc/converse/threads.tex
new file mode 100644 (file)
index 0000000..c727ab4
--- /dev/null
@@ -0,0 +1,238 @@
+\section{Message Manager Calls}
+
+To use the following calls, include the file ``SM.h''.
+
+\function{MSG\_MNGR *CmmNew(void)}
+\desc{This call returns a new initialized message manager that can store and 
+retrieve messages.}
+
+\function{CmmPut(MSG\_MNGR *mm, void *msg, int tag, int size)}
+\hspace{2in} (AND)\\
+\function{CmmPut2(MSG\_MNGR *mm, void *msg, int tag1, int tag2, int size)}
+\desc{This call puts the message \param{msg} into the message manager 
+\param{mm}'s data structure along with its \param{tag} and \param{size} 
+fields.}
+
+\note{In the following calls, \param{tag} parameters may be wildcarded by 
+placing a value of {\bf CmmWildCard} in them. The actual values of the tag(s) of 
+the message, if any, are returned in the \param{rettag} parameters if they are
+non-NULL.}
+
+\function{int CmmProbe(MSG\_MNGR *mm, int tag, int *rettag)}
+\hspace{2in} (AND)\\
+\function{int CmmProbe(MSG\_MNGR *mm, int tag1, int tag2, int *rettag1, int *rettag2)}
+\desc{This call returns the size of the message with tag \param{tag} that is 
+stored in the message manager \param{mm}, and returns -1 if such a message 
+is not found.}
+
+\function{int CmmGet(MSG\_MNGR *mm, void *addr, int tag, int size, int *rettag)}
+\hspace{2in} (AND)\\
+\function{int CmmGet2(MSG\_MNGR *mm, void *addr, int tag1, int tag2, int size, int *rettag1, int *rettag2)}
+\desc{This call copies at most \param{size} bytes of a message stored in the 
+message manager \param{mm} with the tag(s) into the address pointed to by 
+\param{addr}. The return value is the length of the message.}
+
+\function{int CmmGetPtr(MSG\_MNGR *mm, void *addr, int tag, int *rettag)}
+\hspace{2in} (AND)\\
+\function{int CmmGetPtr2(MSG\_MNGR *mm, void **addr, int tag1, int tag2, int *rettag1, int *rettag2)}
+\desc{This call allocates memory for the message in the message manager 
+\param{mm} with the tag(s) and returns this address in \param{*addr}. 
+The return value is the length of the message.}
+
+\section{Thread Manipulation}
+
+To use the following calls, include the file ``thr\_defns.h''.
+
+\subsection{Thread Object Calls}
+
+\function{int CthInit(void)}
+\desc{This call initializes some variables that are used by the thread calls 
+library, and should be called before any other thread calls are made.}
+
+\function{THREAD *CthCreate(THRFN fn, void *arg)}
+\hspace{2in}
+  (AND)\\
+\function{THREAD *CthCreateOfSize(THRFN fn, void *arg, int stacksize)}
+\desc{These are calls to create a thread. This function takes a
+function pointer \param{fn} and its void pointer argument \param{arg}.
+The second call can be used if a stack of size other than the standard
+STACKSIZE is to be allocated for the thread.}
+
+\function{int CthResume(THREAD *thr)}
+\desc{This call causes an immediate context switch to the specified
+thread {\tt thr}. The thread {\tt thr} continues to run until it, in
+turn, gives up control using CthResume or some variant of CthResume.}
+
+\function{int CthSuspend(void)}
+\desc{This function is a variant of CthResume --- it immediately causes
+a context-switch to some other thread.  This function differs from
+CthResume in only one way: it makes its own decision about which thread
+to transfer control to.  It always chooses a thread from a "ready pool"
+which is maintained by the user.
+
+By default, CthSuspend always selects the thread which has been in
+its ready-pool the longest.  This selection strategy may be altered
+by the user on a per-thread basis by calling CthSetStrategy below.}
+
+\function{int CthAwaken(THREAD thr)}
+\desc{The thread is added to
+CthSuspend's ready-pool.  This essentially constitutes permission for
+CthSuspend to transfer control to thread {\tt thr}.  CthAwaken must only
+be called on a thread when it can be shown that it is indeed acceptable
+for the thread to continue execution.}
+
+\function{THREAD *CthSetStrategy(THREAD thr, THRFN suspfn, void *susparg, THRFN awakefn, void *awakearg)}
+\desc{CthAwaken and CthSuspend work together.  By default, CthAwaken
+``adds a thread to the ready pool'' by pushing it on a FIFO queue.  By
+default, CthSuspend ``finds a thread in the ready-pool'' by popping
+this same FIFO queue.  Together, this behavior guarantees that
+CthSuspend always can find a thread which is in the ready-pool.
+
+Using CthSetStrategy, you may alter the way CthAwaken and CthSuspend
+work together.  The purpose of such modification is to give you
+control over the order in which CthSuspend selects threads for
+execution.  Note that you should not otherwise change the semantics
+of CthAwaken and CthSuspend: only the order of selection should be
+altered.
+
+Each time a CthAwaken is performed on a thread t, thread t's
+{\tt awakefn} is called.  The {\tt awakefn} must perform the task of
+CthAwaken: it must store the thread t in a location such that it can
+later be found by CthSuspend.
+
+Each time a thread t calls CthSuspend, thread t's {\tt suspfn} is
+called.  The {\tt suspfn} must look for a ready thread to transfer
+control to.  It does this by looking in a location where CthAwaken
+stores threads.  Once found, the {\tt suspfn} must resume the thread
+using CthResume.
+
+Note that CthSetStrategy overrides the behavior of CthAwaken and
+CthSuspend only on a per-thread basis.  In a modular program, it is
+therefore possible for each module to control the order in which
+its own threads are scheduled.}
+
+\mycomment{
+% Sanjay wanted this out.
+\function{QUEUE *CthGetFifo()}
+\desc{Returns the FIFO queue on which CthAwaken stores threads by
+default.  Naturally, this is the same queue that CthSuspend looks on
+for ready threads by default.  The queue can be managed using the
+queue routines below.}
+}
+
+\function{int CthExit(void)}
+\desc{This call is used by a thread that has finished execution.  The
+thread ceases to exist, and transfer is controlled to some other
+thread using CthSuspend.  If the thread that exited had a special
+scheduling strategy, that strategy is used to choose the next thread.}
+
+\function{int CthYield(void)}
+\desc{This call simply calls CthAwaken on the current thread (thereby
+adding the current thread to CthSuspend's ready-pool), after which it
+calls CthSuspend.  This may cause a transfer of control to another
+thread.  Control will probably come back to the thread that yielded,
+given that it is now in CthSuspend's ready-pool.}
+
+\function{THREAD *CthSelf(void)}
+\desc{This call returns a pointer to the currently executing thread.}
+
+\mycomment{
+% Sanjay wanted this out
+\subsection{Elementary Queues}
+This subsection describes an elementary queue of threads that can be used
+to manage lists of threads.
+
+\function{QUEUE *CthNewQueue()}
+\desc{This call returns a new empty queue of threads.}
+
+\function{int CthQueueInit(QUEUE *queue)}
+\desc{This call initializes a queue that has been allocated earlier.}
+
+\function{int CthQueueEmpty(QUEUE *queue)}
+\desc{This call returns 1 if the queue \param{queue} is empty and 0 if not.}
+
+\function{int CthQAddThread(QUEUE *queue, THREAD *thr)}
+\desc{This call adds the thread \param{thr} to the queue \param{queue}.}
+
+\function{THREAD *CthQPop(QUEUE *queue)}
+\desc{This call pops a thread from the front of the queue and returns NULL if 
+the queue is empty.}
+}
+\section{Synchronization Mechanisms}
+To use the following calls, include the file ``sync.h''
+
+\subsection{Locks}
+
+Locks (or mutexes) are synchronization mechanisms that can be used by user 
+programs to provide mutual exclusion to critical sections. Threads that attempt
+to ``lock'' such a variable are suspended if the lock is already taken and are
+awakened when the lock becomes available to them.
+
+\function{LOCK *CtsNewLock(void)}
+\desc{This call can be used to create a new lock variable.}
+
+\function{CtsLockInit(LOCK *lock)}
+\desc{This call can be used to initialize a lock \param{lock} that was 
+earlier allocated.}
+
+\function{int CtsTryLock(LOCK *lock)}
+\desc{This call is a nonblocking attempt to lock \param{lock}. It returns 
+1 immediately if \param{lock} is available after making the current thread 
+\param{lock}'s owner and returns 0 if \param{lock} is already locked.}
+
+\function{int CtsLock(LOCK *lock)}
+\desc{This call is used by a thread to wait until it obtains the ownership of 
+\param{lock}. Several threads making this call may be queued up at the lock,
+which is then ``given'' to each in turn.}
+
+\function{int CtsUnLock(LOCK *lock)}
+\desc{This call is used by a thread to relinquish the control of \param{lock}.
+An error value is returned if the thread attempts the unlock is not 
+\param{lock}'s owner.}
+
+\subsection{Condition Variables}
+
+Condition variables are synchronization mechanisms that are used to implement 
+trigger like functionality. Threads can wait on a condition variable. Other
+threads can either signal or broadcast this condition variable causing the 
+awakening of either one or all of the threads waiting on this variable.
+
+\function{CONDN *CtsNewCondn(void)}
+\desc{This call returns a new initialized condition variable.}
+
+\function{int CtsCondnInit(CONDN *condn)}
+\desc{This call can be used to initialize a condition variable that was earlier
+allocated. This call causes all the waiting threads on this condition variable 
+to be awakened.}
+
+\function{int CtsCondnWait(CONDN *condn)}
+\desc{This call is used by thread that want to wait on the condition 
+variable \param{condn}.}
+
+\function{int CtsCondnSignal(CONDN *condn)}
+\desc{This call releases one of the threads waiting on the condition 
+variable \param{condn}.}
+
+\function{int CtsCondnBroadcast(CONDN *condn)}
+\desc{This call releases all the threads waiting on the condition variable
+\param{condn}.}
+
+\subsection{Barriers}
+Barriers are a specialization of condition variables. A barrier is 
+a condition variable whose {\em k}th wait is a broadcast for some initial k.
+That is, the barrier waits for k threads to reach a particular point before it
+lets them all go.
+
+\function{BARRIER *CtsNewBarrier(void)}
+\desc{can be used to create a new barrier.}
+
+\function{int CtsBarrierReinit(BARRIER *bar, int num)}
+\desc{This call (re)initializes the barrier \param{bar} to free any 
+threads waiting on it and then to await the arrival of {\tt num} threads.}
+
+\function{int CtsAtBarrier(BARRIER *bar)}
+\desc{Following the initialization of the barrier, the {\tt num} participating 
+threads need to make this call before they can proceed beyond this point in 
+the program. This call hence blocks all but the last thread to make this call, 
+and awakens them all upon the arrival of this thread at the barrier.}
+