Assignment 9: Many processes make light work

Due Wednesday, March 29, at midnight

The goals for this assignment are:

  • Implement an algorithm using multiple processes with fork()

  • Compare single- and multi-process implementation performance

  • Work with fork(), wait(), process ids, and shared memory

Update your repository

Do a fetch upstream to obtain the basecode for this assignment.

Using the command line

  • Open terminal and change your current directory to your assignment repository.

  • Run the command git fetch upstream

  • Run the command git merge upstream/master

Your repository should now contain a new folder named A08.

The fetch and merge commands update your repository with any changes from the original.

1. Search

In the file, search.c, implement a program that uses two processes to search for a value in a list. Your program should use fork() to spawn a child process and then split the workload between the parent and the child.

$ make search
gcc -g -Wall -Wvla -Werror search.c -o search
$ ./search
Enter a value to search: 3
Child found 3 at index 5003
Not found!
$ ./search
Enter a value to search: 5003
Not found!
Parent found 5003 at index 3
$ ./search
Enter a value to search: -2
Not found!
Not found!

Requirements:

  • Your program should load the binary file, data.bin. This file stores a sequence of non-sorted integers. The first value in the file holds the number of integers. This class example shows how to read in binary data. Your program should read the first integer to get the size, malloc an array with the given size, and then read in the data as a big block.

  • Your program should split the work of searching through the data between the parent and child process.

2. Multi-Mandelbrot

In the file, multi_mandelbrot.c, compute a program that outputs a PPM image of the mandelbrot set using multiple processes spawned with fork(). Your basecode implements the same command line arguments in with single_mandelbrot. You should use the same algorithm you used to compte single_mandelbrot.

Your program should use shared memory to split the computation of the image across 4 child processes. After each child completes, the parent process should save the result to a file using write_ppm.

$ ./multi_mandelbrot
Generating mandelbrot with size 480x480
  Num processes = 4
  X range = [-2.0000,0.4700]
  Y range = [-1.1200,1.1200]
Launched child process: 9150
Launched child process: 9151
9150) Sub-image block: cols (0, 240) to rows (0,240)
9151) Sub-image block: cols (240, 480) to rows (0,240)
Launched child process: 9152
9152) Sub-image block: cols (0, 240) to rows (240,480)
Launched child process: 9153
9153) Sub-image block: cols (240, 480) to rows (240,480)
Child process complete: 9150
Child process complete: 9152
Child process complete: 9151
Child process complete: 9153
Computed mandelbrot set (480x480) in 0.152178 seconds
Writing file: multi-mandelbrot-480-1649001405.ppm
A09 multi

Requirements and hints:

  • You should re-use your PPM functions from A06.

  • Allocate an array of pixels using shared memory and then save the final image using write_ppm. Use this example from class as a reference.

  • Print the pids and work tasks for each child.

  • Use fork() to create 4 child processes and wait() to wait for each to complete.

  • You should output the number of seconds needed to compute the image. Use this class example, matrix.c for an example.

  • Your output filename should have the format multi-mandelbrot-<size>-<timestamp>.ppm. The timestamp can be obtained by calling time(0).

  • Set a random seed to ensure that the color palette is different each time, e.g. srand(time(0))

  • In your README.adoc, compute images with sizes of 100, 400, 800, 1000, and 2000 using both your single process and multi process implementations. Record the number of seconds it takes to compute each image.

Cleaning up leaked shared memory files

If a program does not detatch and remove a shared memory file, the system can run out of shared memory resources. We can clean up these files manually.

To check for shared memory files on your system, run the command ipcs

$ ipcs -m

 shared Memory Segments _
key        shmid      owner      perms      bytes      nattch     status
0x00000000 4          alinen     644        41         0
0x00000000 5          alinen     644        41         0
0x00000000 6          alinen     644        41         0
0x00000000 7          alinen     644        41         0

To remove a shared memory file, run the command ipcrm -m <shmid>.

We have given you a script, shm_cleanup.sh, that will remove all shared memory files on your system.

$ ipcs -m

 Shared Memory Segments 
key        shmid      owner      perms      bytes      nattch     status
0x00000000 4          alinen     644        41         0
0x00000000 5          alinen     644        41         0
0x00000000 6          alinen     644        41         0
0x00000000 7          alinen     644        41         0

$ ./shm_cleanup.sh
$ ipcs -m

_ Shared Memory Segments _
key        shmid      owner      perms      bytes      nattch     status

3. Submit your work

Submit both your code, images, and a brief report containing your results in your README.

1) Push your code work to github

$ git status
$ git add .
$ git status
$ git commit -m "assignment complete"
$ git status
$ git push
$ git status