Ingo Molnar, in his project to give Linux "world-class threading support,"
has set his sights on another Linux performance problem: the allocation of
process ID (PID) numbers for new processes. This does not seem like it
should be a difficult problem, but the current kernel get_pid()
shows quadratic behavior when the number of processes gets large.
Essentially, the algorithm looks like this:
for each possible PID
for each task in the system
if task_pid == pid
The above is an oversimplification, since the get_pid() code tries to
find a range of usable PIDs, not just one. Look here for
the real get_pid() implementation. The point is that, with very
large numbers of processes (i.e. on the order of 100,000),
process ID allocation can lock up the system for long periods of time.
Ingo's solution starts with some work done
by William Lee Irwin. William's "idtag" infrastructure adds hash tables
for managing things with numeric ID tags; it is used in this patch to
manage PID-related things like process groups and session IDs. The idtags
help to eliminate many iterations over the whole process space done in the
kernel, but do not solve the PID allocation problem.
Ingo handles PID allocation through a new allocator that he wrote from
scratch. This allocator maintains an array of pages (allocated as needed)
which are used as PID bitmaps; allocating a new PID becomes a matter of
finding a page with a free PID available, then finding and clearing the
first set bit. It all happens with no locking required. Ingo claims:
Ie. even in the most hopeless situation, if there are 999,999 PIDs
allocated already, it takes less than 10 usecs to find and allocate
the remaining one PID. The common fastpath is a couple of
So it's fast - though a few extra features
have been requested. But this patch has stirred up a bit of a debate.
Rather than put in a complicated new PID allocator, it is asked, why not just make the
maximum PID be very large? Then, in theory, the quadratic part of
get_pid() will never run so the performance problems go away, and
the code stays simpler. Linus prefers this
approach, as do a number of other developers; he has put a simple patch
along these lines into his pre-2.5.37 BitKeeper tree.
Ingo disagrees, pointing out that any
reasonable maximum PID size can be exceeded eventually. He would rather
fix the problem than try to hid it behind a large process ID space. In the
absence of real-world examples that show people being bitten by
get_pid()'s behavior in a larger PID space, though, Linus appears
unlikely to accept any more complicated fix.
to post comments)