os_cp:threads
Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| os_cp:threads [2023/05/16 23:51] – utworzono jkonczak | os_cp:threads [2025/04/25 11:55] (current) – [POSIX condition variables] jkonczak | ||
|---|---|---|---|
| Line 52: | Line 52: | ||
| pointer to arbitrary data((To specify a pointer without specifying the type of | pointer to arbitrary data((To specify a pointer without specifying the type of | ||
| underlying data one has to use '' | underlying data one has to use '' | ||
| + | < | ||
| <code c> | <code c> | ||
| void * start_routine (void * argument){ | void * start_routine (void * argument){ | ||
| Line 58: | Line 59: | ||
| } | } | ||
| </ | </ | ||
| + | < | ||
| < | < | ||
| '' | '' | ||
| Line 67: | Line 69: | ||
| \\ | \\ | ||
| < | < | ||
| - | <a href=" | + | <a href=" |
| '' | '' | ||
| '' | '' | ||
| Line 77: | Line 79: | ||
| argument is not NULL, thread attributes will be set before starting the thread. | argument is not NULL, thread attributes will be set before starting the thread. | ||
| - | < | + | < |
| ++++An example of creating a thread and passing it some data| | ++++An example of creating a thread and passing it some data| | ||
| <code c> | <code c> | ||
| Line 130: | Line 132: | ||
| \\ | \\ | ||
| < | < | ||
| - | <a href=" | + | <a href=" |
| '' | '' | ||
| < | < | ||
| Line 138: | Line 140: | ||
| The ''// | The ''// | ||
| - | < | + | < |
| ++++An example code that creates 3 threads and joins them, collecting their result.| | ++++An example code that creates 3 threads and joins them, collecting their result.| | ||
| <code c> | <code c> | ||
| Line 207: | Line 209: | ||
| \\ | \\ | ||
| < | < | ||
| - | <a href=" | + | <a href=" |
| '' | '' | ||
| < | < | ||
| Line 217: | Line 219: | ||
| typically the thread that spawned it calls the detach. | typically the thread that spawned it calls the detach. | ||
| - | < | + | < |
| ++++An example code that creates a thread and detaches it.| | ++++An example code that creates a thread and detaches it.| | ||
| <code c> | <code c> | ||
| Line 269: | Line 271: | ||
| ++++ | ++++ | ||
| < | < | ||
| + | |||
| + | < | ||
| + | POSIX offers a mechanism called // | ||
| + | thread a cancellation request using the | ||
| + | '' | ||
| + | function. Each thread can select is behaviour on receiving such request using the | ||
| + | '' | ||
| + | and | ||
| + | '' | ||
| + | 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 | ||
| + | '' | ||
| + | is there just to this end. | ||
| + | Once the thread complies to the cancellation request, it roughly does the same | ||
| + | actions as if '' | ||
| + | The cancellation mechanism allows deferring thread termination until a logically consistent state (e.g. of data shared with other threads) is reached. | ||
| + | </ | ||
| === Exercises === | === Exercises === | ||
| Line 278: | Line 299: | ||
| ~~Exercise.# | ~~Exercise.# | ||
| - | Remove the code you wrote for the previous exercise the '' | + | Remove |
| - | 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.# | ~~Exercise.# | ||
| Line 292: | Line 313: | ||
| the ordinal number, and return it from the thread entry routine. | the ordinal number, and return it from the thread entry routine. | ||
| In the main thread, collect the returned numbers and display them. | 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 " | ||
| + | < | ||
| + | <code c> | ||
| + | #include < | ||
| + | #include < | ||
| + | #include < | ||
| + | |||
| + | unsigned long long version; | ||
| + | char text[1020]; | ||
| + | |||
| + | void *updater(void * arg) { | ||
| + | while (1) | ||
| + | for (char letter = ' | ||
| + | version++; | ||
| + | for (int i = 0; i < 1020 - 1; ++i) | ||
| + | text[i] = letter; | ||
| + | // memset(text, | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() { | ||
| + | pthread_t tid; | ||
| + | pthread_create(& | ||
| + | while (getchar() != EOF) | ||
| + | printf(" | ||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | < | ||
| + | |||
| + | Next, let's read-modify-write the same variable from multiple threads: | ||
| + | < | ||
| + | <code c> | ||
| + | #include < | ||
| + | #include < | ||
| + | |||
| + | 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, | ||
| + | for (int i = 0; i < 16; ++i) | ||
| + | pthread_join(tid[i], | ||
| + | printf(" | ||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | < | ||
| + | < | ||
| + | < | ||
| + | '' | ||
| + | </ | ||
| + | < | ||
| + | |||
| + | ~~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:// | ||
| + | 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// | ||
| + | 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 '' | ||
| + | and initialize it, using either an initializer macro: | ||
| + | \\ | ||
| + | < | ||
| + | <a href=" | ||
| + | '' | ||
| + | < | ||
| + | \\ | ||
| + | to initialize a mutex with default semantics, or an initialisation function: | ||
| + | \\ | ||
| + | < | ||
| + | <a href=" | ||
| + | '' | ||
| + | '' | ||
| + | < | ||
| + | |||
| + | When using the '' | ||
| + | for a mutex. | ||
| + | \\ | ||
| + | To do so, one has to declare a '' | ||
| + | initialize it using: | ||
| + | \\ | ||
| + | < | ||
| + | <a href=" | ||
| + | '' | ||
| + | < | ||
| + | \\ | ||
| + | and finally set the attributes using corresponding functions: | ||
| + | * < | ||
| + | * < | ||
| + | * < | ||
| + | * < | ||
| + | |||
| + | The mutex type impacts what happens when a mutex that is already locked is | ||
| + | locked again by the same thread: | ||
| + | * '' | ||
| + | * '' | ||
| + | * '' | ||
| + | * '' | ||
| + | Some mutex types also guarantee failing((returning '' | ||
| + | |||
| + | An example of creating a recursive mutex is as follows: | ||
| + | < | ||
| + | <code c> | ||
| + | pthread_mutexattr_t recursiveAttrs; | ||
| + | pthread_mutexattr_init(& | ||
| + | pthread_mutexattr_settype(& | ||
| + | pthread_mutex_t mutex; | ||
| + | pthread_mutex_init(& | ||
| + | </ | ||
| + | < | ||
| + | |||
| + | To lock a mutex one can use either of: | ||
| + | \\ | ||
| + | < | ||
| + | <a href=" | ||
| + | '' | ||
| + | '' | ||
| + | < | ||
| + | \\ | ||
| + | < | ||
| + | '' | ||
| + | < | ||
| + | \\ | ||
| + | If the ''// | ||
| + | currently locked, '' | ||
| + | '' | ||
| + | < | ||
| + | \\ | ||
| + | < | ||
| + | accordingly.</ | ||
| + | |||
| + | To unlock a mutex, one has to use the function: | ||
| + | \\ | ||
| + | < | ||
| + | <a href=" | ||
| + | '' | ||
| + | < | ||
| + | \\ | ||
| + | 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 | ||
| + | [[# | ||
| + | |||
| + | < | ||
| + | < | ||
| + | ~~Exercise.# | ||
| + | The program below accesses a linked list from multiple threads. | ||
| + | Add mutexes to functions which names start with '' | ||
| + | no longer crashes. | ||
| + | < | ||
| + | ++++ Source code for this exercise: | | ||
| + | < | ||
| + | <code c linkedlist.c> | ||
| + | #include < | ||
| + | #include < | ||
| + | #include < | ||
| + | #include < | ||
| + | |||
| + | 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-> | ||
| + | newNode-> | ||
| + | if (l->tail == NULL) { | ||
| + | newNode-> | ||
| + | l->head = l->tail = newNode; | ||
| + | } else { | ||
| + | newNode-> | ||
| + | l-> | ||
| + | l->tail = newNode; | ||
| + | } | ||
| + | return newNode; | ||
| + | } | ||
| + | |||
| + | void list_delete_node(struct list *l, struct node *n) { | ||
| + | if (n-> | ||
| + | l->head = n->next; | ||
| + | else | ||
| + | n-> | ||
| + | if (n->next == NULL) | ||
| + | l->tail = n-> | ||
| + | else | ||
| + | n-> | ||
| + | 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 = next; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | void list_print(struct list *l, int reverse) { | ||
| + | struct node *n = reverse ? l->tail : l->head; | ||
| + | while (n != NULL) { | ||
| + | printf(" | ||
| + | n = reverse ? n-> | ||
| + | } | ||
| + | } | ||
| + | |||
| + | void *adder(void *arg) { | ||
| + | struct list *l = (struct list *)arg; | ||
| + | srand(time(0)); | ||
| + | while (1) { | ||
| + | list_add_back(l, | ||
| + | usleep(10); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | void *remover(void *arg) { | ||
| + | struct list *l = (struct list *)arg; | ||
| + | srand(time(0) + 2); | ||
| + | while (1) { | ||
| + | list_delete_value(l, | ||
| + | usleep(5); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() { | ||
| + | struct list l; | ||
| + | list_init(& | ||
| + | | ||
| + | pthread_t a, r; | ||
| + | pthread_create(& | ||
| + | pthread_create(& | ||
| + | pthread_detach(a); | ||
| + | pthread_detach(r); | ||
| + | |||
| + | while (getchar() != EOF) | ||
| + | list_print(& | ||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | < | ||
| + | ++++ | ||
| + | |||
| + | ~~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: | ||
| + | < | ||
| + | <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, | ||
| + | usleep(50); | ||
| + | } | ||
| + | } | ||
| + | </ | ||
| + | < | ||
| + | </ | ||
| + | |||
| + | ==== Readers-writers locks [extra] ==== | ||
| + | |||
| + | A [[https:// | ||
| + | (// | ||
| + | offers two modes of locking: shared (// | ||
| + | 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 '' | ||
| + | it with either '' | ||
| + | \\ | ||
| + | A read-write lock can be locked with: | ||
| + | * '' | ||
| + | * '' | ||
| + | < | ||
| + | \\ | ||
| + | To unlock a rwlock (locked in any mode), '' | ||
| + | |||
| + | |||
| + | ===== [extra] Concurrency, | ||
| + | |||
| + | The aim of __[[https:// | ||
| + | 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:// | ||
| + | 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:// | ||
| + | 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:// | ||
| + | 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 '' | ||
| + | could wake the ones waiting (say, execute '' | ||
| + | the waiting ones, then a __[[https:// | ||
| + | occurred. | ||
| + | \\ | ||
| + | A deadlock usually means that the processing stops. | ||
| + | |||
| + | < | ||
| + | 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: | ||
| + | < | ||
| + | < | ||
| + | < | ||
| + | <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) { | ||
| + | pthread_mutex_lock(& | ||
| + | if (*x==0 && *y==0) { | ||
| + | /* do business logic */ | ||
| + | loop = 0; | ||
| + | } | ||
| + | pthread_mutex_unlock(& | ||
| + | } | ||
| + | </ | ||
| + | </ | ||
| + | < | ||
| + | |||
| + | __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:// | ||
| + | \\ | ||
| + | If the algorithm is completely unfair for some process / thread, it can | ||
| + | __[[https:// | ||
| + | never entering the critical section on contention. | ||
| + | |||
| + | ===== Critical sections, deadlocks ===== | ||
| + | |||
| + | ~~Exercise.# | ||
| + | |||
| + | ~~Exercise.# | ||
| + | |||
| + | ~~Exercise.# | ||
| + | |||
| + | < | ||
| + | <code c> | ||
| + | … | ||
| + | 10│ struct myIO {FILE *in; FILE *out;}; | ||
| + | 11│ void* threadFunc(void *num); | ||
| + | … | ||
| + | 17│ struct { | ||
| + | 18│ | ||
| + | 19│ char text[256]; | ||
| + | 20│ } item[5]; | ||
| + | 21│ | ||
| + | 22│ int main(int argc, char **argv) { | ||
| + | … | ||
| + | 28│ for (intptr_t i = 1; i < 5; ++i) { | ||
| + | 29│ | ||
| + | 30│ | ||
| + | 31│ | ||
| + | 32│ } | ||
| + | 33│ | ||
| + | 34│ } | ||
| + | 35│ | ||
| + | 36│ void *threadFunc(void* numRaw) { | ||
| + | 37│ | ||
| + | 38│ | ||
| + | … | ||
| + | 48│ while (1) { | ||
| + | 49│ | ||
| + | 50│ | ||
| + | 51│ char line[1024]; | ||
| + | 52│ | ||
| + | 53│ | ||
| + | 54│ | ||
| + | 55│ int argOne = atoi(line); | ||
| + | … | ||
| + | 61│ char *argTwoTxt = strchr(line, | ||
| + | 62│ | ||
| + | 63│ if (!argTwoTxt) { | ||
| + | 65│ | ||
| + | 66│ | ||
| + | 67│ | ||
| + | 68│ | ||
| + | 69│ } | ||
| + | 70│ | ||
| + | 71│ | ||
| + | 72│ char *e; | ||
| + | 73│ int argTwo = strtol(argTwoTxt, | ||
| + | 74│ | ||
| + | 75│ if (!*e && argTwo < 5 && argTwo >= 0 && argOne != argTwo) { | ||
| + | 77│ | ||
| + | 78│ | ||
| + | 79│ | ||
| + | 80│ | ||
| + | 81│ | ||
| + | 82│ | ||
| + | 83│ } else { | ||
| + | 85│ | ||
| + | 86│ | ||
| + | 87│ | ||
| + | 88│ | ||
| + | 89│ | ||
| + | 90│ } | ||
| + | 91│ } | ||
| + | 92│ } | ||
| + | … | ||
| + | </ | ||
| + | < | ||
| ===== Thread-specific data, thread local storage [extra] ===== | ===== Thread-specific data, thread local storage [extra] ===== | ||
| Line 317: | Line 801: | ||
| \\ | \\ | ||
| < | < | ||
| - | <a href=" | + | <a href=" |
| '' | '' | ||
| < | < | ||
| \\ | \\ | ||
| - | < | + | < |
| '' | '' | ||
| \\ | \\ | ||
| Line 329: | Line 813: | ||
| Each key is initially associated with a '' | Each key is initially associated with a '' | ||
| - | < | + | < |
| ++++An example code that creates a key, stores and retrieves the value from two threads.| | ++++An example code that creates a key, stores and retrieves the value from two threads.| | ||
| <code c> | <code c> | ||
| Line 379: | Line 863: | ||
| POSIX), but there is no way to provide a custom destructor (unlike in POSIX). | POSIX), but there is no way to provide a custom destructor (unlike in POSIX). | ||
| + | |||
| + | ===== POSIX condition variables ===== | ||
| + | |||
| + | [[https:// | ||
| + | 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: | ||
| + | < | ||
| + | <WRAP group> | ||
| + | <WRAP half column> | ||
| + | - lock a mutex, | ||
| + | - check the condition, | ||
| + | - while the condition is false: | ||
| + | - wait on a condition variable, | ||
| + | - go back to step 2, | ||
| + | - do the logic, | ||
| + | - unlock the mutex. | ||
| + | </ | ||
| + | <WRAP half column> | ||
| + | < | ||
| + | <pre class=" | ||
| + | <span style=" | ||
| + | <span class=" | ||
| + | <span style=" | ||
| + | < | ||
| + | <span style=" | ||
| + | </ | ||
| + | </ | ||
| + | </ | ||
| + | </ | ||
| + | A thread that may change the state and thus affect the condition should: | ||
| + | < | ||
| + | <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 half column> | ||
| + | < | ||
| + | <pre class=" | ||
| + | <span style=" | ||
| + | < | ||
| + | <span style=" | ||
| + | <span style=" | ||
| + | </ | ||
| + | </ | ||
| + | </ | ||
| + | </ | ||
| + | |||
| + | < | ||
| + | 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. | ||
| + | </ | ||
| + | |||
| + | To use a condition variable, one has to declare a '' | ||
| + | and then initialize it with: | ||
| + | \\ | ||
| + | < | ||
| + | <a href=" | ||
| + | '' | ||
| + | < | ||
| + | \\ | ||
| + | to use default semantic, < | ||
| + | choosing desired semantic: | ||
| + | \\ | ||
| + | < | ||
| + | <a href=" | ||
| + | '' | ||
| + | < | ||
| + | </ | ||
| + | |||
| + | A thread holding mutex //mutex// can use the function: | ||
| + | \\ | ||
| + | < | ||
| + | <a href=" | ||
| + | '' | ||
| + | < | ||
| + | \\ | ||
| + | to atomically release the //mutex// and start waiting on //cond//. | ||
| + | |||
| + | Another thread can use one of the functions: | ||
| + | \\ | ||
| + | < | ||
| + | <a href=" | ||
| + | '' | ||
| + | '' | ||
| + | < | ||
| + | \\ | ||
| + | to wake at least one ('' | ||
| + | threads waiting on the condition variable '' | ||
| + | \\ | ||
| + | The thread that is signalling/ | ||
| + | |||
| + | ~~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. | ||
| + | < | ||
| + | <code c linkedlist.c> | ||
| + | #include < | ||
| + | #include < | ||
| + | #include < | ||
| + | #include < | ||
| + | |||
| + | 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-> | ||
| + | } | ||
| + | |||
| + | int take_element() { | ||
| + | int v = head-> | ||
| + | struct element *e = head; | ||
| + | head = head-> | ||
| + | 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, | ||
| + | |||
| + | int computed_count = 0; | ||
| + | while (computed_count < 10) { | ||
| + | while (head == NULL); | ||
| + | int value = take_element(); | ||
| + | printf(" | ||
| + | } | ||
| + | |||
| + | for (int i = 0; i < 4; ++i) | ||
| + | pthread_cancel(t[i]); | ||
| + | for (int i = 0; i < 4; ++i) | ||
| + | pthread_join(t[i], | ||
| + | |||
| + | return 0; | ||
| + | } | ||
| + | </ | ||
| + | < | ||
| + | |||
| + | ~~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. | ||
| + | \\ | ||
| + | < | ||
| + | This idea of creating worker threads and passing them tasks is very popular | ||
| + | bears the name [[https:// | ||
| + | software engineering. | ||
| + | </ | ||
| + | |||
| + | ===== 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: | ||
| + | < | ||
| + | <code c> | ||
| + | #include < | ||
| + | #include < | ||
| + | |||
| + | mtx_t mutex; | ||
| + | cnd_t condition_variable; | ||
| + | |||
| + | char shared_data = 0; | ||
| + | |||
| + | int func(void *arg); | ||
| + | |||
| + | int main() { | ||
| + | mtx_init(& | ||
| + | cnd_init(& | ||
| + | thrd_t t; | ||
| + | thrd_create(& | ||
| + | char c = getchar(); | ||
| + | |||
| + | mtx_lock(& | ||
| + | shared_data = c; | ||
| + | mtx_unlock(& | ||
| + | cnd_signal(& | ||
| + | |||
| + | thrd_join(t, | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | int func(void *arg) { | ||
| + | char c; | ||
| + | |||
| + | mtx_lock(& | ||
| + | while (shared_data == 0) | ||
| + | cnd_wait(& | ||
| + | c = shared_data; | ||
| + | mtx_unlock(& | ||
| + | |||
| + | printf(" | ||
| + | |||
| + | return thrd_success; | ||
| + | } | ||
| + | </ | ||
| + | < | ||
| + | For a full reference, consult for instance: [[https:// | ||
| + | |||
| + | ===== Atomic variables [extra] ===== | ||
| + | |||
| + | Current [[https:// | ||
| + | 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:// | ||
| + | * [[https:// | ||
| + | * [[https:// | ||
| + | |||
| + | 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 '' | ||
| + | type specifier or '' | ||
| + | \\ | ||
| + | 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:// | ||
| + | \\ | ||
| + | The list of available atomic operations includes: load, store, swap, test-and-set, | ||
| + | compare-and-swap, | ||
| + | \\ | ||
| + | For details, consult e.g., [[https:// | ||
| + | |||
| + | Each atomic instruction in C can be also combined with a memory ordering | ||
| + | instruction. A memory ordering instruction can be issued explicitly using | ||
| + | '' | ||
| + | The memory model of C, as well as the memory ordering enum values, are described | ||
| + | among others in here: [[https:// | ||
os_cp/threads.1684281061.txt.gz · Last modified: (external edit)