Case Study

 

This case study introduces the new BFPX language constructs. We will write "Hello world!" onto the program's output stream. The example serves to introduce parallel processes, process synchronisation and interprocess communication.


Our goal is to write a program where the mother process prepares a lowercase letter 'a' in memory cell 1. We use cell 1, because that is the cell that the writer process listens to for output. The mother process then forks processes to prepare and write individual letters. Special characters, such as the space, exclamation mark and finally the linefeed are written by the mother process.




   
++++++++++[>++++++++++<-]>---

{<+++[>--------<-]>-.}
{++++.}
{<+++[>+++<-]>++.}
{<+++[>+++<-]>++.}
{<++++[>+++<-]>++.}

{----------.}
{<++++[>+++<-]>++.}
{<++++[>++++<-]>+.}
{<+++[>+++<-]>++.}
{+++.}

[-]>++++++++[<++++>-]<.
+.
[-]++++++++++.http://www.kjkoster.org/download/case_study_1a.b


Each child process changes the value of cell 1 into that of their desired character and writes it out into the standard output stream.


Unfortunately, the output is not quite what we might have expected to see. In fact, running the program several times may even produce different results.


The order in which processes run is not specified. We simply created a bunch of processes that each write a character into the output stream, without putting some form of synchronisation mechanism in place to order the output. This results in a race condition, where several threads are competing to write to the standard output stream at the same time.


Brainfuck processes tend to live rather short in real life applications. They fork, do a little work and die. If your program accidentally relies on the order in which you defined your processes in the source code, it may even run well during initial tests. Please check your code for such race conditions.


Clearly, we need a mechanism to synchronise the processes we created. Channels are the standard synchronisation mechanism in brainfuck, so that we can control the order in which output is sent to the output stream. The code sample below demonstrates the use of channels to solve the race condition.


   
++++++++++[>++++++++++<-]>---

{<+++[>--------<-]>-  >>,<<.}
{++++                 >>>,<<<.}
{<+++[>+++<-]>++      >>>>,<<<<.}
{<+++[>+++<-]>++      >>>>>,<<<<<.}
{<++++[>+++<-]>++     >>>>>>,<<<<<<.}

{----------           >>>>>>>,<<<<<<<.}
{<++++[>+++<-]>++     >>>>>>>>,<<<<<<<<.}
{<++++[>++++<-]>+     >>>>>>>>>,<<<<<<<<<.}
{<+++[>+++<-]>++      >>>>>>>>>>,<<<<<<<<<<.}
{+++                  >>>>>>>>>>>,<<<<<<<<<<<.}

>>.>.>.>.>.           <<<<<<
[-]>++++++++[<++++>-] <.
>>>>>>>.>.>.>.>.      <<<<<<<<<<<
+.
[-]++++++++++.http://www.kjkoster.org/download/case_study_1b.b


In the revised implementation, the mother process passes a token value to each child process in order. Each child process prepares its letter as before, but waits to be passed a token before it writes the letter out to the standard output stream.


The actual value of the token is of no interest in this implementation. The channels are only used as a signalling medium.


In spite of our use of a synchronisation token, running this example still gives us an unexpected and unpredictable result.

The explanation is that although we have synchronised the moment that the child processes may start writing to the output, we have no check to ensure that the child process has actually finished writing its data into the output stream. The solution is of course to add a second layer of synchronisation, as shown in the code below.


   
++++++++++[>++++++++++<-]>---

{<+++[>--------<-]>-  >>,<<.                   >>,}
{++++                 >>>,<<<.                 >>>,}
{<+++[>+++<-]>++      >>>>,<<<<.               >>>>,}
{<+++[>+++<-]>++      >>>>>,<<<<<.             >>>>>,}
{<++++[>+++<-]>++     >>>>>>,<<<<<<.           >>>>>>,}

{----------           >>>>>>>,<<<<<<<.         >>>>>>>,}
{<++++[>+++<-]>++     >>>>>>>>,<<<<<<<<.       >>>>>>>>,}
{<++++[>++++<-]>+     >>>>>>>>>,<<<<<<<<<.     >>>>>>>>>,}
{<+++[>+++<-]>++      >>>>>>>>>>,<<<<<<<<<<.   >>>>>>>>>>,}
{+++                  >>>>>>>>>>>,<<<<<<<<<<<. >>>>>>>>>>>,}

>>..>..>..>..>..      <<<<<<
[-]>++++++++[<++++>-] <.
>>>>>>>..>..>..>..>.. <<<<<<<<<<<
+.
[-]++++++++++.http://www.kjkoster.org/download/case_study_1c.b


Running this code finally gives us the result we were looking for. Running the program several times will result in the same output each time. The double rendez-vouz on the channels guarantees this.

There is another solution to this race condition. We could have made the mother process responsible for all program output operations. Child processes pass their prepared bytes back to the mother process for output. This solution would have been more efficient in the sense that it reduces the amount of synchronisation. However, there is a trade-off. The bytes need to be moved into cell 1 for output. Implementing this solution is left as an exercise for the reader.
 
photo: Audrey Johnsonhttp://www.sxc.hu/profile/reuben4eva
if you find this interesting, terrible or just would like to know more, e-mail memailto:kjkoster@kjkoster.org?subject=
web statistics
http://java-monitor.com/