Parallélisme · Programmation en C

Version sans JavaScript, en lecture seule : les ateliers, les quiz et l’exécution du code n’y sont pas. Version complète · Catalogue · Se connecter

Parallélisme

Entrelacements et mises à jour perdues, trouver et corriger un interblocage, déboguer une file bornée, passer des arguments aux fils d'exécution, un rendez-vous avec des sémaphores, et le coût d'un verrou. Chapitre 7.

Les programmes se compilent avec gcc -std=c11 -Wall -Wextra -Werror -D_POSIX_C_SOURCE=200809L -pthread.

Exercice · Un virement qui bloque

Chaque compte bancaire a son verrou. Un virement verrouille les deux comptes concernés, puis déplace l'argent :

#include <pthread.h>
#include <stdio.h>

struct compte {
    pthread_mutex_t verrou;
    int numero;
    long solde;
};

static struct compte a = { PTHREAD_MUTEX_INITIALIZER, 1, 1000 };
static struct compte b = { PTHREAD_MUTEX_INITIALIZER, 2, 1000 };

static void virer(struct compte *de, struct compte *vers, long montant)
{
    pthread_mutex_lock(&de->verrou);
    pthread_mutex_lock(&vers->verrou);
    de->solde -= montant;
    vers->solde += montant;
    pthread_mutex_unlock(&vers->verrou);
    pthread_mutex_unlock(&de->verrou);
}

static void *de_a_vers_b(void *arg)
{
    (void)arg;
    for (int i = 0; i < 100000; i++)
        virer(&a, &b, 1);
    return NULL;
}

static void *de_b_vers_a(void *arg)
{
    (void)arg;
    for (int i = 0; i < 100000; i++)
        virer(&b, &a, 1);
    return NULL;
}

int main(void)
{
    pthread_t t1, t2;
    pthread_create(&t1, NULL, de_a_vers_b, NULL);
    pthread_create(&t2, NULL, de_b_vers_a, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("a = %ld, b = %ld\n", a.solde, b.solde);
    return 0;
}

Le programme ne se termine pas (essayez-le avec timeout 5 ./virement). Expliquer pourquoi, avec un entrelacement précis.
Pourquoi faut-il verrouiller les deux comptes ? Que pourrait-on observer en ne verrouillant que de ?
Corriger virer, sans ajouter de verrou global. Le champ numero est là pour ça.

Exercice · Une file bornée qui déraille

Voici une version fautive de la file bornée du chapitre, utilisée par un producteur et deux consommateurs :

static void deposer(int x)
{
    pthread_mutex_lock(&verrou);
    if (nb == CAPACITE)
        pthread_cond_wait(&non_pleine, &verrou);
    file[(tete + nb) % CAPACITE] = x;
    nb++;
    pthread_mutex_unlock(&verrou);
}

static int retirer(void)
{
    pthread_mutex_lock(&verrou);
    if (nb == 0)
        pthread_cond_wait(&non_vide, &verrou);
    int x = file[tete];
    tete = (tete + 1) % CAPACITE;
    nb--;
    pthread_cond_signal(&non_pleine);
    pthread_mutex_unlock(&verrou);
    return x;
}

Il manque une ligne dans deposer. Laquelle, et que se passe-t-il sans elle ?
Même avec cette ligne, les if posent problème. Décrire une exécution où un consommateur retire d'une file vide.
Et la marque de fin -1 du chapitre : suffit-elle avec deux consommateurs ?

Exercice · Le prix d'un verrou

On somme un tableau de dix millions d'entiers avec quatre fils, chacun sur un quart du tableau. Première version : chaque fil ajoute chaque case à un total global, protégé par un verrou.

static void *sommer(void *arg)
{
    int k = *(int *)arg;
    for (int i = k * (TAILLE / N); i < (k + 1) * (TAILLE / N); i++) {
        pthread_mutex_lock(&verrou);
        total += tab[i];
        pthread_mutex_unlock(&verrou);
    }
    return NULL;
}

Le résultat est-il juste ? Pourquoi ce programme est-il plus lent que la même somme faite par un seul fil, sans verrou ?
Réécrire sommer pour ne prendre le verrou qu'une fois par fil.