Programming with POSIX® Threads

protocol, when a thread locks a mutex the thread's priority is controlled through the mutex (Figure 5.4). When another thread needs to block on that mutex, it looks at the priority of the thread that owns the mutex. If the thread that owns the mutex has a lower priority than the thread attempting to block on the mutex, the priority of the owner is raised to the priority of the blocking thread.

The priority increase ensures that the thread that has the mutex locked cannot be preempted unless the waiting thread would also have been preempted — in a sense, the thread owning the mutex is working on behalf of the higher-priority thread. When the thread unlocks the mutex, the thread's priority is automatically lowered to its normal priority and the highest-priority waiter is awakened. If a second thread of even higher priority blocks on the mutex, the thread that has the mutex blocked will again have its priority increased. The thread will still be returned to its original priority when the mutex is unlocked.

The priority inheritance protocol is more general and powerful than priority ceiling, but also more complicated and expensive. If a library package must make use of priority scheduling, and cannot avoid use of a mutex from threads of differ-ent priority, then priority inheritance is the only currently available solution. If you are writing a main program, and know that none of your mutexes can be locked by threads created within a library, then priority ceiling will accomplish the same result as priority inheritance, and with less overhead.

FIGURE 5.4 Priority inheritance mutex operation

5.6 Threads and kernel entities

'Two llnesl' cried the Mock Turtle. 'Seals, turtles, salmon, and so on:

then, when you've cleared all the jelly-fish out of the way—'

'That generally takes some time,'interrupted the Gryphon, '

—you advance twice—'

'Each with a lobster as a partner!' cried the Gryphon.

— Lewis Carroll Alice's Adventures in Wonderland

Pthreads deliberately says very little about implementation details. This leaves each vendor free to make decisions based on the needs of their users and to allow the state of the art to advance by permitting innovation. The standard places a few essential requirements on the implementation — enough that you can write strictly conforming POSIX applications that do useful work with threads and will be able to run correctly on all conforming implementations of the standard.

Any Pthreads implementation must ensure that 'system services invoked by one thread do not suspend other threads' so that you do not need to worry that calling read might block all threads in the process on some systems. On the other hand, this does not mean that your process will always have the maximum possible level of concurrency.

Nevertheless, when using a system it is often useful to understand the ways in which the system may be implemented. When writing ANSI C expressions, for example, it is often helpful to understand what the code generator, and even the hardware, will do with those expressions. With that in mind, the following sections describe, briefly, a few of the main variations you're likely to encounter.

The important terms used in these sections are 'Pthreads thread,' 'kernel entity,' and 'processor.' 'Pthreads thread' means a thread that you created by calling pthread_create, represented by an identifier of type pthread_t. These are the threads that you control using Pthreads interfaces. By 'processor,' I refer to the physical hardware, the particular thing of which a 'multiprocessor' has more than one.

Most operating systems have at least one additional level of abstraction between 'Pthreads thread' and 'processor' and I refer to that as a 'kernel entity,' because that is the term used by Pthreads. In some systems, 'kernel entity' may be a traditional UNIX process. It may be a Digital UNIX Mach thread, or a Solaris 2.x LWP, or an IRLX sproc process. The exact meaning of 'kernel entity,' and how it interacts with the Pthreads thread, is the crucial difference between the three models described in the following sections.

* Strictly conforming is used by POSIX to mean something quite specific: a strictly conforming application is one that does not rely on any options or extensions to the standard and requires only the specified minimum value for all implementation limits (but will work correctly with any allowed value).

5.6.1 Many-to-one (user level)

The many-to-one method is also sometimes called a 'library implementation.' In general, 'many-to-one' implementations are designed for operating systems with no support for threads. Pthreads implementations that run on generic UNIX kernels usually fall into this category—for example, the classic DCE threads reference implementation, or the SunOS 4.x LWP package (no relation to the Solaris 2.x LWP, which is a kernel entity).

Many-to-one implementations cannot take advantage of parallelism on a multiprocessor, and any blocking system service, for example, a call to read, will block all threads in the process. Some implementations may help you avoid this problem by using features such as UNIX nonblocking I/O, or POSIX.1b asynchronous I/O, where available. However, these features have limitations; for example, not all device drivers support nonblocking I/O, and traditional UNIX disk file system response is usually considered 'instantaneous' and will ignore the nonblocking I/O mode.

Some many-to-one implementations may not be tightly integrated with the ANSI C library's support functions, and that can cause serious trouble. The stdio functions, for example, might block the entire process (and all threads) while one thread waits for you to enter a command. Any many-to-one implementation that conforms to the Pthreads standard, however, has gotten around these problems, perhaps by including a special version of stdio and other functions.

When you require concurrency but do not need parallelism, a many-to-one implementation may provide the best thread creation performance, as well as the best context switch performance for voluntary blocking using mutexes and condition variables. It is fast because the Pthreads library saves and restores thread context entirely in user mode. You can, for example, create a lot of threads and block most of them on condition variables (waiting for some external event) very quickly, without involving the kernel at all.

Figure 5.5 shows the mapping ofPthreads threads (left column) to the kernel entity (middle column), which is a process, to physical processors (right column). In this case, the process has four Pthreads threads, labeled 'Pthread 1' through 'Pthread 4.' The Pthreads library schedules the four threads onto the single process in user mode by swapping register state (SP, general registers, and so forth). The library may use a timer to preempt a Pthreads thread that runs too long. The kernel schedules the process onto one of the two physical processors, labeled 'processor 1' and 'processor 2.' The important characteristics of this model are shown in Table 5.2.

FIGURE 5.5 Many-to-one thread mapping

Advantages	Disadvantages
Fastest context switch time.