Methods and apparatus for tuple management in data processing system

• US 6,751,619 B1
• Filed: 03/15/2000
• Issued: 06/15/2004
• Est. Priority Date: 03/15/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: De Nicola, Rocco, Rowstron, Antony Ian Taylor
• Primary Examiner(s): Le, Uyen
• Assistant Examiner(s): CHEN, TE Y
• Application Number:
  US09/526,640
• Time in Patent Office: 1,553 Days
• Field of Search: 707/1-5, 707/10, 707/101-104, 707/6, 706/48-50, 711/108, 709/203, 709/228, 709/217, 718/101
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A data processing system stores information in tuple space as tuples that are accessible by multiple entities. Methods, apparatus, computer-readable media, and data structures provide efficient extensions to tuple space coordination languages for example Linda, that increase concurrency by lessening tuple removal, without requiring compile time analysis, altering existing primitives, or adding new primitives. Traces are used to analyze tuple space access in distributed systems, resulting in optimizations based upon certain conditions which, if met, enable a tuple to remain visible in tuple space without blocking, so that other processes can continue to read the tuple while a first process is updating the tuple. A run-time optimization modifies the conditions if the execution is in a closed system that is known not to intentionally contain deadlock, further improving performance.

Claims

1. A method of managing information in information space, the method comprising:

performing a first access operation on the information by a first entity; and

keeping the information in information space for a second access operation by a second entity, provided that the following conditions are true;

(a) the second access operation is not destructive;

(b) the second entity is not the first entity;

(c) the first entity has not subsequently accessed the information space;

(d) the second access operation blocks a thread of execution of the second entity until a result is returned; and

,

(e) the first entity has not terminated.

2. The method recited in claim 1 and further comprising:

discarding the information if any of the conditions is untrue.

3. The method recited in claim 1, wherein the information is a tuple, and information space is tuple space.

4. The method recited in claim 1, wherein the first and second access operations are primitives.

5. The method recited in claim 1, wherein the first access operation is an in primitive, and the second access operation is a rd primitive.

6. The method recited in claim 5, wherein the information is a tuple functioning as a counter.

7. The method recited in claim 1, wherein the first and second entities are agents.

8. The method recited in claim 1, wherein in condition (d) a result comprises a tuple or an indication of completion of movement of tuples.

9. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.

10. A method of managing tuple space, the method comprising:

performing a first primitive on a tuple by a first entity; and

keeping the tuple in tuple space for the performance of a second primitive by a second entity, provided that the following conditions are true;

(a) the second primitive is not destructive;

(b) The second primitive is not being performed by the same entity that performed the first primitive;

(c) The first entity has not subsequently accessed the tuple space;

(d) The second primitive blocks a thread of execution of the second entity until a result is returned; and

,

(e) The first entity has not terminated.

11. The method recited in claim 10, and further comprising:

discarding the tuple if any of the conditions is untrue.

12. The method recited in claim 10, wherein the first primitive is an in primitive, and the second primitive is a rd primitive.

13. The method recited in claim 12, wherein the tuple is a counter.

14. The method recited in claim 10, wherein the first and second entities are agents.

15. The method recited in claim 10, wherein in condition (d) a result comprises a tuple or an indication of completion of movement of tuples.

16. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 10.

17. A computer system to manage information in information space comprising:

at least one processor to execute instructions;

a memory to store the information and instructions, wherein the instructions comprise at least one instruction for performing a first access operation on the information, and at least one additional instruction for performing a second access operation on the information, the performance of the at least one additional instruction being subject to the following conditions being true;

(a) the second access operation would not be destructive;

(b) the at least one instruction and the at least one additional instruction would not be executed on behalf of an identical entity;

(c) an entity requesting execution of the at least one instruction has not subsequently accessed the information space;

(d) the second access operation blocks a thread of execution of which the at least one additional instruction is a part until a result is returned; and

,

(e) an entity requesting execution of the at least one instruction has not terminated.

18. The computer system recited in claim 17 wherein the instructions further comprise an instruction for discarding the information if any of the conditions is untrue.

19. The computer system recited in claim 17, wherein the information is a tuple, and the information space is tuple space.

20. The computer system recited in claim 17, wherein the at least one instruction and the at least one additional instruction are primitives.

21. The computer system recited in claim 17, wherein the at least one instruction is an in primitive, and the at least one additional instruction is a rd primitive.

22. The computer system recited in claim 21, wherein the information is a tuple functioning as a counter.

23. The computer system recited in claim 21, wherein the at least one instruction and the at least one additional instruction are to be executed on behalf of respective first and second agents.

24. The computer system recited in claim 21, wherein in condition (d) a result comprises a tuple or an indication of completion of movement of tuples.

25. The computer system recited in claim 17, wherein the instructions in the memory further comprise a run-time switch that, if enabled, substitutes the following condition for condition (c):

(c1) an entity requesting execution of the at least one instruction has not subsequently inserted information into the information space or caused any information to be inserted into the information space.

26. A computer system to manage a tuple in tuple space comprising:

at least one processor to execute instructions;

a memory to store the tuple and instructions, wherein the instructions comprise at least one instruction for performing a first primitive on the tuple by a first entity, and at least one additional instruction for performing a second primitive on the tuple by a second entity, the performance of the second primitive being subject to the following conditions being true;

(a) performance of the second primitive would not be destructive;

(b) the second entity is different from the first entity;

(c) the first entity has not subsequently accessed the tuple space;

(d) The second primitive blocks a thread of execution of the second entity until a result is returned; and

,

(e) the first entity has not terminated.

27. The computer system recited in claim 26, wherein the instructions further comprise an instruction for discarding the information if any of the conditions is untrue.

28. The computer system recited in claim 26, wherein the first primitive is an in primitive, and the second primitive is a rd primitive.

29. The computer system recited in claim 28, wherein the tuple is a counter.

30. The computer system recited in claim 26, wherein the entities are agents.

31. The computer system recited in claim 26, wherein in condition (d) a result comprises a tuple or an indication of completion of movement of tuples.

32. The computer system recited in claim 26, wherein the instructions in the memory further comprise a run-time switch that, if enabled, substitutes the following condition for condition (c):

(c1) the first entity has not subsequently inserted a tuple into the tuple space or caused any tuples to be inserted into the tuple space.

33. A computer-readable medium having computer-executable components to cause a computer to perform a method of managing tuple space comprising:

a first primitive to be performed on a tuple by a first entity;

a second primitive to be performed on the tuple by a second entity; and

a decision module to determine whether to keep the tuple in tuple space after the performance of the first primitive, the decision module keeping the tuple if the following conditions are true;

(a) the second primitive is not destructive;

(b) the second primitive is not being performed by the first entity;

(c) the first entity has not subsequently accessed the tuple space;

(d) the second primitive blocks a thread of execution of the second entity until a result is returned; and

,

(e) the first entity has not terminated.

34. The computer-readable medium recited in claim 33, wherein the decision module comprises at least one computer-executable instruction to discard the tuple if any of the conditions is untrue.

35. The computer-readable medium recited in claim 33, wherein the first primitive is an in primitive, and the second primitive is a rd primitive.

36. The computer-readable medium recited in claim 35, wherein the tuple is a counter.

37. The computer-readable medium recited in claim 35, wherein the first and second entities are agents.

38. The computer-readable medium recited in claim 33, wherein in condition (d) a result comprises a tuple or an indication of completion of movement of tuples.

39. The computer-readable medium recited in claim 33 and further comprising:

a run-time switch that, if enabled, substitutes the following condition for condition (c);

(c1) the first entity has not subsequently inserted a tuple into the tuple space or caused any tuples to be inserted into the tuple space.

40. A computer-readable medium having stored thereon a data structure comprising:

a first data structure member that stores a plurality of tuples;

a second data structure member that stores a list of primitives performed on the plurality of tuples;

a third data structure member that stores for each primitive an identifier for an entity that performed the primitive;

a fourth data structure member that stores a count for each entity, the count being incremented whenever a predetermined type of primitive is performed by the entity and,

a fifth data structure member that stores a set of conditions under which a particular tuple can be kept visible to a second entity after a first entity has performed a primitive on the tuple.

41. The computer-readable medium recited in claim 40, wherein the predetermined type of primitive is an out or collect.

42. The computer-readable medium recited in claim 40, wherein the set of conditions comprises:

(a) the second primitive is not destructive;

(b) the second primitive is not being performed by the first entity;

(c) the first entity has not subsequently accessed the tuple space;

(d) the second primitive blocks a thread of execution of the second entity until a result is returned.

43. The computer-readable medium recited in claim 42 wherein the conditions additionally comprise:

(e) the first entity has not terminated.

44. The computer-readable medium recited in claim 40, and further comprising:

a sixth data structure member for storing a run-time switch that, if enabled, substitutes the following condition for condition (c);

(c1) the first entity has not subsequently inserted a tuple into the tuple space or caused any tuples to be inserted into the tuple space.