Part 9 - Semaphores

What is a semaphore?

Semaphores control the number of user transactions that can be run in parallel. It makes sure there aren't too many things running at once. It does this by keeping an internal integer value that can be incremented or decremented and based on its value it may wake up a waiting thread.

What two main functions exists for interacting with semaphores?

- sem_wait()

- sem_post()

What does sem_wait() do?

It decrements the semaphore's integer value. If the value now is greater than 0, then it resumes. If not then it is placed in a waiting queue.

What does sem_post() do?

It increments the semaphore's integer value. If the integer value now is greater than 0, wake up a thread in the queue. If not, do nothing.

What do we call it whenever we make a semaphore only be able to have one executing thread at a time?

A binary semaphore

What should the initial value of a binary semaphore be?

1, because then a wait call will serve as the lock function

What other synchronization primitive does a binary semaphore resemble?

A lock

What differentiates a binary semaphore and a lock?

A lock can only be released by the owner while a semaphore might be posted to by any thread.

What should the initial value of a semaphore be if we want to use it like a condition variable?

0, because then the parent can wait before it is posted to

What is a deadlock?

A set of theads that are all waiting for an event that can only be caused by another thread in the set. Therefore it will never fire.

When using semaphores to solve the producer/consumer problem (bounded-buffer), what is important to keep in mind to avoid deadlocks?

To only wrap the critical section with a semaphore that functions as a mutex lock. That means that the empty/full semaphore wait needs to come before the mutex semaphore.

What types of locks are based on semaphores?

- Binary semaphores

- Reader-Writer locks

What is the purpose of a reader-writer lock?

Only allow one thread to write at a time, but allow many readers to read at a time. Also don't allow write if any readers are active.

How does a reader-writer lock work?

Whenever a thread wants to write, acquire the write lock. Then release when done.

Whenever a thread wants to read, acquire the read lock and increment the semaphore value. The first reader must also acquire the write lock and the last reader to finish must call sem_post() to release it.

What are the four needed conditions for a deadlock?

- Mutual exclusion

- Hold-and-wait

- No preemption

- Circular wait

What is the definition of mutual exclusion?

Theads claim exclusive control of resources

What is the definition of hold-and-wait?

Theads hold resources allocated to them while waiting for additional resources

What is the definition of preemption?

Resources cannot be forcibly removed from threads that are holding them

What is the definition of circular wait?

There exists a circular chain of threads such that each holds one or more resources that are being requested by the next thread in the chain

How can semaphores be used to throttle a thread pool?

Set the initial value of the semaphore to the max threads that should be able to work at the same time.

What is special about the integer value of a semaphore that some operating systems like Linux use?

The integer can never be less than 0. It doesn't care how many threads are waiting, it only cares about not too many being active at the same time.