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
  1. Limited preemption, release jitter and overheads

Non-preemptive scheduling

PreviousDynamic Priority ServersNextImpact of Release Jitter

Last updated 2 years ago

Non preemptive scheduling consists in executing the jobs until completion, without allowing its suspension for the execution of higher priority jobs.

Main characteristics/ advantages:

  • Very simple to implement, as it is not necessary to save the intermediate job’s state.

  • Stack size much lower (equal to the stack size of the task with higher requirements + interrupt service routines).

  • No need for any synchronization protocol to access shared resources, since tasks execute inherently with mutual exclusion.

Main characteristics/ disadvantages:

  • Penalizes the system schedulability, mainly when there are tasks with long execution times.

  • This penalization may be excessive when, simultaneously, the system has tasks with high activation rates (short periods).

  • The penalization can be seen as a blocking on the access of a shared resource, in the case the CPU.

Sometimes the use of offsets may turn a system schedulable.

However, finding these offset is usually is very complex ...

Computation of the Rwci with fixed priorities:

  • The feasibility analysis must be adapted and becomes more complex.

  • In non-preemptive scheduling the longest response time does not necessarily coincide with the first job after the critical instant.

    • Self-pushing phenomenon: high priority jobs activated during the first instance of Ï„i are pushed ahead to the following jobs of Ï„i, which may experience higher interference.

Therefore the response time analysis must be performed until the processor finishes executing all tasks with priority greater than or equal to Pi : Level-i Active Period (Li)

Li is the smallest value for which Li(s) = Li(s − 1)

For a generic task Ï„i we must compute the response time for all jobs Ï„i, k, where k=1, ...Ki and

The starting times of the relevant jobs can be computed as follows:

Since once started a job cannot be preempted, the finishing time is

And finally the worst-case response time is

Exercise

Given the task set below, compute the worst-case response time, without preemption, of each tasks.

Assume RM priority assignment.

Is the task set schedulable without preemption? And with preemption?