CS245A LAB #3
Due by 5pm, Tuesday, March 10, 1998.
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.


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:


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.


Possible Messages


Transaction started


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


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


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


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




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.