System for scheduling serial message transmission on a bus which is adoptable for rescheduling prioritized messages using a doubly-linked list

• US 4,896,261 A
• Filed: 11/24/1986
• Issued: 01/23/1990
• Est. Priority Date: 11/24/1986
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Nolan, Michael P.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Munteanu-R, Florin
• Application Number:
  US06/934,057
• Time in Patent Office: 1,156 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 340/825.5, 370/85, 371/32, 371/33
• US Class Current: 710/107
• CPC Class Codes: G06F 13/38 Information transfer, e.g. on bus G06F13/14 takes precedence

Abstract

A system (10) for scheduling serial message transmission on a single bus (11) having a plurality of messages to be sent stored in memory (21) with each message located between associated start and end message addresses (START, END). A message list or queue (28) of the messages to be sent is formed and stored in memory (22) wherein the list comprises message pointer blocks (27) associated with each of the messages. Each pointer block includes at least the message start and end addresses, the message unique ID code (MID), the message priority (PRI), the address of the message pointer block associated with the next message to be sent (NEXT) and the address of the message pointer block associated with the previous message to be sent (PREV). A message transmission apparatus (16, 17, 18, 19) then sequentially serially transmits the messages on the bus in accordance with the message transmission order specified in the message list. New messages are scheduled for transmission by appropriately linking a new message pointer block to the lift, and previously sent messages are rescheduled for retransmission by delinking the previous message pointer block and relinking it further down the list. The system eliminates the need for storing sent messages in buffer memory in the event a message is improperly sent and must be resent, and no movement of actual messages in memory is required to alter the message transmission sequence since this is accomplished by just appropriately relinking message pointer blocks in the list.

Claims

1. System for scheduling serial message transmission on a single bus, comprising:

means for storing in a memory a plurality of messages to be sent, each message being stored in sequential address locations in said memory between a corresponding message start address and a corresponding message end address;

means for storing in a memory a list (queue) of said messages, said list comprising a plurality of message pointer blocks each corresponding to, and thereby identifying, one of said messages, each pointer block including at least the following information, the message start address of the message corresponding to the pointer block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the pointer block corresponding to the previous message to be sent;

message transmission means, coupled to said message storing means and said message list storing means, for sequentially serially transmitting said messages on a bus in accordance with the next message transmission order specified in said list; and

means, coupled to said message list storing means, for adding a new message to be transmitted by said transmission means by adding a corresponding new message block, which identifies the new message, to said list and altering two of said pointer blocks previously on said message list to refer to the address of said new block, said new block including at least the following information, the message start address of the new message corresponding to the new block, the address of the pointer block corresponding to the next message scheduled to be sent and the address of the pointer block corresponding to the previous message to be sent,

said system including means for rescheduling, in response to reception of a repeat request, a previously-sent message for retransmission, wherein rescheduling occurs by utilization of said message list to identify the message pointer block corresponding to the message to be resent, and effectively adding said identified message pointer block to said list as a new block corresponding to a message to be sent,

wherein said rescheduling means includes means for, after identifying the message pointer block in said list corresponding to the message to be resent, increasing priority date corresponding to said identified pointer block, such increased priority data being compared to priority data corresponding other pointer blocks on said list when adding said identified block to said list as a new block of a message to be sent to determine where on said list said new block should effectively be added.

2. System for rescheduling serial message transmission on a single bus, comprising:

means for storing in a memory a plurality of messages to be sent, each message being stored in sequential address locations in said memory between a corresponding message start address and a corresponding message end address;

means for storing in a memory a list (queue) of said messages, said list comprising a plurality of message pointer blocks each corresponding to, and thereby identifying, one of said messages, each pointer block including at least the following information, the message start address of the message corresponding to the pointer block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the pointer block corresponding to the previous message to be sent;

message transmission means, coupled to said message storing means and said message list storing means, for sequentially serially transmitting said messages on a bus in accordance with the next message transmission order specified in said list; and

means, coupled to said message list storing means, for adding a new message to be transmitted by said transmission means by adding a corresponding new message block, which identifies the new message, to said list and altering two of said pointer blocks previously on said message list to refer to the address of said new block, said new block including at least the following information, the message start address of the new message corresponding to the new block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the pointer block corresponding to the previous message to be sent,

wherein each of said message pointer blocks includes the message end address of the message corresponding to the pointer block, wherein each message includes a check sum byte therein associated with the message, and wherein said check sum byte is located at the message end address corresponding to the message.

3. System for scheduling serial message transmission according to claim 2 wherein each message includes therein a unique message identification byte (MID) associated with the message.

4. System for scheduling serial message transmission according to claim 3 wherein said MID is located at the message start address of the message.

5. System for scheduling serial message transmission on a single bus, comprising:

means for storing in memory a plurality of messages to be sent, each message being stored in sequential address locations in said memory between a corresponding message start address and a corresponding message end address;

means for storing in a memory a list (queue) of said messages, said list comprising a plurality of memory pointer blocks each corresponding to, and thereby identifying, one of said message pointer blocks including at least the following information, the message start address of the message corresponding to the pointer block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the pointer block corresponding to the previous message to be sent;

message transmission means, coupled to said message storing means and said message list storing means, for sequentially serially transmitting said messages on a bus in accordance with the next message transmission order specified in said list; and

means, coupled to said message list storing means, for adding a new message to be transmitted by said transmission means by adding a corresponding new message block, which identifies the new message, to said list and altering two of said pointer blocks previously on said message list to refer to the address of said new block, said new block including at least the following information, the message start address of the new message corresponding to the new block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the pointer block corresponding to the previous message to be sent,

said system including means for rescheduling, in response to reception of a repeat request, a previously-sent message for retransmission, wherein rescheduling occurs by utilization of said message list to identify the message point block corresponding to the message to be resent, and effectively adding said identified message pointer block to said list as a new block corresponding to a message to be sent, said system also includes a transmit pointer means for effectively keeping track of which pointer block in said message list corresponds to the next scheduled message to be sent.

6. System for scheduling serial message transmission according to claim 5 wherein said rescheduling means includes means for effectively searching said message list backwards from the message pointer block referred to by said transmit pointer means for the message pointer block corresponding to the message to be resent.

7. System for scheduling serial message transmission according to claim 6 wherein said means for adding said identified message pointer block to said message list as a new block includes means for adding said identified block to said list at a position no earlier than the message block which precedes the message block referred to by said transmit pointer means.

8. System for scheduling serial message transmission according to claim 7 wherein said rescheduling means includes means for removing said identified message pointer block from said message list from a position prior to the message pointer block referred to by said transmit pointer means.

9. Method for scheduling serial message transmission on a single bus, comprising the steps of:

storing in a memory a plurality of messages to be sent, each message being stored in sequential address locations in said memory between a corresponding message start address and a corresponding message end address;

storing in a memory a list (queue) of said messages, said list comprising a plurality of message pointer blocks each corresponding to one of said messages, each pointer block including at least the following information, the message start address of the message corresponding to the pointer block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the pointer block corresponding to the previous message to be sent;

sequentially serially transmitting said messages on a bus in accordance with the next message transmission order specified in said list; and

adding a new message to be transmitted by adding a corresponding new message block, which identifies the new message, to said list and altering at least one of said pointer blocks previously on said message list to refer to the address of said new block, said new block including at least the following information, the message start address of the new message corresponding to the new block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the pointer block corresponding to the previous message to be sent,

said method includes the step of rescheduling, in response to reception of a repeat request, a previously-sent message for retransmission, wherein rescheduling occurs by utilization of said message list to identify the message pointer block corresponding to the message to be resent, and effectively adding said identified message pointer block to said list as a new block corresponding to a message to be sent, wherein said rescheduling step includes the step of, after identifying the message pointer block in said list corresponding to the message to be resent, increasing priority data corresponding said identified pointer block, such increased priority data being compared to priority data corresponding to other pointer blocks on said list when adding said identified block to said list as a new block of a message to be sent to determine where on said list said new block should effectively be added.

10. Method for scheduling serial message transmission on a single bus, comprising the steps of:

storing in a memory a plurality of messages to be sent, each message being stored in sequential address locations in said memory between a corresponding message start address and a corresponding message end address;

storing in a memory a list (queue) of said messages, said list comprising a plurality of message pointer blocks each corresponding to, and thereby identifying, one of said messages, each pointer block including at least the following information, the message start address of the message corresponding to the point block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the point block corresponding to the previous message to be sent;

sequentially serially transmitting said messages on a bus in accordance with the next message transmission order specified in said list; and

adding a new message to be transmitted by adding an associated new message block, which identifies the new message, to said list and altering at least one of said pointer blocks previously on said message list to refer to the address of said new block, said new block including at least the following information, the message start address of the new message corresponding to the new block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the pointer block corresponding to the previous message to be sent, wherein each of said message pointer blocks includes the message end address of the message corresponding to the pointer block, and

wherein each message includes a check sum byte therein associated with the message and wherein said check sum byte is located at the message end address corresponding to the message.

11. Method for scheduling serial message transmission according to claim 10 wherein each message includes therein a unique message identification byte (MID) associated with the message and wherein said MID is located at the message start address of the message.

12. Method for scheduling serial message transmission on a single bus, comprising the steps of:

storing in a memory a plurality of messages to be sent, each message being stored in sequential address locations in said memory between a corresponding message start address and a corresponding message end address;

storing in a memory a list (queue) of said messages, said list comprising a plurality of message pointer blocks each corresponding to, and thereby identifying, one of said messages, each pointer block including at least the following information, the message start address of the message corresponding to the pointer block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the pointer block corresponding to the previous message to be sent;

sequentially serially transmitting said messages on a bus in accordance with the next message transmission order specified in said list; and

adding a new message to be transmitted by adding an associated new message block, which identifies the new message, to said list and altering at least one of said pointer blocks previously on said message list to refer to the address of said new block, said new block including at least the following information, the message start address of the new message corresponding to the new block, the address of the pointer block corresponding to the next message scheduled to be sent, and the address of the pointer block associated with the previous message to be sent,

said method includes the step of rescheduling, in response to reception of a repeat request, a previously-sent message for retransmission, wherein rescheduling occurs by utilization of said message list to identify the message pointer block associated with the message to be resent, and effectively adding said identified message pointer block to said list as a new block associated with a message to be sent,

said method also includes the step of effectively keeping track of which pointer block in said message list corresponds to the next message scheduled to be sent.

13. Method for scheduling serial message transmission according to claim 12 wherein said rescheduling step includes the step of effectively searching said message list backwards, from no later than the message pointer block corresponding to the next message scheduled to be sent, for the message pointer block corresponding to the message to be resent.

14. Method for scheduling serial message transmission according to claim 13 wherein said step of adding said identified message pointer block to said message list as a new block comprises adding said identified block to said list at a position no earlier than the message block which precedes the message block corresponding to the next message scheduled to be sent.

15. Method for scheduling serial message transmission according to claim 14 wherein said rescheduling step includes the step of removing said identified message pointer block from said message list from a position prior to the message pointer block corresponding to the next message scheduled to be sent.