Method and apparatus for providing enhanced pay per view in a video server employing a coarse-grained striping scheme
First Claim
1. 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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
29 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A server for programming periodically recurring tasks, said tasks having periods Pi 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. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29)
-
Specification