Scalable Network Programming
The fork-and-do-something latency on my notebook on Linux 2.6 is 200
microseconds. That means my notebook can create 5.000 processes per second. Thus my notebook can handle about 13 billion forks per month. My Athlon XP 2000+ desktop can do 10.000 processes per second, or 26 billion per month. Heise Online, the biggest German site, had 118 million page impressions in September.
Scheduling
Why does the fork benchmark include writing to the pipe? Because having many processes not only makes creating more processes more difficult, it also makes choosing which process to run more difficult. The part of the operating system that chooses which process to run next is called the scheduler. A typical workload is having two dozen processes, with one or two of them actually having something to do (they are runnable).
Linux interrupts running processes every 1/100th second (1/1000th on Alpha; this value is traditionally called HZ on Unix and Linux and is a compile time constant) to give others a chance to run. The scheduler is also activated when a process blocks (waiting for input, for example). The scheduler’s job is to select the process that should run next. What makes this hard is the fairness requirement: all processes should get an equal share of the CPU. In particular, no process should starve. It obviously makes sense to have two lists: one for the runnable processes, one for the blocked ones.
Unix has a mechanism to favour interactive processes over batch jobs. To that end, the kernel calculates a nice value for each process once per second. When there are 10.000 processes, this thrashes the 2nd level cache. This is especially bad for SMP, because the process table must be protected by a spinlock, i.e. the other CPUs can’t switch processes while the first CPU calculates the nice value. The typical solution from the commercial Unices is to have one run queue per CPU. Further optimizations include keeping the run queues sorted, for example with a heap, or having one run queue per priority.
Download file here
