Messages in this thread | | | Date | Thu, 7 Mar 2002 14:44:07 -0500 (EST) | From | "Richard B. Johnson" <> | Subject | Re: Fwd: [Lse-tech] get_pid() performance fix |
| |
On Thu, 7 Mar 2002, Hubertus Franke wrote:
> On Thursday 07 March 2002 09:54 am, Guest section DW wrote: > > On Thu, Mar 07, 2002 at 09:35:09AM -0500, Hubertus Franke wrote: > > ... > > > > Long ago I submitted a patch that changed the max pid from 15 bits to > > 24 or 30 bits or so. (And of course removed the inefficiency noticed > > by some people in the current thread.) > > Probably this is a good moment to try and see what Linus thinks > > about this today. > > > > [Of course Albert Cahalan will object that this is bad for the columns > > of ps output. Maybe Alan will mutter something about sysvipc. > > Roughly speaking there are only advantages, especially since > > I think we'll have to do this sooner or later, and in such cases > > sooner is better.] > > 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) > -
If security issues were not a concern, you save the last PID, freed at _exit() and use that immediately. If it's already used, it's zeroed. exit() just stuffs the exit() PID into the variable, overwriting any previous, including zero. It needs to be handled under a lock, but it gets a quick return on investment for the usual fork() exec() stuff that interactive users use.
Cheers, Dick Johnson
Penguin : Linux version 2.4.18 on an i686 machine (799.53 BogoMips).
Bill Gates? Who?
- 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/
| |