Table of Contents
Scheduling Approaches In Real Time Operating System
In Real Time Operating System there are mainly three scheduling approaches which are used to schedule the tasks.
- Clock driven
- Weighted round-robin
- Priority driven
Clock driven approach
- On initialising the system
- Scheduler decides the tasks that have to
be executed.
- Scheduler decides the tasks that have to
- These operations are repeated periodically.
- Tasks are periodic in nature.
Round robin approach
- Tasks are scheduled in a repetitive manner based on a time slice allocated.
- The time slice depends on the total available time or resource allocated by the processor
- The processor would execute tasks based on the time slice allotted
- 2 approaches
- Weighted round robbin
- Non-weighted round robbin
Weighted Round-robin approach
Round-robin approach is a commonly used technique in time shared systems.
- Tasks are scheduled in a queue.
- Queue is implemented in a FIFO manner.
- A time slice is allocated to each task for execution.
- If a task does not complete execution before the lapse of time slice
- It is preempted.
- If n tasks are present in the queue
- Each task gets one time slice every n time slices.
- If n tasks are present in the queue
- Each task gets one time slice every n time slices.
- Each task gets 1/n th of share of the processor.
- Round-robin is a processor sharing algorithm.
- Weighted round-robin approach assigns each task a weight instead of providing equal share of
resources. - Time slice is allocated based on the processor or core speed
- Time slice = ((quantum time allocated) / (total resource allocated) * core speed)
- The time slice would vary based on 2 factors
- Quantum time allocated
- Processor core speed
Priority Driven approach
- No resource is kept idle.
- Priority driven scheduling algorithms are work conserving and are event driven.
- Such scheduling algorithms are greedy.
- Tasks are scheduled based on priority and not based on resource availability.
- Scheduling solutions are optimal.
- Priority driven approach also called as list driven approach
- Non-real time scheduling algorithms are priority-driven.
- Examples are FIFO (First In First Out),
- LIFO(Last In First Out),
- SETF(Shortest Execution Time First) and
- LETF(Longest-Execution Time First)
- If round-robin scheduling strategy can be modified to incorporate dynamic changing priorities, they can be called as priority driven scheduling.
- When tasks have similar release times
- Preemptive scheduling without
- preemption cost will be preferable.
- In multiprocessor systems a minimum makespan can be obtained using an optimal
- non-preemptive algorithm.
- algorithms provided cost of preemption is
- negligible and can be ignored.
- When the system has 2 processors
- Theoretical makespan obtained by
- preemption is sufficient to compensate the
- context switching overhead of preemption.
- Garey’s Statement
- Minimum makespan obtained in nonpreemptive algorithms is less than or equal to 4/3 times the minimum makespan obtained using preemptive algorithms provided cost of preemption is negligible and can be ignored.
Dynamic Versus Static Systems
- Tasks placed in the priority queue are dispatched for execution based on priority.
- In a multiprocessor dynamic system tasks are dynamically dispatched.
- Tasks can be migrated by preempting its execution on one processor and resuming execution on another processor.
- If configuration should not be modified Static configuration of priorities can be made.
Effective Release Times and Deadlines
When precedence constraints areincorporated
- Release times and deadlines tend to become inconsistent.
- To resolve this issue, a modification factor has to be included and the resulting release time are termed as effective release time and deadline.
Effective release time
- Effective release time of a task without predecessors is equal to release time of the task.
- Effective release time is the maximum value of all release times of all the predecessors of a task.
Effective deadline
- Effective deadline of a task without a successor is equal to the deadline of the task.
- Effective deadline is the minimum value of all the successors of a task.
- Complexity of the algorithm is O(n2)
- Computation of release times and deadlines does not take into account execution times of tasks.
Optimality of the EDF and LST algorithms
Tasks can be prioritised based on deadlines.
- Task whose deadline is earlier has a higher priority.
- This priotisation strategy is Earliest Deadline First algorithm.
- Optimality is guaranteed by this algorithm.
- Few theorems and informal proofs on the optimality have been discussed.