Outline
▪ Functionalities of Real Time Operating System
▪ Classification of Task Scheduling Strategies in Realtime Kernel
▪ Examples of Task Scheduling Algorithms for Real Time Systems
▪ Round-Robin Approach
▪ Cyclic Code Scheduling (Clock-Driven Scheduling)
▪ Priority-Driven Scheduling Algorithms
▪ Scheduling on Multiprocessor System
▪ System Services for Inter-Task Communications and Synchronization
▪ Commercial RTOS
Lebanese University - Fall 2025/2026 28
Fixed-Priority Scheduling:
Rate-Monotonic Algorithm (RMA) (1/2)
▪ Fixed-Priority Scheduling:
▪ the priority of each periodic task is fixed relative to other tasks
▪ Priorities of ready tasks determine the execution order of tasks
▪ A critical instant of a task is defined to be an instant at which a
request for that task will have the largest response time.
▪ Proved to occur whenever the task is requested
simultaneously with requests for all higher-priority tasks.
▪ RMA has been proved to be the optimal fixed-priority real time task
scheduling algorithm
▪ RMA assigns priority of tasks according to their frequency of
occurrence:
▪ The lower the occurrence rate (the higher the period) the
lower is the priority
** priority is inversely proportional to the period
Lebanese University - Fall 2025/2026 29
Fixed-Priority Scheduling:
Rate-Monotonic Algorithm (RMA) (2/3)
Schedulability Tests: to check whether a
set of periodic real-time tasks can feasibly
be scheduled under RMA
𝑒𝑖
▪ CPU utilization: 𝑈 = σ𝑛𝑖=1
𝑝𝑖
▪ Necessary schedulability test for RMA:
𝑈≤1
▪ Sufficient schedulability test for RMA:
1
𝑈≤𝑛 −12𝑛
**under the assumption the the relative
deadline 𝑑𝑖 is equal to the task period 𝑝𝑖 University - Fall 2025/2026
Lebanese 30
Fixed-Priority Scheduling:
Rate-Monotonic Algorithm (RMA) (3/3)
Exercise 2
▪ Test if the following tasks can be schedulable under RMA
𝑇1 = (𝑒1 = 4, 𝑝1 = 8), 𝑇2 = (𝑒2 = 3, 𝑝2 = 16), and 𝑇3 = (𝑒3 = 1, 𝑝3 = 4)
▪ Consider that the first occurrence of these tasks happens to be
simultaneous. Show their scheduling over time
Lebanese University - Fall 2025/2026 31
Dynamic Priority Scheduling:
Earliest Deadline First Algorithm (EDFA) (1/2)
▪ In dynamic-priority schemes, the priority of a task with respect to that of other tasks
changes as tasks are released and completed.
▪ One of the most well-known dynamic algorithms, the earliest deadline first algorithm,
deals with deadlines rather than execution times.
▪ At any point of time, the ready task with the earliest deadline has the highest priority
▪ Sufficient and necessary schedulability test:
𝑛
𝑒𝑖
𝑈= ≤1
𝑝𝑖
𝑖=1
**under the assumption the the relative deadline 𝑑𝑖 is equal to the task period 𝑝𝑖
Lebanese University - Fall 2025/2026 32
Dynamic Priority Scheduling:
Earliest Deadline First Algorithm (EDFA) (2/2)
Exercise 3
▪ Test if the following tasks can be schedulable under EDFA
𝑇1 = (𝑒1 = 2, 𝑝1 = 5) and 𝑇2 = 𝑒2 = 4, 𝑝2 = 7
▪ Consider that the first occurrence of these tasks happens to be
simultaneous. Show their scheduling over time
Lebanese University - Fall 2025/2026 33
Priority-Driven Scheduling of Aperiodic Tasks
▪ Approach 1: schedule aperiodic
tasks at the lowest priority level
▪ In the background
▪ Extremely poor performance for
aperiodic tasks;
▪ Approach 2: Polling Server
Lebanese University - Fall 2025/2026 34
Priority-Driven Scheduling of Sporadic Tasks
▪ Polling Server with a period equal to the minimum interarrival time
between any two consecutive instances of the task.
▪ An acceptance test should be performed before a sporadic task is
scheduled for execution
Lebanese University - Fall 2025/2026 35