Processes in the Kernel

Mathew G. Monroe (
Fri, 28 Jul 1995 07:56:01 -0400 (EDT)

I dont know if this has been hashed over before. I was talking to someone
about the linux kernel and he was amazed that an array was used to store
the processes. He said using a double linked list for processes is what
he has always used, and been told was best. To me this would also seem
best. The question is, why does linux use a table?

I can see many advantages to the linked list. First, no process limit,
unless the super user wants to set one. Should really cut down the
time find_empty_process generally takes to run. Should reduce kernel
size, no fixed array, generally the list will be smaller then the current
array. The disadvantage I see is the kernel memory has to be allocated,
but this only needs done once for each process.

What are the advantages of the array?

I also have a second question about the scheduler. The run queue way just
added, but I one thing I think can improve it. Why isn't a priority heap
used for it. If you used a priority queue then in the main scheduler you
would not have to run through all the runable tasks, you would know the
one with the highest countable. Of course you would have to rebalance
the heap every time a task changed it countable, but this should always
be faster then going through the list of runable tasks as is done now.
As long as you are careful about it you should even be able to keep
interupts on during the scheduler, you aren't looking at all the runables
just the one at the top. Any comments on this?

I am asking about these thing because I am interested in actually doing them,
but I want to be sure I am not missing something major before I go off and
spend the time to try and do them.