0

我想实现一个能够在 FIFO 模式和优先级模式下运行的队列。这是一个消息队列,优先级首先基于消息类型:例如,如果A类型的消息比该B类型的消息具有更高的优先级,那么所有A类型的消息都会首先出队,最后类型的消息B出队。

优先模式:我的想法是使用多个队列,每种类型的消息一个;通过这种方式,我可以根据消息类型管理优先级:首先从队列中以较高优先级获取消息,然后逐步从较低优先级队列中获取消息。

FIFO 模式:如何处理使用多个队列的 FIFO 模式?换句话说,用户看不到多个队列,但它使用队列就像它是单个队列一样,以便在禁用优先级模式时消息按照它们到达的顺序离开队列。为了实现第二个目标,我考虑使用另一个队列来管理消息类型的到达顺序:让我用下面的代码片段更好地解释一下。

int NUMBER_OF_MESSAGE_TYPES = 4;
int CAPACITY = 50;
Queue[] internalQueues = new Queue[NUMBER_OF_MESSAGE_TYPES];
Queue<int> queueIndexes = new Queue<int>(CAPACITY);

void Enqueue(object message)
{
    int index = ... // the destination queue (ie its index) is chosen according to the type of message.
    internalQueues[index].Enqueue(message);
    queueIndexes.Enqueue(index);
}

object Dequeue()
{
    if (fifo_mode_enabled)
    {
        // What is the next type that has been enqueued?
        int index = queueIndexes.Dequeue();

        return internalQueues[index].Dequeue();
    }

    if (priority_mode_enabled)
    {
        for(int i=0; i < NUMBER_OF_MESSAGE_TYPES; i++)
        {
            int currentQueueIndex = i;
            if (!internalQueues[currentQueueIndex].IsEmpty())
            {
                object result = internalQueues[currentQueueIndex].Dequeue();

                // The following statement is fundamental to a subsequent switching
                // from priority mode to FIFO mode: the messages that have not been
                // dequeued (since they had lower priority) remain in the order in
                // which they were queued.
                queueIndexes.RemoveFirstOccurrence(currentQueueIndex);

                return result;
            }
        }
    }
}

你怎么看这个想法?有更好或更简单的实现吗?

4

1 回答 1

2

应该管用。然而,简而言之,我的想法是

a)不是线程安全的,需要做很多工作才能做到这一点。b) 不是异常安全的——即排队或出队的异常可能会留下不一致的状态——也许不是问题,例如如果异常是致命的,但也许是。c)可能过于复杂和脆弱,尽管我不知道它正在使用的上下文。

就个人而言,除非我进行了分析并证明存在性能问题,否则我将拥有一个“容器”,优先级模式将遍历容器寻找下一个最高优先级的消息——毕竟它只有 50 条消息。我几乎肯定会使用链表。我的下一个优化是将一个带有指向每个消息类型的第一个指针的容器放入该容器中,并在消息出队时更新指针。

于 2012-09-25T01:51:37.343 回答