Small Clients Beside Large Ones: Ready Queues and Fairness

In one line

Finding the ready connections and deciding how much CPU to give each one are different problems. A finite work budget and a ready queue without duplicates keep small requests from starving behind long ones.

Why this was needed

Earlier, we called recv once and went back to the other connection. This time, imagine an optimization that keeps reading as long as there is data. Client A hands in an 8KiB manuscript and client B hands in a single character. If you fully drain A and then look at B, total throughput looks good, but B's first response is late. If A keeps sending faster than you read, the loop may never get back to B or to a termination request. Non-blocking means each call does not wait; it does not mean code that repeats calls without limit is fair.

This problem exists in accept too. A loop that accepts new connections until EAGAIN ends quickly in normal times, but under conditions where connections keep arriving, it postpones the work of existing connections. That is why you put a budget on each of the bytes read, the connections started, and the ready jobs handled. A budget differs from a connection's total allowance. Saying you will read only 1KiB this turn and saying you will accept at most 1KiB of a request are different contracts.

How it works

epoll(7) describes a design that avoids starvation with a ready list and round-robin. With level triggering, if the condition remains, the ready state is visible at the next wait too. With edge triggering, if you trust only the notification you have already received and fall asleep after part of the data, you may miss the remaining data. In ET, the application has to remember work that stopped because the budget ran out. Only when you observe EAGAIN do you judge that you have exhausted what can be done right now.

This comparison experiment specifies EPOLLET directly on Python's low-level epoll. The follow-up connection diagnostic tool uses DefaultSelector and does not implement an ET read server. Keep the two pieces of code apart. The experiment shows the error of forgetting the ready state, and the diagnostic tool applies the same queue principle to handling several completion events divided by budget.

python3 /opt/fixtures/reactor/fairness_probe.py

The experiment creates two socketpairs with no external communication and puts 8192 bytes in A and 1 byte in B first. So as not to assume the order the kernel returns, the program deliberately handles A first. On each turn it reads at most 1024 bytes. It compares the following results without any additional sending or EOF.

Strategy	Consumed from A	B's turn	Next kernel events
Handle each connection once and discard the ready fact	1024 bytes	Second	0
Send a connection with work remaining to the back of the queue	8192 bytes	Second	0

The first strategy gave B a turn but left the remaining 7168 bytes of A. Do not interpret 0 next events as 0 bytes of input. The second handles B quickly while continuing A's work. This is a controlled result for two connections, and it does not prove a latency upper bound or a performance improvement rate for all traffic.

Keep the queue from becoming a new memory leak

Even if the same connection shows up on every select, put it in the queue only once. A deque takes care of the order and a set takes care of membership. When you pop, you must also remove it from the set so that it can be put in again later. When a connection terminates, you must delete it from the queue too. If you use only the file descriptor number as the key, when the number of a closed FD is reused for a new connection, it can be confused with the earlier work. The lab uses the Dial object as the key, and the conceptual test tells them apart by attaching different generation numbers to the same FD.

A small budget is not always better

If you reduce the budget to 1, switching between connections gets more frequent, but the cost of queue management and system calls also grows. Conversely, if you give a large budget, the amount of work in one turn grows and control requests can be pushed back. Don't run only requests with the same total bytes; change the ratio of long requests to short ones. If you record throughput, the short requests' waiting, and the number of turns it took to observe a control request separately, you can explain what you gained and lost. The value "second turn" in this experiment is evidence for this input batch and not a guarantee that it would be second for any number of requests.

If the queue is non-empty and you sleep in select for 1 second, you postpone work you have already found. Make the next wait 0, but keep this turn's handling budget. Conversely, if there is neither a queue nor new work and you keep calling with 0, it becomes a busy wait. The wait time is computed not as "always short" but from the work that can still be done and the nearest deadline.

What it looks like in the field

If you look only at a download server's total transfer volume, the phenomenon of short control requests being pushed back can hide. Mix long and short connections, and observe together which turn the short connection gets handled on and the longest wait. If the structure is such that a single job computes for a long time, an I/O budget alone is not enough. Separating CPU work or limiting the amount of computation has to be designed separately.

What you will do in the next check

In the next quiz, you first check the counterexample for the ready queue. After that, in the combined lab's ReadyQueue, you implement deduplication, FIFO, and deleting terminated jobs. You verify the connection start budget and the completion handling budget separately. If you only build the queue and then write a loop that consumes everything at once, you do not achieve the purpose of this module.