Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Hi,
What is the need for implementing a linked list at kernel level ? Any specific real time scenario to implement a linked list while designing a kernel( may be a new kernel ).

Appreciate your inputs :)
Posted

There is no need to do it, but it may be a very useful device in lots of places.
 
Share this answer
 
Comments
enhzflep 29-Oct-12 16:39pm    
Good choice of emphasis. My 5.
Richard MacCutchan 30-Oct-12 4:35am    
Thanks, I'm not really sure what this is about, but it's quite possibly an interview question.
One example would be timers. Timers are often arranged as linked lists.

That way, only one value has to be decremented under a clock interrupt.

For example, if you have timers due to expire in 10, 30 and 100 seconds, you will have
3 values in a linked list, which looks like this:
10, 20 and 70.
This means: first timer expires in 10 seconds, second timer in 20 seconds after that, and the third one in 70 seconds after the second one.

If you then want to add another one expiring in 25 seconds, you will insert it in the appropriate position (#2) in the list, adjust the next element (from 20 to 5) and the list will look like this:
10, 15, 5, 70

When a clock ticks, you only decrement the head value, e.g:
9, 15, 5, 70

A bit more processing when inserting and removing but is worth it - read below.

If, as opposed to the linked list, you keep them in an array, you would have to decrement each and every running timer, every time the clock interrupt occurs. If you have lots of timers, it can be very substantial.

I am not making it up, by the way, this is how most RTOS-es that I have seen do it .
 
Share this answer
 
v2
Comments
Chuck O'Toole 30-Oct-12 11:29am    
Good explanation +5. It's how I implemented a process sleep queue in a RTOS from the '80's.
michaelmel 30-Oct-12 19:06pm    
I think we both are showing our age here :)
maybe it needs to be reentrant or points to read only memory structures..

in general, unless the list is very large or has many insertions/deletions at random locations, a dynamic array (or stl vector) is MUCH more efficient.
 
Share this answer
 
Comments
Chuck O'Toole 30-Oct-12 11:32am    
True. The ratio of "process the list" events versus "add or remove from the list" events is usually the deciding factor. Timers are something you scan every "tick" yet occasionally add (new process/thread sleeping) or remove (timer expiring) them.
Sure, unless you want to limit yourself to the number of processes that you can keep track of at once (i.e the number that are running) you'll need to either

(a) Set aside a fixed quantity of memory exclusively for this task or
(b) implement a linked list, that creates new nodes from the kernel's pool of memory.

That's how windows does it, you get a list to iterate throught, with the option of a callback at each node - you don't get the process list as an array - though you could build one from the list if it floated your boat.

Can't think of another just this moment, but it's a matter of efficient memory use.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900