Mel Writes

Welcome » NERWous C » Mel

1. Mel Write Attributes
2. Mel Writer Mode
3. Mel Write Waits
   1. Mel Write Process
   2. Mel Write Conditions
   3. Mel Write Buffers
4. Mel Writeover Mode
5. Mel OR Writes
   1. Serial OR Writes
   2. Random OR Writes
   3. OR Write Exceptions
6. Mel AND Writes
1. Serial AND Writes
2. Parallel AND Writes
3. InSimul AND Writes
7. Mel LIST Writes

---

Mel Write Attributes

The other side of a mel read which we explore in the previous chapter, is a mel write. Let's consider these two mel write statements:

<?>store1 = c1;
<? priority timeout mode="writeover">store2 = c2;

The first statement is a simple mel write statement with no attributes. The second statement is a mel write statement with all the attributes stated:

Operation	Attributes	Synopsis
<?>store = c	Mel write operation on the mel variable store
	priority =n	Access the mel element for writing with priority n
	timeout =msec	Wait for the mel buffer to have an empty slot for writing for msec milliseconds before aborting
	mode =setting	Request write access to the mel with this mode setting: writer: request a write access (default) writeover: request an overwrite access
	method =<keyword>	Method used for mel multiple writes: mel OR writes and mel AND writes

A mel write statement is not only about accessing the remote mel element, but also about waiting for the task's turn to access in one of the writer's queues, then waiting for an empty slot in the mel buffer from the writer's end, and finally depositing the new value to that available slot. The last action will allow any reader task that is waiting for the mel element to be filled, to read out the new value and make the mel buffer slot available again for a new write.

Instead of depositing a new value, a writer task can overwrite the last written (and still un-read) value in the mel buffer, by using the mode attribute writeover. This feature can be used by a producing task to keep improving the interim result until a reader task takes it away.

---

Mel Writer Mode

A mel write operation accesses a mel variable at the writer's end of the mel buffer. A fully descriptive mel write operation specifies the writer mel buffer access mode. For example to write to the mel variable store the value of the local variable c:

<? mode=writer> store = c;

The mode keyword can always be omitted:

<?writer> store = c;

Finally, the attribute value writer can also be omitted:

<?> store = c;

Due to the position of the mel variable on the left-hand side of the = operator, a mel write operation can be identified at compile time without the verbose use of the writer mel buffer access mode. However, when we come upon mel writer zones in the future, we'll see the writer mode is necessary to differentiate them from mel reader zones.

---

Mel Write Waits

In the following Producer/Consumer example, the Producer task makes use of the mel write access:

main () {
  <mel> int store;
  <!> Producer (store);
  <!> Consumer (store);
}
void Producer (<mel> int store) {
  while ( 1 ) {
    try { <?>store = Produce(); }
    catch ( store<TIMEDOUT> ) {
      printf ("Timeout - try again");
      <resume>;
    }
    catch ( store<CLOSED> ) {
      printf ("Store closed - get out");
      break;
    }
    catch ( store<...> ) {
      printf ("Unexpected error [%d] due to [%s]", store<error>, store<why>);
      break;
    }
  }
}
void Consumer (<mel> int store) {
  int maxconsump = 500;
  while ( maxconsump-- ) {
    Consume(<?>store);
  }
  <close>store;
}

This Consumer task only Consumes 500 items. Then it ends the while loop, closes the mel store, and ends itself.

The purpose of the Producer task is to keep Produce'ing the items for Consumer until the latter is done with consumption.

Mel Write Process

This is the behind-the-scene process for the statement

<? timeout>store = Produce();

1. The Producer task Produces a new product and puts itself into one of many possible writers' queues of the mel store.
    
2. The writers' queue Producer selects to stand in line is based on the priority of the mel write operation. Here, no priority attribute is explicit so the default writers' queue is used.
    
3. If there are other writer tasks in the queue, the Producer task moves up the queue as the front tasks get off the queue, until it reaches the top position of the queue.
    
4. At the top position, the Producer waits for the queue to have WRITE access to the mel store. In this example, Producer is the only writer task, there is no vying for the access from higher priority queues. Therefore, although the default writers' queue has the lowest priority to write to the mel buffer, it is granted WRITE access.
    
5. If the mel buffer is vacant, the Producer task will deposit its product into the mel buffer from the writer's end, increases the sequence number, and gets off the mel store default writers' queue. The mel buffer is now filled. The slot with the new product eventually moves up the mel buffer to the top position on the reader's end and becomes available for retrieval by the Consumer reader task.
    
6. If the mel buffer is fullProducer keeps the top position in the queue and waits until the mel buffer of store becomes vaant. Then it processes as above.
    
7. If Producer cannot write its product before the timeout, the TIMEDOUT exception is raised. Producer will get off the mel store writers' queue, and processes the <resume> operation to try to deposit again.

   If we were using continue instead of <resume>, we would loop back the while loop, which would cause a new product to be Produced. The product that got timed out would be lost. If the logic of the program were to skip any timed out item (perhaps because it had become obsolete), then continue would be the right choice.

8. If Consumer has processed 500 items, it will close the mel element store. On the next iteration of the while loop, the Producer will get hit with the CLOSED exception, when it tries to write to the mel store.
    
9. When the Producer receives the CLOSED exception, it will get off the mel store writers' queue, and processes the CLOSED catch handler. Here, it breaks out of the while loop, and with nothing else to do, it will end itself.

If during an attempt to write to the mel store, the Producer detects an exception other than TIMEDOUT or CLOSED, it will get off the mel writers' queue, and jumps to the catch-all handler:

catch ( store<...> )

Here, it prints the Unexpected exception statement with the error code and cause of the exception, and then breaks off the while loop. Without the catch-all handler for store, any unexpected and thus unprocessed exception from store will cause the Producer task to abort abruptly, instead of ending graciously.

Mel Write Conditions

As a summary, the following conditions must be met before a task can write in a mel value:

1. The task is at the top position of a writers' queue
2. The writers' queue has been granted WRITE access to the mel element
3. The mel element must have a vacant slot for the task to deposit its product

The first condition is relevant when there are other tasks already in the queue. Only the task at the top of the queue can deposit its product to the next available slot of the mel buffer from the writer's end.

The second condition is relevant when there are multiple queues vying for access to the same mel element. A queue with a higher priority is granted access to the mel element more often than lower priority queues.

The third condition is relevant when the mel element is full. The writer task must wait for a reader task to remove a value in the mel buffer to make room for the deposit.

Mel Write Buffers

The purpose of a mel write request is to deposit a new value to the mel element. If the mel element is not buffered -- which is the default for a mel declaration, the writer task has to wait for a reader task to empty the mel element to make room. If the mel element is buffered, the writer task can deposit into an empty slot in the buffer until the buffer is full.

The availability of a mel buffer differentiates a mel write from a mel read. A read can only work with only the top value of a mel. This also how a write works if the mel is not buffered. If a programmer buffers a mel variable, a writer can deposit in the empty slots of the buffer without waiting for a reader to empty the top slot. With enough resources assigned to the buffer, a mel write wait can be greatly minimized.

Note that we have been using the term mel buffer even on mel elements that are not buffered. In these cases the mel buffer is considered to be of size one (i.e. having one slot).

---

Mel Writeover Mode

In addition to the default writer mode which requires the task to wait for a vacant mel buffer, the mel write operation supports the writeover mode that does not require such wait. This mode behaves like the writer mode if the mel buffer is vacant, but if the buffer is full or filled, it will overwrite the last written item without looking for an empty slot.

Let's create a new Producer that creates a "good-enough" product first for impatient consumers. It then produces a "better" product to replace the "good-enough" product if the latter has not been retrieved by any consumer.

void Producer (<mel> int store) {
  int c;
  while ( 1 ) {
    if ( c = ProduceGood() ) break;
    <?>store = c;
    if ( c = ProduceBetter() ) break;
    <? mode=writeover>store = c;
  }
  <close>store;
}

The mode keyword is optional. The Producer could also make this statement:

<?writeover>store = c;

The above Producer makes two write operations to the mel variable store. The first one is a normal write operation using the default writer mode where it has to wait for a vacant slot in the mel buffer. The second write overwrites the value from the first write if it has not been picked up by a consumer; otherwise it just deposits the "better" product for the next consumer.

This is the behind-the-scene processing of a generic task doing a writeover to a mel element. The first steps are the same as those for a writer mode:

1. The task generates a new product and puts itself into one of many possible writers' queues of the mel element.
    
2. The writers' queue the task selects to stand in line is based on the priority of the mel write operation. If no priority attribute is explicit, the task joins the default writers' queue.
    
3. If there are other writer tasks in the queue, the task stays in the queue, and moves up to the front of the queue as the tasks in front of it get off the queue.
    
4. At the front position, the task waits for the queue to have WRITE access to the mel buffer due to competition from higher priority queues, if any.
    
5. After its queue is granted WRITE access, the task checks for the status of the mel buffer. This is where the writeovr mode can differ from the default writer mode:
   • If the mel buffer is empty (i.e., all mel buffer slots are vacant), the task deposits its product at the writer's end of the mel buffer. This is the same as in a writer mode.
      
   • If the mel buffer filled (i.e., some slots are vacant and some not), the task overwrites the last written slot with its own product. This differs from the writer mode where the task deposits its product on an available vacant slot.
      
   • If the mel buffer is full (i.e., none of the slots are vacant), the task overwrites the last written slot with its own product. This differs from the writer mode where the task waits for a vacant slot to be made available.
6. The task increases the sequence number of the deposited or overwritten item, and gets off the mel queue with no error reported.
    
7. If there is an error during the writeover process, the task will get off the mel queue without making any new deposit or overwrite in the mel buffer, and raises an exception.

The above Producer attempts to overwrite a "good-enough" product with a "better" product, but a fast Consumer task can still retrieve the "good-enough" product before Producer has time to overwrite it. In addition, if there is another writer task that inserts its own product right after Producer writes in its "good-enough" product, the value that Producer overwrites with its "better" product will be of the other writer task since this value is the last written value.

There are several uses of a writeover mode in NERWous C:

1. Ad-hoc use like in the above example, to fit the logical need of a program
2. As the write mode for a read-only mel
3. As the write mode for a release statement
4. As the write mode for exclusive zones

---

Mel OR Writes

Like the mel OR read, there is a corresponding mel OR write. Let's consider a Producer task that can send its product to either store1 or store2 mel elements, depending on which one is available to receive the new value. There are two methods that such a task can use to traverse the mel elements:

Mel OR Write Methods
Method Value	Description
Serial	The task checks the mel elements serially based on the order in the OR list.
Random	This is the default method when no method is specified. A random generator dictates which mel element in the OR list is checked first. The task then circulates through the remaining mel elements in the list. This method is more compute intensive but gives a fairer chance to all mel elements in the OR list.

Serial OR Writes

Let's start with a Producer that uses the Serial method:

void Producer (<mel> int store1, <mel> int store2) {
  while ( <? method=serial>(store1 || store2) = Produce() );
  <close>store1;
  <close>store2;
}

The keyword method can be omitted:

while ( <? serial>(store1 || store2) = Produce() );

This is the behind-the-scene process of the Serial mel OR write statement:

<? serial>(store1 || store2) = Produce()

1. The Producer task Produces a product, and puts itself onto store1 default writers' queue.
    
2. If the mel WRITE conditions are satisfied on store1, Producer will deposit its product into store1 buffer at the writer's end, increases the sequence number on store1, gets off the mel store1 default writers' queue, and exits the mel OR write statement. The store1 mel element is now filled for a reader task.
    
3. If the mel WRITE conditions are not met at store1, the Producer continues to wait in the store1 writers' queue, and also puts itself to store2 default writers' queue.
    
4. If the mel WRITE conditions are satisfied on store2, Producer will deposit its product into store2 buffer at the writer's end, increases the sequence number on store2, removes itself from both mel writers' queues, and gets off the mel OR write statement. The store2 mel element is now filled for a reader task.
    
5. Otherwise, Producer will wait on both queues, until the mel WRITE conditions become true for either one. The Producer then deposits its product to the identified mel buffer, increases the sequence number on that mel element, removes itself from both queues, and gets off the mel OR write statement. Either store1 or store2 has been filled, but Producer does not know which one.
    
6. If it happens that the mel WRITE conditions become true at both mel elements at the same time, the CHAOS runtime will ensure that Producer will write to one or the other mel element , and not both.

In the above example, Producer keeps producing and depositing its product to either store1 or store2 whichever is vacant at that time, until it Produces a zero value. It then breaks off the while loop and closes both mel channels.

Random OR Writes

Although either mel element can be selected, there is a bias for the first mel element in the Serial OR write method, due to it being looked on first when the OR write starts. If this first mel element is always vacant, perhaps due to it having an ample buffer or working with a fast reader task, it will keep being picked up, shunting the rest from ever be. If the logic of the program demands that all mel elements in the mel OR write have a fair chance, then the Random method is used:

void Producer (<mel> int store1, <mel> int store2) {
  while ( <? method=random>(store1 || store2) = Produce() );
  <close>store1;
  <close>store2;
}

The keyword method can be omitted:

<? random>(store1 || store2) = Produce()

Since the Random method is the default method for mel OR writes, the keyword value random can also be omitted:

<?>(store1 || store2) = Produce()

The behind-the-scene process for the Random mel OR write starts with the task picking a mel element in the mel OR list in a "fairly random" manner. NERWous C does not define a particular strategy for "fairly random" as long all the mel elements in the mel OR list has a fair chance to be picked first.

Once the starting element is picked, the Random method follows the Serial method. After the last mel element in the OR list is checked and found not available for writing, the Random method wraps around and checks the first element in the mel OR write list.

OR Write Exceptions

The above Producer assumes no error to happen in the mel OR write operation. The following Producer is hardened with exceptions to handle possible errors:

void Producer (<mel> int store1, <mel> int store2) {
  while ( 1 ) {
    try {
      int c = Produce();
      if ( !c ) break;
      <? timeout=100>(store1 || store2) = c );
    }
    catch ( (store1 || store2)<TIMEDOUT as=store> ) {
      printf ("The mel element [%s] has timed out", store<name>);
      <resume>;
    }
    catch ( (store1 && store2)<CLOSED> ) {
      printf ("Both mel elements have closed");
      break;
    }
    catch ( (store1 || store2)<... as=store> ) {
      printf ("The mel element [%s] has error [%d]", store<name>, store<error>);
      if ( store<error> == NERW_ERROR_CLOSED ) <resume>;
      break;
    }

    <close>store1;
    <close>store2;
}

The exception rules for mel OR writes are similar to the mel OR reads rules:

• Skipping rule: if an exception happens to a mel element, and there is no specific handler for that mel exception, the CHAOS runtime will remove the task from waiting on that mel element. The mel OR write continues with the mel elements that have not had any exception.
   
• Aborting rule: if there is a specific handler for that mel exception, the mel OR write is aborted. The task gets off all the waiting mel queues, including those that belong to mel elements that do not have exceptions; and the task will process the identified handler.
   
• Precedence rule: individual exception handlers take precedence over combination exception handlers. An AND combination exception handler takes precedence over an OR combination exception handler.

Based on the above rules, we can simplify Producer as follows:

void Producer (<mel> int store1, <mel> int store2) {
  while ( 1 ) {
    try {
      <? timeout=100>(store1 || store2) = Produce() );
    }
    catch ( (store1 && store2)<...> ) {
      if ( store1<error> == NERW_ERROR_TIMEDOUT || store2<error> == NERW_ERROR_TIMEDOUT)
          <resume>;
      break;
    }
  }
  <close>store1;
  <close>store2;
}

In this new Producer, if one mel element gets into an error, it will be automatically skipped; and the mel OR write continues with the other mel element. There is no need for an explicit handler for this built-in behavior.

If both mel elements get any kind of error (same or different errors), then the task gets off the mel OR write, and processes the AND combination catch-all exception handler. If one or both errors are a TIMEDOUT, the task does a resumption in order to try to deposit the current product from Produce again. The timed-out mel element or elements will be cleared on this error on exit of the handler, and can accept a write deposit. (If the logic of the program says to discard timed-out products because they are deemed "stale", the continue statement should be used to re-iterate the while loop for a new product, instead of the <resume> statement.)

If neither mel elements get a TIMEDOUT error (i.e. both get a CLOSED or some other error), the task breaks off the infinite while loop. The <close> operations that Producer does on the mel elements indicate to the other tasks in the program that Producer is done with the mel elements. These operations are extraneous if the mel elemnents are already closed by other tasks.

---

Mel AND Writes

While the mel OR writes allow writing into one of the listed mel elements, the mel AND writes are for writing to all of them. The AND mel write has several built-in methods to process the listed mel elements:

Mel AND Write Methods
Method Value	Description
Serial	The task writes to the mel elements serially based on the order in the AND list.
Parallel	This is the default method when no method is specified. The task makes a parallel attempt to write to all the mel elements in the AND list. The writes occur individually whenever a mel element is available for writing by this task.
InSimul	The task makes a parallel attempt to write to all the mel elements in the AND list. The writes occur simultaneously when all mel elements are available for writing by this task.

Serial AND Writes

To illustrate the mel AND write Serial method, let's first replace the Produce function with ProduceTwo which returns two values:

void Producer (<mel> int store1, <mel> int store2) {
  int c1, c2;
  while ( 1 ) {
    (c1, c2) = ProduceTwo();
    <? timeout> store1 = c1;
    <? timeout> store2 = c2;

    if ( !c1 || !c2 ) break;
  }
  <close>store1;
  <close>store2;
}

Once ProduceTwo generates the two products, they are stored in the local variables c1 and c2. The Producer task then writes the first product to the mel buffer store1. Once that successful, it writes the second product to the mel buffer store2. After both writes are done, Producer checks if any product is 0 which marks the end of the production; in that case, it breaks out of the while loop and lt;close> the mel buffers to signal to any reader tasks the end of production.

The above Producer code is now simplified with the mel AND write statement:

void Producer (<mel> int store1, <mel> int store2) {
  while ( 1 ) {
    try {
      <? timeout serial>(store1 && store2) = ProduceTwo() );

      if ( !store1<value> || !store2<value> ) break;
    }
    catch (store1 || store2)<TIMEDOUT as=store>) {
      printf ("Can't put into %s in time", store<name>);
      <resume> store;
    }
    catch (store1 || store2)<CLOSED as=store>) {
      printf ("%s has closed", store<name>);
      break;
    }
  }
  <close>store1;
  <close>store2;
}

The optional keyword method can be used if one desires to be explicit:

<? timeout method=serial>(store1 && store2) = ProduceTwo() );

Let's look at the behind-the-scene process of the Serial method for a mel AND write:

1. The Producer task runs ProduceTwo and generates two new items.
    
2. The Producer task puts itself to store1 default writers' queue with the default timeout value.
    
3. If the Producer cannot put its item into store1 buffer before the timeout, it aborts the mel wait on store1, exits the mel AND write, and triggers the TIMEDOUT exception on store1.
   
   The handler

   catch ( (store1 || store2)<TIMEDOUT as=store> )

   will pick up this exception. It printfs out a message then invokes <resume> to put itself back at the bottom of the store1 writers' queue to try to deposit the first produced item again.
    
4. If the mel WRITE conditions are met at store1 before the timeout, the Producer deposits the first produced item into the mel buffer, and drops out from that mel writers' queue. This allows other writer tasks to write to the mel element store1.
    
5. The Producer task now puts itself to store2 default writers' queue with the default timeout value.
    
6. If the Producer cannot put the second produced item into store2 buffer before the timeout, it aborts the mel wait on store2, exits the mel AND wait, and triggers the TIMEDOUT exception on store2.
   
   The handler

   catch ( (store1 || store2)<TIMEDOUT as=store> )

   picks up this exception. It printfs out a message then invokes <resume> operation. This operation knows that the first produced item has been successfully deposited in store1. It therefore puts the Producer task back to the store2 writers' queue (at the bottom position) to try to deposit the second produced item again.
    
7. If the mel WRITE conditions are met at store2 before the timeout, the Producer deposits the second produced item into the store2 mel buffer, and drops out from that mel writers' queue. This allows other writer tasks to write to the mel element store2.
 
8. The Producer task exits the mel AND write statement with both produced items deposited into the corresponding mel elements, one after the other as dictated by the Serial AND write method.
    
9. If the Producer task encounters a mel closure from any mel element during the mel waits, the CLOSED exception will be raised, and handled by:

   catch ( (store1 || store2)<CLOSED as=store> )

   This exception handler does a printf on the closing mel element and breaks out of the while loop.
   
   

   What would happen if a <resume> or continue were used instead of the break? The <resume> operation would clear all exceptions, including the CLOSED exceptions, retry the mel AND write on produced item that have not been written by sending a request to the remote mel elemnt(s), get back the piggy-backed status that the mel elements have been closed, jump into the CLOSED exception handler again, and keep repeating the same process, causing the Producer task to livelock -- i.e. to spin endlessly on the same produced items.
   
   The continue would also cause a livelock, but in a different way. This statement would not clear the exceptions, then cause the Producer to loop back to the while loop, ProduceTwo two new items, attempt to write them to the closed mel elements, detect locally that the mel elements already have the CLOSED status, replace the sending a write request to the remote mel elements with the jump into the CLOSED exception handler. This spinning is then repeated endlessly, each time producing and discarding two new products.

In summary, the Serial method for mel AND writes is just a more compact way to write the one-at-a-time program.

---

Parallel AND Writes

Let's now change Producer again so that it still add the products of ProduceTwo to both mel buffers, but we will remove the requirement that the additions to be done at the same time. Instead, they will be added at the same time. This AND write method is therefore referred to as the Parallel method:

void Producer (<mel> int store1, <mel> int store2) {
  while ( 1 ) {
    try {
      <?>(store1 && store2) = ProduceTwo() );

      if ( !store1<value> || !store2<value> ) break;
    }
    catch (store1 || store2)<TIMEDOUT as=store>) {
      printf ("Can't put into %s in time", store<name>);
      <resume> store;
    }
    catch (store1 || store2)<CLOSED as=store>) {
      printf ("%s has closed", store<name>);
      break;
    }
  }
  <close>store1;
  <close>store2;
}

The Parallel method is the default method for the mel AND write, and is assumed when no method is requested, as in the example above. A programmer can choose to be explicit:

<? timeout method=parallel>(store1 && store2) = ProduceTwo() );
Like always, the keyword method can be omitted:
<? timeout parallel>(store1 && store2) = ProduceTwo() );

This is the behind-the-scene processing for a mel AND write with the Parallel method:

The Producer task runs ProduceTwo and generates two new items.

 
The Producer task puts itself to both store1 and store2 writers' queues.

 
Whenever the mel WRITE conditions are satisfied for one mel element, Producer will deposit the corresponding product into that mel buffer, and removes itself from that mel writers' queue.

 
Whenever the mel WRITE conditions are satisfied on the remaining mel element, Producer will do the same thing as above for this mel element.

 
If the mel WRITE conditions are not satisfied in time for one of the mel queues, the Producer task will get off the mel queue, and jumps into the handler
catch ( (store1 || store2)<TIMEDOUT as=store> )
It printfs out a message then invokes <resume> on that mel element. This operation will clear the exception on that mel element, puts the Producer task back at the bottom of that writers' queue to attempt to deposit the correspondent product again.

 



Once the Producer task has both products successfully written into their corresponding mel buffers, it gets off the mel AND write statement.

 
If while waiting in one mel element queue, the Producer task may get timed out in one (or both)


The randomness with the mel LIST write is that we don't know which mel buffer is written to first. If the order is important, then the Producer code must be explicit:


void Producer (<mel> int store1, <mel> int store2) {
     int c1, c2;
     while ( 1 ) {
          if ( (c1, c2) = ProduceTwo() ) break;
          /* Write to store1 then store2 */
          <?>store1 = c1;
          <?>store2 = c2;
     }
     <close>store1;
     <close>store2;
}









InSimul AND Writes





A mel AND write is used when a programmer wants both store1 and store2 to be written to at the same time. Let's now change Producer so that it calls a function ProduceTwo which returns two values. These values will be respectively inserted to store1 and store2 mel buffers at the same time.


void Producer (<mel> int store1, <mel> int store2) {
     while ( <?>(store1 && store2) = ProduceTwo() );
     <close>store1;
     <close>store2;
}


For example, we can think of a gaming program where a launching of nuclear missile requires a squeeze on a trigger and a press of a button to be received simultaneously. Of course for this program to work, the mel variables that represent the trigger and the button ought to be of buffer size 1, since it would be meaningless to buffer such requests.




The mel AND write operation behaves similarly to a mel AND read to prevent deadlocks in case of multiple tasks accessing the same mels for writing. The difference is that instead of waiting for a mel to be valued, a writer task waits for a mel to have an available slot at the mel buffer writer's end so it can deposit its product into. If the buffer is of size greater than 1, it is easier to satisfy a mel AND write than a mel AND read.




This is the behind-the-scene processing for a mel AND write:

The task puts itself in both mel writer's queues.

 
In due course, the task will be at the first position of one the mel writers' queues and joins the "top-of-the-queue" writers group of that queue. It then checks if it is also in the "top-of-the-queue" group at the other mel writer's queue. If it is not, it will wait for it to join the "top-of-the-queue" group at the other writers' queue.

 
While waiting in only one of the "top-of-the-queue" group, if another writer task comes along on that writers' queue, the task will allow that later-coming task to "jump the line" and deposit its value to an available empty buffer slot if there is one.

 
Eventually the task will be in the "top-of-the-queue" groups at both mel writers' queues. It will keep checking for empty slots at both mel buffers. If none is available, it will wait. If only one buffer is available, it will wait, but this time, it will not allow any later-coming writer task, that is not in the "top-of-the-queue" group, to "jump the line" and fill that available buffer slot.

 
Eventually the task will find empty slots at both mel buffers. It will then fill the mel buffer slots with its products, increases the sequence number of both mel variables, removes itself from both writers' queues, and gets off the mel AND write.





There can be more than one task in a "top-of-the-queue" group. This group is reserved for tasks that are doing AND writes. When a task doing an AND write moves up to the first position in a writers' queue, it may not find all the conditions for a successful AND write at that moment. Instead of relinquishing the first position in the queue, it joins the "top-of-the-queue" group, and bides its wait there.




For example, we have a task T1 that does an AND write on mel resource R1 and R2. T1 is in the "top-of-the-queue" group on R2 but not yet on R1. Then a task T2 comes along and does a normal write on R2. If there is mel buffer slot available, T1 will allow T2 to "jump the line" and fills that slot. Eventually, T1 is in the "top-of-the-queue" groups of both R1 and R2. However one or both mel buffers are still full, so T1 waits. When the cyclic T2 comes back for another product deposit run, it cannot "jump the line" this time. It has to wait. The next available empty slot is already reserved to T1 since T1 has achieved the "top-of-the-queue" condition at both queues, and now needs the "available mel buffer slot" condition in order to fulfill its AND write.




Let's keep the above example but add a task T3 that does an AND write on resource R2 and R3. When T3 gets to the first position on R2 but not on R3, it will join T1 in the "top-of-the-queue" group of R2. Now if R2 becomes available, the CHAOS runtime automatically assigns it to T1 and not T3 since the former has attained "top-of-the-queue" in all the mels in the AND list, and not the latter.




Eventually T3 also joins the "top-of-the-queue" group of R3, and has achieved "top-of-the-queue" in all the mels in its AND list. Now if R2 becomes available, CHAOS will also give that slot to T1 because it has joined the "top-of-the-queue" group of R2 before T3. T1 now can satisfy all its AND write conditions, deposits its products and gets off both writers' queues. T3 has to wait for the next empty slot from R2 to go with the R3 slot it already has, before it can exit its AND write. The task T2 that is waiting for both T1 and T3 to be done with R2, can now access the next empty slot from R2.











Previous
Next
Top

A Tour Of Go Language

Welcome » NERWous C » Examples

1. Go Concurrency
2. Fibonacci Example
3. Mutex Example

---

Go Concurrency

The Go language is an open-source programming language created by Google in 2009. It supports concurrency via Goroutines and channels. The NERWous C equivalents are pel constructs, and mel entities.

---

Fibonacci Example

The Fibonacci sequence appears frequently in mathematics, computer algorithms, and biology settings.

Go Implementation:

The Go language Fibonacci example displays the first 10 Fibonacci numbers (i.e. 0, 1, 1, 2, 3, 5, 8, 13, 21,34). This implementation is copied from the Tour Of Go tutorial:

package main
import (
 "fmt"
)
func fibonacci(n int, c chan int) {
 x, y := 0, 1
 for i := 0; i < n; i++ {
  c <- x
  x, y = y, x+y
 }
 close(c)
}

func main() {
 c := make(chan int, 10)
 go fibonacci(cap(c), c)
 for i := range c {
  fmt.Println(i)
 }
}

The Go example has main creating the channel c then forking a light-threaded task via the go command to run the fibonacci function in concurrency. The fibonacci task feeds the channel c whenever it has computed the next number for the sequence. The main task waits on the channel c for any new value to show it on the console via the Println command.

NERWous C Implementations:

We will do several versions of the NERWous C implementations to illustrate different features of the language.

Version 1:
Version 1 follows closely the Go implementation by replacing the Goroutine and Go channel with the pel and mel constructs of NERWous C:

/* VERSION 1 */
void main () {
  <mel> int c;
  <!> fibonacci (10, c);
  for (int i=0; i<10; ++i)
    printf ("%d", <?>c);
}
int fibonacci (int n, mel int c) {
  int x = 0, y = 1;
  for (int i = 0; i < n; ++i ) {
    <?>c = x;
    x = y; y = x + y;
  }
  <close>c;
}

The mel variable c is shared between the main task and the fibonacci task. The main task is the reader and the fibonacci the writer. When main tries to read out from the mel c and the fibonacci has not generated a value for it, main will wait at the mel wait operator <?>. When the mel channel c is filled, main reads out that value and makes the mel c empty again.

The fibonacci task needs the mel channel c to be empty so that it can deposit the x value. If the reader main is slow in removing the previous value, the fibonacci writer has to wait at the mel wait operator <?>.

Although the main and fibonacci tasks run in concurrency, they work in lock step due to the synchronizing chock point at the mel channel c. To possibly increase the concurrency, we can add buffering to the mel c:

<mel buffer=10> int c;

Version 2:
In the second version, we will drop the mel variable c and use the return value of the pel task as the communication channel.

/* VERSION 2 */
void main () {
  <pel> p = <!>fibonacci (10);
  for (int i=0; i<10; ++i)
    printf ("%d", <?>p);
}
int fibonacci (int n) {
  int x = 0, y = 1;
  for (int i = 0; i < n; ++i ) {
    <release> x;
    x = y; y = x + y;
  }
}

The return value of a pel task is a read-only mel. Via the <release> statement, the pelled task "streams" values to any task that is waiting on that return value channel. Unlike Version 1 where the main task depends on the mel entity to be filled, the main task in Version 2 uses the sequence number to make sure it does not process stale values.

Version 3:
The third version builds on the second version by having the main task keeps checking the released value of the fibonacci task until this task ends itself.

/* VERSION 3 */
void main () {
  <pel> p = <!> fibonacci (10);
  while ( 1 ) {
    try { printf ("%d", <?>p); }
    catch (p<ENDED>) break;
  }
}
int fibonacci (int n) {
  int x = 0, y = 1;
  for (int i = 0; i < n; ++i ) {
    <release> x;
    x = y; y = x + y;
  }
}

When the fibonacci task runs off its last statement, it will end itself. This triggers the ENDED exception at the main task which uses it to break out of the infinite while ( 1 ) loop.

---

Mutex Example

The Go language support the concept of a mutex for mutual exclusive access to shared data. A Go language block of code can be executed in mutual exclusion by being surrounding with a Lock and Unlock calls.

Go Implementation:

The Go implementation is taken from Tour of Go tutorial:

package main

import (
 "fmt"
 "sync"
 "time"
)

// SafeCounter is safe to use concurrently.
type SafeCounter struct {
 v   map[string]int
 mux sync.Mutex
}

// Inc increments the counter for the given key.
func (c *SafeCounter) Inc(key string) {
 c.mux.Lock()
 // Lock so only one goroutine at a time can access the map c.v.
 c.v[key]++
 c.mux.Unlock()
}

// Value returns the current value of the counter for the given key.
func (c *SafeCounter) Value(key string) int {
 c.mux.Lock()
 // Lock so only one goroutine at a time can access the map c.v.
 defer c.mux.Unlock()
 return c.v[key]
}

func main() {
 c := SafeCounter{v: make(map[string]int)}
 for i := 0; i < 1000; i++ {
  go c.Inc("somekey")
 }

 time.Sleep(time.Second)
 fmt.Println(c.Value("somekey"))
}

NERWous C Implementations:

NERWous C is the NERW Concurrency Model grafted on the C language, and the C language does not have native support for map nor string. The following NERWous C language implementations make use of a simple array with integer as index. This will not diminish the discussion on Mutex which is the focus here.

Version 1:

/* VERSION 1 */
#include "keys.h"
<mel>int SafeCounter[NUMKEYS];

void Inc (int somekey) {
   <?>SafeCounter[somekey] {
      SafeCounter[somekey]++;
      <checkout replace>;
   }
}

void main () {
   for (int i=0; i<NUMKEYS; ++i)
      <?>SafeCounter[i] = 0;

   int somekey = random(0, NUMKEYS);
   for (int i=0; i<1000; ++i) {
      <!>Inc (somekey);
   }
   sleep (1000);
   printf ("%d", <?>SafeCounter[somekey]);
}

In the first version, we first declare SafeCounter as a global mel array that can contain NUMKEYS items. The value of NUMKEYS come from the include file keys.h.

The main task runs a serial loop to initialize to 0 each of the item of SafeCounter. It then generates a random number between 0 inclusive and NUMKEYS exclusive via a custom function random (which we do not show the implementation). The main task then runs a second serial loop for 1000 iterations. In each iteration, it forks a new task via the pel construct to run the Inc function in parallel.

Inside the Inc function, the deceptively simple auto-increment means a read of the value of the mel entity SafeCounter[somekey], increment that value, and write that value back to the mel entity. Since the read and write must be atomic, all the mentioned operations must be inside a mel reader zone for mutual exclusion. When an Inc task is in the exclusive zone, all the other Inc tasks that needs access to the same SafeCounter[somekey] entity, must queue up in that entity's queue.

The first Inc task that comes to the reader zone can see that the conditions to get into the zone are satisfied. These conditions are the mel entity is valued and that value is not stale. These conditions are made satisfactory by the main task when it initializes all the items in the SafeCounter array to zero.

After doing the auto-increment using the local eponymous variable SafeCount[somekey], the Inc task writes back that value to the shared mel entity via the <checkout replace> operation. Without the replace attribute, the default checkout behavior is to remove the value from the mel entity. This would cause all the waiting Inc tasks to wait forever since there is no new writer task to deposit a fresh value to the mel entity to satisfy the reader zone entry condition.

Back to the main task, we see that it wants to display the final value of SafeCount[somekey]. Since it does not know when all the pelled Inc tasks will all finish, it sleeps for 1 empirical second. To access the mel value at that time, the main task just use the mel read statement <?>SafeCounter[somekey]. There is no need for using a mel read exclusive zone since a NERWous C mel read natively enforces mutual exclusion.

Version 2:
Let's revise the above implementation. Since NERWous C supports inline code blocks, we can drop the Inc function and move its work inside the main task:

/* VERSION 2 */
#include "keys.h"
<mel>int SafeCounter[NUMKEYS];

void main () {
   for (int i=0; i<NUMKEYS; ++i)
      <?>SafeCounter[i] = 0;

   int somekey = random(0, NUMKEYS);
   for (int i=0; i<1000; ++i) {
      <!> <?>SafeCounter[somekey] {
      SafeCounter[somekey]++;
      <checkout replace>;
      }
   }
   sleep (1000);
   printf ("%d", <?>SafeCounter[somekey]);
}

Version 3:
Since auto-increment (and decrement) are frequently used operations, NERWous C supports shortcuts that skip mentioning the explicit use of the mel read zone:

/* VERSION 3 */
#include "keys.h"
<mel>int SafeCounter[NUMKEYS];

void main () {
   for (int i=0; i<NUMKEYS; ++i)
      <?>SafeCounter[i] = 0;

   int somekey = random(0, NUMKEYS);
   for (int i=0; i<1000; ++i)
      <!> <?>SafeCounter[somekey]++;

   sleep (1000);
   printf ("%d", <?>SafeCounter[somekey]);
}

Version 2 and 3 are the same. In both Versions, the mel entity is replaced in place, thus preserving its sequence number. The next task that accesses the mel entity will see a new value but the same sequence number. Sequence numbers are used to prevent re-processing of stale values. This is not an issue with the Mutex example here, since each pelled task that does the auto-increment goes through the SafeCounter[somekey] mel entity once and does not do loops. Loops are where stale values can be encountered.

Version 4:
In the previous versions, we have a sleep operation because we want to display the final value of SafeCounter[somekey], but since the auto-increment tasks run in parallel, we don't know when they all finish. The one second is an empirical value that seems to work in the running environment. (If it does not, just increment it until it does.) NERWous C supports a pel-for loop that allows us to remove the sleep operation:

/* VERSION 4 */
#include "keys.h"
<mel>int SafeCounter[NUMKEYS];

void main () {
   for (int i=0; i<NUMKEYS; ++i)
      <?>SafeCounter[i] = 0;

   int somekey = random(0, NUMKEYS);
   <begin> { for (int i=0; i<1000; ++i)
      <!> <?>SafeCounter[somekey]++;
   } <? ENDED>;

   printf ("%d", <?>SafeCounter[somekey]);
}

Encapsulating the for loop inside the begin-wait-ended block ensures that all pelled tasks in the for loop have ended before the programming flow continues. When main issues the printf command in Version 4, it is assured that all auto-increment tasks are done and the mel entity SafeCounter[somekey] contains the final value.

Version 5 (Serial):
There is no NERWous C Version 5. Version 4 is as compact as it can be. However notice that if we strip out the NERWous C pel and mel constructs, we end up with the correspondent C program:

/* VERSION 5(Serial)  */
#include "keys.h"
int SafeCounter[NUMKEYS];

void main () {
   for (int i=0; i<NUMKEYS; ++i)
      SafeCounter[i] = 0;

   int somekey = random(0, NUMKEYS);
   for (int i=0; i<1000; ++i)
      SafeCounter[somekey]++;

   printf ("%d", SafeCounter[somekey]);
}

Sometimes, with NERWous C, by sprinkling some <?> and <!> here and there, we transform a serial program into a concurrent program without much ado.

---

Previous Next Top