CSE 305 - Tutorial 5

In this tutorial, you will be asked to implement classes/functions described below. The exact definitions and automated tests are given to you in the following archive.

Your task is to fill the implementations of the functions in td5.cpp and submit it on this page by 23:59 April 29. The solution will be graded first by autograder (40% of the grade) and then manually (remaining 60% of the grade). You are allowed (and encouraged) to revise your code based on the output of autograder and resubmit again before the deadline.

Write a function DivideOnceEven(cv, m, n) which takes as input references to a condition variable cv, mutex m, and integer n. Then the function should lock the mutex and use this lock to wait on the condition variable until n becomes even. Once n becomes even, the function should divide it by 2 and terminate.
Based on the thread-safe blocking bounded queue from the lecture, implement its unbounded version by using std::queue instead of a vector in a class SafeUnboundedQueueLock. The class should have a method push and pop_nonblocking. The latter should throw an exception if the queue is empty. Detailed specification is given in td5.cpp.
For the unbounded queue from the previous exercise, implement a method pop_blocking which does not throw an exception but uses busy waiting: if queue is empty, it will release the lock and try again until it succeeds. Detailed specification is given in td5.cpp
Now implement a safe undounded queue in a new class SafeUnboundedQueueCV with blocking pop but without busy waiting. Use condition variables as explained in the last lecture. Detailed specification is given in td5.cpp.

Upload your file td5.cpp:

Upload form is only available when connected

The following problem is optional.

In this exercise, we would like to parallelize the Eratosthene’s sieve algortihm (see a sequentual implementation in primes.cpp). The function should output all prime numbers from \(1\) to \(N\) in the ascending order. One way to parallelize it is to use a fact that if \(N\) is a composite number, then it has a divisor not exceeding \(\sqrt{N}\). So one can use a single thread to perform computations until \(\sqrt{N}\) and parallelize marking the remaining numbers. (important: it may be tempting to use an array of bool, do not do this! See TD1 for why).

If you try this exercise, please, write in the comments what was the speed up you were able to get (it is quite tricky).

Upload your file primes.cpp:

Upload form is only available when connected