[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article
Open access

Responsive Parallelism with Synchronization

Published: 06 June 2023 Publication History

Abstract

Many concurrent programs assign priorities to threads to improve responsiveness. When used in conjunction with synchronization mechanisms such as mutexes and condition variables, however, priorities can lead to priority inversions, in which high-priority threads are delayed by low-priority ones. Priority inversions in the use of mutexes are easily handled using dynamic techniques such as priority inheritance, but priority inversions in the use of condition variables are not well-studied and dynamic techniques are not suitable.
In this work, we use a combination of static and dynamic techniques to prevent priority inversion in code that uses mutexes and condition variables. A type system ensures that condition variables are used safely, even while dynamic techniques change thread priorities at runtime to eliminate priority inversions in the use of mutexes. We prove the soundness of our system, using a model of priority inversions based on cost models for parallel programs. To show that the type system is practical to implement, we encode it within the type systems of Rust and C++, and show that the restrictions are not overly burdensome by writing sizeable case studies using these encodings, including porting the Memcached object server to use our C++ implementation.

References

[1]
2009. Memcached. https://memcached.org/ Accessed in July 2019
[2]
Umut A. Acar, Arthur Charguéraud, Adrien Guatto, Mike Rainey, and Filip Sieczkowski. 2018. Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2018). 769–782. isbn:978-1-4503-5698-5
[3]
Umut A. Acar, Arthur Charguéraud, and Mike Rainey. 2016. Oracle-guided scheduling for controlling granularity in implicitly parallel languages. Journal of Functional Programming (JFP), 26 (2016), e23.
[4]
Amal Ahmed, Matthew Fluet, and Greg Morrisett. 2007. L^ 3: A Linear Language with Locations. Fundam. Inform., 77, 4 (2007), 397–449.
[5]
Jatin Arora, Sam Westrick, and Umut A. Acar. 2021. Provably Space-Efficient Parallel Functional Programming. 5, POPL (2021), Article 18, Jan, 33 pages. https://doi.org/10.1145/3434299
[6]
Arvind and K. P. Gostelow. 1978. The Id Report: An Asychronous Language and Computing Machine. Department of Information and Computer Science, University of California, Irvine.
[7]
Özalp Babaoğlu, Keith Marzullo, and Fred B. Schneider. 1993. A Formalization of Priority Inversion. Real-Time Systems, 5, 4 (1993), 285–303.
[8]
Guy Blelloch and John Greiner. 1995. Parallelism in sequential functional languages. In Proceedings of the 7th International Conference on Functional Programming Languages and Computer Architecture (FPCA ’95). ACM, 226–237.
[9]
Guy E. Blelloch and John Greiner. 1996. A provable time and space efficient implementation of NESL. In Proceedings of the 1st ACM SIGPLAN International Conference on Functional Programming. ACM, 213–225.
[10]
John Boyland. 2003. Checking interference with fractional permissions. In International Static Analysis Symposium. 55–72.
[11]
Richard P. Brent. 1974. The parallel evaluation of general arithmetic expressions. J. ACM, 21, 2 (1974), 201–206.
[12]
Manuel M. T. Chakravarty, Roman Leshchinskiy, Simon L. Peyton Jones, Gabriele Keller, and Simon Marlow. 2007. Data parallel Haskell: a status report. In Proceedings of the POPL 2007 Workshop on Declarative Aspects of Multicore Programming, DAMP 2007, Nice, France, January 16, 2007. 10–18.
[13]
Philippe Charles, Christian Grothoff, Vijay Saraswat, Christopher Donawa, Allan Kielstra, Kemal Ebcioglu, Christoph von Praun, and Vivek Sarkar. 2005. X10: an object-oriented approach to non-uniform cluster computing. In Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (OOPSLA ’05). ACM, 519–538.
[14]
Dennis Cornhill and Lui Sha. 1987. Priority Inversion in Ada. Ada Letters, VII, 7 (1987), Nov., 30–32. issn:1094-3641 https://doi.org/10.1145/36072.36073
[15]
Karl Crary, David Walker, and Greg Morrisett. 1999. Typed Memory Management in a Calculus of Capabilities. In Conference Record of the 26th ACM Symposium on Principles of Programming Languages, San Antonio, Texas. 262–275.
[16]
Tommaso Cucinotta. 2013. Priority Inheritance on Condition Variables. Proceedings of the 9th International Workshop on Operating Systems Platforms for Embedded Real-Time applications (OSPERT 2013).
[17]
Derek L. Eager, John Zahorjan, and Edward D. Lazowska. 1989. Speedup versus efficiency in parallel systems. IEEE Transactions on Computing, 38, 3 (1989), 408–423.
[18]
Matthew Fluet, Mike Rainey, John Reppy, and Adam Shaw. 2011. Implicitly threaded parallelism in Manticore. Journal of Functional Programming, 20, 5-6 (2011), 1–40.
[19]
Matthew Fluet, Mike Rainey, John Reppy, Adam Shaw, and Yingqi Xiao. 2007. Manticore: A Heterogeneous Parallel Language. In Proceedings of the 2007 Workshop on Declarative Aspects of Multicore Programming (DAMP ’07). 37–44. isbn:978-1-59593-690-5
[20]
Jean-Yves Girard. 1987. Linear logic. Theoretical Computer Science, 50, 1 (1987), 1–101. issn:0304-3975 https://doi.org/10.1016/0304-3975(87)90045-4
[21]
Dan Grossman, Greg Morrisett, Trevor Jim, Michael Hicks, Yanling Wang, and James Cheney. 2002. Region-Based Memory Management in Cyclone. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation (PLDI ’02). Association for Computing Machinery, New York, NY, USA. 282–293. isbn:1581134630 https://doi.org/10.1145/512529.512563
[22]
Robert H. Halstead. 1985. MULTILISP: a language for concurrent symbolic computation. ACM Transactions on Programming Languages and Systems, 7 (1985), 501–538.
[23]
Robert H. Halstead, Jr. 1984. Implementation of Multilisp: Lisp on a Multiprocessor. In Proceedings of the 1984 ACM Symposium on LISP and functional programming (LFP ’84). ACM, 9–17.
[24]
Per Brinch Hansen. 1973. Operating system principles. Prentice-Hall, Inc.
[25]
Per Brinch Hansen. 1975. The programming language concurrent pascal. IEEE Transactions on Software Engineering, 199–207.
[26]
Stefan Heule, Rustan Leino, Peter Müller, and Alexander J. Summers. 2011. Fractional Permissions without the Fractions. In FTfJP’11, July 26, 2011, Lancaster, UK.
[27]
Charles Antony Richard Hoare. 1974. Monitors: An operating system structuring concept. In The origin of concurrent programming. Springer, 272–294.
[28]
Shams Mahmood Imam and Vivek Sarkar. 2014. Habanero-Java library: a Java 8 framework for multicore programming. In 2014 International Conference on Principles and Practices of Programming on the Java Platform Virtual Machines, Languages and Tools, PPPJ ’14. 75–86.
[29]
Butler W. Lampson and David D. Redell. 1980. Experience with Processes and Monitors in Mesa. Commun. ACM, 23, 2 (1980), 105–117.
[30]
Stefan K. Muller, Umut A. Acar, and Robert Harper. 2017. Responsive Parallel Computation: Bridging Competitive and Cooperative Threading. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2017). ACM, New York, NY, USA. 677–692. isbn:978-1-4503-4988-8
[31]
Stefan K. Muller, Umut A. Acar, and Robert Harper. 2018. Competitive Parallelism: Getting Your Priorities Right. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP ’18).
[32]
Stefan K. Muller, Kyle Singer, Noah Goldstein, Umut A. Acar, Kunal Agrawal, and I-Ting Angelina Lee. 2020. Responsive Parallelism with Futures and State. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2020). Association for Computing Machinery, New York, NY, USA. 577–591. isbn:9781450376136 https://doi.org/10.1145/3385412.3386013
[33]
Stefan K. Muller, Kyle Singer, Devyn Terra Keeney, Andrew Neth, Kunal Agrawal, I-Ting Angelina Lee, and Umut A. Acar. 2023. Responsive Parallelism with Synchronization. arxiv:2304.03753.
[34]
Stefan K. Muller, Sam Westrick, and Umut A. Acar. 2019. Fairness in Responsive Parallelism. In Proceedings of the 24th ACM SIGPLAN International Conference on Functional Programming (ICFP 2019).
[35]
Karl Naden, Robert Bocchino, Jonathan Aldrich, and Kevin Bierhoff. 2012. A Type System for Borrowing Permissions. In Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’12). Association for Computing Machinery, New York, NY, USA. 557–570. isbn:9781450310833 https://doi.org/10.1145/2103656.2103722
[36]
Simon L. Peyton Jones, Roman Leshchinskiy, Gabriele Keller, and Manuel M. T. Chakravarty. 2008. Harnessing the Multicores: Nested Data Parallelism in Haskell. In FSTTCS. 383–414.
[37]
Ram Raghunathan, Stefan K. Muller, Umut A. Acar, and Guy Blelloch. 2016. Hierarchical Memory Management for Parallel Programs. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016). ACM, New York, NY, USA. 392–406.
[38]
John C. Reynolds. 1974. Towards a theory of type structure. In Programming Symposium, Proceedings Colloque sur la Programmation, Paris, France, April 9-11, 1974. 408–423.
[39]
Mads Rosendahl. 1989. Automatic complexity analysis. In FPCA ’89: Functional Programming Languages and Computer Architecture. ACM, 144–156.
[40]
David Sands. 1990. Complexity Analysis for a Lazy Higher-Order Language. In ESOP ’90: Proceedings of the 3rd European Symposium on Programming. Springer-Verlag, London, UK. 361–376.
[41]
Lui Sha, Ragunathan Rajkumar, and John P Lehoczky. 1990. Priority inheritance protocols: An approach to real-time synchronization. IEEE Transactions on computers, 39, 9 (1990), 1175–1185.
[42]
Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne. 2005. Operating system concepts (7. ed.). Wiley.
[43]
Kyle Singer, Noah Goldstein, Stefan K. Muller, Kunal Agrawal, I-Ting Angelina Lee, and Umut A. Acar. 2020. Priority Scheduling for Interactive Applications. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, New York, NY, USA. 465–477. isbn:9781450369350 https://doi.org/10.1145/3350755.3400236
[44]
Frederick Smith, David Walker, and J. Gregory Morrisett. 2000. Alias Types. In Proceedings of the 9th European Symposium on Programming Languages and Systems (ESOP ’00). Springer-Verlag, London, UK, UK. 366–381.
[45]
Sam Westrick, Rohan Yadav, Matthew Fluet, and Umut A. Acar. 2020. Disentanglement in Nested-Parallel Programs. In Proceedings of the 47th Annual ACM Symposium on Principles of Programming Languages (POPL).

Cited By

View all
  • (2024)Disentanglement with Futures, State, and InteractionProceedings of the ACM on Programming Languages10.1145/36328958:POPL(1569-1599)Online publication date: 5-Jan-2024
  • (2024)Automatic Parallelism ManagementProceedings of the ACM on Programming Languages10.1145/36328808:POPL(1118-1149)Online publication date: 5-Jan-2024

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages
Proceedings of the ACM on Programming Languages  Volume 7, Issue PLDI
June 2023
2020 pages
EISSN:2475-1421
DOI:10.1145/3554310
Issue’s Table of Contents
This work is licensed under a Creative Commons Attribution 4.0 International License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2023
Published in PACMPL Volume 7, Issue PLDI

Permissions

Request permissions for this article.

Check for updates

Badges

Author Tags

  1. condition variables
  2. cost semantics
  3. priority inversions
  4. type systems

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)201
  • Downloads (Last 6 weeks)16
Reflects downloads up to 13 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Disentanglement with Futures, State, and InteractionProceedings of the ACM on Programming Languages10.1145/36328958:POPL(1569-1599)Online publication date: 5-Jan-2024
  • (2024)Automatic Parallelism ManagementProceedings of the ACM on Programming Languages10.1145/36328808:POPL(1118-1149)Online publication date: 5-Jan-2024

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Full Access

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media