DLM Locking Model
This chapter presents a detailed study of the general locking model of Distributed Lock Managers including lock resources, lock modes, lock states, lock queues, and various other aspects of the model. The next chapter explains the Leases approach towards maintaining consistency of resources.
A lock resource is the lockable entity. An application acquires a lock on a lock resource. A one-to-many relationship exists between lock resources and locks: a single lock resource can have multiple locks associated with it. A lock resource can correspond to an actual object, such as a file, a data structure, a database, or an executable routine, but it does not have to correspond to one of these things. The object you associate with a lock resource determines the granularity of the lock. For example, locking an entire database is considered locking at coarse granularity. Locking each item in a database is considered locking at fine granularity.
The following sections provide more information about:
• Lock resources, including lock value blocks and lock queues
• Locks, including lock modes and lock states
• Deadlock, including transaction IDs and lock groups.
3.1. Lock Resources
The lock manager creates a lock resource in response to the first request for a lock on that lock resource. The lock manager destroys the internal data structures for that lock resource when the last lock held on the lock resource is released.
A lock resource has the following components:
- A name, which is a string of no more than 31 characters
- A lock value block
- A set of lock queues
Fig. 3.1. Components of a lock resource
3.1.1. Lock Value Block
The lock value block (LVB) is a 16-byte character array associated with a lock resource that applications can use to store data. This data is application-specific; the lock manager does not make any direct use of this data. The lock manager allocates space for the LVB when it creates the lock resource. When the lock manager destroys the lock resource, any information stored in the lock value block is also destroyed.
3.1.2. Lock Resource Queues
Each lock resource has three queues associated with it, one for each possible lock state.
Grant Queue
The grant queue contains all locks granted by the lock manager on the lock resource, except those locks converting to a mode incompatible with the mode of a granted lock. The lock manager maintains the grant queue as a queue; however, the order of the locks on the queue does not affect processing.
Convert Queue
The convert queue contains all granted locks that have attempted to convert to a mode incompatible with the mode of the most restrictive currently granted lock. The locks on the convert queue are still granted at the same mode as before the conversion request. The lock manager processes the locks on the convert queue in "first-in, first-out" (FIFO) order. The lock at the head of the queue must be granted before any other locks on the queue can be granted.
Wait Queue
The wait queue contains all new lock requests not yet granted because their mode is incompatible with the mode of the most restrictive currently granted lock. The lock manager processes the locks on the wait queue in FIFO order.
3.1.3. Locks
Clients can request a lock from the lock manager on any lock resource. Locks have the following properties:
A mode that defines the degree of protection provided by the lock
A state that indicates whether the lock is currently granted, converting, or waiting
3.2. Lock Modes
A lock mode indicates whether a process shares access to a lock resource with other processes or whether it prevents other processes from accessing that lock resource while it holds the lock. A lock request specifies a lock mode.
3.2.1. Lock Mode Severity
The lock manager supports six lock modes that range in the severity of their restriction. The following table lists the modes, in order from least severe to most severe, with the types of access associated with each mode.
Lock Mode Compatibility
Lock mode compatibility determines whether two locks can be granted simultaneously on a particular lock resource. Because of their restriction, certain lock combinations are compatible and certain other lock combinations are incompatible. For example, because an EX lock does not allow any other user to access the lock resource, it is incompatible with locks of any other mode (except NL locks, which do not grant the holder any privileges). Because a CR lock is less restrictive, however, it is compatible with any other lock mode, except EX.
The following table presents a mode compatibility matrix.
NL mode locks grant no privileges to the lock holder. NL mode locks are compatible with locks of any other mode. Applications typically use NL mode locks as placeholders for later conversion requests.
CR mode locks allow unprotected read operations. The read operations are unprotected because other processes can read or write the lock resource while the holder of a CR lock is reading the lock resource. CR mode locks are compatible with every other mode lock except EX mode.
CW mode locks allow unprotected read and write operations. CW mode locks are compatible with NL mode locks, CR read mode locks, and other CW mode locks.
PR mode locks allow a lock client to read from a lock resource knowing that no other process can write to the lock resource while it holds the lock. PR mode locks are compatible with NL mode locks, CR mode locks, and other PR mode locks. PR mode locks are an example of a traditional shared lock.
PW mode locks allow a lock client to read or write to a lock resource, knowing that no other process can write to the lock resource. PW mode locks are compatible with NL mode locks and CR mode locks. Other processes that hold CR mode locks on the lock resource can read it while a lock client holds a PW lock on a lock resource. A PW lock is an example of a traditional update lock.
EX mode locks allow a lock client to read or write a lock resource without allowing access to any other mode lock (except NL). An EX lock is an example of a traditional exclusive lock.
Figure 3.2 shows the modes in descending order from most to least severe. Note that, because CW and PR modes are both compatible with three modes, they provide the same level of severity.
3.3. Lock States
A lock state indicates the current status of a lock request. A lock is always in one of three states:
Granted: The lock request succeeded and attained the requested mode.
Converting: A client attempted to change the lock mode and the new mode is incompatible with an existing lock.
Blocked: The request for a new lock could not be granted because conflicting locks exist.
A lock’s state is determined by its requested mode and the modes of the other locks on the same resource.
The following figure shows all the possible lock state transitions.
3.3.1. Granted
A lock request that attains its requested mode is granted. The lock manager grants a lock if there are currently no locks on the specified lock resource, or if the requested mode is compatible with the mode of the most restrictive, currently granted lock, and the cut queue is empty. The lock manager adds locks in the granted state to the lock resource’s grant queue. Figure 5.4 illustrates the lock resource queues after some successful grants.
Fig. 3.4. If you request a CR mode lock on a lock resource, named RES-A, and there are no other locks, the lock manager grants your request and adds your lock to the lock resource’s grant queue. If the lock manager receives another request for a lock on RES-A at mode CR, it grants the request because the mode is compatible with the currently granted lock. The lock manager adds this lock to the lock resource’s grant queue.
Leaving the Grant Queue
A lock can leave the grant queue only if the owner makes a request to release it or if the process holding the lock terminates. The lock manager releases all locks owned by the process that terminates. By using flags to the lock open routines, however, you can specify that you want the locks you create on a lock resource to remain after your process
terminates. These locks are called orphan locks. If the orphan lock is on the grant queue, the lock manager leaves it there. If the orphan lock is on the convert queue, the lock manager puts it back on the grant queue at its old grant mode (its conversion request is canceled). If the orphaned lock is on the wait queue, the lock manager ignores its orphan-able state and removes it.
3.3.2. Converting
A lock conversion request changes the mode at which a lock is held. The conversion can promote a lock from a less restrictive to a more restrictive mode, called an up-conversion, or demote a lock from a more restrictive to a less restrictive mode, called a down-conversion.
Fig. 3.5. A request to convert the mode of a Lock1 from CR to PR is granted because it is compatible with the most severe granted lock. But a request to convert Lock2 from CR->CW is queued because it is not compatible the most severe granted lock, i.e. PR. Only granted locks can be converted. It is not possible to convert a lock already in the process of converting or a request that is blocked on the wait queue. The lock manager grants up-conversion requests if the requested mode is compatible with the mode of the most restrictive, currently granted lock, and there are no blocked lock conversion requests waiting on the convert queue.
A lock conversion request that cannot be granted transitions into a converting state. The lock manager moves locks that are in converting state from the grant queue to the end of the convert queue. Locks that are in the converting state retain the lock mode they held in the grant queue.
Once there is a lock on the convert queue, all subsequent up-conversion requests get moved to the convert queue, even if the requested mode is compatible with the most restrictive granted lock.
Leaving the Convert Queue
A lock can leave the converting state if any of the following conditions are met:
The process that requested the lock terminates.
The process that holds the lock cancels the conversion request. When a conversion request is canceled, the lock manager moves the lock back to the grant queue at its previously granted mode.
The requested mode becomes compatible with the most restrictive granted lock, and all previously requested conversions have been granted or canceled.
3.3.3. In-Place Conversions
The lock manager grants all down-conversion requests in-place; that is, the lock is converted to the new mode without being moved to the convert queue, even if there are other lock requests on the convert queue. The lock manager grants all down-conversions because they are compatible with the most restrictive locks on the grant queue (the lock was already granted at a more restrictive mode)
Conversion Deadlock
Because the lock manager processes the convert queue in FIFO order, the conversion of the lock at the head of the convert queue must occur before any other conversions on the convert queue can be granted. Occasionally, the lock at the head of the convert queue can be blocked by one of the other lock conversion requests on the convert queue. The lock at the head of convert queue blocks all the lock conversion requests on the convert queue. Thus, a deadlock cycle is created. Figure 3.7 illustrates one such scenario.
Fig. 3.7. Lock1 blocks Lockk2. Lock 1 cannot be granted because it is blocked by Lock 2, also on the convert queue and is still granted at CR mode, which is incompatible with EX mode. Thus, Lock 2 blocks Lock1 and Lock 1 blocks Lock
3.3.5. Blocked
If you request a lock and the mode is incompatible with the most restrictive granted lock, your request is blocked. The lock manager adds the blocked lock request to the lock resource’s wait queue. (You can choose to have the lock manager abort a request that cannot be immediately granted instead of putting it on the wait queue).
Leaving the Wait Queue
A lock can leave the wait queue if any of the following conditions are met:
The process that requested the lock terminates.
The requester cancels the blocked lock. When a blocked lock is canceled, the lock manager removes it from the wait queue.
The lock request becomes compatible with the mode of the most restrictive lock currently granted on the lock resource, and there are no converting locks or blocked locks queued ahead of the lock request. The lock manager processes the wait queue in FIFO order, after processing the convert queue. No blocked request can be unblocked by the release of a granted lock, regardless of the compatibility of its mode, until all blocked requests on the convert queue and all blocked requests ahead of it on the wait queue have been granted. Thus, a lock request can become blocked only as the result of a lock request, but it can unblock as a result of the release or conversion of some other lock.
Self-Client Deadlock
Self-client deadlock occurs when a single client requests a lock on a lock resource on which it already holds a lock and its first lock blocks the second request. For example, if Process P1 requests a lock on a lock resource on which it already holds a lock, the second lock may be blocked.
3.4. Transaction IDs
By canceling one of the requests causing a deadlock, the lock manager prevents clients contending for the same lock resources from blocking each other indefinitely. Additionally, the lock manager supports transaction IDs, a mechanism clients can use to improve application throughput by diminishing the impact of deadlock when it does occur.
When determining whether a deadlock cycle exists, the lock manager normally assumes the process that created the lock owns the lock. By specifying a transaction ID (also called an XID or deadlock ID) as part of a lock request, a lock client can attribute ownership of a lock related to a particular task to a "transaction" rather than to itself. For deadlock detection, therefore, a transaction replaces a process or group as the owner of a lock. Furthermore, transaction IDs allow different clients to request locks on the same transaction. A unique transaction ID should be associated with each transaction (task).
3.5. Lock Groups
A lock group joins related lock client processes into a single entity. A lock client may create a new lock group or join an existing group. A lock client may belong to, at most, one lock group. Once a client belongs to a group, the group owns all subsequent locks created by that process. Therefore, any process in the group may manipulate group-owned locks.
Alternatively, a process belonging to a lock group can pass a flag to a lock open routine to indicate that the process, not the group, owns this lock. Other processes belonging to the group may not manipulate this lock. The lock manager does not purge a lock owned by a group until all processes belonging to the group have exited or all processes have detached from the group. A lock group may not span cluster nodes. The lock manager only acknowledges a group ID on the node on which it was created. Therefore, a lock client on one node cannot join a group that was created on a different node.
Lock groups affect deadlock detection in the same way as transaction IDs.
0 comments:
Post a Comment
Thanks for your Valuable comment