Передача сообщений между потоками. Классические блокирующие алгоритмы

пожалуйста, вот псевдокод (я игнорирую для наглядности инициализацию и случаи пустой очереди, кроме того он страдает известной ABA проблемой):

struct node { node* next; };

struct queue
{
    node *head, *tail;

// это пример wait-free алгоритма, операция завершается 
//    за известное заранее число инструкций
    void put(node* n) {
        n->next=0;
        atomic_swap(tail, n);
        if(n) n->next=tail;
    }

// это lock-free, но не wait-free алгоритм,
//   мы крутимся в цикле пока операция не пройдет успешно
    node* get() {
        for(;;) {
            node *n=head;
            if(atomic_compare_and_swap(head, n, n->next))
                return n;
        }
    }
};

В общем случае используются атомарные операции, конкретно atomic_swap(a,b) — атомарно обменивает местами значения аргументов, и atomic_compare_and_swap(target, compare, new_value) — атомарно проверяет что target == compare и, если да, присваивает target=new_value, возвращает bool = успех операции.

Я извиняюсь, не понял сразу вопроса.
Не-lock-free алгоритм по определению использует блокирующие операции, но не входит в состояние deadlock, не путайте lock и deadlock.

Если код разросся до такого состояния, что существует куча логики с использованием блокировок в непонятных ситуациях, тогда lock-free алгоритмы точно не помогут такому коду, т.к. эти алгоритмы в разы сложнее алгоритмов с блокировками.
Я бы рекомендовал придерживаться нескольких правил, чтобы избежать взаимных блокировок:
1) мьютекс должен блокировать доступ к данным, а не код (если это возможно)
2) никогда не вызывайте внешний код из под блокировки (коллбеки и т.п.)
3) в идеале lock/unlock должны происходить в одной функции (RAII)