Scheme fair threads

ABSTRACT

This paper presents Fair Threads, a new model for concurrent programming. This multi-threading model combines preemptive and cooperative scheduling. User threads execute according to a cooperative strategy. Service threads execute according to a preemptive strategy. User threads may ask services from service threads in order to improve performance by exploiting hardware parallelism and in order to execute non-blocking operations.Fair threads are experimented within the context of the functional programming language Scheme. This paper also presents the integration in this language. That is, it presents a semantics for Scheme augmented with Fair Threads and the main characteristics of the implementation.

REFERENCES

• 1: Atul Adya , Jon Howell , Marvin Theimer , William J. Bolosky , John R. Douceur, Cooperative Task Management Without Manual Stack Management, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.289-302, June 10-15, 2002
• 2: Joe Armstrong , Robert Virding , Claes Wikström , Mike Williams, Concurrent programming in ERLANG (2nd ed.), Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1996
• 3: Gérard Berry , Georges Gonthier, The ESTEREL synchronous programming language: design, semantics, implementation, Science of Computer Programming, v.19 n.2, p.87-152, Nov. 1992 [doi>10.1016/0167-6423(92)90005-V]
• 4: Biagioni, E. and Cline, K. and Lee, P. and Okasaki, C. and Stone, C. -- Safe-for-Space Threads in Standard ML -- Proc. 2nd ACM SIGPLAN Workshop on Continuations, 1996.
• 5: Birrell, A. -- An Introduction to programming with threads -- 35, DEC Systems Research Center, Palo-Alto, CA, USA, Jan, 1989.
• 6: Boussinot, F. -- Java Fair Threads -- Research Report, RR-4139, Inria, 2001.
• 7: Cardelli, L. and al. -- Modula-3 Report (revised) -- 52, DEC Systems Research Center, Palo-Alto, CA, USA, Nov, 1989.
• 8: Chankhunthod, A. and Danzig, P. and Neerdaels, C., Schwartz, M., Worrell, K. -- A Hierarchical Internet Object Cache -- Proceedings of the Usenix Annual Technical Conference, 1996, pp. 153--164.
• 9: R. K. Dybvig , R. Hieb, Engines from continuations, Computer Languages, v.14 n.2, p.109-123, Aug. 1989 [doi>10.1016/0096-0551(89)90018-0]
• 10: Engelschall, R. -- Portable Multithreading - The Signal Stack Trick for User-Space Thread Creation -- Proceedings of the Usenix Annual Technical Conference, San Diego, CA, USA, Jun, 2000.
• 11: Feeley, M. -- SRFI 18: Multithreading support -- 2000.
• 12: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 13: Hazard, L. and Susini, J-F. and Boussinot, F. -- The Junior reactive kernel -- Research Report RR-3732, Inria, Jul, 1999.
• 14: Hazard, L. and Susini, J-F. and Boussinot, F. -- Programming with Junior -- Research Report RR-4027, Inria, 2000.
• 15: Hollub, A. -- Taming Java Threads -- Apress, 2000.
• 16: Philippe Joubert , Robert B. King , Richard Neves , Mark Russinovich , John M. Tracey, High-Performance Memory-Based Web Servers: Kernel and User-Space Performance, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.175-187, June 25-30, 2001
• 17: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams Iv , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand, Revised Report on the Algorithmic Language Scheme, Higher-Order and Symbolic Computation, v.11 n.1, p.7-105, August 1998 [doi>10.1023/A:1010051815785]
• 18: Richard A. Kelsey , Jonathan A. Rees, A tractable Scheme implementation, Lisp and Symbolic Computation, v.7 n.4, p.315-335, Dec. 1994 [doi>10.1007/BF01018614]
• 19: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States
• 20: James R. Larus , Michael Parkes, Using Cohort-Scheduling to Enhance Server Performance, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.103-114, June 10-15, 2002
• 21: Lea, D. and Pugh, B. -- Correct and Efficient Synchronization of Java Technology-based Threads -- JavaOne, 2000.
• 22: Luis Mateu, An Efficient Implementation for Coroutines, Proceedings of the International Workshop on Memory Management, p.230-247, September 17-19, 1992
• 23: Bradford Nichols , Dick Buttlar , Jacqueline Proulx Farrell, Pthreads programming, O'Reilly & Associates, Inc., Sebastopol, CA, 1996
• 24: Ousterhout, J. -- Why Threads Are a Bad Idea (for most purposes) -- Invited talk of the USENIX Winter Technical Conference, Jan, 1996.
• 25: Simon Peyton Jones , Andrew Gordon , Sigbjorn Finne, Concurrent Haskell, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-308, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237794]
• 26: William Pugh, Fixing the Java memory model, Proceedings of the ACM 1999 conference on Java Grande, p.89-98, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304106]
• 27: Christian Queinnec , Kathleen Callaway, Lisp in small pieces, Cambridge University Press, New York, NY, 1996
• 28: John H. Reppy, Asynchronous Signals is Standard ML, Cornell University, Ithaca, NY, 1990
• 29: John H. Reppy, Concurrent programming in ML, Cambridge University Press, New York, NY, 1999
• 30: John C. Reynolds, G/EDANKEN—a simple typeless language based on the principle of completeness and the reference concept, Communications of the ACM, v.13 n.5, p.308-319, May 1970 [doi>10.1145/362349.362364]
• 31: Bernard Paul Serpette , Manuel Serrano, Compiling scheme to JVM bytecode:: a performance study, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.259-270, October 04-06, 2002, Pittsburgh, PA, USA
• 32: Serrano, M. -- Bigloo user's manual -- 0169, INRIA-Rocquencourt, France, Dec, 1994.
• 33: Shivers, O. -- Continuations and threads: Expressing machine concurrency directly in advanced languages -- ACM SIGPLAN Workshop on Continuations, Paris, France, Jan, 1997.
• 34: Olin Shivers , James W. Clark , Roland McGrath, Atomic heap transactions and fine-grain interrupts, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.48-59, September 27-29, 1999, Paris, France
• 35: Vivek, S. and Druschel, P. and Zwaenepoel, W. -- Flash: An efficient and portable Web server -- Proceedings of the Usenix Annual Technical Conference, Monterey, CA, USA, Jun, 1999.
• 36: Mitchell Wand, Continuation-Based Multiprocessing, Higher-Order and Symbolic Computation, v.12 n.3, p.285-299, October 1999 [doi>10.1023/A:1010093700911]
• 37: N. Wirth, Programming in Modula-2, Springer-Verlag Telos, 1983

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling; Threads; Concurrency; Synchronization

General Terms:
Experimentation, Languages

Keywords:
concurrency, functional languages, scheme, threads