LockGranularity

Granularity of locks

• Concurrency vs Overhead
• => Different granularities coexist

Hierarchical locks

• Exclusive/shared access
  • assign same lock implicitly to descendants
• Intention mode
  • lock all ancestors
• To lock
  • lock all ancestors in intention mode and lock self
  • requested root to leaf, released leaf to root
• Compatible
  • two lock requests can be granted concurrently

    	NL	IS	IX	S	SIX	X
    NL	YES	YES	YES	YES	YES	YES
    IS	YES	YES	YES	YES	YES	NO
    IX	YES	YES	YES	NO	NO	NO
    S	YES	YES	NO	YES	NO	NO
    SIX	YES	YES	NO	NO	NO	NO
    X	YES	NO	NO	NO	NO	NO

DAG Lock

• Requesting S or IS
  • should request at least one parent in IS (or greater)
• Requesting IX, SIX or X
  • should request all parents in IX (or greater)

Dynamic DAG

Scheduling and granting requests

• Granted group: From |IS| … |IS|
• Next request: S -> Next group

Conversions

• One request in a queue may request conversion
  • Must wait for other requests in the same group to be compatible
  • Other request my convert too => dead lock

Consistency

• Degree 2: might read 2 different values for the same key(?)
  • 2 transactions might be finished while Deg2 transaction is running