CSE 305 - Tutorial 4 - Synchronization

Improve the function FindParallel from the first homework to become FindParallel(arr, N, target, count, num_threads) (where arr is a pointer at the beginning of the array and N is its length) that takes one extra input, a positive integer count, and returns True if there are at least count occurrences of target. You function must terminate right after count occurences have been found. In particular, it is not allowed to count the occurences and then decide whether the number is greater than count or not.

Hint: use an atomic integer for counting the occurences.

Implement a class Account (full specification in td4.cpp) having a the following methods

• static method bool transfer(unsigned int amount, Account& from, Account& to). This methods should transfer money from one account to another in a thread-safe manner.

• methods add and withdraw to add and withdraw money, respectively. The latter should not withdraw anything (and return false) if the funds are not sufficient. Both methods must be thread-safe.

Implement this in a way that deadlocks cannot occur. You are not allowed to use std::lock in this exercise.

Hint: You can avoid deadlocks if all locks will be always taken in the same order by a thread. In order to achieve this, introduce a unique account number for each account (the uniqueness can be achieved by having a static variable holding the largest of already assigned id’s), and take locks in the order of increasing id’s (If you are interested, you can read about more general “hierarchical locks” in Section 3.2.5 of “C++ Concurrency in Action”).

Caveat 1: Consider the following situation: Alice has 100$, Bob has 0$. Alice sends her 100$ to Bob. At the same time Carol attempts to receive 100$ first from Alice and then from Bob. A natural common sense requirement is that at least one the these transfers to Carol must succeed. Make sure that your code satisfies this requirement.

Caveat 2: Make sure you do not lock the same mutex twice without unlocking, this leads to undefined behaviour, according to the standard.

Implement a static function Account::massiv_withdraw which takes a vector of pointers to the accounts and withdraws the same amount from them in a thread-safe manner if all the accounts have sufficient funds. As in the previous problem, think about avoiding deadlocks.

Hint: you will likely need to create a vector of lock_guards, this may be easier with unique_lock.

Implement your own lock class (full description is given in td4.cpp) using compare_exchange_weak and atomic boolean.