Differences

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

--- os_cp:threads:solutions [2023/09/15 13:21] – jkonczak
+++ os_cp:threads:solutions [2024/05/07 20:40] (current) – jkonczak
@@ Line 98: / Line 98: @@
 }
 </code>
+~~Exercise.#~~
+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.#~~
@@ Line 104: / Line 123: @@
 #include <pthread.h>
 #include <stdio.h>
+#include <string.h>
 pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
+unsigned long long version;
+char text[1020];
-char buffer[1000];
+void *updater(void *arg) {
-void *writer(void *arg) {
   while (1)
     for (char letter = 'a'; letter <= 'z'; ++letter) {
       pthread_mutex_lock(&mutex);
-      for (int i = 0; i < 999; ++i)
+      version++;
-        buffer[i] = letter;
+      for (int i = 0; i < 1020 - 1; ++i)
+        text[i] = letter;
       pthread_mutex_unlock(&mutex);
     }
@@ Line 120: / Line 141: @@
 int main() {
-  pthread_t thread;
+  pthread_t tid;
-  pthread_create(&thread, NULL, writer, NULL);
+  pthread_create(&tid, NULL, updater, NULL);
-  pthread_detach(thread);
   while (getchar() != EOF) {
     pthread_mutex_lock(&mutex);
-    printf("%s\n", buffer);
+    // 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;
+}
+</code>
+<code c>
+#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;
+}
+</code>
+<small>
+Notice that the second example can also be amended more efficiently by using atomic operations:
+<code c>
+#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;
 }
 </code>
+</small>
 ~~Exercise.#~~
@@ Line 242: / Line 319: @@
   return 0;
 }
+</code>
+~~Exercise.#~~
+Critical sections in this particular example are the lines between ''pthread_mutex_lock''(s) and ''pthread_mutex_unlock''(s)
+~~Exercise.#~~
+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.#~~
+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:
+<code c>
+      pthread_mutex_lock(&item[argOne < argTwo ? argOne : argTwo].mtx);
+      pthread_mutex_lock(&item[argOne < argTwo ? argTwo : argOne].mtx);
 </code>
@@ Line 324: / Line 417: @@
 ...
 </code>
+~~Exercise.#~~
+<code c>#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);
+  }
+}
+</code>
 <html></div></html>