Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

On *nix, PIDs are unique identifiers for running processes. How are PID's generated? Is it just an integer which gets incremented or a more complex structure such as a list? How do they get recycled? By recycling I mean that, when a process terminates, it's PID will eventually be reused by another process.

share|improve this question

migrated from stackoverflow.com Apr 27 '10 at 0:08

This question came from our site for professional and enthusiast programmers.

    
lwn.net/Articles/10238 –  Helltone Apr 26 '10 at 14:48
add comment

4 Answers

up vote 16 down vote accepted

As wikipedia says,

Under Unix, process IDs are usually allocated on a sequential basis, beginning at 0 and rising to a maximum value which varies from system to system. Once this limit is reached, allocation restarts at zero and again increases. However, for this and subsequent passes any PIDs still assigned to processes are skipped.

so it's really a very simple policy for "generation", just increment a counter, and "recycling", just wrap the number around at a max value and keep incrementing until you find a number that was assigned to a process that has finished and has been removed from the process table.

Some Unix implementations such as AIX use a policy that's less simple, see e.g. this FAQ.

share|improve this answer
    
Thanks for the answer. By the way, what is exactly this AIX policy "that's less simple"? –  Helltone Apr 26 '10 at 14:38
1  
@Helltone, I don't think AIX documents exactly what policy it uses (so it could change at any release), but you could think of it as a random number generation in the appropriate range (which gets repeated until a PID is generated that's not currently in use). –  Alex Martelli Apr 26 '10 at 14:49
    
This algorithm seems a bit problematic to me. How do you ensure that you do not run into deadlock? And isn't there a performance problem? –  Helltone Apr 26 '10 at 14:56
    
The kernel is in control and need not lock anything, so how could it deadlock? Yes, there is a small performance price to pay (a small extra overhead at fork time -- say a couple dozen machine instructions for a congruential PRNG or /dev/urandom read, vs many fewer for a counter-increment), but that's always the case for measures intended to improve security (check the CPU overhead of HTTPS communication vs plain HTTP for example;-). –  Alex Martelli Apr 26 '10 at 15:26
    
I meant livelock (while(true);), sorry, I was quick answering ;-) –  Helltone Apr 26 '10 at 16:34
show 2 more comments

It varies.

Most systems simply keep a count of the last PID generated, add one (wrapping at a maximum number such as 65535 or a bit smaller - often the wrap occurs at 65000 or even 60000), and check that the number is not currently in use (repeating if the PID is still in use - so PID 1, the kernel, is still there and doesn't get 'reissued').

Other security minded systems generate a number at random and check that it is not in use.

At any given time, it is guaranteed that all PID numbers are unique.

share|improve this answer
add comment

They're sequence numbers and wrap round (at an OS-specific value) if the system is up for long enough. Numbers are never reused unless they're free at the point of fork().

share|improve this answer
add comment

As to the recycling part of the question, one thing to keep in mind is that a pid does not become available as soon as the process with that pid terminates. The pid does not become available until the parent of that process collects the termination status of its child via some form of the wait() system call. A child that is terminated but whose parent has not issued a wait is called a zombie and will usually show up in a ps as defunct. It is possible for an ill-behaved parent to starve the system of pids if it launches children and does not wait() for them.

If the parent of a process dies before it collects the status of a child, that is ok. The child is inherited by init who will make sure a wait() is issued and the pid is recycled.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.