Real-Time Operating Systems for Embedded Computing Yanbing Li’, Miodrag Potkonjak*, and Wayne Wolf" ‘Department of Electrical Engineering, Princeton University Department of Computer Science, UCLA Abstract, We survey the state-of-the-art in real-time operating sys tems (RTOSs) from the system symthesis point of view. RTOSS have a very long research history which provides important theoretical results and useful industrial imple- ‘mentations. Convergence of applications, technology, and market trends of embeded systems implies a strong need for new generation of RTOS. Therefore, new system syn= thesis problem areas, notably hardware/software co-design and synthesis for systems-on-silicon (SOS), are opening up new avenues for RTOS research and: development. This paper starts with a survey of classical academic and indus- trial RTOS work and continues with a survey of recent results related to co-design and design systems-on-silicon, ‘We conclude by outlining future ditections for the SOS RTOS. 1 Introduet n Recently, a convergence of applications, technology, and ‘market trends of embedded systems has resulted in drastic ‘quantitative and qualitative change in synthesis of applica- tion-specific systems. The size of average embedded con- sumer electronics applications has been approximately doubling each year. At the same time the average size, in terms of number of gates, ofthe integrated circuits has been doubling every three years, while the clock period has been steadily decreasing at just slightly lower pace. For example, the state ofthe art general-purpose processor in 1971 (Intel 4004) had 2,300 transistors and had clock rate 0.1 MHz. Today the Iatest-generation processor, the Intel Pentium-Il, has 7.5 million transistors and a clock rate of 300 MElz § ‘These trends imply that, in each new generation of technol- ‘ogy, higher levels of hardware sharing arc required, feasi- ble, and economically desirable. From the qualitative point of view, new application are characterized by high volume of data, cost sensitivity, and very short market windows. Many popular applications, such as wireless telephony, intemet browsing, and video- 388 1063-6404/97 $10.00 © 1997 EEE conferencing, are intrinsically defined by a need for high volume data management. Recent analysis of electronic ‘market clearly indicates crucial importance of considering customers spending limits and to act promptly to the changes in the market conditions®, [As a result of these trends, there is a growing consensus that the only design reuse techniques can close the fast growing ‘gap. between the potentials of semiconductor production technologies and traditional design productivity’. Software is a major element of modern reuse strategies and real-time ‘operating systems. (RTOSs) are critical components in reusable embedded software systems. ‘Tradivonally, application-specific systems have been imple- ‘mented using the algorithm-to-architecture methodology. While this was a viable option for synthesis of low com- plexity application-specific systems, it does not address needs of more complex emerging designs. Figure 1 illus- trates the new system-level synthesis flow. RTOS provides isolation and interface to application and algorithm devel- ‘gorton : hte Compton —) —> - sytem | prog interpre Conmunkation ae Memory Management a ™ rome) ows FIGURE, RTOS ts tashone of ev peeve Sh ‘oes ‘opers and compilation tools from one side and to architec ‘ure and integrate circuits designs from the other. Our goalin this paper is to analyze opportunities and challenges posed by the emerging field. RTOS have been used in many applications from car, ship, and airplane electronics to wire- less and optical communication equipment, medical instru- ‘mentations, multimedia, internet, and even home appliances, factory automation, process control, financial twansaction processing, and video games machines. Even without strict space limitations of a conference paper, it would be impossible to provide a comprehensive survey of RTOS research and industrial state-of-the-art. Rather than aim for comprehensiveness, we focus attention on a selected subset of key issues and key new directions which characterize well emerging filed of RTOS for SOS. ‘The reminder of the paper is organized as follows. We first very briefly summarize operating system basics. After that ‘we summarize the key results from the traditional RTOS research and discuss RTOS development efforts from the industrial point of view. Next, we present some of the first RTOS behavioral and system-level synthesis efforts. We conclude by outlining the directions for the merging field of system-on-silicon, in particular from RTOS point of view. 2 Preliminaries In this section we briefly outline the basic facts about real- time operating systems and systems-on-silicon. 2.1 [Real Time] Operating Systems Basics ‘An operating system is a system program which provides an interface between application programs (an often a user) and the computer hardware. They have two primary func- tions: to make the computer system convenient to use and to organize efficient and correct use of the computer resources. There are four main tasks of an operating sys- tem: process management, interprocess communication and synchronization, memory management, and input/ output (1/0) management. The process management com- ponent is responsible for process creation, process loading, and execution control, the interaction of the process with signal events, process monitoring, CPU allocation and pro- cess termination. Interprocess communication covers issues such as synchronization and coordination, deadlock and livelock detection and handling, process protection, and data exchange mechanisms. Memory management includes services for file creation, deletion, reposition, and protec- tion, YO management handles request and release subrou- tines for a variety of peripherals and read, write, and reposition programs. Real-time systems are systems where the proper functional ity assumes both the correctness of the output as well as the correct timing behavior of the system. 389 2.2 Systems-on-Silicon Iniegrated circuits with 20 millions or more transistors allow truly significant systems, such as HDTY, video cam- coder, and software radi, to be placed on a single chip. Systems-on-silicon may contain multiple CPUs, special purpose function units, and large amounts of embedded RAM. They find important uses in areas as diverse as wire- Jess, multimedia, and mechanottoaics. ‘Systems-on-silicon demand more careful design because design revisions are both costly and time-consuming. They also require very high-quality software for several reasons: the software will definitely be hard to observe and therefore debug due to pin limitations; the software may be hard to change after fabrication; and the hardware cannot be easily changed to accommodate software performance problems. Design of systems-on-silicon pose many qualitatively new problems such as intellectual property protection, debug ging using incomplete information about hardware and/or software, and one which we address here, a need for embedded operating system layer. 3 Traditional RTOS Research S FFIGURE 2. A pir of tasks ‘A real-time operating system can supply many valuable functions to an embedded application, but the central pur- pose of an RTOS is scheduling of the CPU. The application is structured as a set of processes, each of which has its ‘own program code and state consisting of register and memory values. The process is as well-known and almost universal model. Some operating systems support an addi tional level of structure known as the task. A task isa sot of processes with data dependencies between them, as shown in Figure 2. This example contains two tasks—processes which have no path of data dependencies between them are in separate tasks. A process or task may be executed per- ‘odically or aperiodically. Processes and tasks generally have some sort of temporal constraints on their behavior. The exact nature of these con- straints depends on the scheduling model, but several types ‘of temporal measurements of process/task performance are used, A deadline isthe time at which a process must finishexecution after being initiated. ‘The period of a periodic process or task is the interval between initiating successive executions ‘The RTOS considers a process to be in one of thee states: waiting, ready, and executing. In a uniprocessor system, only one process can be executing at any time, Some pro- cesses may be waiting for data or other events, Processes which are not blocked for external events but are not cur- rently executing are considered ready. The transfer of exe- cution from one process to another is called a context switch, To execute a context switch, the RTOS must save the state of the old process, determine what process will next obtain the CPU, and then set the CPU state to that pro- cess's state. Context switch overhead is non-trivial but often not a major factor in performance; scheduling policies, pro- cess partitioning, memory performance, and other factors are often more critical to obtaining good performance, Stankovi et al, provide a good survey of real-time schedul- ing techniques! There are several types of scheduling poli- ‘ies for real-time systems ‘A cooperative scheduler relies on the current process to give up the CPU before it can start the execution of nother process. Cooperative multitasking is suitable for extremely simple systems, such as digital ters with purely periodic inputs, but is not used in sophisticated ‘embedded systems. A static priority-driven scheduler can preempt the current process to start a new process. The highest-p ority ready process is always the currently executing process. Priorities are set before the system begins exe- ution. A dynamie priority-driven scheduler can redefine the process priorities at run time. The highest-priority ready process i sill the currently-executing process, but since the RTOS can redefine priorities, the scheduling policy is embodied in the dynamic choice of priorities. ‘The best-known static priorty-driven scheduling methodol- gy is rate-monotonic scheduling (RMS)*. Liu and Lay- land showed that the optimal scheduling policy for one particular category of real-time systems is 10 assign priori- fies in inverse order of deadline—the shortest-deadline pro- cess receives the highest priority. A well-known dynamic priority-driven scheme is earliest- Aeadline-irst (EDF). This policy assigns priorities based on the time left until each process reaches its deadline, with the process facing the nearest deadline receiving the highest priority. EDF results in higher CPU utilization than i possi~ be with RMS, but since priorities in an EDF system change during execution, itis more dificult to prove that an EDF 390 system meets al its deadtines under all conditions. 3.1 Recent Directions Recently, there has been a number of new RTOS- and embedded system-related research results which open new rand important development directions. We mention only a subset of them: profile-based load balancing', lottery scheduling"’, dynamic code generation’®, embedding of security and authentication mechanisms'”, jitter hiding”, verification’, and CORBAelated efforts™ Bestvarsos'* demonstrated significant advantages of using the profile-based balancing over traditional balancing tech- yues for optimization of distributed soft real-time sys- tems. Set of promising scheduling technique which address ‘a number of important issues has been also developed by utilizing randomizstion'®, There has been also efforts to censure satisfaction of real-time constraints in object ori- ented CORBA, an important first step in development of real-time large software systems. Inferno, the real-time version of the Plan 9 operating sys- tem from AT&T Bell Labs, is the first RTOS which pro- vides a number of cryptographic, authentication, and protection mechanism!”, The first techniques for jitter hid ing show significant advantages in handling relative small, variation in throughput rate”, Finally, a number of recent studies shows that a great advantages in throughput, latency, and memory requirements can be achieved by applying the dynamic code generation techniques". 4 Commercial RTOS Offerings Leading estimates that a fow tens of millions copies of RTOS have been installed, Some of large RTOS industrial players include Integrated Systems (pSOS Systems), Wind River Systems (VxWorks), Microtec Research (VRTX), Microware Systems (OS-9), Spectron Microsystems (SPOX), QNX (QNX software), Hewlett-Packard (HP-RT), Lynx Real-Time. Systems (LyaxOS). Among the most notable recent entries include Lucent (Inferno) and Eonic ‘Systems (Virtouso RTOS). Recently Microsoft entered the ‘market with their Windows-CE embedded operating sys- tems. While Windows-CE does not directly address requirements for real-time constraints, atleast one company already announce its real-time version. While traditional academic RTOS research is dominated by scheduling efforts, the industrial efforts have been mainly focused on optimization for three design metrics: memory requirements and two performance metries: context switch time and interrupt latency. Table 1 shows area requirements delay for 3 different cache configuration and five differ-cent cache sizes obtained using the Flynn's cache modeling Geesmlroce ua Jun ro ows [Direct [Ares (mmm) [2.107036 [3.807370 |13:960853 | 161,704666 Sa ase ee eee Se escape Se fsa — fess foam foomr tia fa a a THBLET. Cae eof tools!!, Table 2 show features of some of the most popular microprocessor cores. Majority of RTOS have versions Which start from afew KB and go up to several MB. Clk tecnotg| Are, | Power di. Microprocessor cores) | ts | um) | nm’) on) Cat) SeongARM 3 [ss_oas [as __[so00 [ARM fo [3s fos _|s9__[o ARM Thor Pree [27 [20 fos [oa __[esasy tsttogs. Taaior [sr [0 [oss [> [evan Esttogs.cwaoor [wo [= fos [33__| mea Esttogecweont [wo [a0 fos |v [wa DsPGrow. Oar [oo [0 fos [ua _hisoe NeGraion [wo [0 [oss [sa [aan Fro neei0 _|50_|s0 [os fis [woo Morro soond [3 [1s fos [aa [asa Fowate.ws [sar fos [rs__[oaay TABLED Sas fe a oven core Although, the state-of-the-art SRAM design reports state by factor of 2 smaller area per KB of fast memory'®!29 it is clear that in cost sensitive applications large RTOS imposes. high cost penalties. ‘The performance criteria, context switch time and interrupt latency, are highly platform dependent. For 60 MHz com- puters both metrics are usually a few microseconds. The notable exception, with respect to all three metrics is the ‘Virtuoso RTOS which claims atleast an order of magnitude reduction for all of them. ‘The state-of-the-art RTOS usually provides about 16 or ‘more scheduling priority levels, preemption mechanisms, several tasks scheduling algorithms (e.g. FIFO, round rate monotonic, earliest deadline first), file and YO support, and a sets of utility programs (eg. linkers, compil- crs, library managers, debuggers, and increasingly more often visual interfaces). ‘A good starting point for obtaining additional information about commercial RTOS offerings are the following two WWW sites: http:/es-www:bu.edulpubvicee-rts! Home.hnl and ‘tp:/imsn.yahoo.com/msn/ 391 ‘omputers_and_InterneOperating_Systems/Realtime 5 RTOS and [Computer Aided] Design Research and Development In this section, we survey the recent RTOS-telated CAD efforts. The results are mainly due to an impetus provided by two new important trends: hardware/software co-design ‘and synthesis techniques for systems-on-silicon, Recent interest in hardware/software co-design® has opened up new avenues in RTOS research. The ability to simulte- neously design the hardware platform and software allows for new trade-offs and poses new challenges in system axchitecture. The move toward systems-on-silicon, moti vated by the ability to put one or more sophisticated CPUs and embedded RAM on a single chip, will make RTOSs increasingly important over the next several years. Good design and use of an RTOS can help increase the efficiency with which scarce hardware resources are used, while a bad RTOS ean kill performance and reliability. And because systems-on-ilicon are much harder and significantly more expensive to fix than printed circuit boards, performance and reliability are at a premium, ‘The RTOS CAD efforts can be classified in four groups: behavioral synthesis results, system-level synthesis result, design studies, and theoretical and simulation efforts. Potkonjak and Wolf addressed synthesis of a system of multifunctional ASICs where individual tasks are under hard real-time constraints”, They also introduced a heuris- tic approach for the design and optimization of ASIC implementations which realize multiple computational tasks under hard real-time constraints on a single mult- functional ASIC. Kim et al. ?° developed a set of tech- niques to minimize context switching time using the behavioral synthesis techniques. ‘System-level techniques can be grouped into two catego- ries: uniprocessor and multiprocessor. One major trend in next-generation embedded systems is multiprocessors which may contain devices and special-purpose accelera- tors as well as a CPU; although these devices may not be programmable, they still allow parallel execution that must be taken into account by the RTOS. Furthermore, many ‘embedded systems include several CPUs, often of different types. Coordination between the processing elements in the system is essential for both performance and correctness. While there have been a high interest in the multiprocessor reaktime system-level synthesis, only a few efforts have been dedicated. Lee et al.\developed a synthesis algorithm which generates an application-based real-time multipro- cessor. The algorithm uses a three-step synthesis methodol- ogy of resource allocation, assignment, and scheduling. Liand Wolf? developed a hierarchical algorithm for schedul- ing and allocating processes on a multiprocessor. The syn- thesis algorithm takes advantage of the task structure to efficiently schedule and allocate tasks to meet deadlines ‘Yen and Wolf addressed synthesis of distributed embedded systems with both hard and soft deadlines), While all hard deadline must be satisfied, the optimization goal is to sat- isfy as many as possible soft deadlines. Recently, Kirovski etal. proposed a combination of system-level and compila- tion techniques for ares minimization for a set of applca- tion being executed on core-based systems-on-silicon” ‘While there have been a large number of RTOS design stud {es and commercial products in several communities, a very limited efforts have been reported in design community ‘The most notable practical application of real-time schedul- ing approaches, and in particular rate-monotonic schedul- ing algorithms, include the inclusion of rate-monotonic scheduling as the scheduling policy for the IEEE POSIX real-time gperaing system standard and TEEE Fururebuss standards?°279, and the use of the generalized rate-mono- tonic scheduling techniques in several major advance-tech- nology projects such as Space Station Program and the European Space Agency on-board operating system®®. The strong endorsement of several research and development groups of the carliest-deadiine-first and rate-monotonic scheduling as most suitable resource allocation policies for continuous media servers**2528 "and ATM switch scheduling further emphasizes importance of this hard- real ime scheduling approach, ‘Before concluding our survey of the related research efforts, with design methodology and algorithmic issues, we refer to three recent publications in the CAD literature which addressed use of the rate-monotonic scheduling algorithms Hu etal. compared several hard real time scheduling poli cies during hardware-software partitioning of the controller for automotive powertrain module, but did not develop syn- thesis approach or conduct any synthesis optimization Atlenbernd? generalized deadline monotonic scheduling policy along several lines, but also did-not make connection, to the synthesis process. Balarin et al. verified real-time operating system for an automatically controlled vehicle using scalable models!. 6 RTOS for Systems-on-Silicon: Future Directions In this Section we briely outline our vision about future of tte RTOS research and developmient directions. As Bohr said, itis difficult to predict, in particular future. Neverthe- less, it seems that some trends can be identified There is a pending change of behavioral and system level synthesis efforts from the algorithm to architecture frame- work to compiler/RTOS based design methodology. Exploring the interaction between RTOS and system-level synthesis of systems-on-silicon as well as between RTOS and modern embedded real-life applications will be one of the key issues in synthesis of systems using cores, Technology, pricing and applications trends, in particular emerging integration of DRAMs and processor logic and popularity of large data volume applications, will. most likely alleviate the industrial emphasis on RTOS size mini- mization. On other hand, it is reasonable to expect that switching time, and in particular latency, will stay as an important design metrics, ‘The increasing complexity of both hardware and-software will accentuate a strong need for both software and hard- ware debugging. RTOS benchmarking will receive signifi- cantly higher attention. Flexibility and scalability will be important. Applications trends indicate that both security, privacy, authentication, and intellectual property protection ‘mechanisms as well as rich UO features for interaction with sensors, actuators, and humans, will gain importance. Soft real-time systems will also gain popularity There is also a need for adopting a new computational and hhardware models which will form sound theoretical founda- tion for the new filed. New technical ideas, such as dynamic code generation and profle-based resource bal- ‘ancing, and robust implementation will be the key criteria for achieving the outlined goals. Finally, we note the mar- ket trends for other large system software market, indicat- ing that most likely a very small number of RTOSs will hhave-a dominant share of the market. 7 Conclusions Real-time operating systems have long been critical compo: nonts of embedded computing systems; with the advent of systems-on-silicon, RTOSs are playing a major role in all Sorts of integrated circuits, The ability to simultaneously configure the operating system, applications, and underly- ing hardware platform opens up new avenues for improved real-time operating systems. We believe that the next few Years will See continued substantial advances in real-time ‘operating systems. Acknowledgments Li and Wolf's work was supported by the National Science Foundation under grant MIP-9424410. Potkonjak’s work was supported by MICRO grant 96-182 and a grant from the OKAWA Foundation