Efficient lock state transitions in a distributed system

Details Efficient lock state transitions in a distributed system Efficient lock state transitions in a distributed system

2001-03-01

2003-09-09

Oberley, Alvin (Department: 2126)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C709S226000, C709S229000, C707S793000

Reexamination Certificate

active

06618744

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a method and apparatus for lock caching, and more specifically, to a method and apparatus for using distributed resource objects to manage locks to control access to resources.
BACKGROUND OF THE INVENTION
Computers use resources, such as memory, modems and printers, during the execution of computer programs. Many of these resources are only used periodically by any given computer program. For example, the amount of time a word processing application requires a printer to print documents is typically small relative to the amount of time that the word processing application is used to create documents. If the only process that had access to the printer was a single word processing application, the printer would remain idle most of the time.
To take full advantage of resources, computer networks have been developed in which processes running on many computer devices or “nodes” can share resources. Thus, instead of having to purchase one printer for every computer, users may purchase a single printer that may be connected to a network that has many computers. Processes on each computer on the network access the printer only when the processes require the printer.
Even though resources may be shared, as described above, many resources may not be used by more than one process at any given time. For example, most printers are unable to print more than one document at a time. Other resources, such as data blocks of a storage medium or tables stored on a storage medium, may be concurrently accessed in some ways (e.g. read) by multiple processes, but accessed in other ways (e.g. written to) by only one process at a time. Consequently, mechanisms have been developed which control access to resources.
One such mechanism is referred to as a lock. A lock is a data structure that indicates that a particular process has been granted certain rights with respect to the resource. There are many types of locks. Some types of locks may be shared by many processes, while other types of locks prevent any other locks to be granted on the same resource.
FIG. 1
a
illustrates a hierarchy of lock modes that may be used to govern access to a table in a database.
At the lowest level in the hierarchy is a NULL mode lock
160
. Ownership of a NULL mode lock on a table grants a process no permission to access the table in any manner. Ownership of a concurrent read lock
158
grants a process permission to read the table, but does not guarantee that other processes are not concurrently writing to the table. Ownership of a protected read lock
154
grants a process permission to read the table and guarantees that no other process is concurrently writing to the table. Ownership of a concurrent write lock
156
grants a process permission to write to the table, but does not guarantee that another process is not also writing to the table. Ownership of a protected write lock
152
grants a process permission to write to the table and guarantees that another process is not also writing to the table. Ownership of an exclusive mode lock
150
grants a process permission to do anything with a table, and guarantees that no other process is performing any operation on the table.
Due to the various permissions and guarantees associated with these locks, certain lock combinations are not allowed. For example, if a process owns an exclusive mode lock on a resource, then no other process can be granted any lock other than a NULL mode lock. If a process owns a protected write lock, then no other process may be granted an exclusive mode lock, a protected write lock, a protected read lock or a concurrent write lock. If a process owns a protected read lock, then no other process may be granted an exclusive mode lock, a protected write lock or a concurrent write lock. If a process owns a concurrent write lock, then no other process may be granted an exclusive mode lock, a protected write lock, or a protected read lock. If a process owns a concurrent read lock, then no other process may be granted an exclusive mode lock.
A category of lock that may be held by more than one process at a time is referred to as a shared lock. For example, two processes can hold concurrent read locks on the same resource at the same time, so concurrent read locks are shared locks. For the purposes of explanation, the following description shall refer to exclusive mode locks, shared mode locks, and NULL mode locks.
Before a process can perform an operation on a resource, the process is required to obtain a lock that grants to the process the right to perform the desired operation on the resource. To obtain a lock, a process transmits a request for the lock to a lock manager. A lock manager is a process that is responsible for granting, queuing, and keeping track of locks on one or more resources. To manage the use of resources in a network system, lock managers are executed on one or more nodes in the network.
According to one prior art implementation, a lock manager implements two types of objects: a resource object and a lock. Resource objects are data structures that correspond to actual resources. An application that uses a lock manager establishes a mapping between actual resources and resource objects. Each resource object has two queues: a granted queue and a convert queue. The granted queue is an unordered list of locks that have been granted. The convert queue is a partially ordered list of locks that have been requested, but not yet granted. Typically, a request for a lock is actually a convert request, where a process holding a lock is requesting that the lock it holds be converted from one mode of lock to a different mode of lock.
Locks are data structures that identify a process and a lock mode. Lock managers attach locks to the grant queues of resource objects to indicate that the process identified in the lock has been granted a lock of the type indicated in the lock on the resource that corresponds to the resource object to which the lock is attached.
FIG. 1
b
is a block diagram illustrating a typical lock manager
106
. Lock manager
106
is a process that is configured to manage a resource object
100
stored in a memory
108
. The resource object includes a granted queue
102
and a convert queue
104
. Lock manager
106
has attached three locks
110
,
112
and
114
to the granted queue
102
, and one convert request
130
to the convert queue
104
.
All locks and convert requests have a process ID portion and a lock mode portion. The process ID portion
116
of lock
110
indicates that a process PROC_
1
owns lock
110
, and the lock mode portion
118
of lock
110
indicates that lock
110
is an exclusive lock. The process ID portion
120
of lock
112
indicates that lock
112
is owned by a process PROC_
2
, and the lock mode portion
122
of lock
112
indicates that lock
112
is a NULL mode lock. The process ID portion
124
of lock
114
indicates that lock
114
is owned by a process PROC_
3
, and the lock mode portion
126
of lock
114
indicates that lock
114
is a NULL lock. The process ID portion
132
of convert request
130
indicates that convert request
130
is associated with process PROC_
4
, and the lock mode portion
136
of convert request
130
indicates that PROC_
4
currently holds a NULL mode lock on the resource. In addition to a lock mode portion
136
, convert request
130
has a requested mode portion
134
that indicates that PROC_
4
is requesting an exclusive mode lock. Lock manager
106
has attached locks
110
,
112
and
114
to granted queue
102
, indicating that PROC_
1
currently has exclusive ownership of the resource that corresponds to resource object
100
. Lock manager
106
has attached convert request
130
to the convert queue
104
, indicating that PROC_
4
has requested but has not yet been granted an exclusive mode lock on the resource associated with resource object
100
.
Information pertaining to any given resource may be stored in the resource object that corresponds to the resource. Each resource object is stor

Affiliated with

Also associated with

Rating

Efficient lock state transitions in a distributed system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient lock state transitions in a distributed system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient lock state transitions in a distributed system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3087061