Exercise: Locks

For today’s in-class exercise, you’ll get some experience using both coarse- and fine-grained locking to solve problems in a oncurrent program. We’ll be using a common motivating example for locks: a program the models a simple bank. Read about how the bank application works, and follow the steps below to correct its implementation. We will complete today’s exercise in randomly-assigned groups. You do not need to turn anything in for this exercise, but it will help you prepare for our labs this week.

Starter Code and Introduction

One member of your group should go to https://gpu.cs.grinnell.edu and log in with your Grinnell account. Start an XFCE session, and launch a terminal. Run the following commands to get a copy of the starter code for this exercise and open it in VSCode:

              $ mkdir -p ~/csc213/exercises
$ git clone /home/curtsinger/csc213/exercises/bank ~/csc213/exercises/bank
$ code ~/csc213/exercises/bank

            

Review the code provided with this exercise. Here’s a quick overview of what you’ll find in each file:

Makefile: This file specifies the process for building the example program from source. Run make in the terminal to build the project.
main.c: This file implements some testing code for the bank implementation. The test creates a thread for each account at the bank, and then performs a series of random transactions on that account. You should not modify this file, but you are welcome to read through it to see how the bank interface is used.
bank.h: This file declares the interface for the bank application. We see four important functions: bank_init initializes the starting balances for each account; get_balance checks the balances for a given account (identified by an ID number); deposit adds funds to an account in the bank from some outside source; and finally transfer moves funds from one account to another at the bank. You should not modify this file, but you will be updating the implementations of these functions.
bank.c: This is where all of the bank functions are implemented. You will be adding code to this file to fix the problems with the bank. You should review the implementation of each function in this file (including the comments). Make sure you understand these functions before you move on.

Now that you have reviewed the starter code, we’ll discuss the higher-level structure of the program. The code in main.c starts each account off with a balance of 100, then performs a series of random transfers to other accounts. At the end of the run, the program prints the balance of each account. The test code only moves funds around within the bank, so while we expect the individual accounts to change balance during the test, the total funds at the bank should not change during the test. As you’ll see if you run this test a few times, the bank as currently implemented does not work correctly; the bank sometimes gains funds out of thin air, and other times will misplace funds with no obvious explanation. We’ll be looking into these issues during today’s exercise.

Part A: Diagnosing the Problem

Work with your partner to answer the following questions. You will need to review the code for today’s exercise, and you may find it helpful to review the assigned reading for class today.

One important detail from the reading that you should keep in mind is that a single C statement may require several operations to execute. For example, the statement x += 10 requires three separate operations by the processor:

Load the value of x into a temporary location (a register)
Add 10 to that same temporary location
Store the value from the temporary location to the storage location of x.

For the following questions, consider a scenario where two transfers happen at the same time, one from account A and one from account B. These transfers happen in different threads, so their individual events can interleave in many possible ways. You will have to decide where each transfer is going; A and B can transfer to each other, to a third common account, or to two distinct accounts.

For example, if A and B are both transferring 100 to account C, we may see this interleaving, where simultaneous events appear on the same line:

              // Remove funds from account A       // Remove funds from account B
tmp1 = accounts[A].balance;          tmp2 = accounts[B].balance;
tmp1 = tmp1 - 100;                   tmp2 = tmp2 - 100;
accounts[A].balance = tmp1;          accounts[B].balance = tmp2;

// Add funds to account C
tmp3 = account[C].balance;
tmp3 = tmp3 + 100;
accounts[C].balance = tmp3;          // Add funds to account C
                                     tmp4 = accounts[C].balance;
                                     tmp4 = tmp4 + 100;
                                     accounts[C].balance = tmp4;

            

The scenario and interleaving above do not pose a problem; both A and B finish with 100 less in funds, and C finishes with an additional 200 in funds.

Describe a scenario that will cause the bank to lose funds. Identify the specific interleaving of operations between the two transfers.
Describe a scenario that will cause the bank to gain funds. Identify the specific interleaving of operations between the two transfers.
Can you identify any sequences of operations that will need to execute atomically to ensure the bank will not misplace or gain funds?

Once you have answered these questions, move on to the next part. If you are unsure of your answers you can check them with the instructor or a class mentor.

Part B: Fixing the Problem

Using your answers from part A, use a single global lock (pthread_mutex_t) to enforce atomicity. To make a sequence of steps atomic, acquire the lock at the beginning, then release it at the end; this ensure that any other sequence of steps that executes while holding the lock will not interleave with this sequence. We typically say that these operations have been serialized; one occurs entirely before the other.

Once you have create your single global lock and placed lock and unlock operations, your bank should always finish with the correct total balance. Answer the following questions about your solution:

Does your single global lock serialize any operations that could have run concurrently? Identify a specific case.
What might be bad about serializing operations that could have run concurrently? Describe a specific problem that could arise.

Once you have answered these questions, move on to the next part. If you are unsure of your answers you can check them with the instructor or a class mentor.

Part C: Fine-Grained Locking

Now that you have identified at least one scenario where your global lock is causing a problem, it’s time to implement a fine-grained locking scheme. Instead of one global lock, you’ll associate a lock with each account. Keep these requirements in line as you update your implementation to use multiple locks:

You must initialize mutexes before you use them. You will need to call pthread_mutex_init to do this.
Don’t forget to unlock mutexes when you are done with them. It’s easy to mistakenly call pthread_mutex_lock twice on the same lock, which will freeze your program.
If your implementation acquires more than one lock at a time, there is a possibility of deadlock. You can prevent deadlock by always acquiring locks in a consistent order.
Your implementation should never lose or gain funds, just like the version that used a global lock.

Once you have your implementation, move on to part D if you have time. If you are unsure of your work, ask the instructor or a class mentor to check it.

Part D: Extra Challenge (if there’s time)

There are (at least) two good strategies for implementing fine-grained locking, but each has its own drawbacks. One approach maintains a useful invariant: any time locks are released, the bank’s total balance is consistent. Consider a scenario where the bank may be audited any time the account locks are available. Would your implementation from part C pass that audit? If not, how could you adjust your implementation to pass such an audit?