在内核级别实现链接列表有什么用 [英] what is the use of implementing linked list at kernel level

问题描述

在内核级别实现链接列表有什么需要?在设计内核时可以实现链接列表的任何特定实时方案(可能是新内核).

感谢您的输入:)

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 :)

推荐答案

不需要 来完成此操作，但是在很多地方它可能是一个非常有用的设备.

There is no need to do it, but it may be a very useful device in lots of places.

一个例子就是计时器.计时器通常按链接列表排列.

这样一来，在时钟中断下仅需递减一个值.

例如，如果您的计时器要在10、30和100秒后到期，则您将有
链表中的3个值，如下所示:
10、20和70.
这意味着:第一个计时器在10秒后过期，第二个计时器在20秒后过期，第三个计时器在第二个70秒后过期.

然后，如果您要添加另一个将在25秒后到期的元素，请将其插入列表中的适当位置(#2)，调整下一个元素(从20到5)，列表将如下所示:
10，15，5，70

时钟滴答滴答时，您仅会减小磁头值，例如:
9、15、5、70

插入和删除时需要更多的处理，但值得-请阅读以下内容.

如果与链接列表相反，将它们保存在一个数组中，则每次时钟中断发生时，都必须递减每个运行的计时器.如果您有很多计时器，那可能会非常庞大​​.

顺便说一下，我并不是在整理它，这是我所见过的大多数RTOS的工作方式.

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 .

也许它需要重入或指向只读存储器结构. .

通常，除非列表很大，或者在随机位置有很多插入/删除操作，否则动态数组(或stl向量)的效率要高得多.

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.

这篇关于在内核级别实现链接列表有什么用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！