Re: [patch] lockless, scalable get_pid(), for_each_process() elimination, 2.5.35-BK

From: Martin Mares (
Date: Thu Sep 19 2002 - 14:27:58 EST

Hello, world!\n

> nevertheless we do lock up for 32 seconds if there are 32K PIDs allocated
> in a row and last_pid hits that range - regardless of pid_max. (Depending
> on the cache architecture it could take significantly more.)

What about randomizing the PID selection a bit? I.e., allocate PIDs
consecutively as long as they are free; if you hit an already used
PID, roll dice to find a new position where the search should be
continued. As long as the allocated fraction of PID space is reasonably
small, this algorithm should be very quick in average case.

Another possible solution: Divide PID space to blocks and for each
block, keep a counter of PID's available in this block and when
allocating, just skip blocks which are full. Runs in O(sqrt(PID space
size)) in the worst case.

                                Have a nice fortnight

Martin `MJ' Mares   <>
Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
This message is transmited on 100% recycled electrons.
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

This archive was generated by hypermail 2b29 : Mon Sep 23 2002 - 22:00:27 EST