Lock Manager in C++ (500points)

Posted on 2006-04-18
Last Modified: 2013-12-03
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
begin  1
xlock  1   3
read  1   3
write  1   3
begin  2
slock  2   4
read  2   4
begin  3
slock  3   6
read  3   6
unlock  3   6
commit  3
xlock  2   3
read  2   3
write  2   3
xlock  1   4
read  1   4
write  1   4
unlock  1   3
unlock  1   4
commit  1
unlock  2   4
unlock  2   3
commit  2

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

Implementation Details
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
      Waiting Queue

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.

C++ Implementation
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.
Question by:Abdullahfa
    LVL 1

    Expert Comment


    Author Comment

    (pcgabe) there isn't any relevant info on this page you give me
    LVL 30

    Expert Comment

    What exactly is your question?
    Be advise, that it's against EE rules to do homework questions.
    We can help you with specific questions or your existing code, but we can't do the work for you.
    LVL 1

    Accepted Solution

    "Be honest about your purpose

    The Experts won't do your homework for you; they can be suspended for it, and so will you. If you have homework, and don't understand part of it, be honest about it. The Experts will be more than happy to teach you. But asking them to do your homework is the equivalent of asking someone to take an exam for you, and will be met with similar disfavor."

    "...academic honesty or other unethical behavior...

    Most commonly, this means that Experts are prohibited from doing your homework for you. They'll guide you and teach you, but don't ask them to write code to answer a question that seems like it was written for a test. It should be noted that just like bribery, while it's bad to offer a bribe, it's worse to take it -- so don't do homework.

    "Homework" is loosely defined as an assigment, project or quiz offered up an instructor of a technical, trade or eductional institution as part of a scheduled course of instruction, for which the student receives some kind of credit. The Moderators know what homework looks like, and it will be your task to convince them it isn't."

    Featured Post

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Join & Write a Comment

    Article by: SunnyDark
    This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
    Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
    The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
    Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…

    746 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    16 Experts available now in Live!

    Get 1:1 Help Now