ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Introduction to Linux - A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free.
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.
*/
#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' ) ) {
// 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 ) {
// 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++ ) {
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.
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.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.