Patent US5964829A successfully refreshed from Google Patents.
US5964829A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for providing enhanced pay per view in a video server employing a coarse-grained striping scheme
Assignee: Nokia of America Corp
•
Filing: 1996-03-27
•
Granted: 1999-10-12
•
Expires: 2016-03-27
Abstract
Abstract A method and apparatus are disclosed for providing enhanced pay per view in a video server. Specifically, the present invention periodically schedules a group of non pre-emptible tasks corresponding to videos in a video server having a predetermined number of processors, wherein each task begins at predetermined periods and has a set of sub-tasks separated by predetermined intervals. To schedule the group of tasks, the present invention divides the tasks into two groups according to whether they may be scheduled on a single processor. The present invention schedules each group separately. For the group of tasks not scheduleable on a single processor, the present invention determines a number of processors required to schedule such group and schedules such tasks to start at a predetermined time. For the group of tasks scheduleable on a single processor, the present invention determines whether such tasks are scheduleable on the available processors using an array of time slots. If the present invention determines that such group of tasks are not scheduleable on the available processors, then the present invention recursively partitions such group of tasks in subsets and re-performs the second determination of scheduleability. Recursive partitioning continues until the group of tasks is deemed scheduleable or no longer partitionable. In the latter case, the group of tasks is deemed not scheduleable.
Inventors
- 👤 Banu Ozden
- 👤 Rajeev Rastogi
- 👤 Abraham Silberschatz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 21:35
CPC Classifications
H; H04; H04N; H04N7/00; H04N7/16; H04N7/173; H04N7/17309; H04N7/17336
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
152 words
A method for scheduling a group of periodically recurring, non pre-emptible tasks on a server, wherein said tasks have predetermined periods P and include w number of sub-tasks separated by intervals F, said group of tasks including a first class of tasks which are scheduleable on single processors, said server having a first sub-group of processors available for processing said first class of tasks, said method comprising the steps of: partitioning said first class of tasks into one or more disjoint sets; and determining scheduleability of said first class of tasks on said first sub-group of processors based on a function of periods for said first class of tasks and a greatest common divisor of said periods P for tasks in said first class of tasks wherein said first class of tasks is scheduleable if two or more sub-tasks belonging to distinct tasks will not be assigned to a same time slot.
Claim 2
Independent Claim
152 words
A method for scheduling a group of periodically recurring, non pre-emptible tasks on a server, wherein said tasks have predetermined periods P and include w number of sub-tasks separated by intervals F, said group of tasks including a first class of tasks which are scheduleable on single processors, said server having a first sub-group of processors available for processing said first class of tasks, said method comprising the steps of: partitioning said first class of tasks into one or more disjoint sets; and determining scheduleability of said first class of tasks on said first sub-group of processors based on a function of periods for said first class of tasks and a greatest common divisor of said periods P for tasks in said first class of tasks wherein said first class of tasks is scheduleable if two or more sub-tasks belonging to distinct tasks will not be assigned to a same time slot.
Claim 3
Dependent Claim
52 words
The method of claim 1 wherein said step of determining scheduleability of said first class of tasks includes the step of: determining scheduleability of a disjoint set within a division of g number of time slots, wherein g represents a greatest common divisor of periods P for tasks in said disjoint set.
Claim 4
Dependent Claim
51 words
The method of claim 2 wherein said step of determining scheduleability of said disjoint set includes: determining whether a time slot within said division of g number of time slots is free to be assigned a sub-task, wherein said time slot is free if said time slot has no sub-tasks assigned.
Claim 5
Dependent Claim
64 words
The method of claim 2 wherein said step of determining scheduleability of said disjoint set includes the step of: assigning sub-tasks r of a first task in a disjoint set to free time slots (j'+F·k) mod g in said division of g number of time slots, where r=1, . . . , w, k=r-1 and j' is a predetermined value between 0 and g-1.
Claim 6
Dependent Claim
23 words
The method of claim 4 wherein said first task is a task in said disjoint set having a maximum number of sub-tasks r.
Claim 7
Dependent Claim
62 words
The method of claim 4 wherein said step of determining scheduleability of said disjoint set includes the step of: determining whether time slots (j+F·k) mod g are free to be assigned sub-tasks r of another task in said disjoint set for which said sub-tasks r are unassigned, wherein j is a value between 0 and g-1 other than said predetermined value j'.
Claim 8
Dependent Claim
47 words
The method of claim 6 wherein said step of determining scheduleability of said disjoint set includes the step of: assigning said sub-tasks r of another said task in said disjoint set to said times slots (j+F·k) mod g if said time slots (j+F·k) mod g are free.
Claim 9
Dependent Claim
48 words
The method of claim 7 wherein said step of determining scheduleability of said disjoint set includes the step of: repeating said steps of determining whether said time slots (j+F·k) mod g are free and assigning said sub-tasks r of another said task until no unassigned sub-tasks r remain.
Claim 10
Dependent Claim
38 words
The method of claim 7 wherein said step of determining scheduleability of said disjoint set includes the step of: sorting said tasks in said disjoint set to create a sort order according to w number of sub-tasks r.
Claim 11
Dependent Claim
30 words
The method of claim 9 wherein said sub-tasks r of said tasks in said disjoint set are assigned to said time slots (j+k·F) mod g according to said sort order.
Claim 12
Dependent Claim
25 words
The method of claim 7 comprising the additional step of: scheduling said sub-tasks r using said time slots to which said sub-tasks r were assigned.
Claim 13
Dependent Claim
28 words
The method of claim 11 comprising the additional step of: merging schedules of said sub-tasks to obtain a schedule for said tasks in said first class of tasks.
Claim 14
Dependent Claim
65 words
The method of claim 6 wherein said step of determining scheduleability of said disjoint set includes the step of: partitioning said disjoint set of tasks with periods P and sub-tasks at intervals F into g number of disjoint subsets of tasks with periods P/g and sub-tasks at intervals F/g if g is greater than one and said time slots (j+F·k) mod g are not free.
Claim 15
Dependent Claim
47 words
The method of claim 1 comprising the additional step of: determining whether a task is scheduleable on a single processor, wherein a task is scheduleable on a single processor if two or more sub-tasks belonging to said task will not be assigned to a same time slot.
Claim 16
Dependent Claim
51 words
The method of claim 1 wherein said group of tasks includes a second class of tasks which are not scheduleable on a single processor, wherein a task is not scheduleable on a single processor if two or more sub-tasks belonging to said task will be assigned to a same time slot.
Claim 17
Dependent Claim
37 words
The method of claim 15 comprising the additional step of: calculating a number of processors required by said second class of tasks using a value yielded most frequently by equation ((r-1)·F) mod P for each sub-task r.
Claim 18
Dependent Claim
24 words
The method of claim 15 comprising the additional step of: scheduling a predetermined start time for each task in said second class of tasks.
Claim 19
Dependent Claim
72 words
The method of claim 1 wherein said tasks have computation times and said step of partitioning said first class of tasks includes the step of: assigning said tasks to said disjoint sets such that slack values for said disjoint sets are maximized, wherein a slack value is determined by subtracting a sum of said computation times in a disjoint set from a greatest common divisor of said periods in said disjoint set.
Claim 20
Dependent Claim
247 words
The method of claim 1 wherein said step of partitioning said first class of tasks includes the steps of: assigning a first task to a first empty disjoint set, wherein said first task is a task in said first class of tasks which yields a slack value that is less than or equal to any slack value for any other task in said first class of tasks if assigned to said first empty disjoint set, said slack value determined by subtracting a sum of said computation times in a disjoint set from a greatest common divisor of said periods in said disjoint set; assigning an unassigned task in said first class of tasks to an empty disjoint set such that said unassigned task yields a slack value less than or equal to any slack value for any unassigned task in said first class of tasks if assigned to any non-empty disjoint set; repeating said step of assigning said unassigned task until no empty disjoint sets remain; designating an unassigned or non-designated task in said first class of tasks to a non-empty disjoint set such that said non-empty disjoint set to which said unassigned or non-designated task is designated is a disjoint set which yields a maximum slack value if said unassigned or non-designated task is designated to any other non-empty disjoint set; and repeating said step of designating an unassigned or non-designated task until every task in said first class of tasks has been assigned or designated.
Claim 21
Dependent Claim
38 words
The method of claim 1 wherein said first sub-group of processors have p" number of processors and said first class of tasks is partitioned into p" or less number of disjoint sets if p" is greater than one.
Claim 22
Dependent Claim
18 words
The method of claim 1 wherein said server is a video server for servicing tasks corresponding to videos.
Claim 23
Dependent Claim
126 words
A server for programming periodically recurring tasks, said tasks having periods P i and having w number of sub-tasks separated by intervals F, said server having a first sub-group of processors available for processing said first class of tasks said server comprising: means for partitioning a first class of tasks into one or more disjoint sets, wherein said partitioning is performed based on said periods and said first class of tasks include tasks which are scheduleable on single processors; and means for determining scheduleability of said first class of tasks on said first group of processors by ascertaining whether two or more sub-tasks belonging to distinct tasks will be assigned to a same time slot using a greatest common divisor of periods P for said tasks.
Claim 24
Dependent Claim
126 words
A server for programming periodically recurring tasks, said tasks having periods P i and having w number of sub-tasks separated by intervals F, said server having a first sub-group of processors available for processing said first class of tasks said server comprising: means for partitioning a first class of tasks into one or more disjoint sets, wherein said partitioning is performed based on said periods and said first class of tasks include tasks which are scheduleable on single processors; and means for determining scheduleability of said first class of tasks on said first group of processors by ascertaining whether two or more sub-tasks belonging to distinct tasks will be assigned to a same time slot using a greatest common divisor of periods P for said tasks.
Claim 25
Dependent Claim
51 words
The server of claim 22 wherein said means for determining scheduleability of said first class of tasks includes: means for determining scheduleability of a disjoint set within a division of g number of time slots, wherein g represents a greatest common divisor of periods P for tasks in said disjoint set.
Claim 26
Dependent Claim
62 words
The server of claim 23 wherein said means for determining scheduleability of said disjoint set includes: means for assigning sub-tasks r of a first task in a disjoint set to free time slots (j'+F·k) mod g in said division of g number of time slots, where r=1, . . . , w,k=r-1 and j' is a predetermined value between 0 and g-1.
Claim 27
Dependent Claim
61 words
The server of claim 24 wherein said means for determining scheduleability of said disjoint set includes: means for determining whether time slots (j+F·k) mod g are free to be assigned sub-tasks r of another task in said disjoint set for which said sub-tasks r are unassigned, wherein j is a value between 0 and g-1 other than said predetermined value j'.
Claim 28
Dependent Claim
46 words
The server of claim 22 further comprising: means for determining whether a task is scheduleable on a single processor, wherein a task is scheduleable on a single processor if two or more sub-tasks belonging to said task will not be assigned to a same time slot.
Claim 29
Dependent Claim
55 words
The server of claim 26 further comprising: means for calculating a number of processors required by a task in a second class of tasks using a value yielded most frequently by equation ((r-1)·F) mod P for each sub-task r, wherein said second class of tasks includes tasks which are not scheduleable on a single processor.
Claim 30
Dependent Claim
64 words
The server of claim 22 wherein said means for partitioning said first class of tasks includes: means for assigning said tasks to said disjoint sets such that slack values for said disjoint sets are maximized, wherein a slack value is determined by subtracting a sum of computation times in a disjoint set from a greatest common divisor of said periods in said disjoint set.
Claim 31
Dependent Claim
19 words
The server of claim 22 wherein said server is a video server for servicing tasks corresponding to video programming.
References Cited (Backward Citations)
US5606695A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-10-11 | 2003-04-12 | 2003-10-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-10-11 | 2007-04-12 | 2007-10-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-10-11 | 2011-04-12 | 2011-10-12 | $7700.00 | Window Closed / Lapsed |