Real-Time Scheduling

-Real-Time Scheduling (1) (2)

Real-time scheduling is becoming an increasingly important discipline, in which the scheduler is the most important component of a real-time system.In a real-time system, time is an essential role. Real-time computing may be defined as that typo of computing in which the correctness of the system depends not only on the logical result of he computation, but also on the time at which the results are produced. For example, the computer in a compact disc player gets the bits as they come off the drive and must convert them into music within a very tight interval. If the calculation takes too long, the music will sound peculiar.


Real-time tasks can be classified into two categories:

-hard real-time task: the task must meet its deadline; otherwise it will cause undesirable damage or a fatal error to the system.
-soft real-time task: there is an associated deadline that is desirable but not mandatory.

Another characteristic of real-time task is whether they are periodic or aperiodic. A periodic task is one that occurs at regular intervals, while an aperiodic task occurs unpredictably. If there are m periodic events and event i occurs with period Pi and requires Ci seconds of CPU time to handle each event, then the load can only be handled if

(1)
A real-time system that meets this criterion is said to be schedulable.

Real-time scheduling algorithm: (2)

In a real-time system, the various scheduling approaches depends on

1)whether the system performs schedulability analysis
2)if it does, whether it is done statically or dynamically
3)whether the result of the analysis itself produces a schedule or plan according to which tasks are dispatched at run time.


Based on these considerations, there can be these algorithms:

• Static table-driven schedulingThis is applicable to tasks that are periodic. Input to the analysis consists of the periodic arrival time, execution time, periodic ending deadline, and relative priority of each task. The scheduler attempts to develop a schedule that enables it to meet the requirement of all periodic tasks. This is a predictable approach but inflexible because any change to any task requirement requires the scheduler be redone. One of the typical scheduling algorithms in this category is earliest-deadline-first.
  
• Static priority-driven preemptive schedulingIt makes use of the priority-driven preemptive scheduling mechanism common to most non-real-time multiprogramming system. In real-time system, priority assignment is related to the time constraints associated with each task. One example of this approach is rate monotonic algorithm, which assigns static priorities to tasks based on the length of their periods.
  
• Dynamic planning-based schedulingWith this approach, after one task arrives, but before its execution begins, an attempt is made to create a schedule that contains the previously scheduled tasks as well as the new arrival. If the new arrival can be scheduled in such a way that its deadlines are satisfied and that no currently scheduled task misses a deadline, then the schedule is revised to accommodate the new task.
  
• Dynamic best effort scheduling-This is the approach used by many real-time systems that are currently commercially available. When a task arrives, the system assigns a priority based on the characteristics of the task. Some forms of the deadline scheduling, such a earliest-deadline scheduling, is typically used. Usually the tasks are aperiodic and so no static scheduling analysis is possible. With this type of scheduling, until a deadline arrives or until the task completes, we do not know whether a timing constraint will be met. This is the major disadvantage of this form of scheduling. The advantage of this approach is easy to implement