Real-Time Operating System

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.