Week 7.b
CS3650
02/21 2024
https://naizhengtan.github.io/24spring/

1. Condition variable (cont'd)
2. Monitors and standards
3. Four-step design approach
4. Wrap up concurrency
----

- Admin: lab2 cheating

- Mental model of the concurrency programming

          [correct impl]
                  ^
                  |   +--[safe path]
  +--------------| |--|-------+
  | Concurrency  / /  |       |
  | World       / /<--+       |
  | (dangerous)/ /            |
  |           / /all sorts of |
  |          / / concurrency  |
  |         / /  bugs         |
  +---------| |---------------+
             ^
           [you]

  The "safe path" includes:
    * synchronization primitives:
        mutex and condition variable
    * organizing primitives: monitor
    * coding standards: the six commandments
    * problem solving: 4-step design approach

1. Condition variable (cont'd)

    A. Motivation
       producer/consumer problem: busy waiting

    B. Usage
       - void cond_init (Cond *, ...);
       - void cond_wait(Cond *c, Mutex* m);
       - void cond_signal(Cond* c);
       - void cond_broadcast(Cond* c);

       Q: what does cond_wait(...) do?

    [handout from last time]
    C. Important points

      (1) We MUST use "while", not "if". Why?

      --Because we can get an interleaving like this:

          --The signal() puts the waiting thread on the ready list
          but doesn't run it

          --That now-ready thread is ready to acquire() the mutex
          (inside cond_wait()).

          --But a *different* thread (a third thread: not the
          signaler, not the now-ready thread) could acquire() the
          mutex, work in the critical section, and now invalidates
          whatever condition was being checked

          --Our now-ready thread eventually acquire()s the
          mutex...

          --...with no guarantees that the condition it was
          waiting for is still true

      --Solution is to use "while" when waiting on a condition
      variable

      --DO NOT VIOLATE THIS RULE; doing so will (almost always)
      lead to incorrect code

          --NOTE: NOTE: NOTE: There are two ways to understand
          while-versus-if:
          (a) It's the 'while' condition that actually guards the program.
          (b) There's simply no guarantee when the thread comes out of
          wait that the condition holds. 

      (2) cond_wait releases the mutexes and goes into the waiting
      state in one function call (see panel 2b of the handout). 

          --QUESTION: Why?

      --Answer: can get stuck waiting.

          Producer: while (count == BUFFER_SIZE)
          Producer: release()
          Consumer: acquire()
          Consumer: .....
          Consumer: cond_signal(&nonfull)
          Producer: cond_wait(&nonfull)

      --Producer will never hear the signal!

2. Monitors and standards

   A. Monitors = mutex + condition variables

   --High-level idea: an object (as in object-oriented systems)

   --in which methods do not execute concurrently; and

   --that has one or more condition variables

   --More detail

   --Every method call starts with acquire(&mutex), and ends with
   release(&mutex)

   --Technically, these acquire()/release() are invisible to the
   programmer because it is the programming language (i.e., the
   compiler+run-time) that is implementing the monitor

       --So, technically, a monitor is a programming language
       concept

       --But technical definition isn't hugely useful because no
       programming languages in widespread usage have true monitors

       --Java has something close: a class in which every method is
       set by the programmer to be "synchronized" (i.e., implicitly
       protected by a mutex)

       --Not exactly a monitor because there's nothing forcing
       every method to be synchronized

       --And we can *use* mutexes and condition variables to
       implement our own manual versions of monitors, though we
       have to be careful

   --Given the above, we are going to use the term "monitor" more
   loosely to refer to both the technical definition and also a
   "manually constructed" monitor, wherein:

       --all method calls are protected by a mutex (that is, the
       programmer inserts those acquire()/release() on entry and
       exit from every procedure *inside* the object)

       --synchronization happens with condition variables whose
       associated mutex is the mutex that protects the method calls

   --In other words, we will use the term "monitor" to refer to the
   programming conventions that you should follow when building
   multithreaded applications

   --Example: see handout week7.b, panel 1

   B. Standards & why?

     - RULES:
      --acquire/release at beginning/end of methods
      --hold lock when doing condition variable operations
      --always use "while" to check invariants, not "if"

     - why?

       --Mike Dahlin stands on the desk when proclaiming the standards

       --see Mike D's "Programming With Threads"

       --You are required to follow this document

       --You will lose points (potentially many!) on
       the exam if you stray from these standards

       --Note that in his example in section 4, there needs to be
       another line:

       --right before mutex->release(), he should have:
           assert(invariants hold)

       --the primitives may seem strange, and the rules may seem
       arbitrary: why one thing and not another?

       --there is no absolute answer here

       --**However**, history has tested the approach that we're
       using. If you use the recommended primitives and follow
       their suggested use, you will find it easier to write
       correct code

    --For now, just take the recommended approaches as a given,
    and use them for a while. If you can come up with something
    better after that, by all means do so!

    --But please remember three things:

      a. lots of really smart people have thought really hard
      about the right abstractions, so a day or two of
      thinking about a new one or a new use is unlikely to
      yield an advance over the best practices.

      b. the consequences of getting code wrong can be
      atrocious. see for example:

      http://www.nytimes.com/2010/01/24/health/24radiation.html
      http://sunnyday.mit.edu/papers/therac.pdf
      http://en.wikipedia.org/wiki/Therac-25

      c. people who tend to be confident about their abilities
      tend to perform *worse*, so if you are confident you are
      a Threading and Concurrency Ninja and/or you think you
      truly understand how these things work, then you may
      wish to reevaluate.....

      --Dunning-Kruger effect
        --https://en.wikipedia.org/wiki/Dunning%E2%80%93Kruger_effect

    C. The six commandments

       --RULE:

       --acquire/release at beginning/end of methods

       --RULE:

       --hold lock when doing condition variable operations

       --Some people
           [for example, Andrew Birrell in this paper:
               http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-35.pdf ]
       will say: "for experts only, no need to
       hold the lock when signaling". IGNORE THIS. Putting the signal
       outside the lock is only a small performance optimization, and
       it is likely to lead you to write incorrect code.

       --Different styles of monitors:

         --Hoare-style: signal() immediately wakes the waiter

         --Hansen-style and what we will use:
         signal() eventually wakes the waiter. Not an immediate transfer

       --RULE:

       --a thread that is in wait() must be prepared to be restarted at
       any time, not just when another thread calls "signal()".

       --why? because the implementor of the threads and condition
       variables package *assumes* that the user of the threads package
       is doing while(){wait()}.

3. Four-step design approach

    A. Top-level piece of advice: SAFETY FIRST.

    --Locking at coarse grain is easiest to get right, so do
    that (one big lock for each big object or collection of
    them)

    --Don't worry about performance at first

    --In fact, don't even worry about liveness at first

        --In other words don't view deadlock as a disaster

    --Key invariant: make sure your program never does the wrong thing

    B. Four-step design approach:

        1. Getting started:

         1a. Identify units of concurrency. Make each a thread with
         a go() method or main loop. Write down the actions a thread
         takes at a high level.  

         1b. Identify shared chunks of state. Make each shared
         *thing* an object. Identify the methods on those objects,
         which should be the high-level actions made *by* threads
         *on* these objects. Plan to have these objects be protected by mutexes.

         1c. Write down the high-level main loop of each thread. 

        Advice: stay high level here. Don't worry about synchronization 
        yet. Let the objects do the work for you. 

        Separate threads from objects. The code associated with a
        thread should not access shared state directly (and so there
        should be no access to locks/condition variables in the
        "main" procedure for the thread). Shared state and
        synchronization should be encapsulated in shared objects. 

        --QUESTION: how does this apply to the example on the
        handout?
        --separate loops for producer(), consumer(), and
        synchronization happens inside MyBuffer.

        Now, for each object: 

        2. Write down the synchronization constraints on the
        solution. Identify the type of each constraint: mutual
        exclusion or scheduling. For scheduling constraints, ask,
        "when does a thread wait"?

        --NOTE: usually, the mutual exclusion constraint is
        satisfied by the fact that we're programming with
        monitors.

        --QUESTION: how does this apply to the example on the
        handout?
            --Only one thread can manipulate the buffer at a time
            (mutual exclusion constraint)
            --Producer must wait for consumer to empty slots if all
            full (scheduling constraint)
            --Consumer must wait for producer to fill slots if all
            empty (scheduling constraint)

        3. Create a lock or condition variable corresponding to each 
        constraint 

        --QUESTION: how does this apply to the example on the
        handout?
            --Answer: need a lock and two condition variables.
            (lock was sort of a given from the fact of a monitor).

        4. Write the methods, using locks and condition variables for 
        coordination

    C. Applying the approach to a new problem

    Consider a database with multiple readers and writers.
    The high−level goal here is
      (a) to give a writer exclusive access
          (a single active writer means there should be no other writers
          and no readers)
      while (b) allowing multiple readers.

    * A possible solution:

     1. Getting started
         a. what are units of concurrency? [readers/writers]
         b. what are shared chunks of state? [database]
         c. what does the main function look like?

            --read()
              check if writers exist
                 (wait until no writers)
              access DB

            --write()
              check if readers or writers exist
                  (wait until no readers or writers)
              access DB

     2. and 3. Synchronization constraints and objects

            --only one thread manipulates reader/writer numbers at a time;
              only one thread modifies DB at a time.
              NOTE: **this does not mean only one thread in the DB at a time**
              (use mutex)

            --reader can access DB when no writers
              (use a condition variable: okToRead)

            --writer can access DB when no other readers or writers
              (use a condition variable: okToWrite)

     4. Implementing this: see handout
    ]

4. Wrap up

  [skipped most parts]
  -- mental model: dangerous concurrency world
    never ever try to create your own synchronization;
    they are likely to be broke
      (why? so many ways to go wrong.
      for example, hardware consistency model is tricky.
      don't build a castle on a swamp)

  -- what're we doing here?
    Writing correct concurrent code.
    What does that mean?
    usually mean that the concurrent code runs as if it behaves like
    single-threaded---maintaining some invariants.

  -- What is "invariant"?
    for producer/consumer case:

    if adding a line:
      assert count == items(buffer)
    to **anywhere** outside critical sections,
    the program does not crash.

    then, "count == iterms(buffer)" is the invariant
    for this program.

  -- critical section:
    -- invariant always holds outside critical section
    -- one can only manipulate invariant within c.s.,
       and has to restore invariant when exiting c.s.

  -- two synchronization primitives
    -- mutex: providing mutual exclusion
    -- condition variable: providing scheduling constraints

  -- Monitor
    -- an object (= mutex + condition variables)
    -- should be a language primitive
    -- for us, in C: a programming convention

  -- "the safe way": Monitor + 6 rules + 4-step design approach
    -- 6 rules:
      -- must memorize! (one of few things I require you to recite)
    -- 4-step design approach

   -- Don't manipulate synchronization variables or shared state
    variables in the code associated with a thread; do it with the
    code associated with a shared object.

        --Threads tend to have "main" loops. These loops tend to
        access shared objects. *However*, the "thread" piece of it
        should not include locks or condition variables. Instead,
        locks and CVs should be encapsulated in the shared objects.

        --Why?

        (a) Locks are for synchronizing across multiple threads.
        Doesn't make sense for one thread to "own" a lock.

        (b) Encapsulation -- details of synchronization are
        internal details of a shared object. Caller should not
        know about these details.  "Let the shared objects do
        the work."

        --Common confusion: trying to acquire and release locks
        inside the threads' code (i.e., not following this advice).
        Bad idea! Synchronization should happen within the shared
        objects. Mantra: "let the shared objects do the work".

        --Note: our first example of condition variables --
        handout, item 2b -- doesn't actually follow the advice, but
        that is in part so you can see all of the parts working
        together.

    -- Different way to state what's above:
        --You want to decompose your problem into objects, as in
        object-oriented style of programming.

        --Thus:

        (1) Shared object encapsulates code, synchronization 
        variables, and state variables

        (2) Shared objects are separate from threads