`

 

 


`Carnegie Mellon University
`   
`Research Showcase
`
`+/0'010# $,. ,73.# #/#.!&
`Institute for Software Research
`
`!&,,) ,$ ,*-10#. !'#+!#
`School of Computer Science
`
`  
`
`1—1—1992
`
`$    " 
`The Chimera H Real-Time Operating System for
`    
`Advanced Sensor—Based Control Applications
`   !
`David B. Stewart
`
`  #
`Donald E. Schmitz
`
`


`
`Pradeep Khosla
`     -(&,/)!*1#"1
`Carnegie Mellon University, pkhosla@cmu.edu
`
`,)),3 0&'/ +" ""'0',+) 3,.(/ 0 &8-.#-,/'0,.4!*1#"1'/.
`Follow this and additional works at: http: / /repository.cmu.edu/isr
`
`#!,**#+"#" '00',+
`Recommended Citation
`0#3.0 2'"  !&*'05 ,+)"  +" &,/) ."##- 6# &'*#.  #)'*# -#.0'+% 4/0#* $,. "2+!#" #+/,.
`Stewart, David B.; Schmitz, Donald E.; and Khosla, Pradeep, "The Chimera II Real-Time Operating System for Advanced Sensor-
`/#" ,+0.,) --)'!0',+/
` 

    
` -#.


`Based Control Applications" (1992). Institutefor Software Research. Paper 613.
`&8-.#-,/'0,.4!*1#"1'/.


`http: //repositorycmuedu/isr/613
`
`6'/ ,.('+% -#. '/ .,1%&0 0, 4,1 $,. $.## +" ,-#+ !!#// 4 0&# !&,,) ,$ ,*-10#. !'#+!# 0 #/#.!& &,3!/# 0 &/ ##+ !!#-0#" $,.
`This Working Paper is brought to you for free and open access by the School of Computer Science at Research Showcase. It has been accepted for
`
`'+!)1/',+ '+ +/0'010# $,. ,73.# #/#.!& 4 + 10&,.'5#" "*'+'/0.0,. ,$ #/#.!& &,3!/# ,. *,.# '+$,.*0',+ -)#/# !,+0!0 .#/#.!&
`inclusion in Institute for Software Research by an authorized administrator ofResearch Showcase. For more information, please contact research—
`/&,3!/#+".#3!*1#"1
`showcase@andrew.cmu.edu.
`
`Page 1 of 22
`Page 1 of 22
`
`ABB Inc.
`ABB Inc.
`
`EXHIBIT 1009
`
`EXHIBIT 1009
`
`

`

`This paper appeared is a draft copy of the article of the same name that appeared in IEEE Transactions on Systems, Man, and Cybernetics, Vol. 22,
`No. 6, pp. 1282-1295, Nov/Dec 1992. Unfortunately the published article, as it appeared in the journal, is not available on-line.
`
`The Chimera II Real-Time Operating System
`for Advanced Sensor-Based Control Applications
`
`David B. Stewart, Donald E. Schmitz, and Pradeep K. Khosla
`
`Department of Electrical and Computer Engineering
`The Robotics Institute
`Carnegie Mellon University
`Pittsburgh, PA 15312-3890
`
`Abstract: This paper describes the Chimera II Real-time Operating System, which has been developed for advanced
`sensor-based control applications. It has been designed as a local operating system, to be used in conjunction with a
`global operating system. It executes on one or more single board computers in a VMEbus-based system. Advanced
`sensor-based control systems are both statically and dynamically reconfigurable. As a result, they require many special
`features, which are currently not found in commercial real-time operating systems. In this paper, we present several
`design issues for such systems, and we also present the features we have developed and implemented as part of
`Chimera II. These features include a real-time kernel with dynamic scheduling, global error handling, user signals,
`and two levels of device drivers; an enhanced collection of interprocessor communication mechanisms, including glo-
`bal shared memory, spin-locks, remote semaphores, priority message passing, global state variable tables, multipro-
`cessor servo task control, and host workstation integration; and several support utilities, including a UNIX C and math
`libraries, a matrix library, a command interpreter library, and a configuration file library. Chimera II is currently be-
`ing used with a variety of systems, including the CMU Direct Drive Arm II, the CMU Reconfigurable Modular Manip-
`ulator System, the Troikabot System for Rapid Assembly, and the Self-Mobile Space Manipulator.
`
`I. INTRODUCTION
`Advanced sensor-based control applications, such as robotics, process control, and intelligent manufacturing systems
`have several different hierarchical levels of control, which typically fall into three broad categories: servo levels, su-
`pervisory levels, and planning levels. The servo levels involve reading data from sensors, analyzing the data, and con-
`trolling electromechanical devices, such as robots and machines. The timing of these levels is critical, and often
`involves periodic processes ranging from 1 Hz to 1000 Hz. The supervisory levels are higher level actions, such as
`specifying a task, issuing commands like turn on motor 3 or move to position B, and selecting different modes of con-
`trol based on data received from sensors at the servo level. Time at these levels is a factor, but not as critical as for the
`servo levels. In the planning levels time is usually not a critical factor. Examples of processes at this level include gen-
`erating accounting or performance logs of the real-time system, simulating a task, and programming new tasks for the
`system to take on. In order to develop sensor-based control applications, a multitasking, multiprocessing, and flexible
`real-time operating system (RTOS) is needed.
`An RTOS can be subdivided into several parts, including the real-time kernel, the multiprocessor support, the file sys-
`tem, and the programming environment. The real-time kernel provides local task management, scheduling, timing
`primitives, memory management, local communication, interrupt handling, error handling, and an interface to hard-
`ware devices. The multiprocessor support includes interprocessor communication and synchronization, remote inter-
`rupts, access to special purpose processors, and distributed task management. The file system provides access to
`secondary storage, such as disks and tapes, and to local-area-networks. The programming environment provides the
`tools for building applications; it includes the editor, compiler, loader, debugger, windowing environment, graphic in-
`terface, and command interpreter (also called a shell). The level of support provided for each part of the operating sys-
`tem (OS) varies greatly among RTOS.
`
`Page 2 of 22
`
`

`

`To appear in IEEE Transactions on Systems, Man, and Cybernetics
`
`2/21
`
`In this paper, we present the Chimera II Real-Time Operating System, which has been designed especially to support
`advanced sensor-based control applications. Chimera II is designed as a local OS within a global/local OS framework,
`as shown in Figure 1. In such a framework, the global OS provides the programming environment and file system,
`while the local OS provides the real-time kernel, multiprocessor support, and an interface to the global OS. For many
`applications the global OS may be non-real-time, such as UNIX or Mach. However, the use of a real-time global OS
`such as Alpha OS [7] and RT-Mach [30] can add real-time predictability to file accesses, networking, and graphical
`user interfaces.
`Most commercial RTOS, including iRMX II [5], OS-9 [13], and pSOS+ [24], do not use the global/local OS frame-
`work, and hence they provide their own custom programming environment and file system. The environments, includ-
`ing the editors, compilers, file system, and graphics facilities are generally inferior to their counterparts in UNIX-based
`OS. In addition, since much development effort for these RTOS goes into the programming environment, they have
`inferior real-time kernels as compared to other RTOS. Some commercial RTOS, such as VRTX [20] and VxWorks
`[32], do use the global/local OS framework. However, as compared to Chimera II, they provide very little multipro-
`cessor support, and their communications interface to the global OS is limited to networking protocols, thus making
`the communication slow and inflexible. The commercial RTOS only provide basic kernel features, such as static pri-
`ority scheduling and very limited exception handling capabilities, and multiprocessor support is minimal or non-exis-
`tent. Previous research efforts in developing an RTOS for sensor-based control systems include Condor [18], the
`Spring Kernel [25], Sage [21], Chimera [23], and Harmony [3]. They have generally only concentrated on selected
`features for the real-time kernel, or were designed for a specific target application. Chimera II differs from these sys-
`tems in that it not only provides the basic necessities of an RTOS, but also provides the advanced features required for
`implementation of advanced sensor-based control systems, which may be both dynamically and statically reconfig-
`urable.
`
`II. DESIGN ISSUES
`Advanced sensor-based control systems should be dynamically reconfigurable, even for the simplest of applications.
`Consider the example of a robotic manipulator which is required to move an object whose location is known. This task
`can be broken up into three separate phases: pick up object; move to new position; put down object. When the manip-
`ulator is picking up the object, it must use force control for contacting the object, and gripper control to properly pick
`up the object. To move the object a different controller is required for the free motion phase. Possibly vision processing
`is also required to track the object’s target location. To put down the object, force control and gripper control is again
`needed. The set of modules executing and the sensors required during each phase is different. Some of the modules
`and sensors are shared by the different phases, while others must be dynamically changed. As applications become
`more complex, the number of possible configurations also increases.
`Advanced sensor-based control systems should be implemented on open-architecture hardware, so that new sensors
`and additional processing may be incrementally added to the system to increase the system’s intelligence. In addition,
`the hardware and set of software configurations may have to be changed to support a different class of applications.
`Thus advanced sensor-based control systems must also be statically reconfigurable.
`Several design issues, discussed in detail below, were considered in developing Chimera II, an RTOS for advanced
`sensor-based control systems that are both statically and dynamically reconfigurable.
`A. Programming Environment and File System
`The basic functionality found in all RTOS includes the programming environment, the file system, and the real-time
`kernel. The programming environment is required to quickly develop, debug, and maintain code. The basic require-
`ments for the environment are an editor, a high-level language compiler, a linker, and a loader. The file system is re-
`quired to store code and data on secondary storage, and to electronically transfer information to other systems. In order
`to provide all of the advantages of the full-featured programming environments and file systems of today’s UNIX
`workstations, we adopted the global/local OS framework, and developed Chimera II as a local OS. Chimera II then
`requires a global OS to operate as the host, which makes all of the global OS’s programming environment and file sys-
`tem features available to Chimera II. Given such a framework, we have developed a powerful interface between the
`host workstation and real-time environment, as described in Section III.B.
`
`Page 3 of 22
`
`

`

`To appear in IEEE Transactions on Systems, Man, and Cybernetics
`
`3/21
`
`B. Open Architecture Real-Time Hardware
`A typical hardware configuration for advanced sensor-based control applications may consist of multiple general pur-
`pose processors, possibly on multiple buses. The system may contain special processing units, such as floating point
`accelerators, digital signal processors, and image processing systems. The system will also include interfaces to several
`sensory devices, such as force sensors, cameras, tactile sensors, and range finders to gather data about the environment,
`and a variety of control devices such as actuators, switches, and amplifiers to control electromechanical equipment.
`We have implemented Chimera II around the VMEbus [16], since it is the most popular bus standard. However, much
`of the design of Chimera II is independent of the target hardware architecture, and hence can be used with other archi-
`tectures.
`Figure 2 shows a typical hardware configuration. General purpose processing is provided by commercially-available
`single board computers, which we call real-time processing units (RTPUs). We have chosen to support the Motorola
`MC680x0 family of general purpose processors because of their popularity and their one-to-one mapping of hardware
`signals with the VMEbus signals [15]. The design of Chimera II allows other processor-based RTPUs, such as the Intel
`80x86 and SPARC families, to also be used; however, we currently have not ported any software to those platforms.
`Any VMEbus-based I/O device or special purpose processor can be incorporated into Chimera II, by using the two-
`level device driver support offered by our OS.
`C. Real-Time Kernel
`The real-time kernel must include all the basic features found in any RTOS. These include task management, memory
`management, local shared memory, local semaphores, timer access, and hardware independence. Task management
`includes actions such as creating, destroying, blocking, waking up, setting priorities, and scheduling of concurrent
`tasks. Memory management is the allocation and deallocation of physical memory. We do not consider virtual memory,
`because we are not aware of any method to do paging in real-time. Local shared memory allows tasks on the same
`RTPU to share memory. Local semaphores provide basic synchronization for tasks on the same RTPU. Timer access
`allows the execution of tasks to be controlled by time. Hardware independence is a virtual machine layer, which allows
`user software to use the hardware without having to program hardware specific code. The level of hardware indepen-
`dence provided by an OS varies. We have developed an expanded real-time kernel suitable for reconfigurable systems.
`In addition to the basic kernel functions, our kernel also provides dynamic scheduling, two levels of device drivers,
`built-in control of timers, and global error handling. Details of the Chimera II kernel are given in Section III.A.
`D. Interprocessor Communication and Synchronization
`Most RTOS give very few mechanisms for interprocessor communication (IPC) and synchronization. The mechanisms
`available generally include support for an atomic read-modify-write instruction for limiting access to critical sections,
`and some form of message passing for higher-level communication. The VMEbus by default offers shared memory;
`however, most RTOS do not make any provisions for allocating that memory, or for automatically performing the ad-
`dress calculations required to access different parts of memory on the VMEbus. As a result, programs which use any
`of these mechanisms become bound to a single processor. The same code cannot execute on a different processor, with-
`out modification of VMEbus addresses, or in the case of message passing, modifying the names of the source and des-
`tination of the messages. In a reconfigurable system, modules must be designed such that they are independent of the
`target RTPU; hence these methods are not satisfactory. Second, these mechanisms do not provide all the tools desirable
`for quickly developing multiprocessor applications. In Section III.B. we describe the enhanced IPC and synchroniza-
`tion mechanisms developed in Chimera II, including global shared memory, spin-locks, remote semaphores, priori-
`tized message passing, global state variables, and multiprocessor task control.
`E. Predictability
`The primary concern in a real-time system is not that it is fast, but rather that it is predictable. A fast system with un-
`predictable behavior can cause serious damage. In theory, the rate monotonic algorithm [10] is used to ensure predict-
`able execution. However, this static scheduling algorithm is not suitable for dynamically reconfigurable systems and
`does not provide the CPU utilization achievable with dynamic scheduling algorithms [11]. We have developed the
`maximum-urgency-first algorithm to provide a predictable dynamic scheduling algorithm [26]. This algorithm has been
`implemented as the default scheduler for Chimera II. Support for the rate monotonic algorithm, as is provided in most
`RTOS, is also available with the default scheduler.
`Page 4 of 22
`
`

`

`To appear in IEEE Transactions on Systems, Man, and Cybernetics
`
`4/21
`
`Most real-time scheduling theory concentrates on ensuring that tasks always meet their deadlines. However, nothing
`is said about what happens to tasks that fail to meet deadlines. In addition, even though a task can meet all deadlines
`in theory, abnormalities in the implementation may cause the task to miss its deadline in practice. In Chimera II we
`have addressed this issue by designing a deadline failure handling mechanism, which allows an exception handler to
`be automatically called when a task fails to meet its deadline. Possible error handling includes aborting the task and
`preparing it to restart the next period; sending a message to some other part of the system to handler the error; perform-
`ing emergency handling, such as a graceful shutdown of the system or sounding an alarm; maintaining statistics on
`failure frequency to aid in tuning the system; or in the case of iterative algorithms, returning the current approximate
`value regardless of precision. Details of the Chimera II scheduler and deadline failure handling are included in
`Section III.A.
`Deadline failures account for only one of the many types of errors which may occur in a system. Deadline failures are
`unique in that the errors are a function of time. Other errors that may occur in a system include hardware failures, soft-
`ware bugs, invalid data, invalid states, and processor exceptions. These errors may occur at any time, and are often
`detected within the user’s code through the use of consistency if-then statements. The most typical method of dealing
`with these errors is to have the routine detecting the error to either handle it itself, or to return an error value, such as
`–1. Unfortunately, in a hierarchical software architecture, this method has two major problems. First, the exception
`handling code is embedded within the application code, making the code inflexible and difficult to maintain. Second,
`if an error occurs at the lowest level of the architecture, and it is only to be handled by a higher level module, then the
`error must be continually passed up through the intermediate software levels. This method is both cumbersome to code,
`and is also very inefficient, in that the time to enter the exception handling code requires the additional overhead of
`propagating the error through multiple hierarchical levels. In Chimera II we have developed a global error handling
`mechanism, which allows exception handling code and main program code to be coded independently. Details are giv-
`en in Section III.A.
`F. Modular and Reusable Software
`In order to save on development time and make software more maintainable, it is generally accepted that applications
`should be designed in a modular fashion, and the software modules should be reusable. Chimera II extends this ideol-
`ogy to practice, by providing the tools which make it possible to quickly develop modular and reusable software. First,
`all communication mechanisms are processor transparent, and hence modules can be developed without knowledge of
`the final target hardware architecture. Second, the two-level device drivers supported by Chimera II provide a standard
`interface not only to I/O devices, as offered by other RTOS, but also to sensors and actuators. Third, the servo task
`control mechanism forces the programmer to develop code as reconfigurable, hence resulting in reusable modules.
`Each module can then execute on any RTPU at any frequency, and all modules can be controlled by a single task. The
`modules form a library of modules, any of which can be used in later systems without the need for recompiling any
`parts of the code. The intercommunication between the modules is handled automatically using a high-performance
`global state variable table mechanism. The servo task control mechanism and global state variable table are described
`in Section III.B. Details on developing a library of reusable modules can be found in [27].
`G. Libraries
`The usefulness of an operating system does not only lie in the features given, but also on the supporting libraries, which
`save on application development time. Like most other RTOS, Chimera II provides the standard UNIX C and math
`libraries. It also provides a concurrent standard I/O library (stdio), which is suitable for using the stdio facilities in a
`multiprocessor environment. In addition, several other libraries are provided, which are generally not found in other
`OS. These include a matrix math library, a command line interpreter library, and a configuration file support library.
`These libraries provide utilities which are often required by advanced sensor-based control applications. More details
`on these libraries are in Section III.C.
`
`III. SOFTWARE ARCHITECTURE
`The Chimera II software is divided into two distinct parts: 1) Code that runs on the RTPUs, and 2) Code that runs on
`the host workstation.
`
`Page 5 of 22
`
`

`

`To appear in IEEE Transactions on Systems, Man, and Cybernetics
`
`5/21
`
`Figure 3 shows the data flow diagram for code that runs on the RTPUs. On each RTPU, user tasks execute concurrently,
`communicating with each other through local shared memory and local semaphores. They also have direct access to
`local I/O devices, and can communicate with other processors using any of the IPC mechanisms available. Each RTPU
`has a server task which constantly monitors the express mail. The express mail is used to initialize IPC services and to
`provide access to the extended file system. The server translates symbolic names into pointers, and performs any nec-
`essary calculations to translate addresses within various address spaces on the VMEbus. A copy of the Chimera II ker-
`nel executes on each RTPU. The kernel provides a real-time multitasking environment for executing the tasks
`concurrently.
`The host workstation is also an integral part of the Chimera II environment. Figure 4 shows the data-flow diagram for
`code that executes on the host. Three categories of processes execute on the host: the server process, console processes,
`and user processes. All processes communicate via local shared memory and semaphore facilities available in the
`host’s global OS.The host’s server provides similar functionality as the server on the RTPUs. In addition, it can access
`the host file system directly, and it includes special primitives to support the console processes. The console process
`provides the user interface which serves to download and execute programs on the RTPUs. The console process also
`provides the stdin, stdout, and stderr files for tasks executing on the RTPUs. A single console process can control all
`RTPUs within the system. However, if multiple RTPUs are using stdin, only one of them can have it active at once.
`Other tasks reading from stdin block, and send a Waiting for TTY Input message to the user’s terminal, similar to the
`way UNIX handles background processes. If multiple RTPUs require stdin simultaneously, then multiple instances of
`the console process can be created, each in a separate window on the host workstation.
`User processes are just like any other UNIX process running on the host workstation, except that an additional
`Chimera II library is linked in, allowing the process to use the Chimera II IPC package. By using this library, the host
`workstation appears as an RTPU to the other RTPUs, thus making communication between the host workstation and
`RTPUs transparent. The host processes can thus read from and write into the memory of any RTPU, send or receive
`messages, or synchronize using remote semaphores. This powerful feature allows users to create their own custom user
`interfaces, which possibly include graphics or windowing facilities offered by the host workstation.
`A. Real-Time Kernel
`One of the important goals of the kernel is to provide the required functionality at the highest performance possible.
`In our system, this is achieved by sacrificing traditional operating system features, such as virtual memory and inter-
`task security. Our basis for measuring performance is the amount of CPU time during normal execution which must
`be dedicated to the operating system functions, such as scheduling, task switching, and communication overhead. The
`major design decisions that we made in developing the Chimera II kernel are described below.
`1) Tasks: A task in Chimera II is also known as a thread or lightweight process in other operating systems. A user pro-
`gram which is downloaded into an RTPU consists of a single executable file. The kernel is supplied as a C library and
`is linked into the executable image. When a program is downloaded to an RTPU and executed, some kernel initializa-
`tion is performed, following which the user’s main() routine is spawned as a task. Any other task can then be started
`from main().
`2) Inter-task Security: Typically, all of the tasks running on a given RTPU (or set of RTPUs) are designed to cooperate.
`We have sacrificed inter-task protection, allowing one task to access the address space of any other task. This elimi-
`nates a large amount of overhead incurred in performing system calls or their equivalents. In general, inter-task security
`is desirable for two reasons: 1) to prevent multiple users or independent processes from infringing on other processes
`in the system; and 2) to contain software errors within a faulting module for better control of error handling. Although
`Chimera II is multitasking and multiprocessor, it is designed to be single user. Two totally separate control systems
`should each have their own installation of Chimera II. This is necessary if predictable execution of each system must
`be maintained. Therefore the first reason for wanting inter-task security is not applicable to Chimera II. As for contain-
`ing errors within a software module, inter-task security prevents corrupting memory of other modules, and causes the
`faulting module to abort. These types of errors typically occur due to software bugs. The global error handling mech-
`anism has some facilities for automatically detecting bugs, such as memory corruption errors or bad arguments to sys-
`tem calls, and hence provides an alternate method for handling software errors.
`3) Task Management: Chimera II provides the kernel task management features typical to all RTOS, including creat-
`ing, suspending, restarting, preempting and scheduling. In addition, Chimera II provides a different approach to han-
`Page 6 of 22
`
`

`

`To appear in IEEE Transactions on Systems, Man, and Cybernetics
`
`6/21
`
`dling task timing. Whereas other RTOS require the user to program timers, the Chimera II kernel performs all timer
`programming automatically. A pause(restart_time) routine is provided, which tells the kernel to pause the task until
`the specified restart time. The kernel schedules the tasks using virtual timers, all based on a single hardware timer. Us-
`ing this method the number of tasks in an application requiring the use of timers is not limited by the number of timers
`available on the RTPU. Therefore the user does not have to manually perform any timer hardware multiplexing, as is
`necessary with most other RTOS when there are insufficient hardware timers.
`4) Local Inter-task Communication: There is no parent/child relationship among tasks. Any task can communicate or
`synchronize with any other task either through local shared memory, local semaphores, or user signals. Within a single
`executable file, all global variables are automatically shared. Local semaphores provide high speed synchronization
`between tasks, and can be used either to provide mutual exclusion during critical sections (binary semaphores), or to
`provide synchronization among tasks (general or counting semaphores). User signals provide an alternate method of
`synchronization, allowing the receiving task to be interrupted when the signal arrives, instead of explicitly checking if
`the signal has arrived as done with the local semaphores. Any of the IPC mechanisms described in Section III.B. can
`also be used locally.
`5) Memory Management: The total address space used by all tasks on one system is limited by the physical memory
`available on the RTPU. Chimera II does not provide any virtual memory, as the memory management and swapping
`overhead not only decreases the performance of a system drastically, but it also causes the system to become unpre-
`dictable, thus violating one of the important rules of real-time systems. Chimera II provides its own version of the mal-
`loc() family of routines to allocate physical memory.
`6) Interrupt Handling: The Chimera II kernel provides the interfacing routines to easily define and install C-language
`interrupt handlers for VMEbus IRQ interrupts, local LRQ interrupts, and a user-definable number of mailbox inter-
`rupts, even if the hardware only supports one or two mailbox interrupts. Utilities are also given to enable and disable
`interrupts, and to indefinitely lock a task into the CPU for atomic or critical emergency handling code.
`7) Real-Time Task Scheduler: Chimera II supports both static and dynamic preemptive scheduling of real-time tasks.
`The default scheduler supports the rate monotonic (RM) static priority scheduling algorithm [10][11], the earliest-
`deadline-first (EDF) and minimum-laxity-first (MLF) dynamic scheduling algorithms [11][33], and the maximum-ur-
`gency-first (MUF) mixed (static and dynamic) scheduling algorithm [26]. In addition, the scheduler is designed as a
`replaceable module, allowing user-defined schedulers to easily override the default scheduler, just by linking the new
`scheduler with the application.
`The wide range of support for scheduling algorithms with the default scheduler allows Chimera II to be used in many
`applications, without being restricted by the default scheduler, as is the case with the commercial RTOS, which restricts
`the programmer to using a static priority scheduling algorithm. For example, RM is usually the algorithm of choice
`when developing a single-configuration system. EDF and MLF are used in dynamically changing systems when tran-
`sient overloads of the system are not possible, or in static systems when maximum CPU utilization is required. MUF
`is an algorithm we have designed especially for dynamically reconfigurable systems, where critical tasks can be guar-
`anteed to execute, even during transient overloads of the system [26].
`8) Deadline Failure Handling: One novel and powerful feature in Chimera II is its deadline failure handling mecha-
`nism. Whenever a task fails to meet its deadline, an optional failure handler is called on behalf of the failing task. The
`failure handler can be programmed to execute either at the same or different priority than the failing task. Such func-
`tionality is essential in predictable systems. Any of the actions specified in Section II.E. and other user-defined actions
`can be implemented using the deadline failure handling available with our MUF scheduler.
`Estimating the execution time of tasks is often difficult. For example, most commercially-available hardware is geared
`towards increasing average performance via the use of caches and pipelines. Such hardware is often used to implement
`real-time systems. As a result, the execution time cannot necessarily be predicted accurately. Under-estimating worst-
`case execution times can create serious problems, as a task in the critical set may fail. The use of deadline failure han-
`dlers is thus recommended for all tasks in a system. The Chimera II default scheduler provides this ability.
`9) Error and Exception Handling: Three types of errors may occur in an advanced sensor-based control system:
`hardware errors, state errors, and software errors [2][4]. A hardware error is either directly generated by the hardware,
`such as a processor exception (e.g. bus error), or be detected by software, as is usually the case with I/O devices. Some-
`times these errors are only transient, or can be corrected by software; other times human intervention is required to
`Page 7 of 22
`
`

`

`To appear in IEEE Transactions on Systems, Man, and Cybernetics
`
`7/21
`
`reset the hardware. State errors are software generated, generally after some form of if-then comparison. These errors
`are more abstract than hardware errors, and indicate that an invalid softw