Generally sporadic job have hard deadlines such that their minimum and maximum release times are known in advance. It is impossible to guarantee a priori that all jobs can complete in time. Hence scheduling of sporadic jobs are done in two steps:
- Acceptance test
- EDF scheduling of accepted jobs
1. Acceptance Test:
A main problem is to determine whether all sporadic jobs can complete in time. A common way to deal with this situation is to have the scheduler perform an acceptance test when each sporadic job is released. During an acceptance test, the scheduler checks whether the newly released sporadic job can be feasibly scheduled with all the jobs in the system at the time. If there is sufficient amount of time in the frames before its deadlines to complete the newly released sporadic job without causing any job in the system to complete too late then scheduler accepts and schedule the job otherwise rejects the new sporadic jobs. That means
If total amount of slack time in frame >= its execution time and no adverse effect on sporadic job then
Accept the job.
Else
Reject the job.
A queue of sporadic job may be formed for testing at a same time on EDF basis.
2. EDF Scheduling of the Accepted Jobs:
EDF is best suited method to schedule the accepted sporadic jobs. For this purpose, the schedule maintains a queue of accepted sporadic jobs in increasing order of their deadlines and inserts each newly accepted sporadic job into this queue in increasing order.
For example:
Frame size is 4, gray rectangles are periodic tasks S1 – S4 are sporadic tasks with parameters (Di , Ci).
- S1 is released in time
- Must be scheduled in frames 2, 3 and
- Acceptance test – at the beginning of frame 2 and Slack time is 4 which is less that execution time such that job is rejected.
- S2 is released in time
- Must be scheduled in frames 3 through 7.
- Acceptance test – at the beginning of frame 3 but Slack time is 5 such that job is accepted.
- First part (2 units) executes in current frame.
- S3 is released in time
- Must be scheduled in frames 4 and 5. S3 runs ahead of S2.
- Acceptance test – at the beginning of frame 4 and Slack time is 2 (enough for S3 and the part of S2) – job is First part (1 unit) S3 executes in current frame, followed by second part of S2.
- S4 is released in time 14
- Acceptance test – at beginning of frame 5 and Slack time is 5 (accounted for slack committed by S2 and S3) such that job is rejected.
- Remaining portion of S3 completes in current frame, followed by the part of
- Remaining potions of S2 execute in the next two frames.