Re: Kernel Internals

David A Rusling (
Tue, 04 Feb 1997 09:41:18 +0000

> Ted mentioned that this is only done in places that are not time
> crititical. So, what? To me it makes sense to have the process table
> defined as an array to be able to "jump" and not "traverse." What
> advantages would traversing bring over jumping? Since the array is
> already being defined, why not use it?

The array is used as an allocation mechanism as much as anything else.
There is usually a time versus space element to this type of problem.
Linux has gone for a little processing overhead when dereferencing PIDs
as against more space required to keep a hash table (or whatever).
As for the pids not being indexes, there is some attempt to make them
reasonably unique within the lifetime of the OS. However, I'm not sure
why (I can guess though).

> Ted has already addressed the question of why PIDs are not direct
> indexes into the process table. But if speed of access was a problem,
> the kernel could use a binary tree that keeps pointers into the table
> in sorted order.

The question is "is this inefficient?" If it is impacting system performance
enough, then is it worth changing?


David A Rusling Principal Engineer
European Semiconductor Applications Digital Equipment Co Ltd.,
Engineering PO Box 121,
Imperial Way,
Worton Grange
Reading RG2 0TU
Linux, Alpha, StrongArm, PCI Tel: UK-(0)1734-204380
Fax: UK-(0)1734-203133