World's most popular travel blog for travel bloggers.

# [Answers] Peterson's vs. Bakery Algorithm

, ,
Problem Detail:

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?

###### Asked By : Dhruv Ghulati

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).