News Column

Patent Issued for Scanning a Message-List

September 2, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- According to news reporting originating from Alexandria, Virginia, by VerticalNews journalists, a patent by the inventors Meiri, David (Boston, MA); Arnon, Dan (Boston, MA); Halstead, Mark J. (Waltham, MA); Kamvysselis, Peter (Boston, MA), filed on March 18, 2005, was published online on August 19, 2014.

The assignee for this patent, patent number 8812595, is EMC Corporation (Hopkinton, MA).

Reporters obtained the following quote from the background information supplied by the inventors: "A distributed computer system includes several processors that cooperate to perform a task. To cooperate more effectively, the processors often send messages to each other. One method of sending a message from one processor to another is to maintain a message-list in a memory that is accessible to all the processors. Each processor can periodically scan this message-list for messages. A processor can thus post a message in that message-list. Eventually, the processor for which that message is intended will scan the message-list and encounter that message.

"The message-list is typically an ordered sequence of messages having a first message and a last message. These messages are arranged in the order in which a scanning processor will encounter them. In most cases, the messages are arranged in chronological order, with the oldest message being at the beginning of the message-list and the most recently posted messages near the end of the message-list.

"A scanning processor typically scans a message-list by beginning at the first message and proceeding sequentially through the message-list until it either reaches the last message or until it encounters a message for which it is an intended recipient. This ensures that the scanning processor will encounter older messages before it encounters newer messages. If the scanning processor encounters a message for which it is an intended recipient, it interrupts its scan to retrieve and process that message. The next time the scanning processor scans the message-list, it begins again at the first message of the message-list. This simple scanning method guarantees that the scanning processor will always encounter older messages before it encounters newer messages.

"One property of this scanning method is that a scanning processor may inspect messages far more often than necessary. In particular, messages near the beginning of the message-list are likely to be repeatedly inspected. Where the distributed computing system has only a small number of processors, the message-list is not very long. Hence, the repeated inspection of messages near the beginning of the message list does not consume appreciable amounts of time.

"As distributed computing systems have become more complex, the number of processors within such systems has grown. As a result, the message-lists in such systems have lengthened. Because of this, the time spent unnecessarily re-inspecting messages has become more significant."

In addition to obtaining background information on this patent, VerticalNews editors also obtained the inventors' summary information for this patent: "In a distributed computing system according to the invention, a scanning processor's next scan of the message-list begins where its previous scan left off. As a result, the scanning processor avoids unnecessarily inspecting messages that it may have already inspected during a previous scan. In one optional feature of the invention, the scanning processor periodically begins its next scan at the beginning of the message list instead of where its previous scan left off.

"In a system incorporating the invention, a scanning processor selected from a plurality of processors having access to a message list identifies, in the message-list, a message-slot containing a message for which it is an intended recipient. The scanning processor then obtains, from the identified message-slot, information indicative of a location of a succeeding message-slot in the message-list. The scanning processor then caches this information for retrieval during a subsequent scan of the message-list.

"In one aspect of the invention, a next-message pointer associated with the identified message slot embodies information indicative of the location of a succeeding message-slot in the message-list. This information provides the scanning processor with a starting location for beginning a subsequent scan of the message-list.

"The information indicative of the succeeding message slot in the message-list is typically cached in a memory that is local to the scanning processor. However, this information can also be cached in any location accessible to the scanning processor when a subsequent scan of the message-list is to begin.

"To avoid skipping over one or more message slots in the message-list, the scanning method can also include a test for the existence of a reset condition. If the scanning processor detects the occurrence of a reset condition, it begins its next scan of the message-list at the beginning of the message-list instead of where the previous scan left off. This can be implemented by storing information indicative of the location of the succeeding message slot only in the absence of a reset condition. Alternatively, this can be achieved by storing a pointer to the first message on the message-list whenever a reset condition occurs.

"One possible reset condition arises when the information indicative of the location of the succeeding message slot identifies an invalid location. Another possible reset condition arises when a number of scans since a previous occurrence of a reset condition exceeds a reset threshold. This reset threshold can be a fixed, pre-selected reset threshold, or an adaptively selected reset threshold whose value depends upon the likelihood with which the scanning processor will skip over one or more slots in the message-list.

"To scan a message-list accessible to a plurality of processors, a scanning processor retrieves, from its cache, information identifying a starting message-slot. This information can be a pointer to a message subsequent to a previous message intended for the scanning processor. The scanning processor then begins scanning the message-list at this starting message-slot.

"In one practice of the invention, the scanning processor begins a scan of the message-list by determining whether a reset condition exists. The scanning processor then proceeds with scanning the message-list at the starting message-slot if no reset condition exists. A reset condition can be deemed to exist when the information indicative of the location of the starting message-slot identifies an invalid location. Alternatively, a reset condition can be deemed to exist when a number of scans since a previous occurrence of a reset condition exceeds a reset threshold.

"A data-storage system according to the invention includes: a plurality of processors, each of which has a local memory; a shared memory accessible to each processor in the plurality of processors; and a message section maintained in the shared memory. The message section includes a message-list having an ordered sequence of message-slots, each of which includes information identifying a succeeding slot in the message-list.

"The local memory associated with each processor can include a cache for storage of information identifying a succeeding slot. This cache can include a look-ahead pointer that identifies the succeeding message-slot.

"In one embodiment of the data-storage system, the cache includes a counter indicating an interval since a scanning processor encountered a message-slot containing a message for which that scanning processor was an intended recipient. Such a counter can indicate a number of scans since a scanning processor encountered a message-slot containing a message for which that scanning processor was an intended recipient.

"The local memory of a processor from the data-storage system according to the invention can also include a reset-detecting process configured to detect a reset condition. In one embodiment, the reset-detecting process is configured to compare a reset threshold with an interval since a scanning processor encountered a message-slot containing a message for which that scanning processor was an intended recipient. The reset threshold can be a pre-specified constant or an adaptively determined quantity whose value depends upon the operating characteristics of the data-storage system. In another embodiment, the reset-detecting process is configured to detect whether the information identifying a succeeding slot in the message-slot is invalid.

"These and other features of the invention will be apparent from the following detailed description and the accompanying figures, in which:

BRIEF DESCRIPTION OF THE FIGURES

"FIG. 1 shows a data-storage system for implementing the messaging system of the invention;

"FIG. 2 shows the configuration of the shared memory in FIG. 1;

"FIG. 3 shows the message section of FIG. 2;

"FIG. 4 is a flowchart of a process for adding a new message to the message-list in FIG. 3;

"FIG. 5 shows the message-list of FIG. 3 before adding a new message;

"FIG. 6 shows the message-list of FIG. 5 after adding a new message;

"FIG. 7 shows the three states of each scan cycle;

"FIG. 8 is a flow-chart of a scanning method that does not include a test for a reset condition;

"FIG. 9 shows representative scan cycles in which the scan-states are of substantially equal length;

"FIG. 10 is a flow-chart of a scanning method that includes a test for a reset condition;

"FIG. 11 shows a scanning processor configured to carry out the scanning methods shown in FIG. 8 or 10;

"FIG. 12 shows the link structure of a representative message-list;

"FIG. 13 shows the link structure of the message-list of FIG. 11 after having been re-structured by other processors;

"FIG. 14 is a flowchart of a process for removing a message from the message-list of FIG. 3;

"FIG. 15 shows the message-list of FIG. 3 before removing a message; and

"FIG. 16 shows the message-list of FIG. 3 after removing a message."

For more information, see this patent: Meiri, David; Arnon, Dan; Halstead, Mark J.; Kamvysselis, Peter. Scanning a Message-List. U.S. Patent Number 8812595, filed March 18, 2005, and published online on August 19, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8812595.PN.&OS=PN/8812595RS=PN/8812595

Keywords for this news article include: EMC Corporation, Information Technology, Information and Data Storage.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters