Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-01-24T11:05:10.023Z Has data issue: false hasContentIssue false
  • English
  • Français

Composable scheduler activations for Haskell

Part of: JFP Research Articles

Published online by Cambridge University Press:  27 June 2016

K. C. SIVARAMAKRISHNAN ,
TIM HARRIS ,
SIMON MARLOW  and
SIMON PEYTON JONES
K. C. SIVARAMAKRISHNAN
Affiliation:
Computer Laboratory, University of Cambridge, Cambridge, United Kingdom (e-mail: sk826@cl.cam.ac.uk)
TIM HARRIS
Affiliation:
Oracle Labs, Cambridge, Cambridge, United Kingdom (e-mail: timothy.l.harris@oracle.com)
SIMON MARLOW
Affiliation:
Facebook UK Ltd., London, United Kingdom (e-mail: smarlow@fb.com)
SIMON PEYTON JONES
Affiliation:
Microsoft Research, Cambridge, Cambridge, United Kingdom (e-mail: simonpj@microsoft.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The runtime for a modern, concurrent, garbage collected language like Java or Haskell is like an operating system: sophisticated, complex, performant, but alas very hard to change. If more of the runtime system were in the high-level language, it would be far more modular and malleable. In this paper, we describe a novel concurrency substrate design for the Glasgow Haskell Compiler that allows multicore schedulers for concurrent and parallel Haskell programs to be safely and modularly described as libraries in Haskell. The approach relies on abstracting the interface to the user-implemented schedulers through scheduler activations, together with the use of Software Transactional Memory to promote safety in a multicore context.

Type
Articles
Information
Journal of Functional Programming , Volume 26 , 2016 , e9
Copyright
Copyright © Cambridge University Press 2016 

References

Anderson, T. E., Bershad, B. N., Lazowska, E. D. & Levy, H. M. (1991) Scheduler activations: Effective kernel support for the user-level management of parallelism. In Proceedings of the 13th ACM Symposium on Operating Systems Principles, SOSP '91. Pacific Grove, California, USA: ACM, New York, NY, USA, pp. 95–109.CrossRefGoogle Scholar
Async. (2016) Jane Street Capitalś asynchronous execution library. Available at: https://github.com/janestreet/async. Last accessed 10th June 2016.Google Scholar
Baumann, A., Barham, P., Dagand, P.-E., Harris, T., Isaacs, R., Peter, S., Roscoe, T., Schüpbach, A. & Singhania, A. (2009) The multikernel: A new OS architecture for scalable multicore systems. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles, SOSP '09. Big Sky, Montana, USA: ACM, New York, NY, USA, pp. 29–44.CrossRefGoogle Scholar
Bershad, B. N., Chambers, C., Eggers, S., Maeda, C., McNamee, D., Pardyak, P., Savage, S. & Sirer, E. G. (1995) SPIN – an extensible microkernel for application-specific operating system services. Sigops Oper. Syst. Rev. 29 (1), 74–77.CrossRefGoogle Scholar
Bruggeman, C., Waddell, O. & Dybvig, R. K. (1996) Representing control in the presence of one-shot continuations. In Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation, PLDI '96. Philadelphia, Pennsylvania, USA: ACM, New York, NY, USA, pp. 99–107.CrossRefGoogle Scholar
Chakravarty, M. M. T., Leshchinskiy, R., Peyton Jones, S., Keller, G. & Marlow, S. (2007) Data parallel Haskell: A status report. In Proceedings of the 2007 Workshop on Declarative Aspects of Multicore Programming, DAMP '07. Nice, France: ACM, New York, NY, USA, pp. 10–18.CrossRefGoogle Scholar
Dolan, S., White, L., Sivaramakrishnan, K. C., Yallop, J. & Madhavapeddy, A. (2015) Effective concurrency through algebraic effects. In The OCaml Users and Developers Workshop, OCaml '15.Google Scholar
Dybvig, R. K. & Hieb, R. (1989) Engines from continuations. Comput. Lang. 14 (2), 109–123.CrossRefGoogle Scholar
Fluet, M., Rainey, M. & Reppy, J. (2008) A scheduling framework for general-purpose parallel languages. In Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming, ICFP '08. Victoria, BC, Canada: ACM, New York, NY, USA, pp. 241–252.CrossRefGoogle Scholar
Fluet, M., Rainey, M., Reppy, J. & Shaw, A. (2010) Implicitly threaded parallelism in manticore. J. Funct. Program. 20 (5–6), 537–576.CrossRefGoogle Scholar
Frampton, D., Blackburn, S. M., Cheng, P., Garner, R. J., Grove, D., Moss, J. E. B. & Salishev, S. I. (2009) Demystifying magic: High-level low-level programming. In Proceedings of the 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, VEE '09. Washington, DC, USA: ACM, New York, NY, USA, pp. 81–90.CrossRefGoogle Scholar
Galois. (2016) Haskell Lightweight Virtual Machine (HaLVM). Available at: http://corp.galois.com/halvm. Last accessed 10th June 2016.Google Scholar
GHC. (2016) Glasgow Haskell Compiler. Available at: http://www.haskell.org/ghc. Last accessed 10th June 2016.Google Scholar
Hallgren, T., Jones, M. P., Leslie, R. & Tolmach, A. (2005) A principled approach to operating system construction in Haskell. In Proceedings of the 10th ACM SIGPLAN International Conference on Functional Programming, ICFP '05. New York, NY, USA: ACM, pp. 116–128.CrossRefGoogle Scholar
Harris, T., Marlow, S., Peyton-Jones, S. & Herlihy, M. (2005a) Composable memory transactions. In Proceedings of the 10th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '05. Chicago, IL, USA: ACM, New York, NY, USA, pp. 48–60.CrossRefGoogle Scholar
Harris, T., Marlow, S. & Jones, S. P. (2005b) Haskell on a shared-memory multiprocessor. In Proceedings of the 2005 ACM SIGPLAN Workshop on Haskell, Haskell '05. Tallinn, Estonia: ACM, New York, NY, USA, pp. 49–61.CrossRefGoogle Scholar
Haskell. (2016) Haskell Web Development. Available at: http://www.haskell.org/haskellwiki/Web/Servers. Last accessed 10th June 2016.Google Scholar
Haynes, C. T. & Friedman, D. P. (1987) Abstracting timed preemption with engines. Comput. Lang. 12 (2), 109–121.CrossRefGoogle Scholar
HotSpotVM. (2016) Java SE HotSpot at a Glance. Available at: http://www.oracle.com/technetwork/java/javase/tech/index-jsp-137187.html. Last accessed 10th June 2016.Google Scholar
IBM. (2016) Java Platform Standard Edition (Java SE). Available at: http://www.ibm.com/developerworks/java/jdk/. Last accessed 10th June 2016.Google Scholar
Li, P., Marlow, S., Peyton Jones, S. & Tolmach, A. (2007) Lightweight concurrency primitives for GHC. In Proceedings of the ACM SIGPLAN Workshop on Haskell Workshop, Haskell '07. Freiburg, Germany: ACM, New York, NY, USA, pp. 107–118.CrossRefGoogle Scholar
Lippmeier, B., Chakravarty, M., Keller, G. & Peyton Jones, S. (2012) Guiding parallel array fusion with indexed types. In Proceedings of the 2012 Haskell Symposium, Haskell '12. Copenhagen, Denmark: ACM, New York, NY, USA, pp. 25–36.CrossRefGoogle Scholar
Madhavapeddy, A., Mortier, R., Rotsos, C., Scott, D., Singh, B., Gazagnaire, T., Smith, S., Hand, S. & Crowcroft, J. (2013) Unikernels: Library operating systems for the cloud. In Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '13. New York, NY, USA: ACM, pp. 461–472.CrossRefGoogle Scholar
Madhavapeddy, A. & Scott, D. J. (2014) Unikernels: The rise of the virtual library operating system. Commun. ACM 57 (1), 61–69.CrossRefGoogle Scholar
Marlow, S., Jones, S. P., Moran, A. & Reppy, J. (2001) Asynchronous exceptions in Haskell. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, PLDI '01. Snowbird, Utah, USA: ACM, New York, NY, USA, pp. 274–285.CrossRefGoogle Scholar
Marlow, S., Jones, S. P. & Thaller, W. (2004) Extending the Haskell foreign function interface with concurrency. In Proceedings of the 2004 ACM SIGPLAN Workshop on Haskell, Haskell '04. Snowbird, Utah, USA: ACM, New York, NY, USA, pp. 22–32.CrossRefGoogle Scholar
Marlow, S., Maier, P., Loidl, H.-W., Aswad, M. K. & Trinder, P. (2010) Seq no more: Better strategies for parallel Haskell. In Proceedings of the 3rd ACM Haskell Symposium on Haskell, Haskell '10. New York, NY, USA: ACM, pp. 91–102.CrossRefGoogle Scholar
Marsh, B. D., Scott, M. L., LeBlanc, T. J. & Markatos, E. P. (1991) First-class user-level threads. In Proceedings of the 13th ACM Symposium on Operating Systems Principles, SOSP '91. Pacific Grove, California, USA: ACM, New York, NY, USA, pp. 110–121.CrossRefGoogle Scholar
Microsoft Corp. (2016) Common Language Runtime (CLR). Available at: http://msdn.microsoft.com/en-us/library/8bs2ecf4(v=vs.110)aspx. Last accessed 10th June 2016.Google Scholar
Philbin, J. F. (1993) The Design of an Operating System for Modern Programming Languages. Ph.D. thesis, Yale University, New Haven, CT, USA. UMI Order No. GAX93-29376.Google Scholar
Reid, Ar. (1999) Putting the spine back in the spineless tagless G-machine: An implementation of resumable black-holes. In Selected Papers from the 10th International Workshop on 10th International Workshop. IFL '98. London, UK, UK: Springer-Verlag, pp. 186–199.CrossRefGoogle Scholar
Reppy, J. H. (2007) Concurrent Programming in ml. Cambridge University Press.Google Scholar
Reppy, J., Russo, C. V. & Xiao, Y. (2009) Parallel concurrent ML. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming, ICFP '09. Edinburgh, Scotland: ACM, New York, NY, USA, pp. 257–268.CrossRefGoogle Scholar
Shivers, O. (1997) Continuations and threads: Expressing machine concurrency directly in advanced languages. Continuations Workshop.Google Scholar
Shootout. (2016) The Computer Language Benchmarks Game. Available at: http://benchmarksgame.alioth.debian.org/. Last accessed 10th June 2016.Google Scholar
Sivaramakrishnan, K. C., Ziarek, L. & Jagannathan, S. (2014) MultiMLton: A multicore-aware runtime for standard ML. J. Funct. Program. 24 (6): 613–674.CrossRefGoogle Scholar
STMLibrary. (2016) Control.Concurrent.STM. Available at: http://hackage.haskell.org/package/stm-2.1.1.0/docs/Control-Concurrent-STM.html. Last accessed 10th June 2016.Google Scholar
Vouillon, J. (2008) Lwt: A cooperative thread library. In Proceedings of the 2008 ACM SIGPLAN Workshop on ML, ML '08. New York, NY, USA: ACM, pp. 3–12.CrossRefGoogle Scholar
Wand, M. (1980) Continuation-based multiprocessing. In Proceedings of the 1980 ACM Conference on LISP and Functional Programming, LFP '80. Stanford University, California, USA: ACM, New York, NY, USA, pp. 19–28.CrossRefGoogle Scholar
Williams, N. J. (2002) An implementation of scheduler activations on the NetBSD operating system. In Proceedings of the FREENIX Track: 2002 USENIX Annual Technical Conference. Berkeley, CA, USA: USENIX Association, pp. 99–108.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.