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$ Why is this downvoted? $\endgroup$ – Dhruv Ghulati May 8 '16 at 17:25

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:

  1. The original Peterson’s Algorithm works with only 2 processes.
  2. The Peterson's algorithm requires multi-writer registers while the Bakery algorithm uses only single-writer registers.
  3. Both algorithms are starvation-free. Furthermore, the Bakery algorithm offers a strong near-FIFO guarantee.
  4. Both algorithms work with atomic registers. However, the Bakery algorithm works with even weaker registers (safe registers actually, see here).
  5. 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).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.