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

#include <pthread.h>
#include <stdio.h>
 
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
 
char buffer[1000];
 
void *writer(void *arg) {
  while (1)
    for (char letter = 'a'; letter <= 'z'; ++letter) {
      pthread_mutex_lock(&mutex);
      for (int i = 0; i < 999; ++i)
        buffer[i] = letter;
      pthread_mutex_unlock(&mutex);
    }
}
 
int main() {
  pthread_t thread;
  pthread_create(&thread, NULL, writer, NULL);
  pthread_detach(thread);
 
  while (getchar() != EOF) {
    pthread_mutex_lock(&mutex);
    printf("%s\n", buffer);
    pthread_mutex_unlock(&mutex);
  }
 
  return 0;
}

Exercise 6

...
 
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 7

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 8

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