Finding available process IDs

[justin]

How do you guys set the process ID when you are creating a new process? I read JamesM's multitasking tutorial where he stores the next available PID in a variable and increments it each time a process is created. But it seems you could run out of PIDs with this method if your OS is running for a long time. I thought about searching through the process list for an available ID but it seems costly.

Any suggestions?

Thanks,
Justin

[JohnnyTheDon]

Bitmaps maybe? This would be fairly fast. And creating a process is a costly process anyway, since you have to allocate page tables and other stuff when a process is created anyway. A linear search isn't a big deal.

[gzaloprgm]

http://forum.osdev.org/viewtopic.php?f= ... &sk=t&sd=a

Cheers,
Gonzalo

[clange]

Keeping track of a free range of pid's would be quite fast:

- Initialize range as 0 to MAX.
- Each time a new pid is needed use the lowest value of the range and then increment the lower range.
- When the range is empty scan the process list for a new range of empty pids. This will be very fast is the list is already sorted and you only have to find the first empty range.

Assuming that the pid range is 32-bit you will have mostly empty ranges (the number of processes will certainly be limited by the amount of memory).

If you just go with 64-bit ranges and assuming you start 100 processes each second you will have enough pid's for the next 5 billion years or so.

clange

[skwee]

As far as I know Linux uses the way you described, it keeps an integer for example (not sure if is an integer) and sets it to 1, first process to run is "init" that gets pid 1, then this integer increments and you got next free pid 2 and so. I really doubt you will have to execute more than 4 milliard process, and if yes then you need to redesign your OS

[abachler]

windows does the same thing, start with PID 0 and increment it each time. Assuming you start 100 processes per second, you need to restart the system every 1.36 years. I dont think its realyl an issue with real world deployments. You could always verify that the PID is available by scanning the list of running processes.

[Brendan]

Hi,

I really doubt you will have to execute more than 4 milliard process, and if yes then you need to redesign your OS

I wouldn't be so sure (for 32-bit process IDs), because most C library functions treat the process ID as signed. For 2147483648 process IDs, with an average of 1 new process per second you run into trouble after the OS has run for about 68 years (which entirely possible for well written OSs IMHO).

Now imagine a server that's used to rebuild a large project when the source files change (e.g. each time something is committed to CVS). In this case, "make", the compiler, assembler and linker are all separate processes and the compiler and assembler might be run for every source file.

Alternatively, how about a busy web server where a new process is spawned each time anyone accesses any computer generated web page.

The "average of 1 new process per second" assumption is very dodgy. At an average of 1000 new processes per second you'd run out of process IDs before 29 days have passed. If process ID's were unsigned then you'd still only get 49.71 days of uptime.

Using 64-bit process IDs would make a huge difference - you could start an average of 40000 billion processes per second (but still run out of process IDs after a few months)....


Cheers,

Brendan

[Craze Frog]

Bitmaps maybe? This would be fairly fast. And creating a process is a costly process anyway, since you have to allocate page tables and other stuff when a process is created anyway. A linear search isn't a big deal.

Page allocation can be done in constant time, compared to that, a linear search through 2000 processes with half of the process control blocks swapped out is a very big deal.

[JohnnyTheDon]

Bitmaps maybe? This would be fairly fast. And creating a process is a costly process anyway, since you have to allocate page tables and other stuff when a process is created anyway. A linear search isn't a big deal.

Page allocation can be done in constant time, compared to that, a linear search through 2000 processes with half of the process control blocks swapped out is a very big deal.

Only if the they're swapped out. Its probably not a good idea to swap out entries in the process table, since these are used so often. A bitmap is probably the best idea anyway, because then you can use "lock bts" which is atomic so you don't have to worry about problems with multitasking or SMP systems.

[Craze Frog]

Even if they weren't swapped out, I'd say it's a big deal compared to page allocation (which should be blazingly fast and in constant time).

A bitmap for 32-bit ids would be 512 mb, or am i getting mad?

[gzaloprgm]

2^32 = 4 294 967 296 = 4GB

A bitmap would take 4GigaBit = 512MB.

You are right

Searching trought it would take a long time.

[Craze Frog]

2^32 = 4 294 967 296 = 4GB

A bitmap would take 4GigaBit = 512MB.

You are right

Searching trought it would take a long time.

Yes, then I prefer the linear search offered earlier instead.