Differences

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

--- os_cp:threads [2023/05/23 23:21]
jkonczak
+++ os_cp:threads [2025/04/25 13:55] (current)
jkonczak [POSIX condition variables]
@@ 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 67: / Line 69: @@
 \\
 <html><span style="float:right"><small>Needs header:<br><code>pthread.h</code></small></span>
-<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_create.html"></html>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_create.html"></html>
 ''int **pthread_create**(pthread_t *restrict //threadIdentifier//,''  \\
 ''                   const pthread_attr_t *restrict //attr//,''  \\
@@ 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 130: / Line 132: @@
 \\
 <html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
-<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_join.html"></html>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_join.html"></html>
 ''int **pthread_join**(pthread_t //thread//, void %%**%%//value_ptr//);''
 <html></a></html>
@@ 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 207: / Line 209: @@
 \\
 <html><span style="float:right"><small>Needs header: <code>pthread.h</code></small></span>
-<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_detach.html"></html>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_detach.html"></html>
 ''int **pthread_detach**(pthread_t //thread//);''
 <html></a></html>
@@ 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 273: / Line 275: @@
 POSIX offers a mechanism called //cancellation//. That is, one can send to a
 thread a cancellation request using the
-''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_cancel.html|pthread_cancel]]''
+''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_cancel.html|pthread_cancel]]''
 function. Each thread can select is behaviour on receiving such request using the
-''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_setcancelstate.html|pthread_setcancelstate]]''
+''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_setcancelstate.html|pthread_setcancelstate]]''
 and
-''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_setcancelstate.html|pthread_setcanceltype]]''
+''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_setcancelstate.html|pthread_setcanceltype]]''
 functions. One may either allow or disallow cancalling a thread, and one may
 choose whether the cancallation should ouccur immediatly after a request, or
 at the next cancallation point. Cancellation points are the execution points
 of several pthread functions, among which notably
-''[[https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_setcancelstate.html|pthread_testcancel]]''
+''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_setcancelstate.html|pthread_testcancel]]''
 is there just to this end.
 Once the thread complies to the cancellation request, it roughly does the same
@@ 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 312: / Line 314: @@
 In the main thread, collect the returned numbers and display them.
-===== Thread-specific data, thread local storage [extra] =====
-In C, data items can have different storage duration and different linkage.
+===== Accessing the same data from multiple threads =====
-Until C11, there existed only static, automatic or allocated storage durations.
-Roughly:
-\\
- • static = global variables and static variables defined inside functions,
-\\
- • automatic = items on stack, automatically allocated inside functions ('local variables'),
-\\
- • allocated = items on heap, explicitly allocated and freed.
-\\
-None of these cover a case when one wants a static ("global") variable with
-a separate value for each thread.
-Such storage duration is called [[https://en.wikipedia.org/wiki/Thread-local_storage|thread local]]
-and a coupe of ways to create thread-local items are presented in this section.
-==== POSIX Thread-specific data ====
+The following examples show what might happen upon accessing the same data from
+multiple threads with no synchronisation.
-One can create //keys// (that may be understood as identifiers of variables) and
+First, let's read/write "linearly" from/to an array from two threads:
-then associate, for each thread separately, a value for a key.
+<html><div style="margin-top:-1.4em;line-height:1.2em"></html>
-To this end the following functions can be used:
-\\
-<html><span style="float:right"><small>Need header:<br><code>pthread.h</code></small></span>
-<a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_key_create.html"></html>
-''int **pthread_key_create**(pthread_key_t *//key//, void (*//destructor//)(void*))''
-<html></a></html>
-\\
-<html><a href="https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_setspecific.html"></html>
-''int **pthread_setspecific**(pthread_key_t //key//, const void *//value//)''
-\\
-''void %%*%%**pthread_getspecific**(pthread_key_t //key//)''
-<html></a></html>
-\\
-Each key is initially associated with a ''NULL'' for each thread.
-<html><div style="line-height:1em"></html>
-++++An example code that creates a key, stores and retrieves the value from two threads.|
 <code c>
 #include <pthread.h>
 #include <stdio.h>
-#include <stdlib.h>
 #include <string.h>
-pthread_key_t mySpecificVal;
+unsigned long long version;
+char text[1020];
-void printMine() {
+void *updater(void * arg) {
-  printf("I have: %s\n", (char *)pthread_getspecific(mySpecificVal));
+  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);
+    }
 }
-void *routine(void *arg) {
+int main() {
-  char *text = malloc(4);
+  pthread_t tid;
-  strcpy(text, "baz");
+  pthread_create(&tid, NULL, updater, NULL);
-  pthread_setspecific(mySpecificVal, text);
+  while (getchar() != EOF)
-  printMine();
+    printf("version: %llu\n   text: %s\n", version, text);
-  return NULL;
+  return 0;
 }
+</code>
+<html></div></html>
-int main() {
+Next, let's read-modify-write the same variable from multiple threads:
-  char *text = malloc(4);
+<html><div style="margin-top:-1.4em;line-height:1.2em"></html>
-  strcpy(text, "foo");
+<code c>
+#include <pthread.h>
+#include <stdio.h>
-  pthread_key_create(&mySpecificVal, free);
+unsigned long long counter;
-  pthread_setspecific(mySpecificVal, text);
-  pthread_t ti;
+void *incrementer(void * arg) {
-  pthread_create(&ti, NULL, routine, NULL);
+  for (int i = 0; i < 1000; ++i)
-  pthread_join(ti, NULL);
+    counter++;
+  return NULL;
+}
-  printMine();
+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>
-==== C thread-local storage ====
+~~Exercise.#~~
+Read, understand the code, compile and run the two above examples.
-Starting with C11, a new storage duration ''_Thread_local'' or
+What is wrong with the results? What problem do these examples show?
-''[[https://en.cppreference.com/w/c/thread/thread_local|thread_local]]''((Until
-C23 ''thread_local'' was a macro defined in ''threads.h'', since C23 it
-is a keyword with same meaning as the ''_Thread_local'' keyword.)) is defined.
-Variables defined with this storage duration have unique value for each thread.
-Notice that the ''thread_local'' variables can have initial values (unlike in
-POSIX), but there is no way to provide a custom destructor (unlike in POSIX).
 ===== POSIX mutexes and readers-writers locks =====
-==== Mutex vs binary semaphore ====
-There are two vital differences between mutexes and semaphores:
-  - A mutex locked by some thread //belongs// to it and only the thread is allowed to unlock it.\\ A semaphore can be decremented/incremented by distinct threads/processes.
-  - A mutex can be configured recursive, and then it can be locked multiple times by the same thread and will be unlocked only after corresponding number of unlocks.
 ==== Mutexes ====
@@ Line 420: / Line 401: @@
 \\
 <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>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_mutex_init.html"></html>
 ''pthread_mutex_t //mutex// = **PTHREAD_MUTEX_INITIALIZER**;''
 <html></a></html>
@@ Line 427: / Line 408: @@
 \\
 <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>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_mutex_init.html"></html>
 ''int **pthread_mutex_init**(pthread_mutex_t *restrict //mutex//,'' \\
 ''                       const pthread_mutexattr_t *restrict //attr//)''
@@ Line 439: / Line 420: @@
 \\
 <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>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/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),
+  * <html><a href="https://pubs.opengroup.org/onlinepubs/9799919799/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/9799919799/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><html><a href="https://pubs.opengroup.org/onlinepubs/9799919799/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>
+  * <small>''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_mutexattr_setprotocol.html|pthread_mutexattr_setprotocol]]'' and ''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_mutexattr_setprioceiling.html|setprioceiling]]'' deal with priorities.</small>
 The mutex type impacts what happens when a mutex that is already locked is
@@ Line 457: / Line 438: @@
 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.
-Example of creating a recursive mutex:
+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;
@@ Line 465: / Line 447: @@
 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>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/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>
+<small><html><a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_mutex_timedlock.html"></html>
 ''int pthread_mutex_timedlock(pthread_mutex_t *restrict //mutex//, const struct timespec *restrict //abstime//)''
 <html></a></html></small>
@@ Line 489: / Line 472: @@
 \\
 <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>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_mutex_lock.html"></html>
 ''int **pthread_mutex_unlock**(pthread_mutex_t *//mutex//)''
 <html></a></html>
@@ Line 496: / Line 479: @@
 ~~Exercise.#~~
-Use a mutex to fix the program below so that every ''printf'' outputs 999
+Use a mutex to fix the programs from the two examples in the section
-identical letters.
+[[#accessing_the_same_data_from_multiple_threads|accessing the same data from multiple threads]].
-<html><div style="line-height:1em"></html>
-<code c letters.c>
-#include <pthread.h>
-#include <stdio.h>
-char buffer[1000];
-void *writer(void *arg) {
-  while (1)
-    for (char letter = 'a'; letter <= 'z'; ++letter)
-      for (int i = 0; i < 999; ++i)
-        buffer[i] = letter;
-}
-int main() {
-  pthread_t thread;
-  pthread_create(&thread, NULL, writer, NULL);
-  pthread_detach(thread);
-  while (getchar() != EOF)
-    printf("%s\n", buffer);
-  return 0;
-}
-</code>
-<html></div></html>
 <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 style="line-height:1em"></html>
+<html></div></html>
+++++ Source code for this exercise: |
+<html><div style="line-height:1.2em"></html>
 <code c linkedlist.c>
 #include <pthread.h>
@@ Line 627: / Line 587: @@
 </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:1em"></html>
+<html><div style="line-height:1.2em"></html>
 <code c linkedlist.c>
 void *beheader(void *arg) {
@@ Line 657: / Line 618: @@
 \\
 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.
+it with either ''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_rwlock_init.html|PTHREAD_RWLOCK_INITIALIZER]]'' macro or ''[[https://pubs.opengroup.org/onlinepubs/9799919799/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/9799919799/functions/pthread_rwlock_rdlock.html|pthread_rwlock_rdlock]]'' and ''[[https://pubs.opengroup.org/onlinepubs/9799919799/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.
+  * ''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_rwlock_wrlock.html|pthread_rwlock_wrlock]]'' and ''[[https://pubs.opengroup.org/onlinepubs/9799919799/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.
+To unlock a rwlock (locked in any mode), ''[[https://pubs.opengroup.org/onlinepubs/9799919799/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.#~~ Download and read through the {{os_cp:threads:another_bad_idea.c}} file. Which lines of code are the critical section? \\ <small>The vital parts of the file is presented below.</small>
+~~Exercise.#~~ Spot the deadlock scenario in the code from the previous exercise.
+~~Exercise.#~~ Fix the code so that it no longer is able to deadlock.
+<html><div style="line-height:1em"></html>
+<code c>
+  …
+│ struct myIO {FILE *in; FILE *out;};
+│ void* threadFunc(void *num);
+  …
+│ struct {
+│   pthread_mutex_t mtx;
+│   char text[256];
+│ } item[5];
+│
+│ int main(int argc, char **argv) {
+  …
+│   for (intptr_t i = 1; i < 5; ++i) {
+│     pthread_t tid;
+│     pthread_create(&tid, NULL, threadFunc, (void *)i);
+│     pthread_detach(tid);
+│   }
+│   threadFunc(0);
+│ }
+│
+│ void *threadFunc(void* numRaw) {
+│   intptr_t num = (intptr_t) numRaw;
+│   struct myIO win = openWin(num);
+  …
+│   while (1) {
+│     fprintf(win.out, "> ");
+│
+│     char line[1024];
+│     fgets(line, 1024, win.in);
+│     line[strlen(line)-1] = 0;
+│
+│     int argOne = atoi(line);
+  …
+│     char *argTwoTxt = strchr(line, ' ');
+│
+│     if (!argTwoTxt) {
+│       pthread_mutex_lock(&item[argOne].mtx);
+│       fprintf(win.out, "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);
+│       fprintf(win.out, "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);
+│       fprintf(win.out, "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);
+│     }
+│   }
+│ }
+  …
+</code>
+<html></div></html>
+===== Thread-specific data, thread local storage [extra] =====
+In C, data items can have different storage duration and different linkage.
+Until C11, there existed only static, automatic or allocated storage durations.
+Roughly:
+\\
+ • static = global variables and static variables defined inside functions,
+\\
+ • automatic = items on stack, automatically allocated inside functions ('local variables'),
+\\
+ • allocated = items on heap, explicitly allocated and freed.
+\\
+None of these cover a case when one wants a static ("global") variable with
+a separate value for each thread.
+Such storage duration is called [[https://en.wikipedia.org/wiki/Thread-local_storage|thread local]]
+and a coupe of ways to create thread-local items are presented in this section.
+==== POSIX Thread-specific data ====
+One can create //keys// (that may be understood as identifiers of variables) and
+then associate, for each thread separately, a value for a key.
+To this end the following functions can be used:
+\\
+<html><span style="float:right"><small>Need header:<br><code>pthread.h</code></small></span>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_key_create.html"></html>
+''int **pthread_key_create**(pthread_key_t *//key//, void (*//destructor//)(void*))''
+<html></a></html>
+\\
+<html><a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_setspecific.html"></html>
+''int **pthread_setspecific**(pthread_key_t //key//, const void *//value//)''
+\\
+''void %%*%%**pthread_getspecific**(pthread_key_t //key//)''
+<html></a></html>
+\\
+Each key is initially associated with a ''NULL'' for each thread.
+<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>
+#include <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+pthread_key_t mySpecificVal;
+void printMine() {
+  printf("I have: %s\n", (char *)pthread_getspecific(mySpecificVal));
+}
+void *routine(void *arg) {
+  char *text = malloc(4);
+  strcpy(text, "baz");
+  pthread_setspecific(mySpecificVal, text);
+  printMine();
+  return NULL;
+}
+int main() {
+  char *text = malloc(4);
+  strcpy(text, "foo");
+  pthread_key_create(&mySpecificVal, free);
+  pthread_setspecific(mySpecificVal, text);
+  pthread_t ti;
+  pthread_create(&ti, NULL, routine, NULL);
+  pthread_join(ti, NULL);
+  printMine();
+  return 0;
+}
+</code>
+++++
+<html></div></html>
+==== C thread-local storage ====
+Starting with C11, a new storage duration ''_Thread_local'' or
+''[[https://en.cppreference.com/w/c/thread/thread_local|thread_local]]''((Until
+C23 ''thread_local'' was a macro defined in ''threads.h'', since C23 it
+is a keyword with same meaning as the ''_Thread_local'' keyword.)) is defined.
+Variables defined with this storage duration have unique value for each thread.
+Notice that the ''thread_local'' variables can have initial values (unlike in
+POSIX), but there is no way to provide a custom destructor (unlike in POSIX).
 ===== POSIX condition variables =====
@@ Line 679: / Line 877: @@
 When one thread needs to execute some logic once a specific condition is fulfilled,
 it should:
+<html><div style="margin-top:-1.2em"></div></html>
+<WRAP group>
+<WRAP half column>
   - lock a mutex,
   - check the condition,
-  - if the condition is false:
+  - while the condition is false:
     - wait on a condition variable,
     - go back to step 2,
   - do the logic,
   - unlock the mutex.
+</WRAP>
+<WRAP half column>
+<html>
+<pre class="code c" style="margin-top:-1.4em;margin-bottom:-1.4em;">
+<span style="opacity:0.66">pthread_mutex_</span>lock<span class="br0">(</span><span class="sy0">&amp;</span>mutex<span class="br0">)</span><span class="sy0">;</span>
+<span class="kw1">while</span><span class="br0">(</span><span class="sy0">!</span><i>condition</i><span class="br0">)</span>
+  <span style="opacity:0.66">pthread_cond_</span>wait<span class="br0">(</span><span class="sy0">&amp;</span>condvar<span class="sy0">,</span> <span class="sy0">&amp;</span>mutex<span class="br0">)</span><span class="sy0">;</span>
+<i>logic<span class="br0">(</span><span class="br0">)</span><span class="sy0">;</span></i>
+<span style="opacity:0.66">pthread_mutex_</span>unlock<span class="br0">(</span><span class="sy0">&amp;</span>mutex<span class="br0">)</span><span class="sy0">;</span>
+</pre>
+</html>
+</WRAP>
+</WRAP>
 A thread that may change the state and thus affect the condition should:
+<html><div style="margin-top:-1.2em"></div></html>
+<WRAP group>
+<WRAP half column>
   - lock the mutex,
   - do its logic,
   - signal the condition variable,
   - unlock the mutex((One can also signal the condition variable after unlocking the mutex.)).
+</WRAP>
+<WRAP half column>
+<html>
+<pre class="code c" style="padding-top:0; padding-bottom:0; margin-top:-1.4em;margin-bottom:-1.4em;">
+<span style="opacity:0.66">pthread_mutex_</span>lock<span class="br0">(</span><span class="sy0">&amp;</span>mutex<span class="br0">)</span><span class="sy0">;</span>
+<i>logic_that_changes_condition<span class="br0">(</span><span class="br0">)</span><span class="sy0">;</span></i>
+<span style="opacity:0.66">pthread_cond_</span>signal<span class="br0">(</span><span class="sy0">&amp;</span>condvar<span class="br0">)</span><span class="sy0">;</span>
+<span style="opacity:0.66">pthread_mutex_</span>unlock<span class="br0">(</span><span class="sy0">&amp;</span>mutex<span class="br0">)</span><span class="sy0">;</span>
+</pre>
+</html>
+</WRAP>
+</WRAP>
 <small>
 The example conditions include:
+<html><div style="margin-top:-1.2em"></div></html>
   * 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,
@@ Line 703: / Line 933: @@
 \\
 <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>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_cond_init.html"></html>
 ''pthread_cond_t //cond// = **PTHREAD_COND_INITIALIZER**;''
 <html></a></html>
@@ Line 711: / Line 941: @@
 \\
 <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>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_cond_init.html"></html>
 ''int pthread_cond_init(pthread_cond_t *restrict //cond//, const pthread_condattr_t *restrict //attr//)''
 <html></a></html>
@@ Line 719: / Line 949: @@
 \\
 <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>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_cond_wait.html"></html>
 ''int **pthread_cond_wait**(pthread_cond_t *restrict //cond//, pthread_mutex_t *restrict //mutex//)''
 <html></a></html>
@@ Line 728: / Line 958: @@
 \\
 <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>
+<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/pthread_cond_broadcast.html"></html>
 ''int **pthread_cond_signal**(pthread_cond_t *restrict //cond//)''\\
 ''int **pthread_cond_broadcast**(pthread_cond_t *restrict //cond//)''
@@ Line 746: / Line 976: @@
 \\       • 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:1em"></html>
+<html><div style="line-height:1.2em"></html>
 <code c linkedlist.c>
 #include <pthread.h>
@@ Line 831: / Line 1061: @@
 \\
 The API for these synchronisation constructs looks like a simplified POSIX API:
-<html><div style="line-height:1em"></html>
+<html><div style="line-height:1.2em"></html>
 <code c>
 #include <stdio.h>

Jan Kończak

User Tools

Site Tools

Differences

Page Tools