| /* |
| * |
| * Copyright (c) International Business Machines Corp., 2001 |
| * |
| * This program is free software; you can redistribute it and/or modify |
| * it under the terms of the GNU General Public License as published by |
| * the Free Software Foundation; either version 2 of the License, or |
| * (at your option) any later version. |
| * |
| * This program is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See |
| * the GNU General Public License for more details. |
| * |
| * You should have received a copy of the GNU General Public License |
| * along with this program; if not, write to the Free Software |
| * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| */ |
| |
| /* |
| * FILE : pth_str01.c |
| * DESCRIPTION : create a tree of threads does calculations, and |
| * returns result to parent |
| * HISTORY: |
| * 05/l6/2001 Paul Larson (plars@us.ibm.com) |
| * -Ported |
| * |
| */ |
| |
| #include <pthread.h> |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <errno.h> |
| #include <sys/types.h> |
| |
| #define MAXTHREADS 1000 |
| |
| /* Type definition */ |
| struct kid_info { |
| long sum; /* sum of childrens indexes plus our own */ |
| int index; /* our index into the array */ |
| int status; /* return status of this thread */ |
| int child_count; /* Count of children created */ |
| int talk_count; /* Count of siblings that we talked to */ |
| pthread_t *threads; /* dynamic array of thread id of kids */ |
| pthread_mutex_t talk_mutex; /* mutex for the talk_count */ |
| pthread_mutex_t child_mutex; /* mutex for the child_count */ |
| pthread_cond_t talk_condvar; /* condition variable for talk_count */ |
| pthread_cond_t child_condvar; /* condition variable for child_count */ |
| struct kid_info **child_ptrs; /* dynamic array of ptrs to kids */ |
| } ; |
| typedef struct kid_info c_info; |
| |
| |
| /* Global variables */ |
| int depth = 3; |
| int breadth = 4; |
| int timeout = 30; /* minutes */ |
| int cdepth; /* current depth */ |
| int debug = 0; |
| |
| c_info *child_info; /* pointer to info array */ |
| int node_count; /* number of nodes created so far */ |
| pthread_mutex_t node_mutex; /* mutex for the node_count */ |
| pthread_cond_t node_condvar; /* condition variable for node_count */ |
| pthread_attr_t attr; /* attributes for created threads */ |
| |
| |
| /*--------------------------------------------------------------------------------* |
| * parse_args |
| * |
| * Parse command line arguments. Any errors cause the program to exit |
| * at this point. |
| *--------------------------------------------------------------------------------*/ |
| static void parse_args( int argc, char *argv[] ) |
| { |
| int opt, errflag = 0; |
| int bflag = 0, dflag = 0, tflag = 0; |
| extern char *optarg; |
| |
| while ( (opt = getopt( argc, argv, "b:d:t:D?" )) != EOF ) { |
| switch ( opt ) { |
| case 'b': |
| if ( bflag ) |
| errflag++; |
| else { |
| bflag++; |
| breadth = atoi( optarg ); |
| if ( breadth <= 0 ) |
| errflag++; |
| } |
| break; |
| case 'd': |
| if ( dflag ) |
| errflag++; |
| else { |
| dflag++; |
| depth = atoi( optarg ); |
| if ( depth <= 0 ) |
| errflag++; |
| } |
| break; |
| case 't': |
| if ( tflag ) |
| errflag++; |
| else { |
| tflag++; |
| timeout = atoi( optarg ); |
| if ( timeout <= 0 ) |
| errflag++; |
| } |
| break; |
| case 'D': |
| debug = 1; |
| break; |
| case '?': |
| default: |
| errflag++; |
| break; |
| } |
| } |
| |
| if ( errflag ) { |
| fprintf( stderr, "usage: %s [-b <num>] [-d <num>] [-t <num>] [-D]", argv[0] ); |
| fprintf( stderr, "where:\n" ); |
| fprintf( stderr, "\t-b <num>\tbreadth of child nodes\n" ); |
| fprintf( stderr, "\t-d <num>\tdepth of child nodes\n" ); |
| fprintf( stderr, "\t-t <num>\ttimeout for child communication (in minutes)\n" ); |
| fprintf( stderr, "\t-D\tdebug mode\n" ); |
| exit( 1 ); |
| } |
| |
| } |
| |
| |
| /*--------------------------------------------------------------------------------* |
| * num_nodes |
| * |
| * Caculate the number of child nodes for a given breadth and depth tree. |
| *--------------------------------------------------------------------------------*/ |
| int num_nodes( int b, int d ) |
| { |
| int n, sum = 1, partial_exp = 1; |
| |
| /* |
| * The total number of children = sum ( b ** n ) |
| * n=0->d |
| * Since b ** 0 == 1, and it's hard to compute that kind of value |
| * in this simplistic loop, we start sum at 1 (above) to compensate |
| * and do the computations from 1->d below. |
| */ |
| for ( n = 1; n <= d; n++ ) { |
| partial_exp *= b; |
| sum += partial_exp; |
| } |
| |
| return( sum ); |
| } |
| |
| |
| /*--------------------------------------------------------------------------------* |
| * synchronize_children |
| * |
| * Register the child with the parent and then wait for all of the children |
| * at the same level to register also. Return when everything is synched up. |
| *--------------------------------------------------------------------------------*/ |
| int synchronize_children( c_info *parent ) |
| { |
| int my_index, rc; |
| c_info *info_p; |
| struct timespec timer; |
| |
| if ( debug ) { |
| printf( "trying to lock node_mutex\n" ); |
| fflush( stdout ); |
| } |
| |
| /* Lock the node_count mutex to we can safely increment it. We |
| * will unlock it when we broadcast that all of our siblings have |
| * been created or when we block waiting for that broadcast. */ |
| pthread_mutex_lock( &node_mutex ); |
| my_index = node_count++; |
| |
| printf( "thread %d started\n", my_index ); |
| fflush( stdout ); |
| |
| /* Get a pointer into the array of thread structures which will be "me". */ |
| info_p = &child_info[my_index]; |
| info_p->index = my_index; |
| info_p->sum = (long) my_index; |
| |
| if ( debug ) { |
| printf( "thread %d info_p=%x\n", my_index, info_p ); |
| fflush( stdout ); |
| } |
| |
| /* Register with parent bumping the parent's child_count variable. |
| * Make sure we have exclusive access to that variable before we |
| * do the increment. */ |
| if ( debug ) { |
| printf( "thread %d locking child_mutex %x\n", my_index, &parent->child_mutex ); |
| fflush( stdout ); |
| } |
| pthread_mutex_lock( &parent->child_mutex ); |
| if ( debug ) { |
| printf( "thread %d bumping child_count (currently %d)\n", |
| my_index, parent->child_count ); |
| fflush( stdout ); |
| } |
| parent->child_ptrs[parent->child_count++] = info_p; |
| if ( debug ) { |
| printf( "thread %d unlocking child_mutex %x\n", my_index, |
| &parent->child_mutex ); |
| fflush( stdout ); |
| } |
| pthread_mutex_unlock( &parent->child_mutex ); |
| |
| if ( debug ) { |
| printf( "thread %d node_count = %d\n", my_index, node_count ); |
| printf( "expecting %d nodes\n", num_nodes(breadth, cdepth) ); |
| fflush( stdout ); |
| } |
| |
| /* Have all the nodes at our level in the tree been created yet? |
| * If so, then send out a broadcast to wake everyone else up (to let |
| * them know they can now create their children (if they are not |
| * leaf nodes)). Otherwise, go to sleep waiting for the broadcast. */ |
| if ( node_count == num_nodes(breadth, cdepth) ) { |
| |
| /* Increase the current depth variable, as the tree is now |
| * fully one level taller. */ |
| if ( debug ) { |
| printf( "thread %d doing cdepth++ (%d)\n", my_index, cdepth ); |
| fflush( stdout ); |
| } |
| cdepth++; |
| |
| if ( debug ) { |
| printf( "thread %d sending child_mutex broadcast\n", my_index ); |
| fflush( stdout ); |
| } |
| |
| /* Since all of our siblings have been created, this level of |
| * the tree is now allowed to continue its work, so wake up the |
| * rest of the siblings. */ |
| pthread_cond_broadcast( &node_condvar ); |
| |
| } else { |
| |
| /* In this case, not all of our siblings at this level of the |
| * tree have been created, so go to sleep and wait for the |
| * broadcast on node_condvar. */ |
| if ( debug ) { |
| printf( "thread %d waiting for siblings to register\n", |
| my_index ); |
| fflush( stdout ); |
| } |
| time( &timer.tv_sec ); |
| timer.tv_sec += (unsigned long)timeout * 60; |
| timer.tv_nsec = (unsigned long)0; |
| if ( rc = pthread_cond_timedwait(&node_condvar, &node_mutex, |
| &timer) ) { |
| fprintf( stderr, "pthread_cond_timedwait (sync) %d: %s\n", |
| my_index, sys_errlist[rc] ); |
| exit( 2 ); |
| } |
| |
| if ( debug ) { |
| printf( "thread %d is now unblocked\n", my_index ); |
| fflush( stdout ); |
| } |
| |
| } |
| |
| /* Unlock the node_mutex lock, as this thread is finished initializing. */ |
| if ( debug ) { |
| printf( "thread %d unlocking node_mutex\n", my_index ); |
| fflush( stdout ); |
| } |
| pthread_mutex_unlock( &node_mutex ); |
| if ( debug ) { |
| printf( "thread %d unlocked node_mutex\n", my_index ); |
| fflush( stdout ); |
| } |
| |
| if ( debug ) { |
| printf( "synchronize_children returning %d\n", my_index ); |
| fflush( stdout ); |
| } |
| |
| return( my_index ); |
| } |
| |
| |
| /*--------------------------------------------------------------------------------* |
| * doit |
| * |
| * Do it. |
| *--------------------------------------------------------------------------------*/ |
| void *doit( void *param ) |
| { |
| c_info *parent = (c_info *) param; |
| int rc, child, my_index; |
| void *status; |
| c_info *info_p; |
| struct timespec timer; |
| |
| if ( debug ) { |
| printf( "parent=%#010x\n", parent ); |
| fflush( stdout ); |
| } |
| |
| if ( parent != NULL ) { |
| /* Synchronize with our siblings so that all the children at |
| * a given level have been created before we allow those children |
| * to spawn new ones (or do anything else for that matter). */ |
| if ( debug ) { |
| printf( "non-root child calling synchronize_children\n" ); |
| fflush( stdout ); |
| } |
| my_index = synchronize_children( parent ); |
| if ( debug ) { |
| printf( "non-root child has been assigned index %d\n", |
| my_index ); |
| fflush( stdout ); |
| } |
| } else { |
| /* The first thread has no one with which to synchronize, so |
| * set some initial values for things. */ |
| if ( debug ) { |
| printf( "root child\n" ); |
| fflush( stdout ); |
| } |
| cdepth = 1; |
| my_index = 0; |
| node_count = 1; |
| } |
| |
| /* Figure out our place in the pthread array. */ |
| info_p = &child_info[my_index]; |
| |
| if ( debug ) { |
| printf( "thread %d getting to heart of doit.\n", my_index ); |
| printf( "info_p=%x, cdepth=%d, depth=%d\n", info_p, cdepth, depth ); |
| fflush( stdout ); |
| } |
| |
| if ( cdepth <= depth ) |
| { |
| /* Since the tree is not yet complete (it is not yet tall enough), |
| * we need to create another level of children. */ |
| |
| printf( "thread %d creating kids, cdepth=%d\n", my_index, cdepth ); |
| fflush( stdout ); |
| |
| /* Create breadth children. */ |
| for ( child = 0; child < breadth; child++ ) { |
| if ( debug ) { |
| printf( "thread %d making child %d, ptr=%x\n", my_index, |
| child, &(info_p->threads[child]) ); |
| fflush( stdout ); |
| } |
| if ( rc = pthread_create(&(info_p->threads[child]), &attr, doit, (void *) info_p) ) { |
| fprintf( stderr, "pthread_create (doit): %s\n", |
| sys_errlist[rc] ); |
| exit( 3 ); |
| } else { |
| if ( debug ) { |
| printf( "pthread_create made thread %x\n", |
| &(info_p->threads[child]) ); |
| fflush( stdout ); |
| } |
| } |
| } |
| |
| if ( debug ) { |
| printf( "thread %d waits on kids, cdepth=%d\n", my_index, |
| cdepth ); |
| fflush( stdout ); |
| } |
| |
| /* Wait for our children to finish before we exit ourselves. */ |
| for ( child = 0; child < breadth; child++ ) { |
| if ( debug ) { |
| printf( "attempting join on thread %x\n", |
| &(info_p->threads[child]) ); |
| fflush( stdout ); |
| } |
| if ( rc = pthread_join((info_p->threads[child]), &status) ) { |
| if ( debug ) { |
| fprintf( stderr, |
| "join failed on thread %d, status addr=%x: %s\n", |
| my_index, status, sys_errlist[rc] ); |
| fflush( stderr ); |
| } |
| exit( 4 ); |
| } else { |
| if ( debug ) { |
| printf( "thread %d joined child %d ok\n", my_index, child ); |
| fflush( stdout ); |
| } |
| |
| /* Add all childrens indexes to your index value */ |
| info_p->sum += info_p->child_ptrs[child]->sum; |
| printf("thread %d adding child thread %ld to sum = %ld\n", |
| my_index, info_p->child_ptrs[child]->index, info_p->sum); |
| } |
| } |
| |
| } else { |
| |
| /* This is the leaf node case. These children don't create |
| * any kids; they just talk amongst themselves. */ |
| printf( "thread %d is a leaf node, depth=%d\n", my_index, cdepth ); |
| fflush( stdout ); |
| |
| /* Talk to siblings (children of the same parent node). */ |
| if ( breadth > 1 ) { |
| |
| for ( child = 0; child < breadth; child++ ) { |
| /* Don't talk to yourself. */ |
| if ( parent->child_ptrs[child] != info_p ) { |
| if ( debug ) { |
| printf( "thread %d locking talk_mutex\n", |
| my_index ); |
| fflush( stdout ); |
| } |
| pthread_mutex_lock( |
| &(parent->child_ptrs[child]->talk_mutex) ); |
| if ( ++parent->child_ptrs[child]->talk_count == (breadth - 1) ) { |
| if ( debug ) { |
| printf( "thread %d talk siblings\n", my_index ); |
| fflush( stdout ); |
| } |
| if ( rc = pthread_cond_broadcast( |
| &parent->child_ptrs[child]->talk_condvar) ) { |
| fprintf( stderr, "pthread_cond_broadcast: %s\n", |
| sys_errlist[rc] ); |
| exit( 5 ); |
| } |
| } |
| if ( debug ) { |
| printf( "thread %d unlocking talk_mutex\n", |
| my_index ); |
| fflush( stdout ); |
| } |
| pthread_mutex_unlock( |
| &(parent->child_ptrs[child]->talk_mutex) ); |
| } |
| } |
| |
| /* Wait until the breadth - 1 siblings have contacted us. */ |
| if ( debug ) { |
| printf( "thread %d waiting for talk siblings\n", my_index ); |
| fflush( stdout ); |
| } |
| |
| pthread_mutex_lock( &info_p->talk_mutex ); |
| if ( info_p->talk_count < (breadth - 1) ) { |
| time( &timer.tv_sec ); |
| timer.tv_sec += (unsigned long)timeout * 60; |
| timer.tv_nsec = (unsigned long)0; |
| if ( rc = pthread_cond_timedwait(&info_p->talk_condvar, |
| &info_p->talk_mutex, &timer) ) { |
| fprintf( stderr, |
| "pthread_cond_timedwait (leaf) %d: %s\n", |
| my_index, sys_errlist[rc] ); |
| exit( 6 ); |
| } |
| } |
| pthread_mutex_unlock( &info_p->talk_mutex ); |
| |
| } |
| |
| } |
| |
| /* Our work is done. We're outta here. */ |
| printf( "thread %d exiting, depth=%d, status=%d, addr=%x\n", my_index, |
| cdepth, info_p->status, info_p); |
| fflush( stdout ); |
| |
| pthread_exit( 0 ); |
| } |
| |
| |
| |
| /*--------------------------------------------------------------------------------* |
| * main |
| *--------------------------------------------------------------------------------*/ |
| int main( int argc, char *argv[] ) |
| { |
| int rc, index, total; |
| pthread_t root_thread; |
| |
| parse_args( argc, argv ); |
| |
| /* Initialize node mutex. */ |
| if ( rc = pthread_mutex_init(&node_mutex, NULL) ) { |
| fprintf( stderr, "pthread_mutex_init(node_mutex): %s\n", |
| sys_errlist[rc] ); |
| exit( 7 ); |
| } |
| |
| /* Initialize node condition variable. */ |
| if ( rc = pthread_cond_init(&node_condvar, NULL) ) { |
| fprintf( stderr, "pthread_cond_init(node_condvar): %s\n", |
| sys_errlist[rc] ); |
| exit( 8 ); |
| } |
| |
| /* Allocate pthread info structure array. */ |
| if ( (total = num_nodes( breadth, depth )) > MAXTHREADS ) { |
| fprintf( stderr, "Can't create %d threads; max is %d.\n", |
| total, MAXTHREADS ); |
| exit( 9 ); |
| } |
| printf( "Allocating %d nodes.\n", total ); |
| fflush( stdout ); |
| if ( (child_info = (c_info *)malloc( total * sizeof(c_info) )) == NULL ) { |
| perror( "malloc child_info" ); |
| exit( 10 ); |
| } |
| bzero( child_info, total * sizeof(c_info) ); |
| |
| if ( debug ) { |
| printf( "Initializing array for %d children\n", total ); |
| fflush( stdout ); |
| } |
| |
| /* Allocate array of pthreads descriptors and initialize variables. */ |
| for ( index = 0; index < total; index++ ) { |
| |
| if ( (child_info[index].threads = |
| (pthread_t *)malloc( breadth * sizeof(pthread_t) )) == NULL ) { |
| perror( "malloc threads" ); |
| exit( 11 ); |
| } |
| bzero( child_info[index].threads, breadth * sizeof(pthread_t) ); |
| |
| if ( (child_info[index].child_ptrs = |
| (c_info **)malloc( breadth * sizeof(c_info *) )) == NULL ) { |
| perror( "malloc child_ptrs" ); |
| exit( 12 ); |
| } |
| bzero( child_info[index].child_ptrs, |
| breadth * sizeof(c_info *) ); |
| |
| if ( rc = pthread_mutex_init(&child_info[index].child_mutex, NULL) ) { |
| fprintf( stderr, "pthread_mutex_init child_mutex: %s\n", |
| sys_errlist[rc] ); |
| exit( 13 ); |
| } |
| |
| if ( rc = pthread_mutex_init(&child_info[index].talk_mutex, NULL) ) { |
| fprintf( stderr, "pthread_mutex_init talk_mutex: %s\n", |
| sys_errlist[rc] ); |
| exit( 14 ); |
| } |
| |
| if ( rc = pthread_cond_init(&child_info[index].child_condvar, NULL) ) { |
| fprintf( stderr, |
| "pthread_cond_init child_condvar: %s\n", |
| sys_errlist[rc] ); |
| exit( 15 ); |
| } |
| |
| if ( rc = pthread_cond_init(&child_info[index].talk_condvar, NULL) ) { |
| fprintf( stderr, "pthread_cond_init talk_condvar: %s\n", |
| sys_errlist[rc] ); |
| exit( 16 ); |
| } |
| |
| if ( debug ) { |
| printf( "Successfully initialized child %d.\n", index ); |
| fflush( stdout ); |
| } |
| |
| } |
| |
| printf( "Creating root thread attributes via pthread_attr_init.\n" ); |
| fflush( stdout ); |
| |
| if ( rc = pthread_attr_init(&attr) ) { |
| fprintf( stderr, "pthread_attr_init: %s\n", sys_errlist[rc] ); |
| exit( 17 ); |
| } |
| |
| /* Make sure that all the thread children we create have the |
| * PTHREAD_CREATE_JOINABLE attribute. If they don't, then the |
| * pthread_join call will sometimes fail and cause mass confusion. */ |
| if ( rc = pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE)) { |
| fprintf( stderr, "pthread_attr_setdetachstate: %s\n", |
| sys_errlist[rc] ); |
| exit( 18 ); |
| } |
| |
| printf( "Creating root thread via pthread_create.\n" ); |
| fflush( stdout ); |
| |
| if ( rc = pthread_create(&root_thread, &attr, doit, NULL) ) { |
| fprintf( stderr, "pthread_create: %s\n", sys_errlist[rc] ); |
| exit( 19 ); |
| } |
| |
| if ( debug ) { |
| printf( "Doing pthread_join.\n" ); |
| fflush( stdout ); |
| } |
| |
| /* Wait for the root child to exit. */ |
| if ( rc = pthread_join(root_thread, NULL) ) { |
| fprintf( stderr, "pthread_join: %s\n", sys_errlist[rc] ); |
| exit( 20 ); |
| } |
| |
| if ( debug ) { |
| printf( "About to pthread_exit.\n" ); |
| fflush( stdout ); |
| } |
| |
| printf("\n\nThe sum of tree (breadth %d, depth %d) is %ld\n", |
| breadth, depth, child_info[0].sum); |
| exit( 0 ); |
| } |