Lock Manager in C++ (500points)
Posted on 2006-04-18
The following is a description of a Lock Manager (LM) for a hypothetical database with 6 data items; X1, X2, X3, X4, X5, X6. The lock manager does 2 main tasks:
• Manage locks: the LM should handle requests by transactions to lock\unlock
Data items (shared and exclusive).
o Keep track of data items and who's currently holding a lock on each of
o It should keep track of transactions waiting for a lock to be released.
LM should do that by keeping a waiting queue for each data item. The
Queue contains the transactions that are waiting on that lock and the types of their requests (shared or exclusive). Once a transaction
Releases a lock, the LM should grant the lock to the transaction that has been waiting the longest, i.e. the transaction at the beginning of the queue.
o If a transaction is holding a shared lock on a data item and another transaction requests a shared lock, the second transaction is granted the lock as well. If the second transaction requests an exclusive lock, it should wait in the queue of this data item.
o If a transaction is holding an exclusive lock on an item, any requests on locks on that data item are rejected and the requesting transactions are inserted in the queue in the order of their requests.
• Detect deadlocks: the LM should detect deadlocks. It should do that by constructing a WFG after every insert in the waiting queue and checking for cycles in it. If a cycle is found, the LM picks a transaction in the cycle and aborts it. The aborted transaction restarts after the rest of the transactions have committed. The LM should abort the deadlocked transaction that did the least number of writes.
The input the system should be a schedule of transactions with locks inserted before any read and write and unlocks inserted when a locks needs to be released. The input of the system should be a text file (.txt) where each line is in the following format:
Operation TransactionNum [DataItemNum]
Operation is the operation to be performed. It is one of the following:
• begin indicates the beginning of a transaction.
• slock indicates a request by a transaction to acquire a shared lock.
• xlock indicates a request by a transaction to acquire a exclusive lock.
• read indicates a read operation on a data item by a transaction.
• write indicates a write operation on a data item by a transaction.
• unlock indicates a release of a lock by a transaction.
• commit indicates a end of a transaction.
TransactionNum is the number of the transaction performing the operation. It is a non-negative integer.
DataItemNum is the number of the data item the operation is performed on. It is 1, 2, 3, 4, 5 or 6.
Sample Input Lines
begin 4 means that T4 has started.
slock 2 6 means that T2 is requesting a shared lock on X6.
write 20 3 means that T20 is writing X3
Sample Input File → input1.txt
xlock 1 3
read 1 3
write 1 3
slock 2 4
read 2 4
slock 3 6
read 3 6
unlock 3 6
xlock 2 3
read 2 3
write 2 3
xlock 1 4
read 1 4
write 1 4
unlock 1 3
unlock 1 4
unlock 2 4
unlock 2 3
1. All input is in lower-case.
2. You may assume that input is correct. E.g. if a transaction is reading an item, it
Already has the lock for that data item. You don't have to validate input.
Lm produces output in a file residing in the same directory as LM. The file should have the following name: result_X.txt
Where X is the input file name for which this output is produced. The system produces output in the following cases:
1. A transaction commits: when the system reaches the commit of a transaction successfully, a message indicating so is written to the output file result_X.txt
This file should reside in the current directory of the system. When T4 commits successfully, the following message is written to result_X.txt
transaction 4 is committed
2. A transaction acquires a lock: when a transaction requests a lock and it is granted this lock (either immediately or after waiting), a message that indicates so is written to the file: result.txt
If T10 requests a shared lock on X5 and granted this lock, the following message is written to result_X.txt
Transaction 6 is granted exclusive lock on X7
3. A transaction waits: if a transaction requests a lock that is held by another transaction, the transaction has to wait until the lock is released and a message the lock is held by some other transaction, the following message is written to result_X.txt
Transaction 10 is waiting for shared lock on X5
4. A transaction aborts: if Lm detects a deadlock and chooses its victim transaction, this transaction is aborted and later restarted. When the system decides to abort a transaction, it indicates so in result_X.txt. If T6 and T19 are in a deadlock and T6 has done less writes than T19, the system would abort T6 and will indicate this in result_X.txt by writing
DEADLOCK! transaction 6 is aborted
5. A transaction restarts: when a transaction is aborted, LM should restart it after waiting for the rest of the transactions to commit. On restarting, the system should write this fact in (result_X.txt) if T6 is restarted, the following should be written in (result_X.txt) when T6 is started again
transaction 6 is restarted
Sample Output File for input.txt → result_input1.txt
transaction 1 is granted exclusive lock on X3
transaction 2 is granted shared lock on X4
transaction 3 is granted shared lock on X6
transaction 3 is granted committed
transaction 2 is waiting for exclusive lock on X3
transaction 1 is waiting for exclusive lock on X4
DEADLOCK! Transaction 2 is aborted
Transaction 1 is granted exclusive lock on X4
transaction 1 is committed
transaction 2 is restarted
transaction 2 is granted shared lock on X4
transaction 2 is granted exclusive lock on X3
transaction 2 is committed
LM needs to implement a table in memory to keep track of data items and their locks.
The table would look something like this:
Data Item Transaction(s)
Holding Lock Lock Type
X1 T1, T4 S T3\X
X2 T2 X T5\X, T4\S, T9\S
X3 - -
X4 - -
X5 T2 X
X6 - -
Rules for Items in the Table
• A transaction cannot be in the queues of 2 different data items (why?).
• One transaction cannot be in the same queue twice.
• If lock type of an item is S, the first transaction in the waiting queue should not be requesting Slock (why?).
• If more than one transaction are holding a lock, then the lock type must be S.
Initially, the table consists of 6 rows; each is for a data element. The rest of the table is empty. As transactions request locks, the table gets filled. When a transaction requests a lock, it is either inserted in the Transaction Holding Lock column or in the Transaction. Holding Lock column and replaced by either nothing (if the corresponding queue is empty) or by the transaction at the beginning of the queue. At the end, the table is empty again.
Everything is a class in C++. Rows of the above table are of the same class. But since we have a limited number of data items, each of them will be a variable (no need for an array). The class representing the row will have 4 attributes. First attribute is a number from 1 to 6 indicating the data item number. Second attribute is an array of transactions holding the lock on this data item. Each transaction is a non-negative integer. Third attribute is a Boolean indicating the type of lock held on the data item.
Final attribute is another class; queue. Each element in the queue is a struct of transaction (non-negative integer) and a Boolean indicating the type of lock requested.
1- Implement the lock manager described above using C++, The program should be a windows 32 console application. Name your program LockMan. Your Program should take from the command line one argument which is the input file name. The output of your program is a text file named inputFileName_result.txt
Where inputFileName is the name of the input file without the extension. You need to follow the input\output format very carefully.