Application Interface

The operating system provides a series of service calls that allow applications to interact with the kernel. In many cases application writers do not make direct system calls, but instead rely on a set of libraries that provide a broad range of services to applications. Some of these libraries depend on making kernel services calls, while others do not require any interaction with the kernel.

The C library is a good example. The C libraries are defined by the C Library Standard under ISO/IEC 9899:1999 (commonly referred to as C99). The library provides functions such as string manipulation and parsing, memory copy, memory allocation, print formatting, and file I/O. Functions such as string and memory copy do not require any operating services; however, malloc() and file I/O such as printf() do require the use of OS services. A C language application can perform many functions without resorting to using any OS service calls directly. The most common implementation of the C library on Linux systems is the GNU C Library (GLIBC). In addition to complying with C99, the library provides services compatible with POSIX.1c, POSIX.1j, POSIX.1d, and Unix98, Single Unix Specification.

Processes, Tasks, and Threads

An operating system defines a minimal execution context that can be scheduled. Depending on the operating system, they are called tasks or threads. In an RTOS, the system is normally composed exclusively of tasks. Each task contains task-specific context or state. All tasks are generally globally visible with relatively easy access to shared memory between tasks. The task view is flat across the operating system; the primary difference between tasks performing kernel type work and application work are the privilege and priority of the tasks. In recent versions of VxWorks a process concept was introduced in which tasks are assigned to a virtual memory context and do not have global visibility of memory. In the case of more general-purpose operating systems one or more threads are incorporated to execute under a user space process. Threads within a process share the same memory space, descriptors for access to system resources, and the like. In Linux, threads are created within a process through the fork system call, although in most cases programmers use the pthread library to create and manage threads. The kernel threads are not unlike the task equivalent in the VxWorks RTOS case; there is no protection mechanism between the kernel threads and they have access to the kernel memory map. Figure 7.3 shows examples of the differing configurations. In the case of threads created as part of a user space Linux process, the threads are similar to those found in the kernel, but they share the memory space, file descriptors, and signal handles of the process to which they are assigned.

FIGURE 7.3 Tasks, Threads, and Processes.

In both VxWorks and Linux the scheduling unit in the operating system is the task or thread.

In the case of VxWorks and many other real-time operating systems the task creation is explicitly under control of the application. An initial root task is created by the kernel. The kernel root task starts with the highest privileges. The root task subsequently creates a number of other task and then deletes itself (frees all resources associated with it). Each of the threads can create new threads using the taskOpen() function call. The taskOpen() function call takes the following arguments:

The function returns a TaskID number. This task ID can be used for many low-level control functions such as the task activation call taskActivate() or other control functions to change priority, task deletion, and the like. As you can see, the creation of a task in an RTOS offers considerable flexibility for the behavior of the task when it is created and subsequently once it exists.

The pattern above is quite common for operating systems; the equivalent call in the Linux kernel is kernel_thread(). The function takes a function pointer for the entry point to the thread, a number of arguments that are passed to the threads entry point, and a number of configuration flags to indicate what aspects of the system should be shared (such as memory space).

Scheduling

The scheduler in the operating system selects a task/thread from the available list of ready tasks and starts the execution of the task. A number of different scheduler types are used in operating systems with varying characteristics. We will discuss the simple scheduler, round-robin scheduler, preemptive priority scheduler, and completely fair scheduler.

Memory Allocation

All systems provide a mechanism to allocate memory to an application. Functions are provided to allocate and free memory from the system heap. In the case of the C language, the C language library provides the functions to manage the memory allocation. In this case the calls are malloc() and free().

An embedded system may support individual heaps per process, with separate maximum heap sizes assigned to each process. Other configurations have a single heap in the system, where all tasks may allocate from and free to. In the case of the process view, the memory allocation functions return a virtual address that is only valid for the process making the call. In a flat model, the memory allocated is globally visible. It is not uncommon for embedded applications to pass messages between tasks that contain pointers to memory that is allocated using malloc() calls. To access memory allocated by another task, the system must use a flat memory model or use special shared memory APIs to facilitate the sharing of allocated memory across tasks.

The memory allocation system has no prior knowledge of the sequence of memory allocations and frees that might be requested by applications. The allocator algorithms attempt to maximize the size of contiguous blocks within the heap over time to ensure that the heap does not get fragmented. A fragmented heap is one in which a significant amount of memory is free but the size of any contiguous section is small. In this case an application request to allocate memory can fail. Allocator algorithms can help significantly to reduce fragmentation. Figure 7.7 shows an example of how a heap may be fragmented through a series of allocation and free calls.

FIGURE 7.7 Fragmented Heap (Zebra Pattern).

To help achieve this many memory allocations, schemes partition the heap into a number of fixed-size pools and a single large variable-size pool as shown in Figure 7.8. The pools are often referred to as power of two pools, as the entry sizes increase with power of two (for example, 32, 64, 128 bytes).

FIGURE 7.8 Power of Two Heap.

When an application makes a request for a number of bytes, for example, 64 bytes, the allocator first attempts to allocate from the 64-byte pool. If that fails, it tries the next size pool, and so on. If allocation fails for all the fixed-size pools, then the allocator allocates from the variable-size heap. The number of fixed-size pools, the size of the entries in a pool, and the number of entries in each pool are configurable and should be tuned for your embedded application. In embedded applications it is very important to manage possible heap fragmentation. Embedded systems can remain running without restarting for very long periods of time (up to years). The mallopt() call in the C library can be used to tune the behavior of malloc/free.

Despite the techniques described here, over time the pattern of allocation and free may result in fragmentation of the variable-size heap. For embedded systems, it is best practice to pre-allocate all memory requirements for applications at the time of startup and subsequently manage the allocated memory in the form of memory pools. Many real-time operating systems provide APIs to create and manage such pools; it is strongly advised to use such techniques in embedded systems. The Linux kernel uses such techniques in the slab memory allocator.

Clocks and Timers

Timer and clock services are capabilities offered by an operating system. In embedded applications a task may need to issue a delay/sleep for a period of time or manage the generation of events at a particular rate. To facilitate such cases, the platform provides counters and timers. A timer is typically a hardware resource that generates an interrupt to the processor at a periodic rate. Counters are hardware resources that are clocked at a particular rate and can be read by the software to establish the amount of time that has passed.

All operating systems make use of at least one timer called the system tick. This timer is used to trigger timer callback functions and provide the time base to support time slicing of tasks by the OS scheduler.

Mutual Exclusion/Synchronization

In many cases it is critical to ensure serialized atomic access to resources such as data structures and/or physical device resources. There are many mechanisms to ensure mutually exclusive access to a resource. The first is to serialize access to the area where atomic updates must occur. An example of a critical section is when the execution context updates a counter in memory or performs pointer updates associated with insertion/removal of a node in a linked list.

When an execution context is performing the atomic update to a resource, it must prevent execution of any other context that might update the resource.

The simplest mechanism is to prevent the scheduling of any other execution context while the update is occurring. In many simple embedded systems, this was often carried out by disabling interrupts. This is not recommended, as it perturbs real-time behavior, interacts with device drivers, and may not work with multi-core systems. Disabling interrupts effectively prevents an operating system–triggered rescheduling of the task running in the critical section. The task must also avoid any system calls that would trigger execution of the OS scheduler. There may also be an operating system call to suspend scheduling of other tasks. Such mechanisms are blunt instruments to ensure mutual exclusion, as they may have a broad system wide impact. These techniques also do not work when being used by user- or de-privileged contexts such as a POSIX thread.

In many systems a hardware mechanism is provided to perform an atomic update in system memory. Processor architectures provide instructions to build mutual exclusion primitives such as Compare and Swap (CAS) and Compare and Exchange (CMPXCHG) in Intel Architecture and load-link/store-conditional instructions on PowerPC, ARM and MOPS architectures. These are sometimes referred to as atomic test and set operations. As an example, we describe how the CAS instruction can be used to perform an atomic update from two execution contexts. The CAS instruction compares the memory location with a given value. If the value at the memory location is the same as the given value, then the memory is updated with a new value given. Consider two execution contexts (A and B) attempting to update a counter: context A reads the current value, increments the current value by one to create the new value, then issues a CAS with the current and new values. If context B has not intervened, the update to the new value will occur, as the current value in memory is the same as the current value issued in the CAS. If, however, context B reads the same current value as context A and issues the CAS instruction before context A, then the update by context A would fail, as the value in memory is no longer the same as the current value issued in the CAS by context A. This collision can be detected because the CAS instruction returns the value of the memory; if the update fails then context A must try the loop again and will mostly likely succeed the second time. In the case described above, context A may be interrupted by an interrupt and context B may be run in the interrupt handler or from a different context scheduled by the operating system. Alternatively, the system has multiple CPUs where the other CPU is performing an update at exactly the same time.

Using a technique similar to the one described above, we can implement a construct known as a spin lock. A spin lock is where a thread waits to get a lock by repeatedly trying to get the lock. The calling context busy-waits until it acquires the lock. This mechanism works well when the time for which a context owns a lock is very small. However, care must be taken to avoid deadlock. For example, if a kernel task has acquired the spin lock but an interrupt handler wishes to acquire the lock, you could have a scenario where the interrupt hander spins forever waiting for the lock. Spinlocks in embedded systems can create delays due to priority inversion and it would be good to use mutexes where possible.

In reality, building robust multi-CPU mutual exclusion primitives is quite involved. Many papers have been written on efficient use of such resources to update data structures such as binary counters, counters, and linked lists. Techniques can be varied depending on the balance of consumer versus producer contexts (number of readers and writers).

The mechanism described above does not interact with the operating system scheduling behavior and the mechanism is not appropriate if the work to be performed in the critical section is long or if operating system calls are required. Operating systems provide specific calls to facilitate mutual exclusion between threads/tasks. Common capabilities provided include semaphores (invented by Edsger W. Dijkstra), mutexes, and message queues.

These functions often rely on underlying hardware capabilities as described above and interact with the operating system scheduler to manage the state transitions of the calling tasks.

Let’s describe a time sequence of two contexts acquiring a semaphore. Assuming context A has acquired a semaphore and context B makes a call to acquire the same semaphore, the operating system will place task B into a blocked state. Task B will transition to a ready state when task A releases the semaphore. In this case the system has provided the capabilities for the developer to provide mutual exclusion between task A and task B. Figure 7.12 shows the timeline associated with semaphore ownership.

FIGURE 7.12 Semaphore Timeline.

As you can see, the operating system scheduler ensures that only one task is executing in the critical section at any time. Although we show task A continuing to run after the semaphore is released until it is preempted, in many operating systems the call to release the semaphore also performs a scheduling evaluation and the transition to task B (or other task) could occur at that point.

There are two different types of semaphore, namely, binary and counting. Binary semaphores are restricted to two values (one or zero) acquired/available. Counting semaphores increment in value each time the semaphore is acquired. Typically the count is incremented each time the semaphore is acquired or reacquired. Depending on the operating system the semaphore can only be incremented by the task/thread that acquired it in the first place. Generally speaking, a mutex is the same as a binary semaphore. Although we have discussed semaphores in the context of providing mutual exclusion between two threads, in many real-time operating systems a semaphore can also be used to synchronize a task or thread, and in essence indicates an event. Figure 7.13 shows a simple case where a task is notified of an event by an interrupt handler (using VxWorks calls).

FIGURE 7.13 Task Synchronization.

As an embedded programmer, you have to be very aware of the services you can use in an interrupt handler. The documentation associated with your RTOS/OS should be referenced; making an OS call in an interrupt handler that is illegal can result in very strange behavior at runtime.

A common alternative to using mutual exclusion primitives to serialize access to data structure is to nominate a single entity in the system with responsibility to perform the updates. For example, a database structure can be abstracted by a messaging interface to send updates and make inquiries. Since only one thread is operating on the data at any time, there is no need for synchronization to be used within this thread. This can be a beneficial approach especially if the software was not originally designed to be multi-thread safe, but it comes at the higher cost of messaging to and from the owning thread. This technique can also be used to create a data structure that is optimized for a single writer and multiple readers. All writes to the data structures are carried out by a single thread that receives messages to perform the updates. Any thread reading the data structure uses API calls to directly read the data structures. This single write/multi-reader pattern allows for high-performance locking approaches, and it is a common design pattern. Figure 7.14 shows a simple message queue–based interaction between two tasks.

FIGURE 7.14 Message Queues.

Figure 7.14 uses VxWorks API’s calls to demonstrate the example. Two noteworthy arguments are in the calls (in addition to the message-related calls). The first is the blocking behavior: the example in Figure 7.14 blocks the calling thread forever when the task is waiting for a message; that is, the task is placed in the blocked state when no are messages in the queue and transited to ready when messages are in the queue. Similarly, on the msgQSend() call, the sending task may block if the queue is full, and the receive task does not draw down the messages. Balancing task priorities and message queue sizes to ensure that the system does not block or give unusual behavior is a task you will have to perform as an embedded software designer using an RTOS.

Device Driver Models

A function of the operating system is to provide arbitrated shared access to I/O devices in the system. Applications do not directly interact with the I/O devices but instead make use of operating system services to access them.

A number of different device driver models may apply to differing device classes. Some device drivers provide services to other elements with the operating system, while other device drivers provide access to user space applications and the devices are managed directly by the application. A general classification of drivers is as follows:

In some cases there are additional device drivers that operate in conjunction with the low-level device driver, such as USB class drivers. The low-level device driver provides services to the class driver. Figure 7.15 shows the high-level relationship between devices, drivers, and services.

FIGURE 7.15 Device Driver Relationships.

As you can see, the hierarchy in Figure 7.15 demonstrates a significant amount of abstraction of the device and allows for the provision of many services across many physical interfaces. Let us consider storage as an example. An application uses traditional C library/POSIX calls to open, close, read, write calls to the selected file descriptor which subsequently operates on a file on the file system. The operating system provides generic service calls to facilitate these C library/POSIX calls. These calls are the contract between the operating system and applications. The file system receives generic service calls, then calls file system–specific calls to read and write files. There are many different file system types, such as File Allocation Table 32 (FAT32), EXT2/3, and Journaling Flash File System 2 (JFFS2). The file system–specific handlers then call a block level device driver interface. The block device driver manages the block device, which could be a SATA drive connected over a SATA interconnect, or the file system could be connected to a USB mass storage class driver managing an external USB drive. In all cases, there is tremendous freedom to evolve each individual capability without changing the application interface. For example, there has been a great deal of innovation and development in the Linux file systems since its inception, each with increasing robustness, performance, and resilience.

In Figure 7.15, we also show a sample flow for a Bluetooth™ device. Bluetooth devices are often connected via a high-speed UART. The UART provides a host controller interface (HCI) where the serial stream is formatted in accordance with the Bluetooth standard HCI definition. The HCI driver connects to the UART driver connected to the device. The Bluetooth stack provides a number of Bluetooth control services and connects to the TCP/IP stack to provide Personal Area Network (PAN) IP services between devices. Again, this example serves to show the tremendous capabilities and innovation that result from achieving the appropriate level of abstraction between subsystems in the operating systems.

As you have seen, there are a number of different device driver models in place. In many cases the driver provides services to other modules within the operating system. Also, the entry to the device driver often provides a reentrant API; this means that the API can be called from multiple contexts and it is the driver’s responsibility to ensure that data structures are protected from concurrent access. The driver typically relies on synchronization principles (such as mutexes) to ensure safe concurrent access to the actual device or data structures associated with the device. To ensure high-performance drivers, it is important to minimize the amount of time the driver is serialized in these critical sections.

A device driver must manage the memory associated with the payload being sent or received from the device. The device driver or the device through DMA must be able to access the payload data being sent or a receive buffer for data being received. There are a number of scenarios that relate to the accessibility of this memory by the driver or device, depending on where the buffer is residing.

In a flat memory system with no process separation, the buffers are always resident in memory. This is the simplest case to handle for the device driver writer. The driver is executing in the same memory context as applications and drivers; as a result the driver can directly read from/write to the buffer. The buffer is resident in DRAM and the device may also use direct memory access (DMA) to and from the buffer. The biggest concern with a flat memory system with no separation is security and robustness of the system. Because any application can read/write data from other applications or device drivers, the application could obtain information or accidently destroy data structures if the application had defects (and of course, all software has some defects).

In operating systems including real-time operating systems that provide separate address space between user process and the kernel, buffers provided to the device driver may be resident in kernel memory. The driver is running in the same process space (kernel) and has direct access to the buffer. The kernel buffer is not subject to paging and will always be accessible until the driver frees the buffer or returns the buffer to an upper layer. You may have considered that if there are defects in the driver and it runs in the context of the kernel, then defects in the kernel can have a significant impact on the robustness and security of the system. This is true—a buggy device driver will likely crash the entire system, and, to make matters worse, such crashes are difficult to debug if the driver has corrupted a kernel data structure. In some operating systems, there is a trend to move device drivers (or portions thereof) to user space to increase the robustness of the system.

In the case of operating systems that support process separation, the device driver may be providing a direct interface to user space applications (such as /dev/tty in Linux). In this case the top layer of the driver is called with a memory descriptor with references to the user space buffer in the call. The driver must perform buffer copies between user mapped buffer and an allocated kernel buffer. The remainder of the driver then operates on the kernel buffer. There are also techniques for mapping the user space buffer to kernel space; more details can be found in the NMAP section in Chapter 10, “Embedded Graphics and Multimedia Acceleration.”

The case where memory buffers are originating from a user space application is an important one, and we will provide more details. A buffer that has been allocated to a user space process is a virtually contiguous buffer. The buffer has a base address and a length, and the length can be very large (as large as the system can allocate to a process depending on system resources). The memory management system (using the MMU) maps the large virtually contiguous buffer to a number of physical pages in memory. The buffer may or may not be physically contiguous. The user space buffer is represented as a list of physical pages. The device driver uses a system call to copy data from the user-mapped virtually contiguous buffer into kernel buffers. The kernel buffers themselves have a maximum contiguous size, although it is best to assume that the maximum contiguous kernel memory you can allocate is one page. In order for the copy to take place, the kernel must provide a kernel virtual mapping to allow the CPU to read the data and allocate a kernel buffer. Given that, the virtually contiguous user space data is copied into a number of kernel buffers. Linux kernel provides functions such as copy_from_user(to_kernel_pointer, from_user_address, size). The function copies size bytes from the user address to the kernel address pointer. The function actually executes in the context of the user space process, in that the page table mappings for the user space pointer are valid.

Some operating systems (BSD and VxWorks) have optimized the exchange of network buffers through the provision of zero-copy memory buffers. In this case the application writes directly into the network buffer structure and can submit the packet to the stack without a copy operation.

Given that data elements within the kernel are composed of a list of physical pages, the operating systems often defines a construct for a scatter gather list. A scatter gather list is a mechanism defined and supported by an operating system to represent a list of data that is not physically contiguous. The scatter gather list is operating system–specific, and when available it should be used to pass data elements that are larger than the contiguous elements in the system (usually a page). The Linux kernel makes extensive use of scatter gather lists and defines structures and management functions in /linux/include/scatterlist.h. The TCP/IP stack incorporates a scatter gather list representation into the stack buffer known as an SKBUFF. The device driver must iterate through the scatter gather list and write to the devices’ data registers or create device descriptors that point to the scatter gather list as it is submitted to the hardware. The scatter gather list is usually represented as an array of pointers to data elements, or alternately the scatter list can be represented as a linked list structure. The best structure depends on the access pattern of the driver/stack. The array-based approach is best if the CPU needs access to an element down the list (for example, the third buffer is the start of the IP packet in a packet list). However, since the maximum array size is often fixed, the linked list approach can support a very long list of buffers, but the list traversal can take some time. Figure 7.16 shows examples of both array-based and linked-list–based scatter gather lists and a combination structure used in Linux. The data payload pointed to by the data pointer should be viewed as logically contiguous data but is likely to be physically discontiguous.

FIGURE 7.16 Scatter Gather Structures.

The Linux scatter gather list is a combination of both an array and linked list. The determination of which format will actually be used is made at runtime by the design of the software using the scatter gather list.

BUS Drivers

As you have seen in Chapter 4, there are a number of bus standards such as PCIe, USB, SMBus, and I2C. PCIe, USB, and SMBus all provide a mechanism to scan the bus at runtime and identify what devices are attached to the bus. This process is known as enumeration. The bus driver handles the enumeration of the bus and provides services to each of the devices that are attached to the bus. Each bus driver has its own pattern for supporting the attached devices. For example, a PCI bus driver performs the following steps:

Once the scan is complete, the drive initializes a device driver registered for the specific device ID. In the case of Linux the devices are probed and the pci_dev structure is provided, such as in the example below:

static int __devinit device_probe(struct pci_dev ∗pdev,

             const struct pci_device_id ∗ent);

The pci_dev structure provides many elements, but in the context of this discussion, the resources and irq entries are pertinent. The resources elements is a list of memory address assigned to the device. The irq is the interrupt vector assigned to the device (this may be shared/unique).

The bus driver provides an abstraction that allows the device to be written generically regardless of the resources allocated to the device. It allows the driver to be unaltered for devices that are actually incorporated into an SOC or on an external PCI bus.

Networking

Most operating systems provide a networking stack of some kind. The most prevalent networking stack deployed is an Internet Protocol (IP) stack. The IP stack provides an application library to open/close connections to remote devices and send and receive data between the remote device. The application API is provided by a sockets library (usually BSD sockets). The APIs are consistent across nearly all platforms that provide an IP stack. Chapter 12, “Network Connectivity,” provides more detail on networking.

The TCP/IP stack takes socket send and receive requests from the applications. The application may select either Transmission Control Protocol (TCP) or User Datagram Protocol (UDP). The protocol definitions are defined and maintained, along with many other networking protocol standards, by the Internet Engineering Task Force (IEFT). The protocols are identified by the RFC number. The original UDP RFC is RFC768, published in 1980.

TCP is a reliable streaming protocol with retransmission of data if it is lost across the network. UDP is an unreliable datagram protocol. The TCP/IP stack performs the required protocol level processing for the protocol type.

For outgoing packets the IP layer adds the IP header to the PDU and selects the appropriate network interface to submit the packet to. The outgoing network interface is identified by looking up the routing tables and the destination IP address for the packet. In some cases the PDU is also fragmented to PDUs that are no bigger than the Path Maximum Transmission Unit (PMTU). The PMTU is the minimum MTU of any link between the source and destination. The MTU is the maximum size in octets/bytes that a layer can forward. For example, the MTU on an Ethernet (802.3) interface is 1492 bytes (RFC 1191). Fragmentation is an expensive operation (particularly for the receive-side processing), and it is best to ensure that upper layers do not generate PDUs that require IP fragmentation.

For packets received from the network interface, the IP layer validates the header, identifies the appropriate protocol handler, and forwards the packet to the appropriate protocol hander (TCP/UPD/ICMP/other). The IP layer must reassemble any fragmented packets that arrive.

At the bottom of the stack are the network device drivers. The driver model used for networking interfaces is usually different from the generic OPEN/CLOSE/IOCTL driver model described above. The network driver interacts with the protocol stack directly and does not generally provide any direct device interface. A network device driver is specific to the type of network interface (such as Ethernet or 802.11), the driver mode of the OS, and the network stack (such as IP). Figure 7.20 shows an overview of the stack and network interface drivers.

FIGURE 7.20 Network Stack and Device Drivers.

The following APIs are generally provided by a network driver:

On arrival of a packet on the network interface, the network device sends the packet via DMA into a receive buffer and interrupts the processor to indicate that a packet has arrived. The network driver then sends an event or notification to a deferred work task. When the deferred task wakes up to process the packet arrival event, it makes a call to submit the packet to the IP stack. The Linux kernel calls

netif_rx(struct sk_buff ∗skb)

netif_receive_skb (struct sk_buff ∗skb)

are used to send a packet from the driver up into the TCP/IP network stack. The function takes a pointer to an sk_buff buffer. An sk_buff buffer is a special buffer format used to carry packet data up and down the TCP/IP stack.

Storage File Systems

File systems are predominantly used to provide an abstract mechanism to open and close or read and write to a storage device. The storage device may or may not be persistent. Many different file systems are implemented in modern operating systems, with a subset available for real-time operating systems. In a traditional desktop system such as Linux or Microsoft Windows, the operating system provides a mass storage file system that is applicable to a large mass storage device such as a magnetic hard disk or solid state drives. Windows provides the New Technology File System (NTFS) and FAT file system. Linux desktop distributions predominantly use EXT3/4 file systems at the time of writing. In embedded systems, there are many more, such as JFFS2, TFAT, CRAMFS, RAMFS, and INITFS (all of which we will describe later).

When an application performs a write to the file system, the file system must allocate blocks on the storage device and write the required contents into the blocks allocated on the storage device. This operation is typically an asynchronous operation from the perspective of the applications. The write call returns immediately (does not block the application) even though the data may not have been written to the device. The file system drivers will at some point reflect the write in the file system. There are many reasons to defer the actual writing, the primary one being performance. A sophisticated file system will consolidate file system requests from a number of applications concurrently, and it schedules (order) the requests with the purpose of maximizing the file system throughput. At the time of writing, there are four I/O scheduler options available (in Linux):

Given that updates to the file system occur asynchronously to the application, there are cases where the contents on the mass storage do not reflect the current logical state of the file system. At any point in time portions of the data being written to mass storage may still reside in CPU memory buffers or even in buffers within the storage device (in the drive itself). In cases where the storage media is going to be removed or the system is about to be restarted, it is critical to issue a synchronization request to the file system prior to such an event. The synchronization request flushes the data all the way out to the storage media, and the media is guaranteed to be consistent when the media is reinserted or the system restarts. I’m sure you have used the Windows option to “stop a USB device” prior to removal; this effectively ensures that any data contents still on memory are written out to the pen drive. I’m equally sure that you have at times simply removed the drive without taking the time to issue the request—and it has probably always worked, but there is a chance that the data are corrupted or, worse, the file system management structures are not consistent. In embedded systems, this could prevent a system from booting properly or an application getting incorrect data and failing to operate correctly, so it is particularly important to synchronize the file systems before shutdown, restarting, or media removal.

Two distinct file system types are in use today, journaling and non-journaling. A journaling file system maintains a record of updates or deltas to the existing state of the mass storage device. The updates, primarily to metadata, are carried out as transactions. Each transaction is an atomic operation to the file system, thus at any point the file system can be recovered to a consistent state. The journal updates are held on the storage device. When the file system is mounted the journal entries are applied to the file system baseline. This also occurs periodically during the operation of the file system. File systems with journaling capability such as EXT3 rely on a Journaling Block Device driver to provide transaction-based journaling capabilities to the underlying block devices.

A non-journaling file system such as the File Allocation Table 32 (FAT32), often used on USB pen drives, performs all updates directly to the file system management structures (such as file allocation tables). A journaling file system is more resilient to un-notified removal of device or power. The underlying structures are always consistent, and the worst case is loss of some transactions.

We should distinguish between file system consistency and ensuring that the contents of a file reflect all up-to-date application transactions. The journaling file system is very resilient and ensures consistency. However, it may lose the latest transactions depending on the scenario. In this case the application data may not have actually been made persistent on the device. There are transaction-based file systems in which the application writes a transaction that will be written as an atomic operation to the file system. The transaction will either complete in its entirety or none of the transaction will complete (if an error occurred). It allows the application to ensure data consistency by making sure the transactions are written atomically. The application can also ensure that the transaction has made its way to the mass storage device. Transaction file systems are EXT3, JFFS2, and YAFFS2.

In many embedded systems, flash-based file systems are required as the mass storage devices use flash memory. We mentioned in Chapter 4 two primary types of flash, NAND and NOR. There is still a preponderance of NOR-based flash where storage requirements are modest and reliability is paramount (many microcontrollers actually include on-die flash, and in such cases, it is generally NOR). There are two classes of file systems commonly used. The first is read-only compressed file systems, such as CRAMFS. CRAMFS is a simple file system that uses zlib compression routines to compress each file page by page. The file system can be accessed using normal file access routines, and random access is supported. A CRAMFS file system could be used to hold the root file system of an embedded system.

An alternative approach to providing the initial file system for a Linux kernel boot is to use INITRAMFS. This file system consists of an archive that is stored on the flash devices. The archive contains a gzipped cpio format image. This initial image is decompressed at startup to create a root file system (ROOTFS). The root file system is read-only, as any updates will not be written to the compressed archive. This root file system is ramfs. A ramfs file system is a RAM-resident file system with no backing store. It actually reuses much of the kernel’s disk caching mechanisms.

Another file system to consider is a journaling flash file system such as Journaling Flash File System (JFFS2) or Yet Another Flash File System (YAFFS2). JFFS2 file systems operate by continuously writing to the “end” of the file system for wear-leveling purposes and as such is, strictly speaking, a log-structured file system. As the name of the first of these file systems suggests, these are file systems that support flash devices and use journaling. These flash file systems support both NAND and NOR devices. YAFFS2 provides the following features (http://www.yaffs.net/):

To support flash file systems, a flash block driver is provided; this is a low-level interface that manages the blocks on the device. On a Linux system these are provided by MTD drivers.

Power Management

An ever-increasing responsibility of the operating system is to effectively manage power on the platform. Chapter 9, “Power Optimization,” describes some of the overall principles in managing power. Although a number of techniques apply to changing the dynamic power of the system through changing the frequency and core voltage of the CPU, in many embedded cases, the designer is likely not willing to design a sufficient margin for the variable performance when the system is active. It is more likely that the system is designed to perform at a fixed high-performance point and to aggressively bring the system to a sleep state when there is no work to be done. In the case of the operating systems, this is usually determined by the behavior of the “idle” function. This is a function that is scheduled when there is no other high-priority work to be done. The thread may simply halt the CPU. A halt instruction typically puts the processor in a lower power state while waiting for the CPU to receive an interrupt and continue execution. In modern Intel architecture systems, the idle function uses the MWAIT instruction. The MWAIT instruction takes a CPU/platform-specific hint to the targeted sleep state of the CPU. An embedded system designer should be aware of exit latencies associated with CPU sleep states; in general, the deeper the sleep state, the longer the latency to wake up. The operating system may provide configuration of these capabilities. An example of dynamically controlling the suggested sleep state of the CPU can be found in the Linux IA-32 idle driver.

Many desktop-based operating systems support a formal transition to a suspended state, where all state information is saved into DRAM (self-refreshed) and all other aspects of the system are powered down: CPU, caches, and all devices not requiring monitoring for a wakeup event. This state is known as S3 on Intel platforms. When the wakeup event occurs, the operating system resumes execution and sends a notification event to each driver to reprogram the devices. Such a capability is rarely used in embedded systems where they are expected to perform the application function at all times. A further extension of the suspend to RAM (S3) operating system state is hibernation. Hibernation is similar in principal to S3 except that the contents of DRAM are saved into a hibernation file on a mass storage device. Once this is complete, power can be totally removed from the system (except for any wakeup devices, such as support for wake-on-LAN from the NIC card).

Device drivers also play a part in the power management of the system. Each device driver may be asked to place a device in a particular power state; the driver must perform the action and respond to the kernel when the task is complete.

In addition to the basic technique of controlling the idle function of the file operating system, some platforms actively manage the device’s state (power and clock) depending on the current usage of the device. This is an active topic in embedded and especially mobile systems. However, few standardized approaches allow the operating system to automatically manage the overall system at this level of detail (at the time of writing).

Real Time

The real-time behavior of an operating system is critical in many embedded platforms. The real-time behavior is usually defined by having a deterministic bounded time from an external event such as an interrupting device to the execution of the real-time handler (task or thread) and the action resulting from the original event. This may be an output or simply data analysis of the incoming data. Figure 7.22 shows the flow from hardware event to task.

FIGURE 7.22 Interrupt Delivery to Thread Flow.

Many system aspects contribute to the latency from interrupt event to the execution of the thread to handle the interrupt.

Licensing

It might seem strange to include a section on licensing in an operating system chapter, but we think a brief discussion is warranted, especially in the context of embedded systems.

In many systems, you may elect to purchase software to be included in your product. This could range from the operating system itself to special-purpose libraries or applications themselves. Such software is delivered under a license. The license dictates how the software may be used and or redistributed. Let’s discuss proprietary and open source licenses.

If you purchase software for inclusion in your product, it may be provided in either binary or source form. Regardless of the form in which you received the software, it will have an accompanying license that specifies what you can do with it. The most common is that you can include it in your product but you cannot redistribute the source code. Depending on how you purchased the software, you may have made a single buyout payment where you do not have to pay for each individual instance you ship as part of your product, or you may have to make a royalty payment for each copy shipped as part of your product. It will be important for you to have processes in your software development to ensure you track the use of such software. These licenses are known as proprietary licenses and each one is different.

Another class of libraries is known as open source licenses. Many such licenses exist but the most prevalent are BSD License, Apache License, and Gnu Public Licenses (GPLv2, LGPLv2, and GPLv3). The BSD and Apache License generally allow you to reuse the code in your own system and do not make any redistribution demands on you, the user of the code. You may be required to mention the fact that you have included the software in your product. If you make changes or updates to such software you are not required to share these changes with an external party.

Gnu Public License 2 (GPL2) is a license that you can include in your product but with the requirement that you mention that you have incorporated the code in your product, and should you make any change to the source, you are also required to provide that source code to anybody who requests it. This requirement is triggered when you deliver the software or product including the code to a third party. Depending on how you link any GPL software into your product, you may also be required to redistribute the source code of your own software. In general, if you are linking to any GPL software you should pay particular attention. There is also a license known as LGPL, which is the same as GPL in the requirement to redistribute any changes you make to the GPL code in source form, but you are not required to redistribute your software if you simply link to the LGPL code. The attribute where linking GPL code to other code triggers the requirement to also release the source code of your code is known as viral license. You should also consider the implications to the entire system. Perhaps you have purchased a software library under a proprietary license. You then download a piece of open source code released under GPL license. If you link the entire software together into a monolithic application (which would not be unusual in embedded systems), then you may have triggered the requirement to publish the source code of the proprietary software—clearly, you probably don’t have such rights.

This is an important area. You don’t want to find that you have an issue blocking the shipment of your product just when you want to release it.

This is just an overview—don’t consider it to be legal advice on this topic. You should make sure you comprehend your company’s interpretation of each software license that applies to your software and external software you plan on incorporating into the system.