Process synchronization interview questions, with answers

The questions, with answers

1. 1.What is a race condition?

   In short: A bug where the result depends on the timing of threads or processes accessing shared data without coordination.

   A race condition occurs when two or more threads access shared data concurrently, at least one of them writes, and nothing orders their accesses, so the outcome depends on how the scheduler happens to interleave them. The program may work in testing and fail in production, because the harmful interleaving is rare. The cure is to identify the code that touches the shared data, the critical section, and make sure only one thread executes it at a time, using a lock, a semaphore or an atomic operation, or to avoid sharing the data at all.

2. 2.What is the critical-section problem, and what must a solution guarantee?

   In short: Designing entry and exit code so that shared data is used safely, with mutual exclusion, progress and bounded waiting.

   A critical section is the part of a program that accesses shared resources. A correct solution must guarantee three things. Mutual exclusion: at most one process is in its critical section at a time. Progress: if no process is inside and some want to enter, the choice of who enters next cannot be postponed indefinitely. Bounded waiting: a process that has asked to enter will get in after a bounded number of other entries, so it cannot starve. Peterson's algorithm solves it for two processes in software; real systems use hardware instructions such as test-and-set or compare-and-swap.

3. 3.What is the difference between a mutex and a semaphore?

   In short: A mutex is a lock owned by the thread that acquired it; a semaphore is a counter any thread may signal, used for counting and signalling.

   A mutex provides mutual exclusion: a thread locks it before the critical section and the same thread unlocks it afterwards, so it has an owner, which lets systems check that only the owner releases it and detect a thread relocking a lock it already holds. A semaphore is an integer counter with wait and signal operations and no owner: any thread can signal it. A binary semaphore can act like a lock, but semaphores are mainly used for counting identical resources, such as buffer slots, and for signalling between threads, for example one thread signalling that data is ready for another.

4. 4.How do the wait() and signal() operations on a semaphore work?

   In short: wait() decrements the semaphore and blocks the caller if no unit is available; signal() increments it and wakes a waiting process.

   wait(), also called P or down, decrements the semaphore's value; if the result shows no unit available, the calling process is put on the semaphore's waiting queue and blocked. signal(), also called V or up, increments the value and, if processes are waiting, wakes one of them. Both operations must be atomic, which the operating system guarantees. A binary semaphore takes only the values 0 and 1; a counting semaphore starts at the number of available units, such as the number of free slots in a buffer, and lets that many processes proceed.

5. 5.How is the producer-consumer problem solved with semaphores?

   In short: Use a counting semaphore for empty slots, one for full slots and a mutex for the buffer itself.

   Producers put items into a bounded buffer and consumers remove them; producers must wait when it is full and consumers when it is empty. The classic solution uses three semaphores: empty, starting at the buffer size, full, starting at 0, and a mutex protecting the buffer. A producer calls wait(empty), then locks the mutex, inserts, unlocks, and calls signal(full); a consumer does wait(full), lock, remove, unlock, signal(empty). The order matters: taking the mutex before waiting on empty or full can deadlock, because a blocked producer would hold the lock the consumer needs.

6. 6.What is a spinlock, and when is busy waiting acceptable?

   In short: A lock that waits by looping on an atomic test instead of sleeping; worth it only when locks are held very briefly on multicore systems.

   A spinlock makes a waiting thread repeatedly test the lock with an atomic instruction until it becomes free, instead of blocking and being rescheduled. Busy waiting wastes CPU cycles, but it avoids the cost of two context switches, so it pays off when the lock is held for a very short time and the holder is running on another core. Kernels use spinlocks for short critical sections, especially where sleeping is not allowed, such as in interrupt handlers. On a single core, spinning is pointless, because the holder cannot run while the waiter spins.

7. 7.What is the dining philosophers problem?

   In short: Five philosophers share five forks and each needs two to eat, illustrating deadlock and starvation among competing processes.

   Five philosophers sit at a round table with one fork between each pair; each needs both neighbouring forks to eat. If every philosopher picks up the left fork at the same moment, each waits forever for the right one: a deadlock, with a circular wait. Solutions break one of the deadlock conditions: let at most four philosophers try to eat at once, make one philosopher pick up the right fork first so the forks are acquired in a global order, or have a philosopher take both forks only when both are free, as a monitor-based solution does. It models any set of processes competing for several shared resources.

How the diagnostic asks it

One question from the Operating Systems bank, exactly as a sitting would show it. The bank has 4 on process synchronization and 30 across Operating Systems.