briantheprogrammer

Home of the O2 Programming Language

The Readers-Writers Problem In O2 (Part II)

Posted by Brian Andersen on April 7, 2012

In my previous post I solved the first variation of the Readers-Writers Problem. To recall, there are multiple reader fibers that can operate concurrently; at the same time. But there is a writer thread that must block all of the readers before it can proceed. Solving the basic version of this problem in O2 is quite easy because O2′s take operator allows you to acquire multiple locks in an atomic all-or-none fashion. However all is not yet well because this solution would expose your writer thread to the risk of starvation. If the reader threads are too aggressive, it is possible that the writer thread would never or rarely be able to gain all of the locks required in order to enter its critical section.

Good Night New York


In a database application this could mean that all the readers are getting data, but the data they are getting is stale because the writer could not update the database. So let’s assume you have an application where you want to serve incoming readers as quickly as possible. But you want any changes (from the writer) to be seen by readers as quickly as possible. The first thing you want to do is make sure readers should not wait for each other. We did that in Part I. The second thing you want to do is ensure that when the writer arrives, any waiting readers can finish with their work, but new readers will wait until the writer is done. In traditional solutions this is accomplished using shared counter variables and several semaphores to manage concurrency. The O2 solution will have the same effect but is, in my opinion, easier to understand and implement correctly. We will use the blackboard as a communication channel for the writer to tell the readers that they need to wait.

Good Morning Boulder

Solution to the Readers-Writers Problem

{
  writer:
  {
    =#wait write {hold=true}

We begin by defining an operator for the writer. The first thing the writer does is write to the blackboard under the symbol #wait. There is nothing magical about the symbol #wait, but it has to be agreed upon by the reader and the writer. The message written has a variable “hold” with the boolean value true. This is going to signal to the reader that the writer is present and that it should wait.

    =$R take
    {
      =cwrite "writer begins writing"
      =sleep randoml 1 0 1000l
      =cwrite "writer done writing"
      =#wait write {hold=false}
    }

In this case the right argument $R receives a vector containing multiple symbols, one for each reader. This vector becomes the left argument to the take operator, which suspends evaluation until the writer fiber can gain exclusive access to all of the symbols in $R. This means that it will wait for any readers that are already in progress. When the writer is done, it writes the value false to the hold variable under the symbol #wait. This signals waiting readers that they may now proceed, since the writer is done.

    =sleep randoml 1 0 1000l
    <-writer $R
  }

Let the writer sleep for a while and then continue by reentering. This is the end of the writer operator. A quick note about nomenclature. Operators are equivalent to functions or subroutines in other languages. I call them operators because they are allowed to receive two arguments. One on the right, called $R, and one on the left, called $L. $L is always optional but the syntax requires that you always pass something into $R, even if it is not referenced. Traditionally in functional programming, functions can only receive a single argument, but that argument is sometimes a list or a dictionary containing multiple values. In O2 we have monadic operators that take one argument on the right ($R) and dyadic operators that take arguments on both the right and the left ($R and $L respectively).

  reader:
  {
    signal=#wait last 0l
    =if
    {
      test:$signal.hold
      then:#wait last lines $signal
      else:{}
    }

The reader begins every iteration by reading the most recent state of the #wait symbol in the blackboard. It does this by using the last operator which takes one or more symbols on the left, and on the right, it takes the line number in the blackboard where you want to start reading. By passing 0l (zero) here, the reader ensures that last will always return immediately with the most recent state. If it received a right argument greater than 0l, last would block until the blackboard had an appropriate value at or beyond the requested line number. The value returned from last will be a signal, which is a tabular data structure that can have multiple rows and columns. In this case there will be only one column; hold, and one row for the symbol #wait. Then we use the if operator to test the value of the hold column; using the dot notation to reference columns in the signal value ($signal.hold). If hold is set to true, reader will call last again, but this time the goal is to block until the value of #wait changes. The lines operator is used to figure out how many lines were in the blackboard at the point when $signal was created. This ensures that the reader will not miss any updates to #wait even though there is no concurrency control between the two calls to last. It's just a couple lines of code but a lot of explanation is required. That is why I broke this into two posts. The net result of all of this is that the reader will now check to see if the writer is trying to write. If the writer is trying to write, the reader will wait until the writer sets hold=false again.

    =$R take
    {
      =cwrite "reader " + (string $R) + " begins reading"
      =sleep randoml 1 0 1000l
      =cwrite "reader " + (string $R) + " done reading"
    }
    <-reader $R
  }

At this point the reader is ensured that the writer is either not waiting, or if it is, has not been waiting for long because hold was set to false just moments ago when the writer checked on it. So the reader will go again and use take to enter its critical section, acquiring the lock that corresponds to just this reader fiber. This code is identical to the reader code from the prior post with one exception. In last week's example the reader would sleep for a while after the take block. This was to allow the writer thread a chance to occasionally get all the locks. With the improved concurrency control to avoid starving the writer thread, this is now unnecessary. So I have removed the sleep call to simulate a very aggressive reader.

  s:#readers,0l #readers,1l #readers,2l #readers,3l #readers,4l
  =#wait write {hold=false}

$s is a vector of symbols that correspond to each reader fiber. Note that symbols are tuples (ordered lists of typed scalar values). The elements of each tuple are separated by commas (,). This allows the blackboard to represent hierarchical data structures and also gives you a neat way to keep many symbols and groups of symbols organized.

  w=fiber {<-writer $s}
  r={<-fiber {<-reader $R}} each $s
  <-wait $w
}

Now launch a single writer and multiple reader fibers. Wait indefinitely for the writer to finish. Here is the entire piece without commentary.

{
  writer:
  {
    =#wait write {hold=true}
    =$R take
    {
      =cwrite "writer begins writing"
      =sleep randoml 1 0 1000l
      =cwrite "writer done writing"
      =#wait write {hold=false}
    }
    =sleep randoml 1 0 10000l
    <-writer $R
  }
  reader:
  {
    signal=#wait last 0l
    =if
    {
      test:$signal.hold
      then:#wait last lines $signal
      else:{}
    }
    =$R take
    {
      =cwrite "reader " + (string $R) + " begins reading"
      =sleep randoml 1 0 1000l
      =cwrite "reader " + (string $R) + " done reading"
    }
    <-reader $R
  }
  s:#readers,0l #readers,1l #readers,2l #readers,3l #readers,4l
  =#wait write {hold=false}
  w=fiber {<-writer $s}
  r={<-fiber {<-reader $R}} each $s
  <-wait $w
}

Example Output of the Readers-Writers Solution

Now let's run this program and see how it compares to the old version without the extra layer of communication to avoid starving the writer thread.

Welcome to O2, ask brian if you need help
O2>eval fload "../../src/rwnostarve.o2"
writer begins writing
{:2l :3l :4l :5l :6l}
O2>writer done writing
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
reader #readers,3l done reading
reader #readers,4l done reading
writer begins writing
writer done writing
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
reader #readers,3l done reading
reader #readers,4l done reading
writer begins writing
writer done writing
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
reader #readers,3l done reading
reader #readers,4l done reading
writer begins writing
writer done writing
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
reader #readers,3l done reading
reader #readers,4l done reading
writer begins writing
writer done writing
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
reader #readers,3l done reading
reader #readers,4l done reading
writer begins writing
writer done writing
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
reader #readers,3l done reading
reader #readers,4l done reading
writer begins writing
writer done writing
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l done reading
reader #readers,4l done reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
writer begins writing
writer done writing
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l done reading
reader #readers,4l done reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l done reading
reader #readers,4l done reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l done reading
reader #readers,4l done reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
reader #readers,3l begins reading
reader #readers,4l begins reading
reader #readers,0l begins reading
reader #readers,1l begins reading
reader #readers,2l begins reading
reader #readers,3l done reading
reader #readers,4l done reading
reader #readers,0l done reading
reader #readers,1l done reading
reader #readers,2l done reading
writer begins writing
writer done writing

Discussion

So does it work or what?

Yes.

  • The reader fibers are able to read concurrently (at the same time).
  • The writer fiber never begins writing until all readers are done reading.
  • The writer fiber never waits very long to get all of the locks even though the readers are very aggressive.

Why are the readers synchronized with each other?

You might also notice that the readers seem to be synchronized with each other. In most cases all five readers will finish before the first one begins again. After doing some research I found that this is due to a bug in my randoml operator, which is based on the .net Random class. You can pass your own seed into the left argument of randoml, but for simplicity's sake I don't do that in these examples. What happens is that each fiber creates its own instance of the Random class using the default constructor. The default constructor uses a seed that is based on the current time. But because the clock has a limited resolution the Random instances created by each fiber can end up having the same seed, and the producing the same values. This causes the reader fibers to sleep for the same amount of time and wake up at the same time. The recommended fix for this in the .net documentation is to share an instance of the Random class. I might do that but at the moment I don't have a good strategy for sharing instances of values across operators. Operators are always stateless unless they interact with common infrastructure like the blackboard. So I need to meditate a bit on how to proceed. It's kind of a tangent to this post, but a question that could come up.

What about the Third Readers-Writers Problem?

In the CS literature there is also a discussion of a Third Readers-Writers problem. The first one is the naive version that I did in my prior post. The second one is the problem of giving preference to writers, which we have just discussed. But what happens if the writer is too greedy and prevents readers from reading? This could be just as bad as seeing stale data in your database. Instead of stale data, you get no data at all because the writer keeps updating the database and never gives you a chance to read! If I were using classical concurrency control primitives like semaphores I would have to do a third post to solve this problem, and the solution could get very hairy. Fortunately O2's take operator always enforces first-in-first-out semantics. This means that if a symbol has been released that would allow two fibers to proceed, the one that has been waiting the longest will get to go first. This ensures that when the writer releases its symbols, any waiting readers will get to go before the writer goes again.

Where would I use a solution like this?

I would like to point out that you don't ever need to use O2's concurrency control facilities like take and dispatch to safely read and write from the blackboard. Those operations will always be thread-safe to the extreme. The purpose of fiber-level concurrency control is to give you control over how your fibers interact with or avoid interfering with each other. For example, you could have a need to update a database, filesystem, or other external hardware while other fibers are using it. Fibers are not heavy like threads. Potentially they can be used to keep tabs and coordinate things out in the real world, like robots in a factory, soldiers on a battlefield, orders on a trading floor, etc... Object Oriented Programming encouraged us to think about the world as a collection of objects sending messages to each other. I would rather think of the world as a collection of processes that communicate, coordinate, and compete in order to reach their goals. That is why I am spending so much time on concurrency in O2. It has to work and has to be done right. This is post number six which means I am halfway done.

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>