How to Implement Semaphores in Multithreading

TL;DR

To implement semaphores for mutual exclusion and synchronization, use supervisor calls (SVC) in an uninterruptible OS kernel to handle WAIT and SIGNAL operations. Alternatively, a test-and-set instruction can be utilized for creating a simple lock semaphore. Fairness can be achieved by queuing waiting processes, ensuring proper order in semaphore access.

Transcript

Now let's figure out how to implement semaphores. They are themselves shared data and implementing the WAIT and SIGNAL operations will require read/modify/write sequences that must be executed as critical sections. Normally we'd use a lock semaphore to implement the mutual exclusion constraint for critical sections. But obviously we can't use semap... Read More

Key Insights

• 🚦 Semaphores implementation has a bootstrapping problem, as semaphores themselves cannot be used to implement the WAIT and SIGNAL operations.
• 🤙 Supervisor calls (SVC) in an uninterruptible OS kernel can be utilized to implement semaphores' functionality.
• 😫 A test-and-set instruction in the instruction set architecture (ISA) can help implement a simple lock semaphore.
• 🚦 Fairness is not automatically maintained in semaphore implementation, but it can be achieved by maintaining a queue of waiting processes.
• 😒 The provided assembly code demonstrates how to use the TEST-and-CLEAR instruction to implement a simple lock semaphore.
• 💂 The critical section execution can be guarded by the lock semaphore to prevent other processes from entering simultaneously.
• 🚦 The WAIT handler checks the semaphore's value and either decrements it or arranges for re-execution of the WAIT SVC.
• 💋 The SIGNAL handler increments the semaphore's value and marks WAITing processes as active using the WAKEUP call.

Questions & Answers

Q: What is the bootstrapping problem when implementing semaphores?

The bootstrapping problem refers to the challenge of using semaphores to implement semaphores. Since semaphores require critical sections, it becomes impossible to use semaphores themselves to implement mutual exclusion.

Q: How can supervisor calls (SVC) be used to implement semaphores?

In a timeshared processor with an uninterruptible OS kernel, the supervisor call mechanism can be employed to implement semaphores. The OS handlers for WAIT and SIGNAL SVCs can be executed as critical sections, ensuring the required functionality.

Q: What is the purpose of a test-and-set instruction in implementing semaphores?

A test-and-set instruction allows for atomic reading of a memory location and setting its value. By using this instruction, a simple lock semaphore can be implemented. If the returned value is zero, another process holds the lock. If the value is non-zero, the lock has been acquired.

Q: Can fairness be guaranteed in semaphore implementation?

Fairness is not guaranteed in the provided implementation. The round-robin scheduler selects a process in a specific order, prioritizing the next-in-sequence WAITing process. If fairness is desired, a queue of waiting processes can be maintained to ensure the next process in line gets the semaphore.

Summary & Key Takeaways

• Semaphores are shared data that require read/modify/write sequences to implement WAIT and SIGNAL operations as critical sections.

• The bootstrapping problem arises when trying to implement semaphores using semaphores. Supervisor calls (SVC) can be used in an uninterruptible OS kernel to implement required functionality.

• A test-and-set instruction can be added to the instruction set architecture (ISA) to implement a simple lock semaphore that can protect more complex semaphore semantics.