Method and apparatus for providing enhanced pay per view in a video server
First Claim
1. A method for scheduling a group of periodically recurring, non pre-emptible tasks on a server, wherein said group of tasks includes a first class of tasks having periods greater than or equal to computation times, said periods (hereafter designated Pi) being representative of intervals at which tasks are to begin and said computation times (hereafter designated Ci) being representative of run times for said tasks, and further wherein said server has 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 computation times for said first class of tasks and a greatest common divisor of said periods for tasks in said first class of tasks, wherein said first class of tasks is scheduleable on said first sub-group of processors if each of said disjoint sets is determined to be scheduleable.
3 Assignments
0 Petitions
Accused Products
Abstract
A method and an 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 is defined by a computation time and a period. To schedule the group of tasks, the present invention divides the tasks into two groups according to whether they may be scheduled on less than one processor. The present invention schedules each group separately. For the group of tasks scheduleable on less than one processor, the present invention conducts a first determination of scheduleability. If the first determination of scheduleability deems the group of tasks not scheduleable, then the present invention conducts a second determination of scheduleability. If the second determination of scheduleability also deems the group of tasks not scheduleable, then the present invention recursively partitions the 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 group of tasks includes a first class of tasks having periods greater than or equal to computation times, said periods (hereafter designated Pi) being representative of intervals at which tasks are to begin and said computation times (hereafter designated Ci) being representative of run times for said tasks, and further wherein said server has 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 computation times for said first class of tasks and a greatest common divisor of said periods for tasks in said first class of tasks, wherein said first class of tasks is scheduleable on said first sub-group of processors if each of said disjoint sets is determined to be scheduleable. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A server for servicing periodically recurring tasks, having periods (hereafter designated Pi) and computation times (hereafter designated Ci) wherein said server includes a first sub-group of processors, said server comprising:
-
means for partitioning a first class of tasks into one or more disjoint sets, wherein said first class of tasks have said periods Pi that are greater than or equal to their respective computation times Ci ; and means for determining scheduleability of said first class of tasks on said first sub-group of said processors using greatest common divisor of said periods within said first class of tasks. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29)
-
Specification