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.

1. Clock driven
2. Weighted round-robin
3. Priority driven

Clock driven approach

• On initialising the system
  • Scheduler decides the tasks that have to
    be executed.
• 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.