Skip to main content

Chapter 33: Using Select

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives​

  • Explain the main ideas and vocabulary in Using Select.
  • Work through the source examples for Using Select without depending on raw chunk order.
  • Use Using Select as selective reference when learner modules point back to Ostep.

Prerequisites​

  • Earlier prerequisite concepts leading into Chapter 33: Using Select.

Module targets​

  • module-03-concurrency-synchronization

AI companion modes​

  • Explain simply
  • Socratic tutor
  • Quiz me
  • Challenge my understanding
  • Diagnose my confusion
  • Generate extra practice
  • Revision mode
  • Connect forward / backward

Source-of-truth note​

This unit is anchored to Ostep and the source chapter "Chapter 33: Using Select". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment​

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance​

  • Primary source: Ostep
  • Source chapter 33: Chapter 33: Using Select
  • Raw source file: 160-33-3-usingselect.md
  • Raw source file: 161-33-7-another-problem-state-management.md

Merged source​

Using Select​

33.3 Usingselect()

ASIDE: BLOCKING VS. NON-BLOCKINGINTERFACES​

Blocking (orsynchronous) interfaces do all of their work before returning to the caller; non-blocking (orasynchronous) interfaces begin some work but return immediately, thus letting whatever work that needs to be done get done in the background.

The usual culprit in blocking calls is I/O of some kind. For example, if a call must read from disk in order to complete, it might block, waiting for the I/O request that has been sent to the disk to return.

Non-blocking interfaces can be used in any style of programming (e.g., with threads), but are essential in the event-based approach, as a call that blocks will halt all progress.

an exceptional condition pending, respectively. The first nfds descriptors are checked in each set, i.e., the descriptors from 0 through nfds-1 in the descriptor sets are examined. On return, select() replaces the given descriptor sets with subsets consisting of those descriptors that are ready for the requested operation.

select() returns the total number of ready descriptors in all the sets.

A couple of points aboutselect(). First, note that it lets you check whether descriptors can be read from as well as written to; the former lets a server determine that a new packet has arrived and is in need of processing, whereas the latter lets the service know when it is OK to reply (i.e., the outbound queue is not full).

Second, note the timeout argument. One common usage here is to set the timeout to NULL, which causesselect()to block indefinitely, until some descriptor is ready. However, more robust servers will usually specify some kind of timeout; one common technique is to set the timeout to zero, and thus use the call toselect()to return immediately.

Thepoll()system call is quite similar. See its manual page, or Stevens and Rago [SR05], for details.

Either way, these basic primitives give us a way to build a non-blocking event loop, which simply checks for incoming packets, reads from sockets with messages upon them, and replies as needed.

To make this more concrete, let's examine how to useselect()to see which network descriptors have incoming messages upon them. Figure 33.1 shows a simple example.

This code is actually fairly simple to understand. After some initialization, the server enters an infinite loop. Inside the loop, it uses the

FDZERO()macro to first clear the set of file descriptors, and then uses

FDSET()to include all of the file descriptors fromminFDtomaxFDin the set. This set of descriptors might represent, for example, all of the net-

#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>
int main(void) {
// open and set up a bunch of sockets (not shown)
// main loop
while (1) {

11 // initialize the fd_set to all zero 12 fd_set readFDs;

FD_ZERO(&readFDs);
// now set the bits for the descriptors
// this server is interested in
// (for simplicity, all of them from min to max)
int fd;
for (fd = minFD; fd < maxFD; fd++)
FD_SET(fd, &readFDs);

21 22 // do the select

int rc = select(maxFD+1, &readFDs, NULL, NULL, NULL);
// check which actually have data using FD_ISSET()
int fd;
for (fd = minFD; fd < maxFD; fd++)
if (FD_ISSET(fd, &readFDs))
processFD(fd);
}
}

Figure 33.1:Simple Code Usingselect() work sockets to which the server is paying attention. Finally, the server callsselect()to see which of the connections have data available upon them. By then using FDISSET()in a loop, the event server can see which of the descriptors have data ready and process the incoming data.

Of course, a real server would be more complicated than this, and require logic to use when sending messages, issuing disk I/O, and many other details. For further information, see Stevens and Rago [SR05] for

API information, or Pai et. al or Welsh et al. for a good overview of the general flow of event-based servers [PDZ99, WCB01].

33.4 Why Simpler? No Locks Needed​

With a single CPU and an event-based application, the problems found in concurrent programs are no longer present. Specifically, because only one event is being handled at a time, there is no need to acquire or release locks; the event-based server cannot be interrupted by another thread because it is decidedly single threaded. Thus, concurrency bugs common in threaded programs do not manifest in the basic event-based approach.

TIP: DON'TBLOCKINEVENT-BASEDSERVERS

Event-based servers enable fine-grained control over scheduling of tasks.

However, to maintain such control, no call that blocks the execution the caller can ever be made; failing to obey this design tip will result in a blocked event-based server, frustrated clients, and serious questions as to whether you ever read this part of the book.

33.5 A Problem: Blocking System Calls​

Thus far, event-based programming sounds great, right? You program a simple loop, and handle events as they arise. You don't even need to think about locking! But there is an issue: what if an event requires that you issue a system call that might block?

For example, imagine a request comes from a client into a server to read a file from disk and return its contents to the requesting client (much like a simple HTTP request). To service such a request, some event handler will eventually have to issue anopen()system call to open the file, followed by a series ofread()calls to read the file. When the file is read into memory, the server will likely start sending the results to the client.

Both theopen()andread()calls may issue I/O requests to the storage system (when the needed metadata or data is not in memory already), and thus may take a long time to service. With a thread-based server, this is no issue: while the thread issuing the I/O request suspends (waiting for the I/O to complete), other threads can run, thus enabling the server to make progress. Indeed, this naturaloverlapof I/O and other computation is what makes thread-based programming quite natural and straightforward.

With an event-based approach, however, there are no other threads to run: just the main event loop. And this implies that if an event handler issues a call that blocks, theentireserver will do just that: block until the call completes. When the event loop blocks, the system sits idle, and thus is a huge potential waste of resources. We thus have a rule that must be obeyed in event-based systems: no blocking calls are allowed.

33.6 A Solution: Asynchronous I/O​

To overcome this limit, many modern operating systems have introduced new ways to issue I/O requests to the disk system, referred to generically asasynchronous I/O. These interfaces enable an application to issue an I/O request and return control immediately to the caller, before the I/O has completed; additional interfaces enable an application to determine whether various I/Os have completed.

For example, let us examine the interface provided on Mac OS X (other systems have similar APIs). The APIs revolve around a basic structure, the struct aiocborAIO control blockin common terminology. A simplified version of the structure looks like this (see the manual pages for more information):

struct aiocb {
int aio_fildes; /* File descriptor */
off_t aio_offset; /* File offset */
volatile void *aio_buf; /* Location of buffer */
size_t aio_nbytes; /* Length of transfer */
};

To issue an asynchronous read to a file, an application should first fill in this structure with the relevant information: the file descriptor of

the file to be read (aiofildes), the offset within the file (aiooffset)

as well as the length of the request (aionbytes), and finally the target memory location into which the results of the read should be copied (aiobuf).

After this structure is filled in, the application must issue the asynchronous call to read the file; on Mac OS X, this API is simply theasynchronous readAPI:

int aio_read(struct aiocb *aiocbp);

This call tries to issue the I/O; if successful, it simply returns right away and the application (i.e., the event-based server) can continue with its work.

There is one last piece of the puzzle we must solve, however. How can we tell when an I/O is complete, and thus that the buffer (pointed to by aiobuf) now has the requested data within it?

One last API is needed. On Mac OS X, it is referred to (somewhat confusingly) asaioerror(). The API looks like this:

int aio_error(const struct aiocb *aiocbp);

This system call checks whether the request referred to byaiocbphas

completed. If it has, the routine returns success (indicated by a zero);

if not, EINPROGRESS is returned. Thus, for every outstanding asynchronous I/O, an application can periodicallypollthe system via a call toaioerror()to determine whether said I/O has yet completed.

One thing you might have noticed is that it is painful to check whether an I/O has completed; if a program has tens or hundreds of I/Os issued at a given point in time, should it simply keep checking each of them repeatedly, or wait a little while first, or ... ?

To remedy this issue, some systems provide an approach based on the interrupt. This method uses UNIXsignalsto inform applications when an asynchronous I/O completes, thus removing the need to repeatedly ask the system. This polling vs. interrupts issue is seen in devices too, as you will see (or already have seen) in the chapter on I/O devices.

Another Problem State Management​

33.7 Another Problem: State Management

ASIDE: UNIXSIGNALS​

A huge and fascinating infrastructure known assignalsis present in all modern UNIXvariants. At its simplest, signals provide a way to communicate with a process. Specifically, a signal can be delivered to an application; doing so stops the application from whatever it is doing to run asignal handler, i.e., some code in the application to handle that signal. When finished, the process just resumes its previous behavior.

Each signal has a name, such asHUP(hang up),INT(interrupt),SEGV(segmentation violation), etc; see the manual page for details. Interestingly, sometimes it is the kernel itself that does the signaling. For example, when your program encounters a segmentation violation, the OS sends it aSIGSEGV(prependingSIG to signal names is common); if your program is configured to catch that signal, you can actually run some code in response to this erroneous program behavior (which can be useful for debugging). When a signal is sent to a process not configured to handle that signal, some default behavior is enacted; for SEGV, the process is killed.

Here is a simple program that goes into an infinite loop, but has first set up a signal handler to catch SIGHUP:

#include <stdio.h>
#include <signal.h>
void handle(int arg) {
printf("stop wakin' me up...\n");
}
int main(int argc, char *argv[]) {
signal(SIGHUP, handle);
while (1)

; // doin' nothin' except catchin' some sigs

return 0;
}
You can send signals to it with thekillcommand line tool (yes, this is an odd and aggressive name). Doing so will interrupt the main while loop in the program and run the handler codehandle():
prompt> ./main &
[3] 36705
prompt> kill -HUP 36705

stop wakin' me up...

prompt> kill -HUP 36705

stop wakin' me up...

prompt> kill -HUP 36705

stop wakin' me up...

There is a lot more to learn about signals, so much that a single page, much less a single chapter, does not nearly suffice. As always, there is one great source:

Stevens and Rago [SR05]. Read more if interested.

In systems without asynchronous I/O, the pure event-based approach cannot be implemented. However, clever researchers have derived methods that work fairly well in their place. For example, Pai et al. [PDZ99] describe a hybrid approach in which events are used to process network packets, and a thread pool is used to manage outstanding I/Os. Read their paper for details.

Another issue with the event-based approach is that such code is generally more complicated to write than traditional thread-based code. The reason is as follows: when an event handler issues an asynchronous I/O, it must package up some program state for the next event handler to use when the I/O finally completes; this additional work is not needed in thread-based programs, as the state the program needs is on the stack of the thread. Adya et al. call this workmanual stack management, and it is fundamental to event-based programming [A+02].

To make this point more concrete, let's look at a simple example in which a thread-based server needs to read from a file descriptor (fd) and, once complete, write the data that it read from the file to a network socket descriptor (sd). The code (ignoring error checking) looks like this:

int rc = read(fd, buffer, size);
rc = write(sd, buffer, size);

As you can see, in a multi-threaded program, doing this kind of work is trivial; when theread()finally returns, the code immediately knows which socket to write to because that information is on the stack of the thread (in the variablesd).

In an event-based system, life is not so easy. To perform the same task, we'd first issue the read asynchronously, using the AIO calls described above. Let's say we then periodically check for completion of the read using theaioerror()call; when that call informs us that the read is complete, how does the event-based server know what to do?

The solution, as described by Adya et al. [A+02], is to use an old programming language construct known as acontinuation[FHK84]. Though it sounds complicated, the idea is rather simple: basically, record the needed information to finish processing this event in some data structure; when the event happens (i.e., when the disk I/O completes), look up the needed information and process the event.

In this specific case, the solution would be to record the socket descriptor (sd) in some kind of data structure (e.g., a hash table), indexed by the file descriptor (fd). When the disk I/O completes, the event handler would use the file descriptor to look up the continuation, which will return the value of the socket descriptor to the caller. At this point (finally), the server can then do the last bit of work to write the data to the socket.

33.8 What Is Still Difficult With Events​

There are a few other difficulties with the event-based approach that we should mention. For example, when systems moved from a single

CPU to multiple CPUs, some of the simplicity of the event-based approach disappeared. Specifically, in order to utilize more than one CPU, the event server has to run multiple event handlers in parallel; when doing so, the usual synchronization problems (e.g., critical sections) arise, and the usual solutions (e.g., locks) must be employed. Thus, on modern multicore systems, simple event handling without locks is no longer possible.

Another problem with the event-based approach is that it does not integrate well with certain kinds of systems activity, such aspaging. For

example, if an event-handler page faults, it will block, and thus the server will not make progress until the page fault completes. Even though the server has been structured to avoidexplicitblocking, this type ofimplicit blocking due to page faults is hard to avoid and thus can lead to large performance problems when prevalent.

A third issue is that event-based code can be hard to manage over time, as the exact semantics of various routines changes [A+02]. For example, if a routine changes from non-blocking to blocking, the event handler that calls that routine must also change to accommodate its new nature, by ripping itself into two pieces. Because blocking is so disastrous for event-based servers, a programmer must always be on the lookout for such changes in the semantics of the APIs each event uses.

Finally, though asynchronous disk I/O is now possible on most platforms, it has taken a long time to get there [PDZ99], and it never quite integrates with asynchronous network I/O in as simple and uniform a manner as you might think. For example, while one would simply like to use theselect()interface to manage all outstanding I/Os, usually some combination ofselect()for networking and the AIO calls for disk I/O are required.

33.9 Summary​

We've presented a bare bones introduction to a different style of concurrency based on events. Event-based servers give control of scheduling to the application itself, but do so at some cost in complexity and difficulty of integration with other aspects of modern systems (e.g., paging). Because of these challenges, no single approach has emerged as best; thus, both threads and events are likely to persist as two different approaches to the same concurrency problem for many years to come.

Read some research papers (e.g., [A+02, PDZ99, vB+03, WCB01]) or better yet, write some event-based code, to learn more.

[A+02] "Cooperative Task Management Without Manual Stack Management"