Method and apparatus for sharing objects among a plurality of processes

Claim 2

In a multiprocessing environment that performs a plurality of processes, wherein the plurality of processes are supported by at least one processing unit, a method for sharing objects among the plurality of processes, the method comprising the steps of: a) sending, by a process of the plurality of processes, an object request that includes identity of at least some objects of a set of needed objects and a request causal time stamp that indicates, as known by the process, current request value for each process of the plurality of processes; b) entering, by the process, the request causal time stamp and the identity of the at least some objects of the object request into a grant causal list; c) updating, by the process, the grant causal list based on a causal connection order of request causal time stamps and a predetermined order; d) from time to time, receiving another object request from another process of the plurality of processes; e) when the another object request is received, updating, by the process, the grant causal list to include the another object request based on the causal connection order and the predetermined order; f) from time to time, receiving, by the process, an object grant, wherein the object grant includes an object and a grant causal time stamp from a granting process that sent the object grant; g) determining whether the process currently possesses a needed object identified by one of the object requests in the grant causal list and the one of the object requests is of a higher order for the needed object than the object request of the process; h) when the one of the object requests is of the higher order for the needed object, granting the needed object to a needing process affiliated with the one of the object requests.

Claim 3

The method of claim 1, wherein the causal connection order is determined by: comparing request causal time stamps for each entry in the grant causal list; and when a request causal time stamp for a first process is causally precedent to a request causal time stamp for a second process, establishing a causal connection between the first and second processes, wherein a first process' object request has a higher order than a second process' object request.

Claim 4

The method of claim 1, wherein step (d) further comprises: comparing a request causal time stamp of the another process with a current time stamp of the process; and when any current request value in the current time stamp is less than a corresponding current request value in the request causal time stamp of the another process, updating the current causal time stamp.

Claim 5

The method of claim 3, wherein step (a) further comprises: when the object request is generated, setting the request causal time stamp equal to the current time stamp.

Claim 6

The method of claim 3, wherein step (h) further comprises: generating an object grant message to include identity of the needed object and a grant causal time stamp, wherein the grant causal time stamp is equal to the current time stamp of the process.

Claim 7

The method of claim 1, wherein step (f) further comprises: comparing a current time stamp of the process with the grant causal time stamp; and when any current request value in the current time stamp is less than corresponding current request values in the grant causal time stamp of the granting process, updating the current time stamp.

Claim 8

The method of claim 1, wherein step (f) further comprises: updating an object possession set to include the needed object.

Claim 9

The method of claim 1 further comprises the step of: determining whether the needed object gives the process all objects of the set of needed objects based on the object possession set.

Claim 10

The method of claim 8, further comprises: when the needed object gives the process all objects of the set of needed objects, providing the set of needed objects for utilization; and when the set of needed objects are no longer needed, releasing the set of needed objects for subsequent grants.

Claim 11

The method of claim 8 further comprises, when the needed object gives the process all objects of the set of needed objects, updating the current request status of the process within the process' current time stamp.

Claim 12

The method of claim 1 further comprises: invalidating a first object request of a particular process when a second object request of the particular process is received and the current request value of the second object request is more current than the current request value of the first object request, or when a grant causal time stamp or request causal time stamp is received and includes a current request value for the particular process that is more current than the current request value of the first object request.

Claim 13

The method of claim 1 further comprises: when all objects of the set of needed objects are in possession, determining whether one of the objects of the set of needed objects is a read only object; when the read only object is received, copying the read only object; and after copying the read only object, removing the read only object from the set of needed objects.

Claim 16

The method of claim 13, wherein the causal connection order is determined by: comparing request causal time stamps for each entry in the grant causal list; and when a request causal time stamp for a first process is causally precedent to a request causal time stamp for a second process, establishing a causal connection between the first and second processes, wherein a first process' object request has a higher order than a second process' object request.

Claim 17

The method of claim 13, wherein the step (b) further comprises: prior to updating, determining whether an object requested in the object request is a surplus object; and when the object is a surplus object, granting the object to the another process.

Claim 18

An object allocation processor comprising: memory for storing an object allocation algorithm, for storing identity of currently possessed objects, and for storing identity of needed objects; and a processor operably coupled to the memory to execute the object allocation algorithm, wherein the memory further includes, for storing the object allocation algorithm, sending means for storing program instructions that cause the processor to generate an object request that includes identity of at least some objects of a set of needed objects and a request causal time stamp that indicates, as known by the process, current request value for each process of the plurality of processes; entering means for storing program instructions that cause the process to enter the request causal time stamp and the identity of the at least some objects of the object request into a grant causal list; request receiving means for storing program instructions that cause the processor to, from time to time, receive another object request; updating means for storing program instructions that cause the processor to update the grant causal list based on a causal connection order of request causal time stamps and a predetermined order; grant receiving means for storing program instructions that cause the processor to, from time to time, receive object grant, wherein the object grant includes an object and a grant causal time stamp from a granting process that sent the object grant; determining means for storing program instructions that cause the process to determine whether a needed object identified by one of the object requests in the grant causal list is currently possessed and the one of the object requests is of a higher order for the needed object than the object request of the process; and granting means for storing program instructions that cause the processor to grant the needed object to the one of the object requests of the higher order for the needed object.

Claim 19

An object allocation processor comprising: memory for storing an object allocation algorithm, for storing identity of currently possessed objects, and for storing identity of needed objects; and a processor operably coupled to the memory to execute the object allocation algorithm, wherein the memory further includes, for storing the object allocation algorithm, sending means for storing program instructions that cause the processor to generate an object request that includes identity of at least some objects of a set of needed objects and a request causal time stamp that indicates, as known by the process, current request value for each process of the plurality of processes; entering means for storing program instructions that cause the process to enter the request causal time stamp and the identity of the at least some objects of the object request into a grant causal list; request receiving means for storing program instructions that cause the processor to, from time to time, receive another object request; updating means for storing program instructions that cause the processor to update the grant causal list based on a causal connection order of request causal time stamps and a predetermined order; grant receiving means for storing program instructions that cause the processor to, from time to time, receive object grant, wherein the object grant includes an object and a grant causal time stamp from a granting process that sent the object grant; determining means for storing program instructions that cause the process to determine whether a needed object identified by one of the object requests in the grant causal list is currently possessed and the one of the object requests is of a higher order for the needed object than the object request of the process; and granting means for storing program instructions that cause the processor to grant the needed object to the one of the object requests of the higher order for the needed object.

Claim 20

The object allocation processor of claim 16, wherein the updating means further stores program instructions to determine the causal connection order including: comparing request causal time stamps for each entry in the grant causal list; and when a request causal time stamp for a first process is less than a request causal time stamp for a second process, establishing a causal connection between the first and second processes, wherein a first process' object request has a higher order than a second process' object request.

Claim 21

A processing entity comprising: a processing unit; memory operably coupled to the processing unit, wherein the memory stores operating instructions and data for the processing unit; an object allocation section operably coupled to the processing unit, wherein, when instructed by the processing unit, the object allocation section retrieves a set of needed objects, the object allocation section includes: sending means for storing program instructions that cause the processor to generate an object request that includes identity of at least some objects of a set of needed objects and a request causal time stamp that indicates, as known by the process, current request value for each process of the plurality of processes; entering means for storing program instructions that cause the process to enter the request causal time stamp and the identity of the at least some objects of the object request into a grant causal list; request receiving means for storing program instructions that cause the processor to, from time to time, receive another object request; updating means for storing program instructions that cause the processor to update the grant causal list based on a causal connection order of request causal time stamps and a predetermined order when more than one object request is present in the grant causal list; grant receiving means for storing program instructions that cause the processor to, from time to time, receive object grant, wherein the object grant includes an object and a grant causal time stamp from a granting process that sent the object grant; determining means for storing program instructions that cause the process to determine whether a needed object identified by one of the object requests in the grant causal list is currently possessed and the one of the object requests is of a higher order for the needed object; and granting means for storing program instructions that cause the processor to grant the needed object to the one of the object requests of the higher order for the needed object.

Claim 22

A processing entity comprising: a processing unit; memory operably coupled to the processing unit, wherein the memory stores operating instructions and data for the processing unit; an object allocation section operably coupled to the processing unit, wherein, when instructed by the processing unit, the object allocation section retrieves a set of needed objects, the object allocation section includes: sending means for storing program instructions that cause the processor to generate an object request that includes identity of at least some objects of a set of needed objects and a request causal time stamp that indicates, as known by the process, current request value for each process of the plurality of processes; entering means for storing program instructions that cause the process to enter the request causal time stamp and the identity of the at least some objects of the object request into a grant causal list; request receiving means for storing program instructions that cause the processor to, from time to time, receive another object request; updating means for storing program instructions that cause the processor to update the grant causal list based on a causal connection order of request causal time stamps and a predetermined order when more than one object request is present in the grant causal list; grant receiving means for storing program instructions that cause the processor to, from time to time, receive object grant, wherein the object grant includes an object and a grant causal time stamp from a granting process that sent the object grant; determining means for storing program instructions that cause the process to determine whether a needed object identified by one of the object requests in the grant causal list is currently possessed and the one of the object requests is of a higher order for the needed object; and granting means for storing program instructions that cause the processor to grant the needed object to the one of the object requests of the higher order for the needed object.

Claim 23

The processing entity of claim 18, wherein the updating means further stores program instructions to determine the causal connection order including: comparing request causal time stamps for each entry in the grant causal list; and when a request causal time stamp for a first process is less than a request causal time stamp for a second process, establishing a causal connection between the first and second processes, wherein a first process' object request has a higher order than a second process' object request.

Claim 24

A processor readable medium for storing an object allocation algorithm that causes a processor, when reading the object allocation algorithm, to function in a predetermined manner, the processor readable medium comprising: sending means for storing program instructions that cause the processor to generate an object request that includes identity of at least some objects of a set of needed objects and a request causal time stamp that indicates, as known by the process, current request value for each process of the plurality of processes; entering means for storing program instructions that cause the process to enter the request causal time stamp and the identity of the at least some objects of the object request into a grant causal list; request receiving means for storing program instructions that cause the processor to, from time to time, receive another object request; updating means for storing program instructions that cause the processor to update the grant causal list based on a causal connection order of request causal time stamps and a predetermined order; grant receiving means for storing program instructions that cause the processor to, from time to time, receive object grant, wherein the object grant includes an object and a grant causal time stamp from a granting process that sent the object grant; determining means for storing program instructions that cause the process to determine whether a needed object identified by one of the object requests in the grant causal list is currently possessed and the one of the object requests is of a higher order for the needed object; and granting means for storing program instructions that cause the processor to grant the needed object to the one of the object requests of the higher order for the needed object.

Claim 25

A processor readable medium for storing an object allocation algorithm that causes a processor, when reading the object allocation algorithm, to function in a predetermined manner, the processor readable medium comprising: sending means for storing program instructions that cause the processor to generate an object request that includes identity of at least some objects of a set of needed objects and a request causal time stamp that indicates, as known by the process, current request value for each process of the plurality of processes; entering means for storing program instructions that cause the process to enter the request causal time stamp and the identity of the at least some objects of the object request into a grant causal list; request receiving means for storing program instructions that cause the processor to, from time to time, receive another object request; updating means for storing program instructions that cause the processor to update the grant causal list based on a causal connection order of request causal time stamps and a predetermined order; grant receiving means for storing program instructions that cause the processor to, from time to time, receive object grant, wherein the object grant includes an object and a grant causal time stamp from a granting process that sent the object grant; determining means for storing program instructions that cause the process to determine whether a needed object identified by one of the object requests in the grant causal list is currently possessed and the one of the object requests is of a higher order for the needed object; and granting means for storing program instructions that cause the processor to grant the needed object to the one of the object requests of the higher order for the needed object.

Claim 26

The processor readable medium of claim 20, wherein the updating means further stores program instructions to determine the causal connection order including: comparing request causal time stamps for each entry in the grant causal list; and when a request causal time stamp for a first process is causally precedent to a request causal time stamp for a second process, establishing a causal connection between the first and second processes, wherein a first process' object request has a higher order than a second process' object request.