Subject: Re: new pid allocation code
To: None <>
From: gabriel rosenkoetter <>
List: tech-kern
Date: 03/17/2003 14:55:43
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Mon, Mar 17, 2003 at 02:33:00PM -0500, der Mouse wrote:
> Not quite.  As you point out elsewhere, it depends on the constant
> factors.  Indeed, since there is a fixed maximum PID, theoretically,
> any way is O(1) because it is dominated by whatever the worst case is
> over the (finite!) set of all possible used/unused PID distributions.

Heh. True.

As I said, *assuming* that c & k for both algorithms are vaguely
congruent, then o(1) beats o(n^2), and David's not too likely to
have made the comparison if they weren't somewhat close.

Having slightly larger constants is probably acceptable. That is,
the current scheme seems to be running around with mostly 5-digit
PIDs on a system that's been up for a month now. One presumes it's
within its constraints at this point, though I guess I don't really
know that. If David's system behaves about the same for a week and
then significantly better, it's better. If it takes more than a
month's worth of PID allocations to hit its o(1) state, then we're
maybe not so happy (show me a production system running *any* OS
that hasn't been rebooted in a month or two and I'll show you a
security nightmare).

gabriel rosenkoetter

Content-Type: application/pgp-signature
Content-Disposition: inline

Version: GnuPG v1.2.1 (NetBSD)