Cómo implementar colas seguras de subprocesos

Question

He usado la biblioteca de subprocesos múltiples antes en Python, pero esta es la primera vez que intento enhebrar en C. Quiero crear grupos de trabajadores. A su vez, estos trabajadores suponen van moviendo hacia o desde el pop queue.Following código no es bastante todavía, pero es lo que he hecho hasta ahora:

#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); 
} 

me trataron código anterior, y siempre impresa cada nombre exactamente una vez. No omitió ningún nombre ni imprimió el mismo nombre dos veces. Por otro lado, no estoy seguro de cómo es seguro para esta implementación de cola. Entonces mi pregunta es: ¿Es esta una cola de hilos? ¿Si no, porque no? ¿Y cómo hacerlo seguro?

Answer 1

El código no es seguro para subprocesos.

Las funciones push y pop no son seguras para hilos. En el código, el push solo se ejecuta con un único hilo, por lo que no importa, pero los pop se están ejecutando por varios hilos.

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

Imagínese hilo A ejecuta hasta e incluyendo la línea 2. Hilo B ejecuta entonces hasta e incluyendo la línea 4. Hilo A reanuda la ejecución. Encuentra que q-> head ya ha sido libre() ed.

Ahora, esto hasta ahora discute problemas lógicos.

Sin embargo, hay problemas físicos a tener en cuenta.

Imagina que tenemos un mecanismo de bloqueo mediante el cual los hilos pueden sincronizar su comportamiento, de modo que solo un hilo a la vez pueda ejecutar el código en las líneas 1 a 4, p. un mutex, que es un objeto que solo un hilo puede 'contener' a la vez, y donde intentar obtener el mutex bloquea el hilo hasta que se libera el hilo de espera.

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 

todavía tendríamos un problema, porque las escrituras realizadas por cualquier núcleo de la CPU dada (no hilo) son visibles inmediatamente sólo para roscas en que el núcleo; no a hilos en otros núcleos.

No es suficiente meramente sincronizar la ejecución; al mismo tiempo, también debemos asegurarnos de que las escrituras realizadas por un núcleo se vuelvan visibles para otros núcleos.

(Un) afortunadamente, todos los métodos de sincronización modernos también realizan esta descarga de escritura (por ejemplo, cuando obtiene un mutex, también vacía todas las escrituras en la memoria). Digo, lamentablemente, porque usted no siempre necesita este comportamiento y es perjudicial para el rendimiento.

Answer 2

No es seguro para subprocesos, ya que varios subprocesos pueden modificar los punteros en la lista vinculada al mismo tiempo, lo que podría dañarlo.

Aquí tienes una respuesta para una pregunta muy similar: Multiple-writer thread-safe queue in C

Allí se puede ver cómo hacer la cola de subprocesos.