Message FIFO empty early warning method

Details Message FIFO empty early warning method Message FIFO empty early warning method

1997-03-21

2002-11-05

Courtney, III, St. John (Department: 2151)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C710S053000, C710S056000, C710S057000

Reexamination Certificate

active

06477584

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to message passing interfaces between either hardware or software modules. More specifically, the present invention relates to a method for remedying a condition wherein a number of available free messages has dropped below a predetermined level.
2. Previous Art
Modules often are required to communicate with other modules. For example, a host software module is often required to communicate with other software modules, such as an I/O peripheral software driver, or another host software module. As modern applications require increasing amounts of data to be transferred efficiently, at a continuous rate and in a predictable manner, the demands placed on such software modules increases. Various message passing protocols have been developed to facilitate communication between modules, both to facilitate portability of software module across operating systems and to contribute to the development of intelligent, distributed I/O processing. By utilizing a standard message passing interface, modules can be designed independent of both the underlying bus architecture and the specific operating system used. Moreover, by imbuing the modules with added intelligence and autonomy, the burden of the other modules, memory and system bus can be lessened, thus freeing them for other tasks. A message passing protocol can be thought of as an intermediary separating one module from another module which facilitates the exchange of data and control information. A specific implementation of such a message passing protocol includes one inbound and one outbound logical queue for each module of a pair of modules. The inbound logical queue of each module receives all messages targeted for that module, whereas the outbound queue of each module receives all messages processed by that module. The inbound queue of one module is the outbound queue of the other module.
The inbound and outbound queues would each be implemented as a pair of first-in-first-out registers, or FIFOs. Each of the inbound and outbound queues would have a Work FIFO where message frames are posted for processing and a Free FIFO that contains empty message frames that are available for use. A Requesting Module removes a message from the Free FIFO, processes the message, and then posts the message on the Work FIFO. The Receiving Module retrieves the message from the Work FIFO, processes the message and places the message on the Free FIFO.
During initialization of such a message interface, free messages are posted in the Free FIFO. When the Requesting Module removes messages from the Free FIFO, the number of free messages in the free FIFO is reduced. As the Receiving Module processes messages retrieved from the Work FIFO, free messages are posted on the Free FIFO. If the Receiving Module is slower than the Requesting Module in processing messages, free messages will become exhausted in the Free FIFO, and the Requesting Module will be forced to stall, waiting on the availability of free messages in the Free FIFO. Moreover, since there are no free messages left in the Free FIFO at that time, the Receiving Module will not be able to appropriate one to send a message to the Requesting Module to the effect that the Free FIFO is empty. The system constituted by the Requesting and the Receiving Module is now deadlocked, because the Requesting Module can no longer post messages to the Receiving Module's work FIFO, as there are no free messages available to process. Within the context of message passing interfaces, this situation is known as message starvation. The Receiving Module, also lacking free messages because all of the messages reside on the work FIFO, is unable to communicate with the Requesting Module until it has finished processing messages in its Work FIFO and has posted additional Free messages on the Free FIFO.
There exists a need, therefore, for a method which would alleviate the problems inherent in such message passing systems. In particular, there exists a long felt need for a solution to the problems of deadlock and free message starvation between pairs of modules separated by such a message passing interface.
Previous attempts to solve similar problems have depended upon additional circuitry to regulate the transfer rates of data between the software modules, or have relied upon a scheme which prioritizes requests according to some pre-established hierarchy. An example of the former approach is disclosed in U.S. Pat. No. 5,434,892 to Dyke et al. In Dyke et al., to account for different data transfer rates, a throttle circuit is interposed between two devices to throttle the data transmission between a buffer and a register circuit upon receipt of a Buffer Almost Empty Signal, and to stop data transmission upon receipt of a Buffer Empty signal. This method, however, is not optimal, as it tends to actively slow the system down to match the speed of the slowest member of the system, in order to prevent the transmission of invalid data retrieved from an empty buffer.
Another example is disclosed in U.S. Pat. No. 4,272,819 to Katsumata et al. In Katsumata, communication between a host and an I/O subsystem is achieved by means of communication queues, each of the host and I/O subsystems having the ability to enqueue and to dequeue information onto the communication queues. When either the host or I/O subsystem issues an enqueue command, the queue element length is compared with the remaining space available in the queue. If the comparison satisfies a given criterion, a queue overflow state or a queue usable state is detected. When a queue is in an overflow state, it requests a queue usable interruption to a processor, when the remaining space in the queue increases. If this request is accepted, the queue is released from its overflow condition. Thus, communication between the host and the I/O subsystem is interrupted until the queue is released from its overflow condition.
What is desired, however, is to prevent the communication between a pair of software modules, such as a host and an I/O subsystem, from being interrupted, even temporarily.
What is also desired is a method of assuring continued processing of messages, even when one module is slower than the other, without throttling down one module to the rate of the slowest message processor.
What is also desired is a method of avoiding deadlock and free message starvation problems that can occur in message passing interfaces between modules, such as between individual I/O drivers in an operating system.
SUMMARY OF THE INVENTION
It is an object of this invention, therefore, to provide a method for assuring the continuous processing of messages in a message passing interface, even when one module of a pair of modules is slower in processing messages than the other module of the pair.
It is an additional object of this invention to prevent the message passing between a pair of modules from being interrupted when a supply of free messages for processing is exhausted.
In accordance with the above objects and those that will be mentioned and will become apparent below, in a message passing interface between a requesting module and a receiving module, each module having access to two queues in the message passing interface, each queue having a Work FIFO for containing message frames to be processed and a Free FIFO for containing empty message frames, a preferred embodiment of the present inventive method of assuring continuous processing of messages from the Work FIFO comprises the steps of:
monitoring a number of free messages in the Free FIFO;
determining when the number of free messages falls below a selectively determined early warning level;
alerting the receiving module when the number of free messages falls below the early warning level;
sending, by the receiving module, an early warning level signal to the requesting module;
posting additional free messages to the Free FIFO; and
processing, by the receiving module, of messages from the work FIFO,
whereby the requesting module is assured of

Affiliated with

Also associated with

Rating

Message FIFO empty early warning method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Message FIFO empty early warning method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Message FIFO empty early warning method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2984416