Assumptions:
- The parameters of each sporadic job become known after it is released.
- Sporadic jobs may arrive at any instant, even immediately after each other.
- Moreover, their execution times may vary widely, and
- Their deadlines are arbitrary.
It is impossible for some sporadic jobs to meet their deadlines no matter what algorithm we use to schedule them. The only alternatives are:
- To reject the sporadic jobs that cannot complete in time orTo accept all sporadic jobs and allow some of them to complete Which alternative is appropriate depends on the application.
System Model:
System model consists the separate queue for the aperiodic, periodic, sporadic tasks in a well- known order. The main objective of this system model is to complete each aperiodic job as soon as possible, without causing periodic tasks or accepted sporadic jobs to miss deadlines such that aperiodic jobs are always accepted. Based on the execution time and deadline of each newly arrived sporadic jobs are decided as whether to accept or reject. When the job will complete within its deadline, without causing any periodic task or previously accepted sporadic job to miss its deadline then job be accepted. If sporadic job cannot guarantee it will meet its deadline then it is
rejected from the scheduling. This is done by acceptance test. When the sporadic job is accepted then it enters into the priority queue based on known discipline.
Correctness:
- A correct schedule or correctness of schedule is one where all periodic tasks, and any sporadic tasks that have been accepted, meet their deadlines.
- A scheduling algorithm supporting aperiodic and/or sporadic jobs is a correct algorithm if it only produces correct schedules for the system.
Optimality:
- The system is said to be optimal when the queuing discipline is well-known and corresponding scheduling algorithms are optimal to schedule the periodic, aperiodic and sporadic jobs.
- A periodic job scheduling algorithms is said to be optimal algorithm when it always produces a feasible schedule accepted periodic jobs.
- A sporadic job scheduling algorithm is optimal if it accepts a new sporadic job, and schedules that job to complete by its deadline, if and only if the new job can be correctly scheduled to complete in time.
- An aperiodic job scheduling algorithm is said to be optimal if it minimizes either the response time of the job at the head of the aperiodic job queue or the average response time of all aperiodic jobs for a given queuing discipline.
0.1 with execution time 0.8. when the periodic tasks are executed by using RM algorithms and aperiodic task be executed in background as :
- If an aperiodic job is in the queue, it is executed for up to es time units
- If the aperiodic queue is empty, the polling server self-suspends, giving up its execution slot
- The server does not wake-up once it has self-suspended, aperiodic jobs which become active during a period are not considered for execution until the next period begins
For example: Consider a system with two periodic task T1 (3, 1) , T2 (10, 4), a periodic task A with r = 0.1 and e = 0.8 and a poller (2.5, 0.5) then the aperiodic task be scheduled along with scheduling of periodic task using RM as :
Scheduling Aperiodic Jobs:
Generally three approaches are used as
- Background approach
- Interrupt driven execution approach
- Polled approach
Background Approach:
In this approach, aperiodic jobs are executed in the background i.e. Aperiodic jobs are scheduled and executed only at times when there are no periodic or sporadic jobs ready for execution.
Advantages:
- Clearly produces correct schedules
- Extremely simple to implement Disadvantage:
- It is not optimal since it is almost guaranteed to delay execution of aperiodic jobs in favor
of periodic and sporadic jobs, giving unduly long response times for the aperiodic jobs. For example consider two periodic task T1 (3, 1), T2 (10, 4) and a aperiodic task A released at
0.1 with execution time 0.8. when the periodic tasks are executed by using RM algorithms and aperiodic task be executed in background as :
Here, response time for aperiodic job = 7.8 – 0.1 = 7.7 It is a worst case response time.
Interrupt Driven Execution Approach:
Whenever an aperiodic job arrives, the execution of periodic tasks is interrupted, and the aperiodic job is executed then it is called as interrupt driven execution. This approach reduces response times of aperiodic jobs but will not be correct and will often cause periodic/sporadic tasks in the system to miss some deadlines.
Polled Approach:
It is a common way to schedule aperiodic jobs using a polling server. A periodic job (ps, es) is a periodic task called as poller or polling server where ps is the polling period and es execution time. The poller is ready for execution periodically at integer multiple of Ps and scheduled together with periodic tasks in the system according to priority-driven algorithms. When executed, it examines the aperiodic job queue then
- If an aperiodic job is in the queue, it is executed for up to es time units
- If the aperiodic queue is empty, the polling server self-suspends, giving up its execution slot
- The server does not wake-up once it has self-suspended, aperiodic jobs which become active during a period are not considered for execution until the next period begins
For example: Consider a system with two periodic task T1 (3, 1) , T2 (10, 4), a periodic task A with r = 0.1 and e = 0.8 and a poller (2.5, 0.5) then the aperiodic task be scheduled along with scheduling of periodic task using RM as :
Response time of task A = 5.3 – 0.1 = 5.2
Periodic Servers:
A task that behaves much like a periodic task, but is created for the purpose of executing aperiodic jobs, is called as periodic server. A periodic server, TPS = (PPS, ePS) never executes for more than ePS units of time in any time interval of length PPS where the parameter e PS is called the execution budget (or simply budget) of the periodic server. When a server is scheduled and executes aperiodic jobs, it consumes its budget at the rate of 1 per unit time and the budget has been exhausted when it reaches 0. A time instant when the budget is replenished is called a replenishment time.
A periodic server is backlogged whenever the aperiodic job queue is nonempty i.e. it is idle if the queue is empty. The periodic server is scheduled as any other periodic task based upon the priority scheme used by the scheduling algorithm. A polling server is a simple kind of periodic server. The budget is replenished to e s at the beginning of each period and the budget is immediately consumed if there is no work when the server is scheduled
Bandwidth-Preserving Servers:
- A deficiency of the polling server algorithm is that if the server is scheduled when it is not backlogged, it loses its execution budget until it is replenished when it again released.
- An aperiodic job arriving just after the polling server has been scheduled and found the aperiodic job queue empty will have to wait until the next replenishment time.
- Algorithms that improve the polling approach in this manner are called bandwidth- preserving server algorithms
- Bandwidth-preserving servers are periodic servers with additional rules for consumption and replenishment of their The working principle or rules of working of this server are:
- A backlogged bandwidth-preserving server is ready for execution when it has budget
- The scheduler keeps track of the consumption of the budget and suspends the server when it is exhausted, or the server becomes idle.
- The scheduler moves the server back to the ready queue once it replenishes its budget, if the server is backlogged at that time.
- If arrival of an aperiodic job causes the server to become backlogged, and it has budget, the server is put back on the ready queue.
The last rule overcomes the deficiency of pooling server. Different types of bandwidth-preserving server are:
- Deferrable servers
- Sporadic servers
- Constant utilization servers
- Total bandwidth servers
- Weighted fair queuing servers