MTSS: multi task stack sharing for embedded systems

ABSTRACT

Out-of-memory errors are a serious source of unreliability in most embedded systems [22]. Applications run out of main memory because of the frequent difficulty of estimating the memory requirement before deployment, either because it depends on input data, or because certain language features prevent estimation. The typical lack of disks and virtual memory in embedded systems has a serious consequence when an out-of-memory error occurs. Since there is no swap space for the application to grow into, the system crashes if its memory footprint is exceeded by even one byte.This work improves system reliability for multi-tasking embedded systems by proposing MTSS, a multi-task stack sharing technique, that grows the stack of a particular task into other tasks in the system after it has overflown its bounds. This technique can avoid the out-of-memory error if the extra space recovered is enough to complete execution. Experiments show that MTSS, on an average, is able to recover 47% of the stack space allocated to the overflowing task in the free space of other tasks. Therefore, even if we underestimate the stack size of a particular task by 47% on an average, it will still run to completion by reusing stack in other task's stack.Alternatively, MTSS can also be used for decreasing the physical memory for an embedded system by reducing the initial memory allocated to each of the tasks and recovering the deficit by sharing stack with other tasks. Results show that MTSS used in this way can be used to reduce the memory required in multi-tasking embedded systems by 18% on an average, thus reducing the memory cost of the system. MTSS also offers good real time guarantees, since it uses a paging system that never incurs an episodic increase in run-time.The overheads of MTSS are extremely low: the run-time and code size overheads are 1.8% and 2.6% on an average, making it a feasible method for increasing system reliability and reducing the memory footprint of embedded systems.

REFERENCES

• 1: ARM7TDMI Technical Reference Manual, fourth edition, May 2003. Document No. ARM DDI0210B.
• 2: T. Baker. A stack-based resource allocation policy for realtime processes. In Proceedings of the Real-Time Systems Symposium, pages 191--200, 1990.
• 3: Surupa Biswas , Matthew Simpson , Rajeev Barua, Memory overflow protection for embedded systems using run-time checks, reuse and compression, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023872]
• 4: Daniel G. Bobrow , Ben Wegbreit, A model and stack implementation of multiple environments, Communications of the ACM, v.16 n.10, p.591-603, Oct. 1973 [doi>10.1145/362375.362379]
• 5: Dennis Brylow , Niels Damgaard , Jens Palsberg, Static checking of interrupt-driven software, Proceedings of the 23rd International Conference on Software Engineering, p.47-56, May 12-19, 2001, Toronto, Ontario, Canada
• 6: J. Carbone. Efficient memory protection for embedded systems, 2004. www.rtcmagazine.com/home/article.php?id=100120.
• 7: N. D. D. Brylow and J. Palsberg. Stack-size estimation for interrupt-driven microcontrollers. Technical report, Purdue University, June 2000.
• 8: D. J. Dionne. uClinux - Embedded Linux Microcontroller Project. http://www.uclinux.org/.
• 9: M. Durrant. Running linux on low cost, low power mmu-less processors, August 2000. www.linuxdevices.com/articles/AT6245686197.html.
• 10: The GCC Compiler. http://gcc.gnu.org/.
• 11: GDB: The GNU Project Debugger. http://www.gnu.org/software/gdb/gdb.html.
• 12: Dirk Grunwald , Richard Neves, Whole-program optimization for time and space efficient threads, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.50-59, October 01-04, 1996, Cambridge, Massachusetts, United States
• 13: M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown. Mibench: A free, commercially representative embedded benchmark suite. In Proceedings of the IEEE 4th Annual Workshop on Workload Characterization, Dec 2001.
• 14: E. Hauck and B. Dent. Burroughs b6500/b7500 stack mechanism. In Proceedings of AFIPS, SJCC, vol 32, pages 245--251, 1968.
• 15: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 16: G. Hogen and R. Loogen. A new stack technique for the management of runtime structures in distributed implementations. Technical report, RWTH Aachen, Germany, 1993. citeseer.ist.psu.edu/hogen93new.html.
• 17: Bruce Jacob , Trevor Mudge, Uniprocessor Virtual Memory without TLBs, IEEE Transactions on Computers, v.50 n.5, p.482-499, May 2001 [doi>10.1109/12.926161]
• 18: David Seal, ARM Architecture Reference Manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 19: D. Kleidermacher and M. Griglock. Safety-Critical Operating Systems. Embedded Systems Programming, 14(10), September 2001. http://www.embedded.com/- story/OEG20010829S0055.
• 20: B. Lamie. A multitasking revolution, 2000. www.netsilicon.com/pdf/article expresslogic2.pdf.
• 21: R. Moore. Unbound stacks and stoppable tasks, 2001. www.programmersheaven.com/articles/smx/article3.htm.
• 22: George Neville-Neil, Programming Without A Net, Queue, v.1 n.2, April 2003 [doi>10.1145/644254.644264]
• 23: P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001 [doi>10.1145/375977.375978]
• 24: M. Pizka. Thread segment stacks. In In Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications, June 1999.
• 25: J. Regehr, A. Reid, and K. Webb. Eliminating stack overflow by abstract interpretation. In Proceedings of the 3rd International Conference on Embedded Software, pages 306--322. Springer-Verlag, 2003.
• 26: D. M. Shantanu Sardesai and P. Dasgupta. Distributed cactus stacks: Runtime stack-sharing support for distributed parallel programs. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, July 1998.
• 27: Richard Uhlig , David Nagle , Tim Stanley , Trevor Mudge , Stuart Sechrest , Richard Brown, Design tradeoffs for software-managed TLBs, ACM Transactions on Computer Systems (TOCS), v.12 n.3, p.175-205, Aug. 1994 [doi>10.1145/185514.185515]
• 28: Rob von Behren , Jeremy Condit , Feng Zhou , George C. Necula , Eric Brewer, Capriccio: scalable threads for internet services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 29: Emmett Witchel , Josh Cates , Krste Asanović, Mondrian memory protection, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 30: Kam-Fai Wong , Benoît Dageville, Supporting thousands of threads using a hybrid stack sharing scheme, Proceedings of the 1994 ACM symposium on Applied computing, p.493-498, March 06-08, 1994, Phoenix, Arizona, United States [doi>10.1145/326619.326822]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
      D.4.5 Reliability

General Terms:
Languages, Reliability

Keywords:
cactus stack, heap overflow, meshed stack, out-of-memory, reliability, reuse, runtime checks, stack overflow