Ok. as I promised in that post it is now the time to start explaining how to implement the cooperative RtOS kernel.
This may sound like a bit of a paradox, but it will be easier to start explaining how to build a preemptive kernel.
So let gets started….
… from interrupts.
What is an interrupt? Basically this is a hardware signal which makes processor to alter the flow of program execution like this:
Basically main program executes and then, at certain moment, which actually should be considered fully random, an interrupt happens. In response to interrupt signal the program execution “jumps” to a fixed (by hardware) place known as the “interrupt handler routine” and after reaching an instruction indicating “end of interrupt handler routine” it jumps back to main program.
The beauty of it is in the fact, that the interrupt is (or rather – should be, if well done) completely transparent to main program. If main program is not actively looking for effects of interrupt handler routine execution it will never know that interrupt have happen.
But why do I talk about interrupts?
Because we can imagine that they would do something slightly different:
This time at interrupt program execution jumps to interrupt handler routine, but instead of jumping back to original place it jumps to an another place. Now, since interrupts are designed to be transparent, the Task A, when finally started to run again after blue line returns to it, won’t have any blind idea that after the interrupt finished a piece of Task B was executed.
How interrupts are made transparent?
To answer this question we need to define some ideas about a “processor model” (CPU model).
What is the absolute minimum of data resources, except the program and data memory of course, what defines the CPU?
The way the CPU knows what instruction is actually executing. The so called Program Counter (PC).
The Program Counter
The program counter(PC) is a piece of hardware register which contains the address of instruction in memory which is now (or to be next, depends on design) executed by CPU.
In fact, each time the processor executes any instruction it executes following operations:
instruction register = load from memory at address from PC
PC = PC + 1 <-- so that it points to next instruction now
execute instruction stored in instruction register
if result tells me to jump to certain address do
{
PC = that address
}
So the absolute minimum what must happen during interrupt is:
store PC somewhere PC = address of interrupt handler routine
and when interrupt service routine terminates:
PC = somewhere
Hmmph…. isn’t it just a call to subroutine?
You are right. Exactly. Interrupt is just a hardware injected subroutine call.
Registers
The primary difference between subroutine and an interrupt is that the subroutine effects are not transparent. In fact the whole idea of a subroutine is to produce some visible results. So how forced call to interrupt handler routine can be transparent?
For that we need to define in our model the remaining part of the “state of CPU“.
Nowadays most CPU are register based and most of them have a single, hardware, non movable set of registers. I will skip the stack based machines, the machines with paged register banks and etc. and focus just on plain register based machines like my beloved MSP430.
Ok, so what except the PC defines the CPU state?
The registers. Registers are like Program Counter – just a bunch of hardware flip-flops arranged in such a way that they can be manipulated an order of magnitude faster than memory.
Let us for simplicity say that our fictional CPU has 16 registers named from R0 to R15. And, of course, the PC register.
Now we can create a difference between interrupt and a subroutine call:
somewhere_PC = PC PC = interrupt handler routine somewhere_R0 = R0 somewhere_R1 = R1 ... somewhere_R15 = R15 .... and when we return from interrupt R15 = somewhere_R15 ... R0 = somewhere_R0 PC = somewhere_PC
Since PC,R0…R15 do fully define the state of CPU then when we restore them the program executes as if nothing have changed.
But what is that somewhere where we are saving them to?
Stack
Again, as with concept of register machines, I will focus now on CPU which has a “software stack“. Again like my beloved MSP430.
Of course there are other models on the market, like hardware stack based PIC16/17/18 or “linked register” based ARM7 architecture. Let us not complicate things now and focus on the primary example.
A “stack” is a hardware supported data structure which can be used to “push” some value on stack and “pop” some value from it. Just as if it would be a stack of papers on a desk. The stack always serves two purposes:
- to handle subroutine calls;
- to handle temporary data storage beyond the registers pool.
Control stack
Handling subroutine calls is the task which belongs to the “control stack“. If You imagine that Your CPU has the call X instruction which is used to jump to subroutine and a return instruction which is used to jump back they will be implemented as a sequence of following operations:
call X:
{
push on control stack PC+1
PC = X
}
return:
{
PC = pop from control stack
}
Data stack
Data stack is used to just save some data. The CPU is usually not using it beyond offering push x and pop x instructions at assembly level.
In so called “software stack” CPU the control stack and data stack are the same stack.
Stack pointer
If CPU has the support for a stack then it will usually have one extra register which not only can be read or written as normal register but is a base for push and pop operations. This register is called a “stack pointer” (SP) and is used like that:
push x:
{
memory at address SP = x
SP= SP+1
}
pop x:
{
SP = SP -1
x = memory at address SP
}
Note: Of course the direction of stack growth, in this example upwards, can be arbitrary. Different CPUs are using different stack growth direction.
Complete interrupt execution sequence
Now let us try it out again. When interrupt signal is accepted by a CPU the call instruction is injected and what happens is:
push PC (using SP register) PC = interrupt handler routine
This is the hardware action. The rest is usually executed by code in interrupt handler routine:
push R0 (using SP register) push R1 ... push R15
and when return from interrupt happens
pop R15 ... pop R1 pop R0 return (equivalent of: pop PC)
Turning interrupt to task switch
Now get back to tasks for a moment.
A task is usually doing many, many operations. Plenty of them will be implemented with subroutines. What means that the call X instruction will be used frequently. And call puts data on stack. What does it mean? Well… If we would just somehow have stored registers of Task A and restored them for Task B how would nearest return in Task B behave? Would it return where it should be returning? It would, but just in one case: if Task A would not push anything on stack. If Task A would have put anything on stack, the Task B would use it and mess up.
So this means, that each task must have own stack.
Simply the registers PC,R0…R15 do define the state of CPU, but the state of program is defined by PC,R0…R15 and the state of stack. And the state of stack is basically represented by the SP register.
So to actually switch a task with an interrupt we need to:
call interrupt handler routine .... push R0 (using SP register) push R1 ... push R15 store SP of current task somewhere restore SP of next task from somewhere else pop R15 ... pop R1 pop R0 return
In other words we need to switch stack before we start the sequence of operations which constitute the return form interrupt.
Summary
I hope that after reading this small blog entry You could have grasped, that the moment You will be able to write the interrupt handling routine You are only one step from creating the preemptive RtOS task switching kernel.
Does it still looks very complicated?
In next blog entry I will try to show You how interrupt differs from cooperative task switch and why it can be more lightweight.
Old coder's ramblings about software concepts and quality. 