The author of “The Little Book of Semaphores” wrote this week’s problem inspired by real life events at Colby College. The problem’s statement is the following:

The following synchronization constraints apply to students and the Dean of Students:

  1. Any number of students can be in a room at the same time.

  2. The Dean of Students can only enter a room if there are no students in the room (to conduct a search) or if there are more than 50 students in the room (to break up the party).

  3. While the Dean of Students is in the room, no additional students may enter, but students may leave.

  4. The Dean of Students may not leave the room until all students have left.

  5. There is only one Dean of Students, so you do not have to enforce exclusion among multiple deans.

Puzzle: write synchronization code for students and for the Dean of Students that enforces all of these constraints.

This problem is very similar to the previous one (the childcare center problem) in the sense that it’s about limiting access to a critical section to a particular thread only if thread of specific types are already present or not present.

A student can be represented by a goroutine like this:

go func() {
	s := Student{Name: fmt.Sprintf("Student %d", i)}
	r.sIn <- s
	// ...
	r.sOut <- s
}()

When the goroutine is sending to the sIn channel, the student is entering the room. After the send finishes, the student is in the room. When it’s sending to the sOut channel, it’s signaling that it wants to leave the room, and after the send finishes, the student has left the room.

The controlling logic is actually in the room itself:

func (r *Room) Run(timeout <-chan time.Time) {
	var (
		n    int
		dIn  = r.dIn
		dOut = r.dOut
		sIn  = r.sIn
	)

The variables dIn, dOut and sIn are used to control receiving from those channels. When there are no students present, dIn is not nil to allow the dean to enter the room and conduct a search. During the search, sIn is nil to prevent students from entering. If the dean leaves, sIn is not nil to allow students to enter the room and dIn is set to nil to prevent the dean from entering. If enough students enter the room, dIn is set to a non-nil value to allow the dean to enter to break up the party. While students are leaving, sIn is nil and dOut is also nil to prevent the dean from leaving too early.

This is expressed in a for-select loop:

	for {
		select {
		case <-dIn:
			// Dean entered, students cannot enter
			sIn = nil

		case <-dOut:
			// Dean left, students can enter
			sIn = r.sIn

		case s := <-sIn:
			n++

		case s := <-r.sOut:
			n--

		case <-timeout:
			return
		}

In order to make sure that all the conditions are met at all times, the check is performed after the select, like this:

		switch {
		case n == 0:
			// Dean can enter or leave
			dIn = r.dIn
			dOut = r.dOut
		case n > r.Cap:
			// Dean can enter
			dIn = r.dIn
			dOut = nil
		default:
			// Dean cannot enter
			dIn = nil
			dOut = nil
		}
	}
}

Conceptually, this solution is the same as the one for the previous problem. It’s interesting to note that this is not true for the semaphore-based solution in the book. The key thing to note in this and prior solutions is that I have introduced “additional” threads to represent the contended resource in one way or another. For example, in this problem the room is a goroutine that does the bookkeeping. It’s this “extra” goroutine that simplifies the solution. Instead of having the dean and the students communicate by sharing memory, they share memory by communicating.

The full source (with minor modifications for presentation) is here.

The next problem in the book deals with boarding a bus.