Chapter 10. Project: Virtual Timers

Many systems create multiple “virtual” timers from a single hardware timer. This chapter develops application-level virtual timers based on a single operating system timer. The project explores timers, signals and the testing of asynchronous programs with timed input. Special care must be taken in blocking and unblocking the signals at the right times. The project emphasizes careful, modular design by specifying a well-defined interface between the user-implemented virtual timers and the underlying timer facility.

Objectives

  • Learn about testing and timing

  • Experiment with POSIX interval timers

  • Explore implications of asynchronous operation

  • Use POSIX realtime signals

  • Understand timer implementation

Project Overview

This chapter’s project develops an implementation of multiple timers in terms of a single operating system timer. The project consists of five semi-independent modules. Three of these are created as objects with internal static data; the other two are standalone programs designed for driving the timers and for debugging output. Figure 10.1 shows the five modules and their relationships. A dashed arrow indicates communication through a pipe. A solid arrow signifies that a function in the source module calls a function in the target module.

The five timer modules to be created in this project.

Figure 10.1. The five timer modules to be created in this project.

Standard output of the testtime program is fed into standard input of the timermain program. The timermain program calls only functions in virtualtimers. The virtualtimers object calls functions in hardwaretimer and show. The show object, which is only for debugging, calls functions in virtualtimers.

The project design has two layers—a “hardware” level (hardwaretimer) and a virtual timer level (virtualtimers). The hardwaretimer layer encapsulates a single operating system timer that generates a signal when it expires. The underlying timer object can be either a POSIX:XSI timer or a POSIX:TMR timer. While not truly a hardware timer, it is treated as such. The object provides interface functions that hide the underlying timer from outside users. In theory, if the program has access to a real hardware timer, the underlying object can be this timer and the interface remains the same. The interface functions manipulate a single timer that generates a signal when it expires.

The virtualtimers object provides the core facilities for creating and manipulating multiple, low-overhead, application-level software timers. The virtualtimers object calls functions in the hardwaretimer to implement these software timers. The virtualtimers object also calls functions in the show object for logging and debugging.

The show object contains functions to display a running log of the timer operations during debugging. The show object calls functions from virtualtimers to obtain status information about the timers.

Each of the objects has a header file with the same name and a .h extension that contains prototypes for the functions accessible from outside the module. Any program that calls functions from one of these modules should include its corresponding .h file.

Two main programs are used for testing the timer objects. The first one, timermain, receives input from standard input and calls functions in the virtualtimers object. The timermain program might, for example, start a timer to expire after a given interval when it receives appropriate input. The timermain program calls only functions in the virtualtimers object.

It is critical to the debugging process that experiments producing incorrect results be precisely repeatable. Then, when a bug is detected, the programmer can fix the code and repeat the same experiment with the modified code. Experiments that rely on the timing of keyboard input are almost impossible to repeat. To solve this problem, the testtime program supplies input data through a pipe to timermain at precisely timed intervals. The testtime program reads lines from standard input and interprets the first integer on the line as a delay time. After waiting for this amount of time, testtime sends the rest of the input line to standard output. The testtime program then reads its next input line and continues.

This project chapter describes the implementation of virtual timers in stages. Section 10.2 introduces the data structures and gives examples of setting a single timer. Section 10.3 introduces the three objects and specifies how to handle the setting of a single timer with POSIX:XSI timers. Section 10.4 handles multiple active timers. Section 10.5 discusses some of the race conditions that can occur with multiple timers and ways to avoid them, and Section 10.6 discusses advanced timer issues in terms of POSIX:TMR timers. Section 10.7 introduces a simple timer application.

Simple Timers

Operating systems often implement multiple software timers that are based on a single hardware timer. A software timer can be represented by a timer number and an indication of when the timer expires. The implementation depends on the type of hardware timer available.

Suppose the hardware timer generates interrupts at regular short intervals called the clock tick time. The timer interrupt service routine monitors the time remaining on each timer (in terms of clock ticks) and decrements this time for each tick of the clock. When a timer decrements to 0, the program takes the appropriate action. This approach is inefficient if the number of timers is large or if the clock tick time is short.

Alternatively, a program can keep the timer information in a list sorted by expiration time. Each entry contains a timer number and an expiration time. The first entry in the list contains the first timer to expire and the time until expiration (in clock ticks). The second entry contains the next timer to expire and the expiration time relative to the time the first timer expires, and so on. With this representation, the interrupt service routine decrements only one counter on each clock tick, but the program incurs additional overhead when starting a timer. The program must insert the new timer in a sorted list and update the time of the timer that expires immediately after the new one.

Example 10.1. 

For each of the two implementation approaches described above, what is the time complexity of the interrupt handler and the start timer function in terms of the number of timers?

Answer:

Suppose there are n timers. For the first method, the interrupt handler is O(n) since all timer values must be decremented. The start timer function is O(1) since a timer can be started independently of the other timers. For the second method, the interrupt handler is usually O(1) since only the first timer value must be decremented. However, when the decrement causes the first timer to expire, the next entry has to be examined to make sure it did not expire at the same time. This algorithm can degenerate to O(n) in the worst case, but in practice the worst case is unlikely. The start timer function is O(n) to insert the timer in a sorted array but can take less than O(n) if the timer data is represented by a more complex data structure such as a heap.

If the system has a hardware interval timer instead of a simple clock, a program can set the interval timer to expire at a time corresponding to the software timer with the earliest expiration. There is no overhead unless a timer expires, one is started, or one is stopped. Interval timers are efficient when the timer intervals are long.

Example 10.2. 

Analyze the interrupt handler and the start timer function for an interval timer.

Answer:

The interrupt handler is the same order as the clock tick timer above. The complexity of starting the timer depends on how the timers are stored. If the timers are kept in a sorted array, the start timer function is O(n).

The first version of the project uses an interval timer to implement multiple timers, replacing the hardware timer by a POSIX:XSI ITIMER_REAL timer. When ITIMER_REAL expires, it generates a SIGALRM signal. The SIGALRM signal handler puts an entry in an event list sorted by order of occurrence. Each entry just contains a timer number giving a timer that expired.

Figure 10.2 shows a simple implementation of five software timers represented by the timers data structure. The individual timers (designated by [0] through [4]) are represented by long entries in the array active. An array entry of –1 represents a timer that is not active. The events array keeps a list of timers that have expired, and numevents holds the number of unhandled events. The running variable, which holds the timer number of the currently running timer, will be needed for later parts of the project.

The timers data structure with no timers active.

Figure 10.2. The timers data structure with no timers active.

Start a timer by specifying a timer number and an interval in microseconds. Figure 10.3 shows the data structure after timer [2] is started for five seconds (5,000,000 microseconds). No timers have expired, so the event list is still empty.

The timers data structure after timer [2] has been set for five seconds.

Figure 10.3. The timers data structure after timer [2] has been set for five seconds.

Just writing the information into the active array in Figure 10.2 is not enough to implement a timer. The program must set the ITIMER_REAL timer for 5,000,000 microseconds. On delivery of a SIGALRM signal, the program must clear the active array entry and insert an entry in the events array. Figure 10.4 shows the timers data structure after ITIMER_REAL expires.

The timers data structure after timer [2] expires.

Figure 10.4. The timers data structure after timer [2] expires.

Setting One of Five Single Timers

This section describes an implementation for setting one of five possible software timers, using the underlying process interval timer ITIMER_REAL. The main program takes the timer number and the timer interval (in microseconds) as command-line arguments and calls the timerstart function. The main program then waits for the timer to expire, prints out a message that the timer has expired, and exits.

The virtualtimers object

Implement the software timers in an object called virtualtimers. Use a static variable called timers of type timerdata_t to hold the internal timer data for the object as shown below.

#define MAXTIMERS 5
typedef struct timerdata_t {
   long active[MAXTIMERS];
   int events[MAXTIMERS];
   int numevents;
   int running;
} timerdata_t;

The members of timerdata_t have the following meanings.

active

is an array with an entry for each timer. Each entry holds the expiration time (in μ sec) relative to the starting time of the running timer. A negative value signifies that the timer is not active. (In this part only one timer is ever active.)

events

is an array with an entry for each timer that has expired and has not yet been removed. The entries contain timer numbers and appear in increasing order of expiration time. (There is at most one timer on the list for the program of this section.)

numevents

is the number of entries in the events array.

running

is the number of the timer that is running or –1 if none are active. The running timer is the one that is next to expire. It is the one whose expiration time causes the one real timer (set with sethardwaretimer) to generate a signal.

The integer representation of the time intervals simplifies the code but limits the length of the intervals to about 2000 seconds (a little more than half an hour) for 32-bit integers. This should be more than enough time for testing the algorithms of the project.

Place the timers data structure in virtualtimers.c along with the following functions that are callable from outside the object.

int getevent(int eventnumber);

Return the timer number associated with a particular entry in the events array. The eventnumber parameter specifies the position in the events array, which is indexed from 0. The getevent functions returns –1 if eventnumber is negative or greater than or equal to numevents.

int getnumevents(void);

Return the value of numevents.

int getrunning(void);

Return the timer number of the running timer or –1 if there is no running timer.

long getvalue(int n);

Return the current value of a timer n from the active array or –1 if the timer is not active or the timer number is invalid.

int removetop(void);

Remove the top event from events and return the event’s timer number or –1 if events is empty. This function is needed later when multiple timers are handled.

int timerinit(void);

Initialize the timers data structure as shown in Figure 10.2. The function also calls catchsetup of the hardwaretimer object and showinit of the show object. If successful, timerinit returns 0. If unsuccessful, timerinit returns –1 and sets errno.

void timerstart(int n, long interval);

Start timer n with the time interval given in microseconds. For this part, assume that no timers are active. The interval is the number of microseconds in the future after which the timer should expire. To start timer n, do the following.

  1. Remove timer n from the event list if it is there.

  2. Set running to timer n.

  3. Set active[n] to the appropriate time value.

  4. Start the interval timer by calling the sethardwaretimer function in the hardwaretimer object.

void timerstop(int n);

Stop timer n if it is active and remove the timer from events if it is there. This function is needed later when multiple timers are handled.

void waitforevent(void);

Wait until there is an event in events and then return without changing events. Do not use busy waiting, but instead, call waitforinterrupt from the hardwaretimer module.

The virtualtimers object also contains the private timerhandler function, which it passes to the hardware timer module by calling catchsetup in timerinit.

static void timerhandler(void);

Handle the timer signal. This function is called by the actual signal handler in hardwaretimer to maintain the timers structure when the real hardware timer expires. Do the following steps in timerhandler.

  1. Add the running timer to the end of events.

  2. Make the running timer inactive.

  3. Update the timers data structure.

  4. Reset the interval timer if there is an active timer. (There will not be one in the single-timer case.)

Since the hardwaretimer object handles the signals, it must contain the actual signal handler. The prototype of the signal handler may depend on the implementation and should not be part of the virtualtimers object. Since the timers must be manipulated when the signal is caught, this work should be done in the virtualtimers object. The real signal handler calls timerhandler to do this. Since timerhandler has internal linkage, the timerinit function passes a reference to it when calling catchsetup in the hardwaretimer object. The timerhandler is an example of a callback. Callbacks are frequently used by applications to request that a service call one of the application’s functions when some event occurs.

The hardwaretimer object

The hardwaretimer object contains code to handle a single “hardware” timer. The functions that are accessible from outside the object are as follows.

int blockinterrupt(void);

Block the SIGALRM signal. The blockinterrupt function returns 1 if the signal was already blocked and 0 otherwise.

int catchsetup(void (*handler)(void));

Set up a signal handler to catch the SIGALRM signal by calling sigaction. If successful, catchsetup returns 0. If unsuccessful, catchsetup returns –1 and sets errno. The handler parameter is the name of the function that does the work of handling the signal. The actual signal handler in hardwaretimer just calls the handler function. The virtualtimers object calls the function catchsetup to set up signal handling.

long gethardwaretimer(void);

Return the time remaining on the hardware timer if it is running or 0 if it is not running. If unsuccessful, gethardwaretimer returns –1 and sets errno. Use getitimer to implement this function.

int isinterruptblocked(void);

Return 1 if the SIGALRM signal is blocked and 0 otherwise.

void sethardwaretimer(long interval);

Start the ITIMER_REAL timer running with the given interval in microseconds. Call sethardwaretimer only when the timer interrupt is blocked or the interval timer is stopped. The interval parameter specifies the interval for setting the timer in microseconds. Use setitimer to implement this function.

void stophardwaretimer(void);

Stop the hardware timer if it is running. This function is harder to implement than it might seem. We discuss this later since it is not needed in this section.

void unblockinterrupt(void);

Unblock the SIGALRM signal.

void waitforinterrupt(void);

Call sigsuspend to wait until a signal is caught. The waitforinterrupt function does not guarantee that the signal was from a timer expiration. This function is normally entered with the timer signal blocked. The signal set used by sigsuspend must not unblock any signals that were already blocked, other than the one being used for the timers. If the main program has blocked SIGINT, the program should not terminate if Ctrl-C is entered.

Some of these functions are not needed until a later part of this project. The interface to the hardware timer is isolated in this file, so using POSIX:TMR timers or a different underlying timer than ITIMER_REAL only requires changing these functions. Define a header file called hardwaretimer.h that has the prototypes of the functions in the hardwaretimer object.

Main program implementation

Write a main program called timermain that initializes everything by calling timerinit and then loops, reading from standard input until an error or end-of-file occurs. Specifically, timermain does the following tasks in the loop.

  1. Read a pair of integers (a timer number and an interval in microseconds) from standard input.

  2. Call timerstart with these values.

  3. Call waitforevent.

  4. Print the return value of waitforevent to standard output.

Use scanf to read in the values from standard input.

Instrumentation of the timer code with show

Code with signal handlers and timers is hard to test because of the unpredictable nature of the events that drive the program. A particular timing of events that causes an error might occur rarely and not be easily reproducible. Furthermore, the behavior of the program depends not only on the input values but also on the rate at which input data is generated.

This section describes how to instrument the code with calls to a show function as a preliminary step in testing. This instrumentation is critical for debugging the later parts of the project. Two versions of the show function are presented here: one outputs to standard output and the other uses remote logging. This subsection explains what show does and how to use it in the program.

The prototype for show is as follows.

void show(int traceflag, const char *msg, long val1, long val2,
             int blockedflag);

If the traceflag is 0, show does nothing, allowing you to easily remove the debugging output. If traceflag is 1, the show function displays the message in the second parameter and the status of the timer data structure. The show function displays the val1 and val2 parameters if they are nonnegative. Usually, these parameters will represent a timer number and an interval in microseconds, but sometimes they will represent two timers. The blockedflag is 1 if the timer signal is supposed to be blocked when the call is made and 0 if the timer signal should not be blocked. It will be important to keep track of the blocking and unblocking of the signal in the complete timer implementation.

The virtualtimers file should have a traceflag global variable initialized to 1. Insert a call to showinit in the timerinit function of the virtualtimers module. Insert calls to show liberally throughout the virtualtimers module. For example, the first line of timerstart could be the following.

show(traceflag, "Timer Start Enter", n, interval, 0);

A call to start timer [3] for 1,000,000 microseconds might then produce the following output.

****  4.0067: Timer Start Enter 3 1000000 U(2,5.000) A:(2,5.000) (4,9.010) (1E 4)

The fields are as follows.

  • 4.0067 is the time in seconds since showinit was called.

  • The message states where the show function was called.

  • 3 is the timer being started.

  • 1000000 is the duration of the timer interval.

  • U indicates that the call was made with the interrupt unblocked.

  • (2,5.000) gives the currently running timer and its interval in seconds.

  • A:(2,5.000) (4,9.010) shows two active timers and their corresponding intervals.

  • (1E 4) indicates one event for timer [4].

Program 10.1 can be used with this project to display messages similar to the one above.

Example 10.1. show.c

A version of show that prints to standard output.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include "hardwaretimer.h"
#include "show.h"
#include "virtualtimers.h"
#define MILLION 1000000L

static double initialtod = 0.0;
static int maxtimers;
static double gettime(void);
static double timetodouble(long interval);

static double getrelativetime(void) {    /* seconds since showinit was called */
   return gettime() - initialtod;
}

static double gettime(void) {    /* seconds since January 1, 1970 as a double */
   double thistime = 0.0;
   struct timeval tval;

   if (gettimeofday(&tval, NULL))
      fprintf(stderr, "Failed to get time of day
");
   else
      thistime = tval.tv_sec + (double)tval.tv_usec/MILLION;
   return thistime;
}

static void showtimerdata(void) {       /* display the timers data structure */
   int i;

   printf("(%d,%.3f) A:", getrunning(),
      timetodouble(getvalue(getrunning())));
   for (i = 0; i < maxtimers; i++)
      if (getvalue(i) >= 0)
         printf("(%d,%.3f) ", i, timetodouble(getvalue(i)));
   printf(" (%dE", getnumberevents());
   for (i = 0; i < getnumberevents(); i++)
      printf(" %d", getevent(i));
   printf(")
");
}

static double timetodouble(long interval) {        /* microseconds to seconds */
   return (double)interval/MILLION;
}

/* ------------------------Public Functions --------------------------------- */
void show(int traceflag, const char *msg, long val1, long val2,
             int blockedflag) {    /* displays timers with message for evtype */
   int wasblockedflag;

   if (!traceflag)
      return;
   wasblockedflag = blockinterrupt();
   printf("**** %8.4f: ", getrelativetime());
   printf("%s ",msg);
   if (val1 >= 0)
      printf("%ld ", val1);
   if (val2 >= 0)
      printf("%ld ", val2);
   if (blockedflag)
      printf("B");
   else
      printf("U");
   if (blockedflag != wasblockedflag)
      printf("***");
   showtimerdata();
   fflush(stdout);
   if (!wasblockedflag)
      unblockinterrupt();
}

void showinit(int maxt) {      /* set initialtod to seconds since Jan 1, 1970 */
   initialtod = gettime();
   maxtimers = maxt;
}

Put the code of Program 10.1 in a separate file. Instrument the timer functions so that each time something of interest occurs, the program calls show with the appropriate parameters. For this part, just insert the following four lines.

  • In the first line of timerhandler insert the following.

    show(traceflag, "Timer Handler Enter", timers.running, -1, 1);

  • Before returning from timerhandler insert the following.

    show(traceflag, "Timer Handler Exit", timers.running, -1, 1);

  • Before the first line of timerstart insert the following.

    show(traceflag, "Timer Start Enter", n, interval, 0);

  • Before returning from timerstart insert the following.

    show(traceflag, "Timer Start Exit", n, interval, 0);

Test the program with a variety of appropriate inputs and observe the output of show. Remember that printf is not async-signal safe. The calls to show in timerhandler cause a problem if timermain also uses the standard I/O library without blocking the signals during the calls. The show function blocks the timer interrupt before producing any output to avoid this problem as well as to protect the shared timers data structure.

Program 10.2 gives an alternative implementation of show that uses the remote logging facility described in Appendix D.2. It avoids a possible buffer overflow by calling snprintfappend to add to the message. This function takes parameters similar to those of snprintf but appends to a string given by the first parameter. The second parameter is a limit on the total size of the buffer used to hold the string.

In this version, the showinit function opens a connection to the remote logger, using the default parameters. Each output message is associated with a generator string indicating the source of the message. The generator is just the timer gotten from the val1 parameter. The output message has the following fields separated by tabs so they can be displayed in a table.

  • The message from the msg parameter.

  • val1 (the timer).

  • val2 (a second timer or an interval).

  • The letter U if the blockedflag parameter is 0 and the letter B otherwise. If this does not correspond to the actual blocked state of the timer signal, this is followed by three asterisks as a warning.

  • The number of the currently running timer if any.

  • A list of all active timers, each being represented by an ordered pair consisting of the timer number and the remaining time relative to the running timer.

  • The number of events followed by the list of events.

Figure 10.9 on page 363 shows sample output from one window of the remote logger.

Example 10.2. showremote.c

A version of show that uses a remote logging facility.

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include "hardwaretimer.h"
#include "rlogging.h"
#include "show.h"
#include "virtualtimers.h"
#define MILLION 1000000L
#define MSGBUFSIZE 256

static double initialtod = 0.0;
static LFILE *lf;
static int maxtimers;
static double gettime(void);
static double timetodouble(long interval);

static void snprintfappend(char *s, size_t n, const char *fmt, ...) {
   va_list ap;
   int sizeleft;

   sizeleft = n - strlen(s) - 1;
   if (sizeleft <= 0)
      return;
   va_start(ap, fmt);
   vsnprintf(s + strlen(s), sizeleft, fmt, ap);
}

static void createlogstring(char *msg, int n) {       /* create string to log */
   int i;

   if (getrunning() >= 0)
      snprintfappend(msg, n, "	%d	", getrunning());
   else
      snprintfappend(msg, n, "		");
   for (i = 0; i < maxtimers; i++)
      if (getvalue(i) >= 0)
         snprintfappend(msg, n, "(%d,%.3f) ",
                 i, timetodouble(getvalue(i)));
   snprintfappend(msg, n, "	 (%dE", getnumberevents());
   for (i = 0; i < getnumberevents(); i++)
      snprintfappend(msg, n, " %d", getevent(i));
   snprintfappend(msg, n, ")
");
}

static double getrelativetime(void) {    /* seconds since showinit was called */
   return gettime() - initialtod;
}

static double gettime(void) {    /* seconds since January 1, 1970 as a double */
   double thistime = 0.0;
   struct timeval tval;

   if (gettimeofday(&tval, NULL))
      fprintf(stderr, "Warning, cannot get time of day
");
   else
      thistime = tval.tv_sec + (double)tval.tv_usec/MILLION;
   return thistime;
}

static double timetodouble(long interval) {        /* microseconds to seconds */
   return (double)interval/MILLION;
}

/* ------------------------Public Functions --------------------------------- */
void showinit(int maxt) {      /* set initialtod to seconds since Jan 1, 1970 */
   initialtod = gettime();
   maxtimers = maxt;
   lf = lopen(NULL, 0);
   if (lf == NULL)
      fprintf(stderr,"Cannot open remote logger
");
   else
      lsendtime(lf);
}

void show(int traceflag, const char *msg, long val1, long val2,
             int blockedflag) {         /* log timers with message for evtype */
   char genbuf[20];
   char msgbuf[MSGBUFSIZE];
   int wasblockedflag;

   if (!traceflag)
      return;
   wasblockedflag = blockinterrupt();
   if (val1 < 0)
      genbuf[0] = 0;
   else
      sprintf(genbuf, "Timer %ld", val1);
   snprintf(msgbuf, MSGBUFSIZE, "%8.4f: ", getrelativetime());
   snprintfappend(msgbuf, MSGBUFSIZE, "%s", msg);
   if (val1 >= 0)
      snprintfappend(msgbuf, MSGBUFSIZE, "	%ld", val1);
   else
      snprintfappend(msgbuf, MSGBUFSIZE, "%s", "	");
   if (val2 >= 0)
      snprintfappend(msgbuf, MSGBUFSIZE, "	%ld", val2);
   else
      snprintfappend(msgbuf, MSGBUFSIZE, "%s", "	");
   if (blockedflag)
      snprintfappend(msgbuf, MSGBUFSIZE, "%s", "	B");
   else
      snprintfappend(msgbuf, MSGBUFSIZE, "%s", "	U");
   if (blockedflag != wasblockedflag)
      snprintfappend(msgbuf, MSGBUFSIZE, "%s", "***");
   createlogstring(msgbuf, MSGBUFSIZE);
   lprintfg(lf, genbuf, msgbuf);
   if (!wasblockedflag)
      unblockinterrupt();
}

Using Multiple Timers

The potential interactions of multiple timers make their implementation more complex than that of single timers. All the times in the active array are specified relative to the start of the underlying ITIMER_REAL interval timer. Suppose that a program wants to set timer [4] for seven seconds and that two seconds have elapsed since it set timer [2] for five seconds. Use the following procedure.

  1. Find out how much time is left on the real timer. (Call gethardwaretimer.)

  2. Find the start of the real timer relative to the currently running timer by subtracting the time left on the real timer from the timer value of the running timer. (Use getrunning.)

  3. Calculate the time of the timer to be set relative to the start time by adding the relative start time from step 2 to the requested time.

Figure 10.3 on page 346 shows the timers data structure after a program sets timer 2 for five seconds (5,000,000 microseconds). Suppose that two seconds later the program sets timer [4] for seven seconds (7,000,000 microseconds). Figure 10.5 shows the timers data structure after timer [4] is set. The program calls gethardwaretimer and finds that there are three seconds left (3,000,000 microseconds) on the interval timer, so two seconds (5,000,000 - 3,000,000 microseconds) have elapsed since it set timer [2]. The program then computes the time for timer [4] relative to the start of the original setting of the real timer as nine seconds (2,000,000 + 7,000,000 microseconds).

The timers data structure after timer 4 has been set.

Figure 10.5. The timers data structure after timer 4 has been set.

The running timer is the same in Figure 10.3 and Figure 10.5 because timer [4] expires after timer [2]. The program did not change the running timer designation or reset the timer in this case. Continuing the situation of Figure 10.5, suppose that a program wants to set timer [3] for one second and a call to gethardwaretimer shows that the real timer has two seconds left. Timer [3] should expire before the real timer is scheduled to expire, so the program must reset the real timer. Figure 10.6 shows the situation after the program sets timer [3]. The program resets the real timer to expire in one second and adjusts all of the other times in active. The new times are relative to the start time of timer [3] rather than to that of timer [2] (three seconds ago), so the program subtracted three seconds from each of the active times.

The timers data structure after timer [3] has been set.

Figure 10.6. The timers data structure after timer [3] has been set.

Figure 10.7 shows the situation a little over a second after timer [3] was set. Timer [3] expires and timer [2] becomes the running timer. All the times are readjusted to expire relative to timer [2].

The timers data structure after timer [3] expires.

Figure 10.7. The timers data structure after timer [3] expires.

Figure 10.8 shows the situation two seconds later. Timer [2] expires and timer [4] becomes the running timer.

The timers data structure after timer [2] expires.

Figure 10.8. The timers data structure after timer [2] expires.

Setting multiple timers

Modify the timerstart function and add a timerstop function to handle all of the cases of timers being set while other timers are active. At any moment, each timer is either active or inactive. An active timer cannot appear in events, but it is added to events when it expires. If any of the timers is active, exactly one of them is running. The running timer is the one that is next to expire. Its expiration time has been used in sethardwaretimer, so a signal is generated when its time expires.

How starting and stopping should affect events is an arbitrary implementation decision. The implementation outlined here removes an event corresponding to the timer to be started or stopped if one is there. This choice ensures that no timer is represented by more than one event in events, so events can be declared to be the same size as active. The bound on events simplifies the implementation.

With multiple timers active, timerhandler must update the timers data structure by subtracting active[running] from all active times. If the time becomes 0, the corresponding timer has expired and that timer number should be placed in events and made inactive. This method handles multiple timers expiring at the same time.

Section 10.3 handled the case of starting a timer when no timer is active. A similar case is the one in which the timer to be started is already active but all other timers are inactive.

Suppose some other timer is the running timer when a timer is started. If the timer to be started expires after the running timer, only one entry in the timers data structure needs to be modified. However, if starting this timer causes it to expire before the currently running timer, the interval timer must be reset. The entries in the active array must also be adjusted relative to the starting time of the new running timer. To make the adjustment, decrement the active times by the time that the currently running timer has been active (runtime). Use gethardwaretimer to find the remaining time on the interval timer and calculate runtime = active[running] - remaining.

When the running timer changes, take the following actions.

  1. Remove the new timer from events if it is there.

  2. Adjust all active times by runtime.

  3. Set a new running timer.

  4. Start the interval timer by calling sethardwaretimer.

The case in which the timer to be started is the running timer can be treated either as a special case of the above or as a separate case.

A call to timerstop for a timer that is not active just removes the timer from events. If the timer was active but not running, set it to be inactive. The interesting case is that of stopping the running timer. This case is similar to the case of starting a timer that becomes the running timer because the timers data structure needs to be updated by runtime and a new running timer has to be selected.

In this part, the program should handle all combinations of starting and stopping timers as well as removing events from the event list. Enhance the timerstart and timerhandler functions appropriately and write the functions removetop and timerstop, which were not needed before. Insert appropriate calls to show.

Modify timermain so that it interprets a negative interval as a command to stop the timer. Instead of waiting for an event in the main loop, remove and display all events without blocking before waiting for additional input.

Example 10.3. 

What happens if scanf is used for standard input in this version of timermain?

Answer:

Neither scanf or sscanf are guaranteed to interact correctly with signals. The scanf function may indicate end-of-file when a signal is caught by the process. Use the readline function from Program 4.1 on page 95. This function detects end-of-file correctly and is not affected by signals. You can then use sscanf to parse the input line (after blocking the signals).

Example 10.4. 

Why can the single timer of Section 10.3 use scanf without a problem?

Answer:

The program waits for the signal to be caught before calling scanf.

Testing with multiple timers

Even code instrumented by show is difficult to test systematically, since the action of the program depends on the speed of the input typing. One approach to this problem is to use a driver, testtime, to generate the input for the program. Program 10.3 shows the testtime program. It must be linked to the hardwaretimer object.

As with any filter, testtime reads from standard input and writes to standard output. The input consists of lines containing three integers, n, m and p. The filter reads in these three integers, waits n microseconds, and then outputs m and p on a single line. If m < 0, testtime exits after waiting n microseconds. The testtime program ignores any characters on the line after the three integers, so a user can add comments to the end of each input line.

Example 10.5. 

Suppose testtime receives the following input.

1000000  2  5000000 Timer 2 expires at time 6
2000000  4  7000000 Timer 4 expires at time 10
1000000  3  1000000 Timer 1 preempts 2 to expire at time 5

The testtime program waits one second and outputs the following line.

2 5000000

The program then waits two more seconds and outputs the following line.

4 7000000

The program then waits one second and outputs the following line.

3 1000000

Example 10.6. 

Suppose the three lines in Example 10.5 are in the file timer.input and you execute the following command. What happens?

testtime < timer.input | timermain

Answer:

After getting the third line of the file at time 4 seconds, timermain detects end-of-file when testtime exits. This occurs before any timers expire. We can fix this problem by adding the following line to timer.input.

7000000 -1 1000000 Everything done 6 units from now

Example 10.3. testtime.c

The program testtime.

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include "hardwaretimer.h"

static int timerexpired = 0;

static void myalarm() {
   timerexpired = 1;
}

int main(int argc, char *argv[]) {   /* Test the hardware timer and prototype */
   long interval;
   int n1;
   int n2;

   if (argc != 1) {
      fprintf(stderr, "Usage: %s
", argv[0]);
      return 1;
   }
   catchinterrupt(myalarm);

   for( ; ; ){
      if (scanf("%ld%d%d%*[^
]", &interval, &n1, &n2) == EOF)
         break;
      if (interval <= 0)
         break;
      blockinterrupt();
      sethardwaretimer(interval);
      while (!timerexpired)
         waitforinterrupt();
      timerexpired = 0;
      if (n1 < 0)
         break;
      printf("%d %d
", n1, n2);
      fflush(stdout);
      fprintf(stderr, "%d %d
", n1, n2);
   }
   return 0;
}

If the 4-line file described in Example 10.5 and Exercise 10.6 is used as illustrated, the command causes timer [2] to start 1 second after execution begins and to expire five seconds later (at time 6). Two seconds later (at time 3), timer [4] starts and expires in seven seconds (at time 10). One second later (at time 4), timer [3] is set to expire in one second (at time 5). This is exactly the situation illustrated in Figure 10.6 on page 358.

Figure 10.9 displays the output generated for this input by Program 10.1, using an appropriately instrumented implementation of virtualtimers. Figure 10.10 displays the corresponding output generated by Program 10.2.

Example 10.9. The output generated by Program 10.1.

****   0.0001: Initialize U(-1,-0.000) A: (0E)
****   0.9975: Start Enter 2 5000000 U(-1,-0.000) A: (0E)
****   0.9976: None Running 2 5000000 B(-1,-0.000) A: (0E)
****   0.9977: Start Exit 2 5000000 U(2,5.000) A:(2,5.000) (0E)
****   3.0072: Start Enter 4 7000000 U(2,5.000) A:(2,5.000) (0E)
****   3.0073: Start Another Running 4 2 B(2,5.000) A:(2,5.000) (0E)
****   3.0074: Start Running Used 4 2009705 B(2,5.000) A:(2,5.000) (0E)
****   3.0075: Start Running Expires First 4 B(2,5.000) A:(2,5.000) (4,9.010) (0E)
****   4.0173: Start Enter 3 1000000 U(2,5.000) A:(2,5.000) (4,9.010) (0E)
****   4.0174: Start Another Running 3 2 B(2,5.000) A:(2,5.000) (4,9.010) (0E)
****   4.0175: Start Running Used 3 3019778 B(2,5.000) A:(2,5.000) (4,9.010) (0E)
****   4.0176: Start This Expires First 3 B(3,1.000) A:(2,1.980) (3,1.000) (4,5.990) (0E)
****   5.0269: Handler Start 3 1000000 B(3,1.000) A:(2,1.980) (3,1.000) (4,5.990) (0E)
****   5.0271: Handler Setting Hardware 2 980222 B(2,0.980) A:(2,0.980) (4,4.990) (1E 3)
****   5.0272: Handler Exit B(2,0.980) A:(2,0.980) (4,4.990) (1E 3)
****   6.0170: Handler Start 2 980222 B(2,0.980) A:(2,0.980) (4,4.990) (1E 3)
****   6.0172: Handler Setting Hardware 4 4009705 B(4,4.010) A:(4,4.010) (2E 3 2)
****   6.0173: Handler Exit B(4,4.010) A:(4,4.010) (2E 3 2)
****  10.0369: Handler Start 4 4009705 B(4,4.010) A:(4,4.010) (2E 3 2)
****  10.0371: Handler Setting Hardware 4 B(4,-0.000) A: (3E 3 2 4)
****  10.0372: Handler Exit B(4,-0.000) A: (3E 3 2 4)
The output generated by Program 10.2.

Figure 10.10. The output generated by Program 10.2.

A Robust Implementation of Multiple Timers

What happens if a SIGALRM signal is delivered during execution of the timerstart function? Both the timerhandler and the timerstart functions modify the timers data structure, a shared resource. This is the classical critical section problem for shared variables, and care must be taken to ensure that the timers data structure is not corrupted. It is difficult to determine if such a problem exists in the code by testing alone. The events that might cause corruption of the data structure are rare and usually would not show up during testing. If such an event occurred, it would not be easily repeatable and so there might be little information about its cause.

A race condition occurs when the outcome of a program depends on the exact order in which different threads of execution execute statements. The timerstart function is executed by the main thread of execution. That same thread executes timerhandler, but the thread that generates the SIGALRM signal determines when the timer expires. You can prevent race conditions of this type by ensuring that the critical sections are executed in a mutually exclusive manner.

You must analyze the problem to determine where the critical sections are. In this case, the analysis is simple since there is only one global variable, the timers data structure. Any function that modifies this structure must do so at a time when the SIGALRM signal handler may not be entered. The simplest approach is to block the SIGALRM signal before modifying the timers data structure.

Just blocking SIGALRM may not be sufficient. What happens if the interval timer expires during the execution of the timerstart function and SIGALRM is blocked? The timerstart function might make a new timer the running timer and reset the interval timer. Before the timerstart function terminates, it unblocks SIGALRM. At this point, the signal is delivered and the handler assumes that the new timer had expired. Although this sequence of events is extremely unlikely, a correctly working program must account for all possibilities. Exercise 10.7 shows another problem.

Example 10.7. 

Describe a sequence of events in which the timerstop function could fail even if it blocked the signal on entry and unblocked it on exit.

Answer:

The timerstop function blocks the SIGALRM signal. The timer to be stopped then expires (i.e., the interval timer generates a signal). This signal is not immediately delivered to the process, since the signal is blocked. The timerstop function then starts the interval timer corresponding to the next timer to expire. Before it returns, the timerstop function unblocks the signal and the signal is delivered. The signal handler behaves as if the running timer just expired, when in fact a different timer had expired.

The simplest solution to the problem described in Exercise 10.7 is to modify the hardwaretimer module. The stophardwaretimer function (which should be called with the SIGALRM signal blocked) should stop the timer and check to see if the SIGALRM signal is pending by using sigpending. If it is, the stophardwaretimer function removes the signal either by calling sigwait or by ignoring it and catching it again. The sethardwaretimer function can solve a similar problem by calling stophardwaretimer.

Example 10.8. 

How would you test to see if you solved this problem correctly?

Answer:

This cannot be done just by simple testing, since the problem occurs only when a timer expires in a narrow window. To test this, you will have to make the timerstop take some extra time.

Example 10.9. 

What would happen if you put a call to sleep(10) in timerstop to increase the chance that the error would occur?

Answer:

The sleep function might be implemented with SIGALRM, so sleep should not be called from a program that catches SIGALRM. The program has unpredictable results. The nanosleep function does not interact with SIGALRM and could be used in timerstop.

Program 10.4 is a function that can be used to waste a number of microseconds by busy waiting. It calls gettimeofday in a loop until the required number of microseconds has passed.

Example 10.4. wastetime.c

A function that does busy waiting for a given number of microseconds.

#include <stdio.h>
#include <sys/time.h>
#define MILLION 1000000L

int wastetime(int maxus) {               /* waste maxus microseconds of time */
    long timedif;
    struct timeval tp1, tp2;

    if (gettimeofday(&tp1, NULL)) {
        fprintf(stderr, "Failed to get initial time
");
        return 1;
    }
    timedif = 0;
    while (timedif < maxus) {
        if (gettimeofday(&tp2, NULL)) {
            fprintf(stderr, "Failed to get check time
");
            return 1;
        }
        timedif = MILLION*(tp2.tv_sec - tp1.tv_sec) +
                  tp2.tv_usec - tp1.tv_usec;
        if (timedif < 0)
            break;
    }
    return 0;
}

Analyze the timerstart and timerstop functions and modify the implementation of Section 10.4 so that the timers are handled robustly. Devise a method of testing to verify that the program works correctly. (The test will involve simulating rare events.)

POSIX:TMR Timer Implementation

POSIX:TMR timers have several advantages over POSIX:XSI timers. A program can create several POSIX:TMR timers for a given clock such as CLOCK_REALTIME. The timers have a potentially greater resolution since values are given to the nearest nanosecond rather than the nearest microsecond. The program can specify which signal is delivered for each timer, and the signal handler can determine which timer generated the signal. Also, the signals generated by the timers are queued, and the program can determine when signals have been lost due to overruns.

Several implementations of multiple timers of Section 10.4 with POSIX:TMR timers are possible. The simplest method is to use one timer and make minor changes in the data types to accommodate the higher resolution. Alternatively, a separate POSIX:TMR timer can implement each software timer. Starting and stopping a timer and handling the timer signal are independent of the other timers, so the only shared structure is the event queue. The virtualtimers and hardwaretimer object might have to be reorganized. There may be a limit to the number of timers that are supported for each process given by the constant TIMER_MAX. If the number of timers needed is small, this method would be the easiest to implement. A third approach is to use a single POSIX:TMR timer but modify the method of implementation to make the timing more accurate.

One of the problems with the original timer implementation of this chapter is that there can be a significant amount of timer drift, as discussed in Section 9.6. This drift can be virtually eliminated by the use of absolute time rather than relative time. Instead of storing the times relative to the running timer in the active array, store the absolute time of expiration. This approach will probably require 64 bits for each entry, perhaps a struct timeval or struct timespec. Alternatively, use a long long to store the number of microseconds or nanoseconds since the Epoch. This has the advantage of simplifying comparisons of time, but times must be converted to a struct timespec or struct timeval when timers are set.

mycron, a Small Cron Facility

The cron facility in UNIX allows users to execute commands at specified dates and times. This facility is quite flexible and allows regularly scheduled commands. It is implemented with a cron daemon that processes a file containing timing and command information.

Implement a simplified personal cron facility called mycron. Write a program that takes one command-line argument. The argument represents a data file containing time intervals and commands. Each line of the data file specifies a command and the frequency at which that command is to be executed. The lines of the data file have the following format.

interval command

The interval argument specifies the number of seconds between execution of instances of the command. The command argument is the command to execute with its arguments.

  1. Implement the preceding cron facility, assuming that none of the intervals in the cron data file are longer than the maximum interval that the timers can handle (about 30 minutes). Call the executable mycron.

  2. Handle the case in which the intervals can be arbitrarily large. Assume that the number of seconds in the interval will fit in a long. Try to do this without modifying the timer functions.

  3. Find a way to adjust the starting times so that if two commands have the same interval, they will not always be executing at the same time.

Additional Reading

An array representation for timers works well when the number of timers is small. Consider using a priority queue for the timers and a linked list for the events. “Hashed and hierarchical timing wheels: Data structures for efficient implementation of a timer facility” by Varghese and Lauck [128] describes alternative implementations. The POSIX Rationale section on Clocks and Timers [51] provides an excellent discussion of the issues involved in implementing timers at the system level. Aron and Drushel [5] discuss system timer efficiency in “Soft timers: efficient microsecond software timer support for network processing.”

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset