Priority Inversion and Precedence Constraints in Task Management

Aug 09, 2022

Table of contents:

  1. What is Priority Inversion?
  2. What is an example of Priority Inversion?
  3. What is Priority Inheritance?
  4. What are Precedence Constraints?
  5. How to choose what to work on next?

One of the most difficult things in deciding what to work on next is getting the balance right between priority and dependencies. Usually tasks don’t exist in isolation, every task on your task list will have different priorities and certain tasks will need to be completed before other tasks can be started.

Understanding how to choose the right thing to work on next with these two things in mind is incredibly difficult.

However, there are two concepts that can help. Once you understand these concepts, it makes it a lot easier to understand the best way to manage this balance. These two concepts are priority inversion and precedence constraints.

What is Priority Inversion?

Priority inversion is a concept that comes from computer science scheduling theory. It’s when a high priority task is blocked by a low priority task because the low priority task has been interrupted whilst having a lock on a shared resource.

This means both tasks end up being blocked because you can’t complete a low priority task before a high priority task.

Instead, medium priority tasks are completed instead of the high priority task that you should be working on. This can end up having very problematic consequences if the high priority task is not completed in a timely fashion.

What is an example of Priority Inversion?

Let’s take a look at a real life example of where priority inversion might occur.

Imagine you have a long list of tasks. You’re feeling overwhelmed and so you decide you need to dramatically reduce the number of things on your plate to give yourself some breathing space. You decide to use the “shortest processing time” to complete tasks that can be finished quickly.

One of the tasks you have been neglecting because it’s low priority is that you need to take your computer into the shop because the keyboard was starting to not work correctly. It was manageable, but it’s one of those things you kept putting off. Instead of hanging around at the shop waiting for it to be fixed, you decide to come home and work on some other tasks.

However, when you get home, you receive emails from a couple of your long standing clients.

One message is a high priority task for one of your most important (and highest paying!) clients. You can start the initial sketches on paper, but will need your computer to complete the work. The other messages are from clients for medium priority tasks that can all be completed without a computer.

You can start the high priority sketches, but you won’t be able to complete the task and send over the work until you have your computer back. However, picking up your computer is considered a “low priority” task, particularly because it’s going to take a couple of hours to go into town to collect it.

So instead of finishing the high priority task, you start to work through the medium priority tasks that you can complete at home with the resources you have.

This is the wrong way to think of it. You need to complete the high priority task, but the only way to do that is to complete the low priority task first. This violates our internal priority model where only higher priority tasks can take precedence over lower priority tasks.

What is Priority Inheritance?

When a low priority task is blocking a high priority task the low priority task is now the most important task. This is because the high priority task has been indirectly superseded by the low priority task, and therefore the priority of the tasks have been inverted.

You can think of this as the low priority task has inherited the priority of the high priority task as it has become a blocker and the only way to complete the high priority task is to complete the low priority task first.

When there is a dependency relationship between tasks, where one task can’t be started or completed until another task has been completed, we call that precedence constraints.

What are Precedence Constraints?

Precedence constraints are where you can’t start a task until a different task has been completed.

For example, you can’t create the blog post social share images until the blog post is written because you need the title, theme and content of the post to have a good idea of what should be included in the image.

This can make many of the ways in which we’ve previously looked at organising your work difficult, or impossible. Methods like “minimise maximum lateness” or “earliest due date” become a lot more tricky to implement when your tasks also have dependencies between each other.

When one task is dependent on another task to be completed before itself can be completed, there’s no way around not doing the dependent task first. Precedence constraints can also cause priority inversion as we’ve seen above, where a low priority task is blocking a high priority task and therefore must be completed first.

So what’s the solution when your tasks have dependencies?

How to choose what to work on next?

A relatively simple way of choosing what to work on next when your tasks are dependent is to order them by dependency and then then by what you want to optimise for.

For example, the first thing you would do would be to sort your tasks by dependency so that the tasks at the top of your list are the ones that aren’t dependent on any other task being completed first. This means nothing is blocking those tasks, even if they aren’t the most important or highest priority tasks on your task list.

You could then sort these tasks by “shortest processing time”, “minimise maximum lateness”, or by “earliest due date”.

After every completed task you can then re-evaluate the tasks that are now free of dependencies, move those tasks to the top of the list and then once again sort by the method you want to optimise for. You would then continue by keep repeating this process

Philip Brown


© Yellow Flag Ltd 2024.