CES 520 - WEEKS 7/8 October 3/10 2006 - Real-time operating systems (RTOS)

Review of multitasking without a real-time operating system

• Multitasking
• Multiple tasks share common resources (CPU, memory, etc.)
• Some type of scheduler switches between tasks. This is called a context switch.
• Gives the illusion of tasks running in parallel
• Tasks are always in one of three states:
• Running. Only one task is running on a microprocessor at any given time.
• Ready. Waiting for some other task(s) to finish.
• Blocked. Waiting for some external event. (e.g. waiting for input data to appear)
• Simple multitasking schemes
• Round robin
• Each task executes in order. All effectively have the same priority.
• Easiest to implement. No shared-data problems.
• Polled I/O only. Poor control of timing.
• Poor response time.
• Round robin with interrupts
• Interrupts execute immediately = Interrupts have higher priority than other tasks.
• Potential shared-data problems.
• Function-queue scheduling
• As each task ends, a scheduler decides which task to do next.
• Easier to add new tasks without exceeding real-time requirements of previous tasks.
• Real-time operating system
• Most are preemptive:
• A higher-priority task doesn't have to wait for a lower-priority task to finish.
• Each process has its own environment. Interprocess communication is carefully controlled.
• Shared-resource problem
• An RTOS provides the tools, but the programmer must implement them.
• Disadvantages of general-purpose OSs for a real-time system:
• High resource utilization (memory, CPU overhead)
• Difficult to access hardware in timely manner. e.g. no application-level control over interrupts
• No services to allow timing-sensitive interactions between processes

Typical features of a RTOS

• Gives applications direct access to hardware resources such as interrupts and devices.
• Includes a real-time task scheduler that gives predictable (but not necessarily fast) timing.
• Usually not programmable by the end user.
• User code usually starts the operating system, rather than the other way around in non-RT OS.
• The operating system is compiled and/or linked with the application.
• OS is configurable to leave out unused services. Suitable for resource-contrained environments.
• Cross-compiled on a host computer for download as a memory image to the target platform.
• Able to operate out of ROM.
• Two types of tasks: process vs thread
• A process includes:
• The program being executed
• The data it operates on
• The processor state or context (basically the registers)
• Each process has its own address space, file and device handles, sockets, and windows.
• Proceses communicate only through a formal interprocess communication mechanism
• Changing processes involves saving the state and changing the address space
• A thread is one task within a process.
• Threads within a process share the same address space.
• Sharing data between threads is easy and fast.
• However the operating system has no way to protect a thread's data from other threads.
• Thread switching is faster than process switching because of simpler context switching.
• The only context saving required is the stack and registers (including program counter).
• Most RTOSs only support threads to minimize hardware & computation overhead
• Dynamic creation of processes and threads
• Makes the application more flexible
• Increases the complexity of the OS
• Requires an error-handling strategy to cope with the possibility of the OS not being able to create a task because of lack of resources.
• Simple embedded systems typically only support static tasks that are specified in the software.

RTOS architectures

• Privileged mode:
• A supervisory program (typically the operating system kernel) that controls access to resources.
• For example, memory used by the operating system is protected.
• User mode
• Accesses critical resources by sending messages to a higher level.
• Protection rings
• A system of hierarchical privilege levels in an operating system.
• Ring 0 is the highest level. Has access to all hardware.
• Lower levels access higher-level resources through special system calls or "gates".
• Rings typically supported by the microprocessor hardware and/or firmware (software in ROM).
• Operating system layers
• Application Programming Interface (API)
• Method for applications to interface with the OS.
• An API is actually an abstract description, as opposed to a particular implementation of the API.
• The implementation is typically a library or software development kit (SDK).
• SDK may be just libraries and documentation or include debug hardware and IDE (Integrated Development Environment - editor, compiler, linker, simulator, loader, etc.)
• Kernel
• Runs in privileged mode.
• Applications pass control to kernel functions to perform privileged operations.
• Provides abstraction for, and control over:
• Scheduling
• Inter-process communication
• Hardware: Memory, processor, I/O
• Hardware Abstraction Layer (HAL)
• Sits between the OS and the hardware.
• Makes it easier to port an OS to a new hardware platform.
• Similar to a Nanokernel.
• Operating systems with a separate HAL:
• Windows NT, Windows 2000, Windows XP
• BSD (Berkeley Unix)
• Mac OS-X
• Linux
• Solaris
• Monolithic systems
• A complete operating system with full services. Entire OS runs in privileged mode.
• Applications run in user mode, make system calls to the OS to obtain services.
• Some monolithic kernels have small footprint, low processor overhead.
• Interrupts handled directly in kernel.
• Scheduler disabled during interrupt handling .
• Interrupts effectively have highest priority.
• Small interrupt overhead
• Some monolithic kernels are adapted from large operating systems (e.g. Lynux, Microsoft Windows)
• Large footprint, slower real-time response
• Give access to large array of publicly-available device drivers
• Wide selection of development tools
• Layered systems
• Like monilithic systems except OS is organized as heirarchy of layers at system design time
• Higher layers have more complex functionality
• Easier to maintain - changing higher layers does not require modifying lower layers.
• Portions of the OS that are not needed may be left out
• Microkernel
• The OS kernel contains only essential features. Typically:
• Scheduling
• Inter-process communication
• Memory allocation
• Timer management
• Most services are in separate server processes in user mode.
• Message-passing interface encourages modularity and enforces a clear structure.
• Application sends a message to the kernel which calls appropriate service(s).
• Efficient Inter-Process Communication (IPC) is especially important in microkernel OSs
• Microkernels tend to have slower performance than monolithic systems.
• Servers may have special privileges to access hardware devices.
• Adding new services does not require modifying the kernel.
• It's easy to minimize the footprint by eliminating unnecessary services.
• Tends to be more secure since only a small kernel operates in privileged mode.
• A server can crash without crashing the operating system
• Well-suited to large distributed systems where different functions run on different machines.
• Examples of microkernel operating systems
• QNX is one prominent POSIX-compliant microkernel-based RTOS for embedded systems.
• Virtual machine
• Splits OS into two parts, multiprogramming and system services.
• A virtual machine monitor
• Runs in privileged mode
• Implements multiprogramming
• Implements many virtual processors, each representing identical hardware
• One or more guest operating systems, each on a virtual processor, that run system services
• The different OSs do not have to be the same and may not be aware of others' presence.
• All guest OS instructions are intercepted by the virtual machine monitor before execution to assure security
• Failure of one virtual machine does not bring down the system.
• Virtual machine may be different from physical machine. e.g. Java interpreter

The interaction model

• Specifies how software components interact with each other
• Specifies both control (scheduling) and data flow (interprocess communication)
• Scheduling
• There are dozens of different scheduling disciplines. Two major categories are:
• Cooperative multitasking
• Each process voluntarily cedes control at an appropriate time
• An improperly-designed or hung process can bring the system to a stop.
• Preemptive multitasking
• Allows high-priority tasks to execute quickly
• Can guarantee each process a portion of CPU time
• More efficient use of CPU. Processes execute while other processes are waiting for resources.
• Earliest deadline first (EDF)
• Places processes in a priority queue. Next process to execute is the one with the earliest deadline.
• Dynamic scheduling
• Can utilize up to 100% of processor resources when scheculing periodic processes.
• Makes it easy to predict whether a system of periodic processes is schedulable.
• Unpredictable performance under overload conditions.
• Least Slack Time first (LST)
• Slack time = time remaining before deadline - remaining computation time
• Dynamic scheduling
• Can utilize up to 100% of processor resources when scheculing aperiodic processes.
• Rate Monotonic
• Static scheduling. Tasks with shortest periods execute first.
• Assumes tasks have deterministic deadlines equal to their periods. (Must finish before next start.)
• Processor usage approaches 100*ln(2) = 69.3% as the number of processes approaches infinity.
• 
• Time sharing
• Tasks switch on a clock interrupt.
• In real-time systems, usually combined with some preemptive multitasking scheme.
• Guarantees all tasks a "piece of the action".
• Priority inversion: Occurs when a higher-priority task is blocked waiting on a resource to be released by a lower-priority task that can't execute because higher-priority task(s) are running.
• Deadly embrace or deadlock is similar: Two processes lock two resources in reverse order.
• Two or more processes waiting for the same resource but each is waiting on the other to finish.
• No general solution. Each type of deadlock requires its own solution.
• Solutions:
• In simple cases, just make sure each task locks resources in the same order.
• Access the resource atomically
• Disable interrupts (or disable preemption)
• Very low overhead
• May be useful when preemption is disabled only for a very short time
• Priority inheritance protocol (PIP)
• Lower-priority task inherits priority of higher-priority task that is blocked on a resource locked by the lower-priority task.
• May be computationally difficult to calculate worst-case blocking time.
• Chained blocking can result in an almost-infinite blocking time.
• Does not prevent deadly embrace
• Priority Ceiling Protocol (PCP)
• Each resource has a ceiling value equal to highest priority of any task which can lock the resource
• Scheduler manipulates task priorities to avoid problems of priority inheritance
• Prevents some kinds of deadly embrace.
• High run-time overhead, even when locks are not contended (the normal case).
• PCP has better worst-case response but worse average response than PIP.
• Intermediate Ceiling Priority Protocol (ICPP)
• Like PCP but a task is immediately assigned the ceiling priority of the resource it is locking
• Easier to implement. No actual locks need be implemented
• No chained blocking. Only one low-priority task prevents highest-priority task from executing.
• Low-priority tasks must lock resources for only the minimum possible time to avoid delaying higher-priority tasks.
• Interprocess communication (IPC)
• The primary function of IPC is to avoid shared-data probems.
• Same problem as with interrupts.
• Reentrant function
• No global or static variables unless they are only accessed atomically.
• Use only automatic data (stored on the stack)
• Does not call any other non-reentrant functions.
• Does not use hardware in a non-atomic way.
• Semaphore - a synchronization device with an integer value and two atomic operations:
• "P" or "down"or "pend" or "wait" or "get" or "take" checks if semaphore >= 0.
• If yes, it decrements the value and returns to the caller.
• If no, calling process is blocked until another process performs a "V" operation
• "V" or "up" or "post" or "signal" or "give" or "release" checks if any process is blocked on the semaphore
• If yes, wakes exactly one process up so it can complete its P operation
• If no, increments the value of the semaphore
• Place semaphore "take" and "release" around critical sections that access shared resources.
• Mutex is a binary semaphore that ensures mutual exclusion among multiple threads.
• Semaphores can also be used for inter-process communication.
• Semaphores have very low overhead but are difficult to use correctly in complex applications.
• Require programmer to keep track of the various semaphores manually. Prone to errors.
• Holding a semaphore too long is like a too-long interrupt service routine.
• Subject to priority inversion and deadly embrace.
• Message queue
• Asynchronous protocol. Sender and receiver do not have to communicate at the same time.
• Sender doesn't have to wait for reply.
• Unpredictable timing
• The queue consists of a string of "messages", typiclly pointers to buffers.
• The task that reads from the queue must "know" the buffer length.
• Potential for shared-data problems.
• Can be used to pass control as well as data.
• There may be more than one task using a queue.
• There may be more than one queue per task.
• Can provide some message buffering, depending on (pre-defined) size of queue
• Or can use rendezvous strategy with no buffering. Source/receiver run in lockstep.
• Like semaphores, the programmer is responsible to manage which tasks read/write from each queue.
• Potential for queue overflow
• Different RTOSs deal with this in different ways.
• A Mailbox is a message queue with unlimited queue size.
• Pipes (and filters)
• Like a message queue where each "message" is a single byte of data.
• The receiving task (the filter) executes when data arrives at its input.
• Publisher-Subscriber
• Like a message queue, but with multiple receivers
• Topic-based system
• Messages are posted to logical channels (topics).
• Subscribers receive all messages posted to topics they subscribe to.
• Content-based system
• Subscribers select messages based on attributes or content
• Loosely-coupled
• Publisher and subscriber don't need knowledge of system architecture.
• No handshaking. Publisher need not even know of subscribers' existence.
• Easily scalable
• Increases message volume - may be an issue with network traffic.
• Blackboard
• Uses global variables
• Each process has access to the blackboard and reads and writes data as needed
• Client-server
• The client process asynchronously invokes the server, which provides OS services.
• Unpredictable timing
• Monitor - Controls shared resources.
• All tasks access the resource only through the monitor.
• The resource is locked by the compiler until the monitor task finishes or receives a safe condition variable from another task.
• Removes responsibility for avoiding shared data problems from programmer to compiler.

Memory management

• Virtual memory is mapped to physical memory.
• Gives each process the illusion of having exclusive access to memory.
• Prevents applications from accessing operating system memory.
• Also used to map a smaller logical address space to larger physical memory. (e.g. Rabbit 3000)
• Some OSs can map virtual memory to hard disc. Swapped in/out of RAM memory as needed.
• Dynamic memory allocation
• Standard memory allocation scans a linked list to find free memory on the heap. Not good for RTOS:
• The linked list is of indeterminate length. RTOS needs a predictable execution time.
• Memory fragmentation. Unlike a standard OS, the machine may not be rebooted for years.
• Most RTOSs use a system of fixed-size blocks for dynamic memory allocation.
• Usually includes some scheme to support several different-sized blocks.
• Best solution is to use only static and auto (stack-based) memory allocation.
• The virtual memory manager must be set up by software at first turn-on.

Interrupt Issues

• An interrupt service routine may not call any RTOS function that might block the ISR.
• The task that was running when the interrupt occurred is also blocked.
• An ISR may not call any RTOS function that can cause a task switch.
• Unless the RTOS knows it is being called by an ISR.
• Software must somehow specify to the RTOS which routines are ISRs.

POSIX

• "Portable Operating System Interface for UniX"
• Based on Unix, but applicable to other operating systems.
• Most common API standard for RTOSs.
• One of over 30 individual standards is System Interfaces (XSH) volume of IEEE 1003 and ISO/IEC 9945
• Goal is portability of applications at the source code level
• Defines standard OS interface and environment, including real-time extensions.
• Some services included:
• Process and thread management
• Event notification via signals
• Interprocess communication
• File system management
• Asynchronous and list-directed input/output
• Memory management
• Real-time extensions came in with version "1b"
• Preemptive fixed-priority scheduling
• Semaphores
• Message passing
• Clocks and timers
• The user command line and scripting interface is based on the Unix Korn shell (ksh).
• Ksh includes sophisticated programming capability.
• IPC Socket paradigm: Supports inter-process communication in a uniform way.
• Networks, protocols, naming conventions, hardware, etc.
• Connections appear as a byte-stream network, even if no network is involved.

POSIX-compliant operating systems:

• Real-time:
• BeOS
• Integrity
• LynxOS
• QNX
• RTAI
• RTEMS
• VxWorks (partial)
• Non-real-time:
• Linux
• BSD/OS
• A/UX
• MAC OS X
• MINIX
• SkyOS
• Windows NT, XP, Server 2003, 2000 Server or Professionsl

Applicability of RTOS

• Cases where RTOS makes sense:
• Large projects with many programmers working together.
• Enforces code structure and standard methods to share resources.
• Preemptive scheduling is needed to assure high-priority tasks are done first.
• Tasks share data structures or hardware resources.
• Systems with standard hardware resources that can use off-the-shelf drivers.
• Cases where RTOS is not a good choice:
• Simple systems where a simple state-machine scheduler suffices.
• Small systems with limited memory or processor speed.
• Very high-speed (short period) interrupts are needed.

Criteria for choosing a RTOS

• Performance
• Response time
• OS processing time overhead
• Memory usage, "footprint"
• Features
• Preemptive vs non-preemptive scheduling
• Scheduling modes offered
• Interprocess communication modes offered
• Other operating system services offered (memory management, file I/O, timer services, etc.)
• Support for particular microprocessors
• Support
• Integrated development environment (editor, compiler, debugger, etc.)
• Easy-to-use API. (POSIX-compliant?)
• Hardware and network drivers included.
• Source code or binary object code?
• Source code give visibility to OS inner workings. Can be useful if problems arise.
• Source code can be modified to change or add services. (Can be dangerous.)
• OS in binary format is easier to integrate.
• Cost. One-time fee or per-copy license?
• Available real-time operating systems
• Commercial
• LynxOS
• Compatible with Linux. POSIX-compliant.
• Has features to support hard real-time response.
• Supports memory management unit
• QNX
• Unix-like OS. POSIX compliant.
• Microkernel architecture with speed-optimized interprocess communication
• Small and fast
• MicroC/OS-II
• Supplied with our textbook.
• C source code provided. Scalable for small systems.
• VxWorks
• Wind River Systems. Probably the most popular RTOS.
• A scalable Unix-like OS with MMU (memory management unit) support.
• pSOS was purchased by Wind River and merged into VxWorks.
• Windows CE
• Microsoft's OS for small-memory systems.
• Has real-time capability.
• Popular in hand-held computers.
• Open-source
• eCos
• Highly configurable. Good for systems with limited memory.
• Has been ported to a very large number of processors.
• Formerly owned by Red Hat.
• RTAI and RTLinux
• Both are small real-time kernels that run a Linux kernel as the lowest-priority task.
• RTLinux also comes in a commercial version.
• microClinux is a very small Linux kernel often used with RTAI and RTLinux.
• RTEMS
• Originally called "Real-Time Executive for Military Systems"
• POSIX-compliant layered monolithic architecture.
• Has been ported to many processors.

Assignments:

• Read An Embedded Software Primer, Chapters 6, 7 and 8.
• Read Embedded Systems Design, Chapter 10 pp 435-436. Information on microC/OS is in the book listed in the references file.