Lab 1 - "Non-cooperative" multithreading

Due: week 4.

Each student will fully solve a single problem. However, looking at how to solve the others is highly recommended.

Goal

The goal of this lab is to refresh the knowledge regarding threads and mutexes.

The programs to be written will demonstrate the usage of threads to do non-cooperative work on shared data. The access to the shared data must be protected by using mutexes.

Common requirements

1. The problems will require to execute a number of independent operations, that operate on shared data.
2. There shall be several threads launched at the beginning, and each thread shall execute a lot of operations. The operations to be executed are to be randomly choosen, and with randomly choosen parameters.
3. The main thread shall wait for all other threads to end and, then, it shall check that the invariants are obeyed.
4. The operations must be synchronized in order to operate correctly. Write, in a documentation, the rules (which mutex what invariants it protects).
5. You shall play with the number of threads and with the granularity of the locking, in order to asses the performance issues. Document what tests have you done, on what hardware platform, for what size of the data, and what was the time consumed.

Problems

1. Warehouses:

A wholesaler has several warehouses storing goods.

We must keep track of the quantity of each product, in each of the warehouses.

We have some moves between warehouses running concurrently, on several threads. Each move consists in moving some given amounts of some product types from a given source warehouse to another, given, destination warehouse.

From time to time, as well as at the end, an inventory check operation shall be run. It shall check that, for each product type, the total amount of that product in all warehouses is the same as in the beginning.

Two moves involving distinct warehouses, or involving disjoint sets of products, must be able to be processed independently (without having to wait for the same mutex).

2. Bank accounts

At a bank, we have to keep track of the balance of some accounts.

We have concurrently run transfer operations, to be executer on multiple threads. Each operation transfers a given amount of money from one account to someother account.

From time to time, as well as at the end of the program, a consistency check shall be executed. It shall verify that the total amount of money in all accounts is the same as in the beginning.

Two transaction involving distinct accounts must be able to proceed independently (without having to wait for the same mutex).

3. Summation with fixed structure of inputs

We have to keep the values of some integer variables. Some of them are primary variables; they represent input data. The others are secondary variables, and represent aggregations of some other variables. In our case, each secondary variable is a sum of some input variables. The inputs may be primary or secondary variables. However, we assume that the relations do not form cycles.

At runtime, we get notifications of value changes for the primary variable. Processing a notification must atomically update the primary variable, as well as any secondary variable depending, directly or indirectly, on it. The updating shall not re-compute the sums; instead, you must use the difference between the old value and the new value of the primary variable.

From time to time, as well as at the end, a consistency check shall be performed. It shall verify that all the secondary variables are indeed the sums of their inputs, as specified.

Two updates involving distinct variables must be able to proceed independently (without having to wait for the same mutex).

Bonus problem (+4p)

• move-next: given a pointer to the current element, get the pointer to the next
• move-prev
• insert-after: given a pointer to the current element and a value, create a new element with the specified value, link it just after the current element, and return a pointer to it
• insert-before

No central mutex shall be used. Operations involving far enough away elements shall be able to complete without having to aquire a common mutex. The linked list shall remain consistent and the result of calling any nummber of operations independently on distinct threads shall be the same as the result of calling the same operations in some sequencial order.