Polling in concurrent programming

ABSTRACT

Hoare introduced the concept of polling in his Communicating Sequential Processes (CSP) to handle nondeterministic message communication in distributed and concurrent programming. In order to introduce the polling concept effectively in a programming language, the problems of simultaneous polling, effective termination, busy waiting, and expressive power in one-to-many or many-to-one communication must be solved. This paper discusses the concept of polling, the details about the problems, and how a new concurrent programming language, COPL, solves the problems. COPL introduces a general algorithm to establish a hierarchical relationship between two communicating processes, an efficient mechanism to handle polling termination, a flexible polling to avoid busy waiting, and implicit polling to add asymmetry in the language for more expressive power. [Key words: concurrent programming, programming languages, polling, nondeterminism, and distributed systems]

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: F. Baiardi , L. Ricci , M. Vanneschi, Static checking of interprocess communication in ECSP, ACM SIGPLAN Notices, v.19 n.6, p.290-299, June 1984
• 3: J.G.P. Barnes. "An Overview of Adam' Software and Practice Experience, 10, 1980, pp. 851-887.
• 4: Arthur Bernstein, Output Guards and Nondeterminism in “Communicating Sequential Processes”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.234-238, April 1980 [doi>10.1145/357094.357101]
• 5: Grady Booch, Software engineering with Ada, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1983
• 6: Per Brinch Hansen, Distributed processes: a concurrent programming concept, Communications of the ACM, v.21 n.11, p.934-941, Nov. 1978 [doi>10.1145/359642.359651]
• 7: P. B. Hansen, Joyce—a programming language for distributed systems, Software—Practice & Experience, v.17 n.1, p.29-50, Jan. 1987 [doi>10.1002/spe.4380170105]
• 8: G. N. Buckley , Abraham Silberschatz, An Effective Implementation for the Generalized Input-Output Construct of CSP, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.223-235, April 1983 [doi>10.1145/69624.357208]
• 9: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 10: Jerome A. Feldman, High level programming for distributed computing, Communications of the ACM, v.22 n.6, p.353-368, June 1979 [doi>10.1145/359114.359127]
• 11: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 12: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 13: Inmos Corp, Occam Programming Manual, Prentice Hall Trade, 1984
• 14: M. Jazayeri et al. "CSP/80 - A Language for Communicating Sequential Processes"' Proc. IEEE Compcon Fall 1980, Sep. 1980, pp. 736-740.
• 15: Michael B. Jones , Richard F. Rashid, Mach and Matchmaker: kernel and language support for object-oriented distributed systems, Conference proceedings on Object-oriented programming systems, languages and applications, p.67-77, September 29-October 02, 1986, Portland, Oregon, United States
• 16: Chul-Doo Jung, The coordinator and coordinator programming language (copl), 1988
• 17: Elliott Irving Organick, Computer system organization: The B5700/B6700 series (ACM monograph series), Academic Press, Inc., Orlando, FL, 1973
• 18: T.J. Roper and C.J. Barter. "A Communicating Sequential Process Language and Implementation'.' Softw. Prac. Exp., 1981, pp. 1215-1234.
• 19: A. Silberschatz. "Communication and Synchronization in Distributed Systems"' IEEE Trans. Softw. Eng., 5, 6, Nov. 1979, pp. 542-546.
• 20: J. Welsh and A. Lister. "A Comparative Study of Task Communication in Adam' Softw. Prac. Exp., 11, 1981, pp. 257-290.
• 21: R. Williamson and E. Horowitz. "Concurrent Communication and Synchronization Mechanisms?' Softw. Prac. andExp., 14, 2, Feb. 1984, pp. 135-151.
• 22: M. Young , A. Tevanian , R. Rashid , D. Golub , J. Eppinger, The duality of memory and communication in the implementation of a multiprocessor operating system, ACM SIGOPS Operating Systems Review, v.21 n.5, p.63-76, Nov. 1987

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Languages