System for scheduling periodic events having varying rates by cascading a plurality of overlapping linked list data structure

• US 5,933,655 A
• Filed: 09/30/1996
• Issued: 08/03/1999
• Est. Priority Date: 09/30/1996
• Status: Expired due to Term

• Current Assignee: Allen-Bradley Company (Rockwell Automation, Inc.)
• Original Assignee: Allen-Bradley Company LLC (Rockwell Automation, Inc.)
• Inventors: Vrabec, Tina L., Boldt, Peter J., Wallaert, Amy J., Tutkovics, Scot A.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Kim, Harold J.
• Application Number:
  US08/724,100
• Time in Patent Office: 1,037 Days
• Field of Search: 364/260, 395/878, 395/880, 395/860, 395/892
• US Class Current: 710/60
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A system for scheduling periodic events having varying rates. The system uses a linked list type data structure and an array to schedule the plurality of events having varying rates. In a preferred embodiment of the invention, data items are scheduled for transfer during a plurality of data transfer intervals. The linked list type data structure is traversed for each data transfer interval to collect the data items requiring transfer.

Claims

1. A method for scheduling the transfer of data during a plurality of data transfer intervals on a computer network linking devices associated with an automated industrial process, said method comprising:

generating a cascading list comprised of a plurality of overlapping linked lists formed from a plurality of data cells associated with a plurality of data items, each of said data items being transferred during at least one of said data transfer intervals, the cascading list having a set of data items being common to a set of linked lists whereat the plurality of linked lists overlap;

traversing said cascading list for a respective data transfer intervals to collect said data items requiring transfer during said respective data transfer interval.

2. A method according to claim 1, wherein said cascading list is comprised of a plurality of overlapping linked lists, each said linked list having one or more linked data cells associated with data items requiring transfer during the same data transfer interval.

4. A method according to claim 1, wherein said linked data cells include a first field having a first pointer to a data item and a second field having a second pointer to a linked data cell in the cascading list or a NULL pointer.

5. A method according to claim 4, wherein said method further comprises the step of establishing an array to provide a plurality of entry pointers, each said entry pointer respectively pointing to a linked data cell in said cascading list associated with a first data item to be transferred during a respective data transfer interval.

3. A method for scheduling the transfer of data during a plurality of data transfer intervals on a computer network linking devices associated with an automated industrial process, said method comprising:

generating a cascading list comprised of plurality of overlapping linked lists formed from a plurality of data cells associated with a respective plurality of data items, each of said data items being transferred during at least one of said data transfer intervals, each said overlapping linked list having one or more linked data cells associated with data items requiring transfer during the same data transfer interval; and

,

traversing said cascading list for a respective data transfer interval to collect data items requiring transfer during said respective data transfer interval, wherein each of said linked lists consists of a set of linked data cells arranged in descending order, from data cells associated with data items having a low periodic-interval-time-repeat-period value indicating a low data transfer rate to data cells associated with data items having a high periodic-interval-time-repeat-period value indicating a high data transfer rate.

6. A method for scheduling the transfer of data during a plurality of data transfer intervals on a computer network linking devices associated with an automated industrial process, said method comprising:

generating a cascading list comprised of plurality of linked data cells associated with a respective plurality of data items, each of said data items being transferred during at least one of said data transfer intervals, each of said linked data cells including a first field having a first pointer to a data item and a second field having a second pointer to a linked data cell in the cascading list or a NULL pointer;

traversing said cascading list for a respective data transfer interval to collect data items requiring transfer during said respective data transfer interval by retrieving one to said plurality of entry pointers from said array to determine a starting position in said cascading list for a respective data transfer interval; and

,

establishing an array to provide a plurality of entry pointers, each said entry pointer respectively pointing to a linked data cell in said cascading list associated with a first data item to be transferred during a respective data transfer interval.

7. A method for scheduling the transfer of data during a plurality of data transfer intervals on a computer network linking devices associated with an automated industrial process, said method comprising:

generating a cascading list comprised of plurality of linked data cells associated with a respective plurality of data items, each of said data items being transferred during at least one of said data transfer intervals, each of said linked data cells including a first field having a first pointer to a data item and a second field having a second pointer to a linked data cell in the cascading list or a NULL pointer;

traversing said cascading list for a respective data transfer interval to collect data items requiring transfer during said respective data transfer interval; and

,

establishing an array to provide a plurality of entry pointers, each said entry pointer respectively pointing to a linked data cell in said cascading list associated with a first data item to be transferred during a respective data transfer interval, said array having a plurality of array data cells referenced by respective indices, wherein said indices are index numbers equal to the sum of a data transfer rate value and a value indicating a first data transfer interval for transfer of a data item, said plurality of array data cells having a pointer to a linked data cell in the cascading list or a NULL pointer.

8. A method according to claim 7, wherein said method further comprises the step of adding a new linked data cell to said cascading list, wherein said step of adding said new linked data cell includes the step of referencing said array to locate a position in said cascading list for said new linked data cell and resetting the second pointers of one or more existing linked data cells in said cascading list to point to said new linked data cell and setting the second pointer of the new linked data cell to point to a subsequent linked data cell in said cascading list or a NULL.

9. A method according to claim 7, wherein said method further comprises the step of deleting a linked data cell from said cascading list, wherein said step of deleting said linked data cell includes the step of referencing said array to locate said linked data cell to be deleted in said cascading list and resetting said second pointer of one or more linked data cells in said cascading list which previously pointed to said deleted linked data cell to point to the linked data cell in said cascading list said deleted linked data cell previously pointed to.

10. A method for scheduling the transfer of data during a plurality of data transfer intervals on a computer network linking devices for an automated industrial process, said method comprising:

generating a cascading list comprised of a plurality or overlapping linked lists, each overlapping linked list having at least one data cell, each of said data cells including a first pointer to a data item and a second pointer to another data cell or a NULL pointer indicating the end of the linked list, wherein each of said plurality of overlapping linked lists have data cells pointing to data items requiring transfer during the same data transfer interval and wherein at least two of said second pointers point to a single data item whereat said plurality of linked lists overlap; and

traversing one of said plurality of linked lists for each data transfer interval to collect the data items requiring transfer.

11. A method for scheduling periodic events occurring at various time intervals, said method comprising:

generating a plurality of overlapping linked lists having a plurality of linked data cells, each of said plurality of linked data cells being associated with an event, each of said plurality of overlapping linked lists being associated with events occurring during the same time interval, wherein multiple linked data cells are common to multiple linked lists whereat the multiple linked lists overlap;

traversing one of said plurality of overlapping linked lists for each time interval to execute the event.

12. A method according to claim 11, wherein said plurality of linked lists are overlapped to form a single cascading list.

13. A method according to claim 12, wherein said event is data collection of a data item.

14. A method according to claim 12, wherein said event is sampling of a data item.

15. A system for scheduling the transfer of data during a plurality of data transfer intervals on a computer network linking devices associated with an automated industrial process, said system comprising:

means for generating a cascading list comprised of a plurality of overlapping linked lists formed from a plurality of linked data cells, each of the plurality of linked data cells being associated with a corresponding plurality of data items, each of said plurality of data items being transferred during at least one of said data transfer intervals, the cascading list generated having a plurality of data items common to at least two linked lists whereat the at least two linked lists overlap; and

means for traversing said cascading list for a respective data transfer interval to collect said data items requiring transfer during said respective data transfer interval.

16. A system according to claim 15, wherein said system further comprises means of establishing an array to provide a plurality of entry pointers, each said entry pointer respectively pointing to a linked data cell in said cascading list associated with a first data item to be transferred during a respective data transfer interval.

17. A system according to claim 16, wherein said means of traversing said cascading list includes the step of retrieving one of said plurality of entry pointers from said array to determine a starting position in said cascading list for a respective data transfer interval.

18. A system according to claim 16, wherein said array has a plurality of array data cells referenced by respective indices, wherein said indices are index numbers equal to the sum of a data transfer rate value and a value indicating a first data transfer interval for transfer of a data item, said plurality of array data cells having a pointer to a linked data cell in the cascading list or a NULL pointer.

19. A system for scheduling the transfer of data during a plurality of data transfer intervals on a computer network linking devices for an automated industrial process, said system comprising:

means for generating a cascading list comprised of a plurality of overlapping linked lists, each overlapping linked list having at least one data cell, each of said data cells including a first pointer to a data item and a second pointer to another data cell or a NULL pointer indicating the end of the linked list, wherein each of said plurality overlapping linked lists have data cells pointing to data items requiring transfer during the same data transfer interval, and wherein at least two of said second pointers point to a single data item whereat the cascading list overlaps; and

means for traversing one of said plurality of linked lists for each data transfer interval to collect the data items requiring transfer.

20. A method for scheduling the transfer of data during a plurality of data transfer intervals on a computer network linking devices associated with an automated industrial process, the method comprising the steps of:

generating a cascading list comprised of a plurality of linked lists formed from a plurality of linked data cells associated respectively with a plurality of data items, each of said plurality of data items being transferred during at least one of said data transfer intervals, each of said plurality of linked lists including a set of linked data cells arranged in descending order from data cells associated with data items having a low data transfer rate to data cells associated with data items having a high data transfer rate;

for a first data transfer interval, traversing said cascading list to collect first data items requiring transfer during said first data transfer interval; and

,

establishing an array to provide a plurality of entry pointers, each of said plurality of entry pointers respectively pointing to a linked data cell in said cascading list associated with a first data item to be transferred during a respective data transfer interval, said array having a plurality of array data cells referenced by respective indices, wherein said indices are index numbers equal to the sum of a data transfer rate value and a value indicating a first data transfer interval for transfer of a data item, said plurality of array data cells having a pointer to a linked data cell in the cascading list or a NULL pointer.

21. The method for scheduling the transfer of data during a plurality of data transfer intervals according to claim 20 further comprising the step of adding a new linked data cell to said cascading list by referencing said array to locate a position in said cascading list for said new linked data cell and resetting the second pointers of one or more existing linked data cells in said cascading list to point to said new linked data cell and setting the second pointer of the new linked data cell to point to a subsequent linked data cell In said cascading list or a NULL.

22. A method for scheduling the transfer of data during a plurality of data transfer intervals according to claim 20 further comprising the step of deleting a linked data cell from said cascading list by referencing said array to locate said linked data cell to be deleted in said cascading list and resetting said second pointer of one or more linked data cells in said cascading list which previously pointed to said deleted linked data cell to point to the linked data cell in said cascading list said deleted linked data cell previously pointed to.

23. A method for scheduling the transfer of data during a plurality of data transfer intervals on a computer network linking devices associated with an automated industrial process, the method comprising the steps of:

generating a cascading list comprised of a plurality of linked lists formed from a plurality of linked data cells associated respectively with a plurality of data items, each of said plurality of data items being transferred during at least one of said date transfer intervals, each of said plurality of linked lists including a set of linked data cells arranged in descending order from data cells associated with data items having a low data transfer rate to data cells associated with data items having a high data transfer rate;

for a first data transfer interval, traversing said cascading list to collect first data items requiring transfer during said first data transfer interval; and

,

establishing an array to provide a plurality of entry pointers, each of said plurality of entry pointers respectively pointing to a linked data cell in said cascading list associated with a first data item to be transferred during a respective data transfer interval, said array including a plurality of array data cells having a pointer to a linked data cell in the cascading list or A NULL pointer.

24. The method for scheduling the transfer of data during a plurality of data transfer intervals according to claim 23 further comprising the step of adding a new linked data cell to said cascading list by referencing said array to locate a position in said cascading list for said new linked data cell and resetting the second pointers of one or more existing linked data cells in said cascading list to point to said new linked data cell and setting the second pointer of the new linked data cell to point to a subsequent linked data cell in said cascading list or a NULL.

25. A method for scheduling the transfer of data during a plurality of data transfer intervals according to claim 23 further comprising the step of deleting a linked data cell from said cascading list by referencing said array to locate said linked data cell to be deleted in said cascading list and resetting said second pointer of one or more linked data cells in said cascading list which previously pointed to said deleted linked data cell to point to the linked data cell in said cascading list said deleted linked data cell previously pointed to.