Semaphores

What have we learned so far?

• Both lock and condition variables are needed to solve more complex concurrency problems.
• Can we do better?

Edsger Dijkstra

• Dijkstra, Edsger W. “The structure of the “THE” multiprogramming system.” In The origin of concurrent programming, pp. 139-152. Springer, New York, NY, 1968.
• Dijkstra, Edsger W. “Information streams sharing a finite buffer.” In Inf. Proc. Letters, vol. 1, pp. 179-180. 1972.
• Together with colleagues, developed semaphore as a single primitive for all things related to synchronization.

Semaphore

• Is an object with an integer value that can be manipulated with two routines:
  • sem_wait()
  • sem_post()
  • They are atomic operations
• Needs to be initialized to some value.
  • sem_init()

1
2
3
4
5
 
int sem_wait(sem_t *s) {
    // try to decrement the value of semaphore s by one
    // if s is greater than zero, derement proceeds and return
    // else blocks (sleep) until it can decrement (s > 0) or interrupted via signal
}
 

1
2
3
4
5
6
7
 
int sem_post(sem_t *sem){
    // increments (unlocks) the semaphore pointed to by sem.
    // If the semaphore's value consequently becomes greater than zero,
    // then another process or thread blocked in a sem_wait call will
    // be woken up and proceed to lock the semaphore.
    // else, the value of the semaphore is left unchanged. 
}
 

Semaphore as lock (binary semaphore)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
sem_t m;
sem_init (&m, 0, X); // initilize semaphore to X. What should X be?

sem_wait(&m);
    // critical section here
sem_post(&m);

<details class="details details--default" data-variant="default"><summary>Code tracing</summary>
<figure>
  <picture>
    <!-- Auto scaling with imagemagick -->
    <!--
      See https://www.debugbear.com/blog/responsive-images#w-descriptors-and-the-sizes-attribute and
      https://developer.mozilla.org/en-US/docs/Learn/HTML/Multimedia_and_embedding/Responsive_images for info on defining 'sizes' for responsive images
    -->
    
      
        <source class="responsive-img-srcset" srcset="/assets/img/courses/csc331/semaphores/03-480.webp 480w,/assets/img/courses/csc331/semaphores/03-800.webp 800w,/assets/img/courses/csc331/semaphores/03-1400.webp 1400w," type="image/webp" sizes="95vw" />
      
    
    <img src="/assets/img/courses/csc331/semaphores/03.png" width="50%" height="auto" data-zoomable="" loading="lazy" onerror="this.onerror=null; $('.responsive-img-srcset').remove();" />
  </picture>

  
</figure>

</details>
---

## Semaphore as condition variable

```c
sem_t s;

void *child(void *arg) {
    printf("child\n");
    sem_post(&s); //signal here: child is done
    return NULL;
}

int main(int argc, char *argv[]) {
    sem_init(&s, 0, X); // initialize semaphore to X. What should X be?
    printf("parent: begin \n");
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL);
    sem_wait(&s); // wait here for hchild
    printf("parent: end\n");
    return 0;
}
 

Code tracking

Semaphore: producer/consumer I

• What is the risk if MAX > 1 and there are multiple producers/consumers?
  • Race condition: two producers produce at the same time or two consumers consume at the same time.
• What is currently missing from this implementation?
  • Mutual exclusion

Semaphore: producer/consumer II

• Mutual exclusion is added, incorrectly.
  • Consumer runs first, then wait on full (but still holding mutex).
  • Producer sees negative mutex, decreases it further, then goes to sleep.

Semaphore: producer/consumer III

• Mutual exclusion is added, correctly.
  • full and empty are for producers and consumers to wait on one another.
  • mutex for producers and consumers to wait among each group.

The dining philosophers

• It’s Dijkstra again.
  • There are five philosophers seating around a table.
  • Between each pair of philosophers there is a single fork (five forks total).
  • Philosophers alternate between thinking and eating (need fork).
  • Two forks are needed to eat (one to the left and one to the right).
  • How to schedule fork grabbing pattern so that no one starves?

Solutions

• Which one works?