Subsections

3 . Threads

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 for creating threads, destroying threads, yielding, suspending, and awakening a suspended thread. In addition, it provides facilities whereby you can write your own thread schedulers.

3 . 1 Basic Thread Calls

typedef struct CthThreadStruct *CthThread;
This is an opaque type defined in converse.h . It represents a first-class thread object. No information is publicized about the contents of a CthThreadStruct.

typedef void (CthVoidFn)();
This is a type defined in converse.h . It represents a function that returns nothing.

typedef CthThread (CthThFn)();
This is a type defined in converse.h . It represents a function that returns a CthThread.

CthThread CthSelf()
Returns the currently-executing thread. Note: even the initial flow of control that inherently existed when the program began executing main counts as a thread. You may retrieve that thread object using CthSelf and use it like any other.

CthThread CthCreate(CthVoidFn fn, void *arg, int size)
Creates a new thread object. The thread is not given control yet. To make the thread execute, you must push it into the scheduler queue, using CthAwaken below. When (and if) the thread eventually receives control, it will begin executing the specified function fn with the specified argument. The 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 existence when your program was first exec 'd was not created with CthCreate , but it can be retrieved (say, by calling CthSelf in main ), and it can be used like any other CthThread .

CthThread CthCreateMigratable(CthVoidFn fn, void *arg, int size)
Create a thread that can later be moved to other processors. Otherwise identical to CthCreate.

This is only a hint to the runtime system; some threads implementations cannot migrate threads, others always create migratable threads. In these cases, CthCreateMigratable is equivalent to CthCreate.

CthThread CthPup(pup_er p,CthThread t)
Pack/Unpack a thread. This can be used to save a thread to disk, migrate a thread between processors, or checkpoint the state of a thread.

Only a suspended thread can be Pup'd. Only a thread created with CthCreateMigratable can be Pup'd.

void CthFree(CthThread t)
Frees thread t . You may ONLY free the currently-executing thread (yes, this sounds strange, it's historical). Naturally, the free will actually be postponed until the thread suspends. To terminate itself, a thread calls CthFree(CthSelf()) , then gives up control to another thread.

void CthSuspend()
Causes the current thread to stop executing. The suspended thread will not start executing again until somebody pushes it into the scheduler queue again, using CthAwaken below. Control transfers to the next task in the scheduler queue.

void CthAwaken(CthThread t)
Pushes a thread into the scheduler queue. Caution: a thread must only be in the queue once. Pushing it in twice is a crashable error.

void CthAwakenPrio(CthThread t, int strategy, int priobits, int *prio)
Pushes a thread into the scheduler queue with priority specified by priobits and prio and queueing strategy strategy . Caution: a thread must only be in the queue once. Pushing it in twice is a crashable error. prio is not copied internally, and is used when the scheduler dequeues the message, so it should not be reused until then.

void CthYield()
This function is part of the scheduler-interface. It simply executes { CthAwaken(CthSelf()); CthSuspend(); } . This combination gives up control temporarily, but ensures that control will eventually return.

void CthYieldPrio(int strategy, int priobits, int *prio)
This function is part of the scheduler-interface. It simply executes
{CthAwakenPrio(CthSelf(),strategy,priobits,prio);CthSuspend();}
This combination gives up control temporarily, but ensures that control will eventually return.

CthThread CthGetNext(CthThread t)
Each thread contains space for the user to store a ``next'' field (the functions listed here pay no attention to the contents of this field). This field is typically used by the implementors of mutexes, condition variables, and other synchronization abstractions to link threads together into queues. This function returns the contents of the next field.

void CthSetNext(CthThread t, CthThread next)
Each thread contains space for the user to store a ``next'' field (the functions listed here pay no attention to the contents of this field). This field is typically used by the implementors of mutexes, condition variables, and other synchronization abstractions to link threads together into queues. This function sets the contents of the next field.

3 . 2 Thread Scheduling and Blocking Restrictions

Converse threads use a scheduler queue, like any other threads package. We chose to use the same queue as the one used for Converse messages (see Section  2.9 ). Because of this, thread context-switching will not work unless there is a thread polling for messages. A rule of thumb, with Converse , it is best to have a thread polling for messages at all times. In Converse 's normal mode (see Section  1 ), this happens automatically. However, in user-calls-scheduler mode, you must be aware of it.

There is a second caution associated with this design. There is a thread polling for messages (even in normal mode, it's just hidden in normal mode). The continuation of your computation depends on that thread -- you must not block it. In particular, you must not call blocking operations in these places:

These restrictions are usually easy to avoid. For example, if you wanted to use a blocking operation inside a Converse handler, you would restructure the code so that the handler just creates a new thread and returns. The newly-created thread would then do the work that the handler originally did.

3 . 3 Thread Scheduling Hooks

Normally, when you CthAwaken a thread, it goes into the primary ready-queue: namely, the main Converse queue described in Section  2.9 . 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:

void awakenfn(CthThread t, int strategy, int priobits, int *prio);

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:

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:

void CthSetStrategy(CthThread t, CthAwkFn awakenfn, CthThFn choosefn)
Causes the thread to use the specified awakefn whenever you CthAwaken it, and the specified 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 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 choosefn will cause it to transfer control to a thread chosen by your choosefn instead.

You may reset a thread to its normal behavior using CthSetStrategyDefault:

void CthSetStrategyDefault(CthThread t)
Restores the value of awakefn and 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.

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.

Scheduling threads may need to use this function as well:

void CthResume(CthThread t)
Immediately transfers control to thread t . This routine is primarily intended for people who are implementing schedulers, not for end-users. End-users should probably call CthSuspend or CthAwaken (see below). Likewise, programmers implementing locks, barriers, and other synchronization devices should also probably rely on CthSuspend and CthAwaken .

A final caution about the choosefn : it may only return a thread that wants the CPU, eg, a thread that has been awakened using the awakefn . If no such thread exists, if the choosefn cannot return an awakened thread, then it must not return at all: instead, it must wait until, by means of some pending IO event, a thread becomes awakened (pending events could be asynchronous disk reads, networked message receptions, signal handlers, etc). For this reason, many schedulers perform the task of polling the IO devices as a side effect. If handling the IO event causes a thread to be awakened, then the choosefn may return that thread. If no pending events exist, then all threads will remain permanently blocked, the program is therefore done, and the choosefn should call 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 awakefn ''). If a thread t is part of the scheduling module, it is permitted for the scheduling module to resume t whenever it so desires: presumably, the scheduling module knows when its threads want the CPU.