Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Embedded Systems

Interrupt Scheduling


Feb01: Interrupt Scheduling

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

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.

Priority List

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.

Scheduler Algorithm

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.

DDJ

Listing One

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

Back to Article


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.