From my CS course, the Peterson's Algorithm and the Bakery Algorithm both are solutions which satisfy the 3 requirements of any solution to the critical section problem. a) What are their adv/disadv over each other , and b) if they already solve the critical section problem, why do we need semaphores?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
a) what are the advantages/disadvantages over each other?
According to the lecture note: Sections 17.4.1 and 17.4.3, we can summarize as follows:
- The original Peterson’s Algorithm works with only 2 processes.
- The Peterson's algorithm requires multi-writer registers while the Bakery algorithm uses only single-writer registers.
- Both algorithms are starvation-free. Furthermore, the Bakery algorithm offers a strong near-FIFO guarantee.
- Both algorithms work with atomic registers. However, the Bakery algorithm works with even weaker registers (safe registers actually, see here).
- The Bakery algorithm uses unbounded registers. Nevertheless, this problem can be fixed.
b) If they already solve the critical section problem, why do we need semaphores?
A Semaphore is a generalization of mutual exclusion locks. Each Semaphore has a capacity, denoted by $c$ for brevity. Instead of allowing only one thread at a time into the critical section, a Semaphore allows at most $c$ threads, where the capacity $c$ is determined when the semaphore is initialized. (See the book "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit; Section 8.5).
$\begingroup$
$\endgroup$
They don't work for multiprocessors and modifying them to solve them is a hassle.
Whereas semaphores are simply mathematical methods to create process precedence graphs for concurrent execution.
Just an integer variable, that's it.
