The child care problem

Next problem in line in the the little Go book of semaphores series is about caring for children. It comes from the book “Operating Systems and Middleware: Supporting Controlled Interaction” by Max Hailperin (problem 4.6). It reads as follows:

State licensing rules require a child-care center to have no more than three infants present for each adult

To put it in a different way: there’s a room where both adults and children are found. For a children to enter the room, an adult must be already there. At that point up to two more children can enter. A fourth children has to wait for another adult to appear. Same goes when an adult wants to leave: if the number of adults present in the room is n, after one leaves it’s n-1 and therefore the number of children left in the room must be equal or less than 3*(n-1). While there are more children than that, the adult cannot leave.

If you have been reading the series, you already know where this is going: children enter using a channel cIn and adults use a channel aIn. A select switches between the actual cIn channel and nil according to the number of adults present. When they want to leave, they use a cOut and aOut channels. The select statement switches between the actual aOut channel and a nil channel to prevent adults from leaving when there are too many children.

In code:

	select {
	case <-c.aIn:
		nAdults++
	case <-aOut:
		nAdults--
	case <-cIn:
		nChildren++
	case <-c.cOut:
		nChildren--
	}

	if 3*nAdults > nChildren {
		// children can enter
		cIn = c.cIn
	} else {
		// don't let more children in
		cIn = nil
	}

	if 3*(nAdults-1) > nChildren {
		// adults can leave
		aOut = c.aOut
	} else {
		// don't let adults out
		aOut = nil
	}

There are two conditions here. The first one is that there must be enough adults already in the room for children to enter and the state licensing rules to be followed. The second one is that there must be enough adults in the room such that if one of them leaves, the remaining adults in the room are still enough to watch over the children according to the rules.

Adults and children are modelled as gorotines. Each goroutine uses the corresponding channel to “enter” the child care center and each uses the corresponding channel to exit it. For example, the adult goroutines look like this:

	go func() {
		a := Adult{Name: fmt.Sprintf("Adult %d", i)}
		c.aIn <- a
		time.Sleep(randMillisecond(5*N, 7*N))
		c.aOut <- a
	}()

This solution, which I believe solves the problem as stated, happens to be the solution to what the author calls the “extended child care problem”. For the extended version, consider the sitaution where there are 4 children and 2 adults in the center. Within the rules, the center can accept up to 6 children in this case. In the author’s solution to the basic problem, the leaving adult takes away two of the slots and blocks waiting for a child to leave. If another child arrives at the center in this situation, it will block trying to enter because the leaving adult already took away the two free slots it was providing. In the extended version, the arriving child does not block and the adult is now blocking waiting for two children to leave.

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

Next week, the dean gets to break up student parties.