Lecture Notes for Concurrent Programming

22 July 2003 - Monitors

• an advanced, and old (early 70s), concurrency control mechanism

  • provides both mutual exclusion and conditional synchronization

  • java has quasi monitors (brinch hansen's lament)

• a monitor is an abstract data type

  • like a strong class without inheritance

  • data are encapsulated without external access

    • references out of the monitor are blocked too

  • methods are the only externally visible feature

    • methods can be hidden too

    • an externally visible method is an entry

  • data may be initialized - like a static block in java

• monitor concurrency control

  • mutual exclusion

    • only one thread at a time is allowed in a monitor

    • monitor entries are (java) synchronized always

    • the mutex usually has fifo release - the entry queue

  • condition variables

    • a monitor's back porch

    • atomic unlock n block

    • there may be many condition variables per monitor

    • operations empty(), wait(), and signal() and variants

    • signal release behavior

      • condition variable release is usually fifo

      • the relation between signaled and signaler

        • signaled jumps to the front of the entry queue, signaler continues

        • signaler jumps to the front of the entry queue, signaled enters the monitor after the wait()

      • signals are not remembered

• monitor semantics

  • the monitor invariant - starts true, always true

    • the monitor initialization section establishes the invariant

  • defining "always" is not easy

    • outside entries, yes - inside, ?

  • a property per condition variable - noFull, notEmpty

  • finite state machines are a good model for monitor behavior

    • states represent properties and conditions

    • arcs are entry calls

    • not a replacement for invariants an non-interference proofs

• monitor evaluation

  • implemented sporadically in the 70s and 80s - concurrent pascal, modula, euclid, mesa

  • motivated other, similar constructs - java, ada

  • semantics tended to vary - release behavior, signaled-signaler relation

  • nested monitor calls lead to deadlock - easy to do given monitor independence

• example uses

  • semaphores

    monitor
    
      int count = 0   // invariant: 0 <= count <= 1
      cond nonzero    // condition: count = 1
    
      void up()
        count = 1
        positive.signal()
    
      void down()
        if count != 1, positive.wait()
        count = 0
    

    if may need to be while depending on release behavior

    

• readers-writers access

  • a pure mutex solution

    monitor rw_access
    
      bool db_empty = true
      cond empty_db
    
      enter()
        if !db_empty, empty_db.wait()
        db_empty = false
    
      exit()
        db_empty = true
        empty_db.signal()
    

    pure mutual exclusion (no concurrency)

    fifo release gives fairness and timeliness

    used in a before and after pattern

    rw_access.enter()
    // work the database
    rw_access.exit()
    

  • readers concurrency

    differentiate readers and writers for database state

    monitor rw_access
    
      bool writer_in_db = true
      int readers_in_db = 0
      cond clear_db
    
      reader_enter()
        while writer_in_db
          clear_db.wait()
        readers_in_db++
    
      reader_exit()
        readers_in_db--
        clear_db.signal_all()
    
      writer_enter()
        while writer_in_db and readers_in_db > 0
          clear_db.wait()
        writer_in_db = true
    
      writer_exit()
        writer_in_db = false
        clear_db.signal_all()
    

    how does release-all work?

This page last modified on 15 August 2002.