HW3 answers
released: 10/12, 22:00

> - Read Mike Dahlin's "Basic Threads Programming: Standards and Strategy"
>   (https://naizhengtan.github.io/21fall/notes/programming-with-threads.pdf)
> - Study 10/05's lecture handout 
>   (https://naizhengtan.github.io/21fall/notes/handout_5a.pdf)
> and answer the following questions.
> Submit your answers to Canvas assignments. There is an entry for this homework.
> 
> 
> Question 1: is the program still correct if we replace the "cond_signal" at
> handout line 48 with "cond_broadcast"? (yes/no) Why? (explain in 1-2 sentences)

Yes.

Because the "cond_wait" at line 57 guarantees that only one thread will acquire
the mutex, and the "while" at line 56 guarantees whoever having the mutex will
check the condition (i.e., count == 0) before moving forward.


[cheng: btw, if you follow our rules, it is always safe to replace "signal"
with "broadcast", but at the cost of efficiency---waking too many threads is a
waste of CPU cycles.]

> 
> Question 2: here is the "database problem" we discussed on class:
> 
>     """
>     - readers and writers interact with a database
>     - readers never modify database
>     - writers read and modify data
>     - we allow multiple readers touching the database
>     - we only allow one writer (no other readers) touching the database
>     """
> 
>     Follow Mike Dahlin's problem solving strategy (S3 in his write-up)
>     and write down your step 1-3 below.
> 

Answer:

[cheng: below is just one answer; you can have something totally different]

1.
  1.a  readers and writers
  1.b  database
  1.c
       reader loop:
         if writers exits:
           wait
         else:
           access DB

       writer loop:
         if reader exists or writer exits:
           wait
         else:
           access DB

2.
  (a) mutual exclusion:
      only one thread manipulates reader/writer numbers at a time;
      only one thread modifies DB at a time.

  (b) scheduling constraint 1:
      reader can access DB when no writers

  (c) scheduling constraint 2:
      writer can access DB when no readers or writers

3. 
  one mutex for (a) in the step 2
  one condition variable, okToRead, for (b)
  one condition variable, okToWrite, for (c)

> 
> Question 3: read the "smoker problem" and write down the first 3 steps of our
> problem solving strategy.
> 
>   """
>   smoker problem
>   - There are three smokers and one agent.
>   - Each smoker continuously rolls a cigarette and then smokes it.
>   - But to roll and smoke a cigarette, the smoker needs three ingredients: tobacco, paper, and matches.
>   - One of the smoker has paper, another has tobacco, and the third has matches.
>   - The agent has an infinite supply of all three materials.
>   - The agent randomly places two of the ingredients on the table.
>   - The smoker who has the remaining ingredient then makes and smokes a cigarette, telling the agent on completion.
>   - The agent then puts out another two of the three ingredients, and the cycle repeats.
>   """
> 
Answer:

[cheng: again, it is likely that your answer is different]

1. 
  1.a three smoker and an agent
  1.b tobacco, paper, matches
  1.c 

    agent loop:
      randomly pick two items from the three items (tobacco, paper, and matches)
      place them on table
      wait smokers to finish

    smoker loop:
      check the items on table
      decide if I can roll a cigarette with the items
      if yes:
        roll, smoke, and ping the agent
      if not:
        go away (or ping other smokers)

2.

  (a) mutual exclusion:
      among four people (3 smokers and an agent), only one can touch the
      table---putting or fetching items

  (b) scheduling constraint 1:
      agent can dispatch items when the table is empty

  (c) scheduling constraint 2:
      (some) smoker can roll&smoke when there are items on the table

3. 

  a mutex for (a)
  a condition variable, tableEmpty, for (b)
  a condition variable, tableFull, for (c)

[note: you can design more efficient solutions with condition variables
for different situations.]


> Question 4: Read the handout panel 2 and answer the question at line 178 in 1-2 sentences.
> 

A constant stream of writers will prevent readers acquiring the mutex, a starvation.

[note: see line 131; for a reader, it will wait if there are either active
writers (AW) or waiting writers (WW). Thus, writers will not starve because of
readers.]


> Question 5: Read the handout panel 3 and answer the question B at line 223 below.
> (note: write pseudocode like the handout; use comments to explain if necessary)
> 

Answer:

sharedlock lock;

Database::read() {
  AcuiqreShared(&lock);

  // read database

  ReleaseShared(&lock);
}

Database::write() {
  AcuiqreExclusive(&lock);

  // write database

  ReleaseExclusive(&lock);
}