Fibonacci using Fork and message queues Let\'s use the fork system call to creat

Question

Fibonacci using Fork and message queues
Let's use the fork system call to create Linux processes to compute the Fibonacci sequence of a given number.
Write a program that takes two parameters: “-F n –S m”, where n is an input number, to be used to
computer the nth number of the Fibonacci sequence and m specifies a computing threshold.

In general, fib(x)=fib(x-1)+fib(x-2), where fib(0) = 0 and fib(1) = 1
if (x-1) > m (or/and (x-2)>m)), your program must use the fork system call to recursively spawn child
processes to compute the next Fibonacci numbers.
Your need to create a POSIX message queue for Read and Write before your child processes are
created. Thus, the parent process and child processes will communicate via the message queue.
When the child process complete its Fibonacci number computation, it will send the result back to
its parent process via the message queue.
The parent process will receive the results by receive messages from its child processes.
The parent process should wait for all its child processes terminated and then close the message
queue, if existing.
if (x-1) <= m (or/and (x-2)<=m)), your program recursively call fib_seq(x-1) to compute the next Fibonacci number.

int fib_seq(int x) { /* slow/recursive implementation of Fib */
int i, rint = (rand()%30); double dummy;
for (i=0; i<rint*100; i++) {dummy=2.345*i*8.765/1.234;}

if (x==0) return(0); else if (x==1) return(1); else return(fib_seq(x-1)+fib_seq(x-2));

}

Your program should follow the given input/output format: “myfib –F n –S m”. It should output/print ONLY the nth Fibonacci number. See the example below.
$ myfib –F 6 –S 6
8
$ myfib –F 6 –S 3
8

The above two cases will output the same result “8”. The former one will do every computation in sequential
while the later one will create several child processes to do the computation. In a multicore system, the later
one should take less time to complete since multiple processes can utilize multiple cores.
Hint:
You can use C-library call “getopt” to handle your commend line input
Use POSIX message queue to do interprocess communication.
POSIX queue is named by a string “/xxyy”, you can use your PID as a part of string to make your
queue unique.
If you left too many queues in system, go to “/dev/mqueue” to manually remove left over
queues.
Be careful about how many child processes to be created.

Explanation / Answer

# include # include # include # include # include # include # include # include #ifndef MAX_SEQUENCE # define MAX_SEQUENCE 10 #endif // Check that MAX_SEQUENCE is large enough! #if MAX_SEQUENCE < 2 #error MAX_SEQUENCE must be at least 2 #endif typedef struct{ long fib_sequence[MAX_SEQUENCE]; int sequence_size; } shared_data; int main() { int a, b, m, n, i; a = 0; b = 1; printf("Enter the number of a Fibonacci Sequence: "); // Always check whether input conversion worked if (scanf("%d", &m) != 1) { printf("Invalid input, couldn't be converted. "); return EXIT_FAILURE; } if (m MAX_SEQUENCE) { printf("Please enter an integer less than %d ", MAX_SEQUENCE); return EXIT_FAILURE; // exit if input is invalid } /* the identifier for the shared memory segment */ int segment_id; /* the size (in bytes) of the shared memory segment */ size_t segment_size = sizeof(shared_data); /* allocate a shared memory segment */ segment_id = shmget(IPC_PRIVATE, segment_size, S_IRUSR | S_IWUSR); // Check result of shmget if (segment_id == -1) { perror("shmget failed"); return EXIT_FAILURE; } /* attach the shared memory segment */ shared_data *shared_memory = shmat(segment_id, NULL, 0); // Check whether attaching succeeded if ((void*)shared_memory == (void*)-1) { perror("shmat failed"); goto destroy; // clean up } printf(" shared memory segment %d attached at address %p ", segment_id, (void*)shared_memory); shared_memory->sequence_size = m; pid_t pid; pid = fork(); if (pid == 0){ printf("Child is producing the Fibonacci Sequence... "); shared_memory->fib_sequence[0] = a; shared_memory->fib_sequence[1] = b; for (i = 2; i sequence_size; i++){ n = a+b; shared_memory->fib_sequence[i] = n; a = b; b = n; } printf(" Child ends "); } else{ printf("Parent is waiting for child to complete... "); wait(NULL); printf("Parent ends "); for(i = 0; i sequence_size; i++) { printf("%ld ", shared_memory->fib_sequence[i]); } printf(" "); } /* now detach the shared memory segment */ if (shmdt(shared_memory) == -1) { fprintf(stderr, "Unable to detach "); } destroy: /* now remove the shared memory segment */ shmctl(segment_id, IPC_RMID, NULL); return 0; }

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.