Operating Systems: Three Easy Pieces [Concurrency Ch.8: Event-based Concurrency (Advanced)]

Event-based Concurrency (Advanced)

threads are not the only way to write concurrency apps, a different style of concurrent programming is often used in both GUI-based applications and some types of internet servers This style, known as event-based concurrency, has become popular in some modern systems, including server-side frameworks such as node.js

The Basic Idea: An Event Loop

The basic approach we’ll use, as stated above, is called event-based concurrency. The approach is quite simple: you simply wait for something (i.e., an “event”) to occur; when it does, you check what type of event it is and do the small amount of work it requires (which may include issuing I/O requests, or scheduling other events for future handling, etc.).

An Important API: select() (or poll())

What these interfaces enable a program to do is simple: check whether there is any incoming I/O that should be attended to. For example, imagine that a network application (such as a web server) wishes to check whether any network packets have arrived, in order to service them.

Using select()

#include <stdio.h>
#include <stdlib.h>
#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)
    {
        // initialize the fd_set to all zero
        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);

        // 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);
    }
}

This code is actually fairly simple to understand. After some initialization, the server enters an infinite loop. Inside the loop, it uses the FD ZERO() macro to first clear the set of file descriptors, and then uses FD SET() to include all of the file descriptors from minFD to maxFD in

the set. This set of descriptors might represent, for example, all of the network sockets to which the server is paying attention. Finally, the server calls select() to see which of the connections have data available upon them. By then using FD ISSET() 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

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.

A Problem: Blocking System Calls

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 an open() system call to open the file, followed by a series of read() calls to read the file. When the file is read into memory, the server will likely start sending the results to the client.

this natural overlap of I/O and other computation is what makes thread-based programming quite natural and straightforward

in summary: 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.

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 as asynchronous 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;

The APIs revolve around a basic structure, the struct aiocb or AIO control block in common terminology. A simplified version of the structure looks like this

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 application must issue the asynchronous call to read the file; on a Mac, this API is simply the asynchronous read API:

int aio_read(struct aiocb *aiocbp);

There is one last piece of the puzzle we must solve. How can we tell when an I/O is complete

One last API is needed. On a Mac, it is referred to (somewhat confusingly) as aio error(). The API looks like this:

int aio_error(const struct aiocb *aiocbp);

This system call checks whether the request referred to by aiocbp has 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 periodically poll the system via a call to aio error() to determine whether said I/O has yet completed.

Another Problem: State Management

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

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 the read() finally returns, the code immediately knows which socket to write to because that information is on the stack of the thread (in the variable sd).

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 the aio error() call; when that call informs us that the read is complete, how does the event-based server know what to do?

What Is Still Difficult With Events

There are a few other difficulties with the event-based approach that we should mention 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.

This is the end of the series I hope you find it useful :))

References

Operating Systems: Three Easy Pieces