  
  [1X8 Background jobs using fork[0X
  
  This  chapter  describes a way to use multi-processor or multi-core machines
  from  within [5XGAP[0m. In its current version the [5XGAP[0m system is a single threaded
  and  single process system. However, modern operating systems allow, via the
  [10Xfork[0m  system  call,  to  replicate  a  complete  process on the same machine
  relatively  efficiently.  That  is,  at first after a [10Xfork[0m the two processes
  actually use the same physical memory such that not much copying needs to be
  done.  The child process is in exactly the same state as the parent process,
  sharing  open  files,  network  connections  and  the complete status of the
  workspace.  However,  whenever  a  page  of  memory  is  written, it is then
  automatically  copied  using  new,  additional physical memory, such that it
  behaves   like   a  completely  separate  process.  This  method  is  called
  "copy-on-write".
  
  Thus  this  is  a  method to parallelise certain computations. Note however,
  that  from  the  point  of  time  when  the  [10Xfork[0m  has occurred, all further
  communication between the two processes has to be realised via pipes or even
  files.
  
  The operations and methods described in this chapter help to use [5XGAP[0m in this
  way  and implement certain "skeletons" of parallel programming to make these
  readily  available  in  [5XGAP[0m.  Note  that  this implementation has its severe
  limitations   and  should  probably  eventually  be  replaced  by  a  proper
  multi-threaded version of [5XGAP[0m.
  
  
  [1X8.1 Background jobs[0X
  
  One creates a background job with the following operation:
  
  [1X8.1-1 BackgroundJobByFork[0m
  
  [2X> BackgroundJobByFork( [0X[3Xfun, args[, opt][0X[2X ) _________________________[0Xoperation
  [6XReturns:[0X  a background job object or [9Xfail[0m
  
  This  operation creates a background job using [2XIO_fork[0m ([14X3.2-19[0m) which starts
  up  as an identical copy of the currently running [5XGAP[0m process. In this child
  process  the  function  [3Xfun[0m is called with the argument list [3Xargs[0m. The third
  argument  [3Xopt[0m  must be a record for options. The operation returns either an
  object representing the background job or [9Xfail[0m if the startup did not work.
  
  This  operation  automatically  sets up two pipes for communication with the
  child  process.  This  is  in  particular  used  to report the result of the
  function  call  to  [3Xfun[0m  back  to the parent. However, if called without the
  option  [10XTerminateImmediately[0m  (see below) the child process stays alive even
  after  the  completion  of [3Xfun[0m and one can submit further argument lists for
  subsequent  calls  to  [3Xfun[0m.  Of course, these additional argument lists will
  have  to  be sent over a pipe to the child process. A special case is if the
  argument  [3Xargs[0m  is  equal to [9Xfail[0m, in this case the child process is started
  but  does not automatically call [3Xfun[0m but rather waits in an idle state until
  an  argument  list  is  submitted  via  the  pipe  using  the [2XSubmit[0m ([14X8.1-6[0m)
  operation described below.
  
  There  are  two  components defined which can be bound in the options record
  [3Xopt[0m.  One  is  [10XTerminateImmediately[0m, if this is bound to [9Xtrue[0m then the child
  process immediately terminates after the function [3Xfun[0m returns its result. In
  this  case,  no pipe for communication from parent to child is created since
  it  would never be used. Note that in this case one can still get the result
  of the function [3Xfun[0m using the [2XPickup[0m ([14X8.1-5[0m) operation described below, even
  when the child has already terminated, since the result is first transmitted
  back to the parent before termination.
  
  The following operations are available to deal with background job objects:
  
  [1X8.1-2 IsIdle[0m
  
  [2X> IsIdle( [0X[3Xjob[0X[2X ) ___________________________________________________[0Xoperation
  [6XReturns:[0X  [9Xtrue[0m, [9Xfalse[0m or [9Xfail[0m
  
  This  operation  checks whether or not the background job represented by the
  object [3Xjob[0m has already finished the function call to its worker function and
  is  now idle. If so, [9Xtrue[0m is returned. If it is still running and working on
  the  worker  function,  [9Xfalse[0m is returned. If the background job has already
  terminated  altogether,  this  operation  returns [9Xfail[0m. Note that if a child
  process  terminates  automatically  after the first completion of its worker
  function  and  sending  the  result,  then  the  first  call to [2XIsIdle[0m after
  completion  will  return  [9Xtrue[0m  to  indicate  successful  completion and all
  subsequent calls will return [9Xfail[0m.
  
  [1X8.1-3 HasTerminated[0m
  
  [2X> HasTerminated( [0X[3Xjob[0X[2X ) ____________________________________________[0Xoperation
  [6XReturns:[0X  [9Xtrue[0m or [9Xfalse[0m
  
  This  operation  checks whether or not the background job represented by the
  object [3Xjob[0m has already terminated. If so, [9Xtrue[0m is returned, if not, [9Xfalse[0m is
  returned.
  
  [1X8.1-4 WaitUntilIdle[0m
  
  [2X> WaitUntilIdle( [0X[3Xjob[0X[2X ) ____________________________________________[0Xoperation
  [6XReturns:[0X  the result of the worker function or [9Xfail[0m
  
  This operation waits until the worker function of the background job [3Xjob[0m has
  finished  and  the  job  is  idle.  It then returns the result of the worker
  function, which has automatically been transmitted to the parent process. If
  the child process has died before completion [9Xfail[0m is returned.
  
  [1X8.1-5 Pickup[0m
  
  [2X> Pickup( [0X[3Xjob[0X[2X ) ___________________________________________________[0Xoperation
  [6XReturns:[0X  the result of the worker function or [9Xfail[0m
  
  This operation does the same as [2XWaitUntilIdle[0m ([14X8.1-4[0m).
  
  [1X8.1-6 Submit[0m
  
  [2X> Submit( [0X[3Xjob, args[0X[2X ) _____________________________________________[0Xoperation
  [6XReturns:[0X  [9Xtrue[0m or [9Xfail[0m
  
  This  submits  another  argument  list  [3Xargs[0m  for another call to the worker
  function  in the background job [3Xjob[0m. It is an error if either the background
  job  has  already  terminated or if it is still busy working on the previous
  argument list. That is, one must only submit another argument in a situation
  when [2XIsIdle[0m ([14X8.1-2[0m) would return [9Xtrue[0m. This is for example the case directly
  after  a  successful call to [2XPickup[0m ([14X8.1-5[0m) or i [2XWaitUntilIdle[0m ([14X8.1-4[0m) which
  did  not  return  [9Xfail[0m,  unless  the  background  job  was  created with the
  [10XTerminateImmediately[0m option set to [9Xtrue[0m.
  
  This  operation  returns immediately after submission, when the new argument
  list  has  been  sent to the child process through a pipe. In particular, it
  does not await completion of the worker function for the new argument list.
  
  [1X8.1-7 Kill[0m
  
  [2X> Kill( [0X[3Xjob[0X[2X ) _____________________________________________________[0Xoperation
  [6XReturns:[0X  nothing
  
  This  kills  the background job represented by the object [3Xjob[0m with immediate
  effect.  No  more  results can be expected from it. Note that unless one has
  created  the background job with the [10XTerminateImmediately[0m option set to [9Xtrue[0m
  one  always  has  to  call  [2XKill[0m  on a background job eventually for cleanup
  purposes.  Otherwise,  the  background  job  and the connecting pipes remain
  alive until the parent [5XGAP[0m process terminates.
  
  
  [1X8.2 Parallel programming skeletons[0X
  
  In  this section we document the operations for the available skeletons. For
  a general description of these ideas see other sources.
  
  [1X8.2-1 ParTakeFirstResultByFork[0m
  
  [2X> ParTakeFirstResultByFork( [0X[3Xjobs, args[, opt][0X[2X ) ___________________[0Xoperation
  [6XReturns:[0X  a list of results or [9Xfail[0m
  
  The  argument  [3Xjobs[0m  must be a list of [5XGAP[0m functions and the argument [3Xargs[0m a
  list  of  the  same  length  containing  argument  lists  with which the job
  functions  can  be  called.  This operation starts up a background job using
  [10Xfork[0m  for  each  of  the  functions in [3Xjobs[0m, calls it with the corresponding
  argument list in [3Xargs[0m. As soon as any of the background jobs finishes with a
  result,  [2XParTakeFirstResultByFork[0m  terminates all other jobs and reports the
  results  found  so far. Note that it can happen that two jobs finish "at the
  same time" in the sense that both results are received before all other jobs
  could  be  terminated. Therefore the result of [2XParTakeFirstResultByFork[0m is a
  list,  in  which  position i is bound if and only if job number i returned a
  result. So in the result at least one entry is bound but it is possible that
  more than one entry is bound.
  
  You  can  specify  an overall timeout to give up the whole computation if no
  job  finishes by setting the [10XTimeOut[0m component of the options record [3Xopt[0m. In
  this  case  you  have  to  set it to a record with two components [10Xtv_sec[0m and
  [10Xtv_usec[0m which are seconds and microseconds respectively, exactly as returned
  by  the  [2XIO_gettimeofday[0m  ([14X3.2-27[0m) function. In the case of timeout an empty
  list is returned.
  
  [1X8.2-2 ParDoByFork[0m
  
  [2X> ParDoByFork( [0X[3Xjobs, args[, opt][0X[2X ) ________________________________[0Xoperation
  [6XReturns:[0X  a list of results or [9Xfail[0m
  
  The  argument  [3Xjobs[0m  must be a list of [5XGAP[0m functions and the argument [3Xargs[0m a
  list  of  the  same  length  containing  argument  lists  with which the job
  functions  can  be  called.  This operation starts up a background job using
  [10Xfork[0m  for  each  of  the  functions in [3Xjobs[0m, calls it with the corresponding
  argument  list  in [3Xargs[0m. As soon as all of the background jobs finish with a
  result,  [2XParDoByFork[0m  reports  the  results  found.  Therefore the result of
  [2XParDoByFork[0m  is  a list, in which position i is bound to the result that job
  number i returned.
  
  You  can specify an overall timeout to stop the whole computation if not all
  jobs  finish  in time by setting the [10XTimeOut[0m component of the options record
  [3Xopt[0m.  In this case you have to set it to a record with two components [10Xtv_sec[0m
  and  [10Xtv_usec[0m  which  are  seconds  and microseconds respectively, exactly as
  returned  by the [2XIO_gettimeofday[0m ([14X3.2-27[0m) function. In the case of timeout a
  list  is  returned  in  which the positions corresponding to those jobs that
  have  already  finished  are  bound  to the respective results and the other
  positions are unbound.
  
  [1X8.2-3 ParListByFork[0m
  
  [2X> ParListByFork( [0X[3Xl, worker[, opt][0X[2X ) _______________________________[0Xoperation
  [6XReturns:[0X  a list of results or [9Xfail[0m
  
  This  is  a  parallel  version  of  the  [2XList[0m ([14XReference: List[0m) function. It
  applies the function [3Xworker[0m to all elements of the list [3Xl[0m and returns a list
  containing  the  results in corresponding positions. You have to specify the
  component  [10XNumberJobs[0m  in  the  options  record [3Xopt[0m which indicates how many
  background  processes  to  start.  You can optionally use the [10XTimeOut[0m option
  exactly   as   for  [2XParDoByFork[0m  ([14X8.2-2[0m),  however,  if  a  timeout  occurs,
  [2XParListByFork[0m returns [9Xfail[0m.
  
  Note  that  the  usefulness  of  this operation is relatively limited, since
  every  individual  result  has  to  be  sent back over a pipe from the child
  process  to  the  parent  process.  Therefore  this  only makes sense if the
  computation time for the worker function dominates the communication time.
  
  [1X8.2-4 ParMapReduceByFork[0m
  
  [2X> ParMapReduceByFork( [0X[3Xl, map, reduce[, opt][0X[2X ) _____________________[0Xoperation
  [6XReturns:[0X  a value or [9Xfail[0m
  
  This  is  a  parallel  version  implementation  of  the  classical [10XMapReduce[0m
  pattern.  It applies the function [3Xmap[0m to all elements of the list [3Xl[0m and then
  reduces the result using the [3Xreduce[0m function which accepts two return values
  of  [3Xmap[0m  and returns one of them. Thus, the final result is one return value
  or  [9Xfail[0m if the startup of the jobs fails. You have to specify the component
  [10XNumberJobs[0m  in  the  options  record [3Xopt[0m which indicates how many background
  processes to start. You can optionally use the [10XTimeOut[0m option exactly as for
  [2XParDoByFork[0m  ([14X8.2-2[0m),  however,  if  a  timeout  occurs,  [2XParMapReduceByFork[0m
  returns [9Xfail[0m.
  
  Note  that  this  can  be  very  useful  because  quite  often the cumulated
  computation   time   for   all  the  worker  function  calls  dominates  the
  communication time for a single result.
  
  Note  that the next parallel skeleton is a worker farm which is described in
  the following section.
  
  
  [1X8.3 Worker farms[0X
  
  The  parallel  skeleton of a worker farm is basically nothing but a bunch of
  background  jobs  all  with the same worker function and all eagerly waiting
  for  work.  The  only  additional concepts needed are an input and an output
  queue. The input queue contains argument lists and the output queue pairs of
  argument lists and results.
  
  One creates a worker farm with the following operation:
  
  [1X8.3-1 ParWorkerFarmByFork[0m
  
  [2X> ParWorkerFarmByFork( [0X[3Xfun, opt[0X[2X ) _________________________________[0Xoperation
  [6XReturns:[0X  an object representing the worker farm or [9Xfail[0m
  
  This  operation  creates a worker farm with the worker function [3Xfun[0m and sets
  up  its  input and output queue. An object representing the farm is returned
  unless  not  all  jobs  could  be started up in which case [9Xfail[0m is returned.
  After  startup  all  background  jobs  in  the farm are idle. The only valid
  option  in  the options record [3Xopt[0m is [10XNumberJobs[0m and it must be bound to the
  number of worker jobs in the farm, a positive integer.
  
  The following operations are for worker farm objects:
  
  [1X8.3-2 DoQueues[0m
  
  [2X> DoQueues( [0X[3Xwf, block[0X[2X ) ___________________________________________[0Xoperation
  [6XReturns:[0X  nothing
  
  This operation called on a worker farm object [3Xwf[0m administrates the input and
  output  queues  of  the  worker  farm.  In  particular it checks whether new
  results  are  available  from  the  workers and if so it appends them to the
  output  queue.  If  jobs are idle and the input queue is non-empty, argument
  lists  from  the  input queue are sent to the idle jobs and removed from the
  input queue.
  
  This  operation  must  be called regularly to keep up the communication with
  the  clients.  It  uses [10Xselect[0m and so does not block if the boolean argument
  [3Xblock[0m  is  set to [9Xfalse[0m. However, if larger chunks of data has to be sent or
  received this operation might need some time to return.
  
  If  the boolean argument [3Xblock[0m is set to true then the [2XDoQueues[0m blocks until
  at  least  one  job  has returned a result. This can be used to wait for the
  termination  of  all tasks without burning CPU cycles in the parent job. One
  would  repeatedly  call  [2XDoQueues[0m with [3Xblock[0m set to [9Xtrue[0m and after each such
  call  check  with  [2XIsIdle[0m  ([14X8.3-4[0m) whether all tasks are done. Note that one
  should  no longer call [2XDoQueues[0m with [3Xblock[0m set to [9Xtrue[0m once this is the case
  since then it would block forever.
  
  This operation is called automatically by most of the following operations.
  
  [1X8.3-3 Kill[0m
  
  [2X> Kill( [0X[3Xwf[0X[2X ) ______________________________________________________[0Xoperation
  [6XReturns:[0X  nothing
  
  This  operation  terminates all background jobs in the farm [3Xwf[0m, which cannot
  be  used subsequently. One should always call this operation when the worker
  farm is no longer needed to free resources.
  
  [1X8.3-4 IsIdle[0m
  
  [2X> IsIdle( [0X[3Xwf[0X[2X ) ____________________________________________________[0Xoperation
  [6XReturns:[0X  [9Xtrue[0m or [9Xfalse[0m
  
  This operation returns [9Xtrue[0m if all background jobs in the worker farm [3Xwf[0m are
  idle.  This means, that all tasks which have previously been submitted using
  [2XSubmit[0m  ([14X8.3-5[0m)  have  been  completed and their result been appended to the
  output  queue. The operation [2XDoQueues[0m ([14X8.3-2[0m) is automatically called before
  the execution of [2XIsIdle[0m.
  
  [1X8.3-5 Submit[0m
  
  [2X> Submit( [0X[3Xwg, arglist[0X[2X ) ___________________________________________[0Xoperation
  [6XReturns:[0X  nothing
  
  This operation submits a task in the form of an argument list for the worker
  function  to  the worker farm. It is appended at the end of the input queue.
  The  operation  [2XDoQueues[0m ([14X8.3-2[0m) is automatically called after the execution
  of  [2XSubmit[0m,  giving  the  farm a chance to actually send the work out to the
  worker background jobs.
  
  [1X8.3-6 Pickup[0m
  
  [2X> Pickup( [0X[3Xwg, arglist[0X[2X ) ___________________________________________[0Xoperation
  [6XReturns:[0X  nothing
  
  This  operation  collects  all  results  from the output queue of the worker
  farm. The output queue is empty after this function returns. The results are
  reported  as a list of pairs, each pair has the input argument list as first
  component and the output object as second component.
  
  The  operation [2XDoQueues[0m ([14X8.3-2[0m) is automatically called before the execution
  of  [2XPickup[0m,  giving  the farm a chance to actually receive some more results
  from the worker background jobs.
  
