Real-time computing

• Has guaranteed or predictable response time

• Worst-case execution time is most interesting

• Optimized for predictability while general purpose is optimized for speed and throughput

• Not really possible to do with general-purpose operating systems

• Not a fancy way of saying fast computing

• Not irrelevant even if hardware is fast enough

Real-time operating systems (RTOS)

From book

Microprocessors

System-on-Chip (SoC) are typically used for more complex microcontrollers that also include graphic processing units, digital signal processors, FPGAs, etc.

Interrupts

Program

Generated by some condition that is a result from an instruction execution

Timer

Generated by a timer within the processor that ca be programmed to trigger at regular interval or after a certain amount of time has passed

I/O

Generated by an I/O controller to signal completion of an operation or some other condition

Hardware failure

Generated by a failure in the hardware

Can have sequential interrupts or nested interrupts (interrupts within interrupts)

Memory hierarchy

Inboard memory

• Registers
• Cache

Outboard Storage

• Magnetic Disk
• CD-ROM
• CD-RW
• DVD-RW
• DVD-RAM
• Blu-Ray

Off-line Storage

• Magnetic Tape

Cache

• Write policy determines how often the changes in cache is written back to the main memory

  • Update main memory every time cache block value is changed

  • Update main memory when the cache block value is changed – leaves main memory in obsolete state

Caches are divided into levels to exploit locality (lower levels = faster).

CPU ↔ L1 cache ↔ L2 cache ↔ L3 cache ↔ Main memory

Transferring data from I/O to main memory

Continous polling

(CPU)

Interrupt driven

(CPU)

Direct memory access

Writes to DMA module instead of CPU. CPU only informed when transfer is complete.

Reasons for having operating system

• Convenience – OS is the layer between computer hardware and user, interact with OS instead of hardware

  • Instruction set architecture (ISA) – Machine language instructions that a computer can perform
  • Facilitation of concurrency. Scheduling.
  • Abstraction of hardware and stability.

Hardware to OS

• Application binary interface (ABI) – User programs and libraries can access OS and hardware (ISA) services through system calls

OS to libraries

• Application programming interface (API) – Provide functions that other user programs can use to access the OS and hardware through system calls and other commonly used functionality

Libraries come with OS but not strictly part of OS

• Efficiency

  • OS allow efficient use of the computer system resources – scheduling, memory control, I/O access

• Ability to evolve

  • Integrate updated hardware

  • Development of new services

  • Upgrading the OS and programs

From book

• Processor: Controls the operation of the computer and performs its data processing functions. Where there is only one processor, it is often referred to as the central processing unit (CPU)

  • One of the processor’s functions is to exchange data with memory. Makes use of two internal registers: a memory address register (MAR), which specifies the address in memory for the next read or write; and a memory buffer register (MBR). Which contains the data to be written into memory or which receives the data read from memory.

• Main memory: Stores data and programs. This memory is typically volatile.

• I/O modules: Move data between the computer and its external environment.

• System bus: Provides communication among processors, main memory, and I/O modules.

• Microprocessors are now multiprocessors; each chip (called a socket) contains multiple processors (called cores), each with multiple levels of large memory caches, and multiple logical processors sharing the execution units of each core.

• Info about kernel: http://www.linfo.org/kernel.html

• The classic microprocessor is giving way to the system on a chip (SoC), where not just the CPUs and caches are on the same chip, but also many of the other components of the system, such as DSPs, GPUs, I/O devices (such as radios and codecs), and main memory.

• The replacement algorithm chooses, within the constraints of the mapping function, which block to replace when a new block is to be loaded into the cache and the cache already has all slots filled with other blocks

• An OS is a program that controls the execution of application programs and acts as an interface between applications and the computer hardware. It has three objectives

  • Convenience – an OS makes a computer more convenient to use

  • Efficiency – An OS allows the computer system resources to be used in an efficient manner

  • Ability to evolve – An OS should be constructed in such a way as to permit the effective development, testing, and introduction of new system functions without interfering with service

• A monolithic kernel is implemented as a single process, with all elements sharing the same address space

• A microkernel architecture assigns only a few essential functions to the kernel, including address spaces, IPC, and basic scheduling. Other OS services are provided by processes, sometimes called servers, that run in user mode and are treated like any other application by the microkernel

Multiprogramming:

• Maximize processor utilization, providing reasonable response times, let different tasks use different resources, allow tasks to communicate with each other

Process

• A process is an entity that can be assigned to and executed by a processor

• Each process has their own set of data

• Dispatcher – Tells the OS which process to start running

• 5 state process model:

  • Running – process currently executing in the CPU

  • Ready – Process is in a queue waiting to be executed

  • Blocked – running process has to wait for an event, remain blocked until the event occur, a separate queue for the blocked processes

  • New – Process has been created but not yet added to the pool of executable processes

  • Exit – Process that is removed from the pool of executable processes, but still exists in memory

• Swapping – when there is no room for a process in main memory, it is swapped to disk -Seven-state process model includes suspend states for ready and blocked

• Process image

  • User data – the modifiable part of the user space. May include program data, a user stack area, and programs that may be modified

  • User program – the program to be executed

  • Stack – Each process has one or more LIFO stacks associated with it. A stack is used to store parameters and calling addresses for procedure and system calls

  • Process control block – data needed by the OS to control the process

• Modes of execution – necessary to protect OS data structures from interference from user programs

  • User mode – less-privileged mode, user programs typically execute in this mode

  • System mode – more privileged mode, also referred to as control mode or kernel mode, kernel of the operating system

• Process creation

  • The OS assigns a process identifier to the new process, allocate memory space for the process, initialize the process control block, add the new process to appropriate lists (ready or suspended)

• Switching modes

  • Process: switch which process is running

  • Mode: If no interrupts are waiting, continue running the program

Threads vs processes

• The part that own the resources and data is called process or task

• The part or parts that follows an execution path is called a thread

• Multithreading is that the operating system supports multiple threads within each process

• Threads are faster than processes – both when it comes to switching and creating/exiting

• Threads share resources which makes it easier to communicate, synchronize etc.

User-level threads

• The application performs the thread management and scheduling

• The kernel does not know that the thread exists

• Advantages: Fast thread switch, portability, custom scheduling for task

Kernel-level threads

• The kernel schedule each of the threads in the process

• Advantages: If one thread of a process is blocked, the kernel can schedule another to run, different threads of a process can run on different CPU cores

User and kernel combined

-All threads made in user-space, multiple user level threads are mapped into a number of kernel threads

Memory management

• Protection

  • No process should modify the memory another process is currently using

  • No normal programs should be able to access any memory belonging to the kernel

  • Processor should have hardware functionality for enforcing memory protection

• Sharing

  • Processes need to co-operate – protection needs to be flexible enough to allow inter-process communication

• Organization – Logical and physical

• Placement algorithms

  • Best fit – chooses the block that is closest in size to the request

  • First fit – begins to scan memory from the beginning and chooses the first available block that is large enough

  • Next fit – begins to scan memory from the location of the last placement and chooses the next available block that is large enough

• Paging and segmentation – Both divide the memory of a program into smaller parts. Both introduce some variant of a table that keep track of where the different parts of a process is stored

  • Paging divide the data of a process into fixed-size pages that are stored in fixed-size frames in memory

  • Segmentation divide the data of a process into variable-length segments and store these in memory

  • Combination – segmentation from user/programmers point of view, paging from memory’s point of view

Virtual memory – secondary memory can be accessed as if it was main memory

• A process access memory with a virtual address, which can either be in main or secondary

• Some pages/segments of a process can be in main memory while others in secondary

• Advantages: “unlimited” memory, only data that is actually used are placed in main memory

• Disadvantages: thrashing, meaning that a system spend most of its time moving pages/segments between main and secondary memory

• Problem for real-time – if a part of a real-time process is suddenly in secondary memory, it can give an unexpected delay

From book

• When OS creates a process (child) at the explicit request of another process (parent), the action is referred to as process spawning

• When all processes in main memory are in Blocked, the OS can suspend one process by putting it in the Suspend state and transferring it to secondary memory. Same with ready.

• A process image consists of user data, user program, stack and process control block (process id, processor state information, process control information)

• Functions of an OS kernel:

  • Process management – creation and termination, scheduling and dispatching, switching, synchronization and support for IPC, management of process control blocks

  • Memory management – allocation of address space to processes, swapping, page and segment management

  • I/O management – buffer management, allocation of I/O channels and devices to processes

  • Support functions – interrupt handling, accounting, monitoring

• Process switching may occur any time the OS has gained control from the currently running process, caused by events like clock interrupt, I/O interrupt, memory fault)

• In a multiprocessor system, more than one process can be in the running state

• Two main characteristics of a process:

  • Resource ownership – process or task – virtual address space to hold the process image. A process may from time to time be allocated control or ownership of resources (main memory, I/O or files). The OS performs a protection function to prevent unwanted interference between processes with respect to resources.

  • Scheduling/Execution – lightweight process – follows an execution path through one or more programs. May be interleaved with other processes. Thus, a process has an execution state and a dispatching priority and is the entity that is scheduled and dispatched by the OS.

• Threads within the same process can communicate with each other without invoking the kernel, because they share memory and files

• Any alteration of a resource by one thread affects the environment of the other threads in the same process. It is therefore necessary to synchronize the activities of the activities of the various threads so that they do not interfere with each other or corrupt data structures.

• User-level threads – all of the work of thread management is done by the application and the kernel is not aware of the existence of threads (only sees the process).

• Advantages of user-level threads instead of kernel-level threads(KLT)

  • Thread switching does not require kernel mode privileges because all of the thread management data structures are within the user address space of a single process. Saves overhead of mode switches (user to kernel and back)

  • Scheduling can be application specific. One application may benefit most from RR scheduling while another from priority based.

  • ULTs can run on any OS. No changes are required to the underlying kernel support ULTs.

• Disadvantages of ULTs compared to KLTs

  • In a typical OS, many system calls are blocking. As a result, when a ULT executes a system call, not only is that thread blocked, but also all of the threads within the process are blocked

  • In a pure ULT strategy, a multithreaded application can not take advantage of multiprocessing. A kernel assigns one process to only one processor at a time.

• KLT – are threads within a process that are maintained by the kernel. Because they are recognized by the kernel, multiple threads within one process can execute in parallel on a multiprocessor and the blocking of one thread does not block the entire process. However, a mode switch is required to switch from one thread to another.

• Multithreaded native applications are characterized by having a small number of highly threaded processes

• Multiprocess applications are characterized by the presence of many single-threaded processes

• Process relate to resource ownership, thread relates to program execution

• Memory management terms

  • Frame – a fixed length block of main memory

  • Page – a fixed length block of data that resides in secondary memory. A page of data may temporarily be copied into a frame of main memory

  • Segment – a variable length block of data that resides in secondary memory. An entire segment may temporarily be copied into an available region of main memory (segmentation) or the segment may be divided into pages which can be individually copied into memory (combined segmentation and paging)

  • Internal fragmentation – wasted space internal to a partition due to the fact that the block of data loaded is smaller than the partition

  • External fragmentation – memory that is external to all partitions becomes increasingly fragmented. Lots of small holes in memory and memory utilization declines

• Memory management techniques

  • Fixed partitioning – main memory is divided into a number of static partitions at system generation time. A process may be loaded into a partition of equal or greater size. Simple, but inefficient use of memory due to internal fragmentation

  • Dynamic partitioning – Partitions are created dynamically, so that each process is loaded into a partition of exactly the same size as that process. No internal fragmentation and more efficient use of main memory, but inefficient use of processor due to the need for compaction to counter external fragmentation

  • Simple Paging – Main memory is divided into a number of equal-size frames. Each process is divided into a number of equal-size pages of same length as frames. A process is loaded by loading all of its pages into available, not necessarily contiguous frames. No external fragmentation, but a small amount of internal fragmentation.

  • Simple segmentation – each process is divided into a number of segments. A process is loaded by loading all of its segments into dynamic partitions that need not be contiguous. No internal fragmentation, improved memory utilization and reduced overhead compared to dynamic partitioning, but external fragmentation

  • Virtual memory paging – as with simple paging, except that it is not necessary to load all of the pages of a process. Nonresident pages that are needed are brought in later automatically. No external fragmentation, higher degree of multiprogramming, large virtual address space, but overhead of complex memory management

  • Virtual memory segmentation – as with simple segmentation, except it is not necessary to load all of the segments of a process. Nonresident segments that are needed are brought in later automatically. No internal fragmentation, higher degree of multiprogramming, large virtual address space, protection and sharing support, but overhead of complex memory management

• Paging – main memory is divided into many small equal-size frames. Each process is divided into frame-size pages. Smaller process requires fewer pages; larger processes require more. When a process is brought in, all of its pages are loaded into available frames, and a page table is set up. This approach solves many of the problems with partitioning.

• Segmentation – a process is divided into a number of segments that need not be of equal size. When a process is brought in, all of its segments are loaded into available regions of memory, and a segment table is set up

• Virtual memory terminology

  • Virtual memory – a storage allocation scheme in which secondary memory can be addressed as though it were part of main memory. The addresses a program may use to reference a memory are distinguished from the addresses the memory system uses to identify physical storage sites, and program-generated addresses are translated automatically to the corresponding machine addresses. The size of virtual storage is limited by the addressing scheme of the computer system and by the amount of secondary memory available and not by the actual number of main storage locations.

  • Virtual address – the address assigned to a location in virtual memory to allow that location to be accessed as though it were part of main memory

  • Virtual address space – the virtual storage assigned to a process

  • Address space – the range of memory addresses available to a process

  • Real address – the address of a storage location in main memory

• Virtual memory paging

  • Not all pages of a process need be in main memory frames for the process to run. Pages may be read in as needed. Reading a page into main memory may require writing a page out to secondary memory

• Virtual memory segmentation

  • Not all segments of a process need be in main memory for the process to run. Segments may be read in as needed. Reading a segment into main memory may require writing one or more segments to secondary memory

• Trashing – throwing out a piece of memory just before needing it and having to go get it back almost immediately – swapping pieces rather than executing instructions

Scheduling criteria

Turnaround time

interval between submission of a process and its completion

Response time

time from the submission of a request until the start of response

Deadlines

when process completion deadlines can be specified, as many deadlines as possible should be met

Predictability

a given job should run in about the same amount of time and at about the same cost regardless of the load on the system

Throughput

maximize number of processes completed per unit of time

Processor utilization

Percentage of time the processor is busy

Fairness

processes thread the same and no process suffer starvation

Enforcing priorities

favor higher-priority processes

Balancing resources

if a resource is overused, processes not needing it should be favored

Priority based scheduling

each priority gets its own queue, the dispatcher will check higher priority queues first

Scheduling methods

• First come first serve – dispatcher chooses the process that has been in the ready queue the longest
• Round robin – each process is given a time slice
• Shortest process next – shortest executing time
• Shortest remaining time – preemptive version of SPN
• Highest response ratio next – dispatcher chooses process from execution time and time waited in queue $R = \frac{w+s}{s}$
  • $R$: response ratio, $w$: time waited in queue, $s$: service time
• Feedback – decrease priority each time process is preempted, does not require knowledge of execution time

FreeRTOS

• Minimalistic operating system for microcontrollers that often does not use operating systems
• Run on many platforms
• Very small OS
• Tasks – regular process with own stack, is preemptive
• Co-Routines – intended for use on small processors that have severe RAM constraints, share a single stack
• Task model: running, ready, blocked and suspended
• Scheduling
  • Either co-operative or preemptive
  • Scheduler activated by a timer interrupt every clock tick
  • Equal priority tasks are scheduled with Round-Robin
• Use semaphores, mutexes and queues (message passing)
  • Task notification

Inter-process communication - sharing information, synchronization with

• Semaphores – wait/signal, counting/binary – provide synchronization between threads but does not protect the shared buffer
• Mutex – A mutex is a binary semaphore WITH the concept of ownership – only the process/thread that locked the mutex can unlock it
• Message passing – synchronization and exchange of data, blocking/non-blocking
• Race condition – multiple processes or threads read and write to the same data locations

From book

• Multiprogramming – the management of multiple processes within a uniprocessor system
• Multiprocessing – the management of multiple processes within a multiprocessor

• Distributed processing – the management of multiple processes executing on multiple, distributed computer systems.

• Concurrency encompasses a host of design issues, including communication among processes, sharing and competing for resources, synchronization of activities of multiple processes, and allocation of processor time to processes

  • Atomic operations – a function or action implemented as a sequence of one or more instructions that appears to be indivisible. The sequence of instruction is guaranteed to execute as a group, or not execute at all, having no visible effect on system state. Atomicity guarantees isolation from concurrent processes.

  • Critical section – a section of code within a process that requires access to shared resources and that must not be executed while another process is in a corresponding section of code

  • Deadlock – two or more processes are unable to proceed because each is waiting for one of the others to do something

  • Livelock – two or more processes continuously change their states in response to changes in the other process(es) without doing any useful work

  • Mutual exclusion – the requirement that when one process is in a critical section that accesses shared resources, no other process may be in a critical section that accesses any of those shared resources

  • Race condition – multiple threads or processes read and write a shared data item and the final result depends on the relative timing of their execution

  • Starvation – a runnable process is overlooked indefinitely by the scheduler

• To guarantee mutual exclusion, it is sufficient to prevent a process from being interrupted. This capability can be provided in the form of primitives defined by the OS kernel for disabling and enabling interrupts

• Concurrency mechanisms

  • Semaphore – an integer value used for signaling among processes. Only three operations may be performed on a semaphore, all of which are atomic: initialize, decrement, increment.

  • Binary semaphore – takes only values 0 and 1

  • Mutex – binary semaphore with the concept of ownership. This means that only the process/thread that locked the mutex can unlock it.

  • Condition variable – a data type that is used to block a process or thread until a particular condition is true

  • Event flags – a memory word used as a synchronization mechanism.

  • Messages – two processes exchange information and may be used for synchronization

  • Spinlocks – mutual exclusion mechanism in which a process executes in an infinite loop waiting for the value of a lock variable to indicate availability

• In message passing both sender and receiver can be blocking or non-blocking

  • Non-blocking solves the problem where a message might be lost or a process fails before it sends an anticipated message. Prevents the receiving process from being blocked indefinitely

• Indirect addressing – messages are sent to a shared data structure consisting of queues that can temporarily hold messages. The strength of the use of indirect addressing is that by decoupling the sender and receiver it allows for greater flexibility in the use of messages  

Linux kernel – monolithic kernel with loadable modules

Modular monolithic kernel

– Includes virtually all of the OS functionality in one large block of code that runs as a single process with a single address space. All the functional components of the kernel have access to all of its internal data structures and routines. Linux is structured as a collection of modules

• Loadable modules – A module is an object file whose code can be linked to and unlinked from the kernel at run-time. A module is executed in kernel mode on behalf of the current process.

  • Dynamic linking and stackable modules

Linux page replacement

• Least frequently used policy – each page in main memory has a counter, which is incremented each time it is accessed. Periodically decremented. The lower the counter, the less frequently it is used and will be preferred for replacement.

Kernel memory allocation

– Manages physical main memory page frames

• Primary function is to allocate and deallocate frames for particular users (like user-space processes, dynamically allocated kernel data, static kernel code, page cache)

• A buddy algorithm is used so memory for the kernel can be allocated and deallocated in units of one or more pages

• Page allocator alone would be inefficient because the kernel requires small short-term memory chunks in odd sizes

• Slab allocation – used by Linux to accommodate small chunks

Linux scheduling

• Three classes – FIFO, Round-robin, non-real-time threads

• Linux kernel not intended to be preemptive, and can’t be fully preemptive regardless of kernel configuration

Linux thread model

• Originally there were no threads in Linux, only processes. Threads could be implemented in user space inside the processes. One blocked thread would block the whole process

• Now, processes and threads are almost the same, both are running as separate “kernel threads”. Threads share the same virtual memory. Context switch between threads are faster than between processes. The kernel schedules each kernel thread individually.

User space

– Use System Calls to request kernel services. Kernel can notify user-space program with Signals

Kernel space

• Reasons for developing in kernel space: User space programs can only access the services already provided by the kernel. Need to access an unsupported device or a special feature of the CPU of the kernel. Functionality can be implemented in kernel space to reduce the number of “context switches” which reduce performance.

• Disadvantages with kernel space: The normal user-space libraries can’t be used in kernel space

• Root is the highest level of privilege you can have in user-space. Not the same as kernel space.

Real-time

• Linux is not a real-time system and the kernel is not preemptive.

• Soft real-time capabilities can be improved. Configure the kernel to be as preemptive as possible

• How to get harder real-time

  • Make Linux kernel full preemptive, thus more predictable – effect is uncertain

  • Add small real-time co-kernel that runs below Linux (RT-Linux, RTAI, Xenomai) Linux tasks cannot disturb real-time tasks

  • Outsource the hard real-time tasks to a slave microcontroller – provide better control of latencies

    • When outsourcing some of the real-time tasks to a specialized microcontroller, the Linux computer act as a supervisor. Suitable for systems that have a small, separate real-time component.

Xenomai

previous versions used a co-kernel or a dual kernel

• Dual kernel approach – Cobalt core runs beside the Linux kernel. Best performance, lowest latency.

• Single kernel approach – native Linux kernel normally patched with PREEMPT-RI – Mercury core

• Real-time device model (RTDM) – if a Xenomai program uses a Linux driver e.g. some hardware device, the driver will execute in Linux context, not Xenomai – not hard real-time and inefficient due to many switches between Linux and Xenomai

From book

• Most UNIX kernels are monolithic. Monolithic kernels include virtually all the OS functionality in one large block of code that runs as a single process with a single address space.

• Linux is structured as a collection of modules, a number of which can be automatically loaded and unloaded on demand.

  • A module is an object file whose code can be linked to and unlinked from the kernel at runtime.

  • Although Linux may be considered monolithic, its modular structure overcomes some of the difficulties in developing and evolving the kernel.

  • Dynamic linking – a kernel module can be loaded and linked into the kernel while the kernel is already in memory and executing. A module can also be unlinked and removed from memory at any time

  • Stackable modules – the modules are arranged in a hierarchy. Individual modules serve as libraries when they are referenced by client modules higher up in the hierarchy, and as clients when they reference modules further down.

Fixed-Priority Scheduling (FPS)

• If preemptive (which it probably should be), then the highest priority available task will always run.

• Optimal priority assignment for periodic, independent tasks is rate monotonic.

  • The shorter the period, the higher priority

Earliest deadline first (EDF)

• The priority of each task will change dynamically based on the current deadlines. EDF is able to schedule any task set as long as it takes less time to execute than what is available – optimal.

• EDF is more difficult to implement than fixed priority, it has more overhead. Difficult to incorporate tasks without deadlines in EDF. FPS is more predictable if the system gets overloaded.

Scheduling tests

Sufficient

If the test is passed, the tasks are certain to meet their deadlines. Utilization based test. Periods that are multiples of each other are considered to be in the same family.

Necessary

If the test is failed, the tasks will miss their deadlines.

Exact

Both necessary and sufficient. Response-time analysis – a method for calculating the worst case execution time of a task when there are higher priority tasks that interfere.

Utilization-based scheduability test is a simple test of fixed priority scheduling with rate monotonic priorities. It is sufficient (not necessary).

$$ U \equiv \sum_{i=1}^N{\frac{C_i}{T_i}} \leq N(2^{\frac{1}{N}}-1), $$

where $U$ is the utilization, $N$ the number of tasks, $T_i$ the period of task $i$ and $C_i$ the computational time of task $i$.

Tasks that have periods that are multiples of each other are considered to be in the same family.

Priority inversion

– when a high priority task has to wait for a lower-priority task. Okay if high-priority task is blocked by low priority due to shared resource. Not okay if medium priority prevents the low-priority task from completing and return the mutex.

Priority Ceiling protocols

Priority inheritance

Reduces the effect of priority inversions but does not prevent deadlocks – ceiling protocols do. Makes it easier to calculate the worst case blocking time.

Immediate ceiling priority protocol (ICPP)

Each shared resource is assigned the priority of the highest priority task that uses it. When a task is allowed to access a shared resource, it will inherit its priority. This means that when a task starts using a resource, it is guaranteed to be uninterrupted until it is done with the resource. Minimize the time a resource is locked.

Original ceiling priority protocol (OCPP)

A task inherits the priority of a resource ONLY if it blocks a higher priority task. A task can only access a shared resource if its priority is higher than the priority of all locked resources. Does not need to know the priority of the tasks in advance.

ICCP is easier to implement than OCPP, which has to keep track of what is blocking what. ICCP leads to less context switches as blocking is prior to first execution. ICPP requires more priority movements as this happens with all resource usage. OCPP changes priority only if an actual block has occurred.

Deadline monotonic priority

Rate monotonic is not suitable when deadline is shorter than period (D < T). Not the same as EDF, as priorities are still static. Same as rate monotonic when D = T.

Adding block time to response time analysis

The usage function: 1 for shared resources that are used by lower and higher (than i) priority tasks. 0 for others. $R_i = C_i + B_i + I_i$

Scheduling aperiodic tasks

Deadline monotonic is suitable for sporadic tasks. In a rate/deadline monotonic scheme, an aperiodic task could be given the lowest priority (suffer from starvation). For better response of aperiodic tasks, we use Execution-time servers which maintain a budget for clients. An Execution-time server runs as one task / process (periodic or sporadic) in the system. It can be included in a response time analysis modeled as such a task.

Periodic/Polling server

Each period the computation time budget is available for any pending clients – if a client needs more, it will continue next period. If one or more clients are pending, they will be scheduled within the server. The budget has to be used when the server is running or it is wasted.

Defferable server

Only lose budget when used. Better response time for aperiodic tasks. Back-to-back, where one budget is used just after another.

Sporadic server

Budget is replenished one-time period after it has started to be used.

Finding worst case execution time

Highest theoretical value, actual value (impossible to get), worst execution time found when testing x number of times

From book

• No actual tasks exist at run-time; each minor cycle is just a sequence of procedure calls

  • Task based scheduling – tasks exist at run time

• Earliest deadline first – the absolute deadlines are computed at run time and hence the scheme is described as dynamic

QNX microkernel

• A microkernel is an operating system kernel that only contain what has to run in kernel mode. (Scheduling, memory management and inter-process communication (IPC).

• There is no “kernel process”, the CPU executes code in the kernel only when an explicit kernel call is made, an exception is raised or to response to a hardware interrupt. All based around ICP.

Fundamental services in QNX

• Thread services via POSIX thread-creation primitives

• Signal services via POSIX signal primitives

• Message-passing services – the microkernel handles the routing of all messages between all threads throughout the entire system

• Synchronization services via POSIX thread-synchronization

• Scheduling services – the microkernel schedules threads for execution using the various POSIX real-time scheduling policies.

• Timer services – the microkernel provides the rich set of POSIX timer services

• Process management services – managing processes, memory and the pathname space

• POSIX – portable operating system interface

• To make compatibility between operating systems easier

• Defines the API (application programming interface) between user and programs and the kernel

• QNX is POSIX certified, but non-UNIX

QNX is suitable for real-time and embedded because

• QNX is scalable – possible to make very small/large

• Microkernel is in general suitable for real-time applications

  • No large non-preemptive kernel processes

  • Only very short periods that a process is in a non-preemptive kernel state (entry and exit)

• Scheduling – highest priority process will run. Priority inheritance. Sporadic server

• Built in inter-process communication

QNX is not open source – very expensive

Threads and processes

• A thread is the unit of scheduling – QNX schedules threads, not processes

• A process is a container for threads, each process must have at least one thread and it also contains address space, etc.

• Huge thread model – but most are variants of blocked state

Scheduling

• One ready queue for each priority level

  • 256 priorities, 0 is idle, 64-255 is root-only priorities, rest is configurable

• Scheduling is performed when:

  • The running thread is blocked since it has to wait for some event. When unblocked it is placed on the end of its ready queue

  • The running thread is preempted due to a higher priority thread that becomes ready. The preempted thread is placed in the front of its ready queue.

  • The running thread voluntarily yields the processor, and is placed in the end of its ready queue. The scheduler selects the next thread, which can be the one that just yielded.

  • Scheduling methods – FIFO, round robin, sporadic server

Sporadic server

• Is in QNX implemented as a thread that will keep its normal priority for as long as it is within its budget. When budget is exceeded, the priority will drop to a low level until the budget is replenished

Interrupts

• low latencies, because interrupts are enabled almost all of the time (only certain critical code sections requires interrupt to be disabled). QNX supports nested interrupts.

Message passing

• Things that typically are implemented in the kernel are instead implemented as user-space processes.

• The primary inter-process communication mechanism in QNX is message passing

  • One process creates a channel. When another process attaches to the channel, they can exchange messages

• Synchronous message passing

  • Client communication – MsgSend() gets SEND blocked, unless server is already RECEIVE blocked  gets REPLY blocked when server receives message  get READY when server MsgReply()

  • Server communication – MsgReceive() when ready to reply to clients  get RECEIVE blocked, unless client is already SEND blocked  get READY when client does MsgSend()  send MsgReply() which will not block, since client is already synced

• Message passing has priority inheritance

  • Server receives a message from a high priority client – server inherits the (higher) priority when the client sends the message

  • Server receives a message from a low priority client – server inherits the (lower) priority when the server receives the message

Processes share memory – protected by MUTEX etc.

QNX process manager (procnto) is required for all run-time system

• User process, not in kernel mode

• Provides process management, manages process creation, destruction and process attributes such as user ID and group ID. Manages a range of memory-protection capabilities, shared libraries and inter-process POSIX shared-memory primitives

Memory management

– provides protection unlike many other RTOS (choose not to because of large overhead)

• The overhead is less of a problem than the advantages it provides – adds robustness, threads that try to access memory which it is not allowed to access can be killed. Mitigates problems caused by accidental overwriting some memory location, which is typically very difficult to debug

QNX Qnet

• Used for accessing remote file systems, scale applications and extend applications from a single machine to several machines and distribute processes among those CPUs

• Qnet file system is shared between Qnet nodes. Resources and IPC mechanisms are available on the file system, is available for other nodes. Includes message passing, named semaphores, signals and message passing queues.

Memory management

• Originally no memory protection – all tasks share memory. Convenient for communication between tasks, but on task can overwrite the memory of another

• Newest version has memory management

• Newer versions also have real-time process (RTP) - similar to process. Task is similar to thread. Like QNX, all tasks are scheduled independently by the kernel

• Non-overlapped memory model – all virtual addresses in the system are unique – allow the same system to work with memory management units (MMU) in the CPU enabled or disabled

Kernel

• Earlier versions were running on top of 3rd party kernels (VRTX or pSOS) – Wind River systems developed their own “Wind Kernel”

• Older versions were running in “kernel mode” and had access to all memory

• In newer versions, there is both user and kernel mode, and memory protection (more microkernel in the right sense of the term)

Task model

• Consists of states ready, suspended, delayed, pended. Tasks can be in more than one state at a time