Multiplexing is defined as (via wikipedia):
In telecommunications and computer networks, multiplexing (sometimes contracted to muxing) is a method by which multiple analog message signals or digital data streams are combined into one signal over a shared medium. The aim is to share an expensive resource.
In essence, this means taking a multitude of inputs and allowing one through at a given time (or combining them into a single input). I/O multiplexing more specifically deals with input and output streams, blocking, reading, and writing. In this example, I will demonstrate how multiplexing works using the linux kernel system call epoll (via wikipedia again):
A scalable I/O event notification mechanism, first introduced in Linux kernel 2.5.44. It is meant to replace the older POSIX
select(2)andpoll(2)system calls, to achieve better performance in more demanding applications, where the number of watched file descriptors is large (unlike the older system calls, which operate in O(n) time,epolloperates in O(1) time).epollis similar to FreeBSD‘skqueue, in that it operates on a configurable kernel object, exposed to user space as a file descriptor of its own.
In other words, epoll monitors multiple file descriptors and waits for one (or more) of them to be “ready,” i.e. an event has occurred (data is ready to be read/written). Although this is only available on Linux, BSD (which OSX is more or less based off of) has a similar function called kqueue and it is always possible to use the POSIX select and poll. I would highly recommend against using POSIX because the runtime of various applications grow linearly O(n) as opposed to epoll or kqueue which is constant time O(1), you can find a comparison in the linux patch notes.
Use cases include updating various files in a web server (such as HTTP connections), determining when a thread has closed, handling multiple user file requests on the same machine.
Purpose
In the following two examples I will demonstrate how both epoll and kqueue function to achieve the same tasks, in other words a side by side comparison of the two. This should help those who are attempting to learn epoll coming from knowing a kqueue, or attempting to learn how a kqueue works while coming from an epoll background. There are also some key differences which effect readability and possibly performance, though I have not had the opportunity to test both examples on the same machine.
I would not call this article epoll vs kqueue, epoll is used on Linux and Kqueue is used on FreeBSD or OSX to achieve similar results and as such are not really directly comparable. However, I would like to suggest the kqueue is more scalable than epoll. I wont go into the details, but epoll suffers when handling a large number of file descriptors. If you would like to read more I suggest a paper from the linux symposium: Comparing and Evaluating epoll, select, and poll Event Mechanisms. If on the other hand, you would like to understand the difference between the two or see a demonstration, read on!
Epoll
The system calls for epoll interface consists of three system calls[1]:
int epoll_create(int size);int epoll_create1(int flags);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeouts);
Requiring: <sys/epoll.h>
Below is an example where the epoll system call could be used, the example is adapted from CS 241 – Systems Programing at UIUC:
Note that we have two functions run simultaneously should output:
$ A – 1
$ B – 2
$ C – 3
$ D – 4
The real charm to using an epoll is that function we can spawn two child processes (hence the function names), and have each process output signals which epoll can handle, by watching the various file descriptors.
The above epoll example follows the following method:
- Create (two) epoll events (as well as pipes in this case, but any file descriptor works) (epoll_create)
- Generate two child processes and add the read_fd of the pipe to the epoll event (epoll_ctl).
- After all processes generated and events added, wait for signal (using epoll_wait)
- Clear the event file descriptor (ev.data.fd) by deleting it and reseting wait (step 3) if nothing was received (epoll_ctl).
Output:
$ A – 1
$ B – 2
$ C – 3
$ D – 4
As expected! The output was correct.
Kqueue
The system calls for the kqueue interface consists of two system calls:
int kqueue(void);
int kevent(int kq, const struct kevent * changelist, int nchanges, struct kevent *keventlist, int nevents,
const struct timespec * timeout);
Requiring: <sys/types.h> <sys/events.h> <sys/time.h>
There is also a macro I use in the example[2]:
EV_SET(_kev, ident, filter, flags, fflags, data, udata);
In the following example kqueue we will use the same functions as the previous epoll (child_one_func and child_two_func):
The above kqueue example follows the following method:
- Create a kqueue (kqueue)
- Create space for the file descriptors, changelist and eventlist using malloc (the stack could work as well).
- Generate two child processes and add the read_fd of the pipe to the kqueue changelist (EV_SET).
- After all processes generated and events added, wait for signal, and re-watch (using kevent).
Notice step 4 and 5 from epoll have been merged into step 4 for kqueue. This demonstrates one of the advantages and major differences over epoll.
Output:
$ A – 1
$ B – 2
$ C – 3
$ D – 4
As expected! The output was correct and thus both epoll and kqueue can achieve the same results.
Epoll vs Kqueue
It is clear that epoll has its uses and is the standard way to I/O multiplexing it has several weaknesses[3] when compared to kqueue:
- epoll_ctl() called are directly proportional to how many descriptors you would like to update, meaning if you have 50 updates you are required to do 50 epoll_ctl calls().
- epoll does not work with when disk I/O (epoll is blocked), they must be in cached memory.
- File descriptors are a must, and although pretty much all data can be converted to a file descriptor it reduces readability.
All of the code in this article can be downloaded/forked from my github. Remember epoll only works on linux and kqueue works on BSD (and OSX), sorry windows.
Related Articles