Compound Reader Zones

Welcome » NERWous C » Mel

1. Reader OR Zones
2. Reader LIST Zones
3. Reader AND Zones

In the previous chapter, we have been introduced to exclusive reader zones as applicable to a single mel variable. In this chapter we expand the discussion of reader zones to multiple mel variables. A future chapter will cover reader zones used with structured mels.

---

Reader OR Zones

We start with the reader OR zone. Let's look at this example where we have two mel variables worked on by three tasks: a Producer, a Consumer, and a Manipulator that Manipulates all the things that are Produced before being Consumed:

#include "nerw.h"
main () {
   <mel> int store1, store2;
   <pel> p = <!> Manipulator (store1, store2);
   <!> Producer (store1, store2);
   <!> Consumer (store1, store2);
}
void Producer (<mel> int store1, <mel> int store2) {
   while ( <?>(store1 || store2) = Produce() );
   <close>store1;
   <close>store2;
}
void Consumer (<mel> int store1, <mel> int store2) {
   while ( true ) {
     try Consume(<?>(store1 || store2));
     catch((store1 && store2)<CLOSED>) break;
   }
}
void Manipulator (<mel> int store1, <mel> int store2) {
   try <? priority=NERW_PRIORITY_HIGHEST as=store> (store1 || store2) {
      store = Manipulate(store);
      <checkout writeover>;
   } <resume>;
   catch ( (store1 && store2)<CLOSED> ) {}
   printf ("Manipulator is done");
}

The two mel channels back up one another. If Producer finds store1 not available, it will try to deposit its product to store2. When Produce generates a zero product, Producer will break out of the production loop and closes both mel channels. Likewise, the Consumer continuously tries to Consume from either store1 or store2 whichever is available, until it gets a CLOSED exception on both channels. Both tasks use the mel OR read wait facility.

Reader OR Zone Access

As said previously, the goal of the Manipulator task is to capture all the items from Producer via either the store1 or store2 channel, do some manipulation on these items before releasing them to the Consumer task. This is an iteration of the Manipulator for single mel variable we have seen in the previous chapter. To realize this goal for two mel variables, the Manipulator here also makes use of an exclusive zone to do the manipulation, but depends on the mel OR wait on the mel channels.

This is the behind-the-scene process:

1. The Manipulator task puts itself to store1 readers' queue. In the example above, it goes into the NERW_PRIORITY_HIGHEST priority readers' queue so that it can get to any produced items before Consumer.
    
2. If it happens (1) to be first on the queue and (2) store1 is valued and (3) this value is not stale, then it will check into the exclusive reader zone, and invokes Manipulate on the eponymous variable store representing store1.
    
3. If one of the conditions for store1 is false, Manipulator will put itself in the NERW_PRIORITY_HIGHEST priority readers' queue of store2. If it happens (1) to be first on this queue and (2) store2 is valued and (3) this value is not stale, then it will check into store2 exclusive reader zone, and invokes Manipulate on the eponymous variable store representing store2.
    
4. Otherwise, Manipulator will wait on both queues at the same time.
    
5. On the first queue that satisfies all 3 conditions (task first on the queue, mel is valued, and the value is not stale), Manipulator will check into the reader zone with that mel variable. Since this can be either store1 or store2, Manipulator uses the generic store eponymous variable.
    
6. Inside the reader zone, the task makes reads and writes to the eponymous variable store. Since this is a local variable, the mel wait operator (<?>) is not applicable.
    
7. After manipulation, the Manipulator task invokes the <checkout writeover> operation to update the mel channel and get out of the reader zone. The task remembers what mel channel is used on check-in so that the checkout behavior will be applied to that mel channel.
    
8. On checkout of the reader zone, the Manipulator task gets off both priority wait queues - the one for the mel channel it has checked in, and the one for the mel channel it still waiting on. However, as there is a <resume> operator used in our example, the task is put back on both waiting queues right away.

Reader OR Zone Traverse

The behind-the-scene description above uncovers a subtle difference between

<? priority=NERW_PRIORITY_HIGHEST as=store> (store1 || store2)

and

<? priority=NERW_PRIORITY_HIGHEST as=store> (store2 || store1)

The first mel item in the OR list is checked first. If it is re-valued constantly by a writer task, the mel wait on that first item is likely successful and the reader OR zone is spent more with the first mel than with the second mel.

This issue can be resolved by using the random traverse behavior for OR reads:

<? priority=NERW_PRIORITY_HIGHEST as=store> (store1 ||<random> store2)

With the random traverse behavior, the check for store1 and store2 is randomized instead of serialized.

Reader OR Zone Resumption

On checkout of the reader zone, the Manipulator invokes the <resume> operation to jump back to the mel OR zone entrance, waiting for either store1 or store2 again. The task is put at the back of the queues, but since it is the only task for the NERW_PRIORITY_HIGHEST queue, it is at the top of both queues again.

Reader OR Zone Exception

If one channel has been closed, the mel OR wait will focus solely on the remaining channel. If both channels have been closed, the (store1 && store2)<CLOSED> exception will be raised, causing the Manipulator to abort the waiting for the exclusive zone. In the above example, the Manipulator displays the printf statement before it ends.

Reader OR Zone Cases

The previous Manipulator does not care if it selects store1 or store2. It processes using the stand-in store the same. What if it does make a case of doing store1 somewhat differently from store2? Let's explore such a case:

void Manipulator (<mel> int store1, <mel> int store2) {
   try <? priority=NERW_PRIORITY_HIGHEST as=store> (store1 || store2) {
      printf ("Select [%ll] to manipulate", store<id>);
      if ( store<id> == store1<id> )
         store = Manipulate_1 (store);
      else
         store = Manipulate_2 (store);
      <checkout writeover>;
   } <resume>;
   catch ( (store1 && store2)<CLOSED> ) {}
   printf ("Manipulator is done");
}

By using the <id> property, Manipulator can make a case of using either Manipulate_1 or Manipulate_2 depending on what mel variable is selected.

Reader OR Zone Gotcha!

A knowledgeable reader will see that the above implementation of Manipulator is not correct. It will let Producer items slipped by and gone directly to the Consumer without being Manipulated. For example, while Manipulator is working on store1, store2 is available for Producer to deposit a new product and Consumer to consume it.

The correct solution is not to use the reader OR zone, but to use two single reader zones, one for store1 and the other for store2:

main () {
   <mel> int store1, store2;
   <pel> p1 = <!> Manipulator (store1);
   <pel> p2 = <!> Manipulator (store2);
   <!> Producer (store1, store2);
   <!> Consumer (store1, store2);
}
void Producer (<mel> int store1, <mel> int store2) {
   while ( <?>(store1 || store2) = Produce() );
   <close>store1;
   <close>store2;
}
void Consumer (<mel> int store1, <mel> int store2) {
   while ( true ) {
      try Consume(<?>(store1 || store2)); 
      catch((store1 && store2)<CLOSED>) break;
   }
}
void Manipulator (<mel> int store) {
   try <? priority=NERW_PRIORITY_HIGHEST>(store) {
      store = Manipulate(store);
      <checkout writeover>;
   } <resume>;
   catch ( store<CLOSED> ) {}
   printf ("Manipulator for [%s] is done", store<name>);
}

Sometimes it is necessary to use a bad example to introduce a new feature.

---

Reader LIST Zones

In the previous examples, we have Producer and Consumer take in two mel variables but use only one of them. Let's modify the example so that these tasks make use of both of them. This allows us to also change the Manipulator to make use of the reader LIST zone.

main () {
   <mel> int store1, store2;
   <pel> p = <!> Manipulator (store1, store2);
   <!> Producer (store1, store2);
   <!> Consumer (store1, store2);
}
void Producer (<mel> int store1, <mel> int store2) {
   while ( <?>(store1, store2) = ProduceTwoItems() );
   <close>(store1 && store2);
}
void Consumer (<mel> int store1, <mel> int store2) {
   while ( true ) {
     try ConsumeTwoItems(<?>(store1, store2));
     catch((store1 || store2)<CLOSED>) break;
   }
}
void Manipulator(<mel> int store1, <mel> int store2) {
   try <? priority=NERW_PRIORITY_HIGHEST>(store1, store2) {
      store1 = Manipulate(store1);
      store2 = Manipulate(store2);
      <checkout writeover>;
   } <resume>;
   catch ( (store1 || store2)<CLOSED> ) {}
}

This is the behind-the-scene process for a reader LIST zone access:

1. The Manipulator task puts itself to both store1 and store2 NERW_PRIORITY_HIGHEST priority queues.
    
2. In each queue whenever (1) the Manipulator task becomes first on the queue and (2) the corresponding mel is valued and (3) this value is not stale, then it will get hold to that mel and waits for the other queue to also satisfy those three conditions.
    
3. While waiting on a queue at the top of the queue position, the Manipulator task allows another reader task to get a stale value. However it will not allow another reader task to get a new value.
    
4. Once it can get hold of both the required mels, the Manipulator task will check into the exclusive reader zone.
    
5. From this time on, no reader task can get the blocked mel values. Non-intrusive readonly access and snapshot operation are still permissible.
    
6. In the reader zone, the Manipulator task uses the local eponymous variables, which are initialized with the original values of the remote mel variables.
    
7. Once it is done with the manipulations, the Manipulator task invokes the <checkout writeover> to replace the values of the mel variables with the values of the corresponding eponymous variables.
    
8. On checkout of the reader zone, the Manipulator task gets off both priority wait queues. However, since there is a <resume> operator, the task is put back on both waiting queues right away.

Since the reader LIST zone requires both mels, a closure of either one is bad for Manipulator. This is the reason its catch on the CLOSED exception uses an OR clause. Compare this with the reader OR zone example where the Manipulator triggers on an AND CLOSED exception.

Reader LIST Zone Gotcha!

Can a produced item sneaked by from the Producer to the Consumer without going through the Manipulator? This can happen with the reader OR zone, but not with the reader LIST zone.

Like the reader OR zone Manipulator, the reader LIST zone Manipulator is always present in the higher priority queue than the Consumer, thus it always has first dip to the mel variables. Unlike the reader OR zone version though, the reader LIST zone Manipulator blocks both mel variables when it is in the reader zone, preventing the Consumer to sneak by.

On the other hand, a Manipulator-like task can introduce starvation. If instead of checking out with a <checkout writeover> which leaves the mel value available for Consumer, it were to use <checkout> which would remove the mel value, the Consumer would never see a product from Producer.

---

Reader AND Zones

The reader AND zone uses the mel AND wait in order to have exclusive access to all the specified mel items.

Let's rewrite the Manipulator task using a reader AND zone:

void Manipulator(<mel> int store1, <mel> int store2) {
   try <? priority=NERW_PRIORITY_HIGHEST>(store1 && store2) {
      store1 = Manipulate(store1);
      store2 = Manipulate(store2);
      <checkout writeover>;
   } <resume>;
   catch ( (store1 || store2)<CLOSED> ) {}
}

The above Manipulator is a bad Manipulator because it will allow products from the Producer to slip by and go directly to the Consumer. Let's see how so.

1. The Manipulator task puts itself to both store1 and store2 NERW_PRIORITY_HIGHEST priority queues.
    
2. In each queue whenever the Manipulator task becomes first on the queue, it will join the "top-of-the-queue" readers group, as specified by the mel AND wait process. It then waits to join the "top-of-the-queue" readers group of the other requested mel variable.
    
3. When the Manipulator task is in a "top-of-the-queue" group for one mel reader's queue but not the other, it will allow other reader tasks to "jump the line" on that queue to get the mel value -- stale or new, in accordance with the mel AND wait process.
    
4. When the Manipulator task is in the "top-of-the-queue" groups of both mel variables, it will check if both mel variables are (1) valued and (2) not stale. If one of the conditions is not true for either mel, the task keeps waiting. During this wait, it will allow other reader tasks to "jump the line" on both queues to get the mel values -- stale or new.
    
5. Once all the conditions are met at both queues, the Manipulator task blocks both mels at the same time, and checks into the exclusive reader zone.
    
6. From this time on, no reader task can "jump the line" and get the mel values. Non-intrusive readonly access and snapshot operation are still permissible.
    
7. In the reader zone, the Manipulator task uses the local eponymous variables, which are initialized with the values of the mel variables.
    
8. Once it is done with the manipulations, the Manipulator task invokes the <checkout writeover> to replace the values of the mel variables with the values of the corresponding eponymous variables.
    
9. On checkout of the reader zone, the Manipulator task gets off both priority wait queues. However, since there is a <resume> operator, the task is put back on both waiting queues right away.

The use of the "top-of-the-queue" groups allows other reader tasks to "jump the line" and get the mel value even if this mel value is new to the Manipulator task. In our example, this reader task is the Consumer task and "jumping the line" will allow it to consume a product raw without being Manipulated.

On the other hand, the use of "top-of-the-queue" groups prevents deadlocks when multiple tasks vie for the same resources in a circular way, as in the The Dining Philosophers example. Unlike the readers LIST zone where the tasks get hold to the mel variables by themselves without knowledge of similar needs of other tasks, the readers AND zone method collects all such needs in "top-of-the-queue" groups where the NERW runtime has full knowledge to prevent deadlocks when granting exclusive access.

---

Previous Next Top