Real-Time Operating System

5m ago
662.85 KB
90 Pages
Last View : 1m ago
Last Download : 2m ago
Upload by : Baylee Stein

Real-Time Operating SystemELC 4438 – Spring 2016Liang DongBaylor University

RTOS – Basic Kernel Services

Task Management Scheduling is the method by which threads,processes or data flows are given access tosystem resources (e.g. processor time,communication bandwidth). The need for a scheduling algorithm arises fromthe requirement for most modern systems toperform multitasking (executing more than oneprocess at a time) and multiplexing (transmitmultiple data streams simultaneously across asingle physical channel).

Task Management Polled loops; Synchronized polled loopsCyclic Executives (round-robin)State-driven and co-routinesInterrupt-driven systems– Interrupt service routines– Context switching

Interrupt-drivenSystemsvoid main(void){init();while(true);}void }void }

Task scheduling Most RTOSs do their scheduling of tasks using a scheme called"priority-based preemptive scheduling." Each task in a software application must be assigned apriority, with higher priority values representing the need forquicker responsiveness. Very quick responsiveness is made possible by the"preemptive" nature of the task scheduling. "Preemptive"means that the scheduler is allowed to stop any task at anypoint in its execution, if it determines that another task needsto run immediately.

Hybrid Systems A hybrid system is a combination of roundrobin and preemptive-priority systems.– Tasks of higher priority can preempt those oflower priority.– If two or more tasks of the same priority are readyto run simultaneously, they run in round-robinfashion.

Thread wNormalDThreadPriority.LowestDefault priority is Normal.BEF

Thread wNormalDBEFThreadPriority.LowestThreads A and B execute, each for a quantum, in round-robin fashionuntil both threads complete.

Thread wNormalDThreadPriority.LowestThen thread C runs to completion.BEF

Thread wNormalDBEFThreadPriority.LowestNext threads D, E, F execute in round-robin fashion until they allcomplete execution.

Thread wNormalDThreadPriority.LowestBE“Starvation”F

Foreground/Background Systems A set of interrupt-driven or real-time processescalled the foreground and a collection ofnoninterrupt-driven processes called thebackground. The foreground tasks run in round-robin, preemptivepriority, or hybrid fashion. The background task is fully preemptable by anyforeground task and, in a sense, represents thelowest priority task in the system.

Foreground/Background Systems All real-time solutions are just special cases of theforeground/background systems. The polled loop is simply a foreground/backgroundsystem with no foreground, and a polled loop as abackground. Interrupt-only systems are foreground/backgroundsystems without background processing.

RTOSs vs. general-purpose operating systems Many non-real-time operating systems also provide similarkernel services. The key difference between generalcomputing operating systems and real-time operating systemsis the need for " deterministic " timing behavior in the realtime operating systems. Formally, "deterministic" timing means that operating systemservices consume only known and expected amounts of time. In theory, these service times could be expressed asmathematical formulas. These formulas must be strictlyalgebraic and not include any random timing components.

RTOSs vs. general-purpose operating systems General-computing non-real-time operating systems are oftenquite non-deterministic. Their services can inject randomdelays into application software and thus cause slowresponsiveness of an application at unexpected times. Deterministic timing behavior was simply not a design goal forthese general-computing operating systems, such asWindows, Unix, Linux. On the other hand, real-time operating systems often go astep beyond basic determinism. For most kernel services,these operating systems offer constant load-independenttiming.

The horizontal solid green line shows the task switching time characteristic of areal-time operating system. It is constant, independent of any load factor suchas the number of tasks in a software system.

Intertask Communication & Sync Previously, we assume that all tasks are independentand that all tasks can be preempted at any point oftheir execution. In practice, task interaction is needed. The main concern is how to minimize blocking thatmay arise in a uniprocessor system when concurrenttasks use shared resources.

Buffering Data To pass data between tasks in a multitaskingsystem, the simplest way is to use globalvariables. One of the problems related to using globalvariables is that tasks of higher- priority canpreempt lower-priority routines atinopportune times, corrupting the global data. Data buffer

Time-Relative BufferingFill hereEmpty hereSwap buffers with interrupts off

Page Flipping via Pointer SwitchingWhen a page flip occurs,the pointer to the old backbuffer now points to theprimary surface and thepointer to the old primarysurface now points to theback buffer memory. Thissets you up automaticallyfor the next drawoperation.

Receiving and Processing BuffersDataSamplingBack BufferDataProcessingPrimary BufferDouble-Buffering for Data Reception and Process

Time-Relative Buffering Double-buffering uses a hardware or softwareswitch to alternate the buffers. Applications: disk controller, graphicalinterfaces, navigation equipment, robotcontrols, etc.

Circular BufferHead: Empty hereTail: Fill here

Circular BufferingDataSamplingWriting PointerPrimary BufferProcessing PointerDataProcessingCircular-Buffering for Data Reception and ProcessWriting Pointer : mod (total writing count, buffer size);Processing Pointer : mod(total processing count, buffer size);

Circular Buffering (Cont.)Writing PointerDataSamplingDataProcessingProcessing PointerPrimary BufferPointers’ Chases in Circular-Buffering

Mailboxes Mailboxes or message exchanges are an intertaskcommunication device available in many fullfeatured operating systems. A mailbox is a mutually agreed upon memorylocation that one or more tasks can use to pass data. The tasks rely on the kernel to allow them to write tothe location via a post operation or to read from itvia a pend operation.

void pend(int data, S);void post(int data, S); The difference between the pend operation andsimply polling the mailbox is that the pendingtask is suspended while waiting for data toappear. Thus, no time is wasted continuallychecking the mailbox.

Mailboxes The datum that is passed can be a flag used toprotect a critical resource (called a key). When the key is taken from the mailbox, the mailboxis emptied. Thus, although several tasks can pend onthe same mailbox, only one task can receive the key. Since the key represents access to a critical resource,simultaneous access is precluded.

Queues Some operating systems support a type of mailboxthat can queue multiple pend requests. The queue can be regarded as any array ofmailboxes. Queue should not be used to pass array data;pointers should be used instead. Queues – control access to the “circular buffer”.

Critical Regions Multitasking systems are concerned withresource sharing. In most cases, these resources can only beused by one task at a time, and use of theresource cannot be interrupted. Such resources are said to be serially reusable.

Critical Regions While the CPU protects itself againstsimultaneous use, the code that interacts withthe other serially reusable resources cannot. Such code is called a critical region. If two tasks enter the same critical regionsimultaneously, a catastrophic error occur.

Semaphores The most common methods for protectingcritical regions involves a special variablecalled a semaphore. A semaphore S is a memory location that actsas a lock to protect critical regions. Two operations: wait P(S), signal V(S)

Semaphores The wait operation suspends any programcalling until the semaphore S is FALSE,whereas the signal operation sets thesemaphore S to FALSE. Code that enters a critical region is bracketedby calls to wait and signal. This prevents morethan one process from entering the criticalregion.

void P(int S){while (S true);S true;}void V(int S){S false;}Semaphore isinitialized tofalse.

Process 1.P(S)critical regionV(S).Process 2.P(S)critical regionV(S).

Mailboxes and Semaphores Mailboxes can be used to implementsemaphores if semaphore primitives are notprovided by the operating system. In this case, there is the added advantage thatthe pend instruction suspends the waitingprocess rather than actually waiting for thesemaphore.

void P(int S){int key 0;pend(key, S);}void V(int S){int key 0;post(key, S);}

Counting Semaphores The P and V semaphores are called binarysemaphores because they can take one of twovalues. Alternatively, a counting semaphore can beused to protect pools of resources, or to keeptrack of the number of free resources.

void P(int S){S--;while(S 0);}void V(int S){S ;}

void MP(int R){P(S);R--;if (R 0){V(S);P(T);}V(S);}/* multiple wait */void MV(int R){P(S);R ;if (R 0)V(T);elseV(S);}/* multiple signal *//* lock counter *//* request a resource *//* none available? *//* release counter *//* wait for free resource *//* release counter *//* lock counter *//* free resource *//* release counter */

Counting Semaphores The integer R keeps track of the number offree resources. Binary semaphore S protectsR, and binary semaphore T is used to protectthe pool of resources. The initial value of S is set to False, T to True,and R to the number of available resources inthe kernel.

Other Synchronization Mechanisms Monitors are abstract data types that encapsulatethe implementation details of the serial reusableresource and provides a public interface. Instances of the monitor type can only be executedby one process at a time. Monitors can be used to implement any criticalregion.

Other Synchronization Mechanisms Event-flag structures allow for the specification of anevent that causes the setting of some flag. A second process is designed to react to this flag. Event flags in essence represent simulated interruptscreated by the programmer.

Deadlock When tasks are competing for the same set of two ormore serially reusable resources, a deadlocksituation or deadly embrace may occur. Starvation differs from deadlock in that at least oneprocess is satisfying its requirements but one ormore are not. In deadlock, two or more processes cannot advancedue to mutual exclusion.

Deadlock When tasks are competing for the same set of two ormore serially reusable resources, a deadlocksituation or deadly embrace may occur. Starvation differs from deadlock in that at least oneprocess is satisfying its requirements but one ormore are not. In deadlock, two or more processes cannot advancedue to mutual exclusion.Serious problem!!!

Life Cycle of a ThreadUnstarted

Life Cycle of a ThreadUnstartedStartStarted

Life Cycle of a sign a processor)Running

Life Cycle of a ThreadUnstartedStartedRunningcompleteor AbortStopped

Life Cycle of a ThreadUnstartedStartedI/O completion,Lock availableRunningissue I/O request,Lock unavailableStoppedBlocked

Life Cycle of a ThreadUnstartedStartedPulsePulseAllInterruptsleep interval expiresRunningWait, Sleep, JoinWaitSleepJoinStoppedBlocked

Life Cycle of a nResumeSuspendedStoppedBlocked

Life Cycle of a leep interval expiresquantumexpirationRunningWait, Sleep, JoinSuspendedWaitSleepJoinResumedispatch(assign a processor)I/O completion,Lock availableSuspendedcompleteor Abortissue I/O request,Lock unavailableStoppedBlocked

Deadlock Prevention Mutual exclusion can be removed through the use ofprograms that allow resources to appear to beshareable by application (e.g. spoolers for printers). To prevent “hold and wait”, we allocate to a processall potentially required resources at the same time. Finally, preemption can preclude deadlock. Again,this will create starvation.

Deadlock Avoidance The best way to deal with deadlock is to avoid italtogether. A lock refers to any semaphore used to protect acritical region. For example, if the semaphores protecting criticalresources are implemented by mailboxes with timeouts, deadlocking cannot occur, (but starvation ofone or more tasks is possible).

Deadlock Avoidance1. the number of critical regions as well asminimizing their size.All processes must release any lock before returning to thecalling function.Do not suspend any task while it controls a critical region.All critical regions must be error free.Do not lock devices in interrupt handlers.Always perform validity checks on pointers used withincritical regions. (Pointer errors are common in C and canlead to serious problems within the critical regions.)

Deadlock Avoidance:The Banker’s Algorithm Analogy of a bank: depositors and cash reserve. The algorithm ensures that the number of resourcesattached to all processes and potentially needed forat least one to complete, can never exceed thenumber of resources for the system. The program shall not enter “unsafe state” to avoiddeadlock.

Generalized Banker’s Algorithm Extended to two or more pools of resources. Consider a set of processes p1, , pn and a set ofresources r1, , rm. max[i,j] represents the max claim of resources type jby process i. alloc[i,j] represents the number of units of resourcesj held by process i.

Generalized Banker’s Algorithm cj : resources of type j avail[j] : the resulting number of available resourcesof type j if the resource is granted.

Generalized Banker’s Algorithm cj : resources of type j avail[j] : the resulting number of available resourcesof type j if the resource is granted.

Generalized Banker’s Algorithm cj : resources of tpye j avail[j] : the resulting number of available resourcesof tpye j if the resource is granted.

Generalized Banker’s Algorithm cj : resources of tpye j avail[j] : the resulting number of available resourcesof tpye j if the resource is granted.If no such pi exists, the state is unsafe.

Priority Inversion When a low-priority task blocks a higherpriority one, a priority inversion is said tooccur. The problem of priority inversion in real-timesystems has been studied intensively for bothfixed-priority and dynamic-priority scheduling.

Priority Inheritance Protocol The priority of tasks are dynamically changedso that the priority of any task in a criticalregion gets the priority of the highest taskpending on that same critical region. When a task blocks one or more higherpriority tasks, it temporarily inherits thehighest priority of the blocked tasks.

Priority Inheritance Protocol A 1997 NASA incident of MarsPathfinder Space mission’sSojourner rover vehicle: Ameteorological data-gatheringtask (low priority low frequency)blocked a communications task(high priority high frequency).This infrequent scenario causedthe system to reset. The problem was diagnosed in ground-based testing andremotely corrected by reenabling the priority inheritancemechanism.

Priority Inheritance Protocol Priority Inheritance Protocol does not preventdeadlock. In fact, PIP can cause deadlock or multipleblocking. Priority Ceiling Protocol, which imposes a totalordering on the semaphore access, can get aroundthese problems.

Priority Ceiling Protocol Each resource is assigned a priority (thepriority ceiling) equal to the priority of thehighest priority task can use it. A task, T, can be blocked from entering acritical section if there exists any semaphorecurrently held by some other task whosepriority ceiling is greater than or equal to thepriority of T.

Memory Management Dynamic memory allocation is important in both the use ofon-demand memory by applications and the requirements ofthe operating system. Application tasks use memory explicitly through requests forheap memory, and implicitly through the maintenance of therun-time memory needed to support sophisticated high-orderlanguages. Operating system needs to perform extensive memorymanagement.

Process Stack Management In a multitasking system, context for each task needsto be saved and restored in order to switchprocesses. Run-time stacks work best for interrupt-only systemsand foreground/background systems. Task-control block model works best with fullfeatured real-time operating systems.

Run-Time Stack A run-time stack is to be used to handle the run-timesaving and restoring of context. The save routine is called by an interrupt handler tosave the current context of the machine into a stackarea. To prevent disaster, save call should be madeimmediately after interrupts have been disabled.

Run-Time Stack The restore routine is called by an interrupthandler to restore the context of the mainmachine from a stack area. The restore routine should be called justbefore interrupts are enabled and beforereturning from the interrupt handler.

Run-Time Stacksave (stack)restore RESUBLOADEPIRETURER0, &stack, IR0, &stackR0, 1R1, R0, IR0, 1R2, R0, IR0, 1R3, R0, IR0, 1PC, R0, IR0, 1R0, &stackRETURER0, &stackR0, 1PC, R0, IR0, 1R3, R0, 1R0, 1R2, R0, IR0, 1R1, R0, IR0, &stackR0, 1R0, R0, I

Run-Time Stackvoid int handler (void){save(mainstack);switch(interrupt){case 1: int1();break;case 2: int2();break;}restore(mainstack);}void d int2(void){save(stack);task2();restore(stack);}

Run-Time StackPriorityHighTask 1Task 2LowTask 2Task 3Task 3TimeStackContext 2Context 3Context 3Context 3

Task-Control Block Model:Fixed Case N task-control blocks are allocated at systemgeneration time, all in the dormant state. As tasks are created, the task-control block entersthe ready state. Prioritization or time slicing will move the task to theexecute state. If a task is to be deleted, its task-control block issimply placed in the dormant state.

Task-Control Block Model:Dynamic Case In the dynamic case, task-control blocks are added to a linkedlist as tasks are created. The tasks are in the suspended state upon creation and enterthe ready state via an operating system call. The tasks enter the execute state owing to priority or timeslicing. When a task is deleted, its task-control block is removed fromthe linked list, and its heap memory allocation is returned tothe unoccupied status.

Run-Time Ring Buffer A run-time stack cannot be used in a roundrobin system because of its FIFO nature ofscheduling. A circular queue can be used in a round-robinsystem to save context. The context is saved to the tail of the list andrestored from the head of the list.

Maximum Stack Size The maximum amount of space needed for the runtime stack needs to be known a priori. In general, stack size can be determined if recursionis not used and heap data structures are avoided. Ideally, provision for at least one more task thananticipated should be allocated to the stack to allowfor spurious interrupts.

Multiple-Stack Arrangement Often a single run-time stack is inadequate tomanage several processes, e.g. in aforeground/background system. A multiple-stack scheme uses a single run-time stackand several application stacks. The embedded real time system using multiple stackscan be implemented by a language that supportsreentrancy and recursion, such as C.

Multiple-Stack ArrangementPointer toapplication stackRun-Time StackProcess 1 StackProcess 2 Stack Process 3 Stack

Memory Management in the Task-ControlBlock Model When implementing the TCB model of realtime multitasking, the chief memorymanagement issue is the maintenance of thelinked lists for the ready and suspended tasks.Ready ListSuspended ListExecuting Task

Memory Management in the Task-ControlBlock Model When implementing the TCB model of realtime multitasking, the chief memorymanagement issue is the maintenance of thelinked lists for the ready and suspended tasks.Ready ListSuspended ListExecuting Task

Dynamic Memory Allocation Usually, memory fragmentation problem canbe solved by so-called "garbage collection"(defragmentation) software.

Dynamic Memory AllocationUsed blockUnused blockUnmovable block

Dynamic Memory Allocation Usually, memory fragmentation problem canbe solved by so-called "garbage collection"(defragmentation) software. Unfortunately, "garbage collection" algorithmsare often wildly non-deterministic – injectingrandomly-appearing random-duration delaysinto heap services.

Dynamic Memory Allocation RTOSs offer non-fragmenting memory allocationtechniques instead of heaps. They do this by limiting the variety of memory chunksizes they make available to application software. While this approach is less flexible than the approachtaken by memory heaps, they do avoid externalmemory fragmentation and avoid the need fordefragmentation.

Dynamic Memory Allocation Pools totally avoid external memory fragmentation,by not permitting a buffer that is returned to thepool to be broken into smaller buffers in the future.

Dynamic Memory Allocation Instead, when a buffer is returned the pool, it is putonto a "free buffer list" of buffers of its own size thatare available for future re-use at their original buffersize.

Dynamic Memory Allocation Memory is allocated and de-allocated from a poolwith deterministic, often constant, timing.

computing operating systems and real-time operating systems is the need for " deterministic " timing behavior in the real-time operating systems. Formally, "deterministic" timing means that operating system services consume only known and expected amounts of time. In theory, these service times could be expressed as mathematical formulas.

Related Documents:

1.1 Hard Real Time vs. Soft Real Time Hard real time systems and soft real time systems are both used in industry for different tasks [15]. The primary difference between hard real time systems and soft real time systems is that their consequences of missing a deadline dif-fer from each other. For instance, performance (e.g. stability) of a hard real time system such as an avionic control .

Key words and phrases: operating system design, real time operating system, layered operating system, software architecture, and process communication. CR Categories: 3.80, 3.83, 4.35. i. INTRODUCTION The Modular Operating System for SUMC (MOSS) is a general purpose real time operating

Operating System uses CPU scheduling and multiprogramming to provide each user with a small portion of a time-shared computer. (4) Real Time Operating System : Real Time Operating System is a special purpose Operating System, used when there are rigid time requirements on the operation of a processor or the flow of data.

Introduction to Real-Time Systems Real-Time Systems, Lecture 1 Martina Maggio and Karl-Erik Arze n 21 January 2020 Lund University, Department of Automatic Control Content [Real-Time Control System: Chapter 1, 2] 1. Real-Time Systems: De nitions 2. Real-Time Systems: Characteristics 3. Real-Time Systems: Paradigms

Most of the algorithms are applicable for the general-purpose operating system and do not fulfill the necessities of real-time systems. Moreover, limited allocators designed to support real-time . available to simulate different test cases for scheduling in a real-time operating system like Litmus-RT, Mark3, rtsim, etc., but till date, none .

asics of real-time PCR 1 1.1 Introduction 2 1.2 Overview of real-time PCR 3 1.3 Overview of real-time PCR components 4 1.4 Real-time PCR analysis technology 6 1.5 Real-time PCR fluorescence detection systems 10 1.6 Melting curve analysis 14 1.7 Passive reference dyes 15 1.8 Contamination prevention 16 1.9 Multiplex real-time PCR 16 1.10 Internal controls and reference genes 18

Real Time Operating Subcommittee Presentation Package. Presentations are posted with the written consent of the authors. Real Time Operating Subcommittee Meeting. November 4, 2020 . RELIABILITY RESILIENCE SECURITY. Real Time Operating Subcommittee. 2020-2021 Work Plan .

10.2 The Real-Time Operating System (RTOS) Real-time operating systems are built around a multi-tasking kernel which controls the allocation of time slices to tasks. A time slice is the period of time a given task has for execution before it is stopped and replaced by another task. This process, also known as context

The implementation of a real-time operating system for a small satellite project has an extensive list of pros and cons. A real time operating system’s multithreaded structure allows for the ability to design a complex software system with more flight capabilities and configuration options to support the success of mission goals.

Real-time Operating System (RTOS) Fundamentals P/N: BE18-7001 Page 2 of 6 Contact Information: Jacob Beningo P.O. Box 400 Linden, Mi 48451 Sessions Overview: Session 1 – Real-time Embedded Systems Concepts Hard versus soft real-time Bare metal scheduling techniques Designing a Cooperative Scheduler Best .

Getting Started with the LabVIEW Real-Time Module This document provides exercises designed that introduce you to the LabVIEW Real-Time Module. Over the course of these exercises, you will examine, modify, and deploy a real-time application. You will also learn concepts and practices for programming a real-time operating system. Contents

Avoid sources of non-determinism in real-time code - Memory allocation and management ( malloc, new ) Pre-allocate resources in the non real-time path Real-time safe O(1) allocators exist - Blocking synchronization primitives (e.g. mutex) Real-time safe alternatives exist (e.g. lock-free) - Printing, logging ( printf, cout )

Real-Time Analysis 1EF77_3e Rohde & Schwarz Implementation of Real -Time Spectrum Analysis 3 1 Real-Time Analysis 1.1 What “Real-Time” Stands for in R&S Real-Time Analyzers The measurement speed available in today's spectrum analyzers is the result of a long

real-time side to the non-real-time one, as shown in Figure 1. The information flow for the WaitFreeReadQueue is from the non-real-time side to the real-time one, as shown in Figure 2. When a NHRT wants to send data to a regu-lar Java thread, it uses the write (real-time) operation of WaitFreeWriteQueue class. Regular threads use the

Well-defined fixed-time constraints CSE480/CIS700 S. Fischmeister 6 More Precisely? The system allows access to sensitive resources with defined response times. oMaximum response times are good for hard real-time oAverage response times are ok for soft real-time Any system that provides the above can be classified as a real-time system

1.1 Operating System Functionality The operating system controls the machine It is common to draw the following picture to show the place of the operating system: application operating system hardware user This is a misleading picture, because applications mostly execute machine instruc-tions that do not go through the operating system.

in order to run on an embedded device, we still require Real-Time Operating System (RTOS) functions to handle task scheduling. FreeRTOS is an open-source real time operating system owned by Amazon and is a popular choice for embedded device developers. Amazon provides libraries to assist de-velopers in connecting their device to use Amazon Web

Real Time Operating Systems 1 from Fundamentals of Real Time Systems Mukul Shirvaikar & Theodore Elbert Chapter 4. 2 . The "real-time clock" -supported in hardware by a peripheral - on or off chip. 29 The System Timer Most of the modern ARM processor cores

An operating system is a control program. It controls the execution of user programs to prevent errors and improper use of the computer. The Primary goal of operating system is convenience for the user. The operating system makes the use of system easier. The secondary goal of operating system is efficient operation of the computer system.

American Math Competition 8 Practice Test 8 89 American Mathematics Competitions Practice 8 AMC 8 (American Mathematics Contest 8) INSTRUCTIONS 1. DO NOT OPEN THIS BOOKLET UNTIL YOUR PROCTOR TELLS YOU. 2. This is a twenty-five question multiple choice test. Each question is followed by