On Wed, Sep 11, 2002 at 02:29:45PM +0530, Hanumanthu. H wrote:
> >> I don't know what the problem is. The present scheme is very
> >> efficient on the average (since the pid space is very large,
> >> much larger than the number of processes, this scan is hardly
> >> ever done)
>
> > The scan itself i don't mind. It is the rescan that bothers me
>
> And most of others too. One thing that strikes some minds
> immediatly after looking at current pid allocation, is the need
> for improvement. Well, even though the proposals are be clumsy,
> in-efficient (really ?) we should not ignore the fact that this
> is an area to improve. Ok, here is my final (more better) proposal
> which fixes the atomicity problem addressed by ManFred.
>
>
> Lets us have a structure to represent pid, session, pgrp and tgid.
>
> struct idobject {
> struct idobject *id_next;
> struct idobject *id_prev;
> int value;
> atomic_t users;
> task_t *taskp;
> };
Again. We have 2^30 = 10^9 pids. In reality there are fewer than 10^4
processes. So once in 10^5 pid allocations do we make a scan over
these 10^4 processes, that is: for each pid allocation we look at
0.1 other processes. This 0.1 is a small number. As soon as you start
introducing structures that have to be updated for each fork or exit,
things become at least ten times as expensive as they are now.
Some polishing is possible in that code. I think I once gave a shorter
and more efficient version. The fragment "if(last_pid & ~PID_MASK);
last_pid = 300;" occurs twice, and the correct version has it only once.
The correct version does not have the "goto inside".
But, the code may only become smaller and more beautiful.
Large ugly code can be justified only by the need for efficiency,
and there is no such need here, and indeed, none of the proposals
made things more efficient. Once the number of processes gets
above 10^5 we can invent simpleminded schemes to make this
for_each_task faster.
Andries
-
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/
This archive was generated by hypermail 2b29 : Sun Sep 15 2002 - 22:00:26 EST