Think Stitch


Dynamic Creation of Processes 3: Multiple Instances of Child Processes

Consider general cases in which a process creates multiple instances of a process using the parallel composition par like fork.

A process P creates an instance of a process Q as a child process whenever an event c is received. Each instance of the process Q terminates as soon as getting the job done. We indicate the job done by Q with an event a.

(define-process P
  (! c
     (par '()
       P
       Q)))

(define-process Q
  (! a SKIP))

The next figure shows an example of computation trees of the process P. In this example, the process creates child processes five times, and all of them except the last one had already terminated.

As you can see, it troubles us a little bit. The nodes of terminated processes are not cleared until the parent process terminates. Since it is almost the same as resource leak, the system would eventually crash after a long use because of the exhaustion of resources.

As we have seen so far, if the child processes tend to terminate in the creation order, we can clear the nodes and fold the process tree using the sequential compositions. However, if the child processes terminate in arbitrary order, there is no way to clear the nodes of terminated processes which are placed at the nearer positions to the root of the process tree than nodes of the running child processes.

However, we have still some possibility to fold the process tree. When the process which is created most recently terminates, if there is a continuous chain of OMEGA nodes from there towards the root of the process tree, they could be folded at the time. In the example above, we could fold them when the Q terminates. Let's see how to achieve this.

The Way to Fold Process Trees

The points is that the parent process must terminate in order to fold the tree. However, since the parent process is the whole system itself, it cannot terminate, of course. Instead, we prepare an auxiliary process.

A Simple Case

At first we consider a simple case. Suppose we have a parent process P and an auxiliary process F in the initial situation.

When a request to create a child process occurs, the parent process P send the request to the process F.

The process F creates a child process in response to the request. We call it Q1. The process F continues its execution as one of the child processes using par like fork. We call the continuation F1.

When Q1 terminates, Q1 notify P of the termination.

The parent process P sends the termination request to F1 in response to the notification from Q1.

The process F terminates in response to the termination request from P. Since both Q1 and F1 terminates, the nodes are cleared and the system gets back to the initial situation.

A More General Case

Next, we consider a more general case. Suppose we have three child processes running, and the second instance Q2 is about to terminate.

The parent process P receives the termination notification from Q2, but P cannot terminate F2 because the process Q3 which is a child of F2 is still running. This situation tells us that the parent process P needs to manage which child runs and which child terminated in order to judge this kind of situations.

Suppose Q3 terminates next. As a result of the termination, a chain of continuous OMEGA nodes is formed on the tree from the leaf towards the root.

In this case, the parent process P sends the termination requests to Fs from the leaf side in turn. This folds the tree.

Modeling

Definitions of Events and Channels

Let N be the maximum number of child processes which can run simultaneously. We define events and channels as follows. Since child processes run concurrently, we need to prepare events of termination notifications for each child process. Instead of preparing events, we define channel q which takes an argument for process ID here. Each channel event of the channel q indicates the termination notification of the child process corresponding to the process ID.

(define N 5)
(define D (map list (interval 0 N)))

(define-event a)               ; request to create a child.
(define-event e)               ; request to terminate from P to F
(define-channel c (k) D)       ; request to create a child
                               ; from P to F with process ID k.
(define-channel q (k) D)       ; termination notification
                               ; from Q to P.

Child Process Q

All the child process Q does is to notify the parent process P of the termination. The other behaviors are abstracted away. When more than one child process can terminate, it is nondeterministically decided which termination notification is accepted by the parent process P.

(define-process (Q k)
  (! q (k) SKIP))

Process F

The process F has two roles: creating a child process and folding the process tree. The process F achieves these using the parallel compositions and the sequential compositions.

When F receives the termination request e from P, F just terminates via SKIP. This clears the corresponding nodes.

When F receives a request to create a child process through the channel c with a process ID k, F creates an instance of Q with k. Another child process in the parallel composition is the continuation of F and F itself is specified again. At the same time, the continuation process after the termination of the par is specified with the sequential composition seq. This continuation is also F itself. Though it seems to like a trick, it would be clear when you see the behavior of F on the computation tree later.

(define-process F
  (alt
    (? c (k)
       (seq
         (par '()
           (Q k)
           F)
         F))
    (! e SKIP)))

Process P

The process P has three process parameters to manage which child runs.

At first, the whole definition of P is shown. The alt form has three argument processes. We will see each of them in turn.

(define-process (P pst ps fs)
  (alt
    (! a
       (if (null? fs)
           (P pst ps fs)
           (let ((k (car fs)))
             (! c (k)
                (P (cons k pst) (cons k ps) (cdr fs))))))
    (? q (k)
       (P pst (remv k ps) fs))
    (if (and (not (null? pst))
             (not (memv (car pst) ps)))
        (! e
           (P (cdr pst) ps (cons (car pst) fs)))
        STOP)))

The first argument is a process for creating a child process. When an event a, a request to create a child process, is received, check if there is a free process ID or not. If there is no free ID, the request is ignored. If there is a free ID, k say, P sends the request to F through the channel c with k. After that, P updates pst, ps, and fs: k is added to pst and ps, and k is removed from fs.

    (! a
       (if (null? fs)
           (P pst ps fs)
           (let ((k (car fs)))
             (! c (k)
                (P (cons k pst) (cons k ps) (cdr fs))))))

The second argument processes the termination notifications from child processes. When a child process of process ID k terminates, P removes k from ps. pst and fs are not updated here.

    (? q (k)
       (P pst (remv k ps) fs))

The last argument processes the terminations of F. If pst is empty, there is no child process. Otherwise at least one child process is on the tree. (car pst) is the process ID which corresponds to the child process which is created most recently. If (car pst) is in ps, the corresponding child process is running. If (car pst) is not in ps, it is terminated. In this case, P sends a termination request e to F. When e is accepted by F, P removes the top element from pst and return it to ps.

The point of this definition is that this allows P to respond to requests a to create a child process and termination notifications q from the child processes even when P offers the termination request e to F. If P accepts a request a while offering an event e, a new node for the child process is put on the OMEGA node. This could be avoided if you write more code, but a simple code is selected here. This code is also an example of guarded process using if and STOP.

    (if (and (not (null? pst))
             (not (memv (car pst) ps)))
        (! e
           (P (cdr pst) ps (cons (car pst) fs)))
        STOP)))

System Process SYSTEM

The System process SYSTEM composed of P and F using par.

(define-process SYSTEM
  (par (list c q e)
    (P '() '() (interval 0 N))
    F))

Simulations

A Simple Case

Firstly we see a simple case in which a child process terminates as soon as it is created.

In response to a request a, P chooses a free process ID, namely 0, and sends the request through the channel c to F.

The process F creates a child process (Q 0). At this time, the nodes for seq and par are created. P registers process ID 0 to pst and ps.

The child process Q notifies P of the termination through the channel q with the process ID. The process P removes the process ID from ps in response to the notification.

The process Q terminates and the node becomes OMEGA.

The process P sends the termination request e to F because (car pst) = 0 is not in ps, which means the corresponding child process terminated. When the request is accepted, P removes the process ID 0 from pst and return it to fs.

If F terminates, the corresponding par terminates, and the node is folded. After that, the seq shifts to F. the node of the seq is also cleared.

A More General Case

The following figures show the situation in which three child processes are created and running. You can see that ps holds three process IDs. The Transitions list shows that every child process is ready to terminate.

This time we see the case in which (Q 1) terminates. The process P removes the process ID 1 from ps in response to the channel event q.1.

The child process (Q 1) terminates. The process P has nothing to do since (car pst) = 2 is in ps.

Suppose the child process (Q 2) terminates next. The process ID 2 is removed from ps. As a result, P offers the termination request e to F because (car pst) = 2 is no longer in ps. You can see that the event e is on the Transitions list in addition to the event a and the channel event q.0.

The child process (Q 2) terminates.

The process F accepts the termination request e.

The process F terminates.

At this time, the node is folded one step. After that P offers the termination request e to F again because (car pst) = 1 is not in ps as well.

The process F accepts the termination request e.

The process F terminates.

The node is folded one step and only the running child process remains.

3 August, 2013