Real Time Operating Systems

REAL TIME OPERATING SYSTEMS

Process Concepts

·        A process consists of executable program (codes), state of which is controlled by OS, the state during running of a process represented by process-status (running, blocked, or finished), process structure—its data, objects and resources, and process control block (PCB).

·        Runs when it is scheduled to run by the OS (kernel)

·        OS gives the control of the CPU on a process‘s request (system call).

·        Runs by executing the instructions and the continuous changes of its state takes

Place as the program counter (PC) changes.

 •        Process is that executing unit of computation, which is controlled by some process (of the OS) for a scheduling mechanism that lets it execute on the CPU and by some 

process at OS for a resource management mechanism that lets it use the system-memory and other system resources such as network, file, display or printer.

Application program can be said to consist of number of processes

Example - Mobile Phone Device embedded software

·          Software highly complex.

·          Number of functions, ISRs, processes threads, multiple physical and virtual device drivers, and several program objects that must be concurrently processed on a single processor.

·          Voice encoding and convoluting process─ the device captures the spoken words through a speaker and generates the digital signals after analog to digital conversion, the digits are encoded and convoluted using a CODEC,

·        Modulating process,

·        Display process,

·        GUIs (graphic user interfaces), and

·        Key input process ─ for provisioning of the user interrupts

Process Control Block

·        A data structure having the information using which the OS controls the Process state.

·        Stores in protected memory area of the kernel.

·        Consists of the information about the process state

Information about the process state at Process Control Block…

·        Process ID,

·        process priority,

·        parent process (if any),

·        child process (if any), and

·        address to the next process PCB which will run,

·        allocated program memory address blocks in physical memory and in secondary (virtual) memory for the process-codes,

·        allocated process-specific data address blocks

·        allocated process-heap (data generated during the program run) addresses,

·        allocated process-stack addresses for the functions called during running of the process,

·        allocated addresses of CPU register-save area as a process context represents by CPU registers, which include the program counter and stack pointer

·        allocated addresses of CPU register-save area as a process context [Register-contents (define process context) include the program counter and stack pointer contents]

·        process-state signal mask [when mask is set to 0 (active) the process is inhibited from running and when reset to 1, the process is allowed to run],

·        Signals (messages) dispatch table [process IPC functions],

·        OS allocated resources‘ descriptors (for example, file descriptors for open files, device descriptors for open (accessible) devices, device-buffer addresses and status, socket-descriptor for open socket), and

·        Security restrictions and permissions.

Context

·        Context loads into the CPU registers from memory when process starts running, and the registers save at the addresses of register-save area on the context switch to another process

·        The present CPU registers, which include program counter and stack pointer are called context

·        When context saves on the PCB pointed process-stack and register-save area addresses, then the running process stops.

·        Other process context now loads and that process runs─ This means that the context has switched.

Threads and Tasks

Thread Concepts

·          A thread consists of executable program (codes), state of which is controlled by OS,

·        The state information─ thread-status (running, blocked, or finished), thread structure—its data, objects and a subset of the process resources, and thread-stack. Considered a lightweight process and a process level controlled entity.[Light weight means its running does not depend on system resources] .

Process… heavyweight

•         Process considered as a heavyweight process and a kernel-level controlled entity.

•         Process thus can have codes in secondary memory from which the pages can be swapped into the physical primary memory during running of the process. [Heavy weight means its running may depend on system resources]

•         May have process structure with the virtual memory map, file descriptors, user–ID, etc.

•         Can have multiple threads, which share the process structure thread

•         A process or sub-process within a process that has its own program counter, its own stack pointer and stack, its own priority parameter for its scheduling by a thread scheduler

•           Its‘ variables that load into the processor registers on context switching.

•           Has own signal mask at the kernel. Thread‘s signal mask

•         When unmasked lets the thread activate and run.

•         When masked, the thread is put into a queue of pending threads.

Thread‘s Stack

A thread stack is at a memory address block allocated by the OS.

Application program can be said to consist of number of threads or Processes:

Multiprocessing OS

•           A multiprocessing OS runs more than one processes.

•           When a process consists of multiple threads, it is called multithreaded process.

•         A thread can be considered as daughter process.

•         A thread defines a minimum unit of a multithreaded process that an OS schedules onto the CPU and allocates other system resources.

Thread parameters

•         Each thread has independent parameters ID, priority, program counter, stack pointer, CPU registers and its present status.

•         Thread states─ starting, running, blocked (sleep) and finished

Thread’s stack

•         When a function in a thread in OS is called, the calling function state is placed on the stack top.

•         When there is return the calling function takes the state information from the stack top

•         A data structure having the information using which the OS controls the thread state.

•         Stores in protected memory area of the kernel.

•         Consists of the information about the thread state

Thread and Task

•         Thread is a concept used in Java or Unix.

•         A thread can either be a sub-process within a process or a process within an application program.

•         To schedule the multiple processes, there is the concept of forming thread groups and thread libraries.

•         A task is a process and the OS does the multitasking.

•         Task is a kernel-controlled entity while thread is a process-controlled entity.

•         A thread does not call another thread to run. A task also does not directly call another task to run.

•         Multithreading needs a thread-scheduler. Multitasking also needs a task-scheduler.

•           There may or may not be task groups and task libraries in a given OS

Task and Task States

Task Concepts

•         An application program can also be said to be a program consisting of the tasks and task behaviors in various states that are controlled by OS.

•         A task is like a process or thread in an OS.

•         Task─ term used for the process in the RTOSes for the embedded systems. For example, VxWorks and μCOS-II are the RTOSes, which use the term task.

•           A task consists of executable program (codes), state of which is controlled by

OS, the state during running of a task represented by information of process status (running, blocked, or finished),process-structure—its data, objects and resources, and task control block (PCB).

•         Runs when it is scheduled to run by the OS (kernel), which gives the control of the CPU on a task request (system call) or a message.

•         Runs by executing the instructions and the continuous changes of its state takes place as the program counter (PC) changes.

•         Task is that executing unit of computation, which is controlled by some process at the OS scheduling mechanism, which lets it execute on the CPU and by some process at OS for a resource-management mechanism that lets it use the system memory and other system-resources such as network, file, display or printer.

•         A task─ an independent process.

•         No task can call another task. [It is unlike a C (or C++) function, which can call another function.]

•         The task─ can send signal (s) or message(s) that can let another task run.

•         The OS can only block a running task and let another task gain access of CPU to run the servicing codes

Task States

(i) Idle state [Not attached or not registered]

(ii) Ready State [Attached or registered]

(iii) Running state

(iv)Blocked (waiting) state

(v) Delayed for a preset period

Idle (created) state

The task has been created and memory allotted to its structure however, it is not ready and is not schedulable by kernel.

Ready (Active) State

•         The created task is ready and is schedulable by the kernel but not running at present as another higher priority task is scheduled to run and gets the system resources at this instance.

Running state

•       Executing the codes and getting the system resources at this instance. It will run till it needs some IPC (input) or wait for an event or till it gets pre-empted by another higher priority task than this one.

•

Blocked (waiting) state

•   Execution of task codes suspends after saving the needed parameters into its Context. It needs some IPC (input) or it needs to wait for an event or wait for higher

priority task to block to enable running after blocking.

Deleted (finished) state

•       Deleted Task─ The created task has memory deallotted to its structure. It frees the memory. Task has to be re-created.

Function

•       Function is an entity used in any program, function, task or thread for performing specific set of actions when called and on finishing the action the control returns to the function calling entity (a calling function or task or process or thread).

•       Each function has an ID (name)

•       has program counter and

•       has its stack, which saves when it calls another function and the stack restores on return to the caller.

•         Functions can be nested. One function call another, that can call another, and so on and later the return is in reverse order

Memory Management Functions

Memory allocation

·        when a process is created, the memory manager allocates the memory addresses (blocks) to it by mapping the process address space.

·        Threads of a process share the memory space of the process

·        Memory manager of the OS─ secure, robust and well protected.

·        No memory leaks and stack overflows

·        Memory leaks means attempts to write in the memory block not allocated to a process or data structure.

·        Stack overflow means that the stack exceeding the allocated memory block(s)

Memory Management after Initial Allocation

Memory Managing Strategy for a system

·        Fixed-blocks allocation

·        Dynamic -blocks Allocation

·        Dynamic Page-Allocation

·        Dynamic Data memory Allocation

·        Dynamic address-relocation

·        Multiprocessor Memory Allocation

·        Memory Protection to OS functions

Memory allocation in RTOSes

·        RTOS may disable the support to the dynamic block allocation, MMU support to dynamic page allocation and dynamic binding as this increases the latency of servicing the tasks and ISRs.

·        RTOS may not support to memory protection of the OS functions, as this increases the latency of servicing the tasks and ISRs.

·        User functions are then can run in kernel space and run like kernel functions

·        RTOS may provide for disabling of the support to memory protection among the tasks as this increases the memory requirement for each task

Memory Manager functions

(i) use of memory address space by a process,

(ii) specific mechanisms to share the memory space and

(iii) specific mechanisms to restrict sharing of a given memory space

(iv)optimization of the access periods of a memory by using an hierarchy of memory (caches, primary and external secondary magnetic and optical memories).

Remember that the access periods are in the following increasing order: caches, primary and external secondary magnetic and then or optical.

Fragmentation Memory Allocation Problems

Fragmented not continuous memory addresses in two blocks of a process

·        Time is spent in first locating next free memory address before allocating that to the process.

·        A standard memory allocation scheme is to scan a linked list of indeterminate length to find a suitable free memory block.

·        When one allotted block of memory is deallocated, the time is spent in first locating next allocated memory block before deallocating that to the process.

·        the time for allocation and de-allocation of the memory and blocks are variable (not deterministic) when the block sizes are variable and when the memory is fragmented.

·        In RTOS, this leads to unpredicatble task performance

Memory management Example

RTOS COS-II

·        Memory partitioning

·        A task must create a memory partition or several memory partitions by using function OSMemCreate ( )

·        Then the task is permitted to use the partition or partitions.

·        A partition has several memory blocks.

·        Task consists of several fixed size memory blocks.

·        The fixed size memory blocks allocation and de-allocation time takes fixed time (deterministic).

·        OSMemGet ( )

─ to provide a task a memory block or blocks from the partition

·        OSMemPut ( )

─ to release a memory block or blocks to the partition

Interrupt Service routine

•         ISR is a function called on an interrupt from an interrupting source.

•         Further unlike a function, the ISR can have hardware and software assigned priorities.

•         Further unlike a function, the ISR can have mask, which inhibits execution on the event, when mask is set and enables execution when mask reset.

Task

•         Task defined as an executing computational unit that processes on a CPU and state of which is under the control of kernel of an operating system.

Distinction Between Function, ISR and Task

Uses

•         Function─ for running specific set of codes for performing a specific set of actions as per the arguments passed to it

•         ISR─ for running on an event specific set of codes for performing a specific set of actions for servicing the interrupt call.

•         Task ─ for running codes on context switching to it by OS and the codes can be in endless loop for the event (s)

Calling Source

•         Function─ call from another function or process or thread or task.

•         ISR─ interrupt-call for running an ISR can be from hardware or software at any Instance.

•         Task ─ A call to run the task is from the system (RTOS). RTOS can let another higher priority task execute after blocking the present one. It is the RTOS (kernel) only that controls the task scheduling.

Context Saving

•         Function─ run by change in program counter instantaneous value. There is a stack. On the top of which the program counter value (for the code left without running) and other values (called functions‘ context) save.

•         All function have a common stack in order to support the nesting

•         ISR─ Each ISR is an event-driven function code. The code run by change in program counters instantaneous value. ISR has a stack for the program counter instantaneous value and other values that must save.

•         All ISRs can have common stack in case the OS supports nesting

•         Task ─ Each task has a distinct task stack at distinct memory block for the context (program counter instantaneous value and other CPU register values in task control block) that must save .

•         Each task has a distinct process structure (TCB) for it at distinct memory block

Response and Synchronization

•         Function─ nesting of one another, a hardware mechanism for sequential nested mode synchronization between the functions directly without control of scheduler or OS

•         ISR─ a hardware mechanism for responding to an interrupt for the interrupt source calls, according to the given OS kernel feature a synchronizing mechanism for the ISRs, and that can be nesting support by the OS.

•         ISR─ a hardware mechanism for responding to an interrupt for the interrupt source calls, according to the given OS kernel feature a synchronizing mechanism for the ISRs,and that can be nesting support by the OS

Structure

•         Function─ can be the subunit of a process or thread or task or ISR or subunit of another function.

•         ISR─ Can be considered as a function, which runs on an event at the interrupting source.

•         A pending interrupt is scheduled to run using an interrupt handling mechanism in the OS, the mechanism can be priority based scheduling.

•         The system, during running of an ISR, can let another higher priority ISR run.

•         Task ─ is independent and can be considered as a function, which is called to run by the OS scheduler using a context switching and task scheduling mechanism of the OS.

•         The system, during running of a task, can let another higher priority task run. The kernel manages the tasks scheduling

Global Variables Use

•         Function─ can change the global variables. The interrupts must be disabled and after finishing use of global variable the interrupts are enabled.

•         ISR─ When using a global variable in it, the interrupts must be disabled and after finishing use of global variable the interrupts are enabled (analogous to case of a function).

•         Task ─ When using a global variable, either the interrupts are disabled and after finishing use of global variable the interrupts are enabled or use of the semaphores or lock functions in critical sections, which can use global variables and memory buffers.

Posting and Sending Parameters

•         Function─ can get the parameters and messages through the arguments passed to it or global variables the references to which are made by it. Function returns the results of the Operations.

•         ISR─ using IPC functions can send (post) the signals, tokens or messages. ISR can‘t use the mutex protection of the critical sections by wait for the signals, tokens or messages.

•         Task ─ can send (post) the signals and messages.

•         can wait for the signals and messages using the IPC functions, can use the mutex or lock protection of the code section by wait for the token or lock at the section beginning and messages and post the token or unlock at the section end.

Semaphore as an event signalling variable or notifying variable

•         Suppose that there are two trains.

•         Assume that they use an identical track.

•         When the first train A is to start on the track, a signal or token for A is set (true, taken) and

•         same signal or token for other train, B is reset (false, not released).

OS Functions for Semaphore as an event signalling variable or notifying variable:

•                     OS Functions provide for the use of a semaphore for signalling or notifying of certain action or notifying the acceptance of the notice or signal.

•                     Let a binary Boolean variable, s, represents the semaphore. The taken and post operations on s─ (i)signals or notifies operations for communicating the occurrence of an event and (ii) for communicating taking note of the event.

•                     Notifying variable s is like a token ─ (i) acceptance of the token is taking note of that event (ii) Release of a token is the occurrence of an event

Binary Semaphore

•         Let the token (flag for event occurrence) s initial value = 0

•         Assume that the s increments from 0 to 1 for signalling or notifying occurrence of an event from a section of codes in a task or thread.

•         When the event is taken note by section in another task waiting for that event, the s decrements from 1 to 0 and the waiting task codes start another action.

•         When s = 1─ assumed that it has been released (or sent or posted) and no task code section has taken it yet.

•         When s = 0 ─ assumed that it has been taken (or accepted) and other task code

•         section has not taken it yet

Binary Semaphore use in ISR and Task

•         An ISR can release a token.

•         A task can release the token as well accept the token or wait for taking the token

Device Management Functions

Number of device driver ISRs in a system,

Each device or device function having s a separate driver, which is as per its hardware

Software that manages the device drivers of each device

Provides and executes the modules for managing the devices and their drivers ISRs.

effectively operates and adopts appropriate strategy for obtaining optimal performance for the devices.

Coordinates between application-process, driver and device-controller.

Device manager

Process sends a request to the driver by an interrupt; and the driver provides the actions by executing an ISR.

Device manager polls the requests at the devices and the actions occur as per their priorities.

Manages IO Interrupts (requests) queues.

creates an appropriate kernel interface and API and that activates the control register specific actions of the device. [Activates device controller through the API and kernel interface.]

manages the physical as well as virtual devices like the pipes and sockets through a common strategy.

Device management has three standard approaches

Three types of device drivers:

(i) Programmed I/Os by polling from each device its the service need from each device.

(ii) Interrupt(s) from the device drivers‘ device- ISR and

(iii)Device uses DMA operation used by the devices to access the memory.

Most common is the use of device driver ISRs

Device Manager Functions

Device Detection and Addition Device Deletion

Device Allocation and Registration

Detaching and Deregistration

Restricting Device to a specific process Device Sharing

Device control

Device Access Management Device Buffer Management

Device Queue, Circular-queue or blocks of queues Management Device drivers updating and upload of new device-functions

Backup and restoration

Device Types

char devices and block devices

Set of Command Functions for the Device Management

Commands for Device

create open write read ioctl

close and delete

IO control Command for Device

(i) Accessing specific partition information

(ii) Defining commands and control functions of device registers

(iii) IO channel control

Three arguments in ioctl ( )

First Argument: Defines the chosen device and its function by passing as argument the device descriptor (a number), for example, fd or sfd Example is fd = 1 for read, fd = 2 for write.

Second Argument: Defines the control option or uses option for the IO device, for example, baud rate or other parameter optional function

Third Argument: Values needed by the defined function are at the third argument

Example

Status = ioctl (fd, FIOBAUDRATE, 19200) is an instruction in RTOS VxWorks. fd is the device descriptor (an integer returned when the device is opened)

FIOBAUDRATE is the function that takes value = 19200 from the argument. This at configures the device for operation at 19200-baud rate.

Device Driver ISR functions

ISR functions

intlock ( ) to disable device-interrupts systems, intUnlock ( ) to enable device-interrupts,

intConnect ( ) to connect a C function to an interrupt vector

Interrupt vector address for a device ISR points to its specified C function. intContext ( ) finds whether interrupt is called when an ISR was in execution

Unix OS functions

UNIX Device driver functions

Facilitates that for devices and files have an analogous implementation as far as possible.

open ( ), close ( ), read ( ),

write ( ) functions analogous to a file open,

close, read and write functions.

APIs and kernel interfaces in BSD (Berkley sockets for devices)

open, close, read write

in-kernel commands

(i)                select ( ) to check whther read/write will succeed and then select (ii) ioctl ( )

(iii) stop ( ) to cancel the output activity from the device.

(iv) strategy ( ) to permit a block read or write or character read or write

Round Robin Time Slicing of tasks of equal priorities

Common scheduling models

·        Cooperative Scheduling of ready tasks in a circular queue. It closely relates to function queue scheduling.

·        Cooperative Scheduling with Precedence Constraints

·        Cyclic scheduling of periodic tasks and Round Robin Time Slicing Scheduling of equal priority tasks

·        Preemptive Scheduling

·        Scheduling using 'Earliest Deadline First' (EDF) precedence.

Common scheduling models

·        Rate Monotonic Scheduling using ‗higher rate of events occurrence First‘ precedence

·        Fixed Times Scheduling

·        Scheduling of Periodic, sporadic and aperiodic Tasks

·        Advanced scheduling algorithms using the probabilistic Timed Petri nets (Stochastic) or Multi Thread Graph for the multiprocessors and complex distributed systems.

Round Robin Time Slice Scheduling of Equal Priority Tasks

Equal Priority Tasks

·        Round robin means that each ready task runs turn by in turn only in a cyclic queue for a limited time slice.

·          Widely used model in traditional OS.

·        Round robin is a hybrid model of clock-driven

·        model (for example cyclic model) as well as event driven (for example, preemptive)

·        A real time system responds to the event within a bound time limit and within an explicit time.

Tasks programs contexts at the five instances in the Time Scheduling Scheduler for C1 to C5

Programming model for the Cooperative Time sliced scheduling of the tasks

Program counter assignments on the scheduler call to tasks at two consecutive time slices. Each cycle takes time = N tslice

Case : Tcycle = N Tslice

·          Same for every task = Tcycle

·          Tcycle ={Tslice )}   N + tISR.

·          tISR is the sum of all execution times for the ISRs

·        For an i-th task, switching time from one task to another be is st and task execution time be is et

·          Number of tasks = N

Worst-case latency

·          Same for every task in the ready list

·          Tworst = {N   (Tslice)} + tISR.

·          tISR is the sum of all execution times for the ISRs

·          i = 1, 2, …, N   1 , N

VoIP Tasks Example

Assume a VoIP [Voice Over IP.] router.

·        It routes the packets to N destinations from N sources.

·        It has N calls to route.

·        Each of N tasks is allotted from a time slice and is cyclically executed for routing packet from a source to its destination

Round Robin

·          Case 1: Then each task is executed once and finishes in one cycle itself.

·        When a task finishes the execution before the maximum time it can takes, there is a waiting period in-between period between two cycles.

·        The worst-case latency for any task is then N_tslice. A task may periodically need execution. A task The period for the its need of required repeat execution of a task is an integral multiple of tslice.

Case 2: Alternative model strategy

·          Case 2: Certain tasks are executed more than once and do not finish in one cycle

·          Decomposition of a task that takes the abnormally long time to be executed.

·          The decomposition is into two or four or more tasks.

·        Then one set of tasks (or the odd numbered tasks) can run in one time slice, t'slice and the another set of tasks (or the even numbered tasks) in another time slice, t''slice.

Decomposition of the long time taking task into a number of sequential states

·        Decomposition of the long time taking task into a number of sequential states or a number of node-places and transitions as in finite state machine. (FSM).

·        Then its one of its states or transitions runs in the first cycle, the next state in the second cycle and so on.

·        This task then reduces the response times of the remaining tasks that are executed after a state change.