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.
Your program should be executed as follows:
$ ./p1a <no. of threads> <no. of iterations>
where we assume the name of the program is p1a and:
- <no. of threads>
- is the number of producer threads, which should be equal to the number of consumer threads
- <no. of iterations>
- is the number of iterations each thread should execute, i.e. the number of integers each producer thread should put in the buffer and the number of integers each consumer should get from the buffer.
The main thread should create all the consumer and all the producer threads (in this order) and should then wait for all these threads to terminate and print the value of a global variable, named sum, which should have been initialized with 0 at the beginning of the program, and finally exit.
Each producer thread should execute a loop with a number of iterations equal to the 3rd argument. In each iteration, the producer thread should add one integer to the buffer. (This integer may be 1, or the iteration number, or ...)
Each consumer thread should execute a loop with a number of iterations equal to the 3rd argument. In each iteration, the consumer thread should get one integer from the buffer and add that integer to the global variable sum.
typedef struct{
int *buf; /* buffer */
int size; /* buffer size */
int count; /* no. of busy slots */
int p; /* index for next insertion */
int c; /* index for next removal */
} bb_t;
In addition, this data structure should also include as members the required synchronization variables, i.e. either mutexes or condition variables.
The bounded buffer data type should provide the following functions:
bb_t * bb_init(int size); void bb_put(bb_t *bbp, int i); int bb_get(bb_t *bbp);
where:
- bb_t *bb_init(int size)
- creates a bounded buffer, by allocating dynamically a bb_t structure and also the buffer with space for size integers, and initializes the synchronization variables by calling the appropriate pthread_xxx_init() function. It returns the allocated bb_t structure.
- void bb_put(bb_t *bbp, int i)
- inserts the integer i in the bounded buffer pointed to bbp. This function should be thread-safe, by calling the appropriate functions on the synchronization variables in the bb_t struct. Therefore, producers should not have to worry with race conditions, all they need to do is to call bb_put()
- int bb_get(bb_t *bbp)
- returns an integer from the bounded buffer pointed to bbp. Like put(), this function should be thread-safe, by calling the appropriate functions on the synchronization variables in the bb_t struct. Therefore, consumers should not have to worry with race conditions, all they need to do is to call bb_get()
This new version of the program should take the same arguments as the previous version.
Write a new version of p1a, which has now 4 arguments:
$ ./p1c <no. of producers> <no. of consumers> <total no. of items to produce>
where:
- <no. of producers>
- is the number of producer threads
- <no. of consumers>
- is the number of consumers threads
- <total no. of items to produce>
- is the total no. of items to produce by all producers. Of course, each of these items should also be consumed by some consumer
Hint: The challenge in this program is to prevent threads from remaining blocked indefinitely once the total number of items has been produced/consumed. Therefore a relatively simple solution is to use pthread_cond_broadcast(). Once you find a solution with that primitive, try to solve this problem using only pthread_cond_signal().
Write a new version of p1c, this time using the thread-safe bounded buffer type, bb_t, that you have developed in b above.
Hint: Try first to use your solution of exercise b. To get it working most probably you will have to change the interface provided by the bounded buffer interface. This illustrates the limits of encapsulation.
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.