Реализация очереди без блокировки заканчивается циклом под нагрузкой - PullRequest
Новая
       30

Реализация очереди без блокировки заканчивается циклом под нагрузкой

5 голосов
/ 26 апреля 2010

У меня есть очереди без блокировки, написанные на 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 под рукой), но я бы хотел убедитесь, что изменение списка действительно решает мою проблему (в отличие от того, что делает его просто менее вероятным из-за разного времени).

1 Ответ

8 голосов
/ 27 апреля 2010

Это тонко, но у вас там есть состояние гонки.

Начните со списка с одним элементом, req1. Итак имеем: 

device->requests == req1;
req1->next == NULL;

Теперь мы нажимаем новый элемент req2 и одновременно пытаемся вытолкнуть очередь. Нажим для req2 начинается первым. Тело цикла while работает, поэтому теперь у нас есть: 

device->requests == req1;
req1->next == NULL;
req2->next == req1;

Затем запускается COMPARE_EXCHANGE_PTR, поэтому имеем: 

device->requests == req2;
req1->next == NULL;
req2->next == req1;

... и COMPARE_EXCHANGE_PTR() возвращает req1. Теперь, в этот момент, за до сравнения в условии while , нажатие прерывается и запускается всплывающее окно.

Поп работает правильно до завершения, вылетает req1 - это означает, что у нас есть: 

device->requests == req2;
req2->next == NULL;

Пуш возобновляется. Теперь он получает request->next для сравнения - и новое значение req2->next, которое составляет NULL. Он сравнивает req1 с NULL, сравнение успешно, цикл while запускается снова, и теперь мы имеем: 

device->requests == req2;
req2->next == req2;

На этот раз тест не пройден, цикл while завершен, и у вас есть цикл.

Это должно исправить: 

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

    assert(request);

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