What is the difference between a mutex and a semaphore?

A mutex is like the single key to a shared lab's server room. Whoever has the key goes in; everyone else waits outside. When they come out, they return the key and the next person can go in. Only the person holding the key can return it.

A semaphore is like a parking lot at a mall with a board showing "Spaces free: 3". Each car that enters lowers the number by one. When it reaches zero, new cars wait at the gate. When a car leaves, the number goes up and one waiting car can enter. Anyone leaving updates the board; there is no single owner.

A semaphore whose count can only be 0 or 1 is called a binary semaphore. It looks like a mutex, but it still has no idea of ownership.

A connection pool with only 3 database connections, shared by many request threads, written in C-like pseudocode:

semaphore pool = 3;     // 3 connections available
mutex log_lock;

void handle_request() {
    wait(pool);             // also called P() or down(); blocks if count is 0
    use_db_connection();
    signal(pool);           // also called V() or up(); count + 1, wake a waiter

    lock(log_lock);         // only one thread writes to the log file at a time
    write_log("done");
    unlock(log_lock);
}

Up to three threads use the database together. The log file is protected by a mutex because two threads writing at once would mix their lines.

Semaphores can also be used for signalling between threads, which a mutex cannot do properly:

semaphore data_ready = 0;

// producer thread           // consumer thread
prepare_data();              wait(data_ready);   // sleeps until producer signals
signal(data_ready);          use_data();

A semaphore has an integer value and a queue of waiting threads. wait() decrements the value; if it would go below zero, the thread is put to sleep. signal() increments the value and wakes one waiting thread. The OS makes both operations atomic, so two threads can never update the counter at the same time.

A mutex has two states, locked and unlocked, plus an owner. Because the system knows the owner, it can offer extra protections: an error if another thread tries to unlock it, recursive locking in some implementations, and priority inheritance, where a low-priority thread holding the lock is temporarily boosted so a high-priority thread waiting for it is not stuck.

• Mutex: protecting a shared counter, a cache, a linked list or a log file.
• Counting semaphore: limiting concurrent connections, a pool of printers, or the number of parallel downloads.
• Semaphores: the classic producer-consumer problem with a bounded buffer uses two counting semaphores (empty slots, filled slots) plus a mutex.

• Saying "a binary semaphore is the same as a mutex". They behave alike for locking, but a mutex has ownership and a semaphore does not.
• Forgetting to unlock on an error path, which leaves every other thread blocked forever. Languages offer helpers like std::lock_guard in C++ or synchronized and try-finally in Java for this.
• Calling signal() more times than wait(), silently raising the count above its limit.

• Solve the producer-consumer problem using semaphores.
• What is priority inversion, and how does priority inheritance fix it?
• What is a spinlock, and when is it better than a mutex?
• What is the difference between a semaphore and a condition variable?