Вопрос по pthreads, posix, multithreading, queue, c – Как реализовать потокобезопасные очереди

8

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

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define NUMTHREADS 20 /* number of threads to create */

typedef struct node node;
typedef struct queue queue;

struct node {
    char *name;
    node *next;
};

struct queue {
    node *head;
    node *tail;
};

/* pop: remove and return first name from a queue */
char *pop(queue *q)
{
    if (q->head == NULL)
        return NULL;
    char *name = q->head->name;
    node *tmp = q->head;
    q->head = q->head->next;
    free(tmp);
    return name;
}

/* push: add name to the end of the queue */
int push(queue *q, char *name)
{
    node *new = malloc(sizeof(node));
    if (new == NULL)
        return -1;
    new->name = name;
    new->next = NULL;
    if (q->tail != NULL)
        q->tail->next = new;

    q->tail = new;
    if (q->head == NULL) /* first value */
        q->head = new;
    return 0;
}

/* printname: get a name from the queue, and print it. */
void *printname(void *sharedQ)
{
    queue *q = (queue *) sharedQ;
    char *name = pop(q);
    if (name == NULL)
        pthread_exit(NULL);
    printf("%s\n",name);
    pthread_exit(NULL);
}

int main()
{
    size_t i;
    int rc;
    pthread_t threads[NUMTHREADS];
    char *names[] = {
        "yasar",
        "arabaci",
        "osman",
        "ahmet",
        "mehmet",
        "zeliha"
    };

    queue *q = malloc(sizeof(queue));
    q->head = NULL;
    q->tail = NULL;

    /* number of elements in the array */
    size_t numelems = sizeof(names) / sizeof(char *);

    for (i = 0; i < numelems; i++) /* push each name */
        push(q, names[i]);

    for (i = 0; i < NUMTHREADS; i++) { /* fire up threads */
        rc = pthread_create(&threads[i], NULL, printname,
                (void *)q);
        if (rc) {
            printf("Error, return code from pthread is %d\n", rc);
            exit(-1);
        }
    }

    pthread_exit(NULL);
}

Я пробовал приведенный выше код, и он всегда печатал каждое имя ровно один раз. Он не пропустил ни одного имени или напечатал одно и то же имя дважды. С другой стороны, я не уверен, насколько потокобезопасна эта реализация очереди. Итак, мой вопрос: это потокобезопасная очередь? Если нет, то почему? И как сделать это потокобезопасным?

Структуры не нуждаются в typedefs; у них уже есть тип. user82238

Ваш Ответ

2   ответа
7

Функции push и pop не являются поточно-ориентированными. В коде push выполняется только одним потоком, так что это не имеет значения, но pops выполняются несколькими потоками.

1. char *name = q->head->name;
2. node *tmp = q->head;
3. q->head = q->head->next;
4. free(tmp);

Представьте себе, что поток A выполняется до строки 2 включительно, затем поток B выполняется до строки 4 включительно. Поток A возобновляет выполнение. Он находит, что q-> head уже свободна () ed.

Теперь это пока обсуждает логические вопросы.

Тем не менее, есть физические проблемы для рассмотрения.

Представьте, что у нас есть механизм блокировки, благодаря которому потоки могут синхронизировать свое поведение, так что только один поток за раз может выполнять код в строках с 1 по 4, например, мьютекс, который является объектом, который может удерживать только один поток; в то время, когда попытка получить мьютекс блокирует поток, пока удерживающий поток не освободится.

0. get mutex
1. char *name = q->head->name;
2. node *tmp = q->head;
3. q->head = q->head->next;
4. free(tmp);
5. release mutex

У нас все еще была бы проблема в том, что записи, выполняемые любым конкретным ядром ЦП (не потоком), видны сразу только потокам в этом ядре; не на темы на других ядрах.

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

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

3

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

Здесь у вас есть ответ на очень похожий вопрос: Потокобезопасная очередь с несколькими записями в C

Там вы можете увидеть, как сделать очередь потокобезопасной.

Похожие вопросы