Notes - MIECT
Sistemas Operativos E De Tempo-real
Notes - MIECT
Sistemas Operativos E De Tempo-real
  • Sistemas Operativos e de Tempo-real
  • Basic Concepts About Real-Time Systems
    • Preliminaries
    • Definitions
    • Objective of the Study of RTS
    • Requirements of Real-Time Systems
  • Real Time Model
    • Real Time Model
    • Temporal Control
    • Task states and execution
    • Kernel/RTOS Architecture
      • Time Management Functions
    • Examples of RTOS
  • Practical Class 01
    • Real-Time Services in Linux
    • Using the Linux real-time services
  • Scheduling Basics
    • Basic concepts
    • Scheduling Algorithms
      • Basic algorithms
    • Static Cyclic Scheduling
    • Exercise
  • Fixed Priority Scheduling
    • Online scheduling with fixed priorities
    • Schedulability tests based on utilization
      • Deadline Monotonic Scheduling DM
    • Response-time analysis
  • Practical Class 2
    • Xenomai brief introduction
    • API
    • Developing an application
  • Dynamic Priority Scheduling
    • On-line scheduling with dynamic priorities
    • Analysis: CPU utilization bound
    • Analysis: CPU Load Analysis
    • Other deadline assignment criteria
  • Exclusive Access to Shared Resources
    • The priority inversion problem
    • Techniques for allowing exclusive access
    • Priority Inheritance Protocol
    • Priority Ceiling Protocol
    • Stack Resource Policy
    • Notes
  • Aperiodic Servers
    • Joint scheduling of periodic and aperiodic tasks
    • Aperiodic Servers
    • Fixed Priority Servers
    • Dynamic Priority Servers
  • Limited preemption, release jitter and overheads
    • Non-preemptive scheduling
    • Impact of Release Jitter
    • Accounting for overheads
    • Considerations about the WCET
  • Profiling and Code Optimization
    • Code optimization techniques
      • CPU independent optimization techniques
      • Cache impact
      • Optimization techniques dependent on memory architecture
      • Architecture-dependent optimization techniques
    • Profiling
  • Multiprocessor Scheduling, V1.2
    • Introduction
    • Definitions, Assumptions and Scheduling Model
    • Scheduling for Multicore Platforms
    • Task allocation
Powered by GitBook
On this page
  • Assumptions
  • Partitioned scheduling
  • Global scheduling
  • Example
  • Evaluation
  • Global vs Partitioned Scheduling
  • Hybrid approaches
  1. Multiprocessor Scheduling, V1.2

Scheduling for Multicore Platforms

PreviousDefinitions, Assumptions and Scheduling ModelNextTask allocation

Last updated 2 years ago

Assumptions

Identical Multicore Systems (all cores are equal).

WCET (upper bound) is known for any scenario.

Periodic or sporadic tasks.

Main approaches:

  • Partitioned scheduling - Tasks are allocated a priori to a given core - individual queues.

  • Global scheduling - Tasks are allocated to cores at runtime - single queue.

Partitioned scheduling

Each processor has an independent ready queue.

The processor for each task is determined a priori.

Tasks cannot migrate.

The scheduling problem reduces to:

  • Bin-packing problem, for allocating tasks to processors.

    • NP-hard in the strong sense.

    • Several heuristics:FirstFit, NextFit, BestFit, etc.

  • Uniprocessor scheduling problem (already studied and well known).

Global scheduling

The system manages a single queue of ready tasks.

The processor is determined at run time.

During execution, a task can migrate to another processor.

Example

Consider a Global Scheduler with RM policy and the task set below.

Is the system schedulable?

Evaluation

Dhall’s effect: Global RM and Global EDF produce unfeasible schedules for task set utilizations arbitrarily close to 1.

  • m processors and m+1 tasks.

But Partitioned Scheduling allows to schedule such system with just 2 processors!

There are examples of task sets that one of the methods can schedule while the other cannot!

Global vs Partitioned Scheduling

Global
Partitioned

+ Automatic load balancing

+ Supported by automotive industry (e.g., AUTOSAR)

+ Lower avg. response time

+ No migrations

+ Easier re-scheduling

+ Isolation between cores

+ More efficient reclaiming and overload management

+ Mature scheduling framework

+ Lower number of preemptions

+ Low scheduling overhead (no need to access a global ready queue)

- Migration costs

- Cannot exploit unused capacity

- Inter-core synchronization

- Rescheduling not convenient

- Loss of cache affinity

- NP-hard allocation problem

- Weak scheduling framework

Hybrid approaches

Task/job migration can be costly.

  • contex must be moved, impact on cache, etc.

There are other types of partitioning that consider restrictions on task migration.

Job migration

Tasks are allowed to migrate, but only at jobs boundaries.

Semi-partitioned scheduling

Some tasks are statically allocated to processors, others are split into chunks (subtasks) that are allocated to different processors.

Clustered scheduling

A task can only migrate within a predefined subset of processors (cluster).