Solving the process ID allocation problem

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
	        keep_trying

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:

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.

---

(Log in to post comments)