Measuring Program Execution Time

Two basic mechanisms to record the passage of time:

• Interval Counting, which is based on a low frequency time that periodically interrupts the procesor. The operating system uses the time to record the cumulative time used by each process and maintains counts of the amount of user time and the amount of system time used by each process. There are libraries functions for this time (linux) and clock (time.h, ANSI C). We can compute the total time between two different points in a program execution by making two calls to times and computing the difference of the return values. Disadvantage: The interval accounting scheme makes no attempt to resolve time more finely than the time interval. Interval counting is only useful for measuring relatively long computations-- 100,000,000 clock cycles or more and is too coarse-grained to use for any measurement having duration of less than 100 ms.
• Cycle Counters, which is based on a counter that is incremented every clock cycle. The timer is a special register that gets incremented every single clock cycle. Special machine instructions (rdtsc for "read time stamp counter") can be used to read the value of the counter. Cycle counters provide a very precise tool for measuring the time that elapses between two different points in the execution of a program. The disadvantage is that they do not keep track of which process uses those cycles or whether the procesor is operating in kernel or user mode. Context switching and cache operations cause extreme variation in execution time. To overcome this, K-best measurement scheme is proposed but it is reasonably robust for measuring durations shorter than the timer interval.

Process Scheduling and Timer Interrupts: computers have an external timer that periodically generates an interrupt signal to the processor. The spacing between these interrupt signals is called the interval time. When a timer interrupt occurs, the operating system scheduler can choose to either resume the currently executing process or to switch to a different process. This interval time must be set short enough to ensure that the processor will switch between tasks often enough to provide the illusion of performing many tasks simutaneously. Typical timer intervals range between 1 and 10 milliseconds.

Kernel operation (in kernel mode) such as handling page faults, input, or output is considered part of each regular process rather than a separate process. When the scheduler switches from process A to process B, it must enter kernel mode to save the state of process A (still considered part of process A) and to restore the state of proces B (considered part of proces B).

Looking into the future:

• Process-specific cycle timing. All that required is to store the count as part of the process' state.
• Variable Rate Clocks. Power consumption is directly proportional to the clock rate,and to reduce power consumption, future systems will vary the clock rate.