I don't think that will solve the N^2 problem you still have the algorithm
do the following:
if (++last_pid > next_safe) {
repeat:
last_pid++;
foralltasks p:
deal with wraparound;
if (p uses last_pid) goto repeat
determine next_safe
}
[ last_pid ... next_safe ) is the range that can be saftely used
By extending it to 24 or larger bits all you do is handle the wraparound
at some later point and less frequent It also becomes expensive if a large
number of threads is present.
Well, the problem can be fixed. Even in the current 16 bit approach.
What we are experimenting around
is a <mark-and-sweep> algorithm that would be invoked if the nr_threads is
above a threshold.
The algorithm would do something like this. Rajan will code it up and see
its efficacy.
if (last_pid >= next_safe) {
inside:
if (nr_threads > threshold) { // constant
last_pid = get_pid_map(last_pid,&next_safe);
} else {
.. <as now>
}
}
static unsigned long pid_map[1<<12];
/* determine a range of pids that is available for sure
* [ last_pid .. next_safe )
* pid_map has stale information. some pids might be marked
* as used even if they had been freed in the meantime
*/
int get_pid_map(int last_pid, int *next_safe)
{
int again = 1;
repeat:
for_each_task(p)
mark_pids_in_bitmap;
last_pid = ffz(pid_map); /* we will start from last_pid with wraparound */
if ((last_pid == -1) && (again)) {
again = 0;
memset(pid_map,0);
goto repeat
}
}
next_safe = first_non_zero(pid_map,last_pid); /* starting from last_pid */
return last_pid;
}
Note, if the pid map is to large, it can be done in smaller sections or
windows. Also, note keeping stale information is OK actually desirable, as
it avoids the sweep in almost all cases.
-- -- Hubertus Franke (frankeh@watson.ibm.com) - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/