After that short intermission in reactive programming, it’s back to the little Go book of semaphores series with “the Modus Hall problem”. I didn’t understand the reference in the footnote and after some googling, it turns out that “Modus Hall” is the nickname given to a set of temporary student residence buildings at the Olin College of Engineering where the author of the problem, Nathan Karst, was a student.
The problem reads as follows:
After a particularly heavy snowfall this winter, the denizens of Modus Hall created a trench-like path between their cardboard shantytown and the rest of campus. Every day some of the residents walk to and from class, food and civilization via the path; we will ignore the indolent students who chose daily to drive to Tier 3. We will also ignore the direction in which pedestrians are traveling. For some unknown reason, students living in West Hall would occasionally find it necessary to venture to the Mods.
Unfortunately, the path is not wide enough to allow two people to walk side-by-side. If two Mods persons meet at some point on the path, one will gladly step aside into the neck high drift to accommodate the other. A similar situation will occur if two ResHall inhabitants cross paths. If a Mods heathen and a ResHall prude meet, however, a violent skirmish will ensue with the victors determined solely by strength of numbers; that is, the faction with the larger population will force the other to wait.
To put it mildly, I find this problem annoying. Its description implies not only contention for a resource (the path) but also timing (the students from the different fractions must meet somewhere along the road). For this to make sense, the students must enter the path in groups. You could argue that if one Mod encounters a ResHall, there could be another Mod somewhere along the road and he’ll notice the situation rush to help the other. Bullies… sigh …
The approach the author has taken to make the problem statement more meaningful is to say that if a Mod and a ResHall meet they won’t budge and they will wait for other students of their fraction to show up and take control of the path. While they have control, students from their fraction can pass through.
Unless I’m misunderstanding something in the problem statement, there’s an obvious issue with this: if a Mod uses the path without a ResHall present, he can cross; if a ResHall uses the path without a ResHall present, he can cross; if a Mod is crossing and a ResHall arrives, they both get locked in the path until another Mod starts crossing, in which case one of the Mods crosses and the other stays in the path locked with the ResHall. There’s no way for the count to go below one now, and this can only get worse over time. In order to prevent this, if there’s a Mod in the path, it’s necessary to prevent a ResHall from entering it. This allows the Mod to always exit the path, but also prevents the exact situation described in the problem statement where a Mod and ResHall can be in the path at the same time.
With that big caveat out of the way, this solution tries to stay true to what I understand is the problem’s intention.
Starting with the contended resource, the path, it can be represented as follows:
type Path struct {
in chan interface{}
out chan interface{}
mods []*Mod
reshalls []*ResHall
}The two channels in and out serve as the entry and exit points to
the path. The path can be occupied by any number of Mods and ResHalls,
so a buffered channel won’t do, and that’s the purpose of the mods and
reshalls fields.
When the path is setup, the program invokes its Run method:
func (p *Path) Run() {
var (
mods chan interface{}
reshalls chan interface{}
mod *Mod
reshall *ResHall
)the mods and reshalls variables hold the out channel in case the
Mods can use it or the ResHalls can use it. The mod and reshall
variables hold a single instance of the respective type, and it’s more
an implementation detail than anything else.
Next, the Path will enter an usual for-select loop. The intention behind
it is to either accept new students to the path or the send them out as
soon as possible, without giving preference to any operation. This
explains the existence of the mods and reshalls variables: if the
Mods are allowed to move, the mods channel will not be nil and the
reshalls variable will; if the ResHalls are allowed to move, the
opposite will be true:
for {
select {
case s := <-p.in:
// ...
case mods <- mod:
// ...
case reshalls <- reshall:
// ...
}
}
}When a student enters the Path, it will be necessary to determine what
kind of student he is to put it in the correct queue. If it happens that
the new student changes the balance of power, then the corresponding out
variable (mods or reshalls) will get the out channel:
case s := <-p.in:
switch s.(type) {
case *Mod:
s := s.(*Mod)
p.mods = append(p.mods, s)
if len(p.mods) > len(p.reshalls) {
mod = p.mods[0]
mods, reshalls = p.out, nil
}
case *ResHall:
s := s.(*ResHall)
p.reshalls = append(p.reshalls, s)
if len(p.reshalls) > len(p.mods) {
reshall = p.reshalls[0]
mods, reshalls = nil, p.out
}
}When it’s possible for the Mods or ResHalls to exit the Path, they will do so by sending the first student to have entered the Path over the out channel. A new check is made to decide who remains in control:
case mods <- mod:
p.mods = p.mods[1:]
if len(p.mods) <= len(p.reshalls) {
mods = nil
}
case reshalls <- reshall:
p.reshalls = p.reshalls[1:]
if len(p.reshalls) <= len(p.mods) {
reshalls = nil
}
}
}
}and this is the heart of it: allow students in, decide who is in control, allow that category to use the path until the balance of power changes.
The full source (with minor modifications for presentation) is here. If you examine the implementation you’ll see that the situation I described above, where the Path is occupied by increasing numbers of students happens fairly quickly. Again, unless I’m missing something, I believe this is a consequence of the problem’s statement.
Next week five Gophers enter a sushi bar and …