Tuple space operations for fine grained system control6704734Abstract According to the present invention, a plurality of new tuple-space operators is provided for enhancing the capability of tuple spaces to provide fine-grained control of presence and location systems. New Deactivate/Activate and Mass Timer Extension operators may be applied simultaneously to large numbers of tuples and anti-tuples, thereby improving system responsiveness. A new Query operator greatly increases the ability of presence and location systems to guarantee that private information in the tuple space remains private. Claims What is claimed is: Description FIELD OF THE INVENTION
Number of Key-Value Pairs Number of key-value pairs in the tuple
Activated Flag If set the tuple is activated and can be used
in a search process. If not set, the tuple is
inactive and will be excluded from any
search process.
Starting address Location in memory for the start of the
tuple
Tuple Length Length of tuple in words
Time Out Value Absolute system time when tuple is to be
automatically cancelled
Cancel Flag Set if the tuple is to cancelled and removed
from memory
The TAM arrays 16 and 18 can be used to speed up the matching process of the tuple space. In particular, each TAM array holds information about the tuple in addition to the starting point in memory. Tuples/anti-tuples will match only if they contain the same number of key value pairs. This information can be obtained easily from the incoming tuple/anti-tuple and matched against the information in the array. Only the tuples in which the numbers of key/value pairs match are considered for further matching by accessing the tuples themselves in memory. Thus, by having tuples that differ in the number of key-value fields to identify specific classes, only those tuples with the same number of these fields will be compared. By deliberately sizing tuples to differentiate them according to class, enhanced search speed is achieved. According to the present invention, tuples and anti-tuples may be activated or deactivated by using the ACT and DEACT operators (i.e. marked so that they will be included in or excluded from the matching process). If the activated flag is set the tuple is included in the matching process. If it is not set then it is excluded from the process. Use of the ACT and DEACT operators improves system speed and responsivity for applications in which large numbers of tuples or anti-tuples are used for collaboration in different system states. Instead of wasting time removing and entering tuples and anti-tuples at each change of state, they may be activated or deactivated en masse. Tuples and anti-tuples are stored in their respective memories 12 and 14 in contiguous groupings starting at the top of each memory. All lower tuples are moved up to fill in the gaps in the groupings created by cancelled tuples. New tuples are then inserted at the bottom of the memory. When a new tuple of unknown length is obtained, no action needs to be taken to find an appropriately sized space in memory to hold it, in contrast with the prior art hardware-based systems discussed above. Instead, the tuple is placed at the bottom of the memory. This is also in contrast to software-based memory management techniques in which fragmentation is a major and common problem consuming much real time processing. By tracking a Time Out Value for each tuple, an efficient timer-based garbage collection process is provided to handle the problem of orphan tuples whose owner objects have terminated or erroneously forgotten about them. These tuples can fill the memory, which causes management problems requiring software intervention and periodic re-initiation of the space. According to the present invention the Time Out Values are implemented in hardware. Expired tuples are simply marked as cancelled and then removed from memory automatically by the Memory Management process of block 10, as described in greater detail below. Tuples are stored in the tuple memory 12 such that individual keys and values may be determined by the Search Logic of block 10. There are several well-known methods for accomplishing this function, including the use of special delimiting flags, assignment on fixed relative memory locations such as word boundaries, etc. The details of how tuples are determined are not important to the present invention. A particular implementation is set forth below. Operation of the hardware-assisted tuple space with which the operators of the present invention are applied, is set forth below with reference to a typical Pick operation. The operations for Poke, Peek and Cancel are similar and would be obvious to a person skilled in the art upon reading this specification. With the Peek operation, an anti-tuple is received from an external process and placed in the Input/Output buffers of block 10. The attributes described above for the incoming anti-tuple are then extracted and matched in turn by the Search Logic of block 10 against the attributes of the tuples stored in TTAM 16. Initially the state of the ACTIVATE flag is checked. If for a particular tuple it is not set, the tuple is deactivated and is not to be used for matching as described above. In this case the search moves to the next tuple. If for this next tuple the ACTIVATE flag is set, the tuple is to be used for matching, etc. Next, the Number of Key-Value Pairs attributes of the anti-tuple and selected tuple are compared. If these do not match then there is no possibility of a tuple match and the search moves to the next tuple in turn. It will be seen that matching attributes results in a quick search that increases the overall speed of the search by excluding impossible matches. The ordering of these checks is not important and may be reversed in implementation. Analysis of specific applications may reveal that more time in searching may be saved in searching by one ordering sequence or another. This ordering is therefore application specific and may be optionally selected by the user with logic in the device if needed. If the preliminary match succeeds, the Search Logic executes a conventional sequential search wherein keys and values for the tuple are extracted in turn from the tuple memory 12 and matched against the corresponding locations in the received anti-tuple. This matching begins at the location in memory indicated by the TTAM starting address attribute for the tuple. The search continues location-by-location until either the end of the tuple is reached, which indicates that a match has been found, or the first mismatch is found. If a mismatch is found then the Search Logic examines the next tuple. Since this is a Pick operation, if a match is found a copy of the tuple is moved to the I/O Buffers and the Cancel flag is set in the TTAM location for the matched tuple. The tuple value in I/O is used at the end of the process to return the matched tuple to the requesting process. The set Cancel flag indicates to the Search Logic that the tuple is to be removed from memory (described in detail below with reference to the memory management section). The search continues tuple-by-tuple until all of the tuple attributes in TTAM 16 have been checked. At the end of the process the attributes of the received anti-tuple are placed at the bottom of the ATAM memory 18 and the anti-tuple itself is placed at the bottom of the anti-tuple memory 14. The memory management process is then applied to the contents of the tuple memory and the ATAM memory, as described in greater detail below. The algorithms set forth above can be used in parallel across more than one copy of the memory elements in the block diagram. In such as case, the TAM, ATAM tuple memory and anti-tuple memory elements are replicated as needed and the I/O element is modified to accommodate returned tuples from all of the memory blocks and to select the most suitable memory block to store the incoming tuple or anti-tuple. When the DEACT or ACT operator is introduced into the space, it is matched against the attributes in ATAM memory 18. Any attribute which matches the template will have its Activate flag reset to the appropriate state. In subsequent searches when new tuples are submitted, attributes for the anti-tuples with the Activate flag reset by a DEACT operator will not be matched against the tuple. In matching a newly submitted tuple with a stored anti-tuple, the state of the ASSOCIATED Activate flag is checked before field-by-field tuple matching is performed. If the Activate flag has been reset by the DEACT operator, the matching process is aborted. The process for activating and deactivating tuples follows an identical pattern with matching of newly submitted anti-tuples with tuples dependent on the state of the Activate flag stored with the tuple attribute in TTAM 16. The structure of the new operators according to the present invention is as follows: OPERATOR [Optional Parameters] Tuple or Anti-tuple Thus, the DEACT operator for a tuple is of the form: <DEACT_FLAG><NUMBER OF FIELDS><TUPLE> The ACT operator for a tuple is of the form: (ACT FLAG><NUMBER OF FIELDS><TUPLE> The ACT and DEACT operators for anti-tuples follows the same format. As discussed above, for fine-grained control typically a large number of tuples and anti-tuples are active in a specific state. Also, there are typically multiple states for the system. The Deactivate/Activate flag allows for a many tuples and anti-tuples to be activated or deactivated within the tuple space without requiring that they be placed into the space one at a time by the appropriate post, pick or peek operations. Consequently, state change context switching can be done in much less time than is possible according to the prior art. In a typical application, all tuples and anti-tuples for all states are input to the tuple space at set-up time in a manner similar to an initial program load. The tuples are then only deactivated and activated as needed. As discussed above, tuples and anti-tuples are supplied with a time to live parameter (i.e. Time-Out Value stored in TAM). This is conventional and is found in many implementations in order to preserve the performance of the tuple space against orphan tuples and anti-tuples which have been placed into the space and are no longer needed. This is analogous to garbage collection in object-oriented systems (i.e. objects that are not in use are autonomously removed). Likewise, in the present invention an autonomous process searches both the tuple memory and anti-tuple memory for tuples and anti-tuples that have expired. If the search detects that a tuple or anti-tuple has a time to live parameter that is earlier than the current system time, it is removed. However, according to the present invention, specific operators are provided: one to extend tuples (TUPLE EXTEND) and the other to extend anti-tuples (ANTI-TUPLE EXTEND). Each operator is issued with a parameter that indicates the amount of time that the tuple or anti-tuple is to be extended. Thus, in the situation where a process may wish to extend the life of its tuples and anti-tuples the operator is supplied with a template (i.e. the structure of the fixed and don't care fields) that is matched against tuples or anti-tuples as needed. On the occurrence of matched tuples or anti-tuples, the time to live field receives the value of the extension field in the incoming operator added to it. The structure of the TUPLE EXTEND operator is as follows: <TUPLE_EXTEND><EXTENSION VALUE><TUPLE> The structure of the ANTI-TUPLE EXTEND is as follows: <ANTI-TUPLE EXTEND><EXTENSION VALUE><ANTI-TUPLE> The Mass Timer Extension of the present invention allows large numbers of tuples or anti-tuples to be identified at one time and to have their time to live parameters extended. In conventional systems this process is required to be performed one tuple/anti-tuple at a time with the appropriate post, peek and pick operators thereby decreasing the responsivity of the system and making it less suitable for fine-grained operation. The Query operation according to the present invention is very valuable for tuple spaces that are used for private information and/or are used in an open environment. In such environments, it is possible for an intruder to insert an anti-tuple in the space in order to retrieve private information about a person (e.g. the person's location, which could be used by a stalker to track a victim). The Query operator provides a fail-safe mechanism to overcome this problem. QUERY searches through the anti-tuple memory and returns all anti-tuples which match the template supplied with the operator. Thus, using the example tuple given above, John Doe whishes to find all anti-tuples that are subscribed to his name, he can use this operator with a template that has his name as fixed and the remainder as "don't cares". If the QUERY operator detects an unauthorized anti-tuple, the process removes the anti-tuple using a Cancel operation and reports the infraction to a management application. Thus, the Query operator provides a fail safe enforcement strategy that detects and removes all illicit anti-tuples. Variations and modifications of the invention are contemplated.All such alternative embodiments are believed to fall within the sphere and scope of the invention as defined by the appended claims.
|
Same subclass Same class Consider this |
||||||||||