Scheduling Hard and Soft Periodic Tasks

The scheduling of hard periodic tasks is known to be an NP complete problem. To reduce the complexity of this problem, we added the rule that Hard Periodic tasks are scheduled in the order in which they are added. This means that if you add a given number of jobs, you are guaranteed that the ith task (execution) of job j will come before the ith task of all of the jobs entered after j. This is advantageous to the user if certain tasks must be executed before others. One con of this, however, is that there is a greater chance that the entered jobs may not be schedulable, whereas a different permutation of the jobs may be schedulable.

We compute the schedule of the hard and soft periodic jobs (in the Job Table) by scheduling them within a certain slice of time called the hyperperiod H. The hyperperiod is the least common multiple of the periods of all of the hp tasks. If the hp tasks are schedulable, then there exists a schedule for them within the hyperperiod. We iterate through the jobs in order. Each job j must occur Rj times inside the hyperperiod, where Rj = H/Ri. We place job j's first task after the first task of the last job placed (directly after j-1). If it doesn't overlap with anything already in the queue, we attempt to place the rest of the Rj tasks, each one period away from the last. If we run into a conflict along the way, we restart j's first task at a later time to remove the conflict, and update the starting time of the rest of the tasks. If no schedule is attainable (the first task was moved until its starting time was greater than its period), then an error is returned. The computed schedule is stored inside the hard periodic queue.

Soft periodic tasks are scheduled with hard periodic tasks, however sp tasks don't have a deadline. Thus, their deadline is set to 0. They can not be scheduled in the middle of a hard periodic task, but they can be scheduled at the same start time as a different hard periodic task, if necessary.