pthread_cons_signal()
and that thread B executes pthread_cons_wait()
on the same condition variable. For each of the following scenarios:
pthread_cond_signal()
awakes thread C, which was waiting on that condition variablepthread_cond_signal()
does not awake any thread, as no thread was waiting on that condition variablepthread_cond_wait()
by thread B. Justify your answer.Note To compile thread-based programs you must use the -pthread
compiler option. This ensures linking with the libpthread
library and with the thread-safe functions of the C library.
IMP. Follow an incremental code development approach. If you write all the code in a single go and only then compile it, you risk spending the following 15 minutes eliminating the compilation errors and the remaining class debugging it. Instead, you should add code step by step, compiling it and testing it, after each step.
Write the code for a stack in an object oriented way. (All functions of the stack should be in implemented in its own C source file.) Each stack element shall have the following type (which should be included in the header file):
struct stack_el{ char *str; /* String to be printed in show() */ int n; /* Integer to be printed in show() */ };
The stack itself can be implemented as the following type:
struct stack{ struct stack_el ** sp; /* Pointer to array of fixed size for storing the stack elements */ int size; /* Number of elements in the array */ int top; /* Pointer to the top of the stack: initially 0 */ };
Your stack shall provide the standard push()
and pop()
functions, and also a show()
function, which lists all elements in the stack from top to the bottom, as well as init()
and free()
methods. The details of the API are provided in file stack6.h
Note that:
push()
should return 0, and 1 otherwisepop()
should return NULL
, and a pointer to the element that was on the top of the stack, otherwise.Write a small (single-threaded) test program using the functions you have developed.
Write a thread safe version of your stack abstract data type using mutexes. Programs that use your thread safe version of the stack, should not have to invoke explicitly any synchronization primitives. Test it using a multi-threaded program based on the one you have developed for exercise 2.d) of the last set of problems.
In this new version, push()
must always push its input element onto the stack, and return 1. If the stack is full, a thread must wait, inside push()
, until it succeeds pushing the input element on its stack
Likewise, pop()
must always pop an element from the stack and return a pointer to that element. If the stack is empty, a thread must wait inside pop()
, until it succeeds to pop some element from the stack.
Test it using a multi-threaded program based on the one you have developed for exercise 2.d) of the last set of problems.
Write a new version of your solution that uses condition variables to reduce busy waiting.
Test it using a multi-threaded program based on the one you have developed for exercise 2.d) of the last set of problems.
A classical concurrency problem is the readers-writers problem. In this problem, a set of threads accesses to a shared variable. Some of these threads, the readers, only read the variable, whereas the remaining threads, the writers, only write to the variable.
Since reading operations do not interfere with one another, we can increase concurrency, by allowing simultaneous reading operations. On the other hand, write operations interfere with both reading and writing operations, and therefore a write operation must be executed in mutual exclusion. I.e., when a writer thread accesses to the shared variable, no other thread, either reader or writer, should access the shared variable. (Check Section 31.5 of the OSTEP book for a more detailed discussion of this problem.)
In this problem, you should solve a variant of the readers-writers using mutexes and condition variables. In particular, there are two global integer variables, m
and n
, which should be initialized to 0 by the main thread. The main thread creates 2 writer threads and 2 reader threads, and waits for them to exit. After termination of the 4 threads, the main thread should print the final value of the two variables.
Each of the writer threads shall execute a loop 50 million times. In each iteration, a writer shall increment by one each of the two variables, so that their value when the program terminates should be 100 millions.
Each of the reader threads shall execute a loop also 50 million times. In each iteration, a reader shall read the 2 variables and print them after every 1 million iterations. The threads should synchronize in such a way that the values of the two variables printed are identical.
When there is at least one reader accessing the variables, no writer should change the value of these variables, however it is possible for another reader to read them. So the critical question is:
If a reader is reading the variables and a writer is waiting to write, should we allow another reader to read the shared variable, further delaying the writer?
The alternatives are clear:
Try to solve this problem using both strategies (one at a time). Are the observed results as you were expecting?
A sorting algorithm especially appropriate for multiprocessor/multicore systems is merge-sort. The idea is to store the values to sort in an array and divide the array into n (the number of values to sort) subarrays of 1 element each. Then, repeatedly merge subarrays to produce sorted subarrays, until there is only one sorted subarray of n elements. (Check e.g. the Wikipedia's page on merge-sort.)
In this problem you shall write a parallel version of the merge-sort algorithm to sort in increasing order an array with 1 million integers. The main thread shall initialize the array to sort in decreasing order. It shall also create the threads that will do the sorting. The no. of sorting threads shall be a command line argument. Your solution does not need to implement the standard merge-sort, but you should try to maximize concurrency, and use mutexes and condition variables for thread synchronization.
Once the sorting algorithm terminates, the main thread shall check that the array has been correctly sorted.
Hint: Start by implementing merge-sort with a single thread. This algorithm should use two functions sort()
and merge()
, which is called by the former.