I went with this solution as it minimizes locking and ironically, the risk of deadlocks. The source of my issue is that openGL requires every task for a given openGL context to be performed in the same thread, this leads to tasks depending on other tasks for completion. Sometimes these tasks may end up in the same task queue and in the wrong order. The solution I have now simply finds out if a task waits for another in the same queue, and lets the one that is being waited for skip ahead.
Had the requirement to do certain tasks in a given thread not been there, task inter-dependencies would have disappeared and this problem would not be there.