Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
2001-08-21
2003-07-22
Coulter, Kenneth R. (Department: 2141)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C709S203000, C709S241000
Reexamination Certificate
active
06598079
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to data processing systems and, more particularly, to a pledge-based resource allocation system.
BACKGROUND OF THE INVENTION
Conventional systems like the one depicted in
FIG. 1
have been developed where a computer program
101
(a client) on a client computer
102
requests the allocation of a resource, such as a file, stored on a server computer
104
that is communicatively linked to the client computer via a network
106
. After allocating the resource, the client
101
utilizes the resource and then indicates to the server computer
104
that it has completed its use of the resource and that the server computer may deallocate the resource. The deallocation of the resource on the server computer
104
is performed in response to the client
101
indicating that it is finished with the resource.
A number of problems can arise in the conventional system
100
depicted in FIG.
1
. For example, if the client computer
102
is connected to the server computer
104
via a rather untrustworthy network
106
, the resource may never be deallocated by the client and thus the resource cannot be used by other clients. Additionally, the client may forget about the use of the resource (e.g., due to an error) and again the resource is continually allocated and unavailable to other clients. Managing these problems becomes much more complex as the number of resources that the server computer
104
can allocate becomes very large and the number of clients who can use the resources also becomes very large. In this situation, the server computer
104
spends a significant amount of processing time maintaining numerous data structures containing information about thousands or even millions of resources. It is therefore desirable to improve resource allocation strategies to suit the needs of a client/server environment where the server computer has many resources that can be allocated to many clients.
SUMMARY OF THE INVENTION
A pledge-based resource allocation system for a client/server environment is provided. In this system, resources, such as database objects, are allocated to clients for a limited time period. Allocating resources to clients for a limited time period ensures that a client cannot allocate a resource for so long as to affect other client's use of the resource. This limited use of resources also has other benefits, such as preventing concurrency problems like deadlock. Additionally, using this system, a client knows for how long it can utilize a resource since it knows for how long the resource will be valid (i.e., how long its integrity can be guaranteed) and can plan accordingly.
Another aspect of the pledge-based resource allocation system is that it efficiently stores a directory structure containing allocation-related information for all resources in the system. This aspect provides that when accessing resource information, all related information of related resources are grouped closely together (i.e., partitioned) to facilitate their access and reduce memory access time.
In accordance with a first aspect of the present invention, a method is practiced in a computer system for allocating groups of resources of the computer system to a client. The method assigns a first expiration time to each group, receives a request from the client to allocate one of the resources in one of the groups, and allocates the one resource to the client. Further, the method determines when the first expiration time of the one group has been reached, and when it is determined that the first expiration time has been reached, the method assigns a second expiration time to the one group. The method also determines when the second expiration time has been reached, and when it is determined that the second expiration time has been reached, the method deallocates the one resource from the client.
In accordance with a second aspect of the present invention, a method is practiced in a computer system for allocating objects to a client where the computer system has a B+tree data structure with an entry for each object. The entries store allocation information for the objects. The method groups related objects into groups, assigns an expiration time to each group, and receives a request from the client to allocate one of the objects in one of the groups. Further, the method stores an indication of the client into the entry in the B+tree for the one object to allocate the one object to the client, and determines when the expiration time has been reached after the allocation of the one resource. When it is determined that the expiration time has been reached, the method deletes the indication of the client to deallocate the object.
In accordance with a third aspect of the present invention, a data processing system is provided comprising a client computer, a server computer, and a network communicatively linking the server computer to the client computer. The client computer has a memory containing a computer program that requests allocation of a resource, that receives a time limit for using the resource, and that utilizes the resource until the time limit has been reached. The client computer also has a processor for running the computer program. The server computer has a memory containing a resource allocator for allocating resources of the server computer to the computer program and contains a B+tree having subtrees for storing allocation information for partitions of the resources. The server computer also has a processor for running the object allocator. Each partition has an associated expiration time. The subtrees are stored in a contiguous block of the memory. The resource allocator receives an allocation request for a resource from the computer program, calculates the time limit by adding a predetermined time interval to the expiration time, stores an indication of the computer program into the B+tree and sends the time limit to the computer program to allocate the resource, determines when the expiration time expires for a second time, and deallocates the allocated resource when it is determined that the time limit has expired.
REFERENCES:
patent: 5179556 (1993-01-01), Turner
patent: 5265250 (1993-11-01), Andrade et al.
patent: 5461611 (1995-10-01), Drake, Jr. et al.
patent: 5522070 (1996-05-01), Sumimoto
patent: 5600822 (1997-02-01), Grice et al.
patent: 5745694 (1998-04-01), Egawa et al.
patent: 5918049 (1999-06-01), Syvaniemi
patent: 5963945 (1999-10-01), Pal
patent: 6205484 (2001-03-01), Eriksson
patent: 6301616 (2001-10-01), Pal et al.
patent: 6336127 (2002-01-01), Kurtzberg et al.
Silberschatz, Abraham and Peter B. Galvin,Operating System Concepts, 4th Ed. Addison-Wesley, Reading, MA., 1994,pp. 315-325.
Ullman, Jeffrey D., “Principles of Database Systems,” 2nd Ed., Computer Science Press, 1982, pp. 58-69.
Ammann, P., F. Jaeckle and S. Jajodia, “A” Two-Snapshot Algorithm for Concurrency Control in Secure Multi-level Databases, In the Proceedings of the 1992 Symposium on Research in Security and Privacy, Oakland, CA, May 1992, pp. 204-215.
Pal, Shankar, “A Locking Protocol for Multilevel Secure Databases Providing Support for Long Transactions,” In the Proceedings of the IFIP WG11.3 Ninth Annual Conference on Database Security, Rensselaerville, NY, Aug. 13-16, 1995, pp. 199-221.
Bennett John G.
Pal Shankar
Coulter Kenneth R.
Microsoft Corporation
Woodcock & Washburn LLP
LandOfFree
Pledge-based resource allocation 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 Pledge-based resource allocation system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pledge-based resource allocation system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3093369