Organizing execution of events in a distributed system and avoid deadlocks

Question

I have an issue prioritizing events in my system. I have a simple class which can subscribe to each others output

public interface INode<TIn, TOut> : IBaseNode
{
    event EventHandler<TOut> Output; 
    //Note: subscribe just calls node.Output += this.OnInput
    void Subscribe(IBaseNode node);
    void OnInput(object sender, TIn input)
} 

using this I can chain nodes together by subscribing to their output

CarDealerNode.Subscribe(NewModelNode);
LoggerNode.Subscribe(CarDealerNode);

My issue is that when an event fires off, it happens in an semi-undeterminstic breadth first manner. I would like to maintain the order of the execution of these events so I can prioritize event execution in a more dynamic manner.

My first impression is to use a some priority queue to sort the tasks, However this may cause issues because lower priority things may never execute

public class SynchronizationInfo
{
    public SyncPriority Priority { get; set; } = SyncPriority.Normal;
    public object Sender { get; set; }
    public DateTime Created { get; set; } = DateTime.Now;
    public Task Operation { get; set; }
}

public class SynchronizationContext
{
    public PriorityQueue<SynchronizationInfo> ExecutionQueue = new PriorityQueue<SynchronizationInfo>();
    //...
}

However I'm still having trouble of grasping a way to assure that dead locks won't occur, If something of a high priority is added at a quicker rate than the execution of that priority, lower priority events won't execute.

Additionally, just because something is over-lower priority doesn't mean everything of higher priority should go first, time is a big factor.

Is there a solid efficient recommended way of handing priority execution of tasks. In a way that no task experiences dead-lock, (e.g time increases priority in a way in which lower priorities are moved up to assure execution)?

Answer 1

Why have one queue when we can have more?

This works for any constant priority count although a low-enough number is preferred. (From what I can see you have an enum for them so there are likely just a few priorities). Also, we won't be using a priority queue but several ordinary queues.

• Make a queue for every priority. The task gets registered to a queue according to it's priority. For every task store the creation timestamp as @Funk does.
• When you wish to process next task, check the timestamp for the available element in every queue.
• This allows you to detect long-overdue lower priority tasks and to increase their priority.

The increase of the priority can be done in several ways. For example:

• Start the task execution directly when it is in the queue long enough. (E.g high_creation_time > medium_creation_time + C -> run the medium priority task)
• Re-schedule the task to the queue with higher priority instead of running directly.

Which way is more suitable for you is a bit hard to tell.

The complexity of this approach:

• Adding new task: O(1) - just add it to it's respective queue
• Running a task: O(1) - assuming that we have constant number of priorities, this is just a matter of checking all the queues and finding the element that should run next.
• Rescheduling a task(if applicable) - one push and one pop, thus O(1)