LOCKABLES A lockable is a node that can have a lock applied against it. It is organized in a hierarchical relationship tree. There is one tree for the whole system. A lockable looks like: struct lockable; typedef struct lockable IML_L; struct lockable { IML_L *parent; /* our parent locakable*/ IML_L *sibling; /* sibling lockable(s), if any*/ IML_L *child; /* child lockable(s), if any*/ IML_LOCK *locks; /* locks that are held*/ IML_LOCK *waits; /* locks that are waiting*/ unsigned long nesting_lvl; unsigned long flags; }; The lockable tree is a DAG (Directed Acyclic Graph); see FIG 1. o |^ ||<------------------. || ^ ^ | v| | | | o --> o --> o --> o --> null |^ |^ ||<----. || || | || v| | v| o --> o --> null o --> null FIG 1. A lockable tree LOCK ENTITIES A lock entity is a node for holding locks and entity relationships. An entity is considered related to another entity if it operates in the same competition domain. That is, if a lock held by one entity is equivalent to the lock being held by another entity, those entities are said to be related. One example of related entities is multiple kernel threads within a single process. Another example is stack and async operation context for an async calll gate. Effectively, an entity is a a scheduling unit. Relationships between entites are simple. In practice, entity relationships are represented by a relationship vector. The vector is connected through siblings. It is organized as a singly linked list, with the sibling pointer of the last element pointing to the first. Since entities are associative within a vector, the vector may be traversed starting with any entity, and ending with the entity that preceeds the first entity in the list. A lockentity looks like: struct lockentity; typedef struct lockentity IML_E; struct lockentity { IML_E *sibling; /* entites with a relationship to us*/ IML_LOCK *locks; /* the list of locks we hold*/ }; The lockentity vector is a DCG (Directed Cyclic Graph) that can be simplified to a DAG at the time it is examined; see FIG 2. ,--> o --> o --> o --. `-----------------------' FIG 2. A lockentity vector LOCK INSTANCES A lock instance is a node for defining bot a lock vector through an entity and a lock vector through a lockable. A lock instance looks like: struct locklock; typedef struct locklock IML_LOCK; struct locklock { IML_E *entity; /* the entity that applied the lock*/ IML_L *lockable; /* where the lock was applied*/ IML_LOCK *enextlock; /* the next lock by the entity*/ IML_LOCK *lnextlock; /* the next lock on the lockable*/ unsigned long mode; /* the mode of this lock*/ }; The lock vector describes a geodesic through the relationship graphs of both lockables and lock entites. Lock vectors must, by definition, be two dimensional DAG's describing a list of entites in one axis, and a list of lockables in the orthogonal axis. Like the lockentity vector, the lockable is a DCG that is simplified to a DAG at the time it is examined (such simplification does not change its connectedness); see FIG 3. ,--------. | | | v | o | | | v | ,--> o --> o --> o --. | `----+------------------' | v | o | | | v | o | | `--------' FIG 3. A lock vector describing a relationship of 6 locks between 3 entities and 4 lockables held by one entity and 1 lock held by each of the other 2 entities. DEADLOCK AVOIDANCE A deadlock is said to be detected whienever there is a cycle in the overall graph, which has a minimum of three and a maximum of six dimensions. To better illustrate this, consider a two dimensional lock graph with two entities in the same competition space; see FIG 4. entities o o o o o o o o o o | | |\ | ^\ /| |\ | |\ | | | \ | #1| /\ |#2 | \ | | \ v v v vv |v vv v vv v v lockables o o o o o o o o o o (A) (B) (C) (D) (E) FIG 4. Both entities want to lock both lockables. (A) Each entity has initially acquired one lock. (B) The first entity _intends_ to acquire the second lock, and waits on acquisition. (C) The second entity _intends_ to acquire the first lock. There are now two routes between the second entity and the second lock (a cycle). (D) The request is failed with EDEADLOCK. (E) The second entity backs off state, waiting on an acquisition of the first lock; the first entities request is satisfied and it runs to completion. The difference between intent and assertion is that the intention is not coelesced. Because it is not coelesced, it can be backed off without a stack rewind, and the second entity can wait on acquisition of its entire vector instead of just subelements. In this way, it is possible to avoid stack rewind, replay, and starvation. References: Algorithms in C++ Robert Sedgewick Addison-Wesley Publishing Company ISBN 0-201-51059-6 The Art Of computer Programming _Volume 1: Fundamental Algorithms_ Donald Knuth Addison-Wesley Publishing Company ISBN 0-201-03809-9 UNIX Systems for Modern Architectures _Symmetric Multiprocessing and Caching for Kernel Programmers_ Curt Schimmel Addison-Wesley Publishing Company ISBN 0-201-63338-8 Getting a Lock on Integrity and Concurrency C. M. Saracco, Charles J. Bontempo Database Programming & Design URL: http://www.dbpd.com/saracco.htm Weili Yao's algorithm Weili Yao Journal of Information Sciences URL: http://www.cs.ndsu.nodak.edu/~perrizo/classes/766/b3.html Deadlock, Resource trajectories, the Banker's algorithm URL: http://gatsby.lit.tas.edu.au/ostheory/html/deadlock.htm CIS 307: Deadlocks ingargio URL: http://joda.cis.temple.edu/~ingargio/old/cis307f96/readings/deadlock.html Note: the Banker's Algoritm; better pictures. IMAGE/SQL: Issues and Answers Concerning SQL Tables _What is Intention Locking?_ URL: http://jazz.external.hp.com/training/sqltables/c5s17.html