Differences

This shows you the differences between two versions of the page.

--- os_cp:threads [2023/05/17 09:19]
jkonczak [Caring for a thread]
+++ os_cp:threads [2024/04/18 11:42] (current)
jkonczak [Accessing the same data from multiple threads]
@@ Line 52: / Line 52: @@
 pointer to arbitrary data((To specify a pointer without specifying the type of
 underlying data one has to use ''void *''.)):
+<html><div style="margin-top:-1.4em;line-height:1.2em"></html>
 <code c>
 void * start_routine (void * argument){
@@ Line 58: / Line 59: @@
 }
 </code>
+<html></div></html>
 <small>In C such function is of type ''void *(*)(void *)'', and a variable called
 ''func'' of this type should be declared as ''void *(*func)(void *)''.</small>
@@ Line 77: / Line 79: @@
 argument is not NULL, thread attributes will be set before starting the thread.
-<html><div style="line-height:1em"></html>
+<html><div style="line-height:1.2em"></html>
 ++++An example of creating a thread and passing it some data|
 <code c>
@@ Line 138: / Line 140: @@
 The ''//value_ptr//'' can be NULL, and then the return value is discarded.
-<html><div style="line-height:1em"></html>
+<html><div style="line-height:1.2em"></html>
 ++++An example code that creates 3 threads and joins them, collecting their result.|
 <code c>
@@ Line 217: / Line 219: @@
 typically the thread that spawned it calls the detach.
-<html><div style="line-height:1em"></html>
+<html><div style="line-height:1.2em"></html>
 ++++An example code that creates a thread and detaches it.|
 <code c>
@@ Line 297: / Line 299: @@
 ~~Exercise.#~~
-Remove the code you wrote for the previous exercise the ''pthread_join'' and
+Remove from the code you wrote for the previous exercise the ''pthread_join''
-re-run the code. What has changed in the behaviour of the program?
+and re-run the code. What has changed in the behaviour of the program?
 ~~Exercise.#~~
@@ Line 311: / Line 313: @@
 the ordinal number, and return it from the thread entry routine.
 In the main thread, collect the returned numbers and display them.
+===== Accessing the same data from multiple threads =====
+The following examples show what might happen upon accessing the same data from
+multiple threads with no synchronisation.
+First, let's read/write "linearly" from/to an array from two threads:
+<html><div style="margin-top:-1.4em;line-height:1.2em"></html>
+<code c>
+#include <pthread.h>
+#include <stdio.h>
+#include <string.h>
+unsigned long long version;
+char text[1020];
+void *updater(void * arg) {
+  while (1)
+    for (char letter = 'a'; letter <= 'z'; ++letter) {
+      version++;
+      for (int i = 0; i < 1020 - 1; ++i)
+        text[i] = letter;
+      // memset(text, letter, 1020);
+    }
+}
+int main() {
+  pthread_t tid;
+  pthread_create(&tid, NULL, updater, NULL);
+  while (getchar() != EOF)
+    printf("version: %llu\n   text: %s\n", version, text);
+  return 0;
+}
+</code>
+<html></div></html>
+Next, let's read-modify-write the same variable from multiple threads:
+<html><div style="margin-top:-1.4em;line-height:1.2em"></html>
+<code c>
+#include <pthread.h>
+#include <stdio.h>
+unsigned long long counter;
+void *incrementer(void * arg) {
+  for (int i = 0; i < 1000; ++i)
+    counter++;
+  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;
+}
+</code>
+<html></div></html>
+<html><div style="margin-top:-1.4em; line-height: 1em"></html>
+<small>If the code above always returns the right answer, try to run it a million times: \\
+''for X in `seq 1000000`; do RES=$(%%./%%//progname//); test "$RES" -ne 16000 && echo -e "\n$RES" && break || echo -n '.'; done''
+</small>
+<html></div></html>
+~~Exercise.#~~
+Read, understand the code, compile and run the two above examples.
+What is wrong with the results? What problem do these examples show?
+===== POSIX mutexes and readers-writers locks =====
+==== Mutexes ====
+A [[https://en.wikipedia.org/wiki/Lock_(computer_science)|mutex]] is a synchronisation
+primitive that has two operations: //lock// that locks (acquires) the mutex and //unlock//
+that unlocks (releases) the mutex. A thread that invoked lock and did not yet invoke unlock
+//holds// the mutex. A mutex guarantees that at most one thread holds it at a time.
+The name mutex comes from //mutual exclusion//. Mutexes are sometimes called //locks//,
+however some APIs use the name //lock// for an object that locks a mutex upon creation and
+unlocks it upon destruction.
+To create a POSIX mutex, one has to create a variable of ''pthread_mutex_t'' type
+and initialize it, using either an initializer macro:
+\\
+<html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
+<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutex_init.html"></html>
+''pthread_mutex_t //mutex// = **PTHREAD_MUTEX_INITIALIZER**;''
+<html></a></html>
+\\
+to initialize a mutex with default semantics, or an initialisation function:
+\\
+<html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
+<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutex_init.html"></html>
+''int **pthread_mutex_init**(pthread_mutex_t *restrict //mutex//,'' \\
+''                       const pthread_mutexattr_t *restrict //attr//)''
+<html></a></html>
+When using the ''pthread_mutex_init'' function, one can select non-default semantics
+for a mutex.
+\\
+To do so, one has to declare a ''pthread_mutexattr_t'' variable and
+initialize it using:
+\\
+<html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
+<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutexattr_init.html"></html>
+''int **pthread_mutexattr_init**(pthread_mutexattr_t *//attr//)''
+<html></a></html>
+\\
+and finally set the attributes using corresponding functions:
+  * <html><a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutexattr_settype.html"></html> ''int pthread_mutexattr_set**type**(pthread_mutexattr_t *//attr//, int //type//)''<html></a></html> sets mutex type (see below),
+  * <small><html><a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutexattr_setpshared.html"></html>''int pthread_mutexattr_set**pshared**(pthread_mutexattr_t *//attr//, int //pshared//)''<html></a></html> allows sharing mutexes between processes (they need to reside in shared memory), </small>
+  * <small><html><a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutexattr_setrobust.html"></html>''int pthread_mutexattr_set**robust**(pthread_mutexattr_t *//attr//, int //robust//)''<html></a></html> when a thread holding a mutex terminated, a robust mutex will return appropriate error instead of waiting,</small>
+  * <small>''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutexattr_setprotocol.html|pthread_mutexattr_setprotocol]]'' and ''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutexattr_setprioceiling.html|setprioceiling]]'' deal with priorities.</small>
+The mutex type impacts what happens when a mutex that is already locked is
+locked again by the same thread:
+  * ''PTHREAD_MUTEX_NORMAL'' - the thread will deadlock (with itself),
+  * ''PTHREAD_MUTEX_ERRORCHECK'' - locking the mutex will fail (i.e., return ''-1'' and set ''errno'' accordingly),
+  * ''PTHREAD_MUTEX_RECURSIVE'' - the mutex counts how many times it was locked, and will unlock after this many unlocks,
+  * ''PTHREAD_MUTEX_DEFAULT'' - it is undefined what will happen.
+Some mutex types also guarantee failing((returning ''-1'' from ''pthread_mutex_unlock'' and setting ''errno'' accordingly.)) to unlock a lock not owned by the current thread – all mutexes of ''PTHREAD_MUTEX_ERRORCHECK'' and ''PTHREAD_MUTEX_RECURSIVE'' do that, as well as any mutex set to be robust does that.
+An example of creating a recursive mutex is as follows:
+<html><div style="margin-top:-1.4em;line-height:1.2em"></html>
+<code c>
+pthread_mutexattr_t recursiveAttrs;
+pthread_mutexattr_init(&recursiveAttrs);
+pthread_mutexattr_settype(&recursiveAttrs, PTHREAD_MUTEX_RECURSIVE);
+pthread_mutex_t mutex;
+pthread_mutex_init(&mutex, &recursiveAttrs);
+</code>
+<html></div></html>
+To lock a mutex one can use either of:
+\\
+<html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
+<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutex_lock.html"></html>
+''int **pthread_mutex_lock**(pthread_mutex_t *//mutex//)'' \\
+''int pthread_mutex_trylock(pthread_mutex_t *//mutex//)''
+<html></a></html>
+\\
+<small><html><a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutex_timedlock.html"></html>
+''int pthread_mutex_timedlock(pthread_mutex_t *restrict //mutex//, const struct timespec *restrict //abstime//)''
+<html></a></html></small>
+\\
+If the ''//mutex//'' is unlocked, the functions lock the mutex. If ''//mutex//'' is
+currently locked, ''pthread_mutex_lock'' waits until the mutex becomes unlocked,
+''pthread_mutex_trylock'' immediately returns ''-1'' and sets ''errno'' to ''EBUSY'',
+<small>and ''pthread_mutex_timedlock'' waits at most //abstime// for the lock to become available</small>.
+\\
+<small>When a mutex is misused, locking it may return ''-1'' and set ''errno''
+accordingly.</small>
+To unlock a mutex, one has to use the function:
+\\
+<html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
+<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_mutex_lock.html"></html>
+''int **pthread_mutex_unlock**(pthread_mutex_t *//mutex//)''
+<html></a></html>
+\\
+It is important to remember that only the thread that locked the mutex can unlock it.
+~~Exercise.#~~
+Use a mutex to fix the programs from the two examples in the section
+[[#accessing_the_same_data_from_multiple_threads|accessing the same data from multiple threads]].
+<small>
+<html><div style="margin-bottom:-1.2em"></html>
+~~Exercise.#~~
+The program below accesses a linked list from multiple threads.
+Add mutexes to functions which names start with ''list_…'' so that the program
+no longer crashes.
+<html></div></html>
+++++ Source code for this exercise: |
+<html><div style="line-height:1.2em"></html>
+<code c linkedlist.c>
+#include <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+typedef int element_t;
+struct list {
+  struct node {
+    struct node *next, *previous;
+    element_t e;
+  } * head, *tail;
+};
+void list_init(struct list *l) { l->head = l->tail = 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;
+  if (l->tail == NULL) {
+    newNode->previous = NULL;
+    l->head = l->tail = newNode;
+  } else {
+    newNode->previous = l->tail;
+    l->tail->next = newNode;
+    l->tail = newNode;
+  }
+  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) {
+  struct node *n = l->head, *next;
+  while (n != NULL) {
+    next = n->next;
+    if (n->e == e)
+      list_delete_node(l, n);
+    n = next;
+  }
+}
+void list_print(struct list *l, int reverse) {
+  struct node *n = reverse ? l->tail : l->head;
+  while (n != NULL) {
+    printf("%d\n", n->e);
+    n = reverse ? n->previous : n->next;
+  }
+}
+void *adder(void *arg) {
+  struct list *l = (struct list *)arg;
+  srand(time(0));
+  while (1) {
+    list_add_back(l, rand() % 25);
+    usleep(10);
+  }
+}
+void *remover(void *arg) {
+  struct list *l = (struct list *)arg;
+  srand(time(0) + 2);
+  while (1) {
+    list_delete_value(l, rand() % 25);
+    usleep(5);
+  }
+}
+int main() {
+  struct list l;
+  list_init(&l);
+  pthread_t a, r;
+  pthread_create(&a, NULL, adder, &l);
+  pthread_create(&r, NULL, remover, &l);
+  pthread_detach(a);
+  pthread_detach(r);
+  while (getchar() != EOF)
+    list_print(&l, 0);
+  return 0;
+}
+</code>
+<html></div></html>
+++++
+~~Exercise.#~~
+Add to the program from the previous exercise a thread executing the following
+function, and amend the code so that it neither crashes nor deadlocks:
+<html><div style="line-height:1.2em"></html>
+<code c linkedlist.c>
+void *beheader(void *arg) {
+  struct list *l = (struct list *)arg;
+  srand(time(0) + 4);
+  while (1) {
+    if (l->head != NULL)
+      list_delete_node(l, l->head);
+    usleep(50);
+  }
+}
+</code>
+<html></div></html>
+</small>
+==== Readers-writers locks [extra] ====
+A [[https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock|readers-writers lock]]
+(//rwlock//) is a synchronisation primitive similar to a mutex, but it
+offers two modes of locking: shared (//readers//) and exclusive (//writers//).
+At a time, either any number of threads can lock the rwlock in the shared (read)
+mode, or at most one thread can lock the rwlock in the exclusive (write) mode.
+The POSIX read-write lock object API is similar to the mutex API.
+\\
+To create a rwlock one has to create a ''pthread_rwlock_t'' variable and initialize
+it with either ''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_init.html|PTHREAD_RWLOCK_INITIALIZER]]'' macro or ''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_init.html|pthread_rwlock_init]]'' function.
+\\
+A read-write lock can be locked with:
+  * ''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_rdlock.html|pthread_rwlock_rdlock]]'' and ''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_rdlock.html|pthread_rwlock_tryrdlock]]'' in shared (read) mode,
+  * ''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_wrlock.html|pthread_rwlock_wrlock]]'' and ''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_wrlock.html|pthread_rwlock_trywrlock]]'' in exclusive (write) mode.
+<small>''pthread_rwlock_timedrdlock'' / ''pthread_rwlock_timedwrlock'' variants are also available.</small>
+\\
+To unlock a rwlock (locked in any mode), ''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_unlock.html|pthread_rwlock_unlock]]'' is used.
+===== [extra] Concurrency, parallelism =====
+The aim of __[[https://en.wikipedia.org/wiki/Parallel_computing|parallel programming]]__
+is to take advantage of the fact that a computer can execute two or more sequences
+of instructions at the same time (literally).
+\\
+One needs at least two physical threads (for instance, two CPU cores) for this.
+__[[https://en.wikipedia.org/wiki/Resource_contention|Contention]]__ is the situation
+when two processes / threads want to use the same resource (say, the same variable)
+at the same time.
+__Concurrent programming__ deals with processes / threads that contend on some
+resources (and run either interleaved or in parallel).
+\\
+Concurrency also concerns computers that have one physical thread (a single CPU
+core) whenever they can switch context from one process / thread to another.
+When two processes / threads access the same data and at least one of the
+accesses modifies the data, then the __[[https://en.wikipedia.org/wiki/Race_condition#In_software|race condition]]__
+occurs – the result of the computation depends upon a chance.
+\\
+Race conditions often lead to incorrect state of the data and thus introduce
+bugs (that are usually hard to pinpoint).
+Regions of code that must be executed without being interleaved among each other
+are called __[[https://en.wikipedia.org/wiki/Critical_section|critical sections]]__.
+At most one process may be at a time inside inside a critical section.
+When a process P wants to enter a critical section, and another process Q is
+executing a critical section, then P must __wait__ (aka __block__) until Q exits
+the critical section.
+When a number of processes / threads are waiting on synchronisation primitives
+(say, blocked by ''pthread_mutex_lock''), and the only processes / threads that
+could wake the ones waiting (say, execute ''pthread_mutex_unlock'') are within
+the waiting ones, then a __[[https://en.wikipedia.org/wiki/Deadlock|deadlock]]__
+occurred.
+\\
+A deadlock usually means that the processing stops.
+<html><div style="margin-bottom:-1em"></html>
+It is also possible to run into a state when processes don't stop, but can't
+progress either. This is called a __livelock__. Imagine the following code:
+<html></div></html>
+<html><div style="line-height:1em"></html>
+<small>
+<code c>
+/* x, y and mtx are shared */
+/* the programmer believed that eventually x equals y, but now x==1, y==0 and only those two processes run: */
+/* Thread 1 */                │    /* Thread 2 */
+char loop = 1;                │    char loop = 1;
+while(loop) {                 │    while(loop) {
+  pthread_mutex_lock(&mtx);   │      pthread_mutex_lock(&mtx);
+  if (*x==0 && *y==0) {       │      if (*x==1 && *y==1) {
+    /* do business logic */   │        /* do business logic */
+    loop = 0;                 │        loop = 0;
+  }                           │      }
+  pthread_mutex_unlock(&mtx); │      pthread_mutex_unlock(&mtx);
+}                             │    }
+</code>
+</small>
+<html></div></html>
+__Fairness__ describes whether all processes / threads have equal chance to enter
+the critical section.
+Sometimes priorities are intentionally given to selected processes / threads.
+Incorrect implementation of priorities may lead to
+__[[https://en.wikipedia.org/wiki/Priority_inversion|priority inversion]]__.
+\\
+If the algorithm is completely unfair for some process / thread, it can
+__[[https://en.wikipedia.org/wiki/Starvation_(computer_science)|starve]]__ by
+never entering the critical section on contention.
+===== Critical sections, deadlocks =====
+~~Exercise.#~~ Which lines of code are the critical section in the code below?
+~~Exercise.#~~ Spot the deadlock scenario in the code below.
+~~Exercise.#~~ Fix the code so that it no longer is able to deadlock.
+<html><div style="line-height:1.2em"></html>
+<small>
+<code c another_bad_idea.c>
+#include <pthread.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+struct {
+  pthread_mutex_t mtx;
+  char text[256];
+} item[5];
+const char *arg0;
+void *threadFunc(intptr_t num) {
+  char name[1024], cmd[1024];
+  sprintf(name, "%s.pipe.%ld", arg0, num);
+  sprintf(cmd, "rm -f %s; mkfifo %s", name, name);
+  system(cmd);
+  FILE *myPipe = fopen(name, "r+");
+  while (1) {
+    char line[1024], nl;
+    fscanf(myPipe, "%1023[^\n]%c", line, &nl);
+    int argOne = atoi(line);
+    if (argOne >= 5 || argOne < 0)
+      continue;
+    char *argTwoTxt = strchr(line, ' ');
+    if (!argTwoTxt) {
+      pthread_mutex_lock(&item[argOne].mtx);
+      printf("T%ld reads %d as: %s\n", num, argOne, item[argOne].text);
+      pthread_mutex_unlock(&item[argOne].mtx);
+      continue;
+    }
+    argTwoTxt++;
+    char *e;
+    int argTwo = strtol(argTwoTxt, &e, 10);
+    if (!*e && argTwo < 5 && argTwo >= 0 && argOne != argTwo) {
+      pthread_mutex_lock(&item[argOne].mtx);
+      pthread_mutex_lock(&item[argTwo].mtx);
+      printf("T%ld copies %d to %d\n", num, argTwo, argOne);
+      memcpy(item[argOne].text, item[argTwo].text, sizeof(item[argOne].text));
+      pthread_mutex_unlock(&item[argTwo].mtx);
+      pthread_mutex_unlock(&item[argOne].mtx);
+    } else {
+      pthread_mutex_lock(&item[argOne].mtx);
+      printf("T%ld assigns to %d the value: %s\n", num, argOne, argTwoTxt);
+      memset(item[argOne].text, 0, sizeof(item[argOne].text));
+      strncpy(item[argOne].text, argTwoTxt, sizeof(item[argOne].text) - 1);
+      pthread_mutex_unlock(&item[argOne].mtx);
+    }
+  }
+}
+int main(int argc, char **argv) {
+  arg0 = argv[0];
+  printf("To use this program, write to one of the %s.pipe.<thread_id> the "
+         "following:\n"
+         "  <num>             prints <text> from item <num>\n"
+         "  <num> <text>      puts <text> to item <num>\n"
+         "  <num1> <num2>     copies to item <num1> the text from item <num2>\n"
+         "Valid pipe numbers are 0-4, valid item numbers are 0-4.",
+         arg0);
+  for (int i = 0; i < 5; ++i)
+    pthread_mutex_init(&item[i].mtx, NULL);
+  for (intptr_t i = 1; i < 5; ++i) {
+    pthread_t tid;
+    pthread_create(&tid, NULL, (void *(*)(void *))threadFunc, (void *)i);
+    pthread_detach(tid);
+  }
+  threadFunc(0);
+}
+</code>
+</small>
+<html></div></html>
 ===== Thread-specific data, thread local storage [extra] =====
@@ Line 348: / Line 832: @@
 Each key is initially associated with a ''NULL'' for each thread.
-<html><div style="line-height:1em"></html>
+<html><div style="line-height:1.2em"></html>
 ++++An example code that creates a key, stores and retrieves the value from two threads.|
 <code c>
@@ Line 398: / Line 882: @@
 POSIX), but there is no way to provide a custom destructor (unlike in POSIX).
+===== POSIX condition variables =====
+[[https://en.wikipedia.org/wiki/Monitor_(synchronization)|Condition variables]]
+are strictly related to mutexes. They allow a thread that holds a mutex to
+release the mutex and at the same time start //wait//ing for a wakeup signal from
+another thread. When the other thread //signal//s the condition variable, then
+either one or all threads waiting on that variable are waken and each of these
+threads enters the procedure of locking back the mutex.
+**Using condition variables is the most common way to communicate threads.**
+When one thread needs to execute some logic once a specific condition is fulfilled,
+it should:
+  - lock a mutex,
+  - check the condition,
+  - if the condition is false:
+    - wait on a condition variable,
+    - go back to step 2,
+  - do the logic,
+  - unlock the mutex.
+A thread that may change the state and thus affect the condition should:
+  - lock the mutex,
+  - do its logic,
+  - signal the condition variable,
+  - unlock the mutex((One can also signal the condition variable after unlocking the mutex.)).
+<small>
+The example conditions include:
+  * a boolean flag is set; the flag indicates that another thread finished a part of the computation and the results can used,
+  * a list of items is not empty; the list contains tasks to be done by this thread,
+  * a number crossed some threshold; the number is the size of items to potentially garbage collect.
+</small>
+To use a condition variable, one has to declare a ''pthread_cond_t'' variable,
+and then initialize it with:
+\\
+<html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
+<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_cond_init.html"></html>
+''pthread_cond_t //cond// = **PTHREAD_COND_INITIALIZER**;''
+<html></a></html>
+\\
+to use default semantic, <small> or with an initialisation function that allows
+choosing desired semantic:
+\\
+<html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
+<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_cond_init.html"></html>
+''int pthread_cond_init(pthread_cond_t *restrict //cond//, const pthread_condattr_t *restrict //attr//)''
+<html></a></html>
+</small>
+A thread holding mutex //mutex// can use the function:
+\\
+<html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
+<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_cond_wait.html"></html>
+''int **pthread_cond_wait**(pthread_cond_t *restrict //cond//, pthread_mutex_t *restrict //mutex//)''
+<html></a></html>
+\\
+to atomically release the //mutex// and start waiting on //cond//.
+Another thread can use one of the functions:
+\\
+<html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
+<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_cond_broadcast.html"></html>
+''int **pthread_cond_signal**(pthread_cond_t *restrict //cond//)''\\
+''int **pthread_cond_broadcast**(pthread_cond_t *restrict //cond//)''
+<html></a></html>
+\\
+to wake at least one (''pthread_cond_signal''), or all (''pthread_cond_broadcast'')
+threads waiting on the condition variable ''cond''.
+\\
+The thread that is signalling/broadcasting does not need to hold the mutex.
+~~Exercise.#~~
+The program below attempts to calculate 10 items (imagine that it tries to create
+ten class timetables) among four threads, and runs one thread that waits until
+the ten items are ready. __Right now, the program is incorrect.__
+\\       • The program is not thread-safe. Propose an interleaving that looses an element.
+\\       • Use mutex(es) to amend the program.
+\\       • The thread collecting items wastes CPU on busy waiting. Point the line that wastes CPU.
+\\       • Add condition variable(s) to amend the program.
+<html><div style="line-height:1.2em"></html>
+<code c linkedlist.c>
+#include <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+struct element {
+  int value;
+  struct element *next;
+} *head = NULL, *tail = NULL;
+void add_element(int v) {
+  struct element *e = malloc(sizeof(struct element));
+  e->next = NULL;
+  e->value = v;
+  if (tail == NULL)
+    head = tail = e;
+  else
+    tail = tail->next = e;
+}
+int take_element() {
+  int v = head->value;
+  struct element *e = head;
+  head = head->next;
+  if (head == NULL)
+    tail = NULL;
+  free(e);
+  return v;
+}
+#define DO_HEAVY_COMPUTATION (usleep(rand() % 10000000), rand() % 1000000)
+void *worker_thread(void *arg) {
+  srand(time(0) + (intptr_t)arg);
+  while (1) {
+    int v = DO_HEAVY_COMPUTATION;
+    pthread_testcancel();
+    add_element(v);
+  }
+}
+int main() {
+  pthread_t t[4];
+  for (int i = 0; i < 4; ++i)
+    pthread_create(t + i, NULL, worker_thread, NULL);
+  int computed_count = 0;
+  while (computed_count < 10) {
+    while (head == NULL);
+    int value = take_element();
+    printf("%02d: %d\n", ++computed_count, value);
+  }
+  for (int i = 0; i < 4; ++i)
+    pthread_cancel(t[i]);
+  for (int i = 0; i < 4; ++i)
+    pthread_join(t[i], NULL);
+  return 0;
+}
+</code>
+<html></div></html>
+~~Exercise.#~~
+Write a program that starts N worker threads that wait for tasks to do.
+In the main thread read commands from standard input. Once a command is read,
+one of the worker threads should execute the command and once the command is
+executed, the worker thread should print the result to the standard output.
+\\
+For simplicity let the command be an integer, and let the execution procedure be
+sleeping for this many seconds.
+\\
+<small>
+This idea of creating worker threads and passing them tasks is very popular
+bears the name [[https://en.wikipedia.org/wiki/Thread_pool|thread pool]] in
+software engineering.
+</small>
+===== C mutexes and condition variables [extra] =====
+C11 language standard brought mutexes and condition variables to C.
+\\
+The API for these synchronisation constructs looks like a simplified POSIX API:
+<html><div style="line-height:1.2em"></html>
+<code c>
+#include <stdio.h>
+#include <threads.h>
+mtx_t mutex;
+cnd_t condition_variable;
+char shared_data = 0;
+int func(void *arg);
+int main() {
+  mtx_init(&mutex, mtx_plain | mtx_recursive);
+  cnd_init(&condition_variable);
+  thrd_t t;
+  thrd_create(&t, func, NULL);
+  char c = getchar();
+  mtx_lock(&mutex);
+  shared_data = c;
+  mtx_unlock(&mutex);
+  cnd_signal(&condition_variable);
+  thrd_join(t, NULL);
+  return 0;
+}
+int func(void *arg) {
+  char c;
+  mtx_lock(&mutex);
+  while (shared_data == 0)
+    cnd_wait(&condition_variable, &mutex);
+  c = shared_data;
+  mtx_unlock(&mutex);
+  printf("%c\n", c ^ 0x20);
+  return thrd_success;
+}
+</code>
+<html></div></html>
+For a full reference, consult for instance: [[https://en.cppreference.com/w/c/thread#Mutual_exclusion]]
+===== Atomic variables [extra] =====
+Current [[https://en.wikipedia.org/wiki/Instruction_set_architecture|instruction set architectures]]
+offer atomic instructions. An atomic instruction observes all other instructions
+either fully executed or not executed at all and itself is observed by other
+instructions either fully executed or not executed at all.
+Atomic instructions themselves might not impose any order among instructions.
+Some examples of atomic instructions are:
+  * [[https://en.wikipedia.org/wiki/Test-and-set|test-and-set]],
+  * [[https://en.wikipedia.org/wiki/Compare-and-swap|compare-and-swap]],
+  * [[https://en.wikipedia.org/wiki/Fetch-and-add|fetch-and-add]].
+Such instructions are usually the base building blocks of synchronisation
+primitives (e.g., mutexes), but can be useful themselves to the end users.
+For instance, imagine that you need to assign unique identifiers from multiple
+threads – then a single atomic fetch-and-add (or even atomic increment) suffices.
+C11 standardized invoking the atomic instructions. To use them, the variable
+has to be declared with ''[[https://en.cppreference.com/w/c/language/atomic|_Atomic]]''
+type specifier or ''[[https://en.cppreference.com/w/c/thread#Convenience_type_aliases|atomic_…]]'' convenience type alias (e.g. ''_Atomic int i;'' or the equivalent ''atomic_int i;'').
+\\
+On architectures that do not support one of the atomic operations used on a
+variable, a lock is automatically acquired for the duration of each operation on
+that variable.
+One can learn whether the operation is lock-free by checking the value of
+[[https://en.cppreference.com/w/c/atomic/ATOMIC_LOCK_FREE_consts|appropriate macros]].
+\\
+The list of available atomic operations includes: load, store, swap, test-and-set,
+compare-and-swap, fetch-and-add.
+\\
+For details, consult e.g., [[https://en.cppreference.com/w/c/thread#Atomic_operations]].
+Each atomic instruction in C can be also combined with a memory ordering
+instruction. A memory ordering instruction can be issued explicitly using
+''[[https://en.cppreference.com/w/c/atomic/atomic_thread_fence|atomic_thread_fence]]''.
+The memory model of C, as well as the memory ordering enum values, are described
+among others in here: [[https://en.cppreference.com/w/c/atomic/memory_order]].

Jan Kończak

User Tools

Site Tools

Differences

Page Tools