A CSP Equivalence Demonstration
What if I love semaphores, but all I've got is CSP? Am I out of luck?
Actually, no. And it's pretty neat to show that we can implement one scheme for synchronization using the other. It's a good way to demonstrate that the two models are equivalent in power.
A Classic Semaphores Problem
Suppose we have a “party room” that can hold at most five people (it's a small party!), and we have ten people who want to enter the room. We want to ensure that no more than five people are in the room at any time.
This is a classic problem where a semaphore is useful. We can use a semaphore to control access to the room. The semaphore is initialized to 5, and each person who wants to enter the room must acquire the semaphore. If the semaphore is 0, the person must wait until someone leaves the room and signals the semaphore.
We want to replicate this behavior using CSP.
Designing a Semaphore Equivalent in CSP
There are three ways we can solve this problem.
1. Use a Channel that Blocks when Full
If we create a channel with a buffer of size five, that can be the analogue for our party.
- When someone enters the room, we send to the channel.
- If the channel is full, the sender will block until someone leaves the room. When someone leaves the room, we receive from the channel.
In Go, the fundamental code would look like
type Semaphore chan struct{}
func NewSemaphore(capacity int) Semaphore {
return make(Semaphore, capacity)
}
func (s Semaphore) Acquire() {
s <- struct{}{}
}
func (s Semaphore) Release() {
<-s
}
Remember, you can fork the code and try different things! For example, you could add more print statements to see what's happening, or try changing some of the values.
Hay! What's the deal with
struct{}{}?-
It's a way to signal without sending any data. It creates an empty struct, which takes up no space in memory. It's a common idiom in Go for signaling.
-
I don't like this one. If we decided we wanted to expand the room to hold more people, we'd be stuck! We have to decide on the room capacity at the start and then can't change it. That's not very flexible.
-
True. Let's see if we can improve on that while still keeping it simple.
2. Use a Channel that Blocks when Empty
We can also create a channel with a size that is five (or more). This time, we can imagine our channel is full of tickets to get into the room. Initially, we fill the channel with five tickets.
- When someone enters the room, they take a ticket from the channel. If there are no tickets left, they must wait until someone leaves the room and puts a ticket back in the channel.
- When someone leaves the room, they put a ticket back in the channel.
In Go, the fundamental code would look like
type Semaphore chan struct{}
func NewSemaphore(capacity int) Semaphore {
channel := make(Semaphore, capacity)
for i := 0; i < capacity; i++ {
channel <- struct{}{}
}
return channel
}
func (s Semaphore) Acquire() {
<-s
}
func (s Semaphore) Release() {
s <- struct{}{}
}
(Note that in this version, we expand the party room's capacity during the party, something we couldn't do in the previous version.)
-
This is a bit better. We get to decide how many tickets to issue and can issue more later.
But there's still a problem that we have a fixed maximum number of unused tickets. If we issued lots of extra tickets, we'd let all those people in, but when they left, they'd try to return their tickets and hit the maximum buffer capacity and block.
-
That's a good point.
3. Use an Arbitrator Process
We can create a more general solution by having an arbitrator process that manages the semaphore value and the people who want to enter the room.
In this design, we have two (unbuffered) channels to talk to the arbitrator:
- One channel is for people who want to enter the room. The arbitrator only listens to this channel when there is space available in the room.
- One for people who want to leave the room. The arbitrator always listens to this channel, even when it is also listening to the other channel.
In Go, the fundamental code would look like
func NewSemaphore(initialCapacity int) *Semaphore {
s := &Semaphore{
acquire: make(chan struct{}),
release: make(chan struct{}),
}
go s.arbitrator(initialCapacity)
return s
}
func (s *Semaphore) arbitrator(initialCapacity int) {
capacity := initialCapacity
for {
if capacity > 0 {
// Listen for both acquire and release
select {
case s.acquire <- struct{}{}:
capacity--
case <-s.release:
capacity++
}
} else {
// Only listen for release; aquires will block
<-s.release
capacity++
}
}
}
func (s *Semaphore) Acquire() {
<-s.acquire
}
func (s *Semaphore) Release() {
s.release <- struct{}{}
}
Meh. I thought everyone hated semaphores because they were so complicated.
-
True, but the point is that we can implement semaphores using CSP. It's a good way to show that the two models are equivalent in power. And it's a good way to show that CSP can be used to implement other synchronization primitives.
Our final strategy—using a separate arbitrator process—is the most general and could be used to implement almost any synchronization primitive. It's a good way to show that CSP is a powerful model for synchronization.
Takeaways
- One synchronization model can be used to implement another synchronization model.
- We could also have gone in the other direction, and shown how to implement CSP using semaphores (or locks and condition variables).
- In CSP, we can always fall back to a coordinator process to manage the synchronization.
(When logged in, completion status appears here.)