What is the fastest collection in c# to implement a prioritizing queue?

Question

I need to implement a FIFO queue for messages on a game server so it needs to as fast as possible. There will be a queue for each user.

The queue will have a maxiumem size (lets say 2000). The size won't change during runtime.

I need to prioritize messages ONLY if the queue reaches its maximum size by working backwards and removing a lower priority message (if one exists) before adding the new message.

A priority is an int with possible values of 1, 3, 5, 7, 10.

There can be multiple messages with the same priority.

A message cannot change its priority once allocated.

The application is asynchronous so access to the queue needs to be locked.

I'm currently implementing it using a LinkedList as the underlying storage but have concerns that searching and removing nodes will keep it locked for too long.

Heres the basic code I have at the moment:

public class ActionQueue
{
    private LinkedList<ClientAction> _actions = new LinkedList<ClientAction>();
    private int _maxSize;

    /// <summary>
    /// Initializes a new instance of the ActionQueue class.
    /// </summary>
    public ActionQueue(int maxSize)
    {
        _maxSize = maxSize;
    }

    public int Count
    {
        get { return _actions.Count; }            
    }

    public void Enqueue(ClientAction action)
    {
        lock (_actions)
        {
            if (Count < _maxSize)
                _actions.AddLast(action);
            else
            {
                LinkedListNode<ClientAction> node = _actions.Last;
                while (node != null)
                {
                    if (node.Value.Priority < action.Priority)
                    {
                        _actions.Remove(node);
                        _actions.AddLast(action);
                        break;
                    }

                    node = node.Previous;

                }                    
            }
        }
    }

    public ClientAction Dequeue()
    {
        ClientAction action = null;

        lock (_actions)
        {
            action = _actions.First.Value;
            _actions.RemoveFirst();
        }

        return action;
    }

}

Answer 1

A vetted implementation of priority queue for C#/.NET can be found in the C5 Generic Collection Library in the C5.IntervalHeap<T> class.