Implementation Methods

There are 2 different approaches to implement real time in Linux:

 One approach is to combine Linux with an RTOS and a software layer that delegates all the real-time work to the real-time OS and the non-time-critical work to Linux. Sometimes the RTOS is implemented in hardware (for example in an FPGA).

 Another approach is to make changes directly in the existing kernel.

Scheduling in RT linux

Initially RTLinux has a quite primitive, preemptive and fixed priority scheduler which does not have protection against impossible schedules (may lead to starvation). Therefor we think that the programmer has to be sure not to put the OS in starvation and not to schedule more processes than the CPU can handle to still manage to complete them in time. And it's much harder for the programmer to know whether the tasks will be executed before deadline or not. If the OS is going to run in a very time critical environment it will probably be desired, if not also needed, to use a more fancy scheduling algorithm. We think the possibility to use the more complex algorithms rate-monotonic scheduling or EDF scheduling makes RTLinux much more useful. If you need to be totally sure that deadlines are met you can use EDF scheduling or, if your processes are periodic, you can use rate-monotonic scheduling and calculate how low your CPU utilization.

1. Rate-Monotonic : 

The most commonly used static scheduling algorithm is the Rate Monotonic(RM) scheduling algorithm.The RM algorithm assigns different priorities proportional to the frequency of tasks.The task with the shortest period gets the highest priority, and the task with the longest period gets the lowest static priority.Rate monotonic algorithm is a dynamic preemptive algorithm based on static prioritiesRM algorithm provides no support for dynamically changing task periods and/or priorities and tasks that may experience priority inversion.A static priority scheduler for periodic tasks where the task with the smallest period is assigned the highest priority. This is provably the optimal policy.

Priority inversion occurs in an RM system where in order to enforce rate monotonicity, a non-critical task with a high frequency of execution is assigned a higher priority than a critical task with lower frequency of execution. A priority ceiling protocol (PCP) can be used to counter priority inversion, wherein a task blocking a higher priority task inherits the higher priority for the duration of the blocked task. The priority ceiling protocol is used to schedule a set dependant periodic tasks that share resources protected by semaphores.

2.Earliest deadline first :

A dynamic priority scheduler in which the task with the nearest deadline is scheduled.Earliest deadline first (EDF) scheduling can be used for both static and dynamic real-time scheduling.A dynamic priority algorithm which uses the deadline of a task as its priority.The task with the earliest deadline has the highest priority A variant of EDF is Minimum Laxity First (MLF) scheduling where a laxity is assigned to each task in the system and minimum laxity tasks are executed first. 

Laxity : The difference between the time until a tasks completion deadline and its remaining processing time requirement.

File Processes

A program/file in the execution is called a Process. Process is not the same as program. A process is more than a program code. A process is an 'active' entity as opposed to program which is considered to be a 'passive' entity. Attributes held by process include hardware state, memory, CPU etc.

Process memory is divided into four sections for efficient working :

• The text section is made up of the compiled program code, read in from non-volatile storage when the program is launched.
• The data section is made up the global and static variables, allocated and initialized prior to executing the main.
• The heap is used for the dynamic memory allocation, and is managed via calls to new, delete, malloc, free, etc.
• The stack is used for local variables. Space on the stack is reserved for local variables when they are declared.

fig. File Processing

Processes can be any of the following states :

• New - The process is in the stage of being created.
• Ready - The process has all the resources available that it needs to run, but the CPU is not currently working on this process's instructions.
• Running - The CPU is working on this process's instructions.
• Waiting - The process cannot run at the moment, because it is waiting for some resource to become available or for some event to occur.
• Terminated - The process has completed.

File System

A file can be "free formed", indexed or structured collection of related bytes having meaning only to the one who created it. Or in other words an entry in a directory is the file. The file may have attributes like name, creator, date, type, permissions etc.

File Structure

A file has various kinds of structure. Some of them can be :

• Simple Record Structure with lines of fixed or variable lengths.
• Complex Structures like formatted document or reloadable load files.
• No Definite Structure like sequence of words and bytes etc.

Attributes of a File

Following are some of the attributes of a file :

• Name . It is the only information which is in human-readable form.
• Identifier. The file is identified by a unique tag(number) within file system.
• Type. It is needed for systems that support different types of files.
• Location. Pointer to file location on device.
• Size. The current size of the file.
• Protection. This controls and assigns the power of reading, writing, executing.
• Time, date, and user identification. This is the data for protection, security, and usage monitoring.

File Access Methods

The way that files are accessed and read into memory is determined by Access methods. Usually a single access method is supported by systems while there are OS's that support multiple access methods.

Sequential Access

• Data is accessed one record right after another is an order.
• Read command cause a pointer to be moved ahead by one.
• Write command allocate space for the record and move the pointer to the new End Of File.
• Such a method is reasonable for tape.

Direct Access

• This method is useful for disks.
• The file is viewed as a numbered sequence of blocks or records.
• There are no restrictions on which blocks are read/written, it can be dobe in any order.
• User now says "read n" rather than "read next".
• "n" is a number relative to the beginning of file, not relative to an absolute physical disk location.

Indexed Sequential Access

• It is built on top of Sequential access.
• It uses an Index to control the pointer while accessing files.

RTLinux Internal Architecture :

RTOS comprises only a Kernel. For a complex embedded system, an RTOS can be combination of various modules, including the Kernel, networking protocol stacks, and other components.Standard time sharing OS and hard real time executive running on same machine. Kernel provided with the emulation of Interrupt control H/W. RT tasks run at kernel privilege level to provide direct H/W access. Rt linux runs Linux kernel for booting , device drivers ,networking, FS, process control and loadable kernel modules. Linux kernel runs as a low priority task on the RT kernel hence making sure it cannot preempt any RT task.

The RT kernel is actually patched over the Linux kernel and then recompiled to work as rtlinux system.The real-time operating system, another key component of a data-acquisition system is the device driver that controls the digitizing hardware.RT tasks cannot use Linux system calls , directly call routines or access ordinary data structures in Linux Kernel.There are two ways to install a real-time Linux system. First, you can purchase a pre-configured embedded Linux distribution,RT task allocated fixed memory for data and code Therefore RT Processes without memory location features. 

     VM layer only emulates the Interrupt Control.The 0 level OS does not provide any basic services that can be provided by Linux i.e only RT services, No primitives for process creation, switching or MM.Uses software stack for switching and not the expensive H/W switching. RT kernel is not preemptable

RTOS block diagram

 How does Real-time Linux work?

 The general idea of Real-time (RT) Linux is that a small real-time kernel runs beneath Linux, meaning that the real-time kernel has a higher priority than the Linux kernel. 
Real-time tasks are executed by the real-time kernel, and normal Linux programs are allowed to run when no real-time tasks have to be executed. 
Linux can be considered as the idle task of the real-time scheduler. When this idle task runs, it executes its own scheduler and schedules the normal Linux processes. 
Since the real-time kernel has a higher priority, a normal Linux process is preempted when a real-time task becomes ready to run and the real-time task is executed immediately.

 How is the real-time kernel given higher priority than Linux kernel?

 RT Linux uses the flow of interrupts to give the real-time kernel a higher priority than the Linux kernel:

• When an interrupt arrives, it is first given to the real-time kernel, and not to the Linux kernel. But interrupts are stored to give them later to Linux when the real-time kernel has finished.

• As first in row, the real-time kernel can run its real-time tasks driven by these interrupts.

• Only when the real-time kernel is not running anything, the interrupts which were stored are passed on to the Linux kernel.

• As second in row, Linux can schedule its own processes driven by these interrupt.

  

what is RTlinux?


System that has to perform its functions by responding to synchronous or asynchronous events within a specified amount of time.RTLinux is not an operating system by itself, but rather an extension to already available Linux distributions,which adds real-time functionality. The real-time operating system application which RTLinux adds is called RTCore. RTCore takes over interrupt control from the client Linux OS and has its own real-time scheduler.Though, the client Linux OS still has it's own scheduler and schedules it's own processes. This means that the client Linux OS doesn't know about RTCore and can't preempt it.

Why RT linux?

The reasons for the design of RTLinux can be understood by examining the working of the standard Linux kernel. The Linux kernel separates the hardware from the user-level tasks. The kernel uses scheduling algorithms and assigns priority to each task for providing good average performances or throughput.Thus the kernel has the ability to suspend any user-level task, once that task has the time-slice allotted to it by the CPU. This scheduling algorithms along with device drivers, uninterruptible system calls, the use of interrupt disabling and virtual memory operations are sources of unpredictability. That is to say, these sources cause hindrance to the realtime performance of a task. You might already be familiar with the non-realtime performance, say, when you are listening to the music played using 'mpg123' or any other player. 

After executing this process for a pre-determined time-slice, the standard Linux kernel could preempt the task and give the CPU to another one (e.g. one that boots up the X server or Netscape). Consequently, the continuity of the music is lost. Thus, in trying to ensure fair distribution of CPU time among all processes, the kernel can prevent other events from occurring. A realtime kernel should be able to guarantee the timing requirements of the processes under it. The RTLinux kernel accomplishes realtime performances by removing such sources of unpredictability as discussed above. We can consider the RTLinux kernel as sitting between the standard Linux kernel and the hardware. The Linux kernel sees the realtime layer as the actual hardware. Now, the user can both introduce and set priorities to each and every task. 

The user can achieve correct timing for the processes by deciding on the scheduling algorithms, priorities, frequency of execution etc. The RTLinux kernel assigns lowest priority to the standard Linux kernel. Thus the user-task will be executed in realtime. The actual realtime performance is obtained by intercepting all hardware interrupts. Only for those interrupts that are related to the RTLinux, the appropriate interrupt service routine is run. All other interrupts are held and passed to the Linux kernel as software interrupts when the RTLinux kernel is idle and then the standard Linux kernel runs. The RTLinux executive is itself nonpreemptible. Realtime tasks are privileged (that is, they have direct access to hardware), and they do not use virtual memory. Realtime tasks are written as special Linux modules that can be dynamically loaded into memory. The initialization code for a realtime tasks initializes the realtime task structure and informs RTLinux kernel of its deadline, period, and release-time constraints. RTLinux co-exists along with the Linux kernel since it leaves the Linux kernel untouched. Via a set of relatively simple modifications, it manages to convert the existing Linux kernel into a hard realtime environment without hindering future Linux development.

What is real-time operating system (RTOS)?

A real-time operating system (RTOS) is an operating system (OS) intended to serve real-time application process data as it comes in, typically without buffering delays.

A common example of an RTOS application is an HDTV receiver and display. It needs to read a digital signal, decode it and display it as the data comes in. 

Who need real-time operating system?

In many cases, there is little argument. When designing a flight control system, medical instrument, or process control application, for example, most system designers will choose an RTOS, simply because these systems must meet absolute deadlines.

Types of real time operating system -

1. Vx Works:

 VxWorks is a real-time operating system (RTOS) that can be used in embedded systems. VxWorks can be customized easily and can run on most processors designed for distributed computing. VxWorks is used to control network and communication devices, test and measurement equipment, computer peripherals, automotive systems, avionics (aeronautics and astronautics) equipment and diverse consumer products.

2. RT linux : 

RTLinux is a hard real time RTOS micro-kernel that runs the entire Linux operating system as a fully preemptive process. The hard real-time property makes it possible to control robots, data acquisition systems, manufacturing plants, and other time-sensitive instruments and machines from RTLinux applications.

3.MU linux :

The name muLinux comes from the Greek letter mu which is the SI symbol meaning one millionth, harking to the very small size of this OS. muLinux was based on the Linux 2.0.36 kernel.Development was frozen in 2004 at version 14r0, with some of the code and packages taken from software releases going back to 1998 (owing only to their smaller sizes). An experimental, unstable version called Lepton had the 2.4 kernel.