Advanced Programming Techniques for MVC

Process Coordination

The most elementary form of process coordination uses Semaphores. A semaphore is a structure that administrates permissions to continue the execution of a process. It can

• store received permissions that are not immediately used
• queue processes that ask for a permission that is not immediately available.

  | sema block1 block2 |

 sema := Semaphore new.
 block1 := 
   ["sequence of statments"
    sema wait.
    "sequence of statments"].
 block2 := 
   ["sequence of statments"
    sema signal.
    "sequence of statments"].
 block1 forkAt: Processor userBackgroundPriority.
 block2 forkAt: Processor userBackgroundPriority.

This example creates two processes that can run independently until the process that evaluates the statements in block1 asks for a permission to continue. This is done with the statement sema wait. The process that evaluates the statements in block2 grants that permission when it evaluates the statement sema signal.

Synchronization involves exactly two processes:

• one that asks for the permission to continue process execution
• one that grants the permission to continue process execution.

This example may leave you with the impression that Semaphores are a complication that does not solve a problem. To show how semaphores are used to solve a problem, we need a more detailed example. Here it is:

 | block1 block2 
  permissionToWrite permissionToRead
  aboutToTerminate 
  sharedVariable oc |

  permissionToWrite := Semaphore new.
  permissionToRead := Semaphore new.
  aboutToTerminate := Semaphore new.
  
  permissionToWrite signal.
  oc := OrderedCollection new.
  
  block1 :=
    [ 1 to: 100 do:
         [:idx |
            permissionToWrite wait.
            sharedVariable := idx * idx.
            permissionToRead signal
          ].
      aboutToTerminate signal.
    ].

 block2 :=
  [ 1 to: 100 do:
       [:idx2 |
          permissionToRead wait.
          oc add: sharedVariable.
          permissionToWrite signal
       ].
    aboutToTerminate signal.
  ].

 block1 forkAt: Processor userBackgroundPriority.
 block2 forkAt: Processor userBackgroundPriority.

  aboutToTerminate wait;
                   wait.
  oc inspect.

Explanations

In this example we have two processes that use a single shared variable to exchange a sequence of values.

• The process that is forked from block1 computes 100 numbers. When it obtains the permission to write into the shared variable, it assigns a value and grants a read permission for the variable.

• The process that is forked from block2 collects 100 numbers that it fetches from the shared variable. Before it fetches a value, it askes for the permission to read the value of the shared variable. As soon as it has fetched that value, it grants a permission to write into the shared variable.

• The semaphore permissionToWrite is signalled once before the processes are forked. The statement

  permissionToWrite signal.

  
  creates one permission to write into the shared variable.

• The process that forks the two processes has also the responsibility to open an inspector for the final result.

• The counter variable of block1 is named idx, that of block2 is named idx2. For Squeak, it is essential to use different names. The reason is that block variables in Squeak are not really local: The compiler moves all block variables into the method that provides the evaluation environment of the block.

Cooperation is implemented by exchange of permissions. The writing process grants a read permission after it has assigned a value to the shared variable. The reading process grants a write permission after it has fetched the current value of the shared variable. Both processes ask for permission to access the shared variable. It can therefore not happen

• that the reading process reads the shared variable before it was assigned a new value
• that the writing process assigns a new value to the shared variable before the current values was read.

For the termination of both processes it is crucial that the repetition statements in both processes are evaluated the same number of times.

• When block1 terminates after 99 iterations, the process of block2 will wait for a read permission that it will never obtain.
• When block2 terminates after 99 iterations, the process of block1 will wait for a write permission that it will never obtain.
• In both cases, the parent process will never obtain two permissions to continue

There are two different to ensure that the number of repetitions is the same in both processes.:

• Both cooperating processes evaluate the same stop condition independently but in a manner that ensures consistent results for both processes.

• One of the processes evaluates the stop condition and communicates the evaluated value to the other process.

Independent evaluation of the same stop condition in two processes:

 | block1 block2 
  permissionToWrite permissionToRead
  aboutToTerminate 
  sharedVariable oc |

  permissionToWrite := Semaphore new.
  permissionToRead := Semaphore new.
  aboutToTerminate := Semaphore new.
  
  permissionToWrite signal.
  oc := OrderedCollection new.
  
  block1 :=
    [  | idx square |
      idx := 1.
      [square := idx * idx.
       permissionToWrite wait.
       sharedVariable := square.
       permissionToRead signal.
       square < 100000
      ]
        whileTrue:
           [idx := idx + 1].
     aboutToTerminate signal.
    ].

  block2 :=
    [[permissionToRead wait.
      oc add: sharedVariable.
      permissionToWrite signal.
      oc last < 100000
     ]
       whileTrue.
     aboutToTerminate signal
    ].

  block1 forkAt: Processor userBackgroundPriority.
  block2 forkAt: Processor userBackgroundPriority.

  aboutToTerminate wait;
                   wait.
  oc inspect.

Evaluation of the stop condition in one process and communication of the result to the other process. This solution requires an additonal shared variable. Note also that the process block2 cannot reliably use the value of the shared variable continue after it has given a write permission for that variable. The process has to copy the value for later use.

 | block1 block2 
  permissionToWrite permissionToRead
  aboutToTerminate 
  sharedVariable continue oc |

  permissionToWrite := Semaphore new.
  permissionToRead := Semaphore new.
  aboutToTerminate := Semaphore new.
  
  permissionToWrite signal.
  oc := OrderedCollection new.
  
  block1 :=
    [  | idx square |
      idx := 1.
      [square := idx * idx.
       permissionToWrite wait.
       sharedVariable := square.
       continue := square < 100000.
       permissionToRead signal.
       continue
      ]
        whileTrue:
           [idx := idx + 1].
     aboutToTerminate signal.
    ].

  block2 :=
    [[ | mayContinue |
      permissionToRead wait.
      oc add: sharedVariable.
      mayContinue := continue.
      permissionToWrite signal.
      mayContinue
     ]
       whileTrue.
     aboutToTerminate signal
    ].

  block1 forkAt: Processor userBackgroundPriority.
  block2 forkAt: Processor userBackgroundPriority.

  aboutToTerminate wait;
                   wait.
  oc inspect.