Lab #2

CS245A LAB #3
Due by 5pm, Tuesday, March 10, 1998.
100pts

Your third and last programming lab is to write lockmgr, a program that simulates a lock manager. To simplify the assignment, and to focus on database concepts, your program will not be in a concurrent environment. Instead, the program will receive lock requests from stdin, and will output text describing the outcome of those requests to stdout. In the next two sections, we will describe the input and the output of the program.

Input

Each line of the input is a request to the lock manager. Each request may contain a transaction ID (transID), which is an ASCII representation of a number between 0 and 255; and an object name (object) which is an alphanumeric string of at most 10 characters. Following are the possible requests and their formats:

ST transID: starts a transaction with id transID.

EN transID: ends the transaction with id transID. When this request is received, your program should release all locks held by transID as well as cancel any outstanding requests for locks.

SL transID object: transaction transID is requesting a shared lock on object. There are two possible outcomes for this request, the lock is either granted or the transaction is put in the waiting list for the lock.

XL transID object: transaction transID is requesting an exclusive lock on object. As in the previous case, the lock would be granted or the transaction must wait. This request can be issued by a transaction that wishes to upgrade a lock from share to exclusive.

UO transID object: transaction transID releases its lock on object. After releasing the lock, it should be granted to a waiting transaction (if any). You can define your own policy for granting locks (FIFO, LIFO, random, etc.); but you should justify your decision in the documentation (remember to consider the case of a transaction that upgrades a lock from shared to exclusive).

Output

The output for each request will start with the request being considered, followed by a colon and one or more messages. In the following table we present a list of possible messages for each request. You can change the format of the messages or add extra messages if you want.

Request

Possible Messages

ST

Transaction started

SL

Lock granted
Waiting for lock (X-lock held by: <trans_ID>)

XL

Lock granted
Upgrade to XL granted
Waiting for lock (S-lock held by: <transID > . . . < transID>)
Waiting for lock (X-lock held by: <trans_ID>)

EN

Transaction ended
Lock released
Lock granted to <transID > . . . < transID>

UO

Lock released
Lock granted to <transID > . . . < transID>

Request	Possible Messages
ST	Transaction started
SL	Lock granted Waiting for lock (X-lock held by: <`trans_ID`>)
XL	Lock granted Upgrade to XL granted Waiting for lock (S-lock held by: <`transID` > . . . < `transID`>) Waiting for lock (X-lock held by: <`trans_ID`>)
EN	Transaction ended Lock released Lock granted to <`transID` > . . . < `transID`>
UO	Lock released Lock granted to <`transID` > . . . < `transID`>

You may assume that the schedule that is sent to the lock manager is legal and well-formed. Also, no requests (except EN) will be made for a transaction that it is waiting for a lock.

Sample Input and Output

Input

Output

ST1

ST 1 : Transaction 1 started

ST 2

ST 2 : Transaction 2 started

SL 1 A

SL 1 A: Lock granted

XL 2 A

XL 2 A: Waiting for lock (S-lock held by: 1)

UO 1 A

UO 1 A: Lock released
X-Lock granted to 2

XL 1 B

XL 1 B: Lock granted

XL 2 B

XL 2 B: Waiting for lock (X-lock held by: 1)

XL 1 A

XL 1 A: Waiting for lock (X-lock held by: 2)

EN 1

EN 1 : Transaction 1 ended
Release X-lock on B
X-Lock on B granted to 2

UO 2 A

UO 2 A: Lock released

EN 2

EN 2 : Transaction 2 ended

Input	Output
ST1	ST 1 : Transaction 1 started
ST 2	ST 2 : Transaction 2 started
SL 1 A	SL 1 A: Lock granted
XL 2 A	XL 2 A: Waiting for lock (S-lock held by: 1)
UO 1 A	UO 1 A: Lock released X-Lock granted to 2
XL 1 B	XL 1 B: Lock granted
XL 2 B	XL 2 B: Waiting for lock (X-lock held by: 1)
XL 1 A	XL 1 A: Waiting for lock (X-lock held by: 2)
EN 1	EN 1 : Transaction 1 ended Release X-lock on B X-Lock on B granted to 2
UO 2 A	UO 2 A: Lock released
EN 2	EN 2 : Transaction 2 ended

Data Structures and Algorithms

For your program, you need to implement a lock table. You can use the implementation outlined in class or make your own design. In any case, your lock table will reside in memory and will contain information for every outstanding lock in the system. The minimum information that you should maintain is: which transactions have the lock and in which mode; as well as which transactions are waiting for the lock.

For extra credit, after processing a request for an exclusive or share lock your program can report any deadlocks (it does not need to prevent or solve them). For example, in the sample input above, a deadlock is created after processing XL 1 A ; at that moment, your program can print a message like ``Deadlock detected (involving transactions: 1 and 2)''. For your deadlock detection algorithm, do not reinvent the wheel: use an algorithm that detects cycles in a graph from a textbook.

Documentation and Grading

Each student is expected to submit a 1 page description of your design and algorithms in a plain text file called lockmgr.doc, and to include comments in the code. The grade of your program will be based on three aspects: Functionality - that the program correctly implements the specifications. Quality - elegant design and modularity. Documentation - as described above.