verrous.md

author:
- Orestis Malaspinas, Steven Liatti
title: Introduction aux verrous
autoSectionLabels: false
autoEqnLabels: true
eqnPrefix:
  - "éq."
  - "éqs."
chapters: true
numberSections: false
chaptersDepth: 1
sectionsDepth: 3
lang: fr
documentclass: article
papersize: A4
cref: false
urlcolor: blue
toc: false
date: 2020-01-01
mathjax: on
include-before: <script src="css/prism.js"></script>
pthread_mutex_t verrou = PTHREAD_MUTEX_INITIALIZER;
int counter = 0;

// du code

pthread_mutex_lock(&verrou);
counter += 1;
pthread_mutex_unlock(&verrou);

// encore du code
void lock() {
    disable_interrupts();
}

void unlock() {
    enable_interrupts();
}
typedef struct {
    bool locked;
} lock_t;

void init(lock_t *mutex) {
    mutex->locked = false;
}

void lock(lock_t *mutex) {
    while (mutex->locked == true) {
        // do nothing;
    }
    mutex->locked = true;
}

void unlock(lock_t *mutex) {
    mutex->locked = false;
}
bool test_and_set(bool *old_ptr, bool new) {
    bool old = *old_ptr; // on stocke la valeur pointée par d'old_ptr
    *old_ptr = new;     // on assigne `new` à `*old_ptr`
    return old;         // on retourne l'ancienne valeur d'`*old_ptr`
}
typedef struct {
    bool locked;
} lock_t;

void init(lock_t *mutex) {
    mutex->locked = false;
}

void lock(lock_t *mutex) {
    while (test_and_set(&mutex->locked, true) == true) {
        // do nothing;
    }
}

void unlock(lock_t *mutex) {
    mutex->locked = false;
}
bool compare_and_exchange(bool *ptr, bool expected, bool new) {
    bool actual = *ptr;
    if (actual == expected) {
        *ptr = new;
    }
    return actual;
}
int fetch_and_add(int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}
typedef struct {
    int ticket;
    int turn;
} lock_t;

void lock_init(lock_t *lock) {
    lock->ticket = 0;
    lock->turn = 0;
}

void lock(lock_t *lock) {
    int myturn = fetch_and_add(&lock->ticket);
    while (lock->turn != myturn) {
        // do nothing
    }
}

void unlock(lock_t *lock) {
    lock->turn += 1;
}
void init(lock_t *mutex) {
    mutex->locked = false;
}

void lock(lock_t *mutex) {
    while (compare_and_exchange(&mutex->locked, false, true) == true) {
        yield(); // on passe le CPU
    }
}

void unlock(lock_t *mutex) {
    mutex->locked = false;
}
typedef {
    bool locked;
    bool guard;
    queue_t *q; // une file
} lock_t;

void init(lock_t *mutex) {
    mutex->locked = false;
    mutex->guard = false;
    queue_init(mutex->q);
}

void lock(lock_t *mutex) {
    while (test_and_set(&lock->gard, true) == true) {
        // la valeur de guard est acquise en
        // tournant dans la boucle while
    }
    if (mutex->locked == false) {
        mutex->locked = true; // le verrou est maintenant acquis
        mutex->guard = false; // la garde est maintenant fausse
    } else {
        queue_add(mutex->q, get_id()); // on met l'id du thread dans la queue
        m->guard = false;
        park(); // on met le thread en sommeil
    }
}

void unlock(lock_t *mutex) {
    while (test_and_set(&lock->gard, true) == true) {
        // la valeur de guard est acquise en
        // tournant dans la boucle while
    }
    if (queue_empty(mutex->q)) {
        mutex->locked = false; // le verrou est libéré si aucun thread
                               // est en attente
    } else {
        unpark(queue_remove(mutex->q)); // si un thread est en attente
                                        // lui garder le thread
    }
    mutex->guard = false;
}
void mutex_lock (int *mutex) {
    int v;
    /* Bit 31 was clear, we got the mutex (the fastpath) */
    if (atomic_bit_test_set (mutex, 31) == 0)
        return;
    atomic_increment (mutex);
    while (1) {
        if (atomic_bit_test_set (mutex, 31) == 0) {
            atomic_decrement (mutex);
            return;
        }
        /* We have to waitFirst make sure the futex value
            we are monitoring is truly negative (locked). */
        v = *mutex;
        if (v >= 0)
            continue;
        futex_wait (mutex, v);
    }
}
void mutex_unlock (int *mutex) {
    /* Adding 0x80000000 to counter results in 0 if and
       only if there are not other interested threads */
    if (atomic_add_zero (mutex, 0x80000000))
        return;
    /* There are other threads waiting for this mutex,
       wake one of them up. */
    futex_wake (mutex);
}