Jan Kończak

Exercise 1

#include <pthread.h>
#include <stdio.h>
 
void *thread_routine(void *arg) {
  puts("Hello world");
  return NULL;
}
 
int main() {
  pthread_t myThread;
  if (-1 == pthread_create(&myThread, NULL, thread_routine, NULL)) {
    perror("Creating a thread failed");
    return 1;
  }
  pthread_join(myThread, NULL);
  return 0;
}

Exercise 2

Main thread exits before the newly spawned thread, and by default when the main thread exits, all other threads are terminated. Thus, the newly spawned thread is terminated before it prints the text.

Exercise 3

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
 
void *thread_routine(void *arg) {
  int i = *(int *)arg;
  free(arg);
  printf("Hello %d\n", i);
  return NULL;
}
 
int main() {
  pthread_t myThread[10];
  for (int i = 0; i < 10; ++i) {
    int *arg = malloc(sizeof(int));
    *arg = i;
    if (-1 == pthread_create(myThread + i, NULL, thread_routine, arg)) {
      perror("Creating a thread failed");
      return 1;
    }
  }
  for (int i = 0; i < 10; ++i)
    pthread_join(myThread[i], NULL);
  return 0;
}

Exercise 4

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
 
long global = 0;
 
void *thread_routine(void *arg) {
  int i = *(int *)arg;
  free(arg);
  long *k = malloc(sizeof(long));
  *k = global;                       // Reading and updating global is separated
  printf("Hello %d: %ld\n", i, *k);  // on purpose with a printf to increase
  global = global + 1;               // chances of concurrent access to it
  return k;
}
 
int main() {
  pthread_t myThread[10];
  for (int i = 0; i < 10; ++i) {
    int *arg = malloc(sizeof(int));
    *arg = i;
    if (-1 == pthread_create(myThread + i, NULL, thread_routine, arg)) {
      perror("Creating a thread failed");
      return 1;
    }
  }
  long *result[10];
  for (int i = 0; i < 10; ++i)
    pthread_join(myThread[i], (void **)result + i);
  for (int i = 0; i < 10; ++i) {
    printf("Thread %d: %ld\n", i, *result[i]);
    free(result[i]);
  }
  return 0;
}

Exercise 5

The examples show that accessing data with no synchronisation may lead to inconsistent results.
In the first code example one thread updates a text (character array) to a new version, whereas the second thread attempts to read the text. However, the thread reading the text sees some characters in the text being part of one version and some other characters that being from another version.
While the first code example shows that distinct data items can be out of sync, in the second code example the same 64-bit wide integer is used by multiple threads. Each of the 16 threads increments the integer one thousand times, but the result happens to be less than 16 thousands. This shows that even accesses to a single main memory location must be handled with care in concurrent programs.
In general, the examples motivate need for mutexes.

Exercise 6

#include <pthread.h>
#include <stdio.h>
#include <string.h>
 
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
unsigned long long version;
char text[1020];
 
void *updater(void *arg) {
  while (1)
    for (char letter = 'a'; letter <= 'z'; ++letter) {
      pthread_mutex_lock(&mutex);
      version++;
      for (int i = 0; i < 1020 - 1; ++i)
        text[i] = letter;
      pthread_mutex_unlock(&mutex);
    }
}
 
int main() {
  pthread_t tid;
  pthread_create(&tid, NULL, updater, NULL);
  while (getchar() != EOF) {
    pthread_mutex_lock(&mutex);
    // the data is copied locally to make the critical section short
    // and to avoid an I/O operation (printf) in the critical section
    unsigned long long version_copy;
    char text_copy[1020];
    version_copy = version;
    memcpy(text_copy, text, 1020);
    pthread_mutex_unlock(&mutex);
    printf("version: %llu\n   text: %s\n", version_copy, text_copy);
  }
  return 0;
}

#include <pthread.h>
#include <stdio.h>
 
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
unsigned long long counter;
 
void *incrementer(void *arg) {
  for (int i = 0; i < 1000; ++i) {
    pthread_mutex_lock(&mutex);
    counter++;
    pthread_mutex_unlock(&mutex);
  }
  return NULL;
}
 
int main() {
  pthread_t tid[16];
  for (int i = 0; i < 16; ++i)
    pthread_create(tid + i, NULL, incrementer, NULL);
  for (int i = 0; i < 16; ++i)
    pthread_join(tid[i], NULL);
  printf("%llu\n", counter);
  return 0;
}

Notice that the second example can also be amended more efficiently by using atomic operations:

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
 
_Atomic unsigned long long counter;
 
void *incrementer(void *arg) {
  for (int i = 0; i < 1000; ++i)
    atomic_fetch_add(&counter, 1);
  return NULL;
}
 
int main() {
  pthread_t tid[16];
  for (int i = 0; i < 16; ++i)
    pthread_create(tid + i, NULL, incrementer, NULL);
  for (int i = 0; i < 16; ++i)
    pthread_join(tid[i], NULL);
  printf("%llu\n", counter);
  return 0;
}

Exercise 7

...
 
struct list {
  struct node {
    struct node *next, *previous;
    element_t e;
  } *head, *tail;
  pthread_mutex_t coarseLock;
};
 
void list_init(struct list *l) {
  l->head = l->tail = NULL;
  pthread_mutex_init(&l->coarseLock, NULL);
}
 
struct node *list_add_back(struct list *l, element_t e) {
  struct node *newNode = malloc(sizeof(struct node));
  newNode->next = 0;
  newNode->e = e;
  pthread_mutex_lock(&l->coarseLock);
  if (l->tail == NULL) {
    newNode->previous = NULL;
    l->head = l->tail = newNode;
  } else {
    newNode->previous = l->tail;
    l->tail->next = newNode;
    l->tail = newNode;
  }
  pthread_mutex_unlock(&l->coarseLock);
  return newNode;
}
 
void list_delete_node(struct list *l, struct node *n) {
  if (n->previous == NULL)
    l->head = n->next;
  else
    n->previous->next = n->next;
  if (n->next == NULL)
    l->tail = n->previous;
  else
    n->next->previous = n->previous;
  free(n);
}
 
void list_delete_value(struct list *l, element_t e) {
  pthread_mutex_lock(&l->coarseLock);
  struct node *n = l->head, *next;
  while (n != NULL) {
    next = n->next;
    if (n->e == e)
      list_delete_node(l, n);
    n = next;
  }
  pthread_mutex_unlock(&l->coarseLock);
}
 
void list_print(struct list *l, int reverse) {
  pthread_mutex_lock(&l->coarseLock);
  struct node *n = reverse ? l->tail : l->head;
  while (n != NULL) {
    printf("%d\n", n->e);
    n = reverse ? n->previous : n->next;
  }
  pthread_mutex_unlock(&l->coarseLock);
}
 
...

Exercise 8

Notice that beheader must lock the mutex so that no other thread deletes the head between l->head != NULL and list_delete_node(l, l->head).

...
 
void *beheader(void *arg) {
  struct list *l = (struct list *)arg;
  srand(time(0) + 4);
  while (1) {
    pthread_mutex_lock(&l->coarseLock);
    if (l->head != NULL)
      list_delete_node(l, l->head);
    pthread_mutex_unlock(&l->coarseLock);
    usleep(50);
  }
}
 
int main() {
  struct list l;
  list_init(&l);
 
  pthread_t a, r, b;
  pthread_create(&a, NULL, adder, &l);
  pthread_create(&r, NULL, remover, &l);
  pthread_create(&b, NULL, beheader, &l);
  pthread_detach(a);
  pthread_detach(r);
  pthread_detach(b);
 
  while (getchar() != EOF)
    list_print(&l, 0);
  return 0;
}

Exercise 9

Critical sections in this particular example are the lines between pthread_mutex_lock(s) and pthread_mutex_unlock(s)

Exercise 10

For instance, an attempt to exchange item 0 with item 1 in thread #2 concurrently with an attempt to exchange item 1 with item 0 in thread #3 can lead to a situation when thread #2 successfully locks mutex on item 0 and thread #3 successfully locks mutex on item 1. Then, neither thread can proceed, for the other of the two threads holds the required mutex.

Exercise 11

A common solution to prevent deadlocks is to always lock mutexes in predefined order. For instance, the lines locking the mutexes upon exchanging items could look like this:

      pthread_mutex_lock(&item[argOne < argTwo ? argOne : argTwo].mtx);
      pthread_mutex_lock(&item[argOne < argTwo ? argTwo : argOne].mtx);

Exercise 12

An example interleaving that looses an element: when two worker threads execute add_element and both execute head = tail = e; concurrently.

A mutex that amends the program:

...
 
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
 
void add_element(int v) {
  pthread_mutex_lock(&mutex);
  struct element *e = malloc(sizeof(struct element));
  e->next = NULL;
  e->value = v;
  if (tail == NULL)
    head = tail = e;
  else
    tail = tail->next = e;
  pthread_mutex_unlock(&mutex);
}
 
...
 
  while (computed_count < 10) {
    int value;
    while (1) {
      pthread_mutex_lock(&mutex);
      if (head != NULL) {
        value = take_element();
        break;
      }
      pthread_mutex_unlock(&mutex);
    }
    pthread_mutex_unlock(&mutex);
    printf("%02d: %d\n", ++computed_count, value);
  }
 
...

The line that wastes CPU is the while (head == NULL) (and respectively the while (1) loop in the code above).

Condition variable that amends the program:

...
 
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t condvar = PTHREAD_COND_INITIALIZER;
 
void add_element(int v) {
  pthread_mutex_lock(&mutex);
  struct element *e = malloc(sizeof(struct element));
  e->next = NULL;
  e->value = v;
  if (tail == NULL)
    head = tail = e;
  else
    tail = tail->next = e;
  pthread_mutex_unlock(&mutex);
  pthread_cond_signal(&condvar);
}
 
...
 
  while (computed_count < 10) {
    int value;
    pthread_mutex_lock(&mutex);
    while (head == NULL)
      pthread_cond_wait(&condvar, &mutex);
    value = take_element();
    pthread_mutex_unlock(&mutex);
    printf("%02d: %d\n", ++computed_count, value);
  }
 
...

Exercise 13

#include <pthread.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
 
#define N 4
 
typedef int task_specification_t;
#define EXECUTE_TASK(arg) sleep(arg)
 
struct list {
  task_specification_t task;
  struct list *next;
} *head;
pthread_mutex_t list_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t list_cv = PTHREAD_COND_INITIALIZER;
 
void *worker(void *arg) {
  while (1) {
    pthread_mutex_lock(&list_mutex);
    while (head == NULL)
      pthread_cond_wait(&list_cv, &list_mutex);
    struct list *e = head;
    head = e->next;
    if (head != NULL)
      pthread_cond_signal(&list_cv);
    pthread_mutex_unlock(&list_mutex);
 
    printf("Worker %ld executing task %d\n", (intptr_t)arg, e->task);
    EXECUTE_TASK(e->task);
    printf("Worker %ld finished  task %d\n", (intptr_t)arg, e->task);
    free(e);
  }
}
 
int main() {
  for (intptr_t i = 0; i < N; ++i) {
    pthread_t tid;
    pthread_create(&tid, NULL, worker, (void *)i);
    pthread_detach(tid);
  }
 
  int td;
  while (scanf("%d", &td) != EOF) {
    printf("Dispatching task %d\n", td);
    struct list *e = malloc(sizeof(struct list));
    *e = (struct list){.task = td, .next = NULL};
 
    pthread_mutex_lock(&list_mutex);
    if (head == NULL) {
      head = e;
      pthread_cond_signal(&list_cv);
    } else {
      struct list *it = head;
      while (it->next != NULL)
        it = it->next;
      it->next = e;
    }
    pthread_mutex_unlock(&list_mutex);
  }
}