Real-Time Scheduling in Linux
Learn about the various scheduling classes in Linux, including real-time scheduling like SCHED_RR and SCHED_FIFO. Explore tasks, priorities, and how the next task is chosen. Discover the goal of real-time OS support for predictable execution. Dive into the world of operating systems with this advanced topic.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Scheduling Classes and Real-Time Scheduling in Linux David Ferry, Chris Gill CSE 522S - Advanced Operating Systems Washington University in St. Louis St. Louis, MO 63143 1
Scheduling Classes Multiple schedulers are implemented as different scheduling classes. Normal: SCHED_NORMAL: regular, interactive CFS tasks SCHED_BATCH: low priority, non-interactive CFS tasks SCHED_IDLE: very low priority tasks Real-time: SCHED_RR: round-robin SCHED_FIFO: first-in, first-out SCHED_DEADLINE: earliest deadline first CSE 522S Advanced Operating Systems 2
struct sched_class A few major functions: Other functions: Task migration Task yielding Task state queries Other utilities CSE 522S Advanced Operating Systems 3
Current Scheduling Classes and Ordering 1. stop_sched_class //for halting processors 2. dl_sched_class 3. rt_sched_class 4. fair_sched_class 5. idle_sched_class Declared in /kernel/sched/sched.h CSE 522S Advanced Operating Systems 4
Example sched_class Definition From: /kernel/sched/rt.c CSE 522S Advanced Operating Systems 5
How the Next Runnable Task is Picked Function pick_next_task()from /kernel/sched/core.c Have all scheduling classes try to pick a new task The last class, SCHED_IDLE, should always return some idle task CSE 522S Advanced Operating Systems 6
Real-Time Scheduling Real-time tasks execute repeatedly (usually are periodic) under some time constraint Task Task Task Time 0ms 5ms 10ms E.g., a task is released to execute every 5 msec, and each invocation has a deadline of 5 msec Separate priority range from nice: Priorities range from 1 (low) to 99 (high) CSE 522S Advanced Operating Systems 7
Real-Time OS Support Goal is to achieve predictable execution: Ideal: Real world: Preempt Migrate Sources of uncertainty (and solutions): Scheduling preemptions (real-time scheduling) Interrupts (can mask interrupts) Migrations (can pin tasks to cores) OS latency & jitter (RT_PREEMPT patch set) CSE 522S Advanced Operating Systems 8
SCHED_RR Round-robin scheduling Among tasks of equal priority: Rotate through all tasks Each task gets a fixed time slice Task 1 Task 2 Task 3 Task 1 Task 2 Task 3 Task 1 Task 2 Task 3 Time Cannot run if higher priority tasks are runnable CSE 522S Advanced Operating Systems 9
SCHED_FIFO First-in, First-out scheduling The first enqued task of highest priority executes to completion A task will only relinquish a processor when it completes, yields, or blocks Task 1 Task 2 Task 3 Time CSE 522S Advanced Operating Systems 10
SCHED_DEADLINE Earliest Deadline First (EDF)scheduling Whichever task has next deadline gets to run Deadline: 5 Exec time: 4 Deadline: 12 Exec time: 3 Deadline: 8 Exec time: 2 Task 1 Task 2 Task 3 Theory exists to analyze such systems Linux implements bandwidth reservation to prevent deadline abuse Task 1 Task 2 Task 3 Time 0 5 8 12 CSE 522S Advanced Operating Systems 11
