State Threads Library FAQ

1. What is State Threads library (ST)?
2. How is ST different from traditional event-driven state machine implementations?
3. How is ST different from POSIX threads?
4. How is ST different from other user-level thread libraries (e.g., GNU Pth)?
5. How does ST take advantage of multiple CPUs?
6. How does ST deal with disk I/O?
7. How portable is ST?
8. Under what license is ST distributed?
9. What are the advantages of using ST?
10. What are the disadvantages of using ST?

Although ST does not introduce new "breakthrough" ideas, it is a very effective engineering solution for many network applications.

2. How is ST different from traditional event-driven state machine implementations?

In a traditional EDSM implementation (Figure 1) an application registers callback functions to be executed whenever a specific event occurs (e.g., a file descriptor becomes ready for I/O). The main dispatch loop waits for I/O or timing events using select(), poll() or whatever other exotic mechanism available on that OS. When an event occurs, the dispatcher invokes an appropriate callback associated with that event ("event handler"). Thus in a traditional EDSM implementation the request processing logic is represented as a sequence (chain) of disjoint callbacks. The logical "context switch" between requests happens upon a callback return. Before callback returns, it usually registers next callback to be invoked upon event arrival to resume request processing. It also saves the execution state in a data structure which will be passed to the next callback.

Figure 1. Traditional EDSM

The fundamental problem with traditional EDSMs is that they are difficult to implement and extend. Despite that there are several libraries and frameworks to make it easier (from small libevent to complex ACE reactor/proactor patterns), the intrinsic "complexity of breaking up linear thought into a bucketload of callbacks" (as Dean Gaudet put it) always remains.

The ST implementation turns the above EDSM model inside-out (Figure 2). It is meant to replace traditional EDSMs found in many network servers.

Figure 2. State Threads EDSM

ST uses the thread abstraction and thus preserves natural programming model. Unlike traditional EDSMs where the main dispatch loop is exposed and applications are structured around it, the ST scheduler is hidden inside the library and invisible to an application writer. The execution state is saved on the thread's stack (a contiguous chunk of memory) which is transparently managed by the C environment.

Whenever a thread needs to wait for a specific event to occur, it saves its execution state and puts itself on an event wait queue -- this is equivalent to registering a callback in traditional EDSMs. Then the scheduler is executed. It pulls the first thread from the run queue and restores its execution state -- this is equivalent to invoking a callback in traditional EDSMs. If there are no runnable threads (the run queue is empty), the scheduler waits for I/O or timing events using select(), poll() or possibly other exotic mechanism available on that OS. When events occur, the scheduler "wakes up" threads waiting for those events by putting them on the run queue. Then it restores the execution state of the first runnable thread. The cycle is complete.

Performance-wise ST is as fast as traditional EDSM implementations. The context switch overhead is a cost of doing _setjmp()/_longjmp() (no system calls are involved). This is negligible for all practical applications. The thread creation overhead is also very small.

Memory-wise ST is almost as efficient as traditional EDSMs. Although the swap space is reserved for the entire stack segment upon thread creation, only stack pages that are actually used (touched) will be brought into physical memory. There is, however, one page per thread minimum memory requirement. In any case -- ST or traditional EDSM -- the execution state has to be stored somewhere. Keeping it on the stack is much more efficient than in ad hoc data structures. As Dean Gaudet from ASF wrote:

... one of the arguments the event folks sometimes throw against the thread folks is that the thread folks have a stack per thread. And if you've got a thread per connection then you're paying a stack per connection. That can be expensive if your stack is really deep. Whereas with the event model you only have one stack.

It's a good point. The counterpoint is that in the event model, much of the state which the thread folks store on the stack is stored on the heap, in a different form. And because languages such as C are designed more for the threaded/linear programming model, there are few optimizations to help the event folks. For example, in thread land you'd write code:

       int foo()
       {
           int local1;
           int local2;
           ...
           do_some_io();
           ...
       }

in event land you might write:

       struct foo_data {
           int local1;
           int local2;
           ...
       };

       void foo_after_io_completes(void *arg)
       {
           struct foo_data *locals = arg;
           ...
       }

       void foo()
       {
           struct foo_data *locals = malloc(sizeof(struct foo_data));
           ...
           initiate_io(foo_after_io_completes, locals);
       }

But in the thread version, some of those locals may actually never be allocated. They may live only in registers. But the compiler can't perform that optimization in the event model. These sort of micro details are what make me question how good the event model really is for the average programmer who doesn't want to think about cycles all the time. That's what compilers are supposed to help with.

For the full email thread see Apache server development mail archives.

3. How is ST different from POSIX threads?

Pthreads are meant to be general-purpose threads. That is, a POSIX conforming thread library should work correctly for a wide range of applications. In many cases, however, it is not the best choice for a particular application domain, such as event-driven network servers. Pthreads flexibility has its drawbacks. Allowing several kernel execution entities ("lightweight processes") to share the same address space and other resources introduces new level of complexity. Quoting the Linux Threads FAQ: "all the nightmares about sharing, locking, deadlock, race conditions, etc. come vividly alive in threads... Threads can share file handles, pipes, variables, signals, etc. Trying to test and duplicate error conditions can cause more gray hair than a wayward child." To maintain portability, an application writer using Pthreads should never make any assumptions about their underlying implementation and always treat them as concurrent and preemptive.

ST, on the other hand, is not meant to be a general-purpose thread library. It was designed with intention to replace traditional EDSMs found in many network applications. ST is fully deterministic and always guarantees that the context switch can only happen in a well-known set of functions (at I/O points or at explicit synchronization points). As a result, global data does not have to be protected by mutual exclusion locks. The entire application is free to use all the static variables and non-reentrant library functions it wants, greatly simplifying programming and debugging while increasing performance.

For more general information on threads see the comp.programming.threads FAQ.

4. How is ST different from other user-level thread libraries (e.g., GNU Pth)?

For example, top priorities in the development of GNU Pth are platform-independence and completeness. ST, on the other hand, tries to achieve high performance, scalability, and correctness on all explicitly supported platforms. The ST's API and internals are designed with respect to the needs of a specific application domain. Preemptive- or priority-based scheduling of threads is omitted to achieve low thread management overhead. The number of system calls is minimized to make thread creation and context switching as fast as possible. For example, per-thread signal mask is not supported, so there is no need to save and restore a process signal mask on every thread context switch.

To summarize, ST is not designed to provide full functionality of a general-purpose thread library (it is impossible without kernel support anyway). It rather offers a threading API for structuring an application as an event-driven state machine.

5. How does ST take advantage of multiple CPUs?

Figure 3. ST Application Architecture

Using multiple processes allows to avoid synchronization overhead on multiprocessor systems and thus achieve high system scalability. It is often better to have several separate smaller process-specific resources (such as data caches) than one large resource shared and modified by all processes. In other words, each process should be considered as a separate mini-instance of the application ("cluster in a box" approach). This multi-process multi-threaded architecture also increases an application's availability because each process works as a fault container. If one of the processes crashes, only a fraction of all threads (user connections) will be lost.

6. How does ST deal with disk I/O?

To more efficiently multiplex disk I/O, multiple identical application processes may be created (Figure 3). The probability that at any given moment all processes are blocked on disk I/O exponentially decreases with the number of processes. This approach ("symmetric EDSM") is used, for example, by the Zeus Web server. Another approach is to delegate blocking disk I/O operations to a special set of helper processes or kernel threads ("asymmetric EDSM"). This technique is used by the Squid Web proxy server and Flash Web server. In any case, it is up to the application designer to choose the most optimal architecture for the specific application at hand.

7. How portable is ST?

The only part of the library which needs special attention when porting to a new platform is the thread context initialization. ST uses the _setjmp()/_longjmp() routines or their variants to save/restore the machine context. The machine context consists of CPU registers including the program counter (PC) and the stack pointer (SP). It is usually initialized by calling _setjmp() to get the initial state and then manually setting the SP field of the jmp_buf structure to a newly allocated stack segment:

    struct thread {
        ...
        jmp_buf context;
        ...
    };

    ...
    struct thread *t;
    ...

    /* Get the initial state including PC */
    if (_setjmp(t->context)) {
        /* This function never returns */
        thread_main_function(); 
    }

    /* Now set SP to a new value */
    ...

8. Under what license is ST distributed?

In short, ST can be used without restrictions with any other software (both free and non-free). Modifications to ST itself, however, must be made available to anyone who uses your modified version.

9. What are the advantages of using ST?

10. What are the disadvantages of using ST?