IO multiplexing, select, poll, epoll differences

IO multiplexing is a synchronous IO model. A thread listens for multiple I/O events. When an I/O event is ready, the thread will be notified to perform the corresponding read and write operation. Multiplexing refers to network links, and multiplexing refers to the reuse of the same thread.

select

• The fd_set data structure is defined as follows. Fd_set is an integer array used to store socket file descriptors

typedef long int __fd_mask;

/* fd_set for select and pselect. */
typedef struct
  {
#ifdef __USE_XOPEN
    __fd_mask fds_bits[__FD_SETSIZE / __NFDBITS];
# define __FDS_BITS(set) ((set)->fds_bits)
#else
    __fd_mask __fds_bits[__FD_SETSIZE / __NFDBITS];
# define __FDS_BITS(set) ((set)->__fds_bits)
#endif
  } fd_set;
Copy the code

• Implementation process

  

  Process:

  1. The user thread calls select and copies fd_set from user space to kernel space. The kernel iterates over fd_set in kernel space to see if there is a ready socket descriptor. If there is no ready socket descriptor, it goes to sleep until there is a ready socket descriptor. The kernel returns the result of the select to the user thread, that is, the number of file descriptors ready 4. After getting the number of ready file descriptors, the user iterates fd_set again to find the ready file descriptors 5. The user thread reads and writes to the ready file descriptorCopy the code

• advantages

  1. All platforms are supported, good cross-platform

• disadvantages

  1. Every time you call SELECT, you need to copy fd_set from user space to kernel space, which can be expensive when there are many FDS
  2. The maximum number of connections (the maximum number of supported file descriptors) is limited, generally 1024
  3. Each time there is an active socket descriptor, fd_set needs to be traversed, resulting in a large amount of time, time complexity is O(n).
  4. Copy fd_set from user space to kernel space, which also needs to iterate over fd_set

poll

• The data structure

  The data structure is defined as follows and stored in a linked list

  /* Data structure describing a polling request. */
  struct pollfd
    {
      int fd;			/* File descriptor to poll. */
      short int events;		/* Types of events poller cares about. */
      short int revents;		/* Types of events that actually occurred. */
    };
  Copy the code

• Similarities and differences with SELECT

  Similarities:

  1. All kernel threads need to traverse file descriptors, and when the kernel returns the number of ready file descriptors, they need to traverse again to find the ready file descriptors
  2. An array or linked list of file descriptors needs to be copied from user space to kernel space
  3. The performance overhead increases linearly with the number of file descriptors

  Difference:

  1. Select stores an array of file descriptors, poll uses a linked list
  2. Select has a maximum connection limit, poll has no maximum limit because poll is stored in linked lists

• Execution procedures (Basic and SELECT types)

  1. The user thread invokes the poll system call and copies the linked list of file descriptors into the kernel space
  2. The kernel iterates over the file descriptor, and if there is no ready descriptor, the kernel starts sleeping until one is ready
  3. Returns the number of thread-ready file descriptors to the user
  4. The user thread iterates through the linked list of file descriptors again to find the file descriptor that is ready
  5. The user thread reads and writes to the ready file descriptor

epoll

• The core code

  #include <sys/epoll.h>
  
  // Data structure
  // Each epoll object has a separate EventPoll structure
  // The red-black tree is used to store events added to the epoll object by the epoll_ctl method
  // epoll_wait to check whether an event has occurred simply checks for epItem elements in the RDList double-linked list in the eventPoll object
  struct eventpoll {./* The root node of the red-black tree that stores all the events added to epoll to be monitored */
      struct rb_root  rbr;
      /* Double-linked lists store all ready file descriptors */
      struct list_head rdlist;. };// API
  int epoll_create(int size); // Add an eventPoll object in the middle of the kernel to put all the sockets that need to listen into the eventPoll object
  int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); // epoll_ctl is responsible for adding and removing sockets to the kernel red-black tree
  int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);// epoll_wait checks if there are ready file descriptors in the double-linked list and returns if there are
  
  Copy the code

  Emphasis:

  1. Epoll_create Creates an EventPoll object (red-black tree, double-linked list)
  2. A red-black tree that stores all listened file descriptors and adds and removes file descriptors to the red-black tree using epoll_ctl
  3. A double-linked list that stores a list of ready file descriptors. When epoll_wait is called, it checks if there is data in the list and returns if there is
  4. All events added to EventPoll have a callback relationship with the device driver

• disadvantages

  1. It only works under Linux

• advantages

  1. The time complexity is O(1). When an event is ready, epoll_wait only needs to check whether there is data in the ready list and return it directly if there is
  2. Memory mapping (MMAP) techniques are used instead of frequently copying file descriptor collections from user space to kernel space
  3. The user thread is notified in the form of a callback when a ready event occurs

Select, poll, epoll

Epoll is the difference between horizontal triggering (LT) and edge triggering (ET)

LT mode: Epoll_wait returns its event each time the file descriptor has data to read (fired whenever there is data)

ET mode: trigger only when data stream arrives, regardless of whether there is any data in the buffer (trigger only when data stream arrives)

What IO model is used by Nginx and Redis

IO multiplexing

Application scenarios

1. The number of connections is small and all are active, so using SELECT and poll is more efficient
2. It is more efficient to use epoll when the number of connections is large and they are not very active