Method and apparatus for providing enhanced pay per view in a video server

• US 6,012,080 A
• Filed: 03/27/1996
• Issued: 01/04/2000
• Est. Priority Date: 03/27/1996
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Rastogi, Rajeev, Ozden, Banu, Silberschatz, Abraham
• Primary Examiner(s): TOPLU, LUCIEN
• Application Number:
  US08/624,013
• Time in Patent Office: 1,378 Days
• Field of Search: 395/670, 395/671, 395/672, 395/673, 709/102, 709/103, 709/105
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: H04N 21/2312 Data placement on disk arrays data placement in general G06F3/0604
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

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.

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 P_i) being representative of intervals at which tasks are to begin and said computation times (hereafter designated C_i) 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.

2. The method of claim 1 wherein said step of determining scheduleability of said first class of tasks includes the step of:

determining slack values for each of said disjoint sets, 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, said disjoint set being scheduleable on less than one processor if said slack value is non-negative.

3. The method of claim 2 comprising the additional step of:

scheduling a start time for each task in a disjoint set if said disjoint set is determined to be scheduleable.

4. The method of claim 2 wherein each task in said disjoint set is scheduled with a start time equal to a sum of said computation times of previously scheduled tasks if said disjoint set is determined to be scheduleable.

5. The method of claim 1 wherein 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.

6. 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 other 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.

7. 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.

8. The method of claim 7 wherein said first class of tasks are determined to be scheduleable on said first sub-group of processors if each of said disjoint sets is determined to be scheduleable on less than one processor.

9. The method of claim 1 wherein said step of partitioning said first class of tasks includes the step of:

determining whether said first class of tasks is further partitionable into more than one disjoint set.

10. The method of claim 9 wherein said step of determining whether said first class of tasks is partitionable includes the step of:

determining a value C for said first class of tasks such that said value C is a minimum value which is greater than or equal to each computation time in said first class of tasks and said value C divides evenly into each period in said first class of tasks, wherein said first class of tasks is determined not further partitionable if said value C cannot be determined.

11. The method of claim 10 wherein said step of determining whether said first class of tasks is partitionable includes the step of:

computing a value g for said first class of tasks by dividing said value C into said greatest common divisor of said periods in said first class of tasks, wherein said first class of tasks is determined further partitionable if said value g is greater than one and not further partitionable if said value g is equal to one.

12. The method of claim 11 wherein said step of partitioning said first class of tasks includes the step of:

partitioning said first class of tasks having periods P_i and computation times C_i into g number of disjoint sets of tasks having periods P_i /g and computation times C_i.

13. The method of claim 1 wherein said step of determining scheduleability of said first class of tasks includes the steps of:

computing a value g for each of said disjoint sets by dividing a value C into said greatest common divisors of said periods in each of said disjoint sets, wherein said value C is a minimum value which is greater than or equal to each computation time in a disjoint set and said value C divides evenly into each period in said disjoint set; and

packing said tasks in said disjoint set into g number of bins according to said computation times of said tasks being packed.

14. The method of claim 13 wherein said step of packing said tasks includes the steps of:

sorting said tasks in said disjoint set in descending order according to said computation times; and

assigning a task individually in sorted order to a bin having a minimum sum of said computation times of previously assigned tasks for all bins.

15. The method of claim 14 wherein said step of determining scheduleability of said first class of tasks includes the step of:

calculating whether sums of said computation times in each of said bins is greater than or equal to said value C, wherein said disjoint set is scheduleable if said sums of said computation times in each of said bins is greater than or equal to said value C.

16. The method of claim 15 comprising the additional step of:

scheduling start times for said tasks in said disjoint set according to said bins and position of said tasks in said bins.

17. The method of claim 16 comprising the additional step of:

merging said start times for said tasks in said disjoint sets to obtain start times for said tasks in said first class of tasks.

18. The method of claim 1 wherein said group of tasks includes a second class of tasks with said computation times C_i greater than said periods P_i said server having a second sub-group of p'"'"' number of processors available for processing said second class of tasks, said method comprising the additional step of:

calculating a number of processors required by each task in said second class of tasks using a smallest integer greater than P_i /C_i for each said task in said second class of tasks.

19. The method of claim 18 comprising the additional step of:

scheduling a predetermined start time for each task in said second class of tasks.

20. The method of claim 1 wherein said server is a video server for servicing tasks corresponding to videos.

21. A server for servicing periodically recurring tasks, having periods (hereafter designated P_i) and computation times (hereafter designated C_i) 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 P_i that are greater than or equal to their respective computation times C_i ; 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.

22. The server of claim 21 wherein said means for determining scheduleability includes:

means for determining slack values for each of said disjoint sets, 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.

23. The server of claim 21 wherein said means for partitioning 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 said computation times in a disjoint set from a greatest common divisor of said periods in said disjoint set.

24. The server of claim 21 wherein said means for determining scheduleability includes:

means for computing a value g for each of said disjoint sets by dividing a value C into said greatest common divisors of said periods in each of said disjoint sets, wherein said value C is a minimum value which is greater than or equal to each computation time in a disjoint set and said value C divides evenly into each period in said disjoint set; and

means for packing said tasks in a disjoint set into g number of bins according to said computation times of said tasks being packed.

25. The server of claim 24 wherein said means for packing said tasks includes:

means for sorting said tasks in said disjoint set in descending order according to said computation times; and

means for assigning a task individually in sorted order to a bin having a minimum sum of said computation times of previously assigned tasks for all bins.

26. The server of claim 25 wherein said means for determining scheduleability includes:

means for calculating whether sums of said computation times in each of said bins is greater than or equal to said value C, wherein said disjoint set is scheduleable if said sums of said computation times in each of said bins is greater than or equal to said value C.

27. The server of claim 21 further comprising:

means for scheduling start times for tasks in said first class of tasks if said means for determining scheduleability of said first class of tasks determines said first class of tasks to be scheduleable on said first sub-group of processors.

28. The server of claim 21 further comprising:

means for calculating a number of processors to service a second class of tasks using a smallest integer greater than P_i /C_i for each said task in said second class of tasks, wherein said second class of tasks have said period P_i that are less than their respective computation times C_i.

29. The server of claim 21 wherein said server is a video server for servicing tasks corresponding to video programming.