task assignment and scheduling in real time systems ppt

• Engineering Mathematics
• Discrete Mathematics
• Operating System
• Computer Networks
• Digital Logic and Design
• C Programming
• Data Structures
• Theory of Computation
• Compiler Design
• Computer Org and Architecture

Scheduling in Real Time Systems

Real-time systems are systems that carry real-time tasks. These tasks need to be performed immediately with a certain degree of urgency. In particular, these tasks are related to control of certain events (or) reacting to them. Real-time tasks can be classified as hard real-time tasks and soft real-time tasks. 

A hard real-time task must be performed at a specified time which could otherwise lead to huge losses. In soft real-time tasks, a specified deadline can be missed. This is because the task can be rescheduled (or) can be completed after the specified time, 

In real-time systems, the scheduler is considered as the most important component which is typically a short-term task scheduler. The main focus of this scheduler is to reduce the response time associated with each of the associated processes instead of handling the deadline. 

If a preemptive scheduler is used, the real-time task needs to wait until its corresponding tasks time slice completes. In the case of a non-preemptive scheduler, even if the highest priority is allocated to the task, it needs to wait until the completion of the current task. This task can be slow (or) of the lower priority and can lead to a longer wait. 

A better approach is designed by combining both preemptive and non-preemptive scheduling. This can be done by introducing time-based interrupts in priority based systems which means the currently running process is interrupted on a time-based interval and if a higher priority process is present in a ready queue, it is executed by preempting the current process. 

Based on schedulability, implementation (static or dynamic), and the result (self or dependent) of analysis, the scheduling algorithm are classified as follows. 

• Static table-driven approaches:   These algorithms usually perform a static analysis associated with scheduling and capture the schedules that are advantageous. This helps in providing a schedule that can point out a task with which the execution must be started at run time.   
• Static priority-driven preemptive approaches:   Similar to the first approach, these type of algorithms also uses static analysis of scheduling. The difference is that instead of selecting a particular schedule, it provides a useful way of assigning priorities among various tasks in preemptive scheduling.   
• Dynamic planning-based approaches:   Here, the feasible schedules are identified dynamically (at run time). It carries a certain fixed time interval and a process is executed if and only if satisfies the time constraint.   
• Dynamic best effort approaches:   These types of approaches consider deadlines instead of feasible schedules. Therefore the task is aborted if its deadline is reached. This approach is used widely is most of the real-time systems.   

Advantages of Scheduling in Real-Time Systems:

• Meeting Timing Constraints: Scheduling ensures that real-time tasks are executed within their specified timing constraints. It guarantees that critical tasks are completed on time, preventing potential system failures or losses.
• Resource Optimization: Scheduling algorithms allocate system resources effectively, ensuring efficient utilization of processor time, memory, and other resources. This helps maximize system throughput and performance.
• Priority-Based Execution: Scheduling allows for priority-based execution, where higher-priority tasks are given precedence over lower-priority tasks. This ensures that time-critical tasks are promptly executed, leading to improved system responsiveness and reliability.
• Predictability and Determinism: Real-time scheduling provides predictability and determinism in task execution. It enables developers to analyze and guarantee the worst-case execution time and response time of tasks, ensuring that critical deadlines are met.
• Control Over Task Execution: Scheduling algorithms allow developers to have fine-grained control over how tasks are executed, such as specifying task priorities, deadlines, and inter-task dependencies. This control facilitates the design and implementation of complex real-time systems.

Disadvantages of Scheduling in Real-Time Systems:

• Increased Complexity: Real-time scheduling introduces additional complexity to system design and implementation. Developers need to carefully analyze task requirements, define priorities, and select suitable scheduling algorithms. This complexity can lead to increased development time and effort.
• Overhead: Scheduling introduces some overhead in terms of context switching, task prioritization, and scheduling decisions. This overhead can impact system performance, especially in cases where frequent context switches or complex scheduling algorithms are employed.
• Limited Resources: Real-time systems often operate under resource-constrained environments. Scheduling tasks within these limitations can be challenging, as the available resources may not be sufficient to meet all timing constraints or execute all tasks simultaneously.
• Verification and Validation: Validating the correctness of real-time schedules and ensuring that all tasks meet their deadlines require rigorous testing and verification techniques. Verifying timing constraints and guaranteeing the absence of timing errors can be a complex and time-consuming process.
• Scalability: Scheduling algorithms that work well for smaller systems may not scale effectively to larger, more complex real-time systems. As the number of tasks and system complexity increases, scheduling decisions become more challenging and may require more advanced algorithms or approaches.  

Please Login to comment...

Similar reads.

• Operating Systems
• Write From Home
• 105 Funny Things to Do to Make Someone Laugh
• Best PS5 SSDs in 2024: Top Picks for Expanding Your Storage
• Best Nintendo Switch Controllers in 2024
• Xbox Game Pass Ultimate: Features, Benefits, and Pricing in 2024
• #geekstreak2024 – 21 Days POTD Challenge Powered By Deutsche Bank

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

• My presentations

Auth with social network:

Download presentation

We think you have liked this presentation. If you wish to download it, please recommend it to your friends in any social system. Share buttons are a little bit lower. Thank you!

Presentation is loading. Please wait.

REAL-TIME OPERATING SYSTEMS

Published by Francine Stewart Modified over 6 years ago

Similar presentations

Presentation on theme: "REAL-TIME OPERATING SYSTEMS"— Presentation transcript:

Real Time Scheduling.

Chapter 7 - Resource Access Protocols (Critical Sections) Protocols: No Preemptions During Critical Sections Once a job enters a critical section, it cannot.

Introduction to Embedded Systems Resource Management - III Lecture 19.

CSC 360- Instructor: K. Wu Overview of Operating Systems.

Copyright © 2000, Daniel W. Lewis. All Rights Reserved. CHAPTER 8 SCHEDULING.

A Sample RTOS Presentation 4 Group A4: Sean Hudson, Manasi Kapadia Syeda Taib.

Tasks Periodic The period is the amount of time between each iteration of a regularly repeated task Time driven The task is automatically activated by.

Real-Time Kernels and Operating Systems Basic Issue - Purchase commercial “off-the- shelf” system or custom build one Basic Functions –Task scheduling.

Real-Time Operating System Chapter – 8 Embedded System: An integrated approach.

Chapter 19: Real-Time Systems Silberschatz, Galvin and Gagne ©2005 AE4B33OSS Chapter 19: Real-Time Systems System Characteristics Features of Real-Time.

Real-Time Scheduling CS4730 Fall 2010 Dr. José M. Garrido Department of Computer Science and Information Systems Kennesaw State University.

Real-Time Systems Mark Stanovich. Introduction System with timing constraints (e.g., deadlines) What makes a real-time system different? – Meeting timing.

The Linux Operating System C. Blane Adcock Bryan Knehr Kevin Estep Jason Niesz.

1 Review of Process Mechanisms. 2 Scheduling: Policy and Mechanism Scheduling policy answers the question: Which process/thread, among all those ready.

ECGR-6185 µC/OS II Nayana Rao University of North Carolina at Charlotte.

1 VxWorks 5.4 Group A3: Wafa’ Jaffal Kathryn Bean.

Introduction to Embedded Systems Rabie A. Ramadan 5.

19.1 Silberschatz, Galvin and Gagne ©2009 Operating System Concepts with Java – 8 th Edition Chapter 19: Real-Time Systems.

Chapter 19: Real-Time Systems Silberschatz, Galvin and Gagne ©2005 Operating System Concepts Chapter 19: Real-Time Systems System Characteristics.

Sandtids systemer 2.modul el. Henriks 1. forsøg m. Power Point.

About project

© 2024 SlidePlayer.com Inc. All rights reserved.

Chapter 5 Real-Time Operating Systems

Nov 18, 2014

500 likes | 842 Views

Chapter 5 Real-Time Operating Systems. Objectives Multitasking scheduling Inter-task communication RTX51-Tiny RTOS programming Benefits of using RTOS. 5.1 Overview. The RTOS provides an abstraction layer between the hardware and application software.

Share Presentation

• task scheduling
• increment counter
• cooperative task scheduling
• counter1 increment counter 1

Presentation Transcript

Chapter 5Real-Time Operating Systems Objectives • Multitasking scheduling • Inter-task communication • RTX51-Tiny RTOS programming • Benefits of using RTOS

5.1 Overview • The RTOS provides an abstraction layer between the hardware and application software. • They are often called akernel or executiveprocess, not a full-blown Operating System.

Tasks • Application software is split up into multitasking blocks called ‘Tasks’. • Tasks are generic computational blocks with • Timing constraints • Synchronization and communication relationships with other tasks • Generally each device is represented by its own task.

Contd. • Tasks can be in one of four states • SLEEPING • READY • RUNNING • BLOCKED

Contd. Ways to move between tasks: • SLEEPING -> READY through an RTOS system function called from a different task. • READY -> RUNNING from being selected for execution by the RTOS. There can only be one RUNNING task at a time. • RUNNING -> BLOCKED when the task is told to wait for an event to occur. • BLOCKED -> RUNNING After the event, a task has been waiting for occurs and has higher priority than current RUNNING task. 5. RUNNING -> SLEEPING once task has finished execution.

Task scheduling • RTOS decides which task to run using a scheduler, based on a machine clock cycle. • RTOS system clock ‘machine cycles’ based on hardware timer overflow, generally Timer 0. • At each machine clock cycle: • Processor executes RTOS program • RTOS updates tables that track task state, interval count, timeout count, etc. • RTOS decides which task should get to execute

5.2 RTX51-Tiny • RTX51 is a commercial RTOS from Keil, available in Full or Tiny version. • RTX51-Tiny comes with the PK51 Professional Developer’s Kit. • RTX51-Tiny features: • Only 900 bytes of code space required • Requires one hardware timer, Timer 0 • Supports round-robin and cooperative task scheduling • Supports inter-task signaling

Contd. • RTX51-Full supports extra features: • Preemptive task scheduling • Task priorities • Task interrupts • Messaging routines • Semaphores • Memory allocation routines

Task declaration #include <rtx51tny.h> int counter1; void task0 (void) _task_ 0 { // RTX51 begins task 0 counter1 = 0; // initialize counter os_create_task (1); // make task 1 ready os_delete_task (0); // stop task 0 (init is // completed). } void task1 (void) _task_ 1 { while (1) { // infinite loop counter1++; // increment counter 1 } }

Contd. • Task declaration is similar to C function declaration with a ‘_task_’ attribute. • Each task must be assigned a number from 0-255 in Full or 0-15 in Tiny. • Tasks do not return or take any parameters except void. • RTX51-Tiny always starts execution at task number 0. • RTX51-Full must start the RTOS from main()

5.3 Task Scheduling • RTX51 supports preemptive, round-robin, and cooperative task scheduling algorithm. • RTX51 scheduler chooses the task to run by: • The highest priority of all tasks that are READY • The task that has been waiting for the longest time if all tasks have the same priority • RTOS only switches tasks if the first rule is violated, except in round-robin scheduling

5.3.1 Round-Robin Multitasking • Default scheduling method for RTX51-Tiny • Every task is run in turn for an equal length of time called the time-slice • Time-slice is defined during compile, based on number of machine cycles of the system clock

Round-Robin example #include <rtx51tny.h> int counter0; int counter1; int counter2; void job0 (void) _task_ 0 { // RTX51 begins in task0 counter0 = 0; // initialize counters counter1 = 0; counter2 = 0; os_create_task (1); // start task 1 os_create_task(2); // start task 2 while (1) { // infinite loop counter0++; // increment counter 0 } }

Contd. void job1 (void) _task_ 1 { while (1) { // infinite loop counter1++; // increment counter1 } } void job2 (void) _task_ 2 { while (1) { // infinite loop counter2++; // increment counter2 } }

Right after RTOS initialization All 3 tasks are created and READY to run

Contd. • When there is only one task, the RTOS always chooses job0 to run after its time-slice. • When all three tasks are READY to run, job1 runs after job0, and job2 runs after job1. • The time-slice is defined in ‘Conf_tny.A51’. ; Define Hardware-Timer machine cycle time in 8051 machine cycles INT_CLOCK EQU 10000 ;default is 10000 cycles ; ; Define Round-Robin Timeout in Hardware-Timer machine cycles. ; Default is 5 Hardware-Timer machine cycles. ; 0 disables Round-Robin Task Switching TIMESHARING EQU 5

5.3.2 Cooperative Multitasking • Configure RTX51 to schedule in cooperative mode by setting the TIMESHARING variable in ‘Conf_tny.A51’ to 0. TIMESHARING EQU 0 • Tasks switches are only performed when the running task voluntarily gives up control of the processor.

Code example #include <rtx51tny.h> int counter0; int counter1; void job0 (void) _task_ 0 { // RTX51 begins in task 0 os_create (1); // make task 1 READY while (1) { // infinite loop // increment counter if (++counter0 == 0) { // signal task 1 os_send_signal (1); // wait for signal; releases CPU control os_wait (K_SIG, 0, 0); }

Contd. os_wait (K_TMO, 1, 0); // wait for 1 machine cycle, give up CPU } } void job1 (void) _task_ 1 { while (1) { // infinite loop os_wait (K_SIG, 0, 0); // wait for signal // give up CPU // increment counter 1 counter1++; os_send_signal (0); // signal task 0 } }

Contd. • Task 0 gives up control of processor at ‘os_wait’, where it waits for an event to occur. • Before doing so, task 0 signals task 1 making it READY to execute. • Tasks have to manually control execution order using communication methods like signals.

5.3.3 Priority-Driven Preemptive Multitasking • Requires task priorities that are not available in RTX51-Tiny. • Tasks can be assigned a priority from 0-3, with 0 being the lowest priority. 0 is also the default priority for RTX51-Tiny tasks. • Declare task priority by adding a ‘_priority_’ parameter. void job1 (void) _task_ 1 _priority_ 1 {

Contd. • Preemption is necessary sometimes to meet task deadlines. • Preemptive scheduler can switch tasks before the time-slice for the RUNNING task runs out.

Preemption example #include <rtx51tny.h> int counter0; int counter1; void job0 (void) _task_ 0 _priority_ 0 {// RTX51 starts off in task 0 os_create (1); // start task 1 while (1) { // infinite loop // increment counter 0 if (++counter0 == 0) // signal task 1 os_send_signal (1);

Contd. os_wait (K_TMO, 1, 0); // wait for 1 machine cycle } } void job1 (void) _task_ 1 _priority_ 1 { while (1) { // infinite loop os_wait (K_SIG, 0, 0); // wait for signal // increment counter 1 counter1++; } }

(a) While task1 is blocked (b) When task1 preempts task0 (c) While task1 is active (d) When task1 waits for signal

5.4 RTOS Events • Events can be used by tasks to communicate between each other or to help coordinate execution flow. • Four common RTOS events: • Signals • Messages • Semaphores • Interrupts

5.4.1 Signal Event Based Communication • Signaling is the fastest method of communication. • No actual information is exchanged, a signal is simply a single-bit flag. • It is important for coordinating execution flow amongst tasks. • Only one signal can be saved per task, and any extra signals are ignored.

Contd. void task1 (void) _task_ 1 { ... os_send_signal (2); // signal task 2 os_clear_signal (1); // clear task 1 flag os_wait (K_SIG, 0, 0); // wait for signal ... } • Tasks can send and clear signal for any other task, including itself. • Tasks waiting for signal are BLOCKED. The RTOS unblocks that task once the event is received.

5.4.2 Message Event Based Communication • Messaging is only available in RTX51-Full. • A message is a set of data that gets transferred through message queues or mailboxes. • Messages in RTX51 are 16-bit data values or a pointer to data buffer. • RTX51 has eight mailboxes that are not tied to any single task, numbered 0-7.

Contd. • Tasks which send messages are BLOCKED until the message can be sent or timeout occurs. int message; ... // send data in variable ‘message’ to mailbox 2; // timeout after 10 machine cycles os_send_message (2, message, 10); • Tasks can wait for messaging event and store the message to variable. // wait for message in mailbox 3 and store // in &message; or timeout in 10 machine cycles os_wait (K_MBX + K_TMO + 3, 10, &message);

5.4.3 Semaphores • Semaphores are only available for RTX51-Full. • Semaphores help prevent resource sharing conflicts between tasks. • RTX51 has eight binary semaphores, numbered 8-15. // wait for token from semaphore 14 os_wait (K_MBX + 14, 0, 0); // protected task functions ... // finished with semaphore, return token os_send_token (14);

5.4.4 Task Interrupts • RTX51-Full supports attaching hardware interrupt vectors to tasks. • Each interrupt source can only be assigned to one task. • Multiple interrupts can be assigned to a single task. • Attaching an interrupt does not automatically set the corresponding interrupt enable flag. In fact, the relevant flags are only enabled when tasks begin to wait for an interrupt event.

Contd. void task1 (void) _task_ 1 { // attach interrupt 14 (Timer 3 overflow) os_attach_interrupt (14); while (1) { // wait for interrupt os_wait (K_INT, 0, 0); ... } }

5.5 When to use RTOS • Large projects benefit from using an RTOS • Standardized system functions (task switching, task communication, etc.) makes coding easier • Tasks makes large systems more modular and easier to debug • Generally when a system has a dozen or more tasks that all have timing constraints

Contd. • Ultra-compact systems may be better off without using an RTOS • Small systems are easier to code from scratch and can incorporate processor optimizations, making the system more efficient than one using RTOS • A full-featured RTOS may not fit within the size limits of an ultra-compact system.

Summary • RTOS standardizes system functions and makes coding real-time systems easier. • Three predominant scheduling methods are: preemptive, round-robin, and cooperative • Intertask communication can be done through signals or messages. • Large systems benefit from RTOS, while compact systems can be more efficient if it is custom-written.

• More by User

Real Time Operating Systems

Real Time Operating Systems. Alexandru Andrei Embedded Systems Lab. Computer and Information Science Dept., Linköping University [email protected]. QNX (RealTime)Solaris, (RealTime) NT RealTime Java, RealTime Linux. The Question - RealTime Nachos. ?. Why not RealTime Nachos ?

693 views • 26 slides

Real-Time Operating Systems

Real-Time Operating Systems. Read Chapter 6 ( David E. Simon, An Embedded Software Primer ) Read Chapter 1/ Chapter 2 (Labrosse). What, Why, How?. What does real time mean? What is an OS? Why would I need an OS? Why would I need a real time OS? How do we use an OS on embedded systems?.

1.91k views • 59 slides

Real Time Operating Systems. Asynchronous Events Course originally developed by Maj Ron Smith. Outline. Aperiodic versus Sporadic Tasks Approaches to Scheduling Asynchronous Tasks Background Scheduling Interrupt Driven Slack Stealing Polling Bandwidth Servers Deferrable Servers

435 views • 19 slides

Alexandru Andrei ESLAB/IDA/LIU. The Question - RealTime Nachos. QNX(RealTime)Solaris, (RealTime) NT RealTime Java, RealTime Linux. ?. Why not RealTime Nachos ?Why not a RT Linux?. Alexandru Andrei ESLAB/IDA/LIU. App Specific RTOS ?. Build a RTOS from scratch (QNX)Better designUse an existing

600 views • 36 slides

EE551 Real-Time Operating Systems

EE551 Real-Time Operating Systems. Pointers and Pointers to Functions Course originally developed by Maj Ron Smith. Addresses. We know that we use variables to identify our data within our programs

338 views • 21 slides

Operating Systems Real-Time Operating Systems

Operating Systems Real-Time Operating Systems . Chalermek Intanagonwiwat. Slides courtesy of Subhashis Banerjee. Real-Time Systems. Result in severe consequences if logical and timing correctness are not met Two types exist Soft real-time Tasks are performed as fast as possible

1.48k views • 80 slides

Real Time Operating Systems. Fateha Khanam Bappee ID: 201104674 Dept. of Mathematics, Statistics &amp; Computer Science St. Francis Xavier University Antigonish , NS June 11, 2012. Presentation Outline. Introduction Time Services and Scheduling Mechanisms

1.12k views • 74 slides

CSED191 | 컴퓨터공학소개 | November 2006. Real-Time Operating Systems. 서광열 , 류준호 , 오병찬. What is a Real-Time OS?. A RTOS(Real-Time Operating System) An Operating System with the necessary features to support a Real-Time System What is a Real-Time System?

621 views • 27 slides

Real Time Operating Systems. Group A5 Amit Sharma Ali Abbas Dhaval Sanghvi. Strategy for today’s presentation. Short (10 minutes) Outline What is a RTOS Types of RTOS RTOS general structure VxWorks in particular. Operating System Services. Operating System Hierarchy. RTOS Definition.

558 views • 26 slides

Real Time Operating Systems. It’s not Rocket Science!. Schedulability It’s Not Rocket Science!. Maj Smith’s experience - the Electronic Support Trainer (EST) Case. 70+ periodic (and asynchronous) tasks Scheduled according to RM no “special” deadlines assigned

208 views • 9 slides

EE551 Real-Time Operating Systems. Modeling IPC and Constraints Course originally developed by Maj Ron Smith. So far…. We have covered RMA Priority based on period Utilisation bound What are the limitations of RMA? We have covered DMPO

292 views • 18 slides

Operating Systems Real-Time Operating Systems. Chalermek Intanagonwiwat. Slides courtesy of Subhashis Banerjee. Real-Time Systems. Result in severe consequences if logical and timing correctness are not met Two types exist Soft real-time Tasks are performed as fast as possible

2.1k views • 80 slides

Real-Time Operating Systems. Suzanne Rivoire November 20, 2002. http://www.stanford.edu/~skrufi/rtospres.ppt. Motivating Example. void main() { do forever{ check keypad; measure temperature; control oven power; decrement timer; update display;

434 views • 22 slides

EE551 Real-Time Operating Systems. Processes, Threads and Tasks Course originally developed by Maj Ron Smith. Processes. The process is the most central concept in an operating system A process is an abstraction of a running program

221 views • 13 slides

Real Time Operating Systems. Mutual Exclusion, Synchronization &amp; Intertask Communication Course originally developed by Maj Ron Smith. Outline. Mutual Exclusion, Synchronization &amp; Intertask Communications Semaphores Message Mailboxes &amp; Queues Event Flags Task Dependency Issues

434 views • 24 slides

Real Time Operating Systems. Introduction to Real-Time Operating Systems (Part II) Course originally developed by Maj Ron Smith. Outline. Multitasking tasks, kernels, context switching Scheduling types, priorities, interrupts, the “tick” Resource Sharing (Mutual Exclusion)

568 views • 34 slides

Real-Time Operating Systems. Real-Time Kernels Theoretical Foundations of RTOS Intertask Communication &amp; Synchronization Memory Management Case Study. Real-Time Kernels. A process is an abstraction of a running program and is the logical unit of work scheduled by OS

735 views • 45 slides

Real Time Operating Systems. Group A2 Roland Hollis Rachit Gupta EJ Chambers. Guideline. Overview of Real Time Operating Systems Hard vs Soft POSIX Discussion about RTLinux How Real Time is it? In Depth about Real Time Operating Systems. What is a Real Time OS?.

469 views • 18 slides

Real Time Operating Systems. Introduction to Real-Time Systems Course originally developed by Maj Ron Smith. Outline. Definitions Applications of real-time computer systems Lifecycles An Example. Definitions. Real-Time System:

366 views • 18 slides

Real-Time Operating Systems. Raquel S. Whittlesey-Harris. Contents. What is a real-time OS? OS Structures OS Basics RTOS Basics Basic Facilities Interrupts Memory Development Methodologies Summary References. What is a Real-time OS?. A RTOS (Real-Time Operating System)

791 views • 53 slides

316 views • 27 slides

REAL-TIME OPERATING SYSTEMS

REAL-TIME OPERATING SYSTEMS. PRESENTED BY KIRAN K. CONTENTS. Introduction General Purpose Operating System Non-Real-Time systems RTOS Types of RTOS Basic Functions of RTOS kernel RTOS Categories RT Linux: an example Conclusion. General Purpose Operating System.

825 views • 28 slides

• Computer Science and Engineering
• NOC:Real-Time Systems (Video) 
• Co-ordinated by : IIT Kharagpur
• Available from : 2021-05-07
• Intro Video
• Lecture 01 Introduction
• Lecture 02 Introduction
• Lecture 03 Characteristics of a real-time embedded system
• Lecture 04 Characteristics of a real-time embedded system
• Lecture 05 Types of real-time tasks
• Lecture 06 Events in a Real-Time System
• Lecture 07 Types of time constraints
• Lecture 08 Basics of Real-Time Task scheduling
• Lecture 09 Clock-driven schedulers
• Lecture 10 Basics of Cyclic schedulers
• Lecture 11 Cyclic Scheduler
• Lecture 12 Frame size constraints
• Lecture 13 Frame size selection: Examples
• Lecture 14 Event-driven scheduling
• Lecture 15 EDF scheduler
• Lecture 16 : Variants of EDF and Rate Monotonic Scheduling
• Lecture 17 : Rate Monotonic Schedulability Analysis
• Lecture 18 : Rate Monotonic Schedulability Analysis
• Lecture 19 : Rate Monotonic Scheduling: Miscellaneous issues
• Lecture 20 : RMS Generalizations
• Lecture 21 : RMS Generalizations
• Lecture 22 : Handling aperiodic and sporadic tasks in rate monotonic scheduling
• Lecture 23 : Handling aperiodic and sporadic tasks in rate monotonic scheduling
• Lecture 24 : Coping up with Insufficient number of priorities
• Lecture 25 : Handling task jitter and precedence ordering
• Lecture 26: Resource Sharing Among Real-Time Tasks
• Lecture 27: Basic priority inheritance protocol (PIP)
• Lecture 28: Highest Locker Protocol (HLP)
• Lecture 29: Priority Ceiling Protocol (PCP)
• Lecture 30: Working of Priority Ceiling Protocol
• Lecture 31: Analysis of Priority Ceiling Protocol
• Lecture 32: Introduction to Multiprocessor and Distributed Systems
• Lecture 33 : Static Allocation of Tasks
• Lecture 34: Dynamic Allocation of Tasks
• Lecture 35: Centralized Clock Synchronization in Distributed RT Systems
• Lecture 36 : Distributed Clock Synchronization in R-T Systems
• Lecture 37 : A Few Basics in Real-Time Operating Systems
• Lecture 38 : Time Services
• Lecture 39 : Unix as a Real-Time Operating System
• Lecture 40 : Unix as a Real-Time Operating System cont …
• Lecture 41 : Windows as RTOS
• Lecture 42 : POSIX
• Lecture 43 : Unix-Based Real-Time Operating Systems
• Lecture 44 : A survey of some contemporary Real-Time Operating Systems
• Lecture 45 : A survey of some contemporary Real-Time Operating Systems cont …
• Lecture 46: Benchmarking Real-Time Systems
• Lecture 47 : Introduction to Real-Time Communication
• Lecture 48 : Basics of Real-Time Communication
• Lecture 49 : Basics of Networking
• Lecture 50 : Basics of Internet
• Lecture 51 : Real-Time Communication in a LAN
• Lecture 52 : Bounded Access Protocols for LANs
• Lecture 53 : Performance Comparison & QoS Framework
• Lecture 54 : Routing & Resource Reservation
• Lecture 55 : Rate Control
• Lecture 56 : QoS Models & Soft Real-Time Communication in a LAN
• Lecture 57 : Review of Basic Database Concepts
• Lecture 58 : Applications and Issues of Real-Time Database
• Lecture 59 : Characteristics of Temporal Data
• Lecture 60 : Locking-Based Concurrency Control In Real-Time Databases
• Lecture 61 : Concurrency Control In Real-Time Databases and Commercial RT Databases
• Live Session 09-08-2021
• Live Session 17-09-2021
• Watch on YouTube
• Assignments
• Download Videos
• Transcripts

• Preferences

Lecture 7 Real Time Task Scheduling - PowerPoint PPT Presentation

Lecture 7 Real Time Task Scheduling

T=the task execution during ... assigned a priority to the new arrival then apply earliest ... complexity of algorithm is o(n^2). upper bound of process ... – powerpoint ppt presentation.

• Forrest Brewer
• ANSI defines real time as
• A Real time process is a process which delivers the results of processing in a given time span
• A data may require processing at a priori known point in time, or it may be demanded without any priori knowledge
• Correctness of computation
• Deadlines (latest acceptable time)
• Soft deadline
• Diminished functionality as deadlines are missed
• System does not fail
• Hard deadline
• System fails (X-29 wings fall off)
• Processing guarantees for time-critical applications
• Predictably fast response to time-critical events accurate timing information
• Jitter issues
• High degree of schedulability
• High degree of resource utilization below which the processing guarantee is a question
• Stability under transient overload
• Under system overload, critical jobs processing of must be ensured
• Priority Scheme, process preemption
• Sharing of Resources
• Management of Arbitration
• Low Overhead
• Determinism concerned with how long an operating system delays before acknowledging an event
• Responsiveness concerned with how long after acknowledgment, it takes an operating system to finish the event (interrupt) service
• Determinism and responsiveness together make up the response time to external events which are crucial for real-time systems
• User control allow the user (dynamic?) fine-grained control over task priority
• Reliability a transient failure may cause financial loss or major equipment damage or even loss of life.
• Fail-soft operation during overload, continued operation at a reduced level of service
• Tasks are the schedulable unit of the system.
• A task is characterized by timing constraints and resource requirements.
• Periodic task (T)
• processing time
• Task schedulable entity
• Processing of separate tasks are assumed mutually independent
• Timing constraints of a periodic task ti is specified by (s, e, D, p)
• si-(scheduled) Starting Time of Task i
• ei-Processing time of i
• fi-Finish time of i
• Di-Deadline of i
• pi-Period of i
• ri-Rate of i (1/pi)
• Tasks can be
• Nonpreemptive
• Guarantee ratio
• Processing time used by guaranteed tasks versus total processing time
• Utilization
• Assumptions
• Periodic tasks without precedence relations
• Aimed at vertical system decomposition
• No OS overhead
• time added to every task invocation
• this is a problem for preemptive task models
• Time Constraints (non-periodic)
• C t1(s1, e1, D1), t3(s3, e3, D3), t2(s2, e2, D2),
• Ct1(0,8,13), t2(3,5,10), t3(4,7,20)
• A(0,3,t1),(3,8,t2),(8,13,t1),(13,7,t3) is a feasible schedule
• for t1, (3-0) (13-8) 3 5 8
• Ct1(1,8,12), t2(3,5,10), t3(4,7,14)
• No feasible schedule
• Static table-driven
• Suitable for periodic tasks/earliest-deadline first scheduling
• Requires Static analysis of feasible schedule
• Static priority-driven preemptive ? rate monotonic algorithm
• Static analysis to determine priority
• Traditional priority-driven scheduler is used
• Dynamic planning-based (evaluate priorities on the fly)
• Create a schedule containing the previously scheduled tasks and the new arrival ? if all tasks meets their constraints, the new one is accepted
• Dynamic best effort
• No feasibility analysis is performed
• Assigned a priority to the new arrival ? then apply earliest deadline first
• System tries to meet all deadlines and aborts any started process whose deadline is missed
• Suppose the tasks tsk 1tsk 3 have the following properties
• The tasks get assigned priorities
• Once assigned, these priorities do not change
• The tasks are scheduled according to their priorities, i.e. a ready task with highest priority is executed until a higher priority task becomes ready. Such higher priority task then pre-empts the lower priority task.
• Time Line Scheduling (Off-line scheduling strategy) Divide the time line into time slices for scheduling tasks, e.g. use the Greatest Common Divisor of the Task Periods as the time slice
• Suppose we assign the priorities depending on their (worst) computation time, I.e. the longer the computation time the higher priority
• What will be then the execution?
• Suppose we assign the priorities depending on their (worst) computation time, I.e. the shortest the computation time the higher priority
• In this specific case, this priority assignment works
• Does it always work?
• If it does not work in this specific case is there an assignment that always works?
• Is there a better way (than trace analysis) to decide whether an assignment works?
• Classic paper, Liu Layland, JACM 1973
• m tasks, with periodicities (Pi), deadlines (Di Pi) and computation time (Ci)
• Monotone Priority
• task frequency fi task priority 1/ Pi),
• Always Scheduable if (but not only-if)
• Simple, elegant result
• No tight upper bound on the Utilization metric is available
• a trivial upper bound can be summation of the Task Utilization lt 1
• Tasks are periodic
• Tasks do not communicate with each other
• Tasks are scheduled according to priority, and task priorities are fixed (static priority scheduling)
• A task set may have feasible schedule, but not by using any static priority schedule
• Feasible static priority assignment
• Rate Monotonic Scheduling (RMS)
• Assigns priorities to tasks on the basis of their periods
• Highest-priority task is the one with the shortest period
• If ph lt pl, then Priorityh gt Priorityl
• P1 C1 1 T1 2 C1/T1 0.5
• P2 C2 1 T2 3 C2/T2 0.333
• P3 C3 1 T3 6 C3/T3 0.166
• Total utilization 1.0
• Since 1.0 lt 1.0 lt 3 (21/3 1) 0.779
• May or may not be schedulable
• However if C1 ½ the total utilization would be 0.75 and the system will always be schedulable.
• If a set of periodic tasks has a feasible static priority assignment, RMS is a feasible static priority assignment
• Outline of Proof
• Hint if there is a non-RMS feasible static priority assignment
• List the tasks in decremented order of priority
• Because non-RMS, there must be ? i and ? i1 such that
• Prove exchange ? i and ? i1 and the schedule is feasible
• Repeat the priority exchange
• RMA assumption the processes are independent
• Issue real RT-processes often are required to share resources that are unique to the system
• under such circumstances processes can block each other. In particular execution of high priority task can be blocked by execution of a low priority task which has locked a required resource
• In other word priorities are effectively inverted
• tasks 1 and 3 share a resource (S1)
• prio(task1) gtprio(task2) gtprio(task3)
• Task 2 can run for any amount of time it blocks Task 3 from finishing and unlocking resource needed by task 1.
• Infamous Mars pathfinder Priority Inversion Bug
• High priority task (task 1) is blocked by low priority task (task 3)
• the blocking period can be arbitrarily long
• Possible solutions
• no preemption during critical section (Interrupt-Masking Protocol)
• good for short critical sections, otherwise bad unnecessary CS blocking
• in critical section (CS), raise the task's priority to a level higher than all tasks ever using that CS (Priority inheritance protocol)
• In example, this prohibits Task 2 from preempting Task 3
• disadvantage unnecessary (priority) blocking, possibility of deadlock
• Each resource is assigned a priority equal to that of the highest priority task that uses that resource.
• Tasks then inherit the priority of the resource while it is locked
• Tasks are not scheduled if any resource it may need it already locked by another task
• This scheme prevents improper nesting of the priorities of critical section and thus prevents deadlocks
• Ref Lui Sha, Ragunathan Rajkumar, and John P. Lehoczky (September 1990). "Priority Inheritance Protocols An Approach to Real-Time Synchronization". IEEE Transactions on Computers 39 (9) 11751185. doi10.1109/12.57058
• Deadline Scheduling the task which has the earliest deadline, will be scheduled first
• A system that collects and processes data from two sensors, A and B. The deadline for collecting data from sensor A must be met every 20 ms, and that for B every 50 ms. It takes 10 ms to process each sample of data from A and 25 ms to process each sample of data from B.
• Very well known for real-time processing
• Optimal dynamic algorithm - produces a valid schedule whenever one exists.
• If priorities are used, earliest deadline gets the highest priority.
• Complexity of algorithm is O(n2).
• Upper bound of process utilization is 100.
• Time Driven Scheduler - extension of EDF
• handles overload situation by aborting tasks if overload occurs. It also removes tasks from the queue with low priority.
• Best known algorithm for real time processing
• At every new ready state, the scheduler selects the task with earliest deadline among the tasks that are ready not fully processed
• The processing of the interrupted task is done according to EDF algorithm later on
• Optimal algorithm
• Dynamic algorithm
• Produces a valid schedule whenever exists
• If a task can be scheduled using any static priority assignment, it can also be scheduled by EDF
• Schedules every instances of incoming task according to its specific demands
• Each task is assigned a priority according to its deadline
• Highest priority to the task with earliest deadline
• Overhead in rearranging priorities
• TDS-Time driven Scheduler
• An extension of EDF
• Handles overload
• Aborts all the tasks that cannot meet their deadlines anymore
• If there is still overload, tasks with low value densities(importance of a task for the system) are removed
• Another variation handles every task as consisting of two parts, mandatory part and optional part
• A task is scheduled for its mandatory part
• Optional part is processed, if the resource capacity is not fully utilized
• A set of task is schedulable if all tasks can meet the deadlines of their mandatory part
• Improves the system performance at the expense of media quality
• Audio stream have the rate of 1/75 s/sample video stream have the rate of 1/25 s/frame
• Priority assigned to an audio stream is then higher
• Arrival of messages from audio stream will interrupt video frame
• The context switches with rate monotonic algorithm will be more than EDF in the presence of more than one stream
• Processor utilization in rate monotonic
• Upper bound of processor utilization is determined by critical instant
• For each number of n independent tasks t(j), a constellation can be found where maximum possible processor utilization is minimal
• The sharing of (data) resource, when the use of the resource must be atomic, and the tasks must realise deadlines , necessitates choosing
• a synchronisation primitive (semaphors, regions etc.)
• an allocation policy (what happens when request is made but the resource is taken)
• an execution priority during the use of the resource (change? of priority while using of a resource)
• Definition Combined choice is called a synchronisation protocol
• FIFO semaphores
• semaphores are used to implement the critical section
• if the resource is busy, queueing is performed in FIFO order
• the task that is using the resource does not adjust its execution priority
• interrupt masking
• disable pre-emption
• set interrupt level to the maximum level
• The best scheduling algorithm maximizes the number of completed tasks
• Tasks are usually treated as preemptive, to guarantee the processing of periodic processes
• High preemtability minimizes priority inversion
• There may not be any feasible schedule for non-preemptive schedule
• Scheduling of non-preemptive tasks is less favorable because number of schedulable task sets is smaller compared to preemptive tasks

PowerShow.com is a leading presentation sharing website. It has millions of presentations already uploaded and available with 1,000s more being uploaded by its users every day. Whatever your area of interest, here you’ll be able to find and view presentations you’ll love and possibly download. And, best of all, it is completely free and easy to use.

You might even have a presentation you’d like to share with others. If so, just upload it to PowerShow.com. We’ll convert it to an HTML5 slideshow that includes all the media types you’ve already added: audio, video, music, pictures, animations and transition effects. Then you can share it with your target audience as well as PowerShow.com’s millions of monthly visitors. And, again, it’s all free.

About the Developers

PowerShow.com is brought to you by  CrystalGraphics , the award-winning developer and market-leading publisher of rich-media enhancement products for presentations. Our product offerings include millions of PowerPoint templates, diagrams, animated 3D characters and more.