This assignment will be closed on May 14, 2025 (23:59:59).
You must be authenticated to submit your files

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 May 14. 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.

  1. 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.

  2. 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

  3. Implement a class OrderedVec (full description in td5.cpp) that stores internally a sorted vector of integers and allows for thread-safe insertion and search: at most one operation (search or insertion) may happen at each moment.

  4. Continuing with the class OrderedVec from the previous exercise: insertions change the internal state, so should not be performed concurrently. On the other hand, there is no problem in performing several searches at the same time. Update the code so that: when an insertion is happening, nothing else can happen, while searches can happen at the same time (as they do not change the internal state).

    Hint: you can add a counter for the currently ongoing searches which can be incremented only under a lock (so, if this lock is taken by an insertion, no new searcher will start).

Upload your file td5.cpp:

Upload form is only available when connected

The following problem is optional.

  1. 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