Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-05-01
2002-01-08
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C709S241000, C709S241000
Reexamination Certificate
active
06338063
ABSTRACT:
BACKGROUND OF THE INVENTION
1. The Field of the Invention
The field of the present invention is that of protecting critical segments of code in an environment where multiple streams of executable instructions may be operating through the critical segment. This occurs typically in multi-tasking operating systems and special structures known as “locks” are used to protect the critical code sections. Particularly, the present invention treats ways of reducing situations where a stream of executable instructions must “wait” on a lock or other protection mechanism that results in degraded system performance.
2. Present State of the Art
In an environment where multiple streams of executable instructions operate independent of one another, such as in a multi-tasking and multi-threaded operating system, certain operations must be performed by a stream of executable instructions to the exclusion of other streams of executable instructions. It is important in some instances to manipulate data in such a manner that only one processing thread operates thereon with no other stream of executable instructions disturbing the data until the operation is finished. For example, when updating a data structure that is common to the multiple streams of executable instructions, it is important that only one stream be making any modifications at a time or otherwise have write-access so that the integrity of the data structure is maintained. In some scenarios, read-access may occur while write-access must only occur in a protected mode.
One mechanism that is used to protect such critical areas of code is known as a “lock.” A lock must be held or acquired in order to proceed through the critical area or segment of code. After passing through the critical segment, the lock will be released and another executable stream may acquire or hold the lock. If one executable stream holds a lock and another attempts to access or acquire the lock that is already held, the second executable stream will in some way “wait” upon the lock until it is released by the first executable stream. Such waiting can cause degraded system performance, and it is desirable to reduce such waiting as much as possible.
Since the lock acts as a gate to allow only one stream of executable instructions to operate through a critical segment at any one time, many executable streams vying for a given lock can lead to “contention” for that lock. As a general rule, the more often a given lock needs to be accessed during the course of normal processing for a given application program or system having multiple streams of executable instructions, the greater the potential for lock contention.
A stream of executable instructions may wait on a lock in a variety of different manners depending on the system implementation and nature of the stream of executable instructions. For example, in the Windows NT operating system by Microsoft a stream of executable instructions may be a thread in user mode that will sleep upon encountering an unavailable lock that will in turn “awaken” when the lock later becomes available. As another example, in the Windows NT environment kernel mode operations on a multi-processor system will encounter “spin” locks that control access to common resources such as memory. Therefore, when a spin lock is encountered that is held by another stream of executable instructions on another processor, the encountering processor and stream of executable instructions will simply spin in place and be completely blocked from doing productive work until the spin lock is released.
One situation where lock contention may become a serious performance issue is where a common data structure representing a database known as a database or database structure contains objects that may be used by one of many different streams of executable instructions. Access to the database structure or a relevant portion of the database structure is controlled by a lock known as a “global lock.” This may be a global lock for the entire database structure or for a relevant portion thereof. For example, if employee record objects were contained in a database structure, 26 separate locks could be used to control relevant portions of the database structure based on the first letter of each employee's last name.
Objects may be created, placed in the database, and used as necessary by one or more streams of executable instructions. The objects may be deleted from the database structure and destroyed when they are not longer needed. Since the multiple streams of instructions may be simultaneously operating, a global lock is used to control access to the database structure when creating the object and inserting it into the database structure, searching the database structure to use the object, or removing the object from the database structure and destroying it as part of a delete operation.
Efficient programming techniques mandate that a global lock be held for the minimum of time possible in order to achieve the desired function in order to reduce lock contention amongst the different streams of executable instructions that may need relatively simultaneous access to the database structure. Additionally, a reference count is used to track the life cycle of a particular object. The reference count is initialized at creation to a value of one and will be incremented when a stream of executable instructions begins using the object and decremented when a stream of executable instructions is finished using the object. There will be a final decrementation of the reference count when deleting the object so that the reference count value will be zero, signifying that the object is no longer in the database structure and thus can be used no longer. In other words, when an objects reference count reaches zero, the object will be destroyed.
FIGS. 1-4
show how conventional methods are used in a typical scenario that may result in excessive contention for a global lock.
FIGS. 1-3
are flow charts corresponding to the operations of creating and placing an object in a database structure, using an object, and removing an object from a database structure and destroying it, respectively, while
FIGS. 4A-4F
show the creation, placement in a database structure, use, removal from a database structure, and destruction of two objects according to the flow charts in
FIGS. 1-3
.
Referring to
FIG. 1
, a flow chart showing the processing steps taken by a stream of executable instructions, such as a process thread, to create an object and place it in a database structure are shown. After beginning processing at step
20
, the object is allocated at step
22
with any necessary storage requirements. One variable associated with the object is a reference count or ref count that will track the life of the object. As long as the reference count value is not zero, the object will not be destroyed since it has not been deleted or, if deleted, a stream of executable instructions is still processing the associated object.
The object will be initialized into a known state and the reference count assigned a value of one at step
24
. At this point, the object is ready to be inserted into the database or database structure, such as a tree structure, queue structure, linked list structure, etc.
At step
26
, the global lock is acquired, thereby blocking any other stream of executable instructions from interfering with the insertion operation. The object is inserted into the database at step
28
. This must be done while the global lock is held so that pointers in a linked list or other data structure will not be inadvertently corrupted or read before they are in a stable condition. Finally, the global lock is released at step
30
and processing for the insertion operation ends at step
32
.
Referring now to
FIG. 2
, processing steps taken by a stream of executable instructions for using an object located in a database or database structure are shown. Processing begins at step
34
and the global lock is acquired at step
36
in order to access the database containing object.
At step
38
, the d
Alam Hosain T.
Microsoft Corporation
Workman & Nydegger & Seeley
LandOfFree
Method and computer program product for reducing lock... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and computer program product for reducing lock..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and computer program product for reducing lock... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2870586