This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
os_cp:threads:solutions [2023/09/15 15:21] jkonczak |
os_cp:threads:solutions [2024/05/07 22:40] (current) jkonczak |
||
---|---|---|---|
Line 98: | Line 98: | ||
} | } | ||
</code> | </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.#~~ | ~~Exercise.#~~ | ||
Line 104: | Line 123: | ||
#include <pthread.h> | #include <pthread.h> | ||
#include <stdio.h> | #include <stdio.h> | ||
+ | #include <string.h> | ||
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; | 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) | while (1) | ||
for (char letter = 'a'; letter <= 'z'; ++letter) { | for (char letter = 'a'; letter <= 'z'; ++letter) { | ||
pthread_mutex_lock(&mutex); | 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); | pthread_mutex_unlock(&mutex); | ||
} | } | ||
Line 120: | Line 141: | ||
int main() { | 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) { | while (getchar() != EOF) { | ||
pthread_mutex_lock(&mutex); | 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); | 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; | return 0; | ||
} | } | ||
</code> | </code> | ||
+ | </small> | ||
~~Exercise.#~~ | ~~Exercise.#~~ | ||
Line 242: | Line 319: | ||
return 0; | 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> | </code> | ||
Line 324: | Line 417: | ||
... | ... | ||
</code> | </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> | <html></div></html> |