Fixed – Priority Vs. Dynamic – Priority Algorithms

• A priority – driven scheduler is an on-line scheduler. It does not pre-compute a schedule of tasks, instead if assigns priority to jobs after they are released and places the jobs in a ready job queue in priority
• When preemption is allowed at any time, a scheduling decision is made whenever a job is released or completes. At each scheduling decision time, the scheduler update the ready job and then schedules and executes the job a head of head of the
• Priority driven algorithms differ from each other in how priorities are assigned to jobs
  • Fixed priority
  • Dynamic priority
• A fixed priority algorithms assigns the same priorities to all the jobs in each tasks. The priority of each periodic task is fixed relative to other tasks.
• A dynamic priority algorithms assigns different priorities to the individual jobs in each Hence the priority of the task with respect to that of other tasks changes as jobs are released and completed.

Rate – Monotonic (RM) algorithms:

A well-known fixed priority algorithms is the rate monotonic algorithms. The algorithm assigns priorities to task based on their periods as shorter period have higher priority. The rate (of job release) of a task is inverse of periods that means higher rate gets higher priority.

For example: consider a system contains three tasks T1 (4, 1), T2 (5, 2) and T3 (20, 5) then Rate for task T1 = ¼

Rate for task T2 = 1/5 Rate for task T3 = 1/ 20

So the priority be assign as T1>T2>T3

The schedule table be constructed as:

The required schedule be constructed as:

Deadline Monotonic Algorithms:

This algorithms assigns priorities to tasks according to their relative deadlines as the shorter deadline gets higher priority. When the relative deadlines are arbitrary, DM algorithms performs better in the sense that it can sometimes produce the feasible schedule if RM algorithms fails that means RM algorithms always fails if DM algorithms fails.

For example: consider three tasks

• T1 (50, 50, 25, 100)
• T2 (0, 62.5, 10, 20)
• T3 (0, 125, 25, 50)

According to DM priority be assigned as T2> T3 >T1 The schedule table be constructed as:

Corresponding Schedule be constructed as:

Dynamic Priority Algorithms:

Dynamic priority algorithms are:

1. Earliest Deadline First (EDF)
2. Least Slack Time (LST)
3. First In First Out (FIFO)
4. Last In First Out (LIFO)

1. Earliest Deadline First (EDF):

The EDF algorithms assigns priorities to individual’s job in the tasks according to their absolute deadlines. EDF algorithms is a task level dynamic priority algorithm.

For example: consider a system with task

• T1 (2, 1)
• T2 (5, 2.5)

Hyper period (H) = 10

The schedule table be constructed as:

Corresponding Schedule be constructed as:

2. Least Slack Time (LST):

A well-known dynamic priority algorithms is least slack time. It assigns the priorities to individual jobs in the task according to slack time. If d be the deadline, e be the execution time then at time t slack time be equals to d-e-t.

The scheduler checks the slack of all ready jobs at each time a new job is released and orders the new and existing jobs in accordance with slack time as smaller slack have the higher priority.

For example: consider a system with two jobs:

T1 (2, 1)

T2 (5, 2.5)

• Two jobs J11 and J21 are released at time 0 then Slack for J11 = 2-1-0=1

Slack for J11 = 5-2.5-0=2.5

Here T1> T2, the job J11 is completely executes in between time 0 and 1 then J21 inters into the execution.

• At time 2, new job J12 is released then Slack for J12 = 4-1-2=1

Slack for J21 = 5-1.5-2= 1.5

Here T1>T2, the job J12 is preempted and J12 enters into the execution and released at 3. The job J21 resumed for execution after time 3.

• At time 4, new job J13 is released then Slack for J13 = 6-1-4=1

Slack for J21 = 5-0.5-4=0.5

Here T2>T1, the job J21 executes up to 4.5 and J13 enters into execution.

• At time 5, new job J22 is released then Slack for J22= 10-2.5-5=2.5

Slack for J13 = 6-0.5-5=0.5

Here T1> T2, the job executes up to 5.5 and job J22 enters into execution.

• At time 6, the new job J14 released then Slack for J14 = 8-1-6=1

Slack for J22 = 10-2-6=2

Here T1>T2, so J14 executes up to 7 and J22 resumes its execution.

• At time 8, new job J15 is released then Slack for J15 = 10-1-8=1

Slack for J22 = 10-1-8 = 1

Here have the equal priority so J15 completes its execution up to 9 and J22 completes its execution up to 10.

The corresponding schedule table be constructed as:

The required schedule is:

In this approach, the priority order is only changed only when the new job is released or any job finishes its execution such that there is no follow of LST algorithms at any time. This type of priorities is non strict and corresponding algorithms is called non strict LST algorithms otherwise it is called strict algorithms. In case of strict approach, scheduler follow the LST rule during the change of slack at any time and updates the job list of queue according to change of priority.

For example: in above, at time 2.6 Slack time for J12 = 4-0.4-2.6 = 1 Slack time for J21 = 5- 1.5- 2.6 = 0.9

Here J21 gets higher priority than J12. Due to continuous observation and computation of slacks at each period of time, strict LST algorithms suffers from run-time overhead.

3. First in, first out (FIFO):

Job queue is first-in-first-out by release time

4. Last in, first out (LIFO):

Job queue is last-in-first-out by release time