FrançaisGet started

Semaphores and monitors

The semaphore (counter and waiting queue), its P and V operations, its four uses, then the monitor: a lock and condition variables, wait, signal, broadcast and the loop around wait.

  • 26 cards
  • 5 topics
  • Free
Study this deck

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

  1. Concepts
  2. Questions
  3. Sort and link
  4. Scenarios
  5. Understand

A few cards from the deck

  • Semaphore: what is it?

    Show the answer

    An integer counter that never goes below 0, tied to a queue of sleeping threads; it is only handled through two atomic operations.

    Its initial value decides its role: 1 for exclusion, N for a limit, 0 for waiting on a signal.

  • Semaphore s starts at 0. What does this program print, whatever order the threads are started in?

    ```c
    /* thread 1 */ /* thread 2 */
    sem_wait(&s); printf("A");
    printf("B"); sem_post(&s);
    `

    • AB
    • BA
    • AB or BA depending on the scheduler
    • Nothing: both threads block
    Show the answer

    AB

    Thread 1 only gets past sem_wait after thread 2's sem_post, which comes after printing A. If thread 2 goes first, the token is kept: the semaphore is 1 and sem_wait will pass without waiting.

  • Initialised to …, a semaphore serves as mutual exclusion; initialised to …, it makes a thread wait until another signals.

    Show the answer

    Initialised to 1, a semaphore serves as mutual exclusion; initialised to 0, it makes a thread wait until another signals.

    At 1, the first P passes and the following ones wait for the V. At 0, every P waits, until the first V from another thread.

  • P operation (sem_wait): what is it?

    Show the answer

    Takes a token: decrements the counter if it is positive, otherwise puts the calling thread to sleep until a token is given back.

    P on a semaphore at 0 blocks: it is the only case where P waits. In POSIX, it is sem_wait.

  • A server must never open more than ten simultaneous connections to the database, however many threads there are. Which tool, with which initial value?

    • A mutex, with ten threads sharing the lock in turn
    • A semaphore initialised to 0, with V before each connection and P after
    • A semaphore initialised to 1 for each thread, taken before connecting
    • A semaphore initialised to 10, with P before connecting and V after
    Show the answer

    A semaphore initialised to 10, with P before connecting and V after

    A mutex admits one thread at a time; a semaphore at N admits N. Initialised to 0, nobody would ever get past the first P.

Study this deck