Pledge-based resource allocation system

• US 6,301,616 B1
• Filed: 04/11/1997
• Issued: 10/09/2001
• Est. Priority Date: 04/11/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bennett, John G., Pal, Shankar
• Primary Examiner(s): Coulter, Kenneth R.
• Application Number:
  US08/827,827
• Time in Patent Office: 1,642 Days
• Field of Search: 709/226, 709/203, 709/217, 709/218, 709/219, 709/104, 395/200.56, 395/200.33
• US Class Current: 709/226
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5022 Mechanisms to release resources

Abstract

A pledge-based resource allocation system is provided in a client/server environment. 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 scheme, 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 it 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.

Claims

1. A method in a server computer for allocating groups of resources of the server computer to a client computer, comprising:

assigning, by the server computer, a first expiration time to each group;

receiving, by the server computer, a request from the client computer to allocate a selected one of the resources in a selected one of the groups;

allocating, by the server computer, the selected resource in the selected group to the client computer;

determining, by the server computer, when the first expiration time of the selected group has been reached after allocating the selected resource;

when it is determined that the first expiration time has been reached, assigning, by the server computer, a second expiration time to the selected group;

determining, by the server computer, when the second expiration time has been reached; and

when it is determined that the second expiration time has been reached, deallocating, by the server computer, the selected resource from the client computer.

2. The method of claim 1 wherein the resources are database objects.

3. The method of claim 1 wherein assigning, by the server computer, a first expiration time includes setting, by the server computer, the first expiration time equivalent to a current time plus a time interval.

4. The method of claim 3 wherein assigning, by the server computer, a second expiration time includes setting, by the server computer, the second expiration time equivalent to the first expiration time plus the time interval.

5. The method of claim 1 wherein allocating, by the server computer, the one resource includes sending, by the server computer, a response to the client computer containing an indication that the one resource has been allocated and containing a time limit specifying a time beyond which validity of the one resource cannot be guaranteed.

6. The method of claim 5 wherein sending an indication includes sending, by the server computer, the selected resource to the client.

7. A method in a computer system for allocating groups of resources of the computer system to a client, comprising:

assigning a first expiration time to each group;

receiving a request from the client to allocate a selected one of the resources in a selected one of the groups;

allocating the selected resource in the selected group to the client;

determining when the first expiration time of the selected group has been reached after allocating the selected resource;

when it is determined that the first expiration time has been reached, assigning a second expiration time to the selected group;

determining when the second expiration time has been reached; and

when it is determined that the second expiration time has been reached, deallocating the selected resource from the client,

wherein the computer system has a B+tree data structure storing allocation information for the groups of resources, and wherein allocating the selected resource includes storing an identifier of the client into the B+tree data structure to indicate the allocation.

8. The method of claim 7 wherein deallocating the selected resource includes deleting the identifier of the client from the B+tree data structure to indicate the deallocation of the selected resource.

9. A method in a computer system for allocating groups of resources of the computer system to a client, comprising:

assigning a first expiration time to each group;

receiving a request from the client to allocate a selected one of the resources in a selected one of the groups;

allocating the selected resource in the selected group to the client;

determining when the first expiration time of the selected group has been reached after allocating the selected resource;

when it is determined that the first expiration time has been reached, assigning a second expiration time to the selected group;

determining when the second expiration time has been reached;

when it is determined that the second expiration time has been reached, deallocating the selected resource from the client;

before assigning the first expiration time to each group,

determining objects that are related; and

forming the groups by grouping the related objects together.

10. A method in a computer system for allocating groups of objects to a client, the computer system having a B+tree data structure with an entry for each object, the entries storing allocation information for the objects, comprising:

assigning an expiration time to each group;

receiving a request from the client to allocate a selected one of the objects in a selected one of the groups;

storing an indication of the client into the entry in the B+tree for the selected object to allocate the selected object to the client;

determining when the expiration time has been reached after the allocation of the selected object; and

when it is determined that the expiration time has been reached, deleting the indication of the client to deallocate the object.

11. The method of claim 10, further including:

before assigning the expiration time to each group,

determining objects that are related; and

forming the groups by grouping the related objects together.

12. A method in a computer system for allocating objects to clients, comprising:

dividing the objects into groups wherein each group contains related objects;

assigning unique numerical identifiers to the objects of each group wherein the numerical identifiers for each group have a range and the range of each group is nonoverlapping;

associating a time value with each group;

allocating a plurality of the objects to the clients to create allocated objects;

detecting when one of the time values associated with one of the groups has been reached, the one group having an allocated object; and

deallocating the allocated object in the one group,

wherein the computer system has a B+tree data structure storing allocation information for the objects and wherein allocating a plurality of the objects includes storing an identifier of the clients allocating the plurality of objects into the B+tree data structure.

13. The method of claim 12 wherein deallocating the allocated object includes deleting the identifier from the B+tree data structure of the client that allocated the allocated object.

14. A method in a data processing system for allocating a resource on a server computer by a resource allocator to a client on a client computer, the method performed by the resource allocator comprising:

receiving a request from the client on the client computer system to allocate a resource;

allocating the resource for use by the client for a preset amount of time;

determining when the preset amount of time has expired; and

when it is determined that the preset amount of time has expired, deallocating the resource,

wherein the server computer has a B+tree data structure storing allocation information for the resource, and wherein allocating the resource includes storing an indication of the client into the B+tree data structure to indicate that the client has allocated the resource.

15. The method of claim 14 wherein deallocating the resource includes deleting the stored indication of the client to deallocate the resource.

16. A data processing system comprising:

a client computer having 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, and having a processor for running the computer program;

a server computer having a memory containing a resource allocator for allocating resources of the server computer to the computer program and containing a B+tree having subtrees for storing allocation information for partitions of the resources, and having a processor for running the resource allocator, each partition having an associated expiration time, the subtrees stored in a contiguous block of the memory, wherein 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 time limit expires, and deallocates the allocated resource when it is determined that the time limit has expired; and

a network communicatively linking the server computer to the client computer.

17. The data processing system of claim 16 wherein the allocated resource is a database object.

18. A method in a computer system for allocating objects to clients, the computer system having a B+tree storing allocation information for the objects in object records containing client entries indicating clients that have allocated the object, comprising:

grouping the objects into partitions of related objects;

assigning unique identifiers to the objects of each partition wherein the identifiers for each partition have a range of values and the range of values of each partition is nonoverlapping;

storing each partition in a subtree of the B+tree wherein the subtree occupies a contiguous block of memory;

assigning an expiration time to each partition;

receiving a request to allocate an object in one of the partitions to the client;

determining when the expiration time for the one partition has expired to perform deallocation;

when it is determined that the expiration time for the one partition has expired,

for each object record in the subtree for the partition,

for each client entry for the object record,

determining if the client entry has been allocated through the expiration of a previous expiration time;

when it is determined that the client entry has been allocated though the expiration of the previous expiration time, deleting the client entry; and

when it is determined that the client entry has not been allocated through the expiration of the previous expiration time,

updating the client entry to indicate that the client entry has been allocated through the expiration of the previous expiration time; and

assigning a new expiration time to the one partition that is equivalent to the expiration time plus a preset time interval;

accessing the object entry for the object; and

inserting an indication of the client into the client entry in the object record.

19. A method in a computer system for allocating objects to clients, the computer system having a B+tree storing allocation information for the objects in object records containing client entries indicating clients that have allocated the object, comprising the steps of:

grouping the objects into partitions of related objects;

assigning unique identifiers to the objects of each partition wherein the identifiers for each partition have a range of values and the range of values of each partition is nonoverlapping;

storing each partition in a subtree of the B+tree wherein the subtree occupies a contiguous block of memory;

assigning an expiration time to each partition;

receiving a request to allocate an object in one of the partitions to the client;

determining when the expiration time for the one partition has expired to perform deallocation;

when it is determined that the expiration time for the one partition has expired,

for each object record in the subtree for the partition,

for each client entry for the object record,

determining if the client entry has been allocated through the expiration of a previous expiration time;

when it is determined that the client entry has been allocated though the expiration of the previous expiration time, deleting the client entry; and

when it is determined that the client entry has not been allocated through the expiration of the previous expiration time,

updating the client entry to indicate that the client entry has been allocated through the expiration of the previous expiration time; and

assigning a new expiration time to the one partition that is equivalent to the expiration time plus a preset time interval;

accessing the object entry for the object; and

inserting an indication of the client into the client entry in the object record;

wherein the step of assigning a new expiration time includes;

determining a number of object records in the one partition;

increasing the time interval when the number of object records is within a first predefined range; and

decreasing the time interval when the number of object records is within a second predefined range.

20. A method in a computer system for allocating objects to clients, the computer system having a B+tree storing allocation information for the objects in object records containing client entries indicating clients that have allocated the object, comprising the steps of:

grouping the objects into partitions of related objects;

assigning unique identifiers to the objects of each partition wherein the identifiers for each partition have a range of values and the range of values of each partition is nonoverlapping;

storing each partition in a subtree of the B+tree wherein the subtree occupies a contiguous block of memory;

assigning an expiration time to each partition;

receiving a request to allocate an object in one of the partitions to the client;

determining when the expiration time for the one partition has expired to perform deallocation;

when it is determined that the expiration time for the one partition has expired,

for each object record in the subtree for the partition,

for each client entry for the object record,

determining if the client entry has been allocated through the expiration of a previous expiration time;

when it is determined that the client entry has been allocated though the expiration of the previous expiration time,

deleting the client entry; and

when it is determined that the client entry has not been allocated through the expiration of the previous expiration time,

updating the client entry to indicate that the client entry has been allocated through the expiration of the previous expiration time; and

assigning a new expiration time to the one partition that is equivalent to the expiration time plus a preset time interval;

accessing the object entry for the object; and

inserting an indication of the client into the client entry in the object record;

wherein the step of deleting the client entry includes;

determining if an overflow record has been allocated to store client entries that do not fit into the object record;

when it is determined that an overflow record has been allocated,

determining if the overflow record contains client entries that do not fit into the object record; and

when it is determined that the overflow record does not contain client entries that do not fit into the object record,

copying the client entries in the overflow record into the object record; and

deleting the overflow record.

21. A computer-readable memory device containing a B+tree data structure having leaf nodes storing references to object records for a plurality of objects and having an associated time value, the time value being set based on a preset time interval, each leaf node referring to an object record containing;

one or more client entries that each contain an indication of a client allocating the object, and an indication of whether the client has allocated the object for one time interval or two time intervals.

22. A computer-readable medium containing instructions for controlling a server computer to allocate groups of resources of the server computer to a client computer, by performing:

assigning, by the server computer, a first expiration time to each group;

receiving, by the server computer, a request from the client computer to allocate a selected one of the resources in a selected one of the groups;

allocating, by the server computer, the selected resource in the selected group to the client computer;

determining, by the server computer, when the first expiration time of the selected group has been reached after allocating the selected resource;

when it is determined that the first expiration time has been reached, assigning, by the server computer, a second expiration time to the selected group;

determining, by the server computer, when the second expiration time has been reached; and

when it is determined that the second expiration time has been reached, deallocating, by the server computer, the selected resource from the client computer.

23. The computer-readable medium of claim 22 wherein the resources are database objects.

24. The computer-readable medium of claim 22 wherein assigning a first expiration time includes setting, by the server computer, the first expiration time equivalent to a current time plus a time interval.

25. The computer-readable medium of claim 22 wherein assigning a second expiration time includes setting, by the server computer, the second expiration time equivalent to the first expiration time plus the time interval.

26. The computer-readable medium of claim 22 wherein allocating the one resource includes sending, by the server computer, a response to the client computer containing an indication that the one resource has been allocated and containing a time limit specifying a time beyond which validity of the one resource cannot be guaranteed.

27. The computer-readable medium of claim 26 wherein sending an indication includes sending, by the server computer, the selected resource to the client computer.

28. A computer-readable medium containing instructions for controlling a computer system to allocate groups of resources of the computer system to a client, by performing:

assigning a first expiration time to each group;

receiving a request from the client to allocate a selected one of the resources in a selected one of the groups;

allocating the selected resource in the selected group to the client;

determining when the first expiration time of the selected group has been reached after allocating the selected resource;

when it is determined that the first expiration time has been reached, assigning a second expiration time to the selected group;

determining when the second expiration time has been reached; and

when it is determined that the second expiration time has been reached, deallocating the selected resource from the client,

wherein the computer system has a B+tree data structure storing allocation information for the groups of the resources, and wherein allocating the selected resource includes storing an identifier of the client into the B+tree data structure to indicate the allocation.

29. The computer-readable medium of claim 28 wherein deallocating the selected resource includes deleting the identifier of the client from the B+tree data structure to indicate the deallocation of the selected resource.

30. A computer-readable medium containing instructions for controlling a computer system to allocate groups of resources of the computer system to a client, by performing:

assigning a first expiration time to each group;

receiving a request from the client to allocate a selected one of the resources in a selected one of the groups;

allocating the selected resource in the selected group to the client;

determining when the first expiration time of the selected group has been reached after allocating the selected resource;

when it is determined that the first expiration time has been reached, assigning a second expiration time to the selected group;

determining when the second expiration time has been reached;

when it is determined that the second expiration time has been reached, deallocating the selected resource from the client;

before assigning the first expiration time to each group, determining objects that are related; and

forming the groups by grouping the related objects together.

31. A computer-readable medium containing instructions for controlling a computer system to allocate groups of objects to a client, the computer system having a B+tree data structure with an entry for each object, the entries storing allocation information for the objects, by performing:

assigning an expiration time to each group;

receiving a request from the client to allocate a selected one of the objects in a selected on one of the groups;

storing an indication of the client into the entry in the B+tree for the selected object to allocate the selected object to the client;

determining when the expiration time has been reached after the allocation of the selected object;

when it is determined that the expiration time has been reached, deleting the indication of the client to deallocate the object;

before assigning the first expiration time to each group,

determining objects that are related; and

forming the groups by grouping the related objects together.

32. A computer-readable medium containing instructions for controlling a computer system to allocate objects to clients, by performing:

dividing the objects into groups wherein each group contains related objects;

assigning unique numerical identifiers to the objects of each group wherein the numerical identifiers for each group have a range and the range of each group is nonoverlapping;

associating a time value with each group;

allocating a plurality of the objects to the clients to create allocated objects;

detecting when one of the time values associated with one of the groups has been reached, the one group having an allocated object; and

deallocating the allocated object in the one group.

33. A method in a server computer for allocating groups of resources of the server computer to a client computer, comprising:

assigning, by the server computer, a first expiration time to each group, wherein the first expiration time is stored in a data structure in the server computer;

receiving, by the server computer, a request from the client computer to allocate a selected one of the resources in a selected one of the groups;

allocating, by the server computer, the selected resource in the selected group to the client computer;

determining, by the server computer, when the first expiration time of the selected group has been reached after allocating the selected resource;

when it is determined that the first expiration time has been reached, assigning, by the server computer, a second expiration time to the selected group, wherein the second expiration time is stored in the data structure in the server computer;

determining, by the server computer, when the second expiration time has been reached; and

when it is determined that the second expiration time has been reached, deallocating, by the server computer, the selected resource from the client computer.