Messages in this thread |  | | Date | Wed, 11 Sep 2002 13:23:34 -0700 | From | jw schultz <> | Subject | Re: [PATCH] pid_max hang again... |
| |
On Wed, Sep 11, 2002 at 07:19:34PM +0200, Andries Brouwer 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 > > 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 clarification. The problems were triggered when PID_MAX was 2^15. Linus has bumped it with a recomendation of somthing on the order of 2^20 - 2^24 not 2^30 to allow for SSI clusters.
Once last_pid cylces we do a complete scan of the task list testing four task_struct values for every free pid we get. If the attempted pid is in use the scan will abort (somewhere about half way through, perhaps less, on average) and a new scan will be started. The increase of PID_MAX will (when it takes effect) dramatically reduce the frequency of collisons causing rescans but not eliminate them.
I am less certain than you that a little more structure managment on fork and exit might not reduce the amount of scanning we have to do. From what i see in sched there is lot of task list scanning going on there as well. Structure management is a fixed cost. The cost of scanning the entire task list is linear.
> 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.
Let's relax and see what comes out. Maybe someone will suprise you. I trust Linus to reject patches that make things worse especially if they haven't been vetted by a leutenant.
-- ________________________________________________________________ J.W. Schultz Pegasystems Technologies email address: jw@pegasys.ws
Remember Cernan and Schmitt - 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/
|  |