Незапертая реализация очереди заканчивает тем, что имела цикл под напряжением

Мне записали незапертые очереди в C в форме связанного списка, который содержит запросы от нескольких потоков, отправленных на и обработанный в единственном потоке. После нескольких часов напряжения я заканчиваю тем, что имел прямой указатель последнего запроса, указывающий на себя, который создает бесконечный цикл и запирает поток обработки.

Выполнение приложения (и сбои) и на Linux и на Windows. Я отлаживаю в Windows, где мой COMPARE_EXCHANGE_PTR карты к InterlockedCompareExchangePointer.

Это - код, который продвигает запрос к заголовку списка и назван от нескольких потоков:

void push_request(struct request * volatile * root, struct request * request)
{
    assert(request);

    do {
        request->next = *root;
    } while(COMPARE_EXCHANGE_PTR(root, request, request->next) != request->next);
}

Это - код, который получает запрос от конца списка и только назван единственным потоком, который обрабатывает их:

struct request * pop_request(struct request * volatile * root)
{
    struct request * volatile * p;
    struct request * request;

    do {
        p = root;
        while(*p && (*p)->next) p = &(*p)->next; // <- loops here
        request = *p;
    } while(COMPARE_EXCHANGE_PTR(p, NULL, request) != request);

     assert(request->next == NULL);

     return request;
}

Обратите внимание, что я не использую указатель хвоста, потому что я хотел избежать сложности необходимости иметь дело с указателем хвоста в push_request. Однако я подозреваю, что проблема могла бы быть в способе, которым я нахожу конец списка.

Существует несколько мест, которые продвигают запрос в очередь, но они все обычно походят на это:

// device->requests is defined as struct request * volatile requests;
struct request * request = malloc(sizeof(struct request));
if(request) {
    // fill out request fields
    push_request(&device->requests, request);
    sem_post(device->request_sem);
}

Код, который обрабатывает запрос, делает больше, чем это, но в сущности делает это в цикле:

if(sem_wait_timeout(device->request_sem, timeout) == sem_success) {
    struct request * request = pop_request(&device->requests);
    // handle request
    free(request);
}

Я также просто добавил функцию, которая проверяет список на дубликаты прежде и после каждой операции, но я боюсь, что эта проверка изменит синхронизацию так, чтобы я никогда не встречался с точкой, где это перестало работать. (Я ожидаю его для повреждения, поскольку я пишу это.)

Когда я повреждаюсь, зависание программируют циклы потока обработчика в pop_request в отмеченном положении. У меня есть действительный список одного или нескольких запросов и последнего, на которое прямой указатель указывает на себя. Очереди запроса обычно коротки, я никогда не видел более затем 10 и только 1, и 3 эти два раза я мог смотреть на этот отказ в отладчике.

Я продумал это так, как я мог, и я пришел к выводу, что никогда не должен мочь закончить с циклом в своем списке, если я не продвигаю тот же запрос дважды. Я совершенно уверен, что этого никогда не происходит. Я также абсолютно уверен (хотя не полностью), что это не проблема ABA.

Я знаю, что мог бы вытолкать больше чем один запрос одновременно, но я полагаю, что это не важно здесь, и я никогда не видел, что он происходит. (Я зафиксирую это также),

Я хорошо подумал о том, как я могу повредить свою функцию, но я не вижу способ закончиться с циклом.

Таким образом, вопрос: кто-то может видеть путь, как это может повредиться? Кто-то может доказать, что это не может?

В конечном счете я решу это (возможно, при помощи указателя хвоста или некоторого другого решения - блокировка была бы проблемой, потому что потоки, что сообщение не должно быть заблокировано, у меня действительно есть блокировка RW под рукой, хотя), но я хотел бы удостовериться, что изменение списка на самом деле решает мою проблему (в противоположность, делает его просто менее вероятно из-за другой синхронизации).