pth.pod

Linux下的中文输入法

signal (for kernel-space threads) or a software interrupt signal (for
user-space threads), like C<SIGALRM> or C<SIGVTALRM>. In non-preemptive
scheduling, once a thread received control from the scheduler it keeps
it until either a blocking situation occurs (again a function call which
would block and instead switches back to the scheduler) or the thread
explicitly yields control back to the scheduler in a cooperative way.

=item B<o> B<concurrency> vs. B<parallelism>

Concurrency exists when at least two threads are I<in progress> at the
same time. Parallelism arises when at least two threads are I<executing>
simultaneously. Real parallelism can be only achieved on multiprocessor
machines, of course. But one also usually speaks of parallelism or
I<high concurrency> in the context of preemptive thread scheduling
and of I<low concurrency> in the context of non-preemptive thread
scheduling.

=item B<o> B<responsiveness>

The responsiveness of a system can be described by the user visible
delay until the system responses to an external request. When this delay
is small enough and the user doesn't recognize a noticeable delay,
the responsiveness of the system is considered good. When the user
recognizes or is even annoyed by the delay, the responsiveness of the
system is considered bad.

=item B<o> B<reentrant>, B<thread-safe> and B<asynchronous-safe> functions

A reentrant function is one that behaves correctly if it is called
simultaneously by several threads and then also executes simultaneously.
Functions that access global state, such as memory or files, of course,
need to be carefully designed in order to be reentrant. Two traditional
approaches to solve these problems are caller-supplied states and
thread-specific data.

Thread-safety is the avoidance of I<data races>, i.e., situations
in which data is set to either correct or incorrect value depending
upon the (unpredictable) order in which multiple threads access and
modify the data. So a function is thread-safe when it still behaves
semantically correct when called simultaneously by several threads (it
is not required that the functions also execute simultaneously). The
traditional approach to achieve thread-safety is to wrap a function body
with an internal mutual exclusion lock (aka `mutex'). As you should
recognize, reentrant is a stronger attribute than thread-safe, because
it is harder to achieve and results especially in no run-time contention
between threads. So, a reentrant function is always thread-safe, but not
vice versa.

Additionally there is a related attribute for functions named
asynchronous-safe, which comes into play in conjunction with signal
handlers. This is very related to the problem of reentrant functions. An
asynchronous-safe function is one that can be called safe and without
side-effects from within a signal handler context. Usually very few
functions are of this type, because an application is very restricted in
what it can perform from within a signal handler (especially what system
functions it is allowed to call). The reason mainly is, because only a
few system functions are officially declared by POSIX as guaranteed to
be asynchronous-safe. Asynchronous-safe functions usually have to be
already reentrant.

=back

=head2 User-Space Threads

User-space threads can be implemented in various way. The two
traditional approaches are:

=over 3

=item B<1.>

B<Matrix-based explicit dispatching between small units of execution:>

Here the global procedures of the application are split into small
execution units (each is required to not run for more than a few
milliseconds) and those units are implemented by separate functions.
Then a global matrix is defined which describes the execution (and
perhaps even dependency) order of these functions. The main server
procedure then just dispatches between these units by calling one
function after each other controlled by this matrix. The threads are
created by more than one jump-trail through this matrix and by switching
between these jump-trails controlled by corresponding occurred events.

This approach gives the best possible performance, because one can
fine-tune the threads of execution by adjusting the matrix, and the
scheduling is done explicitly by the application itself. It is also very
portable, because the matrix is just an ordinary data structure, and
functions are a standard feature of ANSI C.

The disadvantage of this approach is that it is complicated to write
large applications with this approach, because in those applications
one quickly gets hundreds(!) of execution units and the control flow
inside such an application is very hard to understand (because it is
interrupted by function borders and one always has to remember the
global dispatching matrix to follow it). Additionally, all threads
operate on the same execution stack. Although this saves memory, it is
often nasty, because one cannot switch between threads in the middle of
a function. Thus the scheduling borders are the function borders.

=item B<2.>

B<Context-based implicit scheduling between threads of execution:>

Here the idea is that one programs the application as with forked
processes, i.e., one spawns a thread of execution and this runs from the
begin to the end without an interrupted control flow. But the control
flow can be still interrupted - even in the middle of a function.
Actually in a preemptive way, similar to what the kernel does for the
heavy-weight processes, i.e., every few milliseconds the user-space
scheduler switches between the threads of execution. But the thread
itself doesn't recognize this and usually (except for synchronization
issues) doesn't have to care about this.

The advantage of this approach is that it's very easy to program,
because the control flow and context of a thread directly follows
a procedure without forced interrupts through function borders.
Additionally, the programming is very similar to a traditional and well
understood fork(2) based approach.

The disadvantage is that although the general performance is increased,
compared to using approaches based on heavy-weight processes, it is decreased
compared to the matrix-approach above. Because the implicit preemptive
scheduling does usually a lot more context switches (every user-space context
switch costs some overhead even when it is a lot cheaper than a kernel-level
context switch) than the explicit cooperative/non-preemptive scheduling.
Finally, there is no really portable POSIX/ANSI-C based way to implement
user-space preemptive threading. Either the platform already has threads,
or one has to hope that some semi-portable package exists for it. And
even those semi-portable packages usually have to deal with assembler
code and other nasty internals and are not easy to port to forthcoming
platforms.

=back

So, in short: the matrix-dispatching approach is portable and fast, but
nasty to program. The thread scheduling approach is easy to program,
but suffers from synchronization and portability problems caused by its
preemptive nature.

=head2 The Compromise of Pth

But why not combine the good aspects of both approaches while avoiding
their bad aspects? That's the goal of B<Pth>. B<Pth> implements
easy-to-program threads of execution, but avoids the problems of
preemptive scheduling by using non-preemptive scheduling instead.

This sounds like, and is, a useful approach. Nevertheless, one has to
keep the implications of non-preemptive thread scheduling in mind when
working with B<Pth>. The following list summarizes a few essential
points:

=over 2

=item B<o>

B<Pth provides maximum portability, but NOT the fanciest features>.

This is, because it uses a nifty and portable POSIX/ANSI-C approach for
thread creation (and this way doesn't require any platform dependent
assembler hacks) and schedules the threads in non-preemptive way (which
doesn't require unportable facilities like C<SIGVTALRM>). On the other
hand, this way not all fancy threading features can be implemented.
Nevertheless the available facilities are enough to provide a robust and
full-featured threading system.

=item B<o>

B<Pth increases the responsiveness and concurrency of an event-driven
application, but NOT the concurrency of number-crunching applications>.

The reason is the non-preemptive scheduling. Number-crunching
applications usually require preemptive scheduling to achieve
concurrency because of their long CPU bursts. For them, non-preemptive
scheduling (even together with explicit yielding) provides only the old
concept of `coroutines'. On the other hand, event driven applications
benefit greatly from non-preemptive scheduling. They have only short
CPU bursts and lots of events to wait on, and this way run faster under
non-preemptive scheduling because no unnecessary context switching
occurs, as it is the case for preemptive scheduling. That's why B<Pth>
is mainly intended for server type applications, although there is no
technical restriction.

=item B<o>

B<Pth requires thread-safe functions, but NOT reentrant functions>.

This nice fact exists again because of the nature of non-preemptive
scheduling, where a function isn't interrupted and this way cannot be
reentered before it returned. This is a great portability benefit,
because thread-safety can be achieved more easily than reentrance
possibility. Especially this means that under B<Pth> more existing
third-party libraries can be used without side-effects than it's the case
for other threading systems.

=item B<o>

B<Pth doesn't require any kernel support, but can NOT
benefit from multiprocessor machines>.

This means that B<Pth> runs on almost all Unix kernels, because the
kernel does not need to be aware of the B<Pth> threads (because they
are implemented entirely in user-space). On the other hand, it cannot
benefit from the existence of multiprocessors, because for this, kernel
support would be needed. In practice, this is no problem, because
multiprocessor systems are rare, and portability is almost more
important than highest concurrency.

=back

=head2 The life cycle of a thread

To understand the B<Pth> Application Programming Interface (API), it
helps to first understand the life cycle of a thread in the B<Pth>
threading system. It can be illustrated with the following directed
graph:

             NEW
              |
              V
      +---> READY ---+
      |       ^      |
      |       |      V
   WAITING <--+-- RUNNING
                     |
      :              V
   SUSPENDED       DEAD

When a new thread is created, it is moved into the B<NEW> queue of the
scheduler. On the next dispatching for this thread, the scheduler picks
it up from there and moves it to the B<READY> queue. This is a queue
containing all threads which want to perform a CPU burst. There they are
queued in priority order. On each dispatching step, the scheduler always
removes the thread with the highest priority only. It then increases the
priority of all remaining threads by 1, to prevent them from `starving'.

The thread which was removed from the B<READY> queue is the new
B<RUNNING> thread (there is always just one B<RUNNING> thread, of
course). The B<RUNNING> thread is assigned execution control. After
this thread yields execution (either explicitly by yielding execution
or implicitly by calling a function which would block) there are three
possibilities: Either it has terminated, then it is moved to the B<DEAD>
queue, or it has events on which it wants to wait, then it is moved into
the B<WAITING> queue. Else it is assumed it wants to perform more CPU
bursts and immediately enters the B<READY> queue again.

Before the next thread is taken out of the B<READY> queue, the
B<WAITING> queue is checked for pending events. If one or more events
occurred, the threads that are waiting on them are immediately moved to
the B<READY> queue.

The purpose of the B<NEW> queue has to do with the fact that in B<Pth>
a thread never directly switches to another thread. A thread always
yields execution to the scheduler and the scheduler dispatches to the
next thread. So a freshly spawned thread has to be kept somewhere until
the scheduler gets a chance to pick it up for scheduling. That is
what the B<NEW> queue is for.

The purpose of the B<DEAD> queue is to support thread joining. When a
thread is marked to be unjoinable, it is directly kicked out of the
system after it terminated. But when it is joinable, it enters the
B<DEAD> queue. There it remains until another thread joins it.

Finally, there is a special separated queue named B<SUSPENDED>, to where
threads can be manually moved from the B<NEW>, B<READY> or B<WAITING>
queues by the application. The purpose of this special queue is to
temporarily absorb suspended threads until they are again resumed by
the application. Suspended threads do not cost scheduling or event
handling resources, because they are temporarily completely out of the
scheduler's scope. If a thread is resumed, it is moved back to the queue
from where it originally came and this way again enters the schedulers
scope.

=head1 APPLICATION PROGRAMMING INTERFACE (API)

In the following the B<Pth> I<Application Programming Interface> (API)
is discussed in detail. With the knowledge given above, it should now
be easy to understand how to program threads with this API. In good
Unix tradition, B<Pth> functions use special return values (C<NULL>
in pointer context, C<FALSE> in boolean context and C<-1> in integer
context) to indicate an error condition and set (or pass through) the
C<errno> system variable to pass more details about the error to the
caller.

=head2 Global Library Management

The following functions act on the library as a whole.  They are used to
initialize and shutdown the scheduler and fetch information from it.

=over 4

=item int B<pth_init>(void);

This initializes the B<Pth> library. It has to be the first B<Pth> API
function call in an application, and is mandatory. It's usually done at
the begin of the main() function of the application. This implicitly
spawns the internal scheduler thread and transforms the single execution
unit of the current process into a thread (the `main' thread). It
returns C<TRUE> on success and C<FALSE> on error.

=item int B<pth_kill>(void);

This kills the B<Pth> library. It should be the last B<Pth> API function call
in an application, but is not really required. It's usually done at the end of
the main function of the application. At least, it has to be called from within
the main thread. It implicitly kills all threads and transforms back the
calling thread into the single execution unit of the underlying process.  The
usual way to terminate a B<Pth> application is either a simple
`C<pth_exit(0);>' in the main thread (which waits for all other threads to
terminate, kills the threading system and then terminates the process) or a