US5528513A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Scheduling and admission control policy for a continuous media server
Assignee: Enterasys Networks Inc
•
Filing: 1993-11-04
•
Granted: 1996-06-18
•
Expires: 2013-11-04
Abstract
Abstract A scheduler with admissions control in a continuous media file server is presented. The scheduler supports multiple classes of tasks with diverse performance requirements. The scheduler is based on a combination of rate-monotonic and weighted round-robin scheduling schemes. Scheduling is accomplished in a hierarchical manner. Isochronous tasks have the highest priority and are scheduled first followed by real-time and general-purpose tasks. Isochronous tasks run periodically and are invoked by a timer interrupt set for each task. After scheduling the isochronous tasks, the scheduler alternates between the real-time tasks and the general-purpose tasks using a weighted round-robin scheme.
Inventors
- 👤 Lev Vaitzblit
- 👤 Kadangode K. Ramakrishnan
- 👤 Percy Tzelnic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 16:23
CPC Classifications
H; H04; H04L; H04L65/00; H04L65/80; H04L65/1066; H04L65/1101; H04L67/00; H04L67/50; H04L67/60; H04L67/61; H04L67/62; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/329; H04N; H04N7/00; H04N7/16; H04N7/173; H04N7/17309; H04N7/17336
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
94 words
A method for scheduling multiple tasks in a communications network, comprising: providing a server for scheduling said tasks; determining a first time interval during which said tasks are to be performed in said communications network; scheduling isochronous tasks, said isochronous tasks being highest priority tasks, to begin at selected time points within said first time interval; determining a plurality of free time intervals by identifying unused time in said first time interval which is not used by said isochronous tasks; scheduling lower priority tasks to begin running during ones of said free time intervals.
Claim 2
Independent Claim
94 words
A method for scheduling multiple tasks in a communications network, comprising: providing a server for scheduling said tasks; determining a first time interval during which said tasks are to be performed in said communications network; scheduling isochronous tasks, said isochronous tasks being highest priority tasks, to begin at selected time points within said first time interval; determining a plurality of free time intervals by identifying unused time in said first time interval which is not used by said isochronous tasks; scheduling lower priority tasks to begin running during ones of said free time intervals.
Claim 3
Dependent Claim
23 words
The method as in claim 1, further comprising: determining said plurality of free time intervals as fitting between ones of said isochronous tasks.
Claim 4
Dependent Claim
82 words
The method as in claim 1, further comprising: testing a new isochronous task for admission into said multiple tasks for which scheduling is done by: A. first, determining if there is enough said unused time for the new task to execute; B. second, determining if there is enough time for the isochronous tasks including said new isochronous task to execute by themselves; admitting said new isochronous task to be scheduled in the event that both condition A and B above are satisfied.
Claim 5
Dependent Claim
65 words
The method as in claim 1, further comprising: testing a new lower priority task for admission into said multiple tasks for which scheduling is done by determining if there is enough said unused time for the new task to execute; admitting said new lower priority task to be scheduled in the event that there is enough said unused time for the new task to execute.
Claim 6
Dependent Claim
49 words
The method as in claim 1, further comprising: testing during selected time windows while execution of said lower priority tasks are executing to determine of an isochronous task is scheduled to begin; preempting said lower priority task so that an isochronous task scheduled to begin does begin to execute.
Claim 7
Dependent Claim
81 words
The method as in claim 1 further comprising: dividing said lower priority tasks into real-time tasks and general-purpose tasks, and assigning an intermediate priority to said real-time tasks and assigning a lowest priority to said general-purpose tasks; preempting a general-purpose task by an isochronous task, to halt execution of said general-purpose task to permit said isochronous task to execute; preempting a real-time task by an isochronous task, to halt execution of said real-time task to permit said isochronous task to execute.
Claim 8
Dependent Claim
80 words
The method as in claim 6, further comprising: having said real-time task process a data packet being transmitted onto a network; checking by said real-time task during predetermined time windows to determine if an isochronous task is scheduled to run, and halting operation of said real-time task in the even that an isochronous task is scheduled to run; executing said isochronous task upon halting of said real-time task; continuing execution of said real-time task upon completion of said isochronous task.
Claim 9
Dependent Claim
52 words
The method as in claim 1, further comprising: checking by said general-purpose task at selected time windows to determine if an isochronous task is scheduled to execute; preempting said general-purpose task in the event that an isochronous task is found to be scheduled to execute, and beginning execution of said isochronous task.
Claim 10
Dependent Claim
31 words
The method as in claim 1, further comprising: executing said lower priority task in a plurality of said free time intervals in response to preemption by a task of higher priority.
Claim 11
Dependent Claim
29 words
The method as in claim 1, further comprising: checking for preemption by an isochronous task handling frames for transmission on a network at the completion of processing each frame.
Claim 12
Dependent Claim
19 words
The method as in claim 1, further comprising: checking by a general-purpose task for preemption at periodic time intervals.
Claim 13
Dependent Claim
20 words
The method as in claim 11, further comprising: testing a flag by a task in order to check for preemption.
Claim 14
Independent Claim
103 words
An apparatus for scheduling multiple tasks in a communications network, comprising: a scheduler for establishing a schedule with rounds and windows, said scheduler scheduling a plurality of tasks in said schedule, each task of said plurality of tasks having a class and a priority, said scheduler scheduling each said task in said schedule first according to said class and then according to said priority; and, an admissions control apparatus admitting to said schedule each task of said plurality of tasks according to A. unused time left in said rounds, and B. windows available to accommodate said each task of said plurality of tasks.
Claim 15
Independent Claim
103 words
An apparatus for scheduling multiple tasks in a communications network, comprising: a scheduler for establishing a schedule with rounds and windows, said scheduler scheduling a plurality of tasks in said schedule, each task of said plurality of tasks having a class and a priority, said scheduler scheduling each said task in said schedule first according to said class and then according to said priority; and, an admissions control apparatus admitting to said schedule each task of said plurality of tasks according to A. unused time left in said rounds, and B. windows available to accommodate said each task of said plurality of tasks.
Claim 16
Dependent Claim
32 words
An apparatus as in claim 13 wherein said plurality of classes tasks comprises: an isochronous class, being the class highest in said hierarchy of classes, a real-time class, and, a general-purpose class.
Claim 17
Dependent Claim
26 words
An apparatus as in claim 14 wherein said real-time class and said general-purpose class are scheduled by said means for scheduling by a weighted round robin.
Claim 18
Dependent Claim
37 words
An apparatus as in claim 14 wherein said admissions control apparatus admits tasks of said real-time class when only condition A is satisfied, and admits tasks of said isochronous class when conditions A and B are satisfied.
Claim 19
Independent Claim
96 words
An apparatus for scheduling multiple tasks in a communications network, comprising: means for determining a first time interval during which said tasks are to be performed in said communications network; means for scheduling isochronous tasks, said isochronous tasks being highest priority tasks, to begin at selected time points within said first time interval; means for determining a plurality of free time intervals by identifying unused time in said first time interval which is not used by said isochronous task; and means for scheduling lower priority tasks to begin running during ones of said free time intervals.
Claim 20
Independent Claim
96 words
An apparatus for scheduling multiple tasks in a communications network, comprising: means for determining a first time interval during which said tasks are to be performed in said communications network; means for scheduling isochronous tasks, said isochronous tasks being highest priority tasks, to begin at selected time points within said first time interval; means for determining a plurality of free time intervals by identifying unused time in said first time interval which is not used by said isochronous task; and means for scheduling lower priority tasks to begin running during ones of said free time intervals.
Claim 21
Dependent Claim
74 words
The apparatus as in claim 17, further comprising: means for testing a new isochronous task for admission into said multiple tasks for which scheduling is done, said means for testing having a means for determining if there is enough said unused time for the new task to execute, said means for testing having a means for determining if there is enough time for isochronous tasks including said new isochronous task to execute by themselves.
References Cited (Backward Citations)
US3639912A
Cited
US4177513A
Cited
US4642756A
Cited
US4920432A
Cited
US5293620A
Cited
US5261099A
Cited
US5111391A
Cited
US5163046A
Cited
US5014265A
Cited
US5231633A
Cited
US5168353A
Cited
US5210872A
Cited
US5268900A
Cited
US5291481A
Cited
US5325526A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-06-18 | 1999-12-18 | 2000-06-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-06-18 | 2003-12-18 | 2004-06-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-06-18 | 2007-12-18 | 2008-06-18 | $7700.00 | Window Closed / Lapsed |