Saturday, February 25, 2012

Conditional Critical Regions

Hoare, in "Towards a Theory of Parallel Programming" describes something called a "conditional critical region", this is an expansion of an idea of Dijkstra's, called critical regions.

Briefly then, a critical region is a syntactic construct that looks something like:

         with r do C

where r is the name of the critical region or resource, and C is the statement to be executed without interference from any other such statements also executed under the auspices of with r. This is pretty much exactly the sort of thing we have in C# and Java with the lock and synchronized statements, respectively.

Stop me if I am going too fast. So what is a conditional critical region then? It, as Hoare described it originally adds a Boolean condition to which the critical region will not be entered until such time as the condition is or becomes true. It looks like

       with r when B do C

So if B is false, we block until it becomes true through the intervention of some other thread of execution. Java and C# do not have this construct. Instead they have a lower level mechanism, await and Monitor.Wait respectively. These are a little bit similar to an extension to condtional critical regions, the await statement.


      with r do 
         begin
                 C1
                 await B
                 C2
         end

After C1, if B is false, control of the region will be relinquished until B becomes true. Then C2 will be executed again with the resource held. The difference between this, and Java's await is that await in Java releases the critical region unconditionally, you have to check B yourself. Consequently, the correct way to write this in Java (or C#) looks like

      synchronized( r ) {
          C1
          while( ! B ) {
             r.await();
          }
          C2
     }

This is, as you can imagine a source of errors, commonly using if instead of while to test B. 

So that is what conditional critical regions are. I think that when and await are probably the appropriate level of abstraction and utility when compared to something like pthread-style condition variables or Java/C# monitors. So I would like to implement them in C++. When I started doing that I found myself facing a problem, which is actually going to be the focus of my next post (and will have nothing to do with concurrency at all really).