delorie.com/archives/browse.cgi   search  
Mail Archives: cygwin-developers/1998/03/21/13:23:36

From: cgf AT bbc DOT com (Christopher Faylor)
Subject: Re: Process ID allocation methods
21 Mar 1998 13:23:36 -0800 :
Message-ID: <Eq6H3D.2Fp.cygnus.cygwin32.developers@bbc.com>
References: <199803210734 DOT XAA30358 AT skaro DOT cygnus DOT com>
Reply-To: cgf AT bbc DOT com
To: cygwin32-developers AT cygnus DOT com

In article <199803210734 DOT XAA30358 AT skaro DOT cygnus DOT com>,
Geoffrey Noer  <noer AT cygnus DOT com> wrote:
>In the original pid allocation scheme, lookups could take a while
>because a pid could be anywhere in the table.  In Chris Faylor's
>scheme that was included in b19, pids were forced to be a PBASE offset
>to the actual index in the process table.  In this scheme, pids
>wrapped every 128th (PSIZE) process. 

Was there a problem with this wrapping?  On any UNIX system I've seen,
the mechanism for pid allocation was always sort of a black box.  The
only thing you could really be sure of was that once you get a pid
you won't get that same pid number anytime "soon".  I've never seen one
that wraps at "INT_MAX".

>In the new scheme, I'm using modular arithmetic to map from a pid to an
>index (which I believe should be fast enough).  This allows us to have
>more standard pids (1000 to INT_MAX) without wrapping all the time.
>Because we skip numbers whenever the new potential pid mod size ()
>maps to a slot already taken by a previous process, as more slots are
>filled, more pids are skipped.  I don't see this as a real problem.

Actually, if you want to go back a couple of revisions, I'd already
done the pid allocation exactly this way.  There was, of course, more
scanning of the pid table when long lived processes didn't vacate their
"slot".  The pid == 1000 + slot number seemed a lot cleaner to me and
it is slightly faster.

>The next step is to extend this to remove the upper limit on the
>number of concurrent processes.  I'm planning on either:
>
>1) Having a linked list of PSIZEd process tables.  Start out with one,
>if you fill it, allocate another.  So with two tables, when you
>allocate, you would first try to allocate a PSIZE range of pids in the
>first table, then try to allocate a PSIZE range of pids in the second
>table, creating a third table if there aren't any slots in either.
>Lookups would involve doing a pid mod size() and then checking that
>position in each existing table.
>
>Under this scheme, lookups get slower as the number of process tables
>increase.  However, this might not be a noticeable performance hit.
>
>2) Alternatively, when the first table runs out of room, you could
>allocate a larger single table, increasing PSIZE and remapping all
>existing processes within the table (in order to keep the pid mod
>PSIZE relationship consistant).
>
>This involves a large up front cost whenever you have to increase the
>table size but lookups would stay fast.

I think that either of these schemes would be hard to do.  You'd
have to somehow instruct every running process to extend its shared
memory to include the new table(s).

Have there been complaints about the pids wrapping too fast or have people
been running out of pids?
-- 
http://www.bbc.com/	cgf AT bbc DOT com			"Strange how unreal
VMS=>UNIX Solutions	Boston Business Computing	 the real can be."

- Raw text -


  webmaster     delorie software   privacy  
  Copyright © 2019   by DJ Delorie     Updated Jul 2019