EXT2-fs panic: ext2_find_entry

Wed, 2 Aug 1995 06:11:15 -0500

"Mathew G. Monroe": "Processes in the Kernel" (Jul 28, 7:56):
> 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?

Mainly historical reasons. A doubly linked list is indeed a better
approach, but the array works well enough.

Actually, the array is seldom used any more: we do have a doubly linked
list as well (next_task/prev_task) and now we also have a doubly linked
list of runnable processes (next_run/prev_run). Most places use the
"for_each_task(p)" macro to go through all the processes.

> 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.

I think a priority heap is probably not worth it: the run-queue is
normally only a few processes deep, so a linked list makes sense (the
overhead of going through 2-3 processes to find the runnable one is
rather small, and doing a heap would make the add/remove operations
slightly more complex).

That said, feel free to try this out in real life: I haven't actually
tried a heap for this.