Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-06-23
2001-02-06
Homere, Jean R. (Department: 2777)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C711S150000, C711S151000
Reexamination Certificate
active
06185564
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related to computer systems for generating, managing and validating reference handles of consumers requiring access to resources.
2. Related Art
It is not uncommon for software modules operating on computer systems to require access to shared resources. For example, a given computer program may require access to files maintained by a file system, or it may require access to network connections maintained by a network driver. Network drivers may require access to information structures maintained by a network packet classifier. This is a complex arrangement that includes numerous software modules, such as software drivers requiring access to many shared resources and an access supervisor that either maintains the resources or at least intercedes in access by the software modules to the resource.
Such intercession exists for several reasons, one especially important reason being when a software module deletes a resource. If a first software module were to delete a first resource, while other software modules maintain direct pointers to the first resource, the pointers of the other software modules would be unaware of the deletion of the resource and would no longer point to a valid resource. Attempts have been made to solve this problem by notifying software modules when a resource deletion occurs. However, this requires detailed accounting and tracking of software modules and their respective pointers to the resources. As a result, this process is extremely expensive and very complex.
Another attempt to solve this problem involves having an access supervisor intercede when a software module requires access to a particular resource. Interceding ensures that the particular resource still exists before the software module is granted access to the particular resource. Typically, this is accomplished by having the access supervisor issue to each software module a handle to a particular resource, rather than allowing each software module a direct pointer to that particular resource. The software module does not use the handle to access the resource directly. Instead, the software module presents the handle to the access supervisor, which can dereference the handle to obtain a pointer to the resource for that software module. Although this approach allows the access supervisor to have control over the management of the shared resources, prior methods that follow this approach provide only rudimentary control, and thus have several limitations.
First, prior methods are inefficient, expensive and limited in their use because they lack constant-time operations, which is a problem when the number of simultaneously active handles is large. Also, the handle databases of prior methods have limited flexibility because they are not capable of growing and shrinking arbitrarily in an efficient manner. In addition, prior methods lack fast and efficient dereferencing and are ineffective in a multi-threaded environment. Further, prior methods lack efficient processes for recycling handles to increase handle space and to optimize the handle database. Therefore, what is needed is a computer-implemented system for generating and validating reference handles effectively and efficiently that overcomes these limitations.
Whatever the merits of the prior systems and methods, they do not achieve the benefits of the present invention.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention is embodied in a system and method for generating and validating reference handles for consumers requiring access to resources in a multi-threaded environment of a computer system. The generation and validation of reference handles in a multi-threaded environment provides efficient management and administration of consumers' access to resources in numerous computer environments, such as networked computers and non-networked personal computers.
The present invention includes a resource manager having a handle administrator, a plurality of consumers, and a plurality of resources. In the description that follows, the term “consumer” refers to a software module that, among other things, requires access to a resource (e.g., a printer driver requiring access to a dynamic link library file). The term “resource manager” refers to a software module that either maintains the resources or at least intercedes in access by the consumers to the resource. The resource manager manages handles that it issues to consumers.
The handle administrator includes an assignment routine, a release routine, and a dereference routine. The assignment routine issues new handles, the release routine releases handles that are no longer required (thus rendering the handle invalid), and the dereference routine dereferences handles into a pointer to a resource which entails verifying that the handle is valid. In addition, the present invention includes an auxiliary sub-routine for managing used and unused records, an expansion sub-routine for efficiently expanding the handle database, a handle recycling sub-routine for recycling handles, a contraction sub-routine for efficiently contracting the handle database, a hysteresis sub-routine for probabilistically contracting the handle database, a memory allocation failure sub-routine, and multi-threading sub-routines enabling operation of the present invention in multi-threaded environments.
A feature of the present invention is that handle assignment and release are constant-time operations, which is especially important if the number of simultaneously active handles is large. Another feature is that the handle administrator of the present invention has efficient assignment, release, and dereferencing routines that effectively work in a multi-threaded environment. Another feature of the present invention is that the size of the database is capable of growing arbitrarily, which is important if the number of handles is unknown ahead of time; and the size of the database is capable of shrinking when possible, which is especially important if the number of handles varies dramatically. Yet another feature of the present invention is that if the number of handles issued over a lifetime exceeds the size of the handle space, then handles can be recycled.
Therefore, the handle administrator of the present invention is designed to work efficiently and effectively when the number of simultaneously active handles is large, when the number of simultaneously active handles is unknown ahead of time, when the number of simultaneously active handles varies dramatically over time, when handle dereferencing needs to be very fast, when operating in multi-threaded environments, and when the number of handles issued over a lifetime is large relative to the handle space.
Further, the multi-threading sub-routines enable safe invalidation of handles in multi-threaded environments and also ensure consistent use of pertinent values, such as array pointers and array sizes during operation of the expansion and contraction sub-routines.
The foregoing and still further features and advantages of the present invention as well as a more complete understanding thereof will be made apparent from a study of the following detailed description of the invention in connection with the accompanying drawings and appended claims.
REFERENCES:
patent: 5375241 (1994-12-01), Walsh
patent: 5802590 (1998-09-01), Draves
patent: 5909580 (1999-06-01), Crelier et al.
patent: 6029160 (2000-02-01), Cabrera et al.
Bar Ofer
Bernet Yoram
Douceur John R.
DeFrank Edmond A.
Homere Jean R.
Lyon, Harr & DeFrank
Microsoft Corporation
LandOfFree
Generation and validation of reference handles in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generation and validation of reference handles in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generation and validation of reference handles in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2560238