An efficient scheduler can make the difference
John is an embedded-systems developer who can be contacted at john@jptechnical .demon.co.uk.
Hardware limitations on a small data logger I was designing meant that three interrupt sources were fed into the microcontroller via one interrupt pin. The microcontroller at issue was the Texas Instruments MSP430C337, which has outstandingly low-power consumption. But experience revealed that even with the maximum clock input of 1.8 MHz at 3.3V supply, it was not terribly quick. One of the interrupt sources was a UART requiring reasonably fast servicing, the second was in response to changes in the modem control lines of the associated RS232 port. The third was the interrupt/busy line from an ATA PC card controller. The modem control lines had less priority than the UART, while the PC card interrupt had no timing requirements at all and could simply wait until the processor time had time to deal with it.
Because there are three sources on one pin, the initial interrupt code has to respond fast enough to determine the interrupt source, clear that source so other interrupts can get through, then jump to the relevant handler. There is one handler for each interrupt source. At some early stage, at least before entry to the handler, global interrupts need enabling to permit other interrupts. Since the handlers may be slow, a second interrupt might occur before the first has terminated. Thus, ideally, everything should be reentrant.
A single high-priority hardware interrupt needs to trigger a number of varying and lower priority handlers. A set of ad hoc flags and appropriate tests at the end of the processor interrupt pin handler and interrupt source handlers could no doubt deal with the situation. However, should additions to the system be needed, then all the handlers would need to be modified. This was felt to be a source of potential problems it would be so easy to forget to make appropriate changes to all the handlers. Clearly, what I needed was an efficient scheduler.
The scheduler I present here was devised to meet the needs of the system just described and allow simple extension if more handlers are needed or the priorities change. A hardware interrupt routine determines the interrupt sources and logs requests against the appropriate handlers. The scheduler is then called. It calls the requested handlers in prioritized order until no requests are pending when it returns to the original background routine. Operation of the scheduler is such that a handler may also issue handler requests, which are then dealt with in the prioritized order as usual. The scheduler runs with interrupts enabled and is fully reentrant but will not cause reentry to a handler. This simplifies the handlers because they do not need to be reentrant, minimizing their stack use. This is useful for an MSP430C337 as stack space is restricted only 1-KB SRAM is available. Figure 1 shows how interrupts cause the various bits of code to run for (in this example) the UART interrupt and handler and the lower priority modem control line interrupt and handler. When the modem interrupt occurs, a second instance of the scheduler starts, and finds the UART handler running, so it immediately returns to the interrupted UART handler. Upon completion, the UART handler returns to the scheduler (first instance), which finds a pending modem handler request, so it runs the modem handler.
The scheduler is essentially a short routine and a linked list. Example 1 is the structure of each list member. Individual handler routines are pointed to by each list member and, along with this pointer, are a request count, RUNNING flag, and a pointer to the next list member (held as a byte offset to conserve memory). This list is processed from head to tail so the highest priority member is at the head and lowest at the tail. A dummy member at the list tail has its RUNNING flag permanently set. This forces termination of the scheduler.
Example 2 is pseudocode for the scheduler. First, an interrupt occurs and the hardware interrupt routine runs. This accesses the external hardware, clears the interrupt source, and increments the request count in the relevant handler member in the linked list. Interrupts are enabled, and the interrupt routine jumps to the scheduler. Eventually, the scheduler will terminate by executing a reti ("return from interrupt") instruction and the original background routine resumes. Starting at the head and working towards the tail, the list is examined. If the request count for a particular member is not zero, then that handler is called. When the handler returns, the request count is decremented and the process repeated. When the request count reaches 0, the next member of the list is selected and the process is repeated. Thus, each handler is called once for each request and in the priority order.
The RUNNING Flag
Basic operation is modified by the RUNNING flag. As soon as the scheduler begins to process a list member, its RUNNING flag is set. It is cleared on completion of that iteration. If it is found to be set, then the current scheduler instance knows that a prior instance of the scheduler is already running or about to run that handler. In this case, this newer instance simply terminates, which allows the prior instance to process the handler request counts. However, an interrupt may occur when the scheduler is still examining a list member but at a point where the RUNNING flag is clear. In this case, the new instance of the scheduler finds the flag clear, so it runs the handler (and, in fact, all handlers with requests in the priority list). On returning to the first instance, it finds all the requests dealt with (that is, request counts are 0), so it does not run any handlers as it continues to scan down the list and finally terminate.
The final member in the list is a dummy member with its RUNNING flag set. There will never be a scheduler instance that set this particular flag, so it will never be cleared. Hence, it provides a permanent end stop to the list because it will always cause the scheduler to terminate.
Code for the Scheduler
Listing One is the MSP430 code for the scheduler. Masks for the request count and the RUNNING flag are held in registers labeled rReqCntBits and rRunning. This makes the code faster than using immediate mode each time the masks are needed, because immediate mode constants need an extra access cycle and cannot be used for the second operand of an instruction. The register rListPtr points to the current list member. As the scheduler is effectively the end of an interrupt routine, it is left to the interrupt routine to save the scheduler's working registers. The interrupt routine can then use these registers rather than saving and restoring its own working registers and a few more cycles are saved. The scheduler runs with interrupts enabled. Careful testing has shown that it may be interrupted without problems at any point. The new interrupt may issue handler requests and jump to the scheduler as usual, creating a second instance of the scheduler. This second instance will run all handlers with request counts greater than 0 and RUNNING flags clear. If the first instance is already running a handler, then the RUNNING flag will be set and the second instance will terminate and return control to the first instance. If the second instance does not find the RUNNING flags set, then it will run all the handlers with request counts greater than 0 before terminating. The first instance then continues, but will find all request counts 0 and, thus, do nothing more.
RUNNING .equ 1 ;RUNNING flag bit mask REQCOUNT .equ 2 ;request count inc/dec value REQCNTBITS .equ 0feh ;i.e. not the running bit ;rListPtr, rRunning, rReqCntBits are ; macro names for general-purpose registers. scheduler: mov.w &schedListFirst, rListPtr ;point to list head ; the next 2 are useful constants to have in registers mov.w #RUNNING, rRunning mov.w #REQCNTBITS, rReqCntBits ;is current function already running? bit.b @rListPtr, rRunning jnz schedEnd doElem: bis.b rRunning, SchedListElem.reqCnt(rListPtr) ;mark this func running bit.b @rListPtr, rReqCntBits ;req cnt > 0? jz zCount ;call the func call SchedListElem.funcPt(rListPtr) sub.b #REQCOUNT, SchedListElem.reqCnt(rListPtr) ;dec req count zCount: bic.b rRunning, SchedListElem.reqCnt(rListPtr) ;clr this func running bit.b @rListPtr, rReqCntBits ;req cnt > 0? jnz doElem ;req count is 0, do next func mov.b SchedListElem.indxNxt(rListPtr), rTemp add rTemp, rListPtr ;->next element in list ;repeat first instrs here for speed ;is new function already running? bit.b @rListPtr, rRunning jz doElem schedEnd: popSchedRegs ;macro to restore scheduler registers reti ;terminate scheduler and interrupt