Due Dates and Times:       (See the Course Calendar.)

Summary:

You are to set up a test framework to measure the execution time demand of another program, using the subtractive method. You will test it using a solution to the gizmo control program,

This is a team assignment. You may work with one or two other people. However, for variety, if you worked in a team on the last assignment you are required to choose a new partner for this one.

• Learn to measure the execution time demand of a subsystem, by indirect (subtractive) measurement.
• Experience the difficulties and subtleties of writing a benchmark program
• Appreciate how the implementation decisions in different gizmo controllers result in different CPU demands.
• Understand the practical meaning of the abstract concept of execution time demand

1. (preliminaries) Package up your solution to the gizmo controller assignment and deliver it to me (baker@cs.fsu.edu) in a standard format that can be compiled and used by other students. That is, send me a file gizmo.tgz that anyone can compile and execute using the following sequence of commands:

   mkdir gizmo
   cd gizmo
   tar xvpf ../gizmo.tgz
   make gizmo
   ./gizmo
   

   I will post all of these on the course website, each in a separate directory, for everyone in the class to access.

   Before sending it to me, modify the code if necessary, to ensure that it can be used for the time demand measurement experiment you will be doing in step 2 below. Specifically, make certain that:

   • All time-critical threads (if you used a cyclic executive, there will be just one, corresponding to your main program) are scheduled at high enough priority to be able to preempt another process running at priority sched_get_priority_max (SCHED_FIFO)-4.
   • The program will run continously for at least 5 minutes without stopping, so that you have time start up and run another program in the background.
   • The program does not require keyboard input to start, so that it can be started an run from a shell script or exec'ed by another program without any special provision for input. That is, set it up with some default text that will display if there is no user input. If you have debugging output code, you should suppress that.
   • The program can be killed successfully by the SIGINT signal.

2. Write and debug a program named timeit that will measure the CPU load of an executable program that is provided as a command line parameter, and produce a file gizmo.pts containing output that is suitable for input to the gnuplot program, in the format that will be described below. The shell script may call programs that you provide, as well as the program gizmo. You should provide a Makefile so that a person can execute make timeit to build whatever programs are needed in order to execute timeit. That is, one should be able to test a gizmo controller and then view a plot of the processor load by the following sequence of commands in the bash shell:

   mkdir gizmo
   cd gizmo
   tar xvpf ../gizmo.tgz
   make gizmo
   cd ..
   mkdir timeit
   cd timeit
   tar xvpf ../timeit.tgz
   make timeit
   cd ..
   mkdir test
   cd test
   ../timeit/timeit ../gizmo/gizmo
   ../plotload
   gv load.eps
   

   where the file plotload above is the following shell script:

   #!/bin/sh
   gnuplot << EOF
   set terminal postscript enhanced eps "Times-Roman" 20
   set data style linespoints
   
   set output "load.eps"
   set yrange [0:1.1]
   plot \
        "gizmo.pts" using 1:2 title "interference" with lines lt 1 lw 1,\
   EOF
   

   The ../timeit/timeit ../gizmo/gizmo step should not take longer than 5 minutes of real time to run.

   The output of timeit should be a text file containing data in two columns, suitable for input to gnuplot, as follows:

   1. value of D (see below)
   2. maximum observed gizmo load over all intervals of length D

   The values in column 1 should be numbers of milliseconds, unique and in increasing order. The values in column 2 should be in the range 0.0 to 1.0, and should be the maximum observed interfering load over several intervals of the length given in the first column.

3. Use the above to measure the processor load of three or more of the student gizmo controllers posted from step (1) above. Compare your results with other students. Try to understand any differences you see.

4. Turn in the following:

   1. a print-out of your implementation code for timeit
   2. print-outs of the graphs generated for 3 or more gizmo programs, with the name of the corresponding gizmo controller version (from the class web page)
   3. an electronic copy of the file timeit.tgz above

1. The program timeit will need to use fork() and exec() calls to run the gizmo program. If you have not used these before, as me for help.

2. Do not expect to be able to follow the subtractive measurement scheme in the class notes exactly, since this is a slightly different problem. Specifically, I recommend the following variation from the example - with tasks T₁ (pink, foreground) and T₂ (blue, background) -- in the notes. Task T₁ should run at the top realtime (SCHED_FIFO) priority, and task T₂

   should run at the next-to-highest priority.
   1. To calibrate T₂:
      Let T₂ repeatedly read the clock, until fixed amount of clock time has elapsed, counting the number of iterations as it goes. At the end of of the time interval, it divides the length of the interval by the number of iterations to get the average execution time per iteration, A.
   2. To measure the demand of T₁:
      Repeat the following, for a series of values D = 1 ms .. 100 ms.
      • Repeat the following, ⌊(1000 ms) / (D)⌋ times. (That is, more iterations for shorter intervals.)
        1. Exec T₁
        2. Sleep long enough for T₁ to set its priority higher than T₂
        3. Repeatedly read the clock, until D_i time has elapsed, counting the number of iterations, N_i.
        4. Multiply the iteration count N_i by the average execution time per iteration A computed in step (a) above, and subtract from D_i to find the approximate demand of T₁ in this sample interval.
        5. Divide the demand computed above by D_i, to obtain the load
        6. If this is higher than the previously measured loads for other intervals of length D, record it as the new maximum.
      • Print out the values of D tested and the corresponding maximum load values measured.

3. Please report progress and problems, so that I can provide advice in time to be of help.

4. Do not expect a time extension on this assignment. Based on experience with the last assignment, I have already added an extra time margin.

Assessment:

The solutions will be judged primarily on how well they perform, including repeatability of the results. They will also be judged on the simplicity, readability, clarity, and documentation of the implementation code.