Version without JavaScript, read-only: workshops, quizzes and running code are not available here. Full version · Catalogue · Sign in
Exercise sheet 7
Parallelism Interleavings and lost updates, finding and fixing a deadlock, debugging a bounded queue, passing arguments to threads, a rendezvous with semaphores, and the cost of a lock. Chapter 7.
Programs are compiled with gcc -std=c11 -Wall -Wextra -Werror -D_POSIX_C_SOURCE=200809L -pthread.
Exercise · Which values?
A global variable x is 0. Two threads each execute x = x + 1; once, without any synchronisation.
Break x = x + 1 down into elementary instructions. What are the possible values of x once both threads have finished? Give an interleaving for each. Same question if each thread executes x = x + 1; ten times . What is the largest possible value? The smallest? Hint: the smallest is not 10. Exercise · A transfer that hangs
Each bank account has its own lock. A transfer locks both accounts involved, then moves the money:
#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 ;
}The program does not terminate (try it with timeout 5 ./virement). Explain why, with a precise interleaving. Why must both accounts be locked? What could we observe if we locked only de? Fix virer, without adding a global lock. The numero field is there for that. Exercise · A bounded queue that goes off the rails
Here is a faulty version of the chapter's bounded queue, used by one producer and two consumers:
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;
}A line is missing in deposer. Which one, and what happens without it? Even with that line, the ifs are a problem. Describe an execution in which a consumer takes from an empty queue. And the chapter's end marker -1: is it enough with two consumers? Exercise · Passing a number to each thread
The chapter's boucle.c program passes &i to each thread, and each thread prints a wrong number.
Fix it by passing each thread the address of a cell of an array. Fix it another way, by allocating one integer per thread with malloc. Who must free it, and when? We would like each thread to return the square of its number, and main to print the sum of the results. How do you retrieve the value returned by a thread's function? Exercise · A rendezvous
Two threads A and B. A prints A1 then A2; B prints B1 then B2. We want A2 and B2 to be printed only once both have printed their first line: A1 before B2, and B1 before A2.
Do it with two semaphores. What initial value should they have? If, in both threads, we do the sem_wait before the sem_post, what happens? Which tool from the chapter does exactly this for N threads? Exercise · The price of a lock
We sum an array of ten million integers with four threads, each on a quarter of the array. First version: each thread adds every cell to a global total, protected by a lock.
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 ;
}Is the result correct? Why is this program slower than the same sum computed by a single thread, without a lock? Rewrite sommer so that it takes the lock only once per thread.