7.4 Simple Communication

Team-FLY

Section 7.2 established the connections for a ring of processes. This section develops a simple application in which processes generate a sequence of Fibonacci numbers on the ring. The next number in a Fibonacci sequence is the sum of the previous two numbers in the sequence.

In this project, the processes pass information in character string format. The original parent outputs the string "1 1" representing the first two Fibonacci numbers to standard output, sending the string to the next process. The other processes read a string from standard input, decode the string, calculate the next Fibonacci number, and write to standard output a string representing the previous Fibonacci number and the one just calculated. Each process then writes the result of its calculation to standard error and exits. The original parent exits after receiving a string and displaying the numbers received.

Start with the original ring function of Program 7.1 and replace the fprintf with code to read two integers from standard input in the string format described below, calculate the next integer in a Fibonacci sequence, and write the result to standard output.

  1. Each string is the ASCII representation of two integers separated by a single blank.

  2. The original parent writes out the string "1 1" , representing two ones and then reads a string. Be sure to send the string terminator.

  3. All other processes first read a string and then write a string.

  4. Fibonacci numbers satisfy the formula xn+1 = xn + xn- . Each process receives two numbers (e.g., a followed by b ), calculates c = a + b and writes b followed by c as a null- terminated string. (The b and c values should be written as strings separated by a single blank.)

  5. After sending the string to standard output, the process writes a single-line message to standard error in the following form.

     Process i with PID x and parent PID y received a b and sent b c. 
  6. After sending the message to standard error, the process exits. Try to write the program in such a way that it handles the largest possible number of processes and still calculates the Fibonacci numbers correctly. The execution either runs out of processes or some process generates a numeric overflow when calculating the next number. Attempt to detect this overflow and send the string "0 0" .

Notes: The program should be able to calculate Fib(46)=1,836,311,903, using 45 processes or Fib(47)=2,971,215,073, using 46 processes. It may even be able to calculate Fib(78)=8,944,394,323,791,464, using 77 processes. With a little extra work, the program can compute higher values. A possible approach for detecting overflow is to check whether the result is less than the first integer in the string.

This program puts a heavy load on the CPU of a machine. Don't try this project with more than a few processes unless it is running on a dedicated computer. Also, on some systems, a limit on the number of processes for a user may interfere with running the program for a large number of processes.

Team-FLY


Unix Systems Programming
UNIX Systems Programming: Communication, Concurrency and Threads
ISBN: 0130424110
EAN: 2147483647
Year: 2003
Pages: 274

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net