Page 94 - DCAP103_Principle of operating system

Unit 3: Process Management-II

manner, primarily due to a lack of any other technique. In the late ‘70s and early ‘80s, researchers Notes
realized that this method of constructing systems was producing systems that were inflexible
and difficult to maintain. It was also realized that new methods and techniques were needed
to support the analysis, design, and implementation of real-time systems. Although many
scheduling techniques were proposed, preemptive static priority-based scheduling has emerged
as one of the more widely studied and implemented techniques. Preemptive static priority-based
scheduling algorithms form the basis for most commercially available real-time operating systems.
The Ada95 and POSIX standards are also based upon preemptive static priority based algorithms.
A literature search will reveal that preemptive static priority-based algorithms are among the
most widely studied and understood of any class of scheduling algorithm. The model assumes:
1. All processes are periodic.

2. All processes have a deadline that is equal to their period.
3. All processes are independent of one another.
4. All processes have a fixed computation time.

5. No process may voluntarily suspend itself.
6. All processes are released as soon as they are ready.
7. Overheads are ignored.

The basic timing constraint assumption is that the computation time of all processes is less than
or equal to the deadline, which is equal to the period. Clearly, if this is not the case, the problem
is unsolvable since the computation time will exceed the period. There are several reasons for
the popularity of the preemptive static priority-based algorithms. This class of algorithms tends
to be easy to understand and easy to implement. In the most basic scenario, the implementation
consists of little more than a priority queue. Additionally, given the necessary system constraints,
these algorithms can guarantee task completion. If execution guarantees are not required, this
algorithm class is also quite flexible. Tasks can be added or deleted with no change to the
scheduler. The rate-monotonic algorithm is one of the most well known in preemptive static
priority-based scheduling and many algorithms are based upon variations of it. That a set of n
independent periodic tasks, where a periodic task t is characterized by a I period T and a worst
case execution time C.
The upper bound on the utilization ii Ti1is ln 2 = 0.69 as n approaches infinity. Fortunately, this
bound is n( ) 21-n very pessimistic. The average CPU utilization for a task set scheduled using the
rate-monotonic algorithm was 88%. The deadline-monotonic scheduling algorithm is really just a
special case of the rate-monotonic algorithm. The rate-monotonic algorithm assumes that a task’s
deadline is the same as the end of the task’s period. Deadline-monotonic scheduling was developed
to comprehend periodic task’s which have deadlines prior to the end of their period, resulting in
a narrower window of opportunity than the task’s period. That a set of n periodic tasks scheduled
by the deadline-monotonic algorithm will always meet its deadlines if:( )( )CBEC1== + ++ ++ = -I
in C,,121 L ii I 1 2 I T TT i1 2i where B is the duration in which task t is blocked by lower priority
tasks,C is ii I the task’s required execution time,T is the task’s period,E is the difference I I between
the task’s period and it’s deadline. When the task’s deadline is ( ) earlier than the end of the period,
ETD =- where D is the earlier I iii deadline. It has also been proven that assigning higher priorities
to tasks with narrower windows is optimal for scheduling.

The main advantage of deadline-monotonic scheduling over rate-monotonic scheduling is that
there are task sets that cannot be scheduled using rate-monotonic scheduling but are schedulable
using deadline-monotonic scheduling. The weight-monotonic scheduling algorithm attempts to
generate schedules that exhibit temporal fairness. Temporal fairness is a property that provides
for more equal allocation of processor time over some period to all tasks, thus providing relative

LOVELY PROFESSIONAL UNIVERSITY 87