-------------------------------------------------------------------------------- LAB 5 | Tree protocol, deadlocks. -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- PRACTICE EXERCISES -------------------------------------------------------------------------------- (1) Get familiar with the terms: - deadlock, - wait-for graph, - wait-die and wound-wait deadlock prevention protocol, - tree protocol, by attending the lecture and reading chapters 15.2, 15.1.5 from the textbook. (2) Give a simple example of a schedule consisting of two transactions that results in a deadlock and can be output of a two-phase locking scheduler. In the schedule include the operations for requesting and granting locks (for example: 'R:lock-X(X)', 'G:lock-X(X)', where 'R' - lock requested, 'G' - lock granted). (3) Consider the following two transactions. T1: T2: read(X) read(Y) read(Y) read(X) if X=0 then Y:=Y+1 if Y=0 then X:=X+1 write(Y) write(X) (a) Show a concurrent schedule of T1 and T2 that results in a deadlock. Show also the evolution of the wait-for graph. (b) What would happen to the transactions according to the wait-die and wound-wait deadlock prevention protocols? (4) Consider the following schedule. (a) Add all granted locks and lock requests according to the two-phase locking with lock conversion. Is there a deadlock? (b) If yes, how can it be resolved? (c) What would happen to the transactions according to the wait-die and wound-wait deadlock prevention protocols? T1: T2: T3: read(X) write(X) read(X) write(X) write(X) (5) Consider the following schedule. T1: T2: read(X) write(Y) read(Y) (a) Is this schedule possible under the tree protocol if the order of data items is X->Y? If yes, add lock and unlock instructions. (b) Is this schedule possible under the tree protocol if the order of data items is Y->X? If yes, add lock and unlock instructions. (6) FURTHER READING: - 'Deadlocks' in PostgreSQL documentation [1]. - 'pg_locks' view in PostgreSQL [2]. (7) CHECKLIST: - I can explain what is a deadlock and show it on an example schedule. - I can verify the occurrence of a deadlock in a schedule. - I can list and explain the methods for preventing deadlocks. - I can explain what is a tree protocol and apply it on an example schedule. -------------------------------------------------------------------------------- HOMEWORK -------------------------------------------------------------------------------- DEADLINE: 12.12.2016, 21:59 In this exercise we will try various isolation levels for eating cookies. Consider the script 'cookie_jar_h5.py'. Your task is to add a support for specifying isolation levels from the command line. The chosen isolation level will be used for every monster. You have to find the correct place in the code to set the isolation level. Setting an isolation level is done with a command-line option: '--transaction-isolation-lavel' or '-l' The possible allowed choices are: 'READ UNCOMMITTED', 'READ COMMITTED', 'REPEATABLE READ', 'SERIALIZABLE' Setting an isolation level can be done with [3] (tested by me): conn.set_session(isolation_level=) or with [4]: conn.set_isolation_level() IMPORTANT: The isolation level has to be added to the output in the function 'summarize_eating'. Modify the first line of that function to: result = ('{"e" : "%s", "m" : %d, "c" : %d, "l" : "%s",' % (args.eating_transaction_mode, args.num_monsters, args.num_cookies, args.transaction_isolation_level)) For the evaluation, I will execute your script with varying parameters. We'll discuss the results of your script during the labs. -------------------------------------------------------------------------------- REFERENCES -------------------------------------------------------------------------------- [1] https://www.postgresql.org/docs/current/static/explicit-locking.html [2] https://www.postgresql.org/docs/current/static/view-pg-locks.html [3] http://initd.org/psycopg/docs/connection.html#connection.set_session [4] http://initd.org/psycopg/docs/connection.html#connection.set_isolation_level