Week 5.b
CS5600
2/16 2022
https://naizhengtan.github.io/22spring/

1. Last time
2. Critical section
3. Bakery algorithm
4. Mutexes
--------------------------------------------

Admin

--Thur office hour changed to 9AM

--No class next Monday (Feb.21)

--Virtual class the Monday after next (Feb.28)

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

1. Last time

  - interesting question: are there zombie threads? [No]
    why not?

  - an example

    void *f(void *xx) {
        sleep(1);
        printf("this is f\n");
        exit(0);
    }

    int main(){
        pthread_t tid;
        pthread_create(&tid, NULL, f, NULL);
        pthread_join(tid, NULL);  // line X
        printf("this is main\n");
    }

    Question: what is the output? 
      [answer: "this is f"]

    Question: if we comment line X, what is the output?
      [answer: "this is main"]

  - Sequential consistency (SC)

    --examples: 

      SC trace:
      T1: W1(x)=1, R1(y)=2
      T2: W2(y)=2, R2(x)=1
        [why? a sequential order: W1,W2,R1,R2]

      non-SC trace:
      T1: W1(x)=1, R1(y)=0
      T2: W2(y)=2, R2(x)=0
         [why? cannot find a sequential order]
         note, this can happen in TSO (namely, your x86 machines)

    [show slides]

    --in fact, checking SC is NP-hard

  - multi-core CPU architecture
    [show slides]


2. Critical sections

    * critical sections intro (last time)
    * protecting critical sections
    * implementing critical sections

    --Solution must satisfy 3 properties:

        1. mutual exclusion
        only one thread can be in c.s. at a time        
                [this is the notion of atomicity]

        2. progress
        if no threads executing in c.s., one of the threads
        trying to enter a given c.s. will eventually get in
          (sometimes called "no lockout")

        3. bounded waiting
        once a thread T starts trying to enter the critical
        section, there is a bound on the number of other threads
        that may enter the critical section before T enters
          (sometimes called "no deadlock")

    --protecting critical sections.

        --want lock()/unlock() or enter()/leave() or acquire()/release()
        --lots of names for the same idea

        --in each case, the semantics are that once the thread of
        execution is executing inside the critical section, no other
        thread of execution is executing there

          --analogy: mutex => door for the room
            --lock/qcuire => close the door
            --unlock/release => open the door
                                (let the next person enter the room)

        [show handout week5a]
        Question: put f()/g() into critical sections on handout week5a,
                  will it make a difference? what about 1.c?

        [answer: 
           1.a: no;
           1.c: yes, the only possible output will be 3.]


    --implementing critical sections

        --"easy" way, assuming a uniprocessor machine: 

            enter() --> disable interrupts
            leave() --> reenable interrupts

            [convince yourself that this provides mutual exclusion]

        --bakery algorithm (see below)

        --we will study other implementations (locks) later.


2. Bakery algorithm

  --the first algorithm to implement critical section
    **without atomic memory primitives**

  --invented by Leslie Lamport, a Turing Award winner

  --idea: simulate bakery shop
    each customer takes a ticket with a number and
      will buy stuff when the number is called.

  "A New Solution of Dijkstra's Concurrent Programming Problem
   Communications of the ACM 17, 8 (August 1974), 453-455."

  [show algorithm]

  --bakery algorithm does not require atomic memory reads/writes.
    It works on "safe registers":
      if a read overlaps writes (they are concurrent operations), the read can return anything.
      if a read does not overlap with writes, the read will return the most recent write.


4. Mutexes

    -- Mutex : mutual exclusion object

    -- Usage:

        mutex_t m
        mutex_init(mutex_t* m)
        acquire(mutex_t* m)
        release(mutex_t* m)
        ....

        --pthread implementation:
         pthread_mutex_init(), pthread_mutex_lock(), ...

    --using critical sections
      [see handout]

        --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.]