I/O Multiplexing

Created

Blocking Operations

We need concurrency in a server because clients execute independently of each other and requests are sent at unpredictable times. The server has to be able to accept new connections and process requests.

In this server main loop (with no concurrency),

int server_fd = open_listenfd(port);

while (1) {
	int client_fd = Accept(server_fd, NULL, NULL); // indefinite wait
	chat_with_client(client_fd); // indefinite wait
	close(client_fd);
}

the server will not be responsive while

  1. waiting for client connection to arrive
  2. waiting to receieve data from client
  3. waiting to send data to client (sometimes required by TCP protocol)

Blocking Operations involve indefinite waits.

  • Operations like accept, read, and write all can block.
  • "Blocking" means that the OS kernel suspends the calling thread untilt eh operation has been completed.
  • E.g., when calling accept the caling thread is blocked until a request for a new clinet connection
  • Problem: while a thread is blocked, it can't do anything else, so there is no way to support multiple simultaneous cleints, and have the server be responsive, using a single thread.

Nonblocking I/O is supported in modern operating systems.

  • In Unix/Linux, a file descriptor can be made nonblocking.
  • All operations that would normally block are guaranteed not to block if the filed descriptor is nonblocking.
  • If a blocking operation (accept, read, write) is invoked, but it can't be completed immediation, Operation returns an error and errno is set to EWOULDBLOCK error code.

Error Codes

When a C library or system call function fails, errno is set to an integer error code to indicate the reason for the failure.

Available using #include <errno.h>.

It's not actually a global variable (because that wouldn't work in a multithreaded program).

Its definition is found in the Linux C library (glibc):

extern int *__errno_location (void) __THROW __attribute_const__;
# define errno (*__errno_location ())

__errno_location function returns a pointer to an integer variable allocated in thread-local storage

  • so each thread has its own errno

I/O Multiplexing

The idea is: can we handle multiple client connections simultaneously as long as the server avoids any blocking I/O?

  • How do we know which file descriptors are ready to perform I/O? (because it takes a lot of processing power to run something that will keep failing)

I/O multiplexing is an alternative approach for supporting multiple simultaneous client connections.

  1. The server maintains sets of active file descriptors (mostly client connectionsm but also for file I/O)
  2. The main server loop uses select or poll (or epoll in modern) system call to check which file descriptors are ready, meaning that a read or write can be performed without blocking.
  3. Compared to using processes or threads for concurrency, its advantages include: less overhead (CPU, memory) per client connection than processes or threads, and its disadvantages include: higher code complexity.

Select

The select system call:

#include <sys/select.h>
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
  • readfds, writefds, and exceptfds are sets of file descriptors

select waits until at least one file descriptor has become ready for reading or writing, or has an exceptional condition.

  • readfds, writefds, and/or exceptfds are modified to indicate the specific file descriptors that are ready
  • timeout specifies the maximum amount of time to wait, NULL indicates indefinitely.

fd_set represets a set of file descriptors. Its operations (where set is a fd_set variable):

  • FD_ZERO(&set): make set empty

  • FD_SET(fd, &set): add fd to set

  • FD_CLR(fd, &set): remove fd from set

  • FD_ISSET(fd, &set): true if fd is in set, false otherwise

    Implementation of multiplexing. Main loop pseudo-code:

while (1) {
	wait for fd to become ready (select or poll)
	if sever socket ready:
		accept a condition, add it to set

	for fd in client connections:
		if fd is ready for reading, read, and update connection state
		if fd is ready for writing, write, and dupdate connection state
}

Updating connection state

The main difficulty of using I/O multiplexing is that communication with clients is event-driven. When data is read from the client, event-processing code must figure out what to do with it.

  • Data read might be a partial message
  • Similar issue when sending data to client: data might need to be sent in chunks

Maintaining and updating state of client connections is more complicated compared to code for process- or thread-based concurrency

  • with these approaches, we just use normal loops and control flow.

Per-connection data structure:

#define CONN_READING  0
#define CONN_WRITING  1
#define CONN_DONE     2

struct Connection {
	char in_buf[BUFFER_SIZE];
	char out_buf[BUFFER_SIZE];
	int in_count, out_pos, out_count;
	int state;
};

in_buf, in_count: data received from client
out_buf, out_pos, out_count: data to be sent to client
state: client state (CONN_READING, CONN_WRITING, or CONN_DONE)

State machine models a synchronous network protocol.

  • In a protocol implementation using threads or processes for concurrency, state is implcit. It correlates to whatever process you are in.
  • When implementing a protocol with I/O multiplexing, state must be explicit.

Make file descriptor nonblocking

Even when using select or poll to determine when file descriptors are ready, it's a good idea to make them nonblocking.

Avoid situations where an I/O operation might block.

To make a file descriptor non-blocking:

void make_nonblocking(int fd) {
	int flags = fcntl(fd, F_GETFL, 0);
	if (flags < 0) {
		fatal("fcntl failed: could not get flags");
	}
	flags |= O_NONBLOCK;
	if (fcntl(fd, F_SETFL, flags) < 0) {
		fatal("fcntl failed: could not set flags");
	}
}

readfds and writefds

  • Server has two fd_sets, readfds and writefds
    • These specify the file descriptors that the server wants to check from being ready to read (readfds) or write (writefds).
    • readfds contains the server sockert and the client file descriptors of all the connections in the CONN_READING state.
    • writefds contains the client file descriptors of all connections in the CONN_WRITING state
  • Each call to select determines which file descriptors in readfds are ready for reading, and which file descriptors in writefds are ready for writing.
    • If the server socket file descriptor is ready for reading, it means that a connection request has arrived (and a call to accept will not block)

To build the file descriptor set:

// Code executed for each iteration of server main loop

// Place client socket fds in readfds and writefds as appropriate
for (int fd = 0; fd <= maxfd; fd++) {
	struct Connection *conn = client_conn[fd];
		if (conn) {
			if (conn->state == CONN_READING) {
				FD_SET(fd, &readfds);
			} else if (conn->state == CONN_WRITING) {
				FD_SET(fd, &writefds);
		} 
	}
}

// Server socket is always in readfds
FD_SET(serverfd, &readfds);
  • go through all the client connection, and for every one that is in a reading state, we add its fd to the reading state (and same for writing).

To determine which file descriptors are ready:

int rc = select(maxfd + 1, &readfds, &writefds, NULL, NULL);
if (rc < 0) {
	fatal("select failed");
}
  • The maxfd variable keeps track of the maximum file descriptor value: select is more efficient when it checks fewer file descriptors for readiness.
  • The last argument to select is the timeout argument. NULL means indefinite, but definite waits are better because it makes sure that the server wakes up some time. A system that has liveness is the absense of indefinite wait. Too much liveness is bad too.

To accept a client connection:

if (FD_ISSET(serverfd, &readfds)) {
	int clientfd = Accept(serverfd, NULL, NULL);
	make_nonblocking(clientfd);
	if (clientfd > maxfd) {
		maxfd = clientfd;
	}
	client_conn[clientfd] = create_client_conn();
}
  • we create a client connection and register it with the map of client connection labeled by its clientfd

Server client connections:

for (int fd = 0; fd <= maxfd; fd++) {
	if (client_conn[fd] != NULL) {
		struct Connection *conn = client_conn[fd];
		if (FD_ISSET(fd, &readfds)) {
			client_do_read(fd, conn);
		}
		if (FD_ISSET(fd, &writefds)) {
			client_do_write(fd, conn);
		}
		if (conn->state == CONN_DONE) {
			close(fd);
			free(conn);
			client_conn[fd] = NULL;
		} 
	}
}

client_do_read:

void client_do_read(int fd, struct Connection *conn) {
	int remaining = BUFFER_SIZE - conn->in_count - 1;
	ssize_t rc = read(fd, conn->in_buf + conn->in_count, remaining);
	if (rc < 0) {
		fatal("read failed");
	}
	conn->in_count += rc;
	
	// process the data that was read
	// ...40+ lines of code omitted... 
}

This code is complicated because it must

  • determine if a complete message was received, and if so, copy it to out_buf, deal with leftover data, and update connection state.

client_do_write:

void client_do_write(int fd, struct Connection *conn) {
	int remaining = conn->out_count - conn->out_pos;
	ssize_t rc = write(fd, conn->out_buf + conn->out_pos, (size_t) remaining);
	if (rc < 0) {
		fatal("write failed");
	}
	
	conn->out_pos += rc;
	if (conn->out_pos == conn->out_count) {
		conn->state = CONN_READING;
	}
}
  • just try to copy data form out_buf to the client socket.

Afterword:

  • The I/O multiplexing echo server implementation not terribly complex (a little over 200 lines of code)
  • However: the protocol was very simple and even so, client_do_read was quite complicated!
  • Real protocols (e.g., HTTP) would be much more complicated to implement
  • It would be nice if there were a way to get the benefits of I/O multiplexing, but write our code in a “threaded” style rather than an “event-driven” style

I/O Multiplexing with coroutines

Couroutines reduce the complexity of I/O multiplexing to implement communication with clients.

  • A lightweight way of implementing threads
  • Runtime cost closer to function call overhead.
  • Each client connection is implemented as a coroutine.

When a client file descriptor finds that a client fd is ready for reading or writing, it yields to the client coroutine.

Client coroutine will do I/O, and then yeild back to the main routine.

Echo server client coroutine:

void chat_with_client(void) {
	struct Connection *conn = (struct Connection *) aco_get_arg();
	for (;;) {
		// read a line
		conn->state = CONN_READING;
		co_readline(conn);
		
		// if line was "quit", we're done
		if (strcmp(conn->out_buf, "quit") == 0) {
			break; 
		}
		
		// echo line back to client
		conn->state = CONN_WRITING;
		co_write_fully(conn->fd, conn->out_buf, strlen(conn->out_buf));
		co_write_fully(conn->fd, "\r\n", 2);
	}
	aco_exit();
}
  • this function looks almost exactly like a thread start function
  • the assignment to conn->state help the main routine know when to schedule the coroutine (based on the readiness of its file descriptor for reading or writing).
  • the co_readline and co_write_fully functions are "coroutine-aware" I/O functions that yield back to the main routine if a call to read or write would block.
  • see complete code for details.

Linked from Computer System Fundamentals