Week 4.b
CS5600
10/01 2021
https://naizhengtan.github.io/21fall/

1. Last time
2. Mutexes
3. Condition variables

--------------------------------------------

Admin

- Lab1
  -- slackhours vs. Canvas timestamp
  -- 20min grace period

- office hours first, then mailing list (best-effort service)

- reading notes is a _must_, instead of optional

- survey:
  -- 1/3 took the survey
  -- 50% think the course is hard
  -- 29% are suffering
  --exam: minimum recitation needed
    --"as a programmer, how much information you will remember";
      that's the bar of how detail you need to have for exam
  --homework: answers published

  --"I think I understand; but not sure for homeworks"
    --ALERT: a strong signal that you miss something
    --the right feeling: "Ha, professor is asking this"
      --see the things behind the question (or why the question exist?)

--------------------------------------------

1. Last time

    -- two problematic cases: 
      --linked list
      --producer/consumer
      [draw on board]

    -- logically impossible case which can happen in practice
      [draw the 4.c case from handout week3.b]

    -- sequential consistency
      --"formal definition of how people think of concurrency"

    -- intro to critical section; three properties
      --mutual exclusion
      --progress
      --bounded waiting

    -- to protect a critical section
      --acuire() before entering
      --release() after leaving


2. Mutexes

    -- Mutex : mutual exclusion object

    --using critical sections

        -- see handout week 4.a, panel 2.a

        --linked list example

        --bounded buffer example

    --why are we doing this?

        --because *atomicity* is required if you want to reason about
        the correctness of concurrent code

        --atomicity requires mutual exclusion aka a solution to critical
        sections

        --mutexes provide that solution

        --once you have mutexes, don't have to worry about arbitrary
        interleavings. critical sections are interleaved, but those are
        much easier to reason about than individual operations.

        --why? because of _invariants_.

            examples of invariants:

            "list structure has integrity"

            "'count' reflects the number of entries in the buffer"

        the meaning of lock.acquire() is that if and only if you get
        past that line, it's safe to violate the invariants.

        the meaning of lock.release() is that right _before_ that line,
        any invariants need to be restored.

        the above is abstract.

        let's make it concrete:

            invariant: "list structure has integrity"

            so protect the list with a mutex

            only after acquire() is it safe to manipulate the list

    --Question: by the way, why aren't we worried about *processes*
      trashing each other's memory?

      [answer: because the OS, with the help of the hardware,
      arranges for two different processes to have isolated memory
      space. such isolation is one of the uses of virtual memory,
      which we will study in a few weeks.]


3. Condition variables

    A. Motivation

        --producer/consumer queue 

        --very common paradigm. also called "bounded buffer":

            --producer puts things into a shared buffer
            --consumer takes them out
            --producer must wait if buffer is full; consumer must
              wait if buffer is empty
            --shows up everywhere
            --Soda machine: producer is delivery person, consumer
                is soda drinkers, shared buffer is the machine
            --OS implementation of pipe()
            --DMA buffers

    --producer/consumer queue using mutexes (see handout week4.a, 2a)

        --what's the problem with that?

          --hint: think of 1 producer and 100 consumers

        --answer: a form of *busy waiting* 
          --99% of the time, consumers are running but have nothing to consume

    --It is convenient to break synchronization into two types:

        --*mutual exclusion*: allow only one thread to access a given
        set of shared state at a time

        --*scheduling constraints*: wait for some other thread to do
        something (finish a job, produce work, consume work, accept
        a connection, get bytes off the disk, etc.)


    B. Usage

    --API

        --void cond_init (Cond *, ...); 
        --Initialize
          [note: you have to init a condition variable first!]

        --void cond_wait(Cond *c, Mutex* m);
        --Atomically unlock m and sleep until c signaled 
        --Then re-acquire m and resume executing 

        --void cond_signal(Cond* c);
        --Wake one thread waiting on c

        [in some pthreads implementations, the analogous
        call wakes *at least* one thread waiting on c. Check the
        the documentation (or source code) to be sure of the
        semantics. But, actually, your implementation shouldn't
        change since you need to be prepared to be "woken" at
        any time, not just when another thread calls signal().
        More on this below.]

        --void cond_broadcast(Cond* c);
        --Wake all threads waiting on c

    C. Important points

       - Read handout week 4.a, panel 2.b

        (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 week4a). 

            --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!

    Discussion: thread_cond_wait implementation

    --pthread implementation: 
    https://code.woboq.org/userspace/glibc/nptl/pthread_cond_wait.c.html

        thread_cond_wait(...) {

            release lock;

            do {
                wait-for-signal;
            } while (!signal)

            acquire lock;
        }