ronanh09
asked on
using fork() to calculate definite integral
i am trying to use fork() to create eight processes to compute a definite integral using simpsons rule. i have already used the program below for simpsons rule to calculate the definate integral but i'm not sure how to go any further. just learning!
#include <math.h>
#include <stdio.h>
#define N 20
#define a 0.0
#define b 2.0
double f(double x);
main()
{
int c, k=1; /* Counters in the algorithm */
double x, h, SUM;
/* FILE *fp; Declares a pointer to a file */
/* fp=fopen("simpson.out","w"
printf("\nSimpson's Rule for numerical integration of f(x)\n");
printf("\n From a=%lf to b=%lf", a,b);
printf("\n\nIntervals\t\tS
SUM=f(a); /* Initial function value */
c=2;
h=(b-a)/N; /* Step size h=(b-a)/N */
while (k <= N-1) /* Steps through the iteration */
{
c=6-c; /* gives the 4,2,4,2,... in the algorithm */
SUM = SUM + c*f(a+k*h); /* Adds on the next area */
k++; /* Increases k, the no. of steps taken, by 1 */
}
SUM = ( SUM + f(b) )*h/3 ; /* add the value f(b) to the sum and multiply*/
/* by overall factor, h/3 */
printf("%d \t\t%lf \t\t%lf\n", N, h, SUM ); /* print the answer */
}
double f(double x)
{
double function;
function = x*x*x*x;
return(function);
}
#include <math.h>
#include <stdio.h>
#define N 20
#define a 0.0
#define b 2.0
double f(double x);
main()
{
int c, k=1; /* Counters in the algorithm */
double x, h, SUM;
/* FILE *fp; Declares a pointer to a file */
/* fp=fopen("simpson.out","w"
printf("\nSimpson's Rule for numerical integration of f(x)\n");
printf("\n From a=%lf to b=%lf", a,b);
printf("\n\nIntervals\t\tS
SUM=f(a); /* Initial function value */
c=2;
h=(b-a)/N; /* Step size h=(b-a)/N */
while (k <= N-1) /* Steps through the iteration */
{
c=6-c; /* gives the 4,2,4,2,... in the algorithm */
SUM = SUM + c*f(a+k*h); /* Adds on the next area */
k++; /* Increases k, the no. of steps taken, by 1 */
}
SUM = ( SUM + f(b) )*h/3 ; /* add the value f(b) to the sum and multiply*/
/* by overall factor, h/3 */
printf("%d \t\t%lf \t\t%lf\n", N, h, SUM ); /* print the answer */
}
double f(double x)
{
double function;
function = x*x*x*x;
return(function);
}
Sjef Bosman
And what would you want each process to do?? Where do you intend to split up the calculation? If that's what you want, how do yo intend to get and "merge" the results of each process?
fork() may not be the optimum way to do this.
It takes many CPU cycles to start up a process with fork().
Then when the process is done, there's no easy way to communicate back the results, other than a 8-bit exit code.
You might do a lot better by using "threads". These start up much quicker than fork()s, and they share the same global variable area, so communicating results back is trivial.
I'd start by separating out the inner loop into a separate function. Then you can start up N-1 threads, each calling that function with their own "k".
It takes many CPU cycles to start up a process with fork().
Then when the process is done, there's no easy way to communicate back the results, other than a 8-bit exit code.
You might do a lot better by using "threads". These start up much quicker than fork()s, and they share the same global variable area, so communicating results back is trivial.
I'd start by separating out the inner loop into a separate function. Then you can start up N-1 threads, each calling that function with their own "k".
For your purpose, fork() is not the right guy to choose. I forgot the Simpson's rule but fork() are very expansive operations so, for just a small tasks, you should not use fork(). And fork() creates a new process and after fork() both the processes run simulteneously, which I don't see of any use of this in your problem. If your program is running fine, why do you want any more improvements. Are you facing any problem..??
fork() can be used to parallise tasks. If you have a multiCPU machine, and expensive task, and a task that can be broken into parts, then using fork() is a sensible option, although as the other posters have stated, the overheads are expensive.
fork() duplicates the current process.
From the manual - "Upon successful completion, fork() returns 0 to the child process and returns the process ID of the child process to the parent process. Otherwise, -1 is returned to the parent process, no child process is created, and errno is set to indicate the error."
Typically, you have a switch statement:
switch(fork()) {
case 0: /* I am the child */
... do child calculations;
break;
case -1: /* error - probably too many processes */
...
exit (1);
default:
/* I am the parent
... Do parent things */
break;
}
In the case of the parent, you might want to run another fork statement. If you surrounded the fork by a for loop you can start many processes.
for(i = 0; i < 8; i++) {
switch(fork()) {
...
...
default: /* parent */
continue; /* do the next iteration */
}
The thing you have to remember is that your code is multi-purpose. It could be either parent or child, and the only way it knows is to check the return value of fork().
The next problem you have is how to collate the results of all of your processes. The most straight-forward way is to write the results of the child processes to a file, and have the parent process read the results when all of the children are finished. The parent process would then collate the results into a single result. An alternative method is to use the return status of the child process, however this only allows a small return value (8 bits), so it isn't really useful, except for success for failure statuses.
You could also use shared memory, but now we are getting complicated. I always used a file.
Two things you need to know:
1) Because the processes are running in parallel, you have to open the file in append mode to prevent the output being corrupted. If you are using creat() to create the output file, use the O_APPEND flag as the third parameter.
2) You need to use the wait() call in the parent to wait for the children to finish. I think you need to call wait for each child process, and you pass it an int pointer in which the status is returned.
So now we have:
int status;
for(i = 0; i < 8; i++) {
switch(fork()) {
case 0: doCalculations(); exit(0);
case -1: /* error - print a message */ exit(1);
default: /* the parent */
break;
}
/* still in the parent here */
for(i = 0; i < 8; i++) {
wait(&status);
}
/* now read the file that the children created and collate the information */
This is of course buggy, and you should add error handling and stuff for when fork() fails. There are also several variants of wait() which will depend on your system.
I used these techniques a lot for crunching big reports. I got the report times down from 6 hours to 30 minutes on a big Sequent system with a load of CPUs in it. For this kind of task, the fork() time is not significant. If you have to sort the output file, I recommend looking up qsort.
One problem you will hit is that if the calculations the children perform are unequal, then some children will finish before others, and in the end you will be back to having 1 process running (the last child). To get round this, I split the problem into say 80 tasks, and I allocated 1 task to each of 8 children. When one child finished, I started a new one giving it the next task until they were all done. In this case, I kept all 8 (or however many) processors running for as long as possible.
fork() duplicates the current process.
From the manual - "Upon successful completion, fork() returns 0 to the child process and returns the process ID of the child process to the parent process. Otherwise, -1 is returned to the parent process, no child process is created, and errno is set to indicate the error."
Typically, you have a switch statement:
switch(fork()) {
case 0: /* I am the child */
... do child calculations;
break;
case -1: /* error - probably too many processes */
...
exit (1);
default:
/* I am the parent
... Do parent things */
break;
}
In the case of the parent, you might want to run another fork statement. If you surrounded the fork by a for loop you can start many processes.
for(i = 0; i < 8; i++) {
switch(fork()) {
...
...
default: /* parent */
continue; /* do the next iteration */
}
The thing you have to remember is that your code is multi-purpose. It could be either parent or child, and the only way it knows is to check the return value of fork().
The next problem you have is how to collate the results of all of your processes. The most straight-forward way is to write the results of the child processes to a file, and have the parent process read the results when all of the children are finished. The parent process would then collate the results into a single result. An alternative method is to use the return status of the child process, however this only allows a small return value (8 bits), so it isn't really useful, except for success for failure statuses.
You could also use shared memory, but now we are getting complicated. I always used a file.
Two things you need to know:
1) Because the processes are running in parallel, you have to open the file in append mode to prevent the output being corrupted. If you are using creat() to create the output file, use the O_APPEND flag as the third parameter.
2) You need to use the wait() call in the parent to wait for the children to finish. I think you need to call wait for each child process, and you pass it an int pointer in which the status is returned.
So now we have:
int status;
for(i = 0; i < 8; i++) {
switch(fork()) {
case 0: doCalculations(); exit(0);
case -1: /* error - print a message */ exit(1);
default: /* the parent */
break;
}
/* still in the parent here */
for(i = 0; i < 8; i++) {
wait(&status);
}
/* now read the file that the children created and collate the information */
This is of course buggy, and you should add error handling and stuff for when fork() fails. There are also several variants of wait() which will depend on your system.
I used these techniques a lot for crunching big reports. I got the report times down from 6 hours to 30 minutes on a big Sequent system with a load of CPUs in it. For this kind of task, the fork() time is not significant. If you have to sort the output file, I recommend looking up qsort.
One problem you will hit is that if the calculations the children perform are unequal, then some children will finish before others, and in the end you will be back to having 1 process running (the last child). To get round this, I split the problem into say 80 tasks, and I allocated 1 task to each of 8 children. When one child finished, I started a new one giving it the next task until they were all done. In this case, I kept all 8 (or however many) processors running for as long as possible.
>1) Because the processes are running in parallel, you have to open the file in append mode to prevent the output being >corrupted. If you are using creat() to create the output file, use the O_APPEND flag as the third parameter.
Watch out, I suspect you could end up with gibberish if two processes tried to write more than one block of data at the same time. Not very likely but possible. Having separate output files would be safer.
Watch out, I suspect you could end up with gibberish if two processes tried to write more than one block of data at the same time. Not very likely but possible. Having separate output files would be safer.
"I suspect you could end up with gibberish "
No, that is wrong. Opening the file in append mode guarantees that the write will always happen at the end of the file, at least if you use the level(2) calls (creat, write, close). It may still work if you use stdio, but I am always suspicous about this. You may have to flush after each write, or set line buffering.
No, that is wrong. Opening the file in append mode guarantees that the write will always happen at the end of the file, at least if you use the level(2) calls (creat, write, close). It may still work if you use stdio, but I am always suspicous about this. You may have to flush after each write, or set line buffering.
>No, that is wrong. Opening the file in append mode guarantees that the write will always happen at the end of the file, at least if >you use the level(2) calls (creat, write, close). It may still work if you use stdio, but I am always suspicous about this. You may >have to flush after each write, or set line buffering.
I'm not "wrong":
(1) The typical sod will use one of the 'f"-prefixed i/o functions, fopen, fwrite, fprintf, etc... These are block-buffered by default. It's quite possible for a fwrite to end up writing one block, then a different fwrite in another thread writing a block, so the data can get interleaved. I call that gibberish.
(2) Even flushing after each write doesnt help if the write wrote more than one block but less than another full block.. Or more than one buffer, but then a bit more.
(3) If the output file is a log file, often automatically redirected thru a NFS link, forget about guaranteed ordering of writes. Just doesnt happen.
(4) Threads are not a "C" standard, so noone can say authoritatively whether C writes from threads are properly handled in general. That's an individual compiler, C library, and operating system implementation issue.
I wouldnt be so picky, but we don't need any more programs out there that work fine 99.73% of the time!
I'm not "wrong":
(1) The typical sod will use one of the 'f"-prefixed i/o functions, fopen, fwrite, fprintf, etc... These are block-buffered by default. It's quite possible for a fwrite to end up writing one block, then a different fwrite in another thread writing a block, so the data can get interleaved. I call that gibberish.
(2) Even flushing after each write doesnt help if the write wrote more than one block but less than another full block.. Or more than one buffer, but then a bit more.
(3) If the output file is a log file, often automatically redirected thru a NFS link, forget about guaranteed ordering of writes. Just doesnt happen.
(4) Threads are not a "C" standard, so noone can say authoritatively whether C writes from threads are properly handled in general. That's an individual compiler, C library, and operating system implementation issue.
I wouldnt be so picky, but we don't need any more programs out there that work fine 99.73% of the time!
May I suggest to suspend the "discussion" until we have some feedback from ronanh09?
Sorry, just a bit wound up about this issue. A while back I paid $99 of my own money for a bulletin board-like web program. Said program had dozens of user complaints about "sometimes the messages get scrambled-looking". I wrote to the author about this, and how the problem was obviously visible by tracing-- he wasnt locking the file when updating. He was apparently fooled by the apparent atomicity of writes, 99.3% of the time. Never did get my money back! :(
And his program's FAQ and web-based helpdesk probably weren't run by said program? Bad omen!
What's happened with gratitude? Even a kind word would have been sufficient to stop you getting pissed off. Let's hope he'll miss 100 customers worth $9,900 due to some bad publicity. I assume he knows what to do now? What a shame...
What's happened with gratitude? Even a kind word would have been sufficient to stop you getting pissed off. Let's hope he'll miss 100 customers worth $9,900 due to some bad publicity. I assume he knows what to do now? What a shame...
Sorry as well; I didn't mean to flame or cause offence, but I have had this argument before!!
creat() is a level(2) (ie, system call) function, and therefore there is no buffering (except in the operating system). Therefore, if you use O_APPEND it WILL always work for single threaded processes to a local file. Even with multiple threads, you should be OK as long as you don't use a shared buffer. Never thought about NFS, but I think that is getting a bit off topic.
I agree though that stdio is another matter. The "a" mode implies it should work, and I tested it once and it did seem to, but I think using creat and write is safer.
creat() is a level(2) (ie, system call) function, and therefore there is no buffering (except in the operating system). Therefore, if you use O_APPEND it WILL always work for single threaded processes to a local file. Even with multiple threads, you should be OK as long as you don't use a shared buffer. Never thought about NFS, but I think that is getting a bit off topic.
I agree though that stdio is another matter. The "a" mode implies it should work, and I tested it once and it did seem to, but I think using creat and write is safer.
Just to clarify, as I appeared to contradict myself.
There is no buffer except in system calls, except obviously for your own data which you are writing; that should not be shared (ie global) if you are using threads.
There is no buffer except in system calls, except obviously for your own data which you are writing; that should not be shared (ie global) if you are using threads.
Hi rghome,
Writes are not atomic. Some FS operations are, such as rename.
When you want to write to the same file with several threads, use a mutex. When you want to do the same with several processes, use a semaphore.
Returning to the idea this question is about, yes, that's a possibility. But using files for communication creates a huge overhead.
I'd use IPC queues and a simple protocol, like transferring the formula (or a function pointer) and the range to calculate. The process calculates the result, and sends it back, using either a queue again, or (probably better) shared memory.
But as grg99 already pointed out, threads are better for this. They're cheaper to create and require less synchronization overhead.
Cheers!
Stefan
Writes are not atomic. Some FS operations are, such as rename.
When you want to write to the same file with several threads, use a mutex. When you want to do the same with several processes, use a semaphore.
Returning to the idea this question is about, yes, that's a possibility. But using files for communication creates a huge overhead.
I'd use IPC queues and a simple protocol, like transferring the formula (or a function pointer) and the range to calculate. The process calculates the result, and sends it back, using either a queue again, or (probably better) shared memory.
But as grg99 already pointed out, threads are better for this. They're cheaper to create and require less synchronization overhead.
Cheers!
Stefan
if you really want to use forks, you need IPC (interprocess communication). the simplest form is a pipe. The pipe() function creates a pair of file descriptors (like STDIN/OUT) that can talk to eachother. You could have one process open up 7 pipes (one for every other process besides itself), and have each process use one of them. Each process does its bit, then sends a float along the pipe. When the 1st one is done, it just listens to the pipes, collects numbers, and adds them together.
But, just to be annother person agreeing... yes, threads are the better way to do this.
But, just to be annother person agreeing... yes, threads are the better way to do this.
ASKER
sorry was away for the weekend. just reading comments now.should have been more clear with my question. i think its the pipe() function that CmdRickHunter is talking about. i agree too that threads would be an easier way to do this but i've been asked too use pipe(). thanks for the help so far. appreciate it very much.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.