Pages

Friday, June 17, 2016

Mel Reader Zones

Welcome » NERWous C » Mel
  1. Reader Zones
  2. Eponymous Variables
  3. Checkout Operation
  4. Reader Zone Attributes
  5. Reader Zone Resumptions


Reader Zones

The NERWous C examples we have seen so far have the tasks getting a lock on the mel variable long enough to put in a new value (Producer tasks), or read out the deposited mel value (Consumer tasks). We now introduce a new NERWous C construct called exclusive zones where the tasks can hold on to the mel variables as long as it needs to. We start with the reader zone in this chapter, and will explore the writer zone in a future chapter.

Let's modify our Consumer task so that it only consumes an odd or even product depending on an argument request. To make sure that all products are consume'd, we will create two Consumer tasks, one for the even products, and the other for the odd products:
#define DO_EVEN 0
#define DO_ODD 1
main () {
   <mel> int store;
   <!>Producer (store);
   <!>Consumer (store, DO_EVEN);
   <!>Consumer (store, DO_ODD);
}
void Producer (<mel> int store) {
   int c;
   while ( 1 ) {
      c = produce();
      if ( c == 0 ) {
        <close>store;
        break;
      }
      <?>store = c;
   }
} 
void Consumer (<mel> int store, int evenodd) {
    while ( 1 ) {
       try {
          printf ("Waiting to enter reader zone");
          <?>store {
             if (  ((evenodd == DO_EVEN) && (store % 2) == 0))
                || ((evenodd == DO_ODD) && (store % 2) != 0)) ) {
                  consume (store);
         
                printf ("Consumed product [%d]", store);
             }
             else {
                printf ("Skipped product [%d]", store);
                <checkout skip>; 
             }
          }
          printf ("Stepped back from reader zone with value [%d]", store<value>);
       }
       catch ( store<CLOSED> ) {
          printf ("Exit because the Store is closed");
          break;
       }
    }
}
There is nothing special about Producer. It keeps produce'ing until a zero product is detected. It then closes the mel store and breaks from the infinite while loop. As it runs out of code to run, the task ends itself.

The task Consumer is the more interesting one. The task main pels two Consumer tasks, one to consume the even products and the other, the odd products. The task Consumer implements its logic inside an exclusive reader zone code block, <?>store { ... }.

When a task uses a mel (exclusive) reader zone, the following behind-the-scene process occurs:
  1. The task puts itself in the mel readers' queue.
     
  2. In due course, the task moves up to the top position of the readers' queue. If the mel is still empty, the task will wait at this position, until the mel becomes valued.
     
  3. If and when the mel is valued, the task checks the mel sequence number. If this number is the same as the locally cached <sequence> property that the task keeps from the last access, the mel is stale, and the task continues to wait at the top of the queue position. During this wait, the task allows another reader task behind it to "jump the line" to get the stale mel.
     
  4. When the task detects that the mel is valued with a new value, the task is ready to check in into the exclusive zone. See summary of conditions.
     
  5. With the task still keeping its top of the queue position, other incoming reader tasks must stand in line in various mel readers' priority queues. At this stage, the task does not allow subsequent reader tasks to "jump the line" to get to the mel value. The task now has exclusive read access to the mel variable.
     
  6. The check-in process has the task copy the mel value into a local eponymous variable but leave the mel value remaining at the remote mel variable.

    Instead of working with the remote mel which requires potentially expensive network communication, the task works with the eponymous local variable. This is the reason within the reader zone, the variable store can be accessed without the <?> wait operation -- we are accessing the eponymous local variable of the same name, and not the remote mel variable.
     
  7. While the task keeps other reader tasks at bay, it allows readonly access to the mel value left at the top slot of the mel buffer. If the readonly task returns for another readonly request, it may find that the mel value is still the same. In this case, the readonly task deems the mel variable stale and will wait at the readonly queue for a new value.
     
  8. If a writer task comes along, it may still able to deposit its item if the mel variable is buffered. When the mel buffer is full, the writer task will wait at the mel writers' queue until the exclusive zone task checks out off the exclusive zone and allows itself or another reader task to empty the top slot of the mel buffer.
     
  9. When the task is done with the reader zone, it either falls out of the reader zone's code block at the closing }, or invokes the checkout operation. The default behavior in both cases is to remove the mel variable off the top of the buffer. The value of the eponymous variable, that has been updated by the code inside the reader zone, is copied to the mel local <value> property. In addition, the mel local <sequence> property is also updated with the sequence number of the mel value that has been removed.
     
  10. Besides the default behavior, the task may choose other behaviors by calling the checkout operation with an attribute. In the example above, the DO_EVEN Consumer task does not process an odd product, and the DO_ODD one, an even product. The <checkout skip> operation has the task getting out of the reader zone without removing the top value from the mel variable buffer. Although there is no removal, the <value> property is still updated with the value of the eponymous variable. The <sequence> property is also updated with the sequence number of the mel variable (that has not been removed form the mel buffer) to prevent the task to re-process the just processed value in case of an iteration.
     
  11. After checking out off the reader zone, the task drops itself out of the mel readers' queue. Any reader task that has been waiting in the various mel priority queues can now has the chance to move up the queues and access the mel variable. Any writer task that has been waiting on the mel writers' queue because the buffer is full, can deposit its value if there is a new slot opened up from the default checkout behavior.
     
  12. After the reader zone checkout, our Consumer task iterates the infinite while loop and vies with other reader tasks to get access to the mel variable. During this wait, the store<CLOSED> exception can happen if the task Producer has closed the mel variable store. At the end of the exception handler, the task breaks out of the while loop, and with nothing else to do, ends itself.
The task main after pelling the three tasks has already ended. With the Producer and the two Consumer tasks also ended, there are no more running tasks. The program itself then exits.

Conditions

Let us repeat the conditions that allow the task to get into the reader zone:
  1. The task must be at the top position of the reader's queue
  2. The mel variable has a value at the reader's end of the mel buffer
  3. This value is not stale


Eponymous Variables

When a task checks into the exclusive reader zone, the value of the mel variable is automatically copied to a local variable in the task's environment. This local variable is called the eponymous variable since it has the same name as the mel variable. Within the reader zone, the task does reads and writes to the local eponymous variable instead of to the remote mel variable. Since the access is local, there is no need for the wait operation (<?>).

When the task is in the exclusive reader zone, it can read from the eponymous variable as we see with the Consumer task that consumes what it reads. It can also make change to the eponymous variable as we will see in the upcoming Manipulator task. Thus, the value of the eponymous variable can diverge from the original value of the mel variable.

When the task checks out of the reader zone, what happens to the value contained in the eponymous variable depends on the mode of the checkout operation.


Checkout Operation

A task checks into a reader zone exclusive to a mel variable, say store, via the <?>store { opening construct. It checks out of the zone at the closing curly bracket (}) or by explicitly invoking the checkout operation. Checking out via the closing bracket is the same as implicitly invoking the checkout operation without any attribute.

On checking into the reader zone, the value of the mel variable is copied to the eponymous variable maintained locally at the task. When the task checks out of the reader zone, what happens to the local mel properties and the remote mel variable depends on the checkout operation attributes:

OperationSynopsis
<checkout> Checkout with default mode. If the default mode is not specified on check-in of the exclusive zone, the <checkout read> is assumed.
<checkout read> This is the default behavior. The task removes the mel value off the mel buffer when checking out of the reader zone. This is similar to a mel read operation. The removal of the mel value frees the top slot of the mel buffer, allowing the next item in the buffer to move up and a writer task to deposit a new value at the writer's end of the buffer.
<checkout skip> The task checks out of the reader zone without removing the value of the mel variable. The value the mel variable has on entry of the reader zone is retained. This value is then available for another reader task. Since the mel buffer is not emptied of its top slot, any writer task that is waiting due to a full buffer, will continue to wait.
<checkout writeover> The task checks out of the reader zone without removing the value of the mel variable. However the value of the mel variable is updated with the value of the eponymous variable. This updated value is then available for another reader task. Since the mel buffer is not emptied of its top slot, any writer task that is waiting due to a full buffer, will continue to wait.

The sequence number is increased at both the remote mel variable and the local mel property <sequence> of the checkout task.

Let's take a look at this example, and compare the local <value> and <sequence> properties against the remote mel variable's value and sequence number, at the checkout of the reader zone.
extern int testcase;
<?>store = 10;  /* mel variable */
printf ("Before value [%d], seqno [%lld]", store<value>, store<sequence>);
<> store {
   store++;    /* eponymous variable */
   if ( testcase == 1 ) <checkout read>;
   if ( testcase == 2 ) <checkout skip>;
   if ( testcase == 3 ) <checkout writeover>;
}
printf ("After value [%d], seqno [%lld]", store<value>, store<sequence>);
On check-in to the reader zone, the value of the mel variable is set to 10, and let's assume that its sequence number is the number X. On checkout, we have this matrix, depending on the testcase taken:

Local Properties Mel Variable
<checkout read> The store<value> property has the value of the eponymous variable (hence, 11). The store<sequence> property has the value of the sequence number of the remote mel variable on check-in of the reader zone (hence X). The value of the remote mel variable is undefined since it has been removed by the <checkout read>. The sequence number of the remote mel variable does not change from the reader zone entry (hence X).
<checkout skip> The store<value> property has the value of the mel variable on entry of the reader zone (hence, 10). The store<sequence> property also retains the sequence number got by reading the mel variable on check-in of the reader zone (hence X). The remote mel variable retains the same original mel value (hence 10) and sequence number (hence X) as on entrance of the reader zone.
<checkout writeover> The store<value> property has the value of the eponymous variable (hence, 11). The store<sequence> property has the value of the sequence number of the remote mel variable on check-in of the reader zone plus one (hence X+1). The remote mel variable has the value of the eponymous variable (hence, 11). Its sequence number has been increased by one (hence X+1).


Checkout Writeover

When a checkout writeover is invoked, the sequence number of the remote mel variable is increased. This allows reader tasks that wait for a new mel value to get out of their slumber. The increased sequence number is also copied to the local <sequence> property of the task that does the checkout writeover. Identical sequence numbers indicate staleness, and this prevents this task to reprocess the mel variable in case the exclusive zone wait is resumed in an iterative loop. As a reminder, the local <sequence> property associated with this mel variable in other tasks is not updated until that particular task has successfully done a read or write operation to the mel variable; thus staleness does not apply to those other tasks -- they are free to read the new mel value.

The checkout writeover mode is used frequently enough in NERWous C programs that it has a shortcut for a particular case. If a task enters a reader zone and knows that most of the ways that it will checkout of the zone is via the checkout writeover mode, it can specify this mode as the default mode on entrance of the reader zone.

The following code samples on the mel variable store are equivalent:
/* Standard version for writeover mode */
<?>store {
   store += 10;   /* no matter what, alwsys increase store by 10 */
   if ( !checkformore(store) ) <checkout writeover>;
   store += 10;   /* store can get another 10 */
   <checkout writeover>;
}
---
/* Writeover mode default version */
<? mode=writeover>store {
   store += 10;   /* no matter what, alwsys increase store by 10 */
   if ( !checkformore(store) ) <checkout>;   /* writeover is assumed */
   store += 10;   /* store can get another 10 */
}  /* <checkout writeover> is assumed
---
/* Omitted mode keyword */
<?writeover>store {
   store += 10;   /* no matter what, alwsys increase store by 10 */
   if ( !checkformore(store) ) <checkout>;   /* writeover is assumed */
   store += 10;   /* store can get another 10 */
}  /* <checkout writeover> is assumed
Like the writeover mode for a mel variable wait, the mode keyword can be omitted for a mel zone wait.


Reader Zone Attributes

Like any mel wait operation, a mel reader zone wait has the following attributes:

AttributeSynopsis
modeDefault mode on checkouts
priorityWait to check in using this priority
timeoutWait to check in up to this timeout value. If the timeout is reached, a <TIMEOUT> exception will be raised.

To illustrate the use of the priority and timeout attributes, let's introduce a new task called the Manipulator. whose purpose is to surreptitiously convert any products from the Producer into an even number.
#include "nerw.h"
#define DO_EVEN 0
#define DO_ODD 1
main () {
    <mel> int store;
    <pel> p = <!>Manipulator (store);
    <!>Producer (store);
    <!>Consumer (store, DO_EVEN);
    <!>Consumer (store, DO_ODD);
}
/* VERSION 1 */
void Manipulator(<mel> int store) {
   while (1) {
      try {
         printf ("Yet another round of waiting...");
         <? priority=NERW_PRIORITY_HIGHEST timeout+timeout>store {
            store += store;      // double store to make it even
            <checkout writeover>;
         }
      }
      catch ( store<CLOSED> ) { break; }
      catch ( store<TIMEOUT> ) {
         printf ("Is something wrong with Producer?");
         continue;
      }
    }
}
The task main pels the task Manipulator and makes sure that is running by using the pel variable assignment. Then the task main pels the Producer and the two Consumer tasks like before. The codes for Producer and Consumer are the same as in the original example, and are not repeated here.
Side note:
The use of the pel variable p for Manipulator is to prevent a potential race condition. A pel operation (<!>) is only a request to run the code in a separate task, not an assurance that the task has actually run. Without the pel variable assignment, there is no guarantee that the Manipulator will run before a Consumer task. If a Consumer gets assigned to faster resources and starts to execute before Manipulator, some initial products may go from Producer to Consumer without being Manipulated.

Priority Attribute

The two Consumer tasks and the Manipulator task vie to enter the exclusive reader zone. Since the Manipulator task waits at the highest possible priority for the run-time environment in use, it will be given first access. The Consumer tasks do not specify a priority and thus will be waiting in the default priority queue. The priority queues used for the reader zones are the same priority queues used for the regular mel reads.

When Manipulator is in the reader zone, it turns the eponymous store value into an even number by doubling it. It then gets out of the zone with a <checkout writeover> operation, resulting in the mel variable value being replaced with the new double even value. The Consumer task that is first in line in the default queue is now given exclusive access to the mel variable. If this is the DO_EVEN task, it will consume the manipulated value, and removes that value off the mel variable. If this is the DO_ODD task, it will get off the reader zone with a <checkout skip> operation, leaving the mel variable value untouched for the upcoming DO_EVEN task.

For all the three tasks, the local <sequence> property of the mel variable is updated, allowing them to wait for a new mel store value from the Producer instead of re-processing a stale value.

Timeout Attribute

The Manipulator also makes use of the timeout attribute during the reader zone wait. If it cannot get into the zone after double the default system timeout (timeout + timeout), it will jump into the store<TIMEOUT> exception handler, prints a message, and iterates back to the while loop to wait again.

The timeout exception as used in this example may allow a Consumer task to sneak in while the Manipulator is running the exception handler, and process an un-manipulated product from Producer.

Mode Attribute

If a task checks into a reader zone and knows that most of the ways that it will check out of the zone is via a certain checkout mode (be it read, skip or writeover), it can specify this mode on the check-in of the reader zone, using the mode attribute.

When specifying the mode attribute, the keyword mode can be ignored. Instead, just the value of the mode (either read, skip or writeover) is specified. In the examples below, we will use this condensed short-form format.

Read Mode Attribute:
This is not necessary because the default mode is already the read mode. However a programmer may feel compel to mention it explicitly for emphasis, especially if one of the checkout cases will be in a different mode. Let's rewrite the Consumer example above with an explicit read mode:
void Consumer (<mel> int store, int evenodd) {
    while ( 1 ) {
       try {
          printf ("Waiting to enter reader zone");
          <?read>store {
             if (  ((evenodd == DO_EVEN) && (store % 2) == 0))
                || ((evenodd == DO_ODD) && (store % 2) != 0)) ) {
                  consume (store);
         
                printf ("Consumed product [%d]", store);
             }
             else {
                printf ("Skipped product [%d]", store);
                <checkout skip>; 
             }
          }
          printf ("Stepped back from reader zone with value [%d]", store<value>);
       }
       catch ( store<CLOSED> ) {
          printf ("Exit because the Store is closed");
          break;
       }
    }
}

Skip Mode Attribute:
Now let's rewrite the Consumer example with the skip mode as the default mode:
void Consumer (<mel> int store, int evenodd) {
    while ( 1 ) {
       try {
          printf ("Waiting to enter reader zone");
          <?skip>store {
             if (  ((evenodd == DO_EVEN) && (store % 2) == 0))
                || ((evenodd == DO_ODD) && (store % 2) != 0)) ) {
                  consume (store);
         
                printf ("Consumed product [%d]", store);
             }
             else {
                printf ("Skipped product [%d]", store);
                <checkout>;   /* this is now checkout skip */
             }
          }
          printf ("Stepped back from reader zone with value [%d]", store<value>);
          <checkout read>;   /* need this */
       }
       catch ( store<CLOSED> ) {
          printf ("Exit because the Store is closed");
          break;
       }
    }
}
We need to add a checkout read statement before getting out of the reader zone because the implicit checkout now means checkout skip due to the default mode now set to skip.

Writeover Mode Attribute:
The writeover mode has been discussed in the Checkout Writeover section:
void Consumer (<mel> int store, int evenodd) {
    while ( 1 ) {
       try {
          printf ("Waiting to enter reader zone");
          <?writeover>store {
             if (  ((evenodd == DO_EVEN) && (store % 2) == 0))
                || ((evenodd == DO_ODD) && (store % 2) != 0)) ) {
                  consume (store);
         
                printf ("Consumed product [%d]", store);
             }
             else {
                printf ("Skipped product [%d]", store);
                <checkout skip>;   /* need to be specific */
             }
          }
          printf ("Stepped back from reader zone with value [%d]", store<value>);
          <checkout read>;   /* need to be specific */
       }
       catch ( store<CLOSED> ) {
          printf ("Exit because the Store is closed");
          break;
       }
    }
}
While the default mode is writeover, none of the checkouts are writeover, thus the checkout modes must be specifically designated.


Reader Zone Resumptions

An astute reader will notice that there is a flaw in the VERSION 1 of the Manipulator above. This flaw may allow a Consumer to access the store variable before Manipulator has a chance to modify it, even though Manipulator is on a higher priority queue.

In VERSION 1, after the reader zone checkout, Manipulator is not on any mel waiting queue. It jumps back to the beginning of the while loop, checks the while loop condition (which is always true), prints to the console the "Yet another round of waiting..." message, and then finally gets back to the high priority mel waiting queue. During this interval, it may happen that the waiting Consumer task is a DO_EVEN one. It will get into the reader zone and processes the mel value that Manipulator has changed, and removes the mel value on checkout. If the mel variable is buffered, the Producer may have feed the subsequent slots. The processing gap that Manipulator has left open, may be enough for the DO_ODD Consumer that is next in line in the default queue to grasp the next item in the mel buffer. If this item is odd, it will be consume'd, defeating Manipulator's goal to manipulate all products to be even.

To resolve this flaw, we will use the resume operation.
/* VERSION 2 */
void Manipulator(<mel> int store) {
    while (1) {
      try {
         printf ("Yet another round of waiting...");
         <? priority=NERW_PRIORITY_HIGHEST timeout+timeout>store {
            store += store;      // double store to make it even
            <checkout writeover>;
         } <resume>;
      }
      catch ( store<CLOSED> ) { break; }
      catch ( store<TIMEOUT> ) {
         printf ("Is something wrong with Producer?");
         continue;
      }
    }
}
The <resume> operation must be invoked at the closing bracket of the reader zone code block. This instructs the CHAOS run-time to put the task right back to the waiting queue for re-entry to the reader zone instead of having it totally leave the queue. The task is put at the end of the waiting queue to give tasks already in the queue the chance to get into the reader zone.

By invoking <resume>, the Manipulator task bypasses the while loop iteration and the "Yet another round of waiting..." printing. If this message is not necessary, we can simplify Manipulator by omitting the while loop and use only the resumption for iterations:
/* VERSION 3 */
void Manipulator(<mel> int store) {
   try {
      <? priority=NERW_PRIORITY_HIGHEST timeout+timeout>store {
         store += store;      // double store to make it even
         <checkout writeover>;
      } <resume>;
   }
   catch ( store<CLOSED> ) { }
   catch ( store<TIMEOUT> ) {
      printf ("Is something wrong with Producer?");
      <resume>;
   }
}
With the removal of the while loop, the break statement inside the <CLOSED> exception handler is unnecessary and is thus removed. On the other hand, the continue statement inside the <TIMEOUT> handler is replaced by a <resume> statement to allow Manipulator to resume its attempt to check into the reader zone again.

Again the astute reader will notice a processing gap between the TIMEOUT exception occurrence and the resume invocation. When an exception occurs. the task is moved out of the waiting queue. By the time Manipulator puts itself back on the highest priority queue via resumption, one or more buffered store products may have been processed by the Consumer tasks. This is the characteristic of a resumption within an exception handler - NERWous C programmers must be aware of it and code the logic of their programs accordingly.


Previous Next Top

No comments:

Post a Comment