Hi Everyone,

I'm having a problem with forking 7 subprocesses.

I'm trying to do bucket sort as an example of a parallel sorting algorithm. I create seven pipes, one to each subprocess. Then I send each process the words from a specified range. Then I get them to sort them. It all works perfectly up to here.

Then I tried getting the subprocesses to send their sorted words back to the parent in succession. But it wont work. Sometimes some of the subprocesses are still running after the parent finishes, even though that shouldnt have happened really( though they could just have had really low priority?) Anyway the words from the second last process dont get outputtedto the outfile and the words from the last process get sent back unsorted.

Here's the code(it's kind of long, sorry!)....



// Author: Ian McLoughlin( 02127377, NUIGalway )
// Date: 27th October 2004

/* Description:
This program mimics the behaviour of a parallel computer
by using the fork() command. It performs bucket sort on a
list of words. Each processor is assigned a range of
the alphabet and then is sent the words from the list
which are in this range. Each processor then sorts its own
list using QuickSort and then returns them to the parent
process.
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>


#define MAX_WORDS 300 // The maximum number of words to read in.
#define MAX_LENGTH 40 // The maximun length of a word.
#define NO_PROCS 8 // The number of subprocesses to create.



// Sets the proper casts for the strcmp() function for qsort()...
int mystrcmp( const void *s1, const void *s2 );
// Handle the opening of the input and output files...
int openfiles( int argc, char *argv[], FILE **infile, FILE **outfile );
// Read in the words from the input file...
int readwords( FILE *infile, char **words );
// Check to see is c between bottom and top inclusive in the alphabet(case insensitive)...
int inrange( char c, char bottom, char top );
void sendstr( int filedes, char *string );
void getstr( int filedes, char **retval );


int main( int argc, char *argv[] ) {

char *words[MAX_WORDS]; // The array of initially unsorted words.
char *mywords[MAX_WORDS]; // Each processor's array of words.
int no_words; // The total number of words.
int no_mywords; // Each processor's amount of words.
int i; // Used for iteration on words.
int j; // Used for iteration on mywords.

FILE *infile; // The input file pointer.
FILE *outfile; // The output file pointer.

int pid = 1; // Each processor's pid.
int pno = 0; // Each processor's number.
int pd[NO_PROCS-1][2]; // The pipes.


// Open the files...
if ( !openfiles( argc, argv, &infile, &outfile ) ) return(-1);

// Read in the words(or exit on an error)...
no_words = readwords( infile, words );
if ( no_words == 0 ) {

printf("\n\tError: no words read in from %s!\n\n", argv[1]);
return(-1);

}

/////////////////////////////////////////////////////////////////////
// Set up the processors(create NO_PROCS-1 sub processes... //
/////////////////////////////////////////////////////////////////////
for ( i = 1 ; i < NO_PROCS ; i++){

// If you're the parent...
if ( pid != 0 ) {

pipe( pd[i-1] ); // Open a new pipe.
pid = fork(); // Create a child.
if ( pid == 0 ) pno = i; // Give the child its processor number.

}

}


////////////////////////////////////////////////////////////////////
// Send the words from the parent to the children processes... //
////////////////////////////////////////////////////////////////////

// If you're the parent...
if ( pid != 0 ) {

// Loop over all the words...
for ( j = 0, i = 0 ; i < no_words ; i++ ) {

// The parent sorts the words with initial letter <= 'c'...
if ( words[i][0] <= 'C' || ( words[i][0] > 'Z' && words[i][0] <= 'c' ) ) {

mywords[j] = (char * ) malloc( sizeof( char ) * ( strlen( words[i] ) + 1 ) );
strcpy( mywords[j], words[i] );
j++;

// The children sort the others....
} else {

if ( inrange( words[i][0], 'd', 'f' ) ) sendstr( pd[0][1], words[i] );
else if ( inrange( words[i][0], 'g', 'i' ) ) sendstr( pd[1][1], words[i] );
else if ( inrange( words[i][0], 'j', 'l' ) ) sendstr( pd[2][1], words[i] );
else if ( inrange( words[i][0], 'm', 'o' ) ) sendstr( pd[3][1], words[i] );
else if ( inrange( words[i][0], 'p', 'r' ) ) sendstr( pd[4][1], words[i] );
else if ( inrange( words[i][0], 's', 'v' ) ) sendstr( pd[5][1], words[i] );
else sendstr( pd[6][1], words[i] );

}

}

// Find out how many words the parent has...
no_mywords = j;

// Tell the children that there are no more words(send them a \n)...
for ( i = 0 ; i < NO_PROCS - 1 ; i++ ) sendstr( pd[i][1], "\n" );


// If you're a child...
} else {


// Read in the words until the parent tells me to stop...
for ( j = 0 ; j < MAX_WORDS ; j++ ) {

getstr( pd[pno-1][0], &mywords[j] );
if ( strcmp( mywords[j], "\n" ) == 0 ) break;

}


// Find out how many words I have...
no_mywords = j - 1;

}


////////////////////////////////////////////////////////////////////
// Sort the words... //
////////////////////////////////////////////////////////////////////

// Sort the words using qsort() from the standard library...
if ( no_mywords > 0 ) qsort( mywords, no_mywords, sizeof( char * ), mystrcmp );


////////////////////////////////////////////////////////////////////
// Send the sorted words from the children to the parent... //
////////////////////////////////////////////////////////////////////


// If I'm the parent...
if ( pid != 0 ) {

// Loop over all the children...
for ( j = no_mywords, i = 0; i < (NO_PROCS-1) ; i++ ) {

// Keep reading words until the child tells us there are no more...
for ( ; j < MAX_WORDS ; j++ ) {

// Read in a word from the child...
getstr( pd[i][0], &mywords[j] );

// Break out of the loop if the child tells you to...
if ( strcmp( mywords[j], "\n" ) == 0 ) break;
else no_mywords++;
}

}


// If Im a child...
} else {

// Send the parent all my words...
for ( i = 0 ; i < no_mywords; i++ ) sendstr( pd[pno-1][1], mywords[i] );
// Tell the parent thereare no mroe words...
sendstr( pd[pno-1][1], "\n" );

}



////////////////////////////////////////////////////////////////////
// Output the words and close the files... //
////////////////////////////////////////////////////////////////////

if ( pid != 0 ) {

// Output the words to sorted.txt...
for ( i = 0 ; i < no_mywords ; i++ ) fprintf( outfile, "%s\n", mywords[i] );

// Close the input/output files...
fclose( infile );
fclose( outfile );

}


return(0);

}


// qsort requires this re-casting of the function strcmp()...
int mystrcmp( const void *s1, const void *s2 ) {

return ( strcmp( * (char **) s1, * (char **) s2 ) );

}


// Open the files, exiting on an error...
int openfiles( int argc, char *argv[], FILE **infile, FILE **outfile ) {

// Make sure the user only gave one command line argument...
if ( argc != 2 ) {

printf("\n\tUsage: %s <unsorted.txt>\n\n", argv[0]);
return(0);

}

// Try to open the input file given as command line argument...
*infile = fopen( argv[1], "r" );
if ( *infile == NULL ) {

printf("\n\tError: can not open %s!\n\n", argv[1]);
return(0);

}

// Try to open the output file ./sorted.txt...
*outfile = fopen( "sorted.txt", "w" );
if ( *outfile == NULL ) {

printf("\n\tError: can not open sorted.txt for writing!\n\n");
return(0);

}

// Return 1 if we're succesful, 0 will already have been returned otherwise...
return(1);

}



// Read the words from the input file, return the no of words inputted...
int readwords( FILE *infile, char **words ) {

char buffer[MAX_LENGTH+1]; // Used for reading in a word.
int i; // For iteration.


// Keep trying to read up to MAX_WORDS words from the file...
for ( i = 0 ; i < MAX_WORDS ; i++ ) {

// Exit the loop if we're at the end of the file...
if ( feof( infile ) ) break;

// Read a word from the file into the buffer...
fscanf( infile, "%s\n", buffer );

// Don't assign the word to a character pointer if it's the empty string...
if ( strcmp( buffer, "" ) == 0 ) {

i--;

} else {

// Use malloc to assign the word in the buffer to the array....
words[i] = ( char * ) malloc( sizeof( char ) * ( strlen( buffer ) + 1 ) );
strcpy( words[i], buffer );

}


}


// Return the number of words read in...
return(i);

}


// Check to see if the character c is between the characters bottom and top...
int inrange( char c, char bottom, char top ) {

// The comparison is case insensitive...
c = tolower( c );
bottom = tolower( bottom );
top = tolower( top );

return( c >= bottom && c <= top );

}


// Send a string through the pipe filedes....
void sendstr( int filedes, char *string ) {

int i;

// Send the string character by character...
for ( i = 0 ; i < MAX_LENGTH ; i++ ) {

write( filedes, &string[i], sizeof( char ) );
if ( string[i] == '\0' ) break;

}

}

// Recieve a string through the pipe filedes...
void getstr( int filedes, char **retval ) {

char buffer[MAX_LENGTH];
int i;

// Read the string character by character...
for ( i = 0 ; i < MAX_LENGTH ; i++ ) {

read( filedes, &buffer[i], sizeof( char ) );
if ( buffer[i] == '\0' ) break;

}

// Set the contents of the buffer to the pointer retval...
*retval = ( char* ) malloc( sizeof( char ) * ( strlen(buffer) + 1 ) );

strcpy( *retval, buffer );


}

ew, ew, ew. Just use posix threads!

yea linux scheduling is the parent and child are totally independant
you are going to have to do that scheduling stuff yourself.

Hi, here is my guess.

#include <sys/types.h>
#include <sys/wait.h>

wait(NULL); //for the parent process

debian:~# man 2 wait

--
next time you should use functions like this.
// A do this, do that
char * A(const char* ,..)
{
...
}

// B do this, do that
void B(pid_t pid, ...)
{
...
}

// C do...
...

int main()
{
char str[MAX];
str=A(..); B(..);...
}

I thought the scheduling would be done automatically by...

for ( j = no_mywords, i = 0; i < (NO_PROCS-1) ; i++ ) {

// Keep reading words until the child tells us there are no more...
for ( ; j < MAX_WORDS ; j++ ) {

// Read in a word from the child...
getstr( pd[i][0], &mywords[j] );

// Break out of the loop if the child tells you to...
if ( strcmp( mywords[j], "\n" ) == 0 ) break;
else no_mywords++;
}

seen as read() will wait for something to be written in the pipe? Anyway I think I solved the problem....I just put a if ( pno >=3) sleep(pno/3); statement in before the processors wrote to the pipe. There must have been a problem with some of the buffer or something.

I had to use fork() because it was for an assignment in college! Bit stupid really.

Anyway thanks a million for all yere help!

You don't need to 'use pthreads', nor do you need to 'do scheduling yourself'.

Using fork() here is a perfectly reasonable thing to do, especially if you are running on a UNIX-like OS such as Linux. As the previous poster suggests, you were just missing the last piece -- calling one of the wait() system calls. This causes the parent to block until a child (in your case multiple children) exits.

Your intuition to use sleep() was correct -- you knew you needed to wait for the children. However, you cannot rely on this to work, which is why we have wait().

See also: waitpid(), which allows you to specify a particular pid for which to wait.