Skip to main content

Operating Systems course guide To follow along with "Three Easy Pieces"

Haris Skiadas

Section 4.5 Semaphores

This section covers book chapter 31, on the topic of semaphores. This whole section is not easy and will require multiple readings and drawing figures.
🔗
Start by reading the introduction and section 31.1.
🔗

Practice 4.5.1.

Which of the following are correct statements about semaphores?
🔗
  • Semaphores need to be given an initial value, which determines their behavior.
  • sem_wait always decrements the value, even when it is negative to begin with.
  • sem_post only increments the value if there are threads waiting.
  • If the value of the semaphore is initially non-negative, then the current value of the semaphore can tell us if there are any threads waiting and also how many.
  • Critical sections are placed between a sem_wait call and a sem_post call.
  • We can implement semaphores using locks and condition variables.
  • We can implement locks and condition variables using semaphores.
🔗
Read section 31.2, about using a semaphore as a lock.
🔗

Practice 4.5.2.

🔗

Practice 4.5.3.

Figure 31.5 describes a case where only two threads compete for the semaphore/lock. Draw a similar table for a case with 3 threads.
🔗
🔗
Read section 31.3 for the use of a semaphore as an ordering primitive, similar to the use of condition variables.
🔗

Practice 4.5.4.

When using the semaphore as an ordering primitive, to make sure a parent waits for a child to complete:
🔗
  • The initial value must be set to 0.
  • The parent must call sem_wait.
  • The child must call sem_post at the start of its code.
🔗

Practice 4.5.5.

After reading the tip section titled SETTING THE VALUE OF A SEMAPHORE answer the following: If we wanted have the parent spawn two child processes and wait for both of them to finish, with as similar a setup as for the one-thread case and by adding another call to pthread_create, what should we do?
🔗
  • Set the initial value of the semaphore to -1, and change nothing else.
  • Keep the value of the semaphore at 0, but call sem_wait twice.
  • Set the value of the semaphore to -1 and call sem_wait twice.
  • Change nothing else
🔗
Read section 31.4, about the producer/consumer problem via semaphores. I strongly encourage you to pause and think about it when the book asks you to, rather than reading ahead immediately.
🔗
Make sure to understand in particular how we can arise at a deadlock situation if we add the mutex lock at the wrong place. The lesson here is to reduce the scope of the mutex lock to the absolute minimum.
🔗
Read section 31.5 about a different kind of locking mechanism, the reader-writer locks, which allow situations where many readers can run concurrently as long as there is no writer updating things at the same time.
🔗

Practice 4.5.6.

In the reader-writer lock example described in the book:
🔗
  • Every reader waits on both the lock and the writelock.
  • A reader only waits on the writelock if there are no other readers.
  • If a writer is currently writing and thus holding the writelock, the first reader will wait on the writelock but subsequent readers will wait on lock instead.
  • A deadlock might occur if we have multiple writers and multiple readers.
  • There is a risk of starvation of the writers where the much more frequent readers keep holding the writelock and not letting the writers run.
🔗
Read section 31.6 about the dining philosophers problem and its solution. Make sure you understand why the solution works. Can you think of other possible solutions?
🔗
Read section 31.7 about the idea of using a semaphore to control how many threads can run something at a given time.
🔗

Practice 4.5.7.

🔗
Read section 31.8, for one way to implement semaphores using locks and condition variables.
🔗
Read the summary on section 31.9.
🔗
🔗
PrevTopNext