Differences

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

--- os_cp:threads [2023/05/23 23:21]
jkonczak
+++ 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 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 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:
@@ 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 665: / Line 626: @@
 \\
 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] =====
+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/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: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 746: / Line 963: @@
 \\       • 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 1048: @@
 \\
 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