Methods and Apparatus for Sharing Slack in a Time-Partitioned System

Abstract

In a multitasking system executing real-time harmonic and dynamic tasks having various priority levels, slack is stolen from both timeline and reclaimed slack to enable the execution of high priority non-essential tasks on a best efforts basis. Counts of the amount of slack consumed, slack reclaimed, and periodic compute time consumed are maintained by individual priority level and dynamically updated at certain times. Idle time is calculated by priority level. Available slack is calculated, and slack is allocated and consumed by rate, with the highest rate first and the lowest rate last. Slack is made available to tasks in more than one time partition. All slack belongs to a common system-wide pool of slack obtained from any one or more of the time partitions. Common slack can also be time-shared by static, non-harmonic tasks residing in different time partitions. Also described are a computer system and various methods that perform slack scheduling in a time-partitioned system.

1 . In a data processing system executing tasks in different time partitions, a method of scheduling tasks comprising: 
 determining available slack; and    allocating slack to tasks in different time partitions.    
   
   
       2 . The method of  claim 1  wherein the tasks that are allocated slack are aperiodic, non-essential tasks.  
   
   
       3 . The method of  claim 2  wherein the tasks comprise essential and non-essential tasks, and wherein the tasks that are allocated slack are from the group consisting of new non-essential tasks and enhancements to essential tasks.  
   
   
       4 . The method of  claim 1  wherein in determining, both timeline slack and reclaimed slack are determined.  
   
   
       5 . A machine-readable medium having instructions stored thereon capable of causing a processor to carry out a method, the method comprising: 
 scheduling tasks to execute in different time partitions;    determining available slack; and    allocating slack to tasks in different time partitions.    
   
   
       6 . In a data processing system executing tasks in different time partitions, a method of scheduling tasks comprising: 
 collecting unscheduled execution time from at least one time partition; and,    allocating the unscheduled execution time to a task in another time partition.    
   
   
       7 . The method of  claim 6 , wherein the task in the other partition is an aperiodic, non-essential task.  
   
   
       8 . The method of  claim 7 , wherein the tasks comprise essential and non-essential tasks, and wherein the task in the other partition is from the group consisting of new non-essential tasks and enhancements to essential tasks.  
   
   
       9 . The method of  claim 6 , wherein in collecting unscheduled execution time, both timeline slack and reclaimed slack are collected.  
   
   
       10 - 30 . (canceled)