FOR FREE YEAR SOLVED

Deadline Scheduling:

Two kinds of deadlines can be specified for a process: 

i)  Starting deadline: The latest instant of time by which operation of the process must begin.

ii) Completion deadline: The time by which operation of the process must complete. 

We consider only completion deadlines in the following.

Figure 21 shows the PPG of a real-time application containing 6 processes. Each circle is a node of the graph and represents a process. The number in a circle indicates the service time of a process.

Deadline Estimation:

Deadlines for individual processes are determined by considering process precedencies and working backward from the response requirement of the application.

where,

${\mathbf{D}}_{\mathbf{i}}$= Completion deadline of a process ${\mathbf{P}}_{\mathbf{i}}$

${\mathbf{D}}_{\mathbf{application}}$ = Deadline of the application. 

${\mathbf{x}}_{\mathbf{k}}$ = Service time of process ${\mathbf{P}}_{\mathbf{k}}$

descendant(i) = the set of descendants of ${\mathbf{P}}_{\mathbf{i}}$ in the PPG, i.e., the set of all processes that lie on some path between ${\mathbf{P}}_{\mathbf{i}}$ and the exit node of the PPG.

Thus the deadline for a process Pi is such that if it is met, all processes that directly or indirectly depend on Pi can also finish by the overall deadline of the application.

Deadline of one process Pi = Deadline of the application – the sum of the service time of the processes which is directly or indirectly dependent on Pi.

As per PPG (Fig: 21) If the application has to produce a response in 25 seconds, the deadlines of the processes would be as follows:

Deadline of the application is given = 25

So, deadline of P1= 25 – (Service time of P2, P3, P4, P6) = 25 – (3 + 5 + 4 + 5) = 25 – 17 = 8

P2, P3, P4, P5 is directly or indirectly dependent on P1.

Deadline of P2 = 25 – (Service time of P4, P6) = 25 – (4 + 5) = 25 – 9 = 16

Deadline of P3 = 25 – (Service time of P4, P6) = 25 – (4 + 5) = 25 – 9 = 16

Deadline of P4 = 25 – (Service time of P6) = 25 – 5 = 25 – 5 =  20

Deadline of P5 = 25 – (Service time of P6) = 25 – 5 = 25 – 5 =  20

Deadline of P6 = 25 – (No one depends on P6) = 25 – 0 = 25 = 25