EMERALDS: a small-memory real-time microkernel

ABSTRACT

EMERALDS (Extensible Microkernel for Embedded, ReAL-time, Distributed Systems) is a real-time microkernel designed for small-memory embedded applications. These applications must run on slow (15-25MHz) processors with just 32-128 kbytes of memory, either to keep production costs down in mass-produced systems or to keep weight and power consumption low. To be feasible for such applications, the OS must not only be small in size (less than 20 kbytes), but also have low-overhead kernel services. Unlike commercial embedded OSs which rely on carefully-crafted code to achieve efficiency, EMERALDS takes the approach of re-designing the basic OS services of task scheduling, synchronization, communication, and system call mechanism by using characteristics found in small-memory embedded systems, such as small code size and a priori knowledge of task execution and communication patterns. With these new schemes, the overheads of various OS services are reduced 20-40% without compromising any OS functionality.

REFERENCES

• 1: ACCETTA, M., BARON, R., BOLOSKY, W., GOLUB, D., RASHID, R., TEVANIAN, A., AND YOUNG, M. Mach: a new kernel foundation for UNIX development. In Prec. Summer Usenix (July 1986), pp. 93-113.
• 2: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.95-109, October 13-16, 1991, Pacific Grove, California, United States
• 3: B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 4: Edsger Wybe Dijkstra, Cooperating Sequential Processes, Technical Report EWD-123, 1965
• 5: Richard P. Draves , Brian N. Bershad , Richard F. Rashid , Randall W. Dean, Using continuations to implement thread management and communication in operating systems, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.122-136, October 13-16, 1991, Pacific Grove, California, United States
• 6: EMBEDDED SYSTEM PRODUCTS, INC. RTXC User's Manual. Houston, TX, 1995.
• 7: GENTLEMAN, W. M. Realtime applications: Multiprocessors in Harmony. In Prec. BUSCON/88 East (October 1988), pp. 269-278.
• 8: A. Nico Habermann, Synchronization of communicating processes, Communications of the ACM, v.15 n.3, p.171-176, March 1972 [doi>10.1145/361268.361277]
• 9: Dan Hildebrand, An Architectural Overview of QNX, Proceedings of the Workshop on Micro-kernels and Other Kernel Architectures, p.113-126, April 27-28, 1992
• 10: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 11: Yutaka Ishikawa , Hideyuki Tokuda , Clifford W. Mercer, An Object-Oriented Real-Time Programming Language, Computer, v.25 n.10, p.66-73, October 1992 [doi>10.1109/2.161281 ]
• 12: Michael B. Jones , Daniela Roşu , Marcel-Cătălin Roşu, CPU reservations and time constraints: efficient, predictable scheduling of independent activities, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.198-211, October 05-08, 1997, Saint Malo, France
• 13: D. I. Katcher , H. Arakawa , J. K. Strosnider, Engineering and Analysis of Fixed Priority Schedulers, IEEE Transactions on Software Engineering, v.19 n.9, p.920-934, September 1993 [doi>10.1109/32.241774 ]
• 14: Hermann Kopetz , Andreas Damm , Christian Koza , Marco Mulazzani , Wolfgang Schwabl , Christoph Senft , Ralph Zainlinger, Distributed Fault-Tolerant Real-Time Systems: The Mars Approach, IEEE Micro, v.9 n.1, p.25-40, January 1989 [doi>10.1109/40.16792 ]
• 15: KOPETZ, H., AND REISINGER, J. The non-blocking write protocol NBW: a solution to a real-time synchronization problem. In Prec. Real-Time Systems Symposium (1993), pp. 131-137.
• 16: Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977 [doi>10.1145/359863.359878]
• 17: LEHOCZKY, J., SHA, L., AND DING, Y. The rate monotonic scheduling algorithm: exact characterization and average case behavior. In Prec. Real-Time Systems Symposium (1989), pp. 166-171.
• 18: LEUNG, J. Y.-T., AND WHITEHEAD, J. On the complexity of fixed-priority scheduling of periodic, realtime tasks. Performance Evaluation 2, 4 (December 1982), 237-250.
• 19: Jochen Liedtke, Improving IPC by kernel design, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.175-188, December 05-08, 1993, Asheville, North Carolina, United States
• 20: Jochen Liedtke , Ulrich Bartling , Uwe Beyer , Dietmar Heinrichs , Rudolf Ruland , Gyula Szalay, Two years of experience with a &mgr;-Kernel based OS, ACM SIGOPS Operating Systems Review, v.25 n.2, p.51-62, April 1991 [doi>10.1145/122120.122124]
• 21: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 22: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 23: MURRAY, J. Microsoft Windows CE memory use. http ://msdn.micreseft. cem/library/backgrnd/ html/msdn_memdrft2.htm (1997).
• 24: POLEDNA, S., MOCKEN, T., AND SCHIEMANN, J. ERCOS: an operating system for automotive applications. In Society ef Autemetive Engineers International Congress and Exposition (February 1996), pp. 55-65. SAE Technical Paper Series 960623.
• 25: Richard Rashid , Avadis Tevanin, Jr. , Michael Young , David Golub , Robert Baron, Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures, IEEE Transactions on Computers, v.37 n.8, p.896-908, August 1988 [doi>10.1109/12.2242 ]
• 26: L. Sha , R. Rajkumar , J. P. Lehoczky, Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, v.39 n.9, p.1175-1185, September 1990 [doi>10.1109/12.57058 ]
• 27: Kang G. Shin , Dilip D. Kandlur , Daniel L. Kiskis , Paul S. Dodd , Harold A. Rosenberg , Atri Indiresan, A Distributed Real-Time Operating System, IEEE Software, v.9 n.5, p.58-68, September 1992 [doi>10.1109/52.156898 ]
• 28: John A. Stankovic , Krithi Ramamritham , Marco Spuri, Deadline Scheduling for Real-Time Systems: Edf and Related Algorithms, Kluwer Academic Publishers, Norwell, MA, 1998
• 29: J. A. Stankovic , K. Ramamritham, The Spring kernel: a new paradigm for real-time operating systems, ACM SIGOPS Operating Systems Review, v.23 n.3, p.54-71, July 1989 [doi>10.1145/71021.71024]
• 30: TAKADA, H., AND SAKAMURA, K. Experimental implementations of priority inheritance semaphore on ITRON-specification kernel. In 11 th TRON Project International Symposium (1994), pp. 106-113.
• 31: THOMPSON, L. M. Using pSOS+ for embedded realtime computing. In COMPCON (1990), pp. 282-288.
• 32: TOKUDA, H., AND NAKAJIMA, T. Evaluation of realtime synchronization in Real-Time Mach. In Second Mach Symposium (1991), Usenix, pp. 213-221.
• 33: TOKUDA, H., NAKAJIMA, T., AND RAO, P. Real- Time Mach: Towards a predictable real-time system. In Prec. USENIX Mach Workshop (October 1990), pp. 73-82.
• 34: Priority Inheritance Spin Locks for Multiprocessor Real-Time Systems, Proceedings of the 1996 International Symposium on Parallel Architectures, Algorithms and Networks, p.70, June 12-14, 1996
• 35: WIND RIVER SYSTEMS. VxWerks Programmer's Guide, 5.1. Alameda, CA, 1993.
• 36: Khawar Mahmood Zuberi , Kang G. Shin, Real-time operating system services for networked embedded systems, 1998
• 37: K. M. Zuberi , K. G. Shin, Non-preemptive scheduling of messages on controller area network for real-time control applications, Proceedings of the Real-Time Technology and Applications Symposium, p.240, May 15-17, 1995
• 38: K. M. Zuberi , K. G. Shin, EMERALDS: a microkernel for embedded real-time systems, Proceedings of the 2nd IEEE Real-Time Technology and Applications Symposium (RTAS '96), p.241, June 10-12, 1996
• 39: Khawar M. Zuberi , Kang G. Shin, An efficient semaphore implementation scheme for small-memory embedded systems, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.25, June 09-11, 1997
• 40: ZUBERI, K. M., AND SHIN, K. G. Scheduling messages on Controller Area Network for real-time CIM applications. IEEE Trans. Robotics and Automation (April 1997), 310-314.
• 41: ZUBERI, K. M., AND SHIN, K. G. An efficient endhost protocol processing architecture for real-time audio and video traffic. In Prec. Network and Operating System Support for Digital Audio and Video (NOSS- DAV) (July 1998), pp. 111-114.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design