Lecture Notes for Concurrent Programming

15 August 2002 - Communicating Sequential Processes

• developed in the late 70s by hoare

  • first a notation, then a language (joyce, occam)

• communication channels

  • a named, bidirectional pipe

    • 1-1, n-1, and m-n communication

    • channels can be typed or not by messages carried

    • names are (usually) global

  • channels carry messages

    • a single anonymous value - 13

    • a named tuple - gcd(x, y)

  • operations to send and receive messages on channels

    • send(c, m) - send message m along channel c, usually abbreviated c!m

    • receive(c, m) - receive message m from channel c, usually abbreviated c?m

  • message transfer along a channel is matched and instantaneous (synchronous)

    • two messages match if

      • they have the same message name or both have no name

      • they have the same number of arguments

      • each argument in the same order has the same type

    • processes communicate via synchronous message passing

      • sender and receiver block until both are ready

      • communication is instantious

    • if more than one receiver matches, one is chosen arbitrarily - same for senders

• processes

  • a process interacts with its environment via messages sent along channels

    • there is no other way into or out of a process

    • no other synchronization needed

  • processes are formed from other processes

    • the skip process does nothing and terminates

    • c?m -> P - a process that receives message m from channel c and then behaves like process P

    • c!m -> P - a process that sends message m to channel c and then behaves like process P

      • a processe of the form c?m -> P or c?m -> P is called a communication-enabled processe

    • P ; Q - a process that behaves like process P and then process Q

    • P || Q - a process that behaves like processes P and Q running in parallel

    • P [] Q - a process that behaves like process P or process Q, but not both

      • P and Q are communication-enabled processes

      • if both are enabled, one is chosen at random

    • recursion implements looping

      swapper: 
        input?one -> input?two -> output!two -> output!one -> swapper
      

• guarded communication

  • synchronous message passing implies committing to a particular process, possibly blocking

  • the guarded communication tests for communication without bocking

    • if B is true and C is ready, exchange messages and execute S

  • guarded communication in an if or a do allows choice

  • if more than one guarded communication is ready, one is chosen

    merge:
      ( ( left?x -> skip [] right?x -> skip ) ; output!x ) -> merge
    

• examples

  • binary semaphore

    locked_mutex
      unlock?x -> lock?x -> locked_mutex
    
    unlocked_mutex
      lock?x -> unlock?x -> unlocked_mutex
    

  • readers-writers access

    db_empty()
      enter?reader() -> enter!ok() -> reader_in_db(1) ||
      enter?writer() -> enter!ok() -> writer_in_db()
    
    reader_in_db(cnt)
      enter?reader() -> enter!ok() -> reader_in_db(cnt + 1) ||
      enter?writer() -> reader_in_db_writer_waiting(cnt)
      exit?reader()  -> 
        if cnt == 1 
          db_empty() 
        else 
          reader_in_db(cnt - 1)
    
    writer_in_db()
      exit?writer -> db_empty()
    
    reader_in_db_writer_waiting()
      exit?reader() -> 
        if cnt == 1 
          enter!ok() -> db_empty() 
        else 
          reader_in_db_writer_waiting(cnt - 1)
    

This page last modified on 15 August 2002.