Concepts in Real Time Operating Systems - 3 | Embedded Systems (Web) - Computer Science Engineering (CSE) PDF Download

Self-Host Systems

Unlike the host-target approach where application development is carried out on a separate host system machine running traditional Unix, in self-host systems a real-time application is developed on the same system on which the real-time application would finally run. Of course, while deploying the application, the operating system modules that are not essential during task execution are excluded during deployment to minimize the size of the operating system in the embedded application. Remember that in host-target approach, the target real-time operating system was a lean and efficient system that could only run the application but did not include program development facilities; program development was carried out on the host system. This made application development and debugging difficult and required cross-compiler and cross-debugger support. Self-host approach takes a different approach where the real-time application is developed on the full-fledged operating system, and once the application runs satisfactorily it is fused on the target board on a ROM or flash memory along with a stripped down version of the same operating system.

Most of the self-host operating systems that are available now are based on micro-kernel architecture. Use of microkernel architecture for a self-host operating system entails several advantages. In microkernel architecture, only the core functionalities such as interrupt handling and process management are implemented as kernel routines. All other functionalities such as memory management, file management, device management, etc are implemented as add-on modules which operate in user mode. As a result, it becomes very easy to configure the operating system. Also, the micro kernel is lean and therefore becomes much more efficient. A monolithic operating system binds most drivers, file systems, and protocol stacks to the operating system kernel and all kernel processes share the same address space. Hence a single programming error in any of these components can cause a fatal kernel fault. In microkernel-based operating systems, these components run in separate memory-protected address spaces. So, system crashes on this count are very rare, and microkernel-based operating systems are very reliable.

We had discussed earlier that any Unix-based system has to overcome the following two main shortcomings of the traditional Unix kernel in order to be useful in hard real-time applications: non-preemptive kernel and dynamic priority values. We now examine how these problems are overcome in self-host systems.

Non-preemptive kernel: We had identified the genesis of the problem of non-preemptive Unix kernel in Sec.4.3.1. We had remarked that in order to preserve the integrity of the kernel data structures, all interrupts are disabled as long as a system call does not complete. This was done from efficiency considerations and worked well for non-real-time and uniprocessor applications.

Masking interrupts during kernel processing makes to even very small critical routines to have worst case response times of the order of a second. Further, this approach would not work in multiprocessor environments. In multiprocessor environments masking the interrupts for one processor does not help, as the tasks running on other processors can still corrupt the kernel data structure.

It is now clear that in order to make the kernel preemptive, locks must be used at appropriate places in the kernel code. In fully preemptive Unix systems, normally two types of locks are used: kernel-level locks, and spin locks.

Fig. 31.6 Operation of a Spin Lock

A kernel-level lock is similar to a traditional lock. When a task waits for a kernel level lock to be released, it is blocked and undergoes a context switch. It becomes ready only after the required lock is released by the holding task and becomes available. This type of locks is inefficient when critical resources are required for short durations of the order of a few milliseconds or less. In some situations such context switching overheads are not acceptable. Consider that some task requires the lock for carrying out very small processing (possibly a single arithmetic operation) on some critical resource.

Now, if a kernel level lock is used, another task requesting the lock at that time would be blocked and a context switch would be incurred, also the cache contents, pages of the task etc. may be swapped. Here a context switching time is comparable to the time for which a task needs a resource even greater than it. In such a situation, a spin lock would be appropriate. Now let us understand the operation of a spin lock. A spin lock has been schematically shown in Fig. 31.6. In Fig. 31.6, a critical resource is required by the tasks T₁ and T₂ for very short times (comparable to a context switching time). This resource is protected by a spin lock. The task T₁ has acquired the spin lock guarding the resource. Meanwhile, the task T₂ requests the resource. When task T₂ cannot get access to the resource, it just busy waits (shown as a loop in the figure) and does not block and suffer context switch. T₂ gets the resource as soon as T₁ relinquishes the resource.

Real-Time Priorities: Let us now examine how self-host systems address the problem of dynamic priority levels of the traditional Unix systems. In Unix based real-time operating systems, in addition to dynamic priorities, real-time and idle priorities are supported. Fig. 31.7 schematically shows the three available priority levels.

Fig. 31.7 Priority Changes in Self-host Unix Systems

Idle(Non-Migrating): This is the lowest priority. The task that runs when there are no other tasks to run (idle), runs at this level. Idle priorities are static and are not recomputed periodically.

Dynamic: Dynamic priorities are recomputed periodically to improve the average response time of soft real-time tasks. Dynamic re-computation of priorities ensures that I/O bound tasks migrate to higher priorities and CPU-bound tasks operate at lower priority levels. As shown in Fig. 31.7, dynamic priority levels are higher than the idle priority, but are lower than the real-time priorities.

Real-Time: Real-time priorities are static priorities and are not recomputed. Hard real-time tasks operate at these levels. Tasks having real-time priorities operate at higher priorities than the tasks with dynamic priority levels.

Windows As A Real-Time Operating System

Microsoft’s Windows operating systems are extremely popular in desktop computers. Windows operating systems have evolved over the years last twenty five years from the naive DOS (Disk Operating System). Microsoft developed DOS in the early eighties. Microsoft kept on announcing new versions of DOS almost every year and kept on adding new features to DOS in the successive versions. DOS evolved to the Windows operating systems, whose main distinguishing feature was a graphical front-end. As several new versions of Windows kept on appearing by way of upgrades, the Windows code was completely rewritten in 1998 to develop the Windows NT system. Since the code was completely rewritten, Windows NT system was much more stable (does not crash) than the earlier DOS-based systems. The later versions of Microsoft’s operating systems were descendants of the Windows NT; the DOS-based systems were scrapped. Fig. 31.8 shows the genealogy of the various operating systems from the Microsoft stable. Because stability is a major requirement for hard real-time applications, we consider only the Windows NT and its descendants in our study and do not include the DOS line of products.

Fig. 31.8 Genealogy of Operating Systems from Microsoft’s Stable

An organization owning Windows NT systems might be interested to use it for its real-time applications on account of either cost saving or convenience. This is especially true in prototype application development and also when only a limited number of deployments are required. In the following, we critically analyze the suitability of Windows NT for real-time application development. First, we highlight some features of Windows NT that are very relevant and useful to a real-time application developer. In the subsequent subsection, we point out some of the lacuna of Windows NT when used in real-time application development.

Features of Windows NT

Windows NT has several features which are very desirable for real-time applications such as support for multithreading, real-time priority levels, and timer. Moreover, the clock resolutions are sufficiently fine for most real-time applications.

Windows NT supports 32 priority levels (see Fig. 31.9). Each process belongs to one of the following priority classes: idle, normal, high, real-time. By default, the priority class at which an application runs is normal. Both normal and high are variable type where the priority is recomputed periodically. NT uses priority-driven pre- emptive scheduling and threads of real-time priorities have precedence over all other threads including kernel threads. Processes such as screen saver use priority class idle. NT lowers the priority of a task (belonging to variable type) if it used all of its last time slice. It raises the priority of a task if it blocked for I/O and could not use its last time slice in full. However, the change of a task from its base priority is restricted to ±2.

Fig. 31.9 Task Priorities in Windows NT

Shortcomings of Windows NT

In spite of the impressive support that Windows provides for real-time program development as discussed in Section 4.5.1, a programmer trying to use Windows in real-time system development has to cope up with several problems. Of these, the following two main problems are the most troublesome.

1. Interrupt Processing: Priority level of interrupts is always higher than that of the user-level threads; including the threads of real-time class. When an interrupt occurs, the handler routine saves the machine’s state and makes the system execute an Interrupt Service Routine (ISR). Only critical processing is performed in ISR and the bulk of the processing is done as a Deferred Procedure Call(DPC). DPCs for various interrupts are queued in the DPC queue in a FIFO manner. While this separation of ISR and DPC has the advantage of providing quick response to further interrupts, it has the disadvantage of maintaining the all DPCs at the same priorities.

A DPC can not be preempted by another DPC but by an interrupt. DPCs are executed in FIFO order at a priority lower than the hardware interrupt priorities but higher than the priority of the scheduler/dispatcher. Further, it is not possible for a user-level thread to execute at a priority higher than that of ISRs or DPCs. Therefore, even ISRs and DPCs corresponding to very low priority tasks can preempt real-time processes. Therefore, the potential blocking of real-time tasks due to DPCs can be large. For example, interrupts due to page faults generated by low priority tasks would get processed faster than real-time processes. Also, ISRs and DPCs generated due to key board and mouse interactions would operate at higher priority levels compared to real-time tasks. If there are processes doing network or disk I/O, the effect of system-wide FIFO queues may lead to unbounded response times for even real-time threads.

These problems have been avoided by Windows CE operating system through a priority inheritance mechanism.

2. Support for Resource Sharing Protocols: We had discussed in Chapter 3 that unless appropriate resource sharing protocols are used, tasks while accessing shared resources may suffer unbounded priority inversions leading to deadline misses and even system failure. Windows NT does not provide any support (such as priority inheritance, etc.) to support real-time tasks to share critical resource among themselves. This is a major shortcoming of Windows NT when used in real-time applications.
Since most real-time applications do involve resource sharing among tasks we outline below the possible ways in which user-level functionalities can be added to the Windows NT system.

The simplest approach to let real-time tasks share critical resources without unbounded priority inversions is as follows. As soon as a task is successful in locking a non-preemptable resource, its priority can be raised to the highest priority (31). As soon as a task releases the required resource, its priority is restored. However, we know that this arrangement would lead to large inheritance-related inversions.

Another possibility is to implement the priority ceiling protocol (PCP). To implement this protocol, we need to restrict the real-time tasks to have even priorities (i.e. 16, 18, ..., 30). The reason for this restriction is that NT does not support FIFO scheduling among equal priority tasks. If the highest priority among all tasks needing a resource is 2∗n, then the ceiling priority of the resource is 2∗n+1. In Unix, FIFO option among equal priority tasks is available; therefore all available priority levels can be used.

Windows vs Unix

Table 31.1 Windows NT versus Unix

Though Windows NT has many of the features desired of a real-time operating system, its implementation of DPCs together its lack of protocol support for resource sharing among equal priority tasks makes it unsuitable for use in safety-critical real-time applications. A comparison of the extent to which some of the basic features required for real-time programming are provided by Windows NT and Unix V is indicated in Table 1. With careful programming, Windows NT may be useful for applications that can tolerate occasional deadline misses, and have deadlines of the order of hundreds of milliseconds than microseconds. Of course, to be used in such applications, the processor utilization must be kept sufficiently low and priority inversion control must be provided at the user level.