Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Periodic Task
3.
Dynamic task
3.1.
Aperiodic Task
3.2.
Sporadic Task
4.
Critical Task
5.
Non Critical Task
6.
Task Scheduling
6.1.
Valid Schedule
6.2.
Feasible Schedule
6.3.
Proficient Scheduler
6.4.
Optimal Scheduler
6.5.
Scheduling Points
6.6.
Preemptive Scheduler
6.7.
Utilization
6.8.
Jitter
7.
Frequently Asked Questions
7.1.
Which tuple is considered for the execution of the task?
7.2.
What is the use of a preemptive scheduler?
7.3.
What is the hyper period of a set of periods?
8.
Conclusion
Last Updated: Mar 27, 2024

Tasks in Real-Time Systems

Author Divyansh Jain
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

A real-time Operating System (RTOS) supports real-time applications that process data without any buffering delay.  It is a time-bound system with defined time constraints. 

Moreover, the system is subjected to real-time limitations, which means that reaction time must be assured within a specific time restriction or the system must meet a deadline. Processing must take place within the given restrictions in this type of system. Otherwise, the system will be rendered useless.

For example, flight control systems, real-time monitors, and other similar devices.

Tasks in Real Time

Types of real-time systems

  1. Periodic Task
  2. Dynamic Task
    1. Aperiodic Task
    2. Sporadic Task
  3. Critical Task

4. Non-critical task

Also see: Multiprogramming vs Multitasking

Periodic Task

The periodic task repeats itself after a fixed period of time. It is denoted by four tuples, are Ti = < Φi, Pi, ei, Di > 

Φi: it is determined as a phase of the task, if the phase of the task is missing then the release time of the first job is assumed to be zero, where the phase of the task is the release time of the first job in the task.

Pi: it is determined as the period of the task.The time interval between the release times of two consecutive tasks.

ei: It is determined as the execution time of the task.

Di: It is determined as the relative deadline of the task.Periodic Task

  • Here, consider a task T with period = 8 and execution time = 5. 
  • Phase is not given so, assume the release time of the first job as 0. Job is first released at t = 0 and it executes for 5s and then the next job is released at t = 8 which executes for 5s and then the next job is released at t = 16. 
  • So the jobs are released at t = 8n, where n = 0,1,2,3,4,...
  • The hyper period of a set of periodic tasks is the least common multiple of all the tasks in that set's period.
  • For example, two tasks having periods 5 and 6 will have a hyper period of 30, i.e, LCM(5,6) = 30.
  • The hyper phase is the point at which the pattern of job release times begins to repeat itself.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Dynamic task

It is a sequential program that is triggered/fired by the occurrence of an event. An event can be generated by either external or internal system activities.

Dynamically arriving tasks can be classified based on their criticality and knowledge of their occurrence periods.

Aperiodic Task

Jobs are released at arbitrary time intervals, i.e., at random. In this form of task, soft deadlines or no deadlines apply to aperiodic jobs.

Sporadic Task

They are similar to aperiodic activities in that they repeat at random. The only distinction is that irregular tasks have strict deadlines

A sporadic task is represented by three tuples: Ti =(ei, gi, Di) 

where,

ei – the execution time of the task. 

gi – the minimum separation between the occurrence of two consecutive instances of the task. 

Di – the relative deadline of the task.

Critical Task

These tasks have a critical deadline. If missed, catastrophes occur. For example, stability control and life support systems of aircraft. 

It is necessary when critical tasks are executed at a higher frequency.

Non Critical Task

These are tasks that must be completed in real-time. As the name suggests, they are not critical to the application. They can deal with time and altering data, but they're useless if they're not done on time.

The purpose of scheduling these tasks is to maximize the percentage of jobs that are completed on time.

Task Scheduling

Real-time task scheduling fundamentally relates to determining how the operating system chooses which tasks to execute. 

Every operating system relies on one or more task schedulers to plan the execution of various tasks that must be completed. 

The scheduling algorithm used by each task scheduler distinguishes it. So far, a vast number of algorithms for real-time job scheduling have been created.

Types of task schedulings are as follows :
 

Task Scheduling

Valid Schedule

A proper schedule for a collection of tasks is one in which only one task is allocated to a processor at a time, no task is scheduled before its arrival time, and all tasks' priority and resource limitations are met.

Feasible Schedule

A valid schedule as discussed above is called a feasible schedule only if all tasks meet their time constraints in the specified schedule.

Proficient Scheduler

A task scheduler S1 is more proficient than another scheduler S2 if S1 can schedule all task sets that S2 can schedule, but not vice versa. 

  • S1 can reasonably plan all work sets that S2 can, but S2 cannot feasibly schedule at least one task set that S1 can. 
  • If S1 can schedule all task sets that S2 can schedule, and vice versa, then S1 and S2 are referred to as equally proficient schedulers.

Optimal Scheduler

A real-time task scheduler is said to be optimal if it can schedule any task set that any other scheduler can schedule. 

In other words, there would be no more proficient scheduling algorithm than an optimal scheduler. 

If an optimal scheduler is unable to schedule a task set, no other scheduler should be able to construct a workable schedule for that task set.

Scheduling Points

A scheduler's scheduling points are the points on a timeline at which the scheduler decides which task should be done next. 

  • It is crucial to understand that a task scheduler does not have to run continuously, and the operating system simply uses it at scheduling points to determine which task to perform next. 
  • In a clock-driven scheduler, scheduling points are defined as instants marked by interruptions created by a periodic timer. 
  • In an event-driven scheduler, the occurrence of specific events determines the scheduling points.

Preemptive Scheduler

A preemptive scheduler is one that, when a higher priority task comes, suspends any lower priority task that is currently running and resumes execution of the higher priority task. 

As a result, with a preemptive scheduler, it is not possible for a higher-priority item to be ready for execution while a lower-priority task is executing. A lower-priority job that has been preempted can restart execution only when no higher-priority task is ready.

Utilization

The processor utilization (or utilization) of a task is the average time it spends executing per unit time interval.

In notation:
for a periodic task Ti, the utilization ui = ei/pi
where, 
ei = execution time and 
pi = period of Ti. 
{Ti} = For a set of periodic tasks: the total utilization due to all tasks for a set of periodic tasks,

 U = i=1∑ n ei/pi.


The goal of any good scheduling algorithm is to schedule even task sets with extremely high utilization, i.e., utilization close to 1.  Of course, on a uniprocessor, task sets with utilizations greater than 1 are not possible to schedule.

Jitter

A jitter is a periodic task's deviation from its precise periodic behavior. Arrival time jitter is the task's variation from the accurate periodic time of arrival. 

It could be due to inaccurate clocks or other things such as network congestion

Similarly, completion time jitter refers to the divergence of a task's completion from precise periodic points.

Note: The completion time jitter may be generated by the particular scheduling method utilized, which takes up a job for scheduling based on convenience and load at an instant, rather than scheduling at some strict time instants. 

Jitters are unsuitable for some applications. Sometimes the actual release time of a job is not known. 

Note that ri is in a range [ri-, ri+]. And, this range is considered a release time jitter. Here,

  • ri is the minimum amount of time a task may be released, 
  • ri+ is the maximum amount of time a task may be released, and

Only the range [ei-, ei+] of the completion time of a job is known. Here

  • ei- is the shortest length of time a job needs to finish its execution, and
  • ei+ is the highest amount of time a job needs to complete its execution.


You can also read about layered structure of operating system.

You can read related articles such as Congestion Control in Computer Networks here.

Frequently Asked Questions

Which tuple is considered for the execution of the task?

We use the tuple ei for the execution of the task in a real-time system while Φi”,”Pi”,”Di”  are determined as phase, period, and relative deadline of the task.  

What is the use of a preemptive scheduler?

When a process transitions from the running to the ready state, or from the waiting to the ready state, preemptive scheduling is used.

What is the hyper period of a set of periods?

A hyper period of two schedules is the least common multiple of all the tasks in that set's period. For example, two tasks having periods 2,3, and 7 will have a hyper period of 42.

Conclusion

To summarize the article, we discussed the various types of real-time systems and we dealt with all kinds of tasks in brief. Then we learned how task scheduling works and the eight types of task scheduling in detail. Hope you learned something. But the knowledge never stops, so to better understand the operating systems, you can go through many articles on our platform.

Recommended Reading: 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning Ninja :) 

Previous article
Real-Time Applications
Next article
Macintosh Operating Systems (Mac OS)
Live masterclass