Understanding Thread Scheduling and Prioritization

Nov 24, 2024

Lecture Notes: Thread Scheduling and Real-time CPU Scheduling

Overview

  • Introduction to the concept of convoy, illustrated by the analogy of being stuck behind a school bus.
  • Discussion of thread scheduling including user-level and kernel-level threads.

Thread Scheduling

Types of Threads

  • User-level Threads: Scheduled by software.
  • Kernel-level Threads: Managed by the Operating System (OS).
  • Lightweight Processors (LWP): Acts as a connection point between user-level and kernel-level threads.

Contention Scopes

  • Process Contention Scope: Prioritization of threads for CPU time, usually set by programmers.
  • System Contention Scope: Prioritization of kernel threads, usually managed by the OS.

Pthread Scheduling

  • Setting up and managing threads with IDs and attributes.
  • Differences in process scope and system scope scheduling.
  • On Linux and Mac, only system scope is adjustable.

Multi-core Processing

Concepts

  • NUMA Systems: Non-uniform memory access systems.
  • Heterogeneous Multiprocessing: Different speeds in cores, common in cell phones.

Scheduling Issues

  • Symmetric Multi-processing: Each core has its own thread queue.
  • Race conditions and blocking in multi-threaded environments.

Chip Multithreading (CMT)

  • Cores handle multiple threads to optimize performance, often 2 threads per core.
  • Logical processors vs. physical cores in systems.

Balancing Thread Loads

Methods

  • Push Migration: Moving threads from overloaded cores to less busy ones.
  • Pull Migration: Underutilized cores request threads from busy ones.

Thread Affinity

  • Soft Affinity: OS tries to keep threads on the same core.
  • Hard Affinity: Threads specify which core to run on, common in gaming.

Real-time CPU Scheduling

Concepts

  • Soft Real-time Systems: Critical tasks get high priority but no guarantee.
  • Hard Real-time Systems: Tasks must be completed by deadlines, crucial for safety.
  • Event Latency: Time from event occurrence to processing.
    • Interrupt Latency: Time before an interrupt is serviced.
    • Dispatch Latency: Time before execution of a response.

Scheduling Strategies

  • Priority-based Scheduling: Preemptive with focus on high-priority tasks.
  • Rate Monotonic Scheduling: Shorter periods get higher priority.
  • Earliest Deadline First Scheduling: Prioritization based on nearest deadlines.
  • Proportional Share Scheduling: Divides processing time among applications.

Operating System Examples

Linux

  • Older Version (Pre-2.5): Quick scheduling with priority-based ranges.
  • CFS (Completely Fair Scheduler): Real-time scheduling with virtual runtime and load balancing.

Windows

  • Priority-based Scheduling: Preemptive with a 32-level priority scheme.
  • User Mode Scheduling (Windows 7+): Allows for application-managed threads for efficiency.

Ensure to review specific code examples provided for POS-X and threading policies for detailed understanding.