Submission Instructions
This is a team assignment.
Submit the following:
hw12/MultithreadedServer.java // Turn sequential starter code into a multithreaded one
hw12/Account.java // You are not permitted to modify this class
hw12/constants.java // You are not permitted to modify this class
hw12/test/MutlithreadedServerTests.java // Add JUnit tests to starter ones
hw12/data/datafiles // Add data files for testing, in addition to files increment and rotate
Keep the above directory structure as introduced by the starter code. From parent directory of hw12, run zip hw12.zip –r hw12 then submit hw12.zip in Submitty for autograding. The autograder will become available around Monday, December 3rd.
Due to Michael Scott
For this homework assignment you will construct a parallel transaction server. To keep the assignment manageable we will build a simple, stylized server that captures the concurrency aspects of the problem domain while avoiding the complexity of Internet communication, database access, logging, fault tolerance, etc.
The bulk of the homework asks to modify MultithreadedServer.java to turn the sequential server into a multithreaded one. In files MultithreadedServer.java and Account.javayou will find the code for the sequential server. Read carefully through file MultithreadedServer.java as it contains TODO notes and additional explanation.
The server operates on an array of 26 “accounts”, named ‘A’ through ‘Z’, which it modifies according to a sequence of transactions, specified one per line. These transactions have the following form:
input | –> | transaction input |
–> | ||
transaction | –> | command more_commands \n |
more_commands | –> | ; command more_commands |
command | –> | account = val val_tail |
account | –> | capital_letter indirects |
indirects | –> | * indirects |
–> | ||
val | –> | account |
–> | integer | |
val_tail | –> | + val |
–> | – val |
Tokens other than semicolon and newline (\n) must be surrounded by white space.
Each command sets the account specified by the left-hand side to the value specified by the right-hand side. For example, the following transaction transfers ten units from account B to account A, atomically:
A = A + 10; B = B – 10
If the letter name of an account is followed by a star, then the value in the account, modulo 26, is interpreted as a reference to another account—kind of a weird variety of pointer. The significance of indirection for this assignment is that transactions are dynamic: they can’t tell up front what accounts they are going to need; they may have to access one or more accounts before figuring out what others will need to be accessed. Suppose, for example, that account Q contains the value 37, account L contains the value 5, and account F contains the value 9. Then the transaction
A = Q**; B = A + A*
will work as follows: Q* has the value 5 (because 37 == 11 mod 26, and L is the 11th letter of the alphabet, counting from 0), and then Q** has the value 9 (because F is the 5th letter of the alphabet, counting from 0). So we assign 9 into A. Then since J is the 9th letter of the alphabet, counting from 0, we take the value in J, add 9 to it, and put the result in B.
Note that the commands within a transaction have to be executed in order, but the transactions in the input do not. This is perfectly normal, and happens all the time in real life. If there is only one concert ticket left and I buy it, then you can’t, and you may choose to do something else on Saturday night. Moreover if we both try to buy that last ticket at about the same time, which one of us “wins” may depend on such artificial factors as Internet delay or temporary conflicts with other transactions.
To get you started, here are two very simple inputs, both with only one command per transaction. The first, hw12/data/increment, has no conflicts among transactions. A parallel server should execute it very quickly. The second, hw12/data/rotate, has a great many conflicts; it presents more of a challenge. You can write a solution that still executes it faster than the sequential version does. Note that the code we are giving you prints a message for each commit or abort operation, so you can figure out whether your program is correct.
The Account class, which you are not permitted to modify, provides several public methods:
Account (constructor)
takes an initial value as argument. You’ll discover that the main program initializes the nth account to 26 − n.
peek
returns the value in an account.
verify
checks to see whether an account contains an expected value. You’ll use this to make sure that no other transaction has updated an account since you peeked at it.
update
sets an account to a new value.
open
secures the right to verify (read) or update (write) an account. Takes a boolean argument indicating which mode is desired.
close
relinquishes rights to verify and update the account.
prints the value of the account to standard output, in a wide (11-column) field.
prints the value of the account mod 26 to standard output, in a two-column zero-padded field. These last two methods are used by the dumpAccounts method of the main (Server) class to print debugging output.
You will find that each open, close, peek, verify, and update operation incurs a delay of 100ms. This is intended to simulate communication with a remote database. Given these delays, server performance will depend critically on the ability to work on more than one transaction at a time, so the delays can overlap. Use the Java 5 Executor mechanism to manage this concurrency. Each transaction should be represented by a task. With thenewFixedThreadPool factory you can specify the number of threads in the worker pool, to balance the performance advantage of concurrency against the performance overhead of extra context switches. Alternatively, you can simply use the newCachedThreadPool factory, which will create as many threads as are able to proceed concurrently.
Where the sequential version of the transaction server performs transactions sequentially, you should arrange for your concurrent version to be disjoint access parallel. That is, any two transactions that access no common accounts should be able to proceed without aborting or otherwise interfering with each other.
Of course if concurrent transactions access the same accounts, their updates may conflict with one another. Moreover because of indirection it’s impossible to tell in advance whether two transactions will conflict. I recommend (and the infrastructure you’ve been given supports) an optimistic strategy in which transactions proceed concurrently unless and until a conflict is discovered, at which point one of them must abort.
You are required to ensure that transactions are serializable; that is, that their overall effect is equivalent to that of an execution in which the transactions occur sequentially, one by one, in some order. To achieve this effect without deadlock you can implement two-phase locking, in which all a transaction’s open operations occur before any of its closes. The key to deadlock freedom in this scheme is to open all accounts in some canonical order (e.g. A through Z), to avoid any circular dependences. This in turn requires that a transaction figure out what it wants to do (including all indirections) before actually opening anything; hence the rule that peek must be called on an unopened account.
To support the implementation outlined above (i.e. to detect conflicts among transactions, and to encourage you to cache peeked-at and to-be-written values), the Account class enforces certain access rules:
Remember: you are not permitted to modify Account.
In addition to MultithreadedServer.java, create new transaction files in hw12/data/ and add JUnit tests to hw12/test/MultithreadedServerTests.java. We will grade for white-box coverage expecting at least 80% statement (block) coverage of Account.java and MultithreadedServer.java.