Detailed Example Using RMS

Detailed example using RMS.

RMS – Smallest period highest priority

Consider the problem:

Process / Execution time / Period
P1 / 1 / 3
P2 / 1 / 4
P3 / 2 / 5

The LCM = __

Utilization =

Time / Running / Ready
0 / P1a / P2a / P3a
1
2
3 / P1b
4 / P2b
5 / P3b
6 / P1c
7
8 / P2c
9 / P1d
10 / P3c
11
12 / P1e / P2d
13
14
15 / P1f / P3d
16 / P2e
17
18 / P1g
19
20 / P2f / P3e
21 / P1h
22
23
24 / P1i / P2g
25 / P3f
26
27 / P1j
28 / P2h
29
Time / Running / Ready
30 / P1k / P3g
31
32 / P2i
33 / P1l
34
35 / P3h
36 / P1m / P2j
37
38
39 / P1n
40 / P2k / P3i
41
42 / P1o
43
44 / P2l
45 / P1p / P3j
46
47
48 / P1q / P2m
49
50 / P3k
51 / P1r
52 / P2n
53
54 / P1s
55 / P3l
56 / P2o
57 / P1t
58
59

Earliest-Deadline-First Scheduling (EDF)

EDF – is another well known scheduling policy.
EDF is a dynamic priority scheme – it changes process priorities during execution based on initiation times.
Can achieve higher CPU utilization than RMS.
Simple policy:
Priorities are assigned in order of deadlines.
The highest-priority process is the one whose deadline is nearest in time.
Priorities must be recalculated at every completion of a process.
The highest priority ready process is chosen for execution.

Same example using DFS:

Scheduling

A schedule is said to be feasible if all constraints such as deadlines are met.

The Rate Monotonic schedule (RMS) was not feasible in the above example since several deadlines were not met. The Earliest Deadline First (EDF) was feasible since all deadlines are meet.

Consider a periodic processes Pi. Let ei be the processes execution time, let pi be the period, and let di be the deadline. Then we can characterize Pi using the 3-tuple

Pi = (ei, pi, di).

Utilization is given by U = execution time/ total time.

Any particular process, say Pi, utilizes the CPU for ei/pi percent of the time.

For n processes

If U > 1, no feasible schedule is possible without going to multiple CPU’s.

Using this notation we would describe the above example as

P1 = (1, 3, 3)

P2 = (1, 4, 4)

P3 = (2, 5, 5)

Fixed or static priorities:

RM is an example of fixed priorities. The priorities do not change over time.

EDF is an example of dynamic priorities. The priorities change over time.

Rate Monotonic (RM) is an optimal priority method in that there cannot be a feasible fixed priority non-RM schedule that cannot be replaced by a RM schedule.

If a fixed priority schedule exists that meets all deadlines then RM will produce a feasible schedule.

Proof for n = 2.

Let P1 = (e1, p1, d1) and P2 = (e2, p2, d2)

Suppose P1 and P2 can be scheduled with a fixed but non-RM priority assignment where P2 has the highest priority. i.e. p2 > p1. The worst-case situation occurs when both processes are ready at the same time. Let this be time t = 0. Since P2 is the highest priority it will execute first and finish after time t = e2. Then P1 will execute and finish at time t = e1 + e2. Since the schedule is feasible e1 + e2 p1. Now since our schedule is non-RM it must be the case that p1 p2 otherwise it would be RM. Therefore, e1+e2p2, and the RM schedule (where P1 has the highest priority) is also feasible.

The argument can be extended to the case where n > 2.

We have previously discussed RM and EDF schedulers.

Let’s consider some other scheduling schemes.
We will ignore process interactions.

First-Come First-Served (FCFS) or First-In First-Out (FIFO)– A process is inserted at the end of a ready list. The process at the beginning of the ready list is executed next. There is no preemption (once a process is running it completes it execution.) If more than one process becomes ready at the same time they are inserted at the end of the list in an arbitrary fashion. Note that the priority is dynamic.

Example. P1 = (1, 2, 2), P2 = (2, 5, 5)

The above shows FCFS when P1 is arbitrarily selected at time t = 0.

What happens if P2 is selected at time t = 0?

Round Robin (RR) – Executing process is preempted at regular time intervals and replaced by the process at the front of the ready list. The preempted process goes to the back of the ready list.

Example 1. P1 = (1, 2, 2), P2 = (2, 5, 5), U = 1/2 + 2/5 = 9/10 = 90%

What happens if P1 is selected at time t = 0.

Example 2. P1 = (3,4,4), P2 = (2,8,8), U = 3/4 + 2/8 = .75 + .25 = 100%

A RM schedule works as shown below. p1 > p2.

P1 = (3,4,4), P2 = (2,8,8), U = 3/4 + 2/8 = .75 + .25 = 100%

RMS

Least compute time (LCT) – Fixed priority is assigned based on inverse of execution time. i.e. Process with the shortest execution time has highest priority.

Example: P1 = (3,4,4), P2 = (2,8,8), e2 < e1; therefore, p2 > p1.

P1
P2
0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8

P1 misses it’s deadline at time t = 4; therefore, in this case LCM schedule is not feasible.

Dynamic priorities – More complicated scheduling policies allow for dynamic priorities.

Dynamic priority scheduling schemes include:

Shortest completion time (SCT) – The ready process with the smallest remaining compute time is given the highest priority.
Earliest deadline first (EDF) – Ready process with the earliest deadline is given the highest priority.
Least slack time (LST) given by (d-t)-c’ where d is the deadline, t is the real time since the start of the current cycle, and c’ is the remaining compute time. The smaller the slack time the higher the priority.

All of these recomputed the priority at the beginning of periods (when a process becomes ready).