Chapter 10.

Realtime Control Platform

Chapter 10. Realtime Control Platform

The control of industrial processes is, in general, a complex task that has to be carried out by several computers linked together and with different specializations. The way computers are programmed depends mostly on the required response speed. The case of computers at the lowest level is directly in control of the physical processes. Here, the timing requirements are usually so strict that special programming methods and techniques must be used. These methods are the subject of this chapter. Hardware is as important as the software for building efficient real-time computer systems. Hardware capacity must be available and the software has to exploit it. In a sense, hardware and software are logically equivalent; many solutions can be realized with hardwired circuits as well as with program instructions. But there are situations where the software seems to fight against all the possibilities the hardware has to offer.

10.1 GENERAL CONCEPTS ABOUT PROGRAMS

10.1.1 Programs and Processes

A program describes the constant and variable data objects and the operations to be performed on them. A program is just pure information; as such, it can be recorded on any medium able to store information, for instance, paper or a floppy disk. Programs may be analysed and written at several abstraction levels by using appropriate formalisms to describe the variables and the operations to perform at each level. At the bottom, the description is straightforward: the variables are stored in memory cells labeled with their location/address. At higher levels, the variables become abstract names and the operations are organized in functions and procedures. The programmer working at higher abstraction levels docs not need to bother about which cells variables are stored in or about

Chapter 10. Realtime Control Platform

the aspect of the machine code generated by the compiler. Sequential programming is the most common way of writing programs. The term sequential indicates that the program instructions are given in a fixed sequence, one instruction after the other. The purpose of a sequential program is to transform input data given in a certain form into output data of a different form according to a specified algorithm (i.e. solution method, Figure 10-1). In a sequential program, the only entities are the data and the code to act upon them. No time constraints are given; the result of a run depends only on the input data and the properties of the algorithm. The algorithm of a sequential program can, in principle, be coded in any programming language. A sequential program acts like a filter on the input data. The filter abstraction is carried further in some operating systems (e.g. MS-DOS and UNIX) with device independence in program input and output. In such systems, the input/output of a program can be a file, a terminal screen or another program. In real-time programming, the abstraction of resource independence cannot be made; on the contrary, one has to be constantly aware of the environment in which the program is operating, be it a microwave oven controller or a robot arm positioner.

Figure 10-1 Data processing via a sequential program.

In real-time systems external signals usually require immediate attention by the processor. In fact, one of the most important features of real-time systems is their reaction time to input signals. The special requirements of real-time programming and in particular the necessity to react quickly to external requests, are not approached adequately with the normal techniques for sequential programming. The forced serial disposition of instruction blocks that should be executed in parallel leads to an unnatural involution of the resulting code and introduces strong ties between functions which should remain separate. We have already seen what problems may arise when two different program modules are bound together. In most cases it is not possible to build real-time systems using the normal methods for

Chapter 10. Realtime Control Platform

sequential programming. In real-time systems, different program modules or tasks have to be active at the same time, that is, operate in parallel, where each task is assigned to a specific function. This is known as concurrent programming to stress the cooperation among the different program modules. The basic operating entity in real-time systems is the processes. There is a very important distinction between programs and processes. Programs are sets of information on how to operate on and transform the input data, while processes are programs in execution. A process consists of code (the program instructions), a data area where the process variables are stored and, depending on the actual implementation, a free work area (heap) and a stack (Figure 10-2). A program written in the same high-level language and then compiled and executed on different machines will lead to different processes each with its own code, data, heap and stack areas.

Figure 10-2 Example of the internal memory organization of a process.

Chapter 10. Realtime Control Platform

Each process is at all instants in a well defined state, unequivocally described by the contents of the CPU registers, the locations of its code, data and stack areas, and a pointer to the next instruction for execution in the code area. This basic information about a running process is called its canonical state or context. The existence of a context is a general fact, whereas what registers, states and pointers are actually part of the context depends on the processor used. The steps needed to transform a program in a process consist of storage on a computerreadable medium such as magnetic tape or floppy disk, compilation, linking, loading and execution. These steps are amply described in books on operating systems and will not be dealt with here. The description used for algorithm definition in the top-down programming method also provides a complete documentation of the system. The importance of good documentation cannot be overestimated; it is enough to consider that maintenance and corrections are the major expenses related to the entire lifetime of a program. Maintenance is much easier if good documentation is available; it might, on the contrary, turn out to be impossible if the documentation is poor or insufficient.

10.1.2 Concurrent Programming, Multiprogramming and Multitasking

In both concurrent programming and real-time programming, the possibility of executing several tasks simultaneously on the same machine may be needed. These tasks share the resources of the system but otherwise are more or less independent from each other. Concurrent programming is a macroscopic effect that can be realized either by using several processors where each task is run on an entirely dedicated processor, or by letting more tasks run on a single processor. The latter is the most common case, even though falling hardware prices make multiprocessors more and more economically feasible. Several processors may, of course, be active at the same time in a bus system. In technical literature the term concurrent programming is sometimes used interchangeably with multiprogramming. Concurrent programming is the abstract study of programs with potential for concurrency, independently from the implementation details of the machine they run on. Concurrent programming is oriented to the execution on virtual processors without concern for the implementation details. Multiprogramming is the technique for letting several programs run on a single central processing unit.

Chapter 10. Realtime Control Platform

A common term in real-time programming is multitasking. A task is a small program or module and multitasking is the technique of letting them run concurrently. In a sense, multitasking is the practical side of concurrent programming, where the actual aspects of the target machine are taken into consideration. Concurrent programming is more difficult than sequential programming because the human capacity for following the development of interdependent processes and for examining their mutual interactions is limited. (Think about school studies in history: first comes national history and then Western or Eastern history in some chronological order. With this perspective, it is not natural to compare, for instance, what happened in different countries in 1848.) Real-time programming is based on concurrent programming and refers also to techniques to increase the efficiency and execution speed of programs: interrupt management, exception handling and the direct use of operating system resources. Real-time programs also require special testing methods.

10.2 THE MANAGEMENT OF SYSTEM RESOURCES

10.2.1 The Function of the Operating System

An operating system is a very complex piece of software for administering the hardware and software resources of a computer system. An operating system offers a virtual (logical) environment, consisting of CPU time and memory space, in which the processes can be executed. With virtual environment, a conceptual environment is intended with specific features and that may or may not exist in physical hardware.Multiprocessing is the basic conceptual tool for the design of multiuser as well as real-time operating systems; it deals primarily with resource allocation and protection. However, the goals of multiuser and realtime operating systems are not the same. A multiuser operating system, also known as a timesharing system, allocates expensive resources to several users, checks that the users do not influence each other and divides the operating costs between them. In real-time programming the purpose of multitasking is to keep distinct operations separate from each other and to distribute the workload among different modules. In real-time systems, the only 'user' is the system to be controlled. In time-sharing systems, much attention is dedicated to the protection and separation of users by way of passwords, access control, etc. Real-time programming is less restrictive in this respect as the system designer(s) know what each module does. In situations where each CPU millisecond counts, no time can be wasted for access control overhead; file systems and protection mechanisms are not important parts of real-time operating systems. Time-sharing

Chapter 10. Realtime Control Platform

systems are also supposed to be 'fair' in some sense, trying not to put any user at a special disadvantage even under heavy machine load conditions. The same does not hold for prioritybased real-time systems, where the processes are strongly differentiated. We will now focus on multiprogramming on a single processor because this is the most common and most important case of digital control applications. Many of the ideas can be transferred to the multiprocessor case. In multiprocessing, the basic entities are the processes or tasks and their contexts. The context of a process in execution can be 'frozen' at any time by saving the content of the CPU registers; while the initial process is suspended, the CPU can run other processes. To achieve multitasking on a single processor, the execution of each task is divided into several short intervals (Figure 10-3). The processor begins executing part of the first task, continues with part of the second, of the third, and so on. A time interval is assigned to each task, so that, for example, for 10 ms the processor is dedicated to the first task, then switches to the second, the third, etc. The macroscopic effect of the CPU time division among the processes is the parallel execution of n processes, each on a fully dedicated CPU of capacity 1/n (that is, n times slower) compared to the original one.

Chapter 10. Realtime Control Platform

Figure 10-3 the principle of multitasking, (a) Macroscopic effect; (b) CPU time division.

The execution of several tasks on different CPUs or on the same CPU are two different realizations of the same logical principle: in the first case the processes are distributed spatially, in the second they are distributed in time. Apart from overhead due to scheduling and intertask communication, if n processes run on k processors, each process is ideally assigned to a processor of capacity k/n of the original one. A basic multitasking system consists of a procedure, implemented in hardware or software or a combination of both, to save the context of a process on the stack or at defined memory locations, and restore the context of another process to continue its execution where it was halted. A system program called a scheduler selects the next process to execute from among the loaded processes. The process switch operations are time critical and must be realized with maximum efficiency.

Chapter 10. Realtime Control Platform

In processors not designed for multiprogramming, the process exchange module must save all registers and other context parameters on the stack and then save the pointers to the stack in a protected data area. Processors designed to support multiprogramming have compact instructions to save and recall the content of all the registers. When the context of a process is saved, it is not necessary to also save the process variables. These are located in the process memory area which has to be protected by the operating system against changes by other processes. The same does not hold for the CPU registers, which are shared by all processes and whose content is changed all the time. To be able to halt CPU execution at regular intervals in order for a different process to be executed, a timing device external to the CPU is needed. A system timer sends interrupt signals (ticks) to the processor at defined intervals; typical rates are one tick every 1 ms on very fast processors down to one tick every 50 ms on slower machines. At each tick, the CPU briefly suspends its operations to check whether the current process has to be interrupted and a new one loaded. The action that forces a running task to halt its execution in order to allow another task to run is called preemption. The tick interrupt is not the only way to stop a process and transfer execution to another. A process can stop on its own either because it has reached the end or because it is idle waiting for an event, such as an I/O operation with a physical device which would take several ticks to complete.

10.2.2 Process States

A process executed in a multitasking environment can be in different states. These states are commonly shown with the help of a diagram (Figure 7.4); they are defined as follows: Removed The program is present on disk, ready to be loaded to internal RAM memory. Waiting The process is waiting for some external event (I/O data transfer, input from keyboard, an external interrupt) or internal (explicit signalling by another process) to be moved to the 'Ready' state. Ready The process can be executed whenever the CPU is available. Running (Executing) The process that is currently being executed.

Chapter 10. Realtime Control Platform

Figure 10-4 shows which changes from one state to another are possible. The defined operations are: 1. From 'Removed' to 'Ready'. The process is loaded from disk to RAM memory, with relocation of all the relative addresses and assignment of the work areas (code, data, heap, stack) with the related pointers.

Figure 10-4 The states of a process.

2. From 'Ready' to 'Running'. The process is selected by the scheduler to run and is assigned CPU control via the process switch module. 3. The opposite change, from 'Running' to 'Ready', is controlled by the same process switch module when it is time to let another process run. 4. From 'Running' to 'Waiting'. The process enters an idle state to wait for an external event, often an I/O operation with units much slower than the CPU, or the process must wait for a determined period of time, because of an explicit instruction. 5. From 'Waiting' to 'Ready'. When the awaited event has occurred or the required time has elapsed, the process is not immediately executed but is put instead in 'Ready' state. The scheduler will later determine when the process can be executed again. 6. When the end instruction of a program is reached, the operating system may eliminate a process from central memory.

Chapter 10. Realtime Control Platform

10.2.3 Strategies for Process Selection

There are several possible strategies for selecting from among the processes waiting in the queue, the one to run next. Several conflicting factors have to be considered: some processes need more execution time than others, must react quickly, are more important, etc. The decision of which process may continue execution at a given time is taken by the scheduler, a service module started every time a running process releases control of execution. The scheduler can follow different strategies, of which the most common are round-robin rotation and priority allocation. The strategies are similar to those used for bus arbitration. The most simple selection strategy is round-robin: the processes are selected one after the other for execution, following a fixed order and for the same time interval. The main advantage of the round-robin method is its simplicity; on the other hand, there are notable drawbacks when processes with different requirements are allocated equal CPU resources. A more complicated principle for process selection is based on the assignment of priorities. At each process change, the scheduler assigns execution to the process with highest priority. The priorities are defined by the programmer and in many cases can also be changed from within a process during execution. Straight priority allocation leads easily to unfair situations. The process with highest priority would be always selected for execution (unless it is in waiting state) and be the only one to run. To avoid this situation, the scheduler decreases the priority of the running process at a constant rate. Eventually, the priority of the running process will be lower than that of some waiting process, which is then selected for execution. In this way, it is ensured that all processes are eventually executed. After some time, the priorities of the waiting processes are set back to their nominal values. This method is called dynamic priority allocation. It ensures that even processes with lower priority will be executed and that processes with high initial priority do not hold indefinite control of the CPU. The consequence of different initial priority allocations is that processes with higher priorities will be executed more often than others. Processes which are called often and/or must be activated quickly have higher priorities; less important processes for which a longer response time is acceptable have lower priorities. In real-time systems, however, the forced preemption of running processes may be undesirable. A different strategy is then employed: each process may start other processes and change the priorities of waiting processes. The responsibility for seeing that the play among the processes is carried out in the desired fashion lies with the programmer. The minimal time interval assigned to each process before it is interrupted is called time slice; it has the length of a few ticks. The length of the time slice influences the performance

Chapter 10. Realtime Control Platform

of the system. If the time slices are short (~ 10-20 ms), the system is quick to react to external events such as interrupts or terminal input, but the process scheduling overhead gets an important share of the total CPU time. With longer time slices, the processes execute more effectively with less overhead, but the reaction time gets appreciably slower. The length of the time slice influences strongly the global performance of a system only when the running processes have similar priorities. Real-time operating systems do not only depend on the time slice. The operating systems are designed to react immediately to situations when changes in the process priorities may have occurred, such as the arrival of an external interrupt or the completion of a disk read operation. For each such event, the relative priorities of the waiting processes are computed anew and, if necessary, a process switch is performed. The scheduling of processes based on priorities works correctly only when the various tasks have different priorities. It does not help to give maximum priority to all processes, as this certainly does not increase the execution speed of the CPU. Each process would still have to wait until all other processes have been executed before it can run again. A system where all tasks have the same priority works in a round-robin fashion. The best results in the operation of a real-time system come when the relative priorities are correctly defined and balanced.

10.2.4 Internal Memory Management

After the CPU, the other most important resource to manage in real-time systems is the central memory RAM. For this purpose, the methods used in real-time systems are generally simpler than the ones used in multiuser computing centres. In large operating systems with many users, most of the programs and data are stored in secondary memory (hard disk) and are loaded to RAM only when they are needed. This is acceptable for timesharing and batch jobs when execution time is not very important, but not for real-time systems where all tasks should always be located in RAM ready for execution. However, disk memory support could still be necessary in real-time systems because the central memory is not always large enough to fit all programs and their data. A strategy is needed in order to allocate the available space as efficiently as possible. A basic memory management technique is segmentation. A process is divided in some parts, called segments or overlays, which can be separately loaded in central memory (Figure 10-5).

Chapter 10. Realtime Control Platform

Figure 10-5 Use of program segments and overlays.

The programmer must explicitly define the program segments. Each program segment will execute and then call the next to continue. This method is straightforward but not particularly efficient because of its dependence on external disk memory. Other memory management schemes are transparent to the processes, in other words, they do not have to be taken into consideration when writing the program. The most straightforward method for memory management is division of the available memory in partitions, each assigned to a process (Figure 10-6). The size of the partitions is defined at the time of system initialization; it may be different for different partitions. When a process is loaded, it is put in the smallest partition large enough to contain it. If no partition is available, the process may have to be broken and loaded in several partitions. Many different algorithms are available to allocate the memory to different processes. With partitions, once the memory space has been allocated at machine start-up, it cannot be reclaimed and reused. To be able to utilize all available memory over and over again, on middle and large-sized computers the virtual memory management technique is commonly used. Virtual memory is based on the assumption that the total size of processes and data may be larger than the RAM space at disposal.

Chapter 10. Realtime Control Platform

Figure 10-6 Memory division in partitions.

A mass memory unit (e.g. a disk) that allows fast data exchange with central memory is used. The mass memory unit is large enough to hold the total memory space required by all processes. With virtual memory, a process may address a space larger than the one at disposal in central memory. The main reason for which virtual memory is used is economic. The central memory is still much more expensive per unit of stored information than secondary mass memory. The central memory is also volatile and draws electric power, which both costs and heats up the system electronics. In case of a system crash, it is possible to restore operations almost to the point where the crash occurred if a constant copy of the processes is stored on disk. If a crash or a power failure occurs when the whole system is only loaded in RAM, then the whole process state is wiped out. In real-time systems, virtual memory is of interest only when it is fast and efficient. To ensure fast reaction, the most important processes can be permanently stored in central memory partitions and less important ones be called at need. Another important consideration related to the use of secondary memory in real-time applications is whether it can be used in the operating environment. For instance, disk units (hard disks and floppies) cannot be used in environments with vibrations and shocks. One of the major differences between multiuser and real-time operating systems lies in file management. The most important issues in multiuser systems are directory structure and file protection. The management and protection of directories, with the related controls and verifications at each access imposes an overhead seldom acceptable in real-time systems. A

Chapter 10. Realtime Control Platform

simplified use of mass memory, mainly for storing logs and reports and common ownership of all the tasks, does not warrant the need for a complex file system. There is a strong analogy between CPU control allocation, resource protection and bus master arbitration in a multiprocessor bus system. In all cases we deal with a limited resource (CPU time, memory, the bus) which has to be divided among several requesting units in a safe, efficient and fair manner. The criteria for assigning the resource, be it a simple roundrobin scheme or a more complicated priority-based allocation, must avoid deadlocks and lockouts, assign the resource to all units requesting it and ensure maximum throughput for the whole system. The most sophisticated operating systems allow the tuning of CPU and memory management parameters to achieve optimal performance. Process priorities and time slice length should be chosen and combined in order to increase the general performance, or throughput, of a system.

10.3 MUTUAL EXCLUSION, CRITICAL REGIONS AND DEADLOCK

10.3.1 Resource Protection

In multiprogramming there are often situations where the processes compete for resources. The consequences of the competition may lead to erratic behaviour and even to the complete halt of a system. Resources do not need to be expensive pieces of hardware, such as printers or magnetic tape units, they can be variables in central memory as well. The classic examples for software resource protection are seat reservations on airplanes and banking with balance control when several operations are executed - almost concurrently - on the same account. Before a flight, the airline seats exist only in the memory of the computer reservation system. Obviously, a seat cannot be allocated to two different customers if they happen to book the same flight at the same time. The seat information is therefore a type of resource to protect, in this case a resource existing only in software. If different processes operate on common variables and read and modify them without a defined precedence order, their interaction could lead to undesirable results. Let us consider two processes. Both processes access the same variable, first read its value

Chapter 10. Realtime Control Platform

and then modify it. If one process is interrupted just after the read operation and before it could change its value, the other process may modify the variable while the first is waiting. The first process then resumes execution without knowing that the variable has changed and then proceeds to work on an old value. After all, in a multitasking environment a process does not know when it is interrupted and when it starts again. The problem is that the variable is accessed by both processes without restrictions. It does not help to check the formal correctness of different programs if the effects of the possible interactions among processes are not taken into account. A situation where the result depends on the relative random order of process execution is called a race condition. This problem, known as resource protection, is central to the whole theory of multiprogramming. The variable accessed by both processes has to be considered as a resource to be protected from their concurrent action. In order to avoid race conditions, access to the resource by the processes should not be free and indiscriminate but instead follow determined precedence rules. The problem of resource protection has been studied for a long time and different solution strategies have been devised. These strategies vary with the type, technology and, most of all, access speed of the resource to be protected. Slow units, which tend to be used for quite a long time by the process (e.g. printer or magnetic tape unit) are usually allocated exclusively to the requesting process on the basis of a precedence queue. Alternately, a resource is permanently allocated to a single process (called a spooler, from simultaneous peripheral operations on line) that accepts as input from other processes the names of the files or other data objects, organizes them according to defined precedence criteria and sends them one at a time to the requested unit. Spoolers are commonly used in multiuser operating systems. Other methods are used for the protection of resources with very short access time and are continuously referred to by different processes, for instance, variables in central memory, records in a file or I/O interfaces on a data bus. This section is mainly devoted to such methods and will show different approaches together with their consequences. The principal rule for resource protection is that a process should never change the state of a shared resource while another process has access to it. Or, more generally: a process should never access a resource currently used by another process, independently of whether or not it is going to change its state. The second rule is more restrictive but simplifies practical control operations because it is not necessary to keep track of what operations each process is going to perform on the resource. The major difficulty in resource protection arises from the fact that in multitasking systems all processes can be interrupted at any time to allow other processes to be executed. The exact instants when the interruptions take place are not under the control of the programmer

Chapter 10. Realtime Control Platform

and cannot be known in advance. A first, elementary, method to guarantee resource protection is to disable interrupts while a resource is accessed. This effect is achieved by blocking the reaction of the processor to the interrupt signals. As process switching is initiated via an interrupt, disabling the interrupt prevents process switching as well. A process is then guaranteed to work without interruptions when it is in a 'protected' area. On the other hand, interrupts should normally be enabled to ensure quick reaction to special conditions requiring immediate attention. In a control system, part of the program modules are controlled by interrupts and disabling them can inhibit the processor from reacting to fully legitimate requests. In some systems, interrupts are not saved after they have occurred so they may go unnoticed if they arise when handling is disabled. Furthermore, interrupt disabling does not work in systems with several CPUs; a task running on a different processor might 'sneak' in the protected resource from behind. Interrupt disabling should thus be used with extreme care and only when no other solution is feasible. It should also be limited to a few code instructions.

10.3.2 Mutual Exclusion

A different approach to the problem of resource protection is possible if we consider it to be a problem of mutual exclusion, that is, where access to a protected resource is done from only one process at a time. No process should then access a resource until the resource is explicitly released by the process that requested it first. The goals of a correct execution of concurrent processes are that:
q

Only one process at a time has access to a protected resource. The processes remain mutually independent. Stopping one process should not hinder the other process(es) from continuing their execution.

The above statements relate to two correctness properties, safety and liveness. Safety means that access limits have to be respected, so that a protected resource is not accessed by more than one process at a time. Liveness indicates that a program at some time will do what it is supposed to or, in other words, that it will not hang indefinitely. Safety can always be obtained by giving up some concurrency between tasks; the safest programs are in fact strictly sequential, where no parallel access to a resource from different parts of the program is possible.

Chapter 10. Realtime Control Platform

10.3.3 Critical Regions

The concept of critical regions has been proposed by Brinch Hansen (1973) to avoid the inconveniences related to the variables for resource protection. A critical region is a part of a program where a protected resource may be accessed. The rules to access a critical region are:
q

When a process intends to enter a critical region, it will receive permission to do it in a finite time. Only one process at a time may enter or stay in a critical region. A process remains in a critical region for a finite amount of time.

It is the responsibility of the compiler to verify that the variables in v are referred only from within s. The run-time operating system should check that only one s module at a time is executed and that no interrupts take place during this execution.

10.3.4 Deadlock
Deadlock is the state when some or all processes in a system are halted waiting for something to happen. If this 'something' can only be initiated by another waiting process, then all processes wait endlessly in a deadlock condition (Figure 10-7). A different case of deadlock is when one or more processes still run but fail to make any progress. This situation is called starvation; this is the case when running processes continuously test the value of a condition variable which is not going to be changed because the other processes are also busy testing. In other words, deadlocked processes are in the 'waiting' queue and starving processes are 'ready' or 'executing', but do not make any progress.

Chapter 10. Realtime Control Platform

Figure 10-7 The deadlock.

It has been shown that it is necessary that several conditions be true at the same time for deadlock to occur. If any of these conditions does not exist, deadlock cannot happen.

Mutual exclusion. There are system resources which can be used only by one process at a time. Non-preempted allocation. A resource can be released only by the process that allocated it. Successive allocation. A process can allocate the necessary resources one at a time. Inverse-order allocation. The processes can allocate resources in a different order.

These four principles indirectly give the key for avoiding deadlock situations; it is sufficient that one of them is not true to make deadlock impossible. The first principle cannot be changed as mutual exclusion is the principal condition to guarantee the ordered management of shared resources. The second principle requires that the operating system recognize a deadlock situation and react accordingly, for instance, by forcing the release of a resource by a process. But recognition without ambiguity of a deadlock situation is very difficult and the forced release

Chapter 10. Realtime Control Platform

of some resources may lead to other types of practical problems. The forced release of a resource is interesting only with internal resources (variables stored in RAM memory) and in situations seldom leading to deadlock. Following the third principle, the alternative to allocating one resource at a time is to assign all needed resources at once. This solution is not feasible, as many resources would remain unused for a longer time, or allocated for the whole execution of a process when their actual use may be more limited. Violation of the fourth principle leads easily to deadlock conditions. If two processes need two resources A and B where one allocates them in order A-B and the second in order B-A, it is sufficient that the first process allocates A, is interrupted and control passed to the second process, which allocates resource B, for deadlock to be verified. Each process is now waiting endlessly for the other to release its resource.

10.4 PROCESS SYNCHRONIZATION: SEMAPHORES AND EVENTS

Mutual exclusion imposes some conditions on access to a resource by two or more different processes. This problem can be considered from a different viewpoint: a process can proceed beyond a certain point only after another process has reached some other point of its execution. If the points in the processes are located before and after the protected resource, then mutual exclusion is achieved. The introduction of a time precedence order in the execution of several processes is called synchronization. Process synchronization is the most natural function in an operating system and is used in practice for the implementation of resource protection: the access to a resource is ordered in time with the help of a synchronization mechanism.

10.4.1 Semaphores
We have seen that the introduction of extra variables for resource protection is not free from problems, as the protection variables become common resources themselves. The root of the problem is that the operations of check and change of the value of a variable are separated and can be interrupted at any time. Moreover, continuous tests on the values of the variables waste CPU time. The semaphore was proposed by Dijkstra (1968) as a basic synchronization

Chapter 10. Realtime Control Platform

principle to overcome the problems related with protection variables. The semaphore is probably the most common method for process synchronization. A semaphore is an integer variable which can only be 0 or take positive values. Its initial value is defined in its first declaration in a program and is usually equal to 0 or 1. Semaphores which can take only values 0 and 1 are called binary semaphores. Two operations are defined on semaphores: signal and wait. The signal operation increases the value of the semaphore by 1; it does not have any other effect on the executing process. The wait operation leads to different results, depending on the current value of the semaphore. If this value is greater than 0, it is decreased by 1 and the process calling the wait function can proceed. If the semaphore has value 0, execution of the process calling wait is halted until the value is increased again by another process with a signal operation. Only then is it possible for wait to decrease the value of the semaphore and proceed with execution. It is very important that the operations of test and decrement of the wait function are executed in one step only. The operating system is not allowed to break the execution of wait after the test on the value and before the decrement operation. The semaphore wait has the same operational significance as the function test_and_set. The names of the functions signal and wait have mnemonic meaning: signal is associated with a 'go' to a process and wait is self-explanatory: if the semaphore has value 0, the process must wait for a signal. If several processes are waiting for the same signal, only one of them may continue execution when signal is given. Depending on the implementation, the processes may wait in an ordered 'First In, First Out' queue or also be selected at random to proceed. The semaphore alone does not imply a given wait and execution order. One semaphore variable is sufficient for access coordination, compared with the different flags of the preceding examples. The processes executing wait are put in the waiting queue and do not have to consume CPU time to test the state of the semaphore. The operating system releases a process when signal is executed. With the use of semaphores, the two processes can access the common resource in an ordered manner. No unnatural bonds are introduced: if one process runs faster than the other one, it will just access the resource more often in a given time interval. A process is forced to wait for the other one only when the latter is in the protected area. Liveness is also guaranteed. If a process should for any reason stop running, provided this happens outside the protected area, the other is not hindered from continuing its execution.

10.4.2 Synchronization

Chapter 10. Realtime Control Platform

The semaphore can help in synchronizing related activities. For instance, if a process has to operate on data only after this has been read from an external port, the code can have the following aspect:

Process read data while true do begin (* get new data *) signal(data_available); end;

Process change data while true do begin wait(data_available); (* process new data *) end;

This solution has the advantage that, if the data processing algorithm is not ready with execution and new data is available, the presence of the data is indicated with a semaphore value higher than 0. The processing routine can then catch up later with the lost data. Synchronization errors due to incorrect use of semaphores may be difficult to trace. A process not executing a wait instruction can enter a protected region together with another process, leading to unforeseeable results. Of course, it cannot be said that such an error will show up during testing, and it may never even happen during the whole lifetime of a system. It is easier to find the opposite error: a missing signal operation should, at a certain point, lead at least one process to halt, which is promptly detected. A compiler does not usually have the possibility of checking whether semaphores are used correctly, i.e. if wait operations are matched in other points by signals, and if the semaphores in programs is arbitrary in the same way as other instructions, and depends on the algorithm logic. The burden to verify the correctness of the code lies, then, with the programmer. The use of structured programming methods helps considerably in this task.

10.4.3 An Example of Resource Protection: the Circular

Chapter 10. Realtime Control Platform

Buffer
A very important problem with an elegant solution based on event variables is the circular or bounded buffer (Figure 10-8). A circular buffer is a finite memory area used for data exchange between two or more processes. Applications of the circular buffer are found in communication problems, where the relative speeds of the transmitting process, the communication channel and the receiving process are different. The processes operating on the circular buffer are of two kinds: producer and consumer. The producer writes data into the buffer and the consumer reads data out of it. Producer and consumer must work independently from each other. Both have bounds: the producer can operate only when it has sufficient space at its disposal to insert new data and the consumer may read data only if this is present in the buffer. The producer must stop when the buffer is full, the consumer when the buffer is empty. The circular buffer is a clear example of a common resource for which the normal protection rules hold: when a process writes or reads data, the other must wait. The buffer is protected with one semaphore.

Figure 10-8 The circular buffer.

10.5 PROCESS COMMUNICATION: MONITOR, MAILBOX, RENDEZVOUS

Chapter 10. Realtime Control Platform

When several processes work in mutual cooperation, they need to exchange information. A multitasking operating system must provide an adequate method for this purpose. Data exchange should be transparent for the processes, in other words, it should not influence the data that have to be transferred. The data and the communication format should be defined within the processes and not depend on the particular communication method used.

10.5.1 Common Memory Areas

A first method for data exchange is the use of common memory areas where different processes have access to read and write. These memory areas are common resources to be protected, e.g. with semaphores, as we have already seen in the case of the bounded buffer. The main advantage of common memory areas is that access to them is direct and immediate apart from semaphore wait operations. The areas can be easily organized for structured data exchange: a process might write fields one by one and another process read whole records at a time. On the other hand, common memory areas have to be located at known addresses in primary memory. This is not difficult to do in assembler but is much trickier in high level languages if the language does not allow direct access to absolute memory locations.

10.5.2 Monitors
The 'classic' method for resource protection and interprocess communication is the monitor. Monitors are a theoretical construct introduced to simplify the writing of programs that exchange messages with each other or which need to be synchronized. The monitor consists of a reserved data area and associated procedures with exclusive right to operate on the data. External procedures are not allowed to access the monitor data area directly, but have to call monitor procedures; in its turn, the monitor gives service to only one external procedure at a time. It is the responsibility of the operating system to check that execution of a monitor procedure is not interrupted by another procedure from the same monitor. In this way, the monitor can guarantee that execution of one called procedure is completed before another procedure has access to the same data area. Monitors are implemented as critical regions with their reserved access routines. Internally monitors use semaphores to control access to their own data areas. The main advantage of

Chapter 10. Realtime Control Platform

monitors is that the details of data protection and task synchronization are left to the operating system. Monitors have been proposed in some multitasking languages (e.g. Concurrent Pascal), but they are not implemented in any commonly used programming language. It is often possible to build one's own monitor structures in programming languages like C and Pascal, when a protection and synchronization mechanism is available. In such a case thorough testing of the monitor procedures is imperative before using them.

10.5.3 Mailboxes
A different communication method that allows data exchange and process synchronization at the same time is the mailbox. A mailbox is a data structure oriented to messages which can be deposited and collected (Figure 10-9). Different mailboxes may be defined within the same system to allow the exchange of different types of messages. In many operating systems (e.g. VAX/VMS) mailboxes are considered to be logical files and the access procedures are similar to those that access physical store devices. The allowed operations on mailboxes are: creation, opening, message writing, message reading, closing, deleting. Mailboxes do not have an independent structure. They are located in central memory or on disk, and exist only as long as the system is powered up and operating. If they are physically located on disk, mailboxes are classified as temporary files, to be deleted at system shutdown. Mailboxes do not have generic identifiers or names; they are labelled with logical identifiers (most often numbers) defined when they are created. All processes that use mailboxes address them with their logical identifiers.

Figure 10-9 Mailbox operation.

Chapter 10. Realtime Control Platform

10.5.4 The Rendezvous

The rendezvous (French for 'meeting') is a function for both synchronization and intertask communication implemented in the programming language ADA. The rendezvous is an asymmetrical operation: one task requests a rendezvous and the other declares that it is ready to accept it. The task requesting the rendezvous operation must know the name of the task to call, while the called task does not need to know who the caller is. The principle is the same as for a subroutine call, or a blind date. The rendezvous works as follows. The task to be called has an interface toward other processes, called an entry point. The entry point is associated with a parameter list where single parameters are qualified as in, out and in out, depending on whether they are input or output for the routine. Inside the called task, one or more accept instructions show where the parameters of the external calling process must be passed. The calling task and the task to be called execute independently. When one of the tasks reaches its accept or entry instruction, it has to wait. When the other task has also reached the corresponding instruction, the rendezvous takes place. The called task continues execution with the instructions in the accept block, while the other waits. When the called task reaches the end of the accept block, both tasks can freely continue execution. Unlike the semaphore, the rendezvous is a synchronous function: both tasks have to stop at the meeting point and, only after both have reached it, may execution continue. Different tasks may refer to the same entry call. If more entries are called than can be accepted by the system, the tasks are put in an ordered wait queue where precedence is given to the task which waited longest ('First In First Out' order). The other tasks must wait until the called task again reaches its accept instruction. The rendezvous combines data transfer (via the parameter list) with task synchronization. Even synchronization alone is possible, if the parameter list is omitted.

10.5.5 Comparison of the Methods for Synchronization and Communication

The main problems related to concurrent programming, mutual exclusion, synchronization and interprocess communication may seem to be distinct, but they are in effect equivalent. A synchronization method can be used to implement mutual exclusion and communication functions. Similarly, with a method of interprocess communication it is possible to realize synchronization and mutual exclusion functions.

Chapter 10. Realtime Control Platform

The relation among the principles is of practical importance when a system offers only one method and the others have to be derived from it. Message passing and access to common memory areas is slower than the control and update of semaphore and event variables, and involves data processing overhead. For each function, the most straightforward implementation method should be chosen and strange constructs should be avoided as much as possible. When it is possible to choose from among different synchronization and communication functions, the function most apt to solve the specific problem should be used; the resulting code will be clearer and probably even faster. It is very important to consider how efficiently the solutions are implemented in practice in the actual software environment.

10.6 METHODS FOR REAL-TIME PROGRAMMING

Real-time programs differ from sequential programs for the following reasons:
q

The execution flow is not only determined by the processor but also by external events Normal programs act on data; real-time programs act on data and on signals. A real-time program may explicitly refer to the time.

There are timing constraints. Failure to compute a result within a specified time may be just as bad as computing a wrong result (the right data too late is wrong data). A typical predictable response time of 1 ms is generally required, in some cases even 0.1 ms may be necessary.
q

The result of a real-time execution depends on the global state of a system and cannot be predicted beforehand. A run is not terminated when the input data has ended. A real-time process waits for new data to be available.

The particular aspects of real-time programming require the use of special techniques and methods, which are not necessary in sequential programming. These techniques are mainly related to control of program execution flow from the external environment and from time.

Chapter 10. Realtime Control Platform

The most important of them are interrupt interception, exception handling and the direct use of operating system functions.

10.6.1 The Programming Environment

Before examining the issues related to real-time programming, we have to consider the environment where the programs will run. A typical real-time environment is a minicomputer, a bus system, a PC or a board-based microcomputer system connected with the outside world via hardware interfaces. The software for a real-time system might range from ROM-stored routines to complex operating systems allowing both program development and execution. In large systems, development and execution take place on the same machine. Smaller systems might not be able to support the development tools; the programs may have to be developed on more powerful machines and then downloaded to the target system. A similar case is given by firmware, software embedded in electronic appliances during their manufacture. Firmware is hard-coded in read-only memory (ROM); it is developed on a different machine from where it is run. The first action for a programmer is to become familiar with the programming environment and the software tools available. The issues to be faced will range from datatype representation in hardware and software, leading to the discovery that some systems order bits in one direction and some in another, some collocate data straight in memory and others use "backward storage', where the low level byte of a word gets a higher memory address than the high level byte. The number of such issues is very high and the attentive programmer knows how to separate general data and code structuring from the technicalities of the actual implementation machine. It is essential to become acquainted early on with the functions provided by the actual environment and define alternatives. For example, the microprocessor Motorola 68000 has the function test_and_set in its instruction set, so that intertask communication can be implemented via shared memory areas. The VAX/VMS operating system offers mailboxes, and process synchronization can be implemented by a message-passing mechanism. As many multitasking and real-time systems are developed by programmer teams, clarity is required from an early stage on which techniques to use. Of great importance is the structuring of hardware and software resources, that is, the assignment of bus addresses and interrupt priority levels for the interface devices. Hardware address definition depends little on software development, so that it can be handled at an early stage. Relative service priorities depend on the type of hardware and the functions to be

Chapter 10. Realtime Control Platform

performed. Their definition should not be postponed until coding time, otherwise conflicts between program modules and risk of deadlock are unavoidable consequences. The software should be built as for an operating system: in a modular and layered fashion, as this considerably simplifies the construction of complex systems. The main objects of attention are the interfaces rather than the content of single modules. It is very important to define with precision interfaces or interaction points between the modules. These points are used for synchronization and communication between the processes. For the tasks to exchange information in shared memory areas or with the help of messages, the exact area structure and message format must be defined in advance. This does not mean that changes in their definition might not take place after software development has started, only that the later they are done, the more expensive they will be in terms of code rewriting, testing, etc. On the other hand, it is to be expected that some changes will be made anyway in the course of software development, as insight into the problem increases with progress on the work.

10.6.2 Program Structure

Real-time programming is a special form of multiprogramming in which, besides the development of cooperating tasks, attention has to be dedicated to the timing issues of the system interacting with the external world. The principal feature of real-time programs is that they must always be running and never halt. If they are not currently running, they are idle and wait to be resumed via an interrupt or event. Error situations which could lead to the arrest and abort of a process must be recognized in time and corrected from within the process itself. The major steps in the development of a real-time system are easily identified. Initially, the problem is analysed and described. The system functions have to be divided into elementary parts, and a program module (task) is associated with each of them. For instance, the tasks for the control of a robot arm could be organized as follows:
q

Read path data from disk. Compute next position. Read actual position from sensors. Compute appropriate control signal for positioning. Execute control action. Verify that reference and actual positions are within the allowed range.

Chapter 10. Realtime Control Platform

q

Accept data from operator. Stop on emergency (asynchronous command, interrupt driven).

The tasks are sequential programs. They have the aspect of closed loops repeating indefinitely, continuously processing the data and the signals at their input. At some point in the code there is usually an instruction to make the loop wait for an external event or for a given time. The code is structured in such a way that the end instruction is never reached: while true do (* repeat forever *) begin (* handling routine *) wait event at ^2,28 (* external interrupt *) (* handling code *) .. end; (* handling routine *) end. (* never reached *) Each module is developed indicating clearly the areas where protected resources are accessed. Entering and exiting those areas is coordinated by some method: semaphores, messages or monitor. In general, a program in a protected area must stay safe there until it leaves the area. Interruptions in the execution of the process should not influence the resources in the protected area. In this way, the chances that the module behaves correctly are increased. Memory allocation by the processes will have to be considered. If all the modules do not fit in the memory together, they will have to be divided into segments to be loaded in at request. A common technique is overlaying, where a main module permanently resides in memory and reads from disk storage overlays with code and/or parameters for some specific operations as described. In real-time systems, the processes might have to access common subroutines. In one solution, the subroutines are linked together with the separate tasks after compiling, but this means that several copies of the same code are loaded in memory.

Chapter 10. Realtime Control Platform

A different approach is to load in memory only one copy of the subroutines, but still access them from several programs. Such subroutines must be reentrant, that is, they can be interrupted and called several times without interference. Reentrant code operates only on the internal registers and on the stack; it does not address any fixed memory location. During execution, there will be one active stack for each process, so that a reentrant module shared by different processes can be interrupted at any time and restarted from a different position in its code, using a different stack. A reentrant procedure can thus be found in many different process contexts at the same time.

10.6.3 Priorities
Many of the support systems for multiprogramming have the possibility of assigning execution priorities to the different tasks. In many cases, priority assignment is dynamic, which means that the priorities may be modified by the processes as well as by the operating system. Other systems place restrictions on the definition and the later change of process priorities. The most important modules, or the ones which should have fast execution response, get higher priority. It is necessary to pay attention to the conventions in the system used, whether highest priority is associated with a higher or lower numerical value. Priorities have a relative meaning and make sense only if they are different from one module to the other.

10.6.4 Interrupt and Exception Handling

Real-time systems interact with the external environment via hardware interfaces. Access to the interfaces and to external data is made either on request (polling) or via interrupts. In polling, the CPU asks all interfaces in succession whether they have new data to report. If this is the case, the program must fetch the data from the input channel and process it. In polling, attention must be paid to the device polling order and how often polling takes place. With interrupts, request for attention comes from external devices when new data is available. Interrupts are asynchronous events with respect to the running process and require immediate attention. On reception of an interrupt signal, the processor stops, saves the context of the process currently executing, reads from a table the address of a service routine for the interrupt and jumps to it (Figure 10-10). The service routine is called interrupt handler.

Chapter 10. Realtime Control Platform

When the CPU transfers control to an interrupt handler, it might save only the pointers to the code area of the running process. It is the duty of the interrupt handler to save, in temporary buffers or on stack, all registers it is going to use and restore them at the end. This is a critical operation, and it might be necessary to disable interrupt servicing under execution of the first instructions of the handler in order to avoid the handler itself being interrupted in turn. In interrupt management a very important factor is the response time, which should obviously be as little as possible. The response time is the sum of the interrupt latency (how long it takes for the interrupt to get attention) and the time needed for a context switch, until the interrupt handler actually runs. The typical system load also plays a role. If the workload is so distributed that the CPU has to service many interrupts at the same time, new ones will have to be queued until the CPU is available. Interrupt service routines should be as compact and short as possible. If a complex action is needed following an interrupt, it is better if the action is performed by a regular process. The interrupt service routine should do only the minimum necessary, for example, get an input value and then pass a message to the other routine, signalling that an interrupt has occurred and service is requested. It is always good practice to write reentrant code for system routines and for interrupt handlers. In this way, conflicts are avoided in case a handler is interrupted and called again before it has terminated its execution in the first context. A problem similar to interrupt servicing is reaction to exceptions, i.e. unusual conditions that result when the CPU cannot properly handle the execution of an instruction and that hinder the normal continuation of a process. Examples of exceptions are division by zero and addressing a non-existing memory location. Names for different kinds of exceptions are also traps, faults and aborts.

Chapter 10. Realtime Control Platform

Figure 10-10 Interrupt handling procedure.

Chapter 10. Realtime Control Platform

The common handling of exceptions by an operating system is the termination of process execution and indication of the error situation with messages written in clear text on the device used for the output messages. While acceptable in interactive multiuser sequential processing, in real-time systems the abrupt halt of a process must be avoided. Think about the possible consequences if a microprocessor-controlled fly-by-wire or car automatic braking system (ABS) should halt because of an unexpected divide-by-zero exception. In real-time systems all possible exceptions should be analysed beforehand and appropriately handled. A very tricky aspect of exception handling is the verification that an exception does not arise again. Put another way, exception handling must address the cause and not the symptoms of the abnormal situation. If an exception is not handled correctly, it may arise again prompting the processor to jump to its specific handling module. For instance, the divide-by-zero exception handler must check and modify the operands and not just resume operations to the point before the fault took place. This would lead to an indefinite loop. The effective memory address of any program module is known only at loading time. At system start-up, a module writes the memory addresses where the interrupt handlers are loaded in the interrupt service table. The interrupt routines are then accessed by referencing this table. Exception handling modules are written in a fashion similar to interrupt handlers. Their addresses are put in the interrupt address table at predefined locations. The possible exceptions and the pointer storage locations depend on the actual system.

10.6.5 Time-related Functions and Time Efficiency

Real-time processes may refer to time waiting for some interval or until a given time. These functions usually have the form: wait(n) and wait until (time) (time == hours, minutes, seconds, ms) (n = time in seconds or milliseconds)

When one of these functions is executed, the operating system puts the process in a waiting queue. After the requested time has elapsed, the process is moved from the waiting queue to the ready queue. The worst, but not uncommon, method to solve a 'time-waiting' problem is to introduce a

Chapter 10. Realtime Control Platform

closed loop to check the system time variable in the so-called busy-wait: repeat (*do nothing*) until (time = 12:00:00);

In general, these active waiting loops are nothing else but a waste of CPU time and should be avoided. But there are cases where reality looks different. In a system where an A/D conversion takes 20 s and a process switching operating 10s, it is more economic to run as busy waiting for the 20s before new input data is fetched than to start the task exchange procedure implicit in a 'well-behaved' wait operation. Each case is judged on its own; obviously they require advanced system knowledge and the correct feel. An important aspect of processes started periodically (such as filtering or regulation algorithms) is the accumulated time error. This depends on the fact that a process is not executed immediately after it is moved out of the waiting queue but has to wait for different time intervals in the queue of executable processes until its execution turn arrives (Figure 7.12). Requested and real execution time are not the same.

Accumulated time errors can take place if the running time for a new activity is computed as: new execution time == end of old execution time + interval

The latter is an example of an instruction like wait 10 seconds written at the end of a loop. The correct solution is obtained by using the equation: new execution time == old reference execution time + interval

The principle appears from Figure 10-12, where the nominal times are drawn on the x axis. As absolute time is taken as reference, accumulated time errors are avoided. Running time efficiency is one of the most important aspects in real-time systems. The processes must execute quickly and compromises between good and structured versus time-

Chapter 10. Realtime Control Platform

efficient code often have to be made. It is a fact of life that if short-cuts are needed to achieve some result, they will be taken anyway. If they can not be avoided, good documentation on what is done and why is imperative.

Figure 10-12 (a) The wrong way to execute periodic tasks (it leads to accumulated time errors); (b) the correct solution (it does not lead to accumulated time errors).

End