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 :
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 :)
8+ registered 