Understanding Timer Management

Timers are fundamental to real-time systems and virtually all real-time kernels implement some form of timer management so that tasks can pause, issue time-outs, and the like. This article presents some basic ways in which timers can be managed.

Timer Management Explained

Consider a preemptive multi-tasking system in which it is desired to allow tasks to suspend execution for a given number of milliseconds. This can be accomplished in a variety of ways. A simple approach is described below.

Timer Management by Table

A simple approach would be to maintain a table; each entry would contain a timer count, and a pointer to the task's tcb. The "timer count" would be decremented each time the timer isr is entered. For example, suppose a task wants to suspend for 50 ms and the timer isr is entered every 10 ms; the timer count would be 5, since after 5 times through the timer isr, 50 ms would have transpired. A task would request to be suspended for a certain number of ms with a call as shown below.

	while (TRUE) {
		pause(50L);
		readData();
		displayData();
	}

The call to pause requests that the task suspend for 50 ms. The pause would do the following.

1. Find an unused table entry and save the active task's tcb and the timer count (which for a 10 ms timer isr rate would be 5 for a 50 ms timer).
2. Suspend the task.

The pause function might look like this.

int pause(long timerCount)
{
	int i;

	disableInterrupts();

	for (i = 0; i < NUM_TIMERS; i++) {
		if (TimerTable[i].inUse == FALSE) {
			TimerTable[i].inUse = TRUE;
			TimerTable[i].timerCount = timerCount;
			TimerTable[i].tcb = ActiveTcb;
			break;
		}
	}

	enableInterrupts();
}

Note that interrupts must be disabled, otherwise another task might preempt the active task and grab the same entry. See time-dependent errors for details.

The timer isr must also detect when a timer has expired and schedule the suspended task to run. A fragment of the timer isr might look like this.

interrupt timerIsr(void)
{
	int i;

	for (i = 0; i < NUM_TIMERS; i++) {
		if (TimerTable[i].inUse == FALSE) continue;
		if (TimerTable[i].timerCount-- == 0) {
			TimerTable[i].inUse = FALSE;
			scheduleTask(TimerTable[i].tcb);
		}
	}

	/* More timer isr code here... */
}

Note that the timer isr code above does not handle the case where a timer for a higher priority task expires. For example, if lower priority taskA is interrupted to run the timer isr, and the timer isr determines that a timer for higher priority taskB has expired, then taskB must not only be scheduled - the timer isr must also return to taskB, not taskA, since taskB is of a higher priority, which can be effected as follows.

1. Schedule taskA to run again (i.e., add taskA to the ready queue according to its priority.)
2. Switch to taskB's stack. (Note that since a task is suspended via software interrupt and resumed by returning from interrupt that simply switching to taskB's stack in the timer isr and executing an IRET will resume taskB. See a previous article for details.)

To accommodate this, the timer isr code would be modified as shown below.

interrupt timerIsr(void)
{
	int i;

	for (i = 0; i < NUM_TIMERS; i++) {
		if (TimerTable[i].inUse == FALSE) continue;
		if (TimerTable[i].timerCount-- == 0) {
			TimerTable[i].inUse = FALSE;
			scheduleTask(TimerTable[i].tcb);
			if (TimerTable[i].tcb->pri < ActiveTcb->pri) {
				scheduleTask(ActiveTcb);
				switchStacks(TimerTable[i].tcb);
			}
		}
	}

	/* More timer isr code here but local variables cannot be
	referenced, since the stack may have been changed.*/
}

Problems with the Timer Table Method

Using a table to manage timers has the following problems.

1. Since the table is static, only a finite number of timers are allowed.
2. Each time through the timer isr, the timer table must be scanned. As the timer table increases in size, the time spent in the timer isr increases which adds overhead to the system.

These problems can be overcome by using a queued differential timer mangement scheme.

Queued Differential Timer Management

The queued differential timer management approach uses a linked list instead of a table, thus eliminating the first problem noted above, and differential timer management is employed to solve the second problem, since no matter how many pending timers are present, only the first timer in the list is decremented.

Concluding Remarks

This article has only touched the surface concerning this subject as there are many ways in which timer management can be effected, and many other areas for discussion (e.g., the system impact of many pending timers expiring all at once, etc.) If you have interest in more depth articles on this subject, please send us your comments.

We welcome comments. Let us know what subjects you would like written up. Send comments to mike@Ticsrealtime.com