Lösung zu Blatt 2 (Aufgabe 2): msearch.h + msearch.c

msearch.h

/*
 *      msearch.h -     header file for multi-process search procedure
 *
 *      Martin Hasch, University of Ulm, April 1997
 */

#include        "typedef.h"

/*
 *      Divide a given search interval in equal parts and run
 *      specified search function concurrently for each part.
 *      Stop after at most (timeout) seconds.  Report results
 *      on stdout.
 */
void multisearch(
        Code code,                      /* code to search for */
        Key min, Key max,               /* search interval */
        Searchfunc search,              /* search function */
        unsigned nproc,                 /* number of subprocesses */
        unsigned timeout);              /* timeout in realtime seconds */

msearch.c

/*
 *      msearch.c -     multi-process search procedure
 *
 *      Martin Hasch, University of Ulm, April 1997
 */

#include        <sys/types.h>
#include        <sys/wait.h>
#include        <errno.h>
#include        <signal.h>
#include        <stdio.h>
#include        <unistd.h>
#include        "typedef.h"
#include        "msearch.h"

#define MAX_NPROC       100             /* maximal number of subprocesses */

/*
 *      Simple signal handler, in order to catch but survive alarm signals.
 */
static void alarm_handler(int sig)
{
        (void) signal(sig, alarm_handler);      /* keep this handler */
}

/*
 *      Broadcast termination signal to given processes.
 */
static void kill_processes(unsigned childcount, int childpid[])
{
        unsigned index;

        for ( index=0; index<childcount; ++index ) {
                if ( kill(childpid[index], SIGTERM) )
                        perror("kill");
        }
}

/*
 *      Try setting up nproc child processes to execute the search function.
 *      Store pids in childpid[] and return how many there actually are,
 *      i.e. return value is less than nproc in case of problems, else nproc.
 *      Precondition: max - min >= nproc - 1 >= 0.
 */
static unsigned setup_processes(
        int childpid[],
        Code code, Key min, Key max, Searchfunc search, unsigned nproc)
{
        unsigned childcount, index;
        Key base, top, result;          /* [base, top] subrange of [min, max]*/
        int pid;

        childcount = 0;
        for ( index=0, base=min; index<nproc; ++index, base=top+1 ) {
                top = base + (max - min - index) / nproc;

                switch ( pid = fork() ) {
                case -1:                /* fork failed: give up immediately */
                        perror("cannot fork");
                        kill_processes(childcount, childpid);
                        return childcount;
                case 0:                 /* child process */
                        if ( (*search)(code, base, top, &result) ) {
                                printf("%lx solves %lu\n", result, code);
                                exit(0);
                        } else {
                                exit(1);
                        }
                        /* NOTREACHED */
                default:                /* parent process */
                        childpid[childcount++] = pid;
                }
        }
        return childcount;
}

/*
 *      Remove given pid from list.  Return 1 if it was found, otherwise 0.
 */
static int exclude_pid(unsigned *childcount, int childpid[], int pid)
{
        unsigned index;

        index = 0;
        while ( index < *childcount && childpid[index] != pid )
                ++index;
        if ( index < *childcount ) {
                --*childcount;
                while ( index < *childcount ) {
                        childpid[index] = childpid[index+1];
                        ++index;
                }
                return 1;
        }
        return 0;
}

/*
 *      Wait until all known child processes are done.
 *      If one of them exits with code 0: kill all others and return 1.
 *      If all of them terminate with nonzero status: return 0.
 *      If waiting is interrupted: kill all remaining processes and return -1.
 *      In any case killed processes are waited for before function returns.
 */
static int waitfor_processes(unsigned childcount, int childpid[])
{
        int pid, status;
        int success;

        success = 0;
        while ( childcount ) {
                pid = wait(&status);
                if ( pid == -1 ) {
                        if ( errno == EINTR ) {
                                /* timelimit exceeded, give up */
                                kill_processes(childcount, childpid);
                        } else {
                                /* errno == ECHILD, unexpectedly, */
                                /* thus no point in waiting any more */
                                childcount = 0;
                        }
                        success = -1;
                } else {
                        /* some child terminated */
                        if ( exclude_pid(&childcount, childpid, pid) ) {
                                /* pid was on the list */
                                if ( !status ) {        /* child had success */
                                        kill_processes(childcount, childpid);
                                        success = 1;
                                }
                        }
                }
        }
        return success;
}

/*
 *      Divide a given search interval into equal parts and run
 *      specified search function concurrently for each part.
 *      Stop after at most (timeout) seconds.  Report results
 *      on stdout.
 */
void multisearch(
        Code code,                      /* code to search for */
        Key min, Key max,               /* search interval */
        Searchfunc search,              /* search function */
        unsigned nproc,                 /* number of subprocesses */
        unsigned timeout)               /* timeout in realtime seconds */
{
        int childpid[MAX_NPROC];        /* id's of child processes */
        unsigned childcount;            /* current number of childs */
        int success;

        /* check parameter values */
        if ( min > max ) {              /* sort min, max */
                Key tmp;
                tmp = max, max = min, min = tmp;
        }
        if ( !nproc )
                nproc = 1;
        if ( nproc > MAX_NPROC )
                nproc = MAX_NPROC;
        if ( nproc - 1 > max - min )
                nproc = max - min + 1;

        /* create children */
        childcount = setup_processes(childpid, code, min, max, search, nproc);

        /* arrange for timeout */
        (void) signal(SIGALRM, alarm_handler);
        (void) alarm(timeout);

        /* wait until all children have terminated */
        success = waitfor_processes(childcount, childpid);

        /* undo alarm request */
        (void) alarm(0);

        if ( childcount != nproc ) {
                printf("try fewer processes\n");
        } else if ( success == 0 ) {
                printf("no solution for %lu\n", code);
        } else if ( success == -1 ) {
                printf("timelimit exceeded\n");
        }
}