Question.1. What is Real time Systems and Categories of Real time Systems with example ?.Identify with justification the type of real time system used in the following scenarios.
a)
Bank security based
system to gain access into the safety vault
b)
Pantry service in an
IT company to deliver snacks and Beverages
c)
Fire alarm setting in
a server room
d)
Flight simulator video
game
e)
Battery operated toy
robot used at home for normal routine task.
Answer: Real time
systems are systems that need to run continuously and take decisions in a
timely manner.
Categories of Real time Systems: There are 2 broad categories.
- Hard Real Time Systems
- Soft Real Time Systems
Hard Real time Systems:
- Failure to meet deadlines lead to catastrophe
- Example would be an automatic flight control scenario
Soft Real Time Systems:
- Failure to meet deadlines would not cause everlasting damages
- Examples could range from a video game to washing machines, etc
Identification of Hard and Soft Real Time Systems
(a) Bank security based system to gain access into the safety vault-Hard RTOs
(b) Pantry service in an IT company to deliver snacks and Beverages-Soft RTOs
(c) Fire alarm setting in a server room-
(d) Flight simulator video game-
(e) Battery operated toy robot used at home for normal routine tasks-Soft RTOs
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Question.2. Elements/Terms used in Real time Systems.
Answer:
- Resources – Basically this can be a CPU, memory, time or any resource directly related to a task.
- Tasks– A set of programs that may have to run on the real time system to accomplish the system’s underlying functionality of a particular application.[A task can be aperiodic if the jobs in it have soft or no deadlines]
- Algorithm – This is basically a scheduling algorithm that decides the quantum of resource a task should utilize and also ensure that no task must have fallen short of resources.
- Execution time: Execution time is an essential temporal parameter as it decides the duration of a job. Two types : Minimum execution time and Maximum execution time.
- Period - Minimum time interval between release times of consecutive jobs.
- Task utilization: Task utilization is the ratio of execution time of a task to its period – Ui = ei/pi. [should be less than or equal to unity]
- Makespan: The makespan is the completion time of the last job in the sequence or The makespan is the sum of all the processing times.
- Periodic Task: If jobs have predictable release times, a task is termed aperiodic.
- Aperiodic Task: If jobs have unpredictable release times, a task is termed aperiodic.
- Sporadic Task: A sporadic task is an aperiodic task where jobs have deadlines once released.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Question.3. Characteristics
of a real time system as well as components. Differentiate the schedulability test among all algorithm.
Answer: Characteristics for a Real Time System:
- Timely in nature
- Capable of handling exceptions
- Reliable
- Fault tolerant
- Sub-optimal
Components for a Real Time System:
- Job
- Task
- Control law computation
Schedulability analysis:
Note: EDF for tasks with D <= T, It's more complicated (out of scope of the course according to me)
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Question.4. Tasks
parameters.
Answer: Any task is defined by the following parameters.
- Release time: It is the time at which task is available for execution.
- Deadline : It is the time by which the task execution must complete.
- Relative deadline : It is the maximum allowable response time.
- Absolute deadline : It is the sum of the relative deadline and its release time.
- Response time is the time interval from the release time of the task to its completion time
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Question.5. Check the
schedulability of the independent, preemptable, tasks T1(3, 1), T2(5, 2), and
T3(8,3); whether they are schedulable using the rate monotonic algorithm.
Answer:
Check schedulability:
1. First constraint(Precise test):
Total utilization U ≤ 1 .
Hence,
U = ∑ Ei / Pi =1/3+2/5+3/8= 0.33 + 0.4 + 0.38 = 1.11 > 1
Hence the tasks are not schedulable under RM algorithm.
2. Second constraint: UB Test(Utilization bound)
Again we need to prove that
where n is the number of task need to schedule.
Hence,
1.11 ≤ 3 .(21/3 – 1) = 3. (1.26 - 1) = 3 . 0.26 = 0.78
=> 1.11 ≤ 0.78 is False. We can conclude from here that the tasks are not schedulable
according to RM algorithm.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Question.6. Difference between EDF and RM.
Answer:
EDF characteristics:
Answer:
Check schedulability:
1. First constraint(Precise test):
Total utilization U ≤ 1 .
Hence,
U = ∑ Ei / Pi =1/3+2/5+3/8= 0.33 + 0.4 + 0.38 = 1.11 > 1
Hence the tasks are not schedulable under RM algorithm.
2. Second constraint: UB Test(Utilization bound)
Again we need to prove that
where n is the number of task need to schedule.
Hence,
1.11 ≤ 3 .(21/3 – 1) = 3. (1.26 - 1) = 3 . 0.26 = 0.78
=> 1.11 ≤ 0.78 is False. We can conclude from here that the tasks are not schedulable
according to RM algorithm.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Question.6. Difference between EDF and RM.
Answer:
EDF characteristics:
- Dynamic Priority Scheduling Algorithm
- Schedule on deadline basis; i.e., earliest deadline jobs need to execute first.
- Here Preemption is allowed.
- Fixed/Static Priority Scheduling Algorithm
- Schedule on priority basis; i.e., higher priority jobs need to execute first.
- Here Preemption is allowed
Question.7. A system
consists of three periodic tasks: T1=(3, 1), T2=(5, 2) and T3=(8, 3). Suppose
we want to reduce the execution time of the task with period 8 in order to make
the task system schedulable according to the earliest deadline first (EDF)
algorithm. What is the minimum amount of reduction necessary for the system to
be schedulable by the EDF algorithm?
Answer: The tasks can be scheduled provided the
total utilization is ≤ 1
Hence,
u1 + u2 + u3 ≤ 1
=> u1 + u2 + E3/p3 ≤ 1
=> 0.33 + 0.4 + E3/8 ≤ 1
=> E3 should be reduced from 3 to 2.16
Hence the modified Tasks are
T1=(3, 1), T2=(5, 2) and T3=(8, 2.16)
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Question.8. What is meant by online scheduling of tasks? Name the algorithm which would be used?
Answer : Online Scheduling
Question.8. What is meant by online scheduling of tasks? Name the algorithm which would be used?
Answer : Online Scheduling
- Online scheduling is done at run-time based on the information about the tasks arrived so far.
- If the scheduler creates each scheduling choice without knowledge about the jobs that will be released in the future, then scheduling is said to be done online.
- Scheduling is done online when we use an online scheduling algorithm.
-
Online scheduling can accommodate dynamic variant in user demands and resource readiness but it cannot make the top use of system resource.
Algorithms Used for Online Scheduling:
- Static priority driven algorithms
- assign fixed priorities to the tasks before the start of the system.
- Rate monotonic (RM) scheduling algorithm is a uni-processor static-priority preemptive scheme.
- Priority inheritance protocol (PIP) dynamically changes the priority of a task if it is blocking a higher priority task.
-
Priority ceiling protocol (PCP) avoids deadlock by taking each semaphore allocated a priority ceiling which is the priority of the uppermost priority task that practices it.
- Dynamic priority driven algorithms
- assign the priorities to tasks during run-time.
- Earliest deadline first (EDF) is a dynamic priority driven scheduling algorithm which gives tasks priority based on deadline.
- Least laxity first (LLF) also known as least slack time, is a dynamic priority driven scheduling algorithm that assigns priority based on the laxity.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Question.9: What is
RMScheduling ? Check if the following tasks are schedulable by RM scheduling
algorithm T(e,d) { T1(3,4), T2(4,5) , T3(5,6) and T4(6,7) }.
Answer:
Answer:
RM Scheduling: It's an
important event-driven scheduling algorithm, RMA assigns priorities to tasks
based on their rates of occurrence. The lower the incidence rate for a job, the lower priority will be given. The priority of a task is inversely proportional to its period (or, directly
proportional to its rate).
- First Constraint: A set of periodic real-time tasks will not be scheduled until the RMA is completed, as long as they do not meet the following required condition.
Total utilization = ∑ Ei / Pi
Total utilization U ≤ 1
- Second Constraint: The below condition should satisfy i.e. Utilization Bound Test
Given: T1(3,4), T2(4,5) , T3(5,6) and T4(6,7)
Check schedulability:
1. First constraint(Precise test):
Total utilization U ≤ 1 .
In this case the task is in order T(e,d)
Therefore , Ei or e = execution time
Di or d = period or Pi
Hence the tasks are not schedulable under RM algorithm.
2. Second Constraint(Utilization bound Test): Again we need to prove that,
Question.10.: Consider the task set: {(1,3),(1,5),(1,6),(2,10)}, is task 4 set schedulable?
Answer: To solve this question, we need to go through with Response Time first.
Study material:
Question.11.: What do you understand by the term makespan ? Give an example.
Answer:
Makespan: The makespan is the completion time of the last job in the sequence or The makespan is the sum of all the processing times.
Example: Consider a single machine that processes five jobs. The jobs are named J1 to J5. The processing times are 10, 8, 6, 12 and 14 minutes. The delivery timings (due dates) of the five jobs are 8, 16, 25, 30 and 40 respectively. If you choose to follow a sequence J2-J4-J3-J1-J5 then what would be the makespan ?
The jobs are sent in the order or sequence J2-J4-J3-J1-J5. Job J2 enters at time = 0 and is completed at time = 8. Job J4, which is the next job in the sequence immediately enters at time = 8 and finishes at time = 8 + 12 = 20. This process continues till the last job J5 is completed at time = 50. The completion times for the jobs (according to the given sequence) is J2 = 8, J4 = 20, J3 = 26, J1 = 36 and J5 = 50.
The makespan is the completion time of the last job in the sequence. For the sequence J2- J4-J3-J1-J5, the makespan is the completion time of J5 which is 50.
Study material: The completion times for the jobs (according to the given sequence) is J2 = 8, J4 = 20, J3 = 26, J1 = 36 and J5 = 50. The total completion time is 140 and the mean completion time is 140/5 = 28
Answer:
Check schedulability:
1. First constraint(Precise test):
Total utilization U ≤ 1 .
In this case the task is in order T(e,d)
Therefore , Ei or e = execution time
Di or d = period or Pi
Now by the formula U = ∑ Ei / Pi
U = 3/4+4/5+5/6+6/7
U = 0.75 + 0.8 + 0.83 + 0.85
U =3.23 > 1
Hence the tasks are not schedulable under RM algorithm.
2. Second Constraint(Utilization bound Test): Again we need to prove that,
Hence,
3.23 ≤ 4 *(21/4 – 1) = 4* (1.18 - 1) = 4 * 0.18 = 0.72
=> 3.23 ≤ 0.72 is
False. We can conclude from here that the tasks are not schedulable
according to RM algorithm.
Therefore
the tasks T1(3,4),
T2(4,5), T3(5,6) and T4(6,7) are not schedulable by RM scheduling
algorithm.
-------------------------------------------------------------------------------------------------------------------------------------------------------------------Question.10.: Consider the task set: {(1,3),(1,5),(1,6),(2,10)}, is task 4 set schedulable?
Answer: To solve this question, we need to go through with Response Time first.
Study material:
Calculate
the worst case response time R for each task with deadline D. If R<=D(period),
the task is schedulable/feasible. Repeat the same check for all tasks.
Ri= Ci + åj Î HP(i) éRi/Tjù*Cj
where,
Ri stand for the response time for task i
Ci is the computing time.[execution time]
Let U= Σ Ci/Ti [ei/pi or ei/di]
and B(n) = n*(21/n-1) [Utilization
Bound Test]
Three possible outcomes:
0<= U<= B(n): schedulable
B(n)<U<=1: no conclusion
1< U : overload
Example:
Assume a task set:T(e,d) {(1,3),(1,5),(1,6),(2,10)}
CPU utilization U= 1/3+1/5+1/6+2/10=0.899
The utilization bound B(4)=0.756
The task
set fails in the UB test due to U>B(4)
Solution: Given as, {(1,3),(1,5),(1,6),(2,10)}
CPU utilization U=
1/3+1/5+1/6+2/10=0.899> B(4)= 0.756
Fail the UB test!
But U(3)= 1/3+1/5+1/6=0.699
This means that the first 3 tasks
are schedulable.
is task 4 set schedulable?
Hence, Not schedulable.
Because If R<=D(period), the task is schedulable/feasible.
Question.11.: What do you understand by the term makespan ? Give an example.
Answer:
Makespan: The makespan is the completion time of the last job in the sequence or The makespan is the sum of all the processing times.
Example: Consider a single machine that processes five jobs. The jobs are named J1 to J5. The processing times are 10, 8, 6, 12 and 14 minutes. The delivery timings (due dates) of the five jobs are 8, 16, 25, 30 and 40 respectively. If you choose to follow a sequence J2-J4-J3-J1-J5 then what would be the makespan ?
The jobs are sent in the order or sequence J2-J4-J3-J1-J5. Job J2 enters at time = 0 and is completed at time = 8. Job J4, which is the next job in the sequence immediately enters at time = 8 and finishes at time = 8 + 12 = 20. This process continues till the last job J5 is completed at time = 50. The completion times for the jobs (according to the given sequence) is J2 = 8, J4 = 20, J3 = 26, J1 = 36 and J5 = 50.
The makespan is the completion time of the last job in the sequence. For the sequence J2- J4-J3-J1-J5, the makespan is the completion time of J5 which is 50.
Study material: The completion times for the jobs (according to the given sequence) is J2 = 8, J4 = 20, J3 = 26, J1 = 36 and J5 = 50. The total completion time is 140 and the mean completion time is 140/5 = 28
Question.12.: What do you understand by the term makespan ? Compute the
makespan on the following processors.
Assume the schedule to be work conserving
T(e,d) T1(2,3), T2(3,7) and T3(4,13) on Processor P1.
T4(3,5) T5 (4,11) and T6(5, 18) on Processor P2.
Answer: Makespan: The makespan is the sum of all the processing time scheduled on a processors.
Makespan on P1 =
2+3+4 = 9 units; Makespan on P2 = 3+4+5=12 units
As given, Scheduler is a work conserving, The processor is never idle when tasks are awaiting
execution.
Question.13: What do you understand by the term hyperperiod ? Compute the hyperperiod of
the following tasks T(e,p) {T1(3,6) T2(4,12) and T3(5,18)}.
Answer: Hyperperiod: Hyperperiod is the duration of the largest task present in
the task set under consideration. Mathematically it is the least common
multiple of all task periods of the task set under consideration.
Hyperperiod of task set = LCM {6,12,18} = 36 units
Question.14.: Compute the RM Schedulability upper bound for a system with
4 tasks.
Answer:
RM schedulability upper bound = (n*(2(1/n)-1))
Here n=4
RMupper = (4* (2(1/4)-1))= 0.76
Question.15.:
Schedule the following tasks by non-weighted round robin ?
Task
|
Execution
time
|
T1
|
5
|
T2
|
6
|
T3
|
4
|
T4
|
7
|
T5
|
5
|
Compute the
makespan, number of cycles for the above task set with a time slice of 3
units?
Answer:
Cycle 1:
T1 (3) T2(3) T3(3) T4(3) T5(3)
Cycle 2:
T1(2) T2(3) T3(1) T4(3) T5(2)
Cycle 3:
T4(1)
3 Cycles and Makespan = 3+3+3+3+3+2+3+1+3+2+1=27 units.
Question.16: Consider the tasks T(e,d) T1(2,5), T2(3,6), T3(2,7),
T4(1,8), T5(2,9)
The start times of the tasks which is also the current
time of T1,T2,T3,T4 and T5 is 1,2,3,4 and 5
The min and max execution times of tasks T(min, max)
T1(2,3), T2(3,4), T3(2,4),T4(1,2) and
T5(2,3). Compute the laxity for all tasks..
Answer:
Laxity =(deadline –(current time + min exec time))
L1=5-(1+2)=2
L2=6-(2+3)=1
L3=7-(3+2)=2
L4=8-(4+1)=3
L5=9-(5+2)=2
