THINK FIRST·CODE LATER

← All labs

Concurrent bank transfers without deadlock

Problem

EdgeCampus keeps a "compute credit" account per research group. Transfers run concurrently on a thread pool; each transfer must lock both accounts, and must never deadlock.

Input: first line nAccounts nThreads; second line the initial balances of accounts 0…nAccounts−1; then transfers from to amount until the end of input (overdrafts are allowed; from ≠ to).

Requirements:

  • Use one ReentrantLock per account and an ExecutorService with nThreads threads; submit one task per transfer.
  • Each task locks the two accounts in increasing account number order (to prevent deadlock), moves the amount, unlocks in finally.
  • Wait for all tasks (shutdown + awaitTermination), then print account i: balance for every account, Total before: X, Total after: Y and Conservation: OK if equal, else Conservation: BROKEN, and Transfers: n.

Because every transfer is applied exactly once and addition is commutative, the final balances are deterministic even though the order of execution is not.

Input:

3 4
100 50 0
0 1 30
1 2 20
2 0 5
1 0 10

Output:

account 0: 85
account 1: 50
account 2: 15
Total before: 150
Total after: 150
Conservation: OK
Transfers: 4

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

os7-4-data-1.txt

3 4
100 50 0
0 1 30
1 2 20
2 0 5
1 0 10
What your program must print for os7-4-data-1.txt
account 0: 85
account 1: 50
account 2: 15
Total before: 150
Total after: 150
Conservation: OK
Transfers: 4

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < os7-4-data-1.txt

Windows PowerShell does not understand <:

Get-Content os7-4-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.