Periodic Task Scheduling: Algorithms, Analysis & Optimization

TAKEAWAYS:

• Understand periodic tasks (fixed arrival times, deadlines) and their scheduling constraints (worst-case response time, CPU utilization).
• Compare Rate-Monotonic (RM) and Earliest Deadline First (EDF) algorithms using utilization bounds and response-time analysis.
• Apply response-time analysis to verify schedulability of task sets under RM and EDF.
• Learn harmonic task sets and how they improve schedulability under RM.
• Analyze priority inheritance and deadline inheritance protocols for shared resources.
• Solve worked examples tied to real systems (e.g., NTC traffic signal coordination, bank transaction processing).

1. Introduction to Periodic Tasks

Periodic tasks are repeating computations with fixed time intervals (periods), deadlines, and execution times. They are fundamental in real-time systems where predictability is critical.

Key Definitions

• Period (T): Time between two consecutive arrivals of a task.
• Execution Time (C): Worst-case time to complete one instance.
• Deadline (D): Time by which a task must finish (often $D=T$ for implicit deadlines).
• Utilization (U): Fraction of CPU time a task requires: $U=\frac{C}{T}$.

Example: Traffic Light Controller

timeline
    title Traffic Light Controller (Periodic Task)
    Task A: Traffic Light 1 (T=30s, C=5s) :start1: 0s
    Task B: Traffic Light 2 (T=45s, C=8s) :start2: 5s
    Task C: Emergency Vehicle Detection (T=10s, C=2s) :start3: 10s

• Task A: Controls a traffic light every 30 seconds (period $T_A=30$s), taking 5 seconds to execute ($C_A=5$s).
• Task B: Controls another light every 45 seconds ($T_B=45$s), taking 8 seconds ($C_B=8$s).
• Task C: Monitors emergency vehicles every 10 seconds ($T_C=10$s), taking 2 seconds ($C_C=2$s).

Question: Can these tasks run on a single CPU without missing deadlines? (Answer: Requires schedulability analysis—see Section 3.)

2. Scheduling Algorithms for Periodic Tasks

Two dominant algorithms: Rate-Monotonic (RM) and Earliest Deadline First (EDF).

A. Rate-Monotonic Scheduling (RM)

• Priority Assignment: Higher priority to tasks with shorter periods (rate-monotonic).
• Preemptive: Higher-priority tasks can interrupt lower-priority ones.
• Utilization Bound: For $n$ tasks, the total utilization must satisfy: $$\sum _{i=1}^n{U}_i\le n(2^{1/n}-1)$$
  • For $n=1$: $U\le 1$ (trivial).
  • For $n=2$: $U\le 0.693$.
  • For $n=\infty$: $U\le 0.692$ (Liu & Layland bound).

Example: NTC Traffic Signal Scheduling

classDiagram
    class TrafficSignal {
        +Period T
        +Execution Time C
        +Priority (RM: shorter T = higher priority)
    }
    class Scheduler {
        +Assigns priorities based on T
        +Preempts lower-priority tasks
    }
    TrafficSignal --> Scheduler : "Scheduled by"

• Task Set:
  • Task 1: $T_1=20$s, $C_1=3$s (high priority).
  • Task 2: $T_2=30$s, $C_2=5$s (lower priority).
• Total Utilization: $U_1+U_2=0.15+0.166=0.316\le 0.693$ → Schedulable under RM.

B. Earliest Deadline First (EDF)

• Dynamic Priority: Task with the earliest deadline runs next.
• Utilization Bound: 100% (optimal for periodic tasks).
• Advantage: Can schedule task sets that RM cannot (e.g., $U=0.7$).
• Disadvantage: Higher runtime overhead (deadlines must be checked frequently).

Comparison Table: RM vs. EDF

3. Response-Time Analysis (RTA)

To verify if a task set is schedulable, compute the worst-case response time ($R_i$) for each task.

Response-Time Equation (for RM)

For task $i$: $$R_i=C_i+\sum _{j=1}^{i-1}\lceil \frac{R_i}{T_j}\rceil C_j$$

• Iterative Solution: Solve for $R_i$ until convergence.
• Schedulable if: $R_i\le D_i$ (deadline).

Worked Example: Bank Transaction Processing

flowchart TD
    A["Transaction Queue"] --> B["Scheduler (RM/EDF)"]
    B --> C["CPU Core 1"]
    B --> D["CPU Core 2"]
    C --> E["Database Update"]
    D --> F["Customer Notification"]

• Task Set:
  • Task 1 (High Priority): $T_1=10$ms, $C_1=2$ms (ATM withdrawal).
  • Task 2: $T_2=20$ms, $C_2=5$ms (Fund transfer).
  • Task 3: $T_3=50$ms, $C_3=10$ms (Monthly statement).
• Check Task 1 ($R_1$): $$R_1=C_1+\lceil \frac{R_1}{T_1}\rceil C_1=2\text{ (no interference)}$$ $R_1=2\le D_1=10$ → OK.
• Check Task 2 ($R_2$): $$R_2=C_2+\lceil \frac{R_2}{T_1}\rceil C_1=5+\lceil \frac{R_2}{10}\rceil \times 2$$ Assume $R_2=7$ → $\lceil 0.7\rceil =1$ → $R_2=5+2=7$. $R_2=7\le D_2=20$ → OK.
• Check Task 3 ($R_3$): $$R_3=C_3+\lceil \frac{R_3}{T_1}\rceil C_1+\lceil \frac{R_3}{T_2}\rceil C_2$$ Assume $R_3=15$ → $\lceil 1.5\rceil =2$, $\lceil 0.75\rceil =1$ → $R_3=10+2\times 2+1\times 5=19\le D_3=50$ → OK.

Conclusion: All tasks meet deadlines under RM.

4. Harmonic Task Sets

A task set is harmonic if all periods are integer multiples of the shortest period.

• Example: $T_1=5$ms, $T_2=10$ms, $T_3=20$ms.
• Advantage: RM can achieve 100% utilization for harmonic sets.

Why?

• No two tasks release at the same time → no interference.
• Utilization Bound: $U\le 1$ (optimal).

Real-World Example: YouTube Video Buffering

sequenceDiagram
    participant User as User Request
    participant Server as YouTube Server
    participant Decoder as Video Decoder (Periodic Task)
    User->>Server: Request Video
    Server->>Decoder: Stream Frames (T=33ms, C=5ms)
    Decoder->>User: Render Frame

• Task: Decode video frames every 33ms (30 FPS).
• Harmonic Subtasks: If split into 60 FPS, periods are $T=16.67$ms, $2T=33.33$ms, etc.
• Scheduling: RM ensures smooth playback without jitter.

5. Priority Inheritance and Deadline Inheritance

When tasks share resources (e.g., mutual exclusion locks), priority inversion can occur:

• Low-priority task holds a resource needed by a high-priority task.
• Solution: Priority inheritance or deadline inheritance.

A. Priority Inheritance Protocol (PIP)

• If a low-priority task $L$ holds a resource needed by a high-priority task $H$, $L$ inherits $H$'s priority temporarily.
• Prevents unbounded priority inversion.

Example: Pathao Driver Assignment System

stateDiagram-v2
    [*] --> Idle
    Idle --> DriverAvailable: "New Ride Request"
    DriverAvailable --> AssignTask: "Check Priority"
    AssignTask --> HighPriority: "High-priority ride?"
    HighPriority --> InheritPriority: "Yes (PIP)"
    InheritPriority --> Execute: "Assign Driver"
    Execute --> [*]

• Task 1 (High Priority): $T_1=10$s (urgent ride).
• Task 2 (Low Priority): $T_2=30$s (standard ride), currently holding a lock on the driver database.
• Problem: Task 1 waits indefinitely for Task 2.
• Solution: Task 2 inherits Task 1’s priority while holding the lock.

B. Deadline Inheritance Protocol (DIP)

• Instead of inheriting priority, the deadline of the blocked task is inherited.
• Used in EDF systems.

6. Optimization Techniques

A. Task Transformation

• Decomposition: Split a long task into smaller periodic tasks.
• Example: A 100ms task → 5 tasks of 20ms each (harmonic set).

B. Resource Reservation

• Reserve CPU time for critical tasks (e.g., Time-Triggered Architecture).
• Used in automotive systems (e.g., Tesla’s Autopilot).

C. Dynamic Voltage and Frequency Scaling (DVFS)

• Reduce CPU speed/frequency to meet deadlines while saving power.
• Used in smartphones (e.g., Pathao’s background task scheduling).

In the Real World

1. NTC Traffic Signal Control

   • Idea Used: Periodic task scheduling (RM) to coordinate traffic lights.
   • How? Tasks run every 30–60 seconds with fixed priorities (shorter periods = higher priority). Priority inheritance ensures emergency vehicle signals preempt normal traffic.

2. Khalti Payment Processing

   • Idea Used: EDF scheduling for transaction deadlines.
   • How? High-priority tasks (e.g., fund transfers) get CPU time before low-priority ones (e.g., bill payments). Deadline misses trigger retries.

3. Daraz Order Fulfillment

   • Idea Used: Harmonic task sets for warehouse robots.
   • How? Robots pick items in fixed cycles (e.g., 5s, 10s, 20s). RM ensures no two robots collide while picking.

Exam Tip

1. Memorize Utilization Bounds:

   • RM: $n(2^{1/n}-1)$ (e.g., for $n=3$, $U\le 0.78$).
   • EDF: Always schedulable if $U\le 1$.

2. Response-Time Analysis Steps:

   • Write the equation: $R_i=C_i+\sum \text{interference}$.
   • Solve iteratively until convergence.
   • Compare $R_i$ with $D_i$.

3. Common Pitfalls:

   • Forgetting to sort tasks by priority in RM.
   • Misapplying deadline inheritance (only for EDF).
   • Ignoring shared resources (always check for priority inversion).

4. Worked Example Expectations:

   • Exams often ask to verify schedulability of 2–3 tasks.
   • Draw a Gantt chart to visualize scheduling (even if not required, it helps).

5. Real-World Links:

   • Relate RM to embedded systems (e.g., washing machines).
   • Relate EDF to financial systems (e.g., stock trading deadlines).

Final Note: Master one worked example (e.g., traffic lights or bank transactions) and adapt it to exam questions. Always show calculations for RTA—partial credit is given for correct steps!