briantheprogrammer

Home of the O2 Programming Language

The Collegial Facility Problem In O2

Posted by Brian Andersen on May 12, 2012

Today’s problem tested my wits, my patience, and of course O2, my new programming language. I started with The Unisex Bathroom Problem as described in Allen Downey’s Little Book of Semaphores. He describes the problem as follows:

I wrote this problem when a friend of mine left her position teaching physics at Colby College and took a job at Xerox. She was working in a cubicle in the basement of a concrete monolith, and the nearest women’s bathroom was two floors up. She proposed to the Uberboss that they convert the men’s bathroom on her floor to a unisex bathroom, sort of like on Ally McBeal. The Uberboss agreed, provided that the following synchronization constraints can be maintained:

  • There cannot be men and women in the bathroom at the same time.
  • There should never be more than three employees squandering company time in the bathroom.

Of course the solution should avoid deadlock. For now, though, don’t worry about starvation. You may assume that the bathroom is equipped with all the semaphores you need.


Downey then provides two concise solutions to the problem using semaphores. The first one is highly concurrent but prone to starvation. It involves a LightSwitch; a higher level abstraction of a semaphore, on the outside of a Multiplex. The lightswitch controls whether men or women are allowed in the room at a given time. And the multiplex ensures that only three occupants are in the room concurrently. The problem is that while one sex is occupying the room, if the other sex is waiting outside they may be skipped over and over again by new arrivals of the same sex that is in the room. The second one is starvation free but suffers from reduced concurrency. Basically everyone goes in first-in-first-out order. There will only be multiple occupants in the bathroom if multiple men or women entered the line together. In the degenerate case, men and women alternate perfectly, and only one person can use the bathroom at a time. I could have implemented either of these solutions in O2. But I felt that since I am introducing a new language that aims to be good at solving concurrency problems I should have a solution that is highly concurrent and free of starvation. So I added the following constraints to my version of the problem. I call it the Collegial Facility.

  • If the room is occupied by men/women and a woman/man arrives at the door, she/he should step aside and let any man/woman that arrives go first, in order to maximize the throughput of the bathroom.
  • If there are one or more women/men waiting in this “skip line”, then they should only be skipped by at most three new arrivals.
  • Once they have been skipped the third time, all of the people that have been skipped get to go before any new arrival can access the bathroom.

The Code

My solution requires a separate “bathroom controller” fiber to coordinate entries and exits from the bathroom. In general I like to avoid using these kinds of helper threads, but sometimes they are necessary. In this case the bathroom fiber can suspend at the necessary times in a way that would not work for one of the person fibers if they were inside a mutually-exclusive take block. Also, many real systems like guis, transaction processing systems, etc… involve serial event processor loops so it is valuable to show how those can be implemented in O2.

{
  person:
  {
    me=$R
    mysex=$R part 0l

We shall start with the definition of the person fiber. The right argument is a symbol (tuple) consisting of the sex of the person; #man or #woman and an integer unique to that fiber.

    =sleep randoml 1 0 1000l

Randomize the attempts enter the bathroom.

    =(#door,entry + $me) write {i=++}
    =(#door,entry + $me) throttle 1l
    =(#skip + $me) throttle 1l

This is a new pattern you haven’t seen before. The throttle operator can be used to implement a kind of request response between fibers. The person writes a message under the symbol #door,entry and then uses throttle to wait until another fiber dispatches that same message from the blackboard. The room fiber will decide whether this person should enter the skip line. All that is necessary to make the person respect the skip line is to introduce the second throttle using the symbol #skip with $me appended.

    =(#room + $me) write {i=++}
    =(#ack + $me) write {i=++}
    =cwrite (string $me) + " entered the bathroom"

Once allowed through the entry and possibly removed from the skip line, the person enters the bathroom. After entering the room the person writes back on the symbol #ack. I will show you when I get to the room code why this is important. Once letting a person in, the room has to wait for the person to actually enter in order to avoid potential race conditions.

    =sleep randoml 1 0 1000l
    =cwrite (string $me) + " left the bathroom"
    =(#room + $me) dispatch 1l
    =(#door,exit + $me) write {i=++}

Person uses the bathroom for a random period of time, then exits by dispatching the line previously written. In addition to removing themselves from the room, the person writes an additional message explicitly indicating that they exited the room.

    <-person $R
  }

Repeat from the top. Now for the room code:

  room:
  {
    =#room throttle 3l

Each lap for the room fiber begins by waiting until the the room is not full. throttle handles this. Recall that the person fiber writes a message to the #room symbol in order to indicate that the person is in the room, and dispatches that same symbol upon leaving.

    next=#door gawk 1l

The gawk operator is yet another variation of dispatch, along with throttle and peek. gawk lets you actually look at the messages that dispatch would yield if you invoked it with the same arguments. The only difference is that gawk does not remove the message from the queue. In this way the room fiber can look at like a kind of lightweight server, inspecting messages and then deciding how to act upon them. Once done it will dispatch the message, indicating to the person fiber that it is ok to continue.

    <-($next.S part 1l) switch
    {
      entry=($R > 2l) switch
      {

In prior posts I have used the if operator to do conditional branches. I hate conditional logic. I prefer code that proceeds in a straight line, such as the person fiber above. But I can not always have my way. So I introduced switch which is a less ugly version of conditional branching. On the left argument it takes a single boolean or symbol value. In the case of a boolean it will execute the first or second branch on the right depending on whether the value is true or false. In the case of a symbol it chooses the branch to execute using its name in the block on the right. So in this case if the event message symbol is #entry then it chooses the branch otherwise it chooses the #exit branch as you shall see. In the entry block there is a nested conditional which checks to see if the right argument ($R) is greater than 2l. This is how the room controls the case where people have been skipped too many times.

        ={=#room throttle 1l =drain {} <-room 0l}

Wait until the room is empty. Then invoke the drain operator which will follow below. The drain operator lets everyone in the skip line use the restroom before continuing. Then reenter the room operator with the right argument, the skip count set to zero.

        =
        {
          othersex=($next.S part 2l) switch {man=#woman woman=#man}
          sexok=not (#room + $othersex) peek 1l
          =cwrite (string $next.S) + " at the entry " + ($sexok switch {="(ok)" ="(not ok)"})

Now begin the case where a person is at the entry and the people in the skip line have not been skipped too many times. Here the switch operator is used again to determine the symbol for the other sex. Then we calculate the $sexok flag which is false if there are members of the other sex in the room, according to the peek operator.

          skip=$sexok switch
          {
            =(#skip peek 1l) switch {=$R + 1l =0l}
            ={=(#skip + $next.S part 2 3l) write {i=++} <-$R}
          }

Another use of switch, you can see why I had to do something about the aesthetics of if before posting this example. The new skip count will be stored in the variable $skip. If $sexok is true, then check to see if someone is in the skip line and increment the skip count before returning. Otherwise we put the person into the skip line by writing a new message to the symbol #skip appended with the name of the fiber that is at the entry. In this case the skip count remains the same.

          =$next.S dispatch 1l
          =($sexok) switch {=#ack dispatch 1l}
          <-room $skip
        }
      }

After deciding whether the person is to enter the room or go into the skip line, we dispatch the symbol of the next message that was obtained from the gawk operator. This will cause the person fiber to advance to the next stage which will either be the skip line or they will actually enter the bathroom (finally!). If they entered the room then the room fiber should wait for the #ack which will only happen after the person has entered the room; that is written to the #room symbol. Another way to accomplish the same thing would be to read from the line given by result of $next.S dispatch 1l.

      exit=((not #room peek 1l) and #skip peek 1l) switch
      {
        ={=$next.S dispatch 1l =drain {} <-room 0l}
        ={=$next.S dispatch 1l <-room $R}
      }
    }
  }

This is the block of code that will evaluate if the room receives a #door,exit message. If the room is now empty and there are people in the skip line then all of the people in the skip line should get to go next. Otherwise just take it from the top.

  drain:
  {
    <-(#skip peek 1l) switch
    {
      =
      {
        =#skip dispatch 1l
        =#ack dispatch 1l
        =#room throttle 3l
        <-drain {}
      }
    }
  }

This is the drain routine as promised. It is recursive. It removes a person from the skip line, waiting for the #ack as they enter the room. Then it waits as long is it takes until there a seat free in the room and lets the next person in, until there is no one left in the room.

  test0:
  {
    b=fiber {<-#none room 0l}
    m0=fiber {<-person #man,0l}
    m1=fiber {<-person #man,1l}
    m2=fiber {<-person #man,2l}
    m3=fiber {<-person #man,3l}
    m4=fiber {<-person #man,4l}
    m5=fiber {<-person #man,5l}
    m6=fiber {<-person #man,6l}
    m7=fiber {<-person #man,7l}
    w8=fiber {<-person #man,8l}
    w0=fiber {<-person #woman,0l}
    w1=fiber {<-person #woman,1l}
    w2=fiber {<-person #woman,2l}
    w3=fiber {<-person #woman,3l}
    w4=fiber {<-person #woman,4l}
    w5=fiber {<-person #woman,5l}
    w6=fiber {<-person #woman,6l}
    w7=fiber {<-person #woman,7l}
    w8=fiber {<-person #woman,8l}
    <-wait $b
  }
  <-test0 {}
}

I configured this test with eight man and eight woman threads. I used a few extra configurations to test this program but I will omit them here in the name of brevity (For some definition of brevity anyway ;) . Here is the full text of the program. It is the most complex O2 example I have published yet.

{
  person:
  {
    me=$R
    mysex=$R part 0l
    othersex=$mysex switch {man=#woman woman=#man}
    =sleep randoml 1 0 1000l
    =(#door,entry + $me) write {i=++}
    =(#door,entry + $me) throttle 1l
    =(#skip + $me) throttle 1l
    =(#room + $me) write {i=++}
    =(#ack + $me) write {i=++}
    =cwrite (string $me) + " entered the bathroom"
    =sleep randoml 1 0 1000l
    =cwrite (string $me) + " left the bathroom"
    =(#room + $me) dispatch 1l
    =(#door,exit + $me) write {i=++}
    <-person $R
  }
  room:
  {
    =#room throttle 3l
    next=#door gawk 1l
    <-($next.S part 1l) switch
    {
      entry=($R > 2l) switch
      {
        ={=#room throttle 1l =drain {} <-room 0l}
        =
        {
          othersex=($next.S part 2l) switch {man=#woman woman=#man}
          sexok=not (#room + $othersex) peek 1l
          =cwrite (string $next.S) + " at the entry " + ($sexok switch {="(ok)" ="(not ok)"})
          skip=$sexok switch
          {
            =(#skip peek 1l) switch {=$R + 1l =0l}
            ={=(#skip + $next.S part 2 3l) write {i=++} <-$R}
          }
          =$next.S dispatch 1l
          =($sexok) switch {=#ack dispatch 1l}
          <-room $skip
        }
      }
      exit=((not #room peek 1l) and #skip peek 1l) switch
      {
        ={=$next.S dispatch 1l =drain {} <-room 0l}
        ={=$next.S dispatch 1l <-room $R}
      }
    }
  }
  drain:
  {
    <-(#skip peek 1l) switch
    {
      =
      {
        =#skip dispatch 1l
        =#ack dispatch 1l
        =#room throttle 3l
        <-drain {}
      }
    }
  }
  test0:
  {
    b=fiber {<-#none room 0l}
    m0=fiber {<-person #man,0l}
    m1=fiber {<-person #man,1l}
    m2=fiber {<-person #man,2l}
    m3=fiber {<-person #man,3l}
    m4=fiber {<-person #man,4l}
    m5=fiber {<-person #man,5l}
    m6=fiber {<-person #man,6l}
    m7=fiber {<-person #man,7l}
    w8=fiber {<-person #man,8l}
    w0=fiber {<-person #woman,0l}
    w1=fiber {<-person #woman,1l}
    w2=fiber {<-person #woman,2l}
    w3=fiber {<-person #woman,3l}
    w4=fiber {<-person #woman,4l}
    w5=fiber {<-person #woman,5l}
    w6=fiber {<-person #woman,6l}
    w7=fiber {<-person #woman,7l}
    w8=fiber {<-person #woman,8l}
    <-wait $b
  }
  <-test0 {}
}

The Output

Welcome to O2, ask brian if you need help
O2>eval fload "../../src/facility.o2"
#door,entry,man,4l at the entry (ok)
#man,4l entered the bathroom
#door,entry,man,7l at the entry (ok)
#man,7l entered the bathroom
#door,entry,woman,1l at the entry (not ok)
#door,entry,man,2l at the entry (ok)
#man,2l entered the bathroom
#man,7l left the bathroom
#door,entry,woman,0l at the entry (not ok)
#door,entry,man,8l at the entry (ok)
#man,8l entered the bathroom
#man,2l left the bathroom
#door,entry,man,5l at the entry (ok)
#man,5l entered the bathroom
#man,4l left the bathroom
#man,8l left the bathroom
#man,5l left the bathroom
#woman,1l entered the bathroom
#woman,0l entered the bathroom
#door,entry,man,3l at the entry (not ok)
#door,entry,man,6l at the entry (not ok)
#door,entry,woman,3l at the entry (ok)
#woman,3l entered the bathroom
#woman,0l left the bathroom
#door,entry,woman,7l at the entry (ok)
#woman,7l entered the bathroom
#woman,7l left the bathroom
#door,entry,woman,8l at the entry (ok)
#woman,8l entered the bathroom
#woman,3l left the bathroom
#woman,8l left the bathroom
#woman,1l left the bathroom
#man,3l entered the bathroom
#man,6l entered the bathroom
#door,entry,man,4l at the entry (ok)
#man,4l entered the bathroom
#man,6l left the bathroom
#door,entry,woman,4l at the entry (not ok)
#door,entry,woman,2l at the entry (not ok)
#door,entry,man,0l at the entry (ok)
#man,0l entered the bathroom
#man,3l left the bathroom
#door,entry,woman,6l at the entry (not ok)
#door,entry,woman,5l at the entry (not ok)
#door,entry,man,1l at the entry (ok)
#man,1l entered the bathroom
#man,1l left the bathroom
#door,entry,man,2l at the entry (ok)
#man,2l entered the bathroom
#man,4l left the bathroom
#man,0l left the bathroom
#man,2l left the bathroom
#woman,4l entered the bathroom
#woman,2l entered the bathroom
#woman,6l entered the bathroom
#woman,2l left the bathroom
#woman,5l entered the bathroom
#woman,6l left the bathroom
#door,entry,man,7l at the entry (not ok)
#door,entry,man,8l at the entry (not ok)
#door,entry,woman,7l at the entry (ok)
#woman,7l entered the bathroom
#woman,4l left the bathroom
#door,entry,woman,0l at the entry (ok)
#woman,0l entered the bathroom
#woman,5l left the bathroom
#door,entry,man,5l at the entry (not ok)
#door,entry,woman,3l at the entry (ok)
#woman,3l entered the bathroom
#woman,7l left the bathroom
#woman,3l left the bathroom
#woman,0l left the bathroom
#man,7l entered the bathroom
#man,8l entered the bathroom
#man,5l entered the bathroom
#man,5l left the bathroom
#door,entry,woman,1l at the entry (not ok)
#door,entry,man,6l at the entry (ok)
#man,6l entered the bathroom
#man,8l left the bathroom
#door,entry,woman,8l at the entry (not ok)
#door,entry,man,4l at the entry (ok)
#man,4l entered the bathroom

I won't break this down line by line but if you do you can see that the bathroom remains highly concurrent while avoiding starvation and obeying the constraints set out in the original problem.

Discussion

When I first added the throttle and peek operators into O2 I thought that they would not be used much in practice. But now that I have them I find myself using them all over. I don't believe I could have solved this problem at all without them. Also, I think that a number of my earlier posts could have been written more elegantly with the benefit of these operators. In this post I introduced yet another operator in the same family; gawk. gawk lets you actually look at the data that would be dispatched without actually experiencing the side effect of dispatch. I think that this operator is going to come in handy in my upcoming series on distributed computing in O2. But who knows? I don't really know what pieces I need until I start trying to build stuff with them. The new switch operator is another example. I think I am going to be able to get rid of ugly old if entirely. It is pretty exciting to feel the language getting better and stronger through repeated use and practice, which is the whole purpose of this blog.

Leave a Comment

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>