Re: Call for testers: New PID allocator patch for -CURRENT

----- Original Message ----- 
From: "David Schultz" <das_at_FreeBSD.ORG>
To: "Xin LI" <delphij_at_frontfree.net>
Cc: <hackers_at_FreeBSD.ORG>; <current_at_FreeBSD.ORG>; <junsu_at_delphij.net>
Sent: Friday, January 30, 2004 4:04 AM
Subject: Re: Call for testers: New PID allocator patch for -CURRENT


> On Thu, Jan 29, 2004, Xin LI wrote:
> > Greetings, everyone
> >
> > A friend of mine has ported NetBSD's new PID allocation[1] code to
FreeBSD,
> > you can obtain the patch here:
> >
> > http://www.arbornet.org/~junsu/pid.diff
> >
> > Some of you may be already aware of this for he has posted[2] this to
both
> > current_at_ and hackers_at_ last September.
> >
> > Currently the patchset has been updated to make it applicable to -HEAD.
> >
> > A number of problems were found and fixed after the first post with many
> > from the FreeBSD community, and we think it's time to post it again and,
> > if you are interested, please give it a chance to run on your own (test)
> > box.
>
> Thanks for the reminder.  Your patch uses a very clever idea.  I
> messed around with the original patch in your PR a few months ago.
> It would take more work to prove that your proposed patch improves
> performance[1] and is a good approach, and to review and clean up
> the implementation.  For instance, it isn't immediately obvious
> that the accelerated pid reuse is acceptable, so that needs to be
> looked into further[2].  I don't have the time at the moment to go
> over the patch with a fine-toothed comb, and jhb_at_ could do a
> better job than me anyway if he has time, but I wanted to let you
> know that it's floating around on at least one person's TODO list.
Thank you for your great feedback. Olivier Houchard contacted to me about
this patch. He also worked on this patch before. I am sorry I didn't
mentioned him in the first email.

>
> Some low-hanging fruit: The patch needs to be cleaned up to
> conform to style(9).  It also changes the meaning of PID_MAX and
> fails to enforce a 5-digit limit on pids.
PID_MAX is now a initial value for the
max pid value. When the concurrent process number is large than PID_MAX. We
will assign PID_MAX *2 to pid_max.

For 5-digit limit, I think I need add this type of check into the patch.

>
>
> [1] That shouldn't be hard, given that the present algorithm takes
>     O(N) amortized time in the worst case, and can examine as many
>     as PID_MAX^2 pids if the number of processes in the system is
>     close to PID_MAX.
>
I think this algorithms for proc_alloc, pfind and zpfind are all O(1). The
worst situation is that
it reaches PID_MAX. In this situation, we need expand our pidtbl. This may
bring some delay. However, this situation will only occurs few times. If a
machine need 1000 concurrent process, it will only need a 2 ^ 10 slots
process table. From the original 2 ^ 5 table, we need only 5 times to expend
the table.

> [2] Many systems have a high enough fork rate that pids recycle
>     every few minutes or hours with the present algorithm.  These
>     systems don't necessarily have lots of processes running at any
>     given time, so the table (and thus the cycle length) in your
>     patch could remain relatively small if I'm interpreting the
>     code correctly.  I think the code would have to be changed to
>     prevent reuse from happening too quickly in wall time.
Reusing the proc slot doesn't mean reusing the pid. Everytime we
reuse a proc slot, we will add pidtbl_mask to the pid. We reuse
the pid when the pid reach the max_pid. Therefore if a user wants, he can
increase
the max_pid to a larger number to increase the period that the pid is not be
reused. I will add a sysctl to allow user to adjust max_pid.

> _______________________________________________
> freebsd-current_at_freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-current
> To unsubscribe, send any mail to "freebsd-current-unsubscribe_at_freebsd.org"
>
>