Purpose The goal of this homework is to become familiar with concurrent processing in Linux using shared memory. The task is fairly simple but the trick is to implement it with multiple processes using shared memory and signals to communicate between processes, and to exercise some control over them. Task Write a program to compute the sum of n integers using a binary tree of processes. Assume that n is a power of 2. If you have fewer than 2k numbers, fill in other numbers with 0 to make it a power of 2. You will achieve the task as follows: Partition the n integers into n/2 pairs. Use n/2 processes to add each pair of integers resulting into n/2 integers. Repeat the method on the n/2 integers and continue until the final result is obtained. This is a binary tree algorithm.) Structure the integers into a file, one integer per line. You will need to store the integers in shared memory and the child processes will store the results back in shared memory. The main program will set up shared memory to read integers, set up a signal handler, and then, read all integers into shared memory from specified file. Since you do not know the number of integers to read, you may have to run two passes over the data file to find the number of integers and to actually read in the integers. Then, the main program will fork child processes who will create more children as needed. The children will test the index assigned to them, perform the computation, and write the result in place of the first integer. Further, the child process will also update a log file, named adder_log to say what has been done. You will have to use the code for multiple process IPC problem (Solution 4 in notes) to protect the critical resource the log file. That is, the code to update the log file will constitute the critical section in each process. Make sure you never have more than 20 processes in the system at any time. Add the PID of the child to the log file as you update it. The preferred output format is: Time PID Index Depth where Index is the logical process id created by your master process and Depth is how deep in the tree your process is. You can get an idea of the depth by looking at the following tree with the first line containing the numbers to be added: 15 19 2 Depth 3 2 1 0 Numbers 10 8 14 27 44 6 21 35 79 15 17 The first line shows numbers in consecutive indices of shared memory array with depth 3 (log 8), the second line shows the sum of consecutive pairs with results in the first index (even index), the third line shows the results from pairs of second line with result in first index (divisible by 4), and so on. The child process will be execed by the command bin_adder xx yy where xx is the index number starting the list of integers to be added in shared memory and yy is the depth of integers to be added. The result from depth 0 will be the final result. If a process starts to execute code to enter the critical section, it must print a message to that effect on stderr. It will be a good idea to include the time when that happens. Also, indicate the time on stderr when the process actually enters and exits the critical section. Within the critical section, wait for 1 second before you write into the file. We do this to let the other children wait before entering the critical section. Other points to remember: You are required to use fork, exec (or one of its variants), wait, and exit to manage multiple processes. Use shmctl suite of calls for shared memory allocation. Make sure that you never have more than 20 processes in the system at any time, even if I specify 256 numbers in my data file. You can do this by keeping a counter in master that gets incremented by fork and decremented by wait. Invoking the solution master should take in several command line options as follows: master -h master [-h] [-s i] [-t time] datafile -h -S X -t time datafile Describe how the project should be run and then, terminate. Indicate the number of children allowed to exist in the system at the same time. (Default 20) The time in seconds after which the process will terminate, even if it has not finished. (Default 100) Input file containing one integer on each line. Note that all of these options should have some sensible default values, which should be described if -h is specified. With the option -s i, master will fork/exec (i-1) child processes but then not create any more until one of them terminates. Once a child terminates, master will create another, continuing this until it has solved the problem. The default for i is 20. At that point it will wait until all children have terminated. When done, it would output appropriate information to the logfile, called output.log. The option -t time allows you to specify maximum time for process execution (default 100 sec) and if it has not terminated by then, abort it. You will be required to create separate bin_adder processes from your main process. That is, the main process will just spawn the child processes and wait for them to finish. The main process also sets a timer at the start of computation to specified time in seconds (default 100). If computation has not finished by this time, the main process kills all the spawned processes and then exits. Make sure that you print appropriate message(s). In addition, the main process should print a message when an interrupt signal (CC) is received. All the children should be killed as a result. All other signals are ignored. Make sure that the processes handle multiple interrupts correctly. As a precaution, add this feature only after your program is well debugged. The code for main and child processes should be compiled separately and the executables be called master and bin_adder. Make sure that you do not use absolute path for the child processes. Termination Criteria: There are several termination criteria. First, if all the children have finished, the parent process should deallocate shared memory and terminate. In addition, I expect your program to terminate after the specified amount of time (-t option) of real clock. This can be done using a timeout signal, at which point it should kill all currently running child processes and terminate. It should also catch the ctrl-c signal, free up shared memory and then terminate all children. No matter how it terminates, master should also output the value of the shared clock to the output file. For an example of a periodic timer interrupt, you can look at p318 in the text, in the program periodicasterik.c. Suggested implementation steps I suggest you implement these requirements in the following order: Concurrent Unix Processes and shared memory 3 1. Get a Makefile that compiles the two source files. 2. Have your main executable read in the command line arguments and output the values to your screen (and ensure -h displays useful results). Make sure that the parameters have correct values. 3. Have master allocate shared memory, use it, then deallocate it. Make sure to check all possible error returns. Read the data into shared memory. 4. Get master to fork and exec one child and have that child attach to shared memory and read the clock. Have the child output any information it was passed from master and then the value of the clock to test for correct launch. master should wait for it to terminate and then output the value of the clock at that time. 5. Put in the signal handling to terminate after specified number of seconds. A good idea to test this is to simply have the child go into an infinite loop so master will not ever terminate normally. Once this is working have it catch Ctrl-c and free up the shared memory, send a kill signal to the child and then terminate itself. 6. Set up the code to fork multiple child processes until the specific limits. You'll end up doing this in a nested loop. The outer loop will handle levels in the tree while the inner loop will take care of the pairs at the level. 7. Make each child process perform its share of the task and update the log file. 8. Ensure that the critical section problem is solved. If you do it in this order, incrementally, you help make sure that the basic fundamentals are working before getting to the point of launching many processes. Make sure you never have more than 20 processes in the system at any time, even if the program is invoked with n being more than 20. This is a hard limit. Purpose The goal of this homework is to become familiar with concurrent processing in Linux using shared memory. The task is fairly simple but the trick is to implement it with multiple processes using shared memory and signals to communicate between processes, and to exercise some control over them. Task Write a program to compute the sum of n integers using a binary tree of processes. Assume that n is a power of 2. If you have fewer than 2k numbers, fill in other numbers with 0 to make it a power of 2. You will achieve the task as follows: Partition the n integers into n/2 pairs. Use n/2 processes to add each pair of integers resulting into n/2 integers. Repeat the method on the n/2 integers and continue until the final result is obtained. This is a binary tree algorithm.) Structure the integers into a file, one integer per line. You will need to store the integers in shared memory and the child processes will store the results back in shared memory. The main program will set up shared memory to read integers, set up a signal handler, and then, read all integers into shared memory from specified file. Since you do not know the number of integers to read, you may have to run two passes over the data file to find the number of integers and to actually read in the integers. Then, the main program will fork child processes who will create more children as needed. The children will test the index assigned to them, perform the computation, and write the result in place of the first integer. Further, the child process will also update a log file, named adder_log to say what has been done. You will have to use the code for multiple process IPC problem (Solution 4 in notes) to protect the critical resource the log file. That is, the code to update the log file will constitute the critical section in each process. Make sure you never have more than 20 processes in the system at any time. Add the PID of the child to the log file as you update it. The preferred output format is: Time PID Index Depth where Index is the logical process id created by your master process and Depth is how deep in the tree your process is. You can get an idea of the depth by looking at the following tree with the first line containing the numbers to be added: 15 19 2 Depth 3 2 1 0 Numbers 10 8 14 27 44 6 21 35 79 15 17 The first line shows numbers in consecutive indices of shared memory array with depth 3 (log 8), the second line shows the sum of consecutive pairs with results in the first index (even index), the third line shows the results from pairs of second line with result in first index (divisible by 4), and so on. The child process will be execed by the command bin_adder xx yy where xx is the index number starting the list of integers to be added in shared memory and yy is the depth of integers to be added. The result from depth 0 will be the final result. If a process starts to execute code to enter the critical section, it must print a message to that effect on stderr. It will be a good idea to include the time when that happens. Also, indicate the time on stderr when the process actually enters and exits the critical section. Within the critical section, wait for 1 second before you write into the file. We do this to let the other children wait before entering the critical section. Other points to remember: You are required to use fork, exec (or one of its variants), wait, and exit to manage multiple processes. Use shmctl suite of calls for shared memory allocation. Make sure that you never have more than 20 processes in the system at any time, even if I specify 256 numbers in my data file. You can do this by keeping a counter in master that gets incremented by fork and decremented by wait. Invoking the solution master should take in several command line options as follows: master -h master [-h] [-s i] [-t time] datafile -h -S X -t time datafile Describe how the project should be run and then, terminate. Indicate the number of children allowed to exist in the system at the same time. (Default 20) The time in seconds after which the process will terminate, even if it has not finished. (Default 100) Input file containing one integer on each line. Note that all of these options should have some sensible default values, which should be described if -h is specified. With the option -s i, master will fork/exec (i-1) child processes but then not create any more until one of them terminates. Once a child terminates, master will create another, continuing this until it has solved the problem. The default for i is 20. At that point it will wait until all children have terminated. When done, it would output appropriate information to the logfile, called output.log. The option -t time allows you to specify maximum time for process execution (default 100 sec) and if it has not terminated by then, abort it. You will be required to create separate bin_adder processes from your main process. That is, the main process will just spawn the child processes and wait for them to finish. The main process also sets a timer at the start of computation to specified time in seconds (default 100). If computation has not finished by this time, the main process kills all the spawned processes and then exits. Make sure that you print appropriate message(s). In addition, the main process should print a message when an interrupt signal (CC) is received. All the children should be killed as a result. All other signals are ignored. Make sure that the processes handle multiple interrupts correctly. As a precaution, add this feature only after your program is well debugged. The code for main and child processes should be compiled separately and the executables be called master and bin_adder. Make sure that you do not use absolute path for the child processes. Termination Criteria: There are several termination criteria. First, if all the children have finished, the parent process should deallocate shared memory and terminate. In addition, I expect your program to terminate after the specified amount of time (-t option) of real clock. This can be done using a timeout signal, at which point it should kill all currently running child processes and terminate. It should also catch the ctrl-c signal, free up shared memory and then terminate all children. No matter how it terminates, master should also output the value of the shared clock to the output file. For an example of a periodic timer interrupt, you can look at p318 in the text, in the program periodicasterik.c. Suggested implementation steps I suggest you implement these requirements in the following order: Concurrent Unix Processes and shared memory 3 1. Get a Makefile that compiles the two source files. 2. Have your main executable read in the command line arguments and output the values to your screen (and ensure -h displays useful results). Make sure that the parameters have correct values. 3. Have master allocate shared memory, use it, then deallocate it. Make sure to check all possible error returns. Read the data into shared memory. 4. Get master to fork and exec one child and have that child attach to shared memory and read the clock. Have the child output any information it was passed from master and then the value of the clock to test for correct launch. master should wait for it to terminate and then output the value of the clock at that time. 5. Put in the signal handling to terminate after specified number of seconds. A good idea to test this is to simply have the child go into an infinite loop so master will not ever terminate normally. Once this is working have it catch Ctrl-c and free up the shared memory, send a kill signal to the child and then terminate itself. 6. Set up the code to fork multiple child processes until the specific limits. You'll end up doing this in a nested loop. The outer loop will handle levels in the tree while the inner loop will take care of the pairs at the level. 7. Make each child process perform its share of the task and update the log file. 8. Ensure that the critical section problem is solved. If you do it in this order, incrementally, you help make sure that the basic fundamentals are working before getting to the point of launching many processes. Make sure you never have more than 20 processes in the system at any time, even if the program is invoked with n being more than 20. This is a hard limit