CSC 213, Fall 2006 : Schedule : Lab 4

Lab 4: Signals and Timers

Goals: This lab exercise provides experience with system timers and signals.

Credit: The lab is based on Lab Exercise 6.1 in Operating Systems, Third Edition by Gary Nutt, Addison-Wesley/Pearson Education, 2004.

Reading: 

• Lab 6.1 (Nutt, p. 232-236) provides general background on timers and outlines a framework for the use of signals and timers in programs.
• signal-1.c, an example of using signals and timers.  We will go over this program at the beginning of our lab meeting.

Collaboration: You will complete this lab in teams of 2 and 3, as assigned by the instructor. 

Basic Problem: Determine the time required to perform a quicksort of 10000, 20000, 40000, 80000, and 160000 items in both a single-process context and in a multiple-process context.

Guidelines for each program:

• Each collection of timings should use three timers:

  • ITIMER_REAL is used to determine overall elapsed time,
  • ITIMER_VIRTUAL is used to determine time for the specific process, and
  • ITIMER_PROF is used to determine time for the specific process plus time of the OS related to this process.

• You may use either my implementation of quicksort or your own from Lab 1.  Either implementation should be properly attributed. You can find my code in the directory ~/davisjan/csc/213/examples/quicksort/.

• The quicksort should be performed on an array of random data.

PART A: due Friday, September 22

1. As a base line, a first program should set the three timers indicated above, perform a quicksort, and retrieve processing times in a single-process environment. This program should not include any fork or signal calls. Also, timing should not include the time required to initialize the array.

   This first program may perform the timing, quicksort, and printout for a single array size, with the program rerun for each of the array sizes given above. Alternatively, the program may call the timing, quicksort, and printout steps within a loop to handle all array sizes with a single execution of the program.

2. Modify the program ~davisjan/csc/213/examples/signal-1.c, so that the child process computes the amount of time required for each quicksort that it performs. The parent process should do no work, but should print its own timings for each period of time that the child spends computing.  As with the baseline program, timing should not include the time required to initialize arrays.

3. Extend the second program to obtain a program that spawns two processes, each of which sets a timer, performs a quicksort, and prints its own processing times. In this third program, each child will do its own processing and timing. The parent process will also perform quicksort and print its own processing times. If you wish, you may use Nutt's program outline from lab exercise 6.1, p. 237-239, as a base.

Work to be turned in:

• Part A: programs 1 and 2, as described above.
• Part B: program 3, as described above.
• You may turn in both part A and part B on Friday, September 22 if you prefer.
• For each program, use the script command to list the program and to execute one or more test runs for the required array sizes.
• In your commentary on correctness, explain the differences in results that you see for different array sizes and configurations of processes.

Janet Davis (davisjan@cs.grinnell.edu)