research-article

Open access

Multiprogramming a 64kB Computer Safely and Efficiently

Authors:

Bradford Campbell,

Daniel B. Giffin,

Philip LevisAuthors Info & Claims

SOSP '17: Proceedings of the 26th Symposium on Operating Systems Principles

Pages 234 - 251

https://doi.org/10.1145/3132747.3132786

Published: 14 October 2017 Publication History

Abstract

Low-power microcontrollers lack some of the hardware features and memory resources that enable multiprogrammable systems. Accordingly, microcontroller-based operating systems have not provided important features like fault isolation, dynamic memory allocation, and flexible concurrency. However, an emerging class of embedded applications are software platforms, rather than single purpose devices, and need these multiprogramming features. Tock, a new operating system for low-power platforms, takes advantage of limited hardware-protection mechanisms as well as the type-safety features of the Rust programming language to provide a multiprogramming environment for microcontrollers. Tock isolates software faults, provides memory protection, and efficiently manages memory for dynamic application workloads written in any language. It achieves this while retaining the dependability requirements of long-running applications.

Supplementary Material

MP4 File (multiprogramming.mp4)

Download
2249.00 MB

References

[1]

Adkins, Joshua and Campbell, Bradford and Ghena, Branden and Jackson, Neal and Pannuto, Pat and Dutta, Prabal. The Signpost Network: Demo Abstract. In Proceedings of the 14th ACM Conference on Embedded Network Sensor Systems CD-ROM (New York, NY, USA, 2016), SenSys '16, ACM, pp. 320--321.

Digital Library

[2]

Al Danial. cloc. http://cloc.sourceforge.net. Accessed 24-August-2017.

[3]

Andersen, M. P., Fierro, G., and Culler, D. E. System Design for a Synergistic, Low Power Mote/BLE Embedded Platform. In 2016 15th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN) (2016), IEEE, pp. 1--12.

Digital Library

[4]

Anderson, T., and Dahlin, M. Operating Systems: Principles and Practice, 2nd ed. Recursive Books LLC, 2014, ch. 2.1, pp. 43--44.

[5]

Baccelli, E., Hahm, O., Wähilsch, M., Günes, M., and Schmidt, T. C. RIOT: One OS to rule them all in IoT. Tech. rep., INRIA, Dec 2012. Research Report, No. RR--8176.

[6]

Banzi, M., Cuartielles, D., Igoe, T., Martino, G., Mellis, D., et al. Arduino. https://www.arduino.cc/. Accessed 09-May-2016.

[7]

Barr, T. W., Smith, R., and Rixner, S. Design and implementation of an embedded Python run-time system. In Proceedings of the 2012 USENIX Conference on Annual Technical Conference (Berkeley, CA, USA, 2012), USENIX ATC'12, USENIX Association, pp. 27--27.

Digital Library

[8]

Barry, R., et al. FreeRTOS. http//:www.freertos.org/. Accessed 09-July-2016.

[9]

Bershad, B. N., Savage, S., Pardyak, P., Sirer, E. G., Fiuczynski, M. E., Becker, D., Chambers, C., and Eggers, S. Extensibility safety and performance in the SPIN operating system. In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (New York, NY, USA, 1995), SOSP '95, ACM, pp. 267--283.

Digital Library

[10]

Cardelli, L., Donahue, J., Jordan, M., Kalsow, B., and Nelson, G. The Modula--3 Type System. In Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (New York, NY, USA, 1989), POPL '89, ACM, pp. 202--212.

Digital Library

[11]

Chen, H., Ziegler, D., Chajed, T., Chlipala, A., Kaashoek, M. F., and Zeldovich, N. Using crash Hoare logic for certifying the FSCQ file system. In Proceedings of the 25th Symposium on Operating Systems Principles (New York, NY, USA, 2015), SOSP '15, ACM, pp. 18--37.

Digital Library

[12]

Coggins, J., Mcdonald, A., Plank, G., Pannell, M., Ward, R., and Parsons, S. Snow web 2.0: The next generation of antarctic meteorological monitoring systems? 591--.

[13]

Dunkels, A., et al. Contiki mulithreading. https://github.com/contiki-os/contiki/wiki/Multithreading. Accessed 09-May-2016.

[14]

Dunkels, A., Gronvall, B., and Voigt, T. Contiki -- A lightweight and flexible operating system for tiny networked sensors. In Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (Washington, DC, USA, 2004), LCN '04, IEEE Computer Society, pp. 455--462.

Digital Library

[15]

Dunkels, A., Schmidt, O., Voigt, T., and Ali, M. Protothreads: Simplifying event-driven programming of memory-constrained embedded systems. In Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (New York, NY, USA, 2006), SenSys '06, ACM, pp. 29--42. Updated documentation: http://contiki.sourceforge.net/docs/2.6/a01802.html.

Digital Library

[16]

FIDO Alliance. FIDO Certified Showcase. https://fidoalliance.org/fido-certified-showcase/, April 2017.

[17]

Fitbit. FitBit: Official site for activity trackers and more, 2017. Accessed: 04-20-2017.

[18]

Garmin. vìvoactive 3. https://buy.garmin.com/en-US/US/p/571520, September 2017.

[19]

Gay, D., and Hui, J. TEP 103: Permanent Data Storage (Flash). http//:www.tinyos.net/tinyos-2.x/doc/txt/tep103.txt, 2007.

[20]

Gay, D., Levis, P., von Behren, R., Welsh, M., Brewer, E., and Culler, D. The nesC Language: A Holistic Approach to Networked Embedded Systems. In SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (2003).

Digital Library

[21]

Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., and Levis, P. Collection Tree Protocol. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems (New York, NY, USA, 2009), SenSys '09, ACM, pp. 1--14.

Digital Library

[22]

Grossman, D., Morrisett, G., Jim, T., Hicks, M., Wang, Y., and Cheney, J. Region-based memory management in Cyclone. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation (New York, NY, USA, 2002), PLDI '02, ACM, pp. 282--293.

Digital Library

[23]

Han, C.-C., Kumar, R., Shea, R., Kohler, E., and Srivastava, M. A dynamic operating system for sensor nodes. In Proceedings of the 3rd International Conference on Mobile Systems, Applications, and Services (New York, NY, USA, 2005), MobiSys '05, ACM, pp. 163--176.

Digital Library

[24]

Hunt, G. C., and Larus, J. R. Singularity: Rethinking the software stack. ACM SIGOPS Operating Systems Review 41, 2 (April 2007), 37--49.

Digital Library

[25]

King, S. T., Chen, P. M., Wang, Y.-M., Verbowski, C., Wang, H. J., and Lorch, J. R. SubVirt: Implementing malware with virtual machines. In Proceedings of the 2006 IEEE Symposium on Security and Privacy (Washington, DC, USA, 2006), SP '06, IEEE Computer Society, pp. 314--327.

Digital Library

[26]

Klein, G., Elphinstone, K., Heiser, G., Andronick, J., Cock, D., Derrin, P., Elkaduwe, D., Engelhardt, K., Kolanski, R., Norrish, M., Sewell, T., Tuch, H., and Winwood, S. seL4: Formal verification of an OS kernel. In Proceedings of the ACM SIGOPS 22Nd Symposium on Operating Systems Principles (New York, NY, USA, 2009), SOSP '09, ACM, pp. 207--220.

Digital Library

[27]

Klues, K., Handziski, V., Lu, C., Wolisz, A., Culler, D., Gay, D., and Levis, P. Integrating concurrency control and energy management in device drivers. In Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles (New York, NY, USA, 2007), SOSP '07, ACM, pp. 251--264.

Digital Library

[28]

Klues, K., Liang, C.-J. M., Paek, J., Musăloiu-E, R., Levis, P., Terzis, A., and Govindan, R. TOSThreads: Thread-safe and Non-invasive Preemption in TinyOS. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems (New York, NY, USA, 2009), SenSys '09, ACM, pp. 127--140.

Digital Library

[29]

Lang, J., Czeskis, A., Balfanz, D., and Schilder, M. Security keys: Practical cryptographic second factors for the modern web. In Financial Cryptography (2016).

[30]

Lédeczi, A., Nádas, A., Völgyesi, P., Balogh, G., Kusy, B., Sallai, J., Pap, G., Dóra, S., Molnár, K., Maróti, M., and Simon, G. Countersniper system for urban warfare. ACM Trans. Sen. Netw. 1, 2 (Nov. 2005), 153--177.

Digital Library

[31]

Levis, P. Experiences from a Decade of TinyOS Development. In Proceedings of the 10th Symposium on Operating System Design and Implementation (OSDI) (October 2012).

Digital Library

[32]

Levis, P., and Culler, D. Maté: A tiny virtual machine for sensor networks. In Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems (New York, NY, USA, 2002), ASPLOS X, ACM, pp. 85--95.

Digital Library

[33]

Levis, P., Madden, S., Polastre, J., Szewczyk, R., White-house, K., Woo, A., Gay, D., Hill, J., Welsh, M., Brewer, E., and Culler, D. Ambient Intelligence. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005, ch. TinyOS: An Operating System for Sensor Networks, pp. 115--148.

[34]

Levy, A., Andersen, M. P., Campbell, B., Culler, D., Dutta, P., Ghena, B., Levis, P., and Pannuto, P. Ownership is theft: Experiences building an embedded OS in Rust. In Proceedings of the 8th Workshop on Programming Languages and Operating Systems (New York, NY, USA, 2015), PLOS '15, ACM, pp. 21--26.

Digital Library

[35]

Levy, A., Campbell, B., Ghena, B., Pannuto, P., Dutta, P., and Levis, P. The Case for Writing a Kernel in Rust. In Proceedings of the Eighth ACM SIGOPS Asia-Pacific Workshop on Systems (APSys 2017) (September 2017).

Digital Library

[36]

Matsakis, N. D., and Klock, II, F. S. The Rust Language. In Proceedings of the 2014 ACM SIGAda Annual Conference on High Integrity Language Technology (New York, NY, USA, 2014), HILT '14, ACM, pp. 103--104.

Digital Library

[37]

mbed. mbed OS 5. https://developer.mbed.org/, 2017. Accessed: 04-20-2017.

[38]

McCartney, W. P. Simplifying Concurrent Programming in Sensor-nets with Threading. PhD thesis, Cleveland State University, 2006.

[39]

MSP430 ultra-low-power Microcontrollers. http//:www.ti.com/lsds/ti/microcontrollers_16-bit_32-bit/msp/overview.page.

[40]

Nest Labs. Meet the Nest Protect smoke and carbon monoxide alarm. https://nest.com/smoke-co-alarm/meet-nest-protect/, 2017.

[41]

Oracle Java Documentation. Intrinsic Locks and Synchronization. https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html, 2017. Accessed: 04-20-2017.

[42]

Polastre, J., Szewczyk, R., and Culler, D. Telos: Enabling ultra-low power wireless research. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (Piscataway, NJ, USA, 2005), IPSN '05, IEEE Press.

Digital Library

[43]

PostgreSQL 9.6.2 Documentation. Memory Management. https://www.postgresql.org/docs/current/static/spi-memory.html, 2017. Accessed: 04-20-2017.

[44]

Ross, D. T. The AED free storage package. Commun. ACM 10, 8 (Aug. 1967), 481--492.

Digital Library

[45]

SAM4L ARM Cortex-M4 Microcontrollers. http//:www.atmel.com/products/microcontrollers/arm/sam4l.aspx.

[46]

Suunto. Ambit3 Sport. http//:www.suunto.com/en-US/Products/Sports-Watches/Suunto-Ambit3-Sport/Suunto-Ambit3-Sport-White/, September 2017.

[47]

Tejun Heo. Control Group v2. https://www.kernel.org/doc/Documentation/cgroup-v2.txt, 2015.

[48]

The Chromium Project. Chromium Embedded Controller (EC) Development. https://www.chromium.org/chromium-os/ec-development, 2017. Accessed: 04-20-2017.

[49]

Tofte, M., and Birkedal, L. A region inference algorithm. ACM Trans. Program. Lang. Syst. 20, 4 (July 1998), 724--767.

Digital Library

[50]

Tofte, M., Birkedal, L., Elsman, M., and Hallenberg, N. A retrospective on region-based memory management. Higher Order Symbol. Comput. 17, 3 (Sept. 2004), 245--265.

Digital Library

[51]

Tolle, G., Polastre, J., Szewczyk, R., Culler, D. a., Turner, N., Tu, K., Burgess, S., Dawson, T., Bu onadonna, P., Gay, D., and Hong, W. A macroscope in the redwoods. In Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems (New York, NY, USA, 2005), SenSys '05, ACM, pp. 51--63.

Digital Library

[52]

Trustworthy Systems Team, Data61. seL4 Reference Manual Version 7.0.0, Sept. 2017. https://sel4.systems/Info/Docs/seL4-manual-7.0.0.pdf.

[53]

Welsh, M., and Mainland, G. Programming Sensor Networks Using Abstract Regions. In Proceedings of the 1st Conference on Symposium on Networked Systems Design and Implementation - Volume 1 (Berkeley, CA, USA, 2004), NSDI'04, USENIX Association, pp. 3--3.

Digital Library

[54]

Werner-Allen, G., Lorincz, K., Johnson, J., Lees, J. o., and Welsh, M. Fidelity and yield in a volcano monitoring sensor network. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (Berkeley, CA, USA, 2006), OSDI '06, USENIX Association, pp. 381--396.

Digital Library

[55]

Yang, J., and Hawblitzel, C. Safe to the last instruction: Automated verification of a type-safe operating system. In Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation (New York, NY, USA, 2010), PLDI '10, ACM, pp. 99--110.

Digital Library

[56]

Yubico. Yubikey hardware. https://www.yubico.com/products/yubikey-hardware/.

Cited By

Bakir FWang SEkaireb TPearson JKrintz CWolski R(2024)Ambience: an operating system for IoT microservicesJournal of Edge Computing10.55056/jec.786Online publication date: 5-Sep-2024
https://doi.org/10.55056/jec.786
Vandervelden TDe Smet RDeac DSteenhaut KBraeken A(2024)Overview of Embedded Rust Operating Systems and FrameworksSensors10.3390/s2417581824:17(5818)Online publication date: 7-Sep-2024
https://doi.org/10.3390/s24175818
LI LZHANG QXU ZZHAO SSHI ZGUAN Y(2024)rOOM: A Rust-Based Linux Out of Memory Kernel ComponentIEICE Transactions on Information and Systems10.1587/transinf.2023MPP0001E107.D:3(245-256)Online publication date: 1-Mar-2024
https://doi.org/10.1587/transinf.2023MPP0001
Show More Cited By

Recommendations

Composing OS extensions safely and efficiently with Bascule
EuroSys '13: Proceedings of the 8th ACM European Conference on Computer Systems

Library OS (LibOS) architectures implement the OS personality as a user-mode library, giving each application the flexibility to choose its LibOS. This approach is appealing for many reasons, not least the ability to extend or customise the LibOS. ...
A multiprogramming operating system for the TI980A
ACM '76: Proceedings of the 1976 annual conference

The University of Wyoming Computer Science Department has developed several versions of a multiprogramming operating system for research and for student use. This paper describes the background of the systems and the hardware facilities available. Major ...
Multiprogramming: promise, performance and prospect
AFIPS '68 (Fall, part I): Proceedings of the December 9-11, 1968, fall joint computer conference, part I

"Multiprogramming" is the label given to the concept of a dynamic sharing of the resources of a given computer system among two or more programs. An operating multiprogramming system presents to external observers the appearance of effecting the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SOSP '17: Proceedings of the 26th Symposium on Operating Systems Principles

October 2017

677 pages

ISBN:9781450350853

DOI:10.1145/3132747

Copyright © 2017 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
USENIX Assoc: USENIX Assoc

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

National Science Foundation

Conference

SOSP '17

Sponsor:

SIGOPS
USENIX Assoc

SOSP '17: ACM SIGOPS 26th Symposium on Operating Systems Principles

October 28, 2017

Shanghai, China

Acceptance Rates

Overall Acceptance Rate 174 of 961 submissions, 18%

Upcoming Conference

SOSP '25

Sponsor:
sigops

ACM SIGOPS 31st Symposium on Operating Systems Principles

October 13 - 16, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

103
Total Citations
View Citations
4,660
Total Downloads

Downloads (Last 12 months)654
Downloads (Last 6 weeks)141

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bakir FWang SEkaireb TPearson JKrintz CWolski R(2024)Ambience: an operating system for IoT microservicesJournal of Edge Computing10.55056/jec.786Online publication date: 5-Sep-2024
https://doi.org/10.55056/jec.786
Vandervelden TDe Smet RDeac DSteenhaut KBraeken A(2024)Overview of Embedded Rust Operating Systems and FrameworksSensors10.3390/s2417581824:17(5818)Online publication date: 7-Sep-2024
https://doi.org/10.3390/s24175818
LI LZHANG QXU ZZHAO SSHI ZGUAN Y(2024)rOOM: A Rust-Based Linux Out of Memory Kernel ComponentIEICE Transactions on Information and Systems10.1587/transinf.2023MPP0001E107.D:3(245-256)Online publication date: 1-Mar-2024
https://doi.org/10.1587/transinf.2023MPP0001
Huang GSchuermann LLevy A(2024)Bridge: A Leak-Free Hardware-Software Architecture for Parallel Embedded SystemsProceedings of the 2nd Workshop on Kernel Isolation, Safety and Verification10.1145/3698576.3698765(16-22)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3698576.3698765
Chiang YChang WLi STu J(2024)Securing a Multiprocessor KVM Hypervisor with RustProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698562(650-667)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698562
Dwivedi KIyer RKashyap SWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)Fast, Flexible, and Practical Kernel ExtensionsProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695950(249-264)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695950
Yang WGao CLiu XLi YXue YFilkov VRay BZhou M(2024)Rust-twins: Automatic Rust Compiler Testing through Program Mutation and Dual Macros GenerationProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695059(631-642)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695059
Peng YTian HXian JZhou SYan SZhang Y(2024)Framekernel: A Safe and Efficient Kernel Architecture via Rust-based Intra-kernel Privilege SeparationProceedings of the 15th ACM SIGOPS Asia-Pacific Workshop on Systems10.1145/3678015.3680492(31-37)Online publication date: 4-Sep-2024
https://dl.acm.org/doi/10.1145/3678015.3680492
Hong JRyu S(2024)Don’t Write, but Return: Replacing Output Parameters with Algebraic Data Types in C-to-Rust TranslationProceedings of the ACM on Programming Languages10.1145/36564068:PLDI(716-740)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656406
Kang JPark JSeo JKwon DDe V(2024)Look Before You Access: Efficient Heap Memory Safety for Embedded Systems on ARMv8-MProceedings of the 61st ACM/IEEE Design Automation Conference10.1145/3649329.3655949(1-6)Online publication date: 23-Jun-2024
https://dl.acm.org/doi/10.1145/3649329.3655949
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents