Methods and apparatus for regulating process state control messages
View Patent ↗In a data processing system, the flow of messages specifying the states of various processes in the system, is regulated using a first register which maintains a list of the current states of each process, and a queue. Whenever a process state message relating to a particular process arrives, the new state of that process is written into the current state register, and an item is placed in a queue. The item indicates the identity of the process concerned. When the item reaches the front of the queue, the current state of the process it identifies is read from the current state register and used to generate an output message. Flags can be used to reduce the redundancy of items in the queue and limit its size. The queue can be modified to cope with messages of differing priorities. To reduce memory requirements, the processes may be grouped into sets, so that each queue item relates to a set of processes.
1. A method of regulating the flow of process state control messages for indicating the state of a corresponding process between processors in a data processing system, each processor operating one or more processes, each process state control message relating to one of the processes and comprising (i) process identity data identifying that process and (ii) a process state value indicative of the state of that process,
the method being characterized by:
employing (a) a message address queue, said queue being operated as a first-in-first-out store, and each item in the queue comprising a process identity section which identifies one of the processes, (b) a current state random access memory having one element for each process, each element being for storing the current state of the respective process, and (c) a process pending flag memory having a flag for each process;
comprising repeatedly performing the steps of:
(a) receiving a process state control message;
(b) writing the process state value specified by the process state control message into the element of the current state random access memory corresponding to the process identified by the process identity data of the process state control message; and
(c) according to the state of the flag corresponding to that process, deciding whether to insert an item into the queue, and, if the decision is positive, (i) inserting into the queue an item identifying that process and (ii) updating the flag corresponding to that process to indicate the existence of the item; and
further comprising repeatedly performing the steps of:
(d) retrieving an item from the queue;
(e) retrieving the current state of the process identified by the item from the element of the current state random access memory corresponding to that process;
(f) using the retrieved state to generate an output message comprising the retrieved state and data identifying that process; and
(g) updating the flag for that process to remove the indication of the existence of the item such that the output message carries the latest state information regarding that process.
2. A method of regulating the flow of process state control messages for indicating the state of a corresponding process between processors in a data processing system, each processor operating one or more processes, each process state control message relating to one of the processes and comprising (i) process identity data identifying that process and (ii) a process state value indicative of the state of that process,
the method being characterized by:
employing (a) a message address queues being operated as a first-in-first-out store, and each item in the queue comprising a process identity section which identifies one of a plurality of predetermined sets of said processes, (b) a current state random access memory having one element for each process, each element being for storing the current state of the respective process, and (c) a process pending flag memory having a flag for each set of processes,
comprising repeatedly performing the steps of:
(a) receiving a process state control message;
(b) writing the process state value specified by the process state control message into the element of the current state random access memory corresponding to the process identified by the process identity data of the process state control message; and
(c) according to the state of the flag corresponding to that set of process, deciding whether to insert an item into the queue, and, if the decision is positive, (i) inserting into the queue an item identifying that process and (ii) updating the flag corresponding to the set including that process to indicate the existence of the item; and
further comprising repeatedly performing the steps of: retrieving an item from the queue; retrieving the current state of each process in the set of processes identified by the item from the corresponding elements of the current state random access memory; using the retrieved states to generate an output message comprising the retrieved states and data identifying the set of processes; and updating the flag for that set of processes to remove the indication of the existence of the item.
3. A method according to claim 2 in which there are a plurality of said message address queues, each corresponding to a predetermined respective priority level associated with at least one respective process state, the number of said flags for each set of processes being equal to the number of priority levels, the item generated from a received process state control message being written into the message address queue with the priority level associated with the process state value of the process state control message, and the existence of the item being specified by the pending flag corresponding to that priority level.
4. A method according to claim 2 in which each said set of processes includes a plurality of processes.
5. A method of communicating data cells comprising data and destination designation information over an interface from a network processor to destination devices, the method comprising receiving the data cells, defining input queues for storing the data cells, and using a data switch to interconnect the input queues with the destination devices, each input queue being administered by a flow control mechanism generating flow control messages comprising the identity and the occupancy state of the input queue for communication to the network processor, the method further comprising regulating the flow of said flow control messages by a method according to claim 1 , the flow control messages corresponding to the process state control messages, and for each flow control message the identity of the input queue corresponding to the process identity data of the process state control message and the occupancy state corresponding to the process state value of the process state control message.
6. A regulation device for regulating the flow of process state control messages for indicating the state of a corresponding process between a plurality of processors in a data processing system in which each processor operates one or more processes, and each process state control message relates to one of the processes and comprises (i) process identity data identifying that process and (ii) a process state value indicative of the state of that process,
the device being characterized by comprising:
(a) means defining a message address queue, said queue being operated as a first-in-first-out store, and each item in the queue comprising a process identity section, which identifies one of the processes;
(b) a current state random access memory having one element for each process, each element being for storing the current state of the respective process;
(c) a process pending flag memory having a flag for each process;
(d) an input processor arranged to
receive a process state control message,
write the process state value specified by the process state control message into the element of the current state random access memory corresponding to the process identified by the process identity data of the process state control message, and
according to the state of the flag corresponding to that process, decide whether to insert an item into the queue, and, if the decision is positive, (i) insert into the queue an item identifying that process and (ii) update the flag corresponding to that process to indicate the existence of the item; and
(e) an output processor arranged to retrieve an item from the queue, retrieve the state of the process identified by the item from the element of the current state random access memory corresponding to that process, use the retrieved state to generate an output message comprising the retrieved state and data identifying that process, and update the flag for that process to remove the indication of the existence of the item such that the output message carries the latest state information regarding that process.
7. A regulation device for regulating the flow of process state control messages for indicating the state of a corresponding process between a plurality of processors in a data processing system in which each processor operates one or more processes, and each process state control message relates to one of the processes and comprises (i) process identity data identifying that process and (ii) a process state value indicative of the state of that process,
the device being characterized by including:
(a) means defining a message address queue being operated as a first-in-first-out store, and each item in the message address queue comprising a process identity section which identifies one of a plurality of predetermined sets of said processes;
(b) a current state random access memory having one element for each process, each element being for storing the current state of the respective process;
(c) a process pending flag memory having a flag for each set of processes;
(d) an input processor arranged to: receive a process state control message;
write the process state value specified by the process state control message into the element of the current state random access memory corresponding to the process identified by the process identity data of the process state control message; and
according to the state of the flags corresponding to that process, decide whether to insert an item into one of the queues, and, if the decision is positive, (i) insert into the message address queue an item identifying that process and (ii) update the flag corresponding to the set including that process to indicate the existence of the item; and
(e) an output processor arranged to retrieve an item from one of the message address queues; retrieve the current state of each process in the set of processes identified by the item from the corresponding elements of the current state random access memory; use the retrieved states to generate an output message comprising the retrieved states and data identifying the set of processes; and update the flags for that set of processes to remove the indication of the existence of the item such that the output message carries the latest state information regarding that process.
8. A device according to claim 7 in which there are a plurality of said message address queues, each corresponding to a predetermined respective priority level associated with at least one respective process state, the number of said flags for each set of processes being equal to the number of priority levels, the input processor being arranged to generate the item from a received process state control message, place it in the queue with the priority level associated with the process state value of the process state control message, and specify the existence of the item by updating the pending flag corresponding to that priority level.
9. A device according to claim 7 in which each said set of processes includes a plurality of processes.
10. A switching system arranged to communicate data cells comprising data and destination designation information over an interface from a network processor to destination devices, the switching system comprising means for receiving the data cells, means for defining input queues for storing the data cells, and a data switch for interconnecting the input queues with the destination devices, each input queue being administered by a flow control mechanism generating flow control messages comprising the identity and the occupancy state of the input queue for communication to the network processor, the switching system further comprising a regulation device according to claim 6 , the flow control messages being transmitted to the regulation device as process state control messages, for each flow control message the identity of the input queue corresponding to the process identity data of the process state control message and the occupancy state corresponding to the process state value of the process state control message, the regulation device transmitting output messages to the network processor.
11. A method of communicating data cells comprising data and destination designation information over an interface from a network processor to destination devices, the method comprising receiving the data cells, defining input queues for storing the data cells, and using a data switch to interconnect the input queues with the destination devices, each input queue being administered by a flow control mechanism generating flow control messages comprising the identity and the occupancy state of the input queue for communication to the network processor, the method further comprising regulating the flow of said flow control messages by a method according to claim 2 , the flow control messages corresponding to the process state control messages, and for each flow control message the identity of the input queue corresponding to the process identity data of the process state control message and the occupancy state corresponding to the process state value of the process state control message.
12. A method of communicating data cells comprising data and destination designation information over an interface from a network processor to destination devices, the method comprising receiving the data cells, defining input queues for storing the data cells, and using a data switch to interconnect the input queues with the destination devices, each input queue being administered by a flow control mechanism generating flow control messages comprising the identity and the occupancy state of the input queue for communication to the network processor, the method further comprising regulating the flow of said flow control messages by a method according to claim 3 , the flow control messages corresponding to the process state control messages, and for each flow control message the identity of the input queue corresponding to the process identity data of the process state control message and the occupancy state corresponding to the process state value of the process state control message.
13. A method of communicating data cells comprising data and destination designation information over an interface from a network processor to destination devices, the method comprising receiving the data cells, defining input queues for storing the data cells, and using a data switch to interconnect the input queues with the destination devices, each input queue being administered by a flow control mechanism generating flow control messages comprising the identity and the occupancy state of the input queue for communication to the network processor, the method further comprising regulating the flow of said flow control messages by a method according to claim 4 , the flow control messages corresponding to the process state control messages, and for each flow control message the identity of the input queue corresponding to the process identity data of the process state control message and the occupancy state corresponding to the process state value of the process state control message.
14. A method of regulating flow of process state control messages for indicating a state of a corresponding process between processors in a data processing system operating one or more processes, the method comprising the steps of:
employing (a) a message address queue operated as a first-in-first-out store for a plurality of items, each item in the message address queue comprising a process identity section which identifies one of the processes, (b) a current state random access memory having an element for each process, each element being for storing a current state of the respective process, and (c) a process pending flag memory having a process pending flag for each process;
receiving a process state control message including process identity data identifying a respective process and a process state value indicative of a state of the respective process;
writing the process state value specified by the process state control message into an element of the current state random access memory corresponding to the process identified by the process identity data of the process state control message; and
deciding whether to insert an item into the message address queue responsive to a state of the process pending flag corresponding to that process, and, if the decision is positive, (i) inserting into the message address queue the item identifying that process and (ii) updating the process pending flag corresponding to that process to indicate the existence of the item.
15. A method according to claim 14 , the method further comprising repeatedly performing the steps of:
retrieving an item from the message address queue;
retrieving the current state of the process identified by the item from the element of the current state random access memory corresponding to that process so that an output message carries the latest state information regarding that process;
using the retrieved state to generate the output message comprising the retrieved current state and data identifying that process; and
updating the process pending flag for that process to remove the indication of the existence of the item in the message address queue.
16. A method according to claim 14 in which there are a plurality of said message address queues, each corresponding to a predetermined respective priority level associated with at least one respective process state, a number of said pending process flags for each process being equal to the number of priority levels, the item generated from a received process state control message being written into the message address queue with the priority level associated with the process state value of the process state control message, and the existence of the item being specified by the pending flag corresponding to that priority level.
17. A method of regulating flow of process state control messages for indicating a state of a corresponding process between processors in a data processing system operating one or more processes, the method comprising the steps of:
employing (a) a message address queue operated as a first-in-first-out store for a plurality of items, each item in the message address queue comprising a process identity section which identifies one of a plurality of predetermined sets of the processes, (b) a current state random access memory having an element for each process, each element being for storing a current state of the respective process, and (c) a process pending flag memory having one or more process pending flags for each set of process;
receiving a process state control message including process identity data identifying a respective process and a process state value indicative of a state of the respective process;
writing the process state value specified by the process state control message into an element of the current state random access memory corresponding to the process identified by the process identity data of the process state control message; and
deciding whether to insert an item into one of the message address queue responsive to a state of the process pending flag corresponding to that process, and, if the decision is positive, (i) inserting into the message address queue the item identifying that process and (ii) updating the process pending flag corresponding to that process to indicate the existence of the item.
18. A method according to claim 17 , the method further comprising repeatedly performing the steps of:
retrieving an item from the message address queue;
retrieving the current state of each process in the set of processes identified by the item from the corresponding elements of the current state random access memory so that an output message carries the latest state information regarding each process in the set of processes;
using the retrieved state to generate the output message comprising the retrieved current states and data identifying the set of processes; and
updating the process pending flag for the set of process to remove the indication of the existence of the item in the message address queue.
19. A method according to claim 17 in which there are a plurality of said message address queues, each corresponding to a predetermined respective priority level associated with at least one respective process state, a number of said pending process flags for each set of processes being equal to a number of priority levels, the item generated from a received process state control message being written into the message address queue with the priority level associated with the process state value of the process state control message, and the existence of the item being specified by the pending flag corresponding to that priority level.