Page 5: Tree Protocol

When You Know Access Pattern in Advance

Like following a family tree - you can only access children after accessing parents.

Tree Protocol Rules:

1. First lock can be on any item

2. To lock item Q, its parent must already be locked

3. Can unlock anytime

4. Once unlocked, cannot relock the same item

Example Tree:

Copy      A
    /   \
   B     C
  / \   /|\
 D   E F G H

Valid Sequence:

• T10: Lock(B) → Lock(E) → Lock(D) → Unlock(B) → Unlock(E) → Lock(G) → Unlock(D)

Benefits:

• ✅ Deadlock-free

• ✅ Earlier unlocking possible

• ❌ May need to lock unnecessary items