0

我正在研究航空电子操作系统（线程层），我正在寻找关于以下（简化）要求的最佳解决方案：“等待[各种对象]的线程按优先级顺序排队。对于相同的优先级，线程是也按 FIFO 顺序排队”。

[各种对象] 例如信号量。

我认为我可以使用经典链表构建这样的等待列表，这使得插入/排序相对快速和容易，并且完全符合预期的使用情况（一个线程一次进入等待状态）。但是我正在研究一个裸机目标并且我没有任何 libc 支持，因此我没有 malloc（这对于链表非常有用！）。

对于按优先级排序线程，我通常使用非常有效的二进制堆（http://en.wikipedia.org/wiki/Binary_heap），但这里不能使用它，因为不能以这种方式管理“FIFO 顺序”。

当然，我可以使用更经典的排序算法来做到这一点，但它们通常很耗时，即使是一次插入也是如此，因为每次插入时可能会移动很多数组元素。

所以我想知道是否存在合适的算法......也许是一种改进的二进制堆？......或者“静态”链表？......或者最好的东西是与链表相关的分配器算法？... .

有关信息： - 线程总数限制为 128，因此内存需求始终是有限的，并且可以在编译时知道/保留。- 我的数量或 RAM 有限，所以我几乎无法构建这样一个按 FIFO 上的优先级排序的二进制堆（自然按到达时间排序）......</p>

我真的很感激关于这个问题的任何想法和新的看法。

谢谢 ！

4

2 回答 2

0

可能您需要一个稳定的就地排序 - 它会在按优先级排序后保持项目的相对顺序，满足您的 FIFO 要求。

从 wiki 中的列表中选择任何内容，例如就地合并排序、块排序和 tim 排序都是就地且稳定的： http ://en.wikipedia.org/wiki/Sorting_algorithm

关于内存分配和链表——也许你可以实现自己的 malloc？您可以分配固定大小的堆（128 * 线程信息大小），然后使用每个块的索引作为指针。所以指向对象的真正指针将是（堆起始地址）+索引*（块大小）。然后像往常一样实现排序，但使用索引而不是指针。

另一个想法是将 FIFO 要求与优先级队列要求分开，并对具有相同优先级项的队列的容器进行排序——但这需要动态列表分配和更大的堆。

于 2014-06-25T08:01:44.123 回答
0

这个问题的标准技术是 Bentley-Saxe 优先队列。我将在此处详细描述它，以及如何以最小的内存要求就地实现它的一些技巧，但我所说的只是重申 Pat Morin 在 CS Theory StackExchange 上的出色回答：Pat Morin 对“是有稳定的堆吗？” 关于 cstheory.SE

于 2017-03-10T05:52:08.467 回答