Showing posts with label RTOS. Show all posts
Showing posts with label RTOS. Show all posts

July 20, 2018

Real Time Operating System Importance - Important QnA


Text Books
T1 Liu, Jane W.S., Real Time Systems, Pearson Education, 2000
T2 Laplante, Phillip A., Real-Time Systems Design and Analysis, Wiley, 3rd Ed., 2004
T3 Jared Hendrix, Raspberry Pi: Essential guide on starting your own raspberry pi3 projects with ingenious tips and tricks
T4 Arshdeep Bahga, Vijay Madisetti, Internet Of Things A hands on Approach


 

Question.1
Design a Biometric Facial Authentication device for a small company of 25 employees. The device should be capable of Enrolling and verifying the face. If the face matches then allow access into the company. The enrollment of New Ids should be stored in the organization database server and the ex-employees access should be denied.Draw the block diagram including the Components required for the design.List out the tasks: periodic, aperiodic and sporadic tasks of the system. Which scheduling algorithm should be used. Illustrate the same with an example. 

Answer:

Components required:




Periodic tasks
LCD  display 
Reading data base till match is found or END of database- 

Aperiodic Task
Face sensing through sensor 
Temporary storing of minutiae points from the image 
Matching the temporary image and database image 
Allowing access into organization(ex: opening of gate etc)

Sporadic tasks: None

Clock driven scheduling algorithm using the above parameters.

Question. 2
Consider a task set comprising of 5 tasksT(e,d) T1(13,20), T2(12,30), T3(18,40), T4(15,50) and T5(14,60) to be scheduled on 2 processors. Which scheduling strategy would ensure tasks get an optimal share of resources. The resource actually consumed is 20% (rounded off to the nearest integer). Assume the first task starts at 0.Construct the schedule and obtain the makespan.

 Answer:

The algorithm for Optimal utilization is Uniform Laxity based method as it uniformly dispenses slack improving resource allocation.

Minimum execution time = 20% of Actual execution time
Min 1 =0.2*13=2.6 = 3 (approx)
Min2= 0.2*12=2.4 = 2(approx)
Min3=0.2*18=3.6=4 (approx)
Min4=0.2*15=3(approx)
Min5=0.2*14=2.8=3(approx)

Laxity = (deadline –(current time +minimum execution time))
L1=(20-(0+3))=17
L2=(30-(20+2))=8
L3=(50-(40+3))=7
L4=(60-(50+3))=7
L5=(30-(25+2))=3
Average Laxity=9

Time utilized =Min exec time + Average Laxity
TU1=3+9=12
TU2=2+9=11
TU3=4+9=13
TU4=3+9=12
TU5=3+9=12

Slack Available = WCET-Time Utilised
S1=13-12=1
S2=12-11=1
S3=18-13=5
S4=15-12=3
S5=14-12=2


Makespan on P1= 12+11 = 23 units
Makespan on P2= 13+12+12 = 37 units

Question. 3
Draw petrinet model for vending machine, The machine dispenses two kinds of snack bars – 20c and 15c.
Only two types of coins can be used – 10c coins and 5c coins. The machine does not return any change.


Answer:
3 scenarios can be considered,
  Scenario 1: 
Deposit 5c, deposit 5c, deposit 5c, deposit 5c, take 20c snack bar.

  Scenario 2:
Deposit 10c, deposit 5c, take 15c snack bar.

  Scenario 3:

Deposit 5c, deposit 10c, deposit 5c, take 20c snack bar.


Question. 4
Given seven tasks, A, B, C, D, E, F, and G, construct the precedence graph from the
following precedence relations:.
A → C
B →C B→ D
C →E C→ F
D →F D→ G
Then, assuming that all tasks arrive at time t = 0, have deadline D = 25, and computation
times 2, 3, 3, 5, 1, 2, 5, respectively, modify their arrival times and deadlines to schedule
them by EDF.

Answer:

The precedence graph is shown below:









Question. 5
Let us consider an automatic car body painting machine has two robotic arms R1 and R2. The real time system that is responsible for paint operation has five different processes P1, P2, P3, P4 and P5. The release time and CPU burst time of each process is ri=(7, 5, 4, 2 and 0) and ei=(3, 3, 2, 6 and 6) respectively. The process P1 requires the robotic arm R1 for duration of 1 unit of time and it is required at time 8. Similarly the process P2 and P5 needs another arm R2 at time 6 and 1 respectively. The process P2 and P5 needs those resources for a period of 1 and 4 unit of time respectively. However, the process P4 required both the robotic arm R1 and R2 for a period of 4 and 1.5 unit of time and at 3 and 9 unit of time. The priority of the process varies with its number i.e. P1 has maximum and P5 has minimum priority. Now schedule those processes by considering the priority ceiling protocol. Determine that if there is any process will be blocked because of resource conflict also find the time of block. Also draw the time line diagram illustrating the above example. Assume you have only one CPU and the robotic arm are non-pre-emptible.

Answer:



May 27, 2018

Real time Operating Systems - MCQS


Question.
IRIS Stands:

Iney Reward with Increased Service
Increased Raw with Increased Service
Increased Reward with Increased Service
None of these

The correct answer is: Increased Reward with Increased Service

Question 
Which of these is true about an open loop system vs closed loop system:

Closed loop systems are comparatively cheaper as they require less components & design effort
Open loop system provides better control in the presence of environmental disturbance
An open loop system can be made closed loop by introducing  and controlling
A kitchen toaster is a closed loop system

The correct answer is: An open loop system can be made closed loop by introducing  and controlling

Question 
RTOS is ________ in nature

timely
memory oriented
high cpacity
non-accurate

The correct answer is: timely

Question 
True for a task vis-à-vis a process?

Tasks are complex compared to processes
Tasks and processes are one and the same thing
Processes can spawn threads but tasks cannot spawn tasks
Tasks represent only a single sequence of instructions 

The correct answer is: Tasks represent only a single sequence of instructions

Question 
Cheddar is written in

 Perl
Ada
Python

The correct answer is: Ada

Question 
In real time operating system

kernel is not required
all processes have the same priority
process scheduling can be done only once
a task must be serviced by its deadline period

The correct answer is: a task must be serviced by its deadline period

Question 
A RTOS is characterised by

Select one:
1. Kernel is not required
2. Same priority for all processes
3. A task must be serviced on time or before time
4. Single time process scheduling

The correct answer is: A task must be serviced on time or before time

Question 
In which scheduling certain amount of CPU time is allocated to each process?

Select one:
1. Equal share scheduling          
2. None of the mentioned
3. Earliest deadline first scheduling
4. Proportional share scheduling

The correct answer is: Proportional share scheduling

Question 
Time gap in-between release time of the job and the time when it completes is

Response Time
Turn around time
Rotation Time

The correct answer is: Response Time

Question 
Hard real time operating system has   ---------jitter than a soft real time operating system

less
more
equal

The correct answer is: less

Question 
The family of processor used in Raspberry Pi is _______

Intel
Motorola
Broadcomm
ARM Correct

The correct answer is: ARM

Question 
Tasks whose execution would begin randomly and within the interval of arrival times of consecutive tasks is known as

Periodic Task
Aperiodic Task
Sporadic Task

The correct answer is: Sporadic Task

Question 
In the current market scenario, IoT captures the maximum share in which one of these?

Select one:
1. Home automation
2. Healthcare
3. Security
4. Industry

The correct answer is: Industry

Question 
The time T between any two consecutive sensor reading is called

Sampling Period
Response Time
Turn around time

The correct answer is: Sampling Period

Question 
Identify the odd one out:

Periodic Task
Aperiodic
Sporadic Tasks
Non-periodic

The correct answer is: Non-periodic

Question
Internet of Things (IoT) can be integrated with which of these separate domains:

Select one:
1. Big-data networks.
2. All
3. Cloud-based storage and computing.
4. Cyber Physical Systems.

Answer: All

Question 
The problem of priority inversion can be solved by

priority inheritance protocol
priority inversion protocol
both (a) and (b)
none of the mentioned

The correct answer is: priority inheritance protocol

Question 
In real time operating system

all processes have the same priority
a task must be serviced by its deadline period
process scheduling can be done only once
kernel is not required

The correct answer is: a task must be serviced by its deadline period

Question 
What are the risks and challenges that we should be aware of when it comes to the Internet of Everything :

Privacy.
Security
Network congestion
Electricity consumption at the peaks
All of these

The correct answer is: Electricity consumption at the peaks

Question 
Embedded system does not contain _________.

Sensors
Actuators
Microcontrollers
None of these

The correct answer is: None of these

Question 
System which processes data instructions without any delay is classified as

real time system
online system
offline system
instruction system

The correct answer is: real time system

Question 
The default language supported by Raspberry Pi board is _________.

Java
Python
C
C#

The correct answer is: Python

Question 
Proportion of Real time and Non-real time tasks in a system

70%, 30%
50%,50%
60%,40%
80%, 20%

The correct answer is: 70%, 30%

Question 
What is the top M2M  acronym stands for:

The acronym M2M application stands for Machine to Man applications
The acronym M2M application stands for Mobile to Mobile applications
The acronym M2M application stands for Machine to Machine applications
None of these

The correct answer is: The acronym M2M application stands for Machine to Machine applications

Question.
The EDF scheduler uses ________ to order requests according to their deadlines.

Select one:
stack
disks
queue
none of the mentioned

Answer: queue

Question
System which processes data instructions without any delay is classified as

Select one:
1. Real time system
2. Offline system
3. Online system
4. Instruction system

Answer: Real time system

Question.
Use of robot by the car manufacturing companies is an example of

Select one:
machine controlled computers
network controlled computers
applicant controlled computers
user controlled computers

Answer: machine controlled computers

Question.
VxWorks is centered around

Select one:
wind microkernel
linux kernel
unix kernel
none of the mentioned

Answer: wind microkernel

Question.
EDF algorithm assigns priorities according to :

Select one:
periods
deadlines
burst times
none of the mentioned

Answer: deadlines

Question.
The priority of a real time task :

Select one:
must degrade over time
must not degrade over time
may degrade over time
none of the mentioned

Answer: must not degrade over time

Question.
What is jitter in Real-time terminology:

Select one:
Variation in a parameter. For example, variation in arrival rates, computation durations, or communication latencies.
An event with an arrival pattern that has a bounded minimum interarrival time with stochastic jitter.
The activation of a task such that it will be considered by the RTOS for execution on the CPU..
None of these

Answer: Variation in a parameter. For example, variation in arrival rates, computation durations, or communication latencies.

Question.
Scheduling of tasks is a very important consideration in RTOS. Which of the following best described the scheduling policy design:

Select one:
The scheduler must follow a pre-emptive policy
The scheduler must not use pre-emptive policy option
The scheduler must not only use pre-emptive policy options with the priority considerations.
The scheduler must not use pre-emptive policy option, but must employ priority consideration

Answer: The scheduler must not use pre-emptive policy option, but must employ priority consideration

Question.
Type of processor in which single task of a particular application is process is termed as

Select one:
real time processor
dedicated processor
applicant processor
one task processor

Answer: dedicated processor

Question.
Chose the statement with respect to RTOS.

Select one:
A real time operating system (RTOS) is an operating system that guarantees a certain capability within a specified time constraint.
An OS is a system program that provides an interface between application programs and the computer system (hardware)
The applications where dependability that a certain task will finish before a particular deadline is just as obtaining the correct results.
Besides meeting deadlines RTOS must also be able to respond predictably to unpredictable events and process multiple events concurrently.
all of above

Answer: all of above

Question
In rate monotonic scheduling algorithm

Select one:
1. Shorter duration job has higher priority
2. Priority does not depend on the duration of the job
3. Longer duration job has higher priority
4. None of the mentioned

Answer: Shorter duration job has higher priority

Question.
Keeping a task’s schedulability in mind, which way a task may be scheduled

Select one:
The task has a predetermined time after which it may be scheduled.
The task has a predetermined time before which it may be scheduled
The task has a predetermined time interval during which it must be scheduled any time.
The task start has a worst case delay estimate before which it must be scheduled

Answer: The task has a predetermined time interval during which it must be scheduled any time.

Question.
Time duration required for scheduling dispatcher to stop one process and start another is known as

Select one:
process latency
dispatch latency
execution latency
interrupt latency

Answer: dispatch latency

Question.
if jobs have unpredictable release times, a task is termed  :

Select one:
aperiodic
sporadic
periodic.
None of these

Answer: aperiodic

Question.
Time required to synchronous switch from the context of one thread to the context of another thread is called

Select one:
threads fly-back time
jitter
context switch time
none of the mentioned

Answer: context switch time

Question.
Which of the following describes the RTOS design philiosophy best

Select one:
Maximize the throughput of the system
Maximize the processor utilization
Minimizing the response time
Response within certain stipulated time period

Answer: Minimizing the response time

Question.
Delay and Jitter :

Select one:
mean the same thing
are two completely different things
all of the mentioned
none of the mentioned

Answer: are two completely different things

Question.
IRIS Stand for :

Select one:
Increased Reward with Increased Service
Iney Reward with Increased Service
Increased Raw with Increased Service
None of these

Answer: Increased Reward with Increased Service

Question.
Which one of the following is a real time operating system?

Select one:
RTLinux
VxWorks
Windows CE
All of the mentioned

Answer: All of the mentioned

Question
IF jobs have unpredicted release times, then the jobs are called

Select one:
1. Periodic
2. Aperiodic
3. Regular
4. Sporadic

AnswerAperiodic

Question.
In rate monotonic scheduling

Select one:
shorter duration job has higher priority
longer duration job has higher priority
priority does not depend on the duration of the job
none of the mentioned

Answer: shorter duration job has higher priority

Question.
The major difference between a multimedia file and a regular file is :

Select one:
the size
the attributes
the ownership
the rate at which the file must be accessed

Answer: the ownership

Question.
Rate monotonic scheduling assumes that the :

Select one:
processing time of a periodic process is same for each CPU burst
processing time of a periodic process is different for each CPU burst
periods of all processes is the same
none of the mentioned

Answer: processing time of a periodic process is same for each CPU burst.

Question.
System which processes the data instructions without any delay is classified as

Select one:
online system
offline system
instruction system
real time system

Answer: real time system

Question.
Delay is :

Select one:
the time from when a request is first submitted to when the desired result is produced
the delay that occurs during playback of the stream
how the errors are handled during transmission and processing of continuous media
none of the mentioned

Answer: the time from when a request is first submitted to when the desired result is produced

Question.
Preemptive, priority based scheduling guarantees :

Select one:
hard real time functionality
soft real time functionality
protection of memory
none of the mentioned

Answer: soft real time functionality

Question.
Describe which of these scheduling policies is most suited for controlling a set of periodic tasks.

Select one:
FCFS
Least laxity first
Earliest dead line first
Rate monotonic policy schedule

Answer: FCFS

Question.
Designing of system take into considerations of

Select one:
hardware
communication system
operating system
all of above

Answer: all of above

Question.
RM Schedulable upper bound for a system with 4 tasks is

Select one:
0.66
0.95
0.44
0.76

Answer: 0.76 [This has been calculated using Utilization Bound]

Question.
Real time systems must have :

Select one:
preemptive kernels
non preemptive kernels
preemptive kernels or non preemptive kernels
neither preemptive nor non preemptive kernels

Answer: preemptive kernels

Question.
Consideration of storage, input and output devices are considered as requirement of

Select one:
hardware requirement
communication requirement
software requirement
process requirement

Answer: hardware requirement

Question.
If a set of processes cannot be scheduled by rate monotonic scheduling algorithm, then :

Select one:
they can be scheduled by EDF algorithm
they cannot be scheduled by EDF algorithm
they cannot be scheduled by any other algorithm
none of the mentioned

Answer: they cannot be scheduled by EDF algorithm

Question.
Hard real-time system is A

Select one:
system with deadline is very Hard
system with stringent deadlines
system whose deadline is very hard to determine
System whose deadline is not so hard to determine

Answer: system with stringent deadlines

Question.
Which one of the following is the characteristic of a multimedia system?

Select one:
high storage
high data rates
both high storage and high data rates
none of the mentioned

Answer: both high storage and high data rates

Question.
Identify which of these are real-time applications scenarios:

Select one:
An on-line bus ticketing system
Printing of annual report of a company’s annual report
Reconciling a day’s transactions in an account book of a small company
An aircrafts  yaw control system

Answer: Printing of annual report of a company’s annual report

Question.
Hyper period of the following tasks T(e,p) {T1(3,6) T2(4,12)}
Select one:
6
4
12
2

Answer: 12

Question.
Slack time

Select one:
is the amount of time left after a job if the job was started now.
is the amount of time left before a job if the job was started now.
is the amount of time left from a job if the job was started now.
is the amount of time left required by a job if the job was started now.

Answer: is the amount of time left after a job if the job was started now

Question.
The delay that occur during the playback of a stream is called

Select one:
stream delay Incorrect
playback delay
jitter
event delay

Answer: jitter

Question
Hard real time operating system has ___ jitter than a soft real time operating system.
Select one:
1. More
2. Equal
3. None
4. Less

Answer: Less

Question
Which of the following is never a part of open loop control system

Select one:
1. Controller
2. Actuator
3. Error Detector
4. Sensor

Answer: Error Detector

Question
For real time operating systems, interrupt latency should be
Select one:
1. Dependent on the scheduling
2. Zero
3. Maximum
4. Minimal

Answer: Minimal

Question
Gyroscope is a sensor which measures

Select one:
1. Acceleration
2. Physical orientation   
3. Velocity
4. Pressure

Answer: Physical orientation 

May 23, 2018

Real Time Operating Systems Importance - MID Sem Excercise


Question.1What 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-Hard RTOs
(d)    Flight simulator video game-Soft RTOs
(e)    Battery operated toy robot used at home for normal routine tasks-Soft RTOs
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Question.2.  Elements/Terms used in Real time Systems.

Answer
  1. Resources – Basically this can be a CPU, memory, time or any resource directly related to a task.
  2. 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]
  3. 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.
  4. 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.
  5. Period - Minimum time interval between release times of consecutive jobs.
  6. 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]
  7. 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.
  8.  Periodic Task: If jobs have predictable release times, a task is termed aperiodic. 
  9. Aperiodic Task: If jobs have unpredictable release times, a task is termed aperiodic.
  10. 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.

AnswerCharacteristics 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:
  • Dynamic Priority Scheduling Algorithm
  • Schedule on deadline basis; i.e., earliest deadline jobs need to execute first.
  • Here Preemption is allowed.
RM characteristics:
  • 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?

AnswerThe 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
  • 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:
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).

The following are some important criteria that can be used to check the schedulability of a set of tasks set under RMA.
  • 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


                   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 + åΠ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