Week 9

Question 1

What are the design goals for counters.

Answer 1

Correctness: how do we make the above operations works as expected with multiple threads?

Performance: how do we allow many threads to access the structure/

Question 2

What is a sloppy counter?

Answer 2

> Performance goal is perfect scaling: threads should complete just as quickly on multiple processors as a single thread does on one.

> How do we improve scaling for counters? We give each core its own local counter
- Be we also relax some assumptions: We no longer assume the counter is exact, only that it is close to the real value.

Question 3

What are condition variables?

Answer 3

A condition variable is a synchronization mechanism allowing threads to:
- wait until a condition is true, and
- signal other threads when the condition becomes true.

Question 4

What is the bounded buffer problem?

What’s the condition in the bounded buffer problem.

Answer 4

Imagine we have one or more producer threads placing items in a buffer.

We also have one or more consumer threads grabbing items from that
buffer.

Problem: The buffer is a shared resource; how do we synchronize access?

What’s the condition in the bounded buffer problem?
- wait: notify me when the buffer has data
- signal: I just put data in the buffer, so notify the threads waiting for the
buffer to have data

Question 5

What are semaphores?

Answer 5

Semaphores are another synchronization primitive. Can initialize the semaphore to any integer, but can only increment or decrement after that.

> They can be used as both a lock and a condition variable.
Unlike locks and condition variables, semaphores can be used to synchronize across different processes.
POSIX Inferface: sem_wait() and sem_post()
- sem_wait(): decrement the value of the semaphore s by one and wait/sleep if is if negative
- sem_post(): increment the value of the semaphore s by one, if there are one or more threads waiting, wake one.

Question 6

How can we use a semaphore as a lock?

Answer 6

• Surround the critical section with a sem_wait and sem_post.
• Set the initial value of the semaphore to 1.
• How does the semaphore’s value change if we have more than two threads? A negative value is equal to the number of threads
  waiting.

Question 7

True or false, When you create the semaphore, you can initialize its value to any integer, but after that the only operations you are allowed to perform are increment (increase by one) and decrement (decrease by one). You cannot read the current value of the semaphore

Answer 7

True

Question 8

True or false, when you signal a semaphore, you know whether another thread is waiting.

Answer 8

False. When you signal a semaphore, you don’t necessarily know whether another thread is waiting, so the number of unblocked threads may be zero or one.

Question 9

What are deadlocks?

Answer 9

Deadlocks occur when a thread or set of threads are waiting for each other to finish and thus nobody ever does.

Question 10

A deadlock only occurs if all of the following conditions are met:

Answer 10

• mutual exclusion: threads claim exclusive access to shared resources m(e.g., thread grabs a lock)
• hold-and-wait: a thread can hold some resources while requesting others,
• no resource preemption: the system cannot forcibly take a resource from
  a thread holding it,
• circular wait: meaning that Thread A is waiting for Thread B which is waiting for Thread C which is waiting for Thread A.