2.3 Run-Time Environment

A run-time environment is an environment that can execute process networks. In this section we present a run-time environment which is designed for functional simulation of process networks. The run-time environment can be activated by calling the function start which is declared in the include file yapi.h, see for example Program 2.1.1.

2.3.1 Deadlock

When none of the processes can make progress and none of the processes has terminated, we speak of deadlock. In case of deadlock the run-time environment terminates the application and displays information about the history and status of the processes and fifos in order to support the programmer with the debugging of the application.

As an example we modify the Producer-Consumer program by adding a fifo from the consumer to the producer and by letting both the producer and the consumer read from an empty fifo. To save space we leave out the declarations in the header files and only show the implementations in the source files. The process network is graphically depicted in Figure 2.3.

Figure 2.3: Modified Producer-Consumer example suffering from deadlock.

Program 2.3.1   Process Network Implementation

#include "pc.h"

PC::PC(const Id& n) :
        ProcessNetwork(n),
        fifo0   (id("fifo0")),
        fifo1   (id("fifo1")),
        producer(id("producer"), fifo1, fifo0),
        consumer(id("consumer"), fifo0, fifo1)
{ }

Program 2.3.2   Producer Process Implementation

#include "producer.h"
#include <iostream>

Producer::Producer(const Id& n, In<int>& i, Out<int>& o) :
        Process(n),
        in( id("in"), i),
        out( id("out"), o)
{ }

void Producer::main()
{
        const int n = 1000;

        write(out, n);

        for (int i=0; i<n; i++)
        {
                write(out, i);
        }
        
        int x;
        read(in, x);
        write(out, x);

        std::cout << type() << " " 
                  << fullName() << ": "
                  << n << " values written" 
                  << std::endl;
}

Program 2.3.3   Consumer Process Implementation

#include "consumer.h"
#include <assert.h>
#include <iostream>

Consumer::Consumer(Id n, In<int>& i, Out<int>& o) :
        Process(n),
        in( id("in"), i),
        out( id("out"), o)
{ }

void Consumer::main()
{
        int n;
        
        read(in, n);

        for (int i=0; i<n; i++)
        {
                int j;
                read(in, j);
                assert(i==j);
        }
        
        int x;
        read(in, x);
        write(out, x);

        std::cout << type() << " " 
                  << fullName() << ": "
                  << n << " values read" 
                  << std::endl;
}

The additional code in the producer and consumer causes deadlock since the consumer waits for input on fifo 0 and the producer waits for input on fifo 1. The run-time environment detects the deadlock and displays a list of the blocked processes and a fifo status table, as shown below. The list of blocked processes shows that the consumer process pc.consumer and the producer process pc.producer, are blocked by read actions on fifos pc.fifo0 and pc.fifo1, respectively.

YAPI > Deadlock, since all processes have blocked:
Blocked processes:
---------------------------
|Process     by   on Fifo |
|pc.consumer read pc.fifo0|
|pc.producer read pc.fifo1|
---------------------------

Fifo Status:
--------------------------------------------------------------------------
|         min  max size room data Wtokens Rtokens Wpend Rpend Wneed Rneed|
|pc.fifo0   1 2048  128  128    0    1001    1001     0     1     0     0|
|pc.fifo1   1 2048  128  128    0       0       0     0     1     0     0|
--------------------------------------------------------------------------

The fifo status table has 12 columns, and lists the state of all fifos in the process network at the moment when the deadlock occurred. Per fifo it lists the name, the minimum and maximum size, the actual size, the free space in the fifo (room), the number of tokens in the fifo (data), the number of tokens that have been written (Wtokens), the number of tokens that have been read (Rtokens), the number of tokens in a pending write (Wpend), the number of tokens in a pending read (Rpend), the number of tokens in a pending select on an output port (Wneed), and the number of tokens in a pending select on an input port (Rneed). Especially the last four colums are important for detecting the cause of a deadlock. A non-zero number of pending tokens indicates that a read or write call has been issued, but the call has not terminated yet because not all tokens could be communicated, i.e., the process is blocked.

In this example Rpend of fifos pc.fifo0 and pc.fifo1 is 1, which is an indication that a process is waiting for one token to be read. The list of blocked processes can be used to find the corresponding process, which are pc.consumer and pc.producer in this example.

From the table we can furthermore derive that both fifos have an actual size of 128 values. The fifos contain no data, and thus, there is room for 128 values. 1001 values have been written and 1001 values have been read.

When deadlock has been detected and the deadlock information has been printed, the start function will return and the program can continue normally.

The use of a select operation can introduce deadlock. As an example we take a select operation on a single input port with a request for ten tokens. A write operation on the corresponding output port of ten or more tokens does not introduce deadlock because the number of committed tokens is larger than or equal to the number of requested tokens. A write operation on the corresponding output port of less than ten tokens introduces deadlock if and only if the number of committed tokens plus the number of tokens in the fifo is smaller than the number of requested tokens and larger than the fifo size.

As a second example we take a select operation on a single output port with a request for ten tokens. A read operation on the corresponding input port introduces deadlock if and only if the number of committed tokens minus the number of tokens in the fifo is smaller than the number of requested tokens and larger than zero.

The above-mentioned deadlock for the select operation on the input port can be avoided either by increasing the size of the fifo or by increasing the number of committed tokens in the write operation. The above-mentioned deadlock for the select operation on the output port can be avoided only by increasing the number of committed tokens in the read operation.

2.3.2 Termination

A process network terminates when all processes terminate. In that case the start function will return and the program can continue normally.

When none of the processes can make progress and one or more processes have terminated, we assume that we are finished. In order to find out which processes terminated and which processes did not terminate we print the process status table and fifo status table as in the case of deadlock as explained in the previous section.

2.3.3 Stack Size and Stack Overflow

In the YAPI run-time environment a separate stack space is allocated for each process in the process network. This stack is used to store the intermediate results of a process. All function calls from the main member function will be done on the stack, which includes the storage for local (automatic) variables. Intermediate results in expressions may also be stored on the stack if insufficient registers are available. The private member variables of a process and memory that is obtained via malloc or new are not allocated on the stack.

To limit the total amount of stack space to a reasonable amount the stack space of each process is fixed to 64 kilobytes. This should suffice for the individual stack of most processes as well as for the total stack due to the total number of processes. However, for some processes this stack size might be insufficient and may result in a stack overflow. In the YAPI run-time environment a stack overflow will not result in an automatic increase of the stack space, but will result in an access violation as a result of a protected memory space that is inserted between the stacks of two processes. The access violation causes the program to be killed and a core dump to be generated. Next, a debugger (gdb or ddd) can be used to find the location of the error. Usually this happens on a source line where a large data structure such as an array is accessed. Note that this form of stack protection is not available in the CYGWIN version of the YAPI run-time environment.

Of course it is better to avoid the above-mentioned stack overflows and associated core dumps. Since it is difficult to determine the required stack space of a process we suggest that you simply avoid that large data stuctures are allocated on the stack. For video applications this typically means that you should not declare complete video frames, and at most a few video lines as local (automatic) variables in your functions. If you need large data structures in your application it is best to allocate these dynamically on the heap, using malloc or new. Another option is to declare these variables as private members in your process.