[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Lock Manager in C++ (500points)

Posted on 2006-04-18
4
Medium Priority
?
746 Views
Last Modified: 2013-12-03
Overview:
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
Them.
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.

Input
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

Notes
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.

Output
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.

Assignment
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.
0
Comment
Question by:Abdullahfa
  • 2
4 Comments
 
LVL 1

Expert Comment

by:pcgabe
ID: 16476863
0
 

Author Comment

by:Abdullahfa
ID: 16476960
(pcgabe) there isn't any relevant info on this page you give me
0
 
LVL 30

Expert Comment

by:Axter
ID: 16477002
Abdullahfa,
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.
0
 
LVL 1

Accepted Solution

by:
pcgabe earned 1500 total points
ID: 16477008
"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."
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
Suggested Courses

830 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