Interrupt

How interrupt work

Simply saying, you change the voltage on a pin and processor start to execute on a new location.

The way interrupt work:

Basically the interrupt is an external hardware that alerts the processor that the input is ready.

The processor suspend what it is doing.

Processor actually is really stupid. They have a clock signal and in every clock it take whatever the value of program counter register is and read from a memory location, get an instruction and execute that instruction. In the next clock, these execution are actually pipelines that spread over several clock cycles but logically it fetching a sequence of instructions and executing them.

What you do is you change the voltage on the interrupt request line. Interrupt says is hardware in the device that says: oh, wait, don't use the program counter on this cycle, on the next cycle instead I want you to fetch from a fixed location in memory, get the instruction there instead of using those in program counter. And what's there is interrupt service routine.

Logically the way it works is you set up your interrupt routine that you tell the hardware you'd like the interrupt to occur if something happens on some external pins, gpio pins goes high, serial port receive a byte. Write into our memory map register says give me an interrupt when this external condition happens.

The processor itself goes into a loop where it just executing code until the interrupt condition is satisfied at which point it goes to execute code in a different interrupt service routine.

Microkernel is small OS just handling scheduling of tasks. You need to decide when to schedule it. One common strategy is to use timer interrupt. Microkernel will write into a memory map register which will setup a periodic interrupt at some interval time, let’s call it jiffy interval. When that interrupt comes in, you got bunch things to do.

1.       Disable interrupt

2.      Store the register of machine into persistent data structure, i.e thread structure which keep track of current thread. Store the return address. What will typically happen in interrupt hardware is program counter gets pushed onto stack. We will store it into a persistent memory independent of stack which is in thread data structure.

3.      Decide whether to continue to execute current thread.

Heap persist the across procedure calls. Stack does not. Malloc space for thread data structure.

4.      Put PC on stack and overwrite it and return from interrupt.

5.       Enable interrupt again

What does create a new thread mean?

Call a procedure, allocate memory for this thread data structure, decide where the stack going to go in memory. Make sure thread stack don’t interfere with one another. Sufficient space between them.

So basically initialize the data structure. Decide which to execute. If you decide continue the thread just created the new thread then you would return from interrupt.

Reset, create the first idle process, timer will wake it up or by external device.

No-op, infinite loop

Branch to a bootloader, look at an outside memory, flash memory, for example and load in program into RAM and start that program and so on.

How to decide which thread to schedule?

1.       Fairness, give every thread a chance to run

2.      Importance, idle thread: lowest

3.      Responsiveness, shortest job first

4.      Precedence, thread might wait for other thread to complete. How to know one is waiting for another one to complete? In thread data structure, you could have some status information that indicate the thread is blocked and why it is blocked. When acquire a lock,  stick on data structure. Later release the lock, go to find all thread blocked. Try to execute the waiting thread.

Non-preemptive: once start, go until done. Only useful problem broke down to small tasks. Cost is tiny.

Time-triggered interruption

Cooperative multitasking

If priority change dynamically, does that mean the scheduler is running concurrently?

Assume we have a single core, execute a single instruction stream. The only way of concurrency is interrupt kick in and give a new task the opportunity to run. The thread scheduler runs only when it is given an opportunity to run by an interrupt or by a procedure call. If you have a thread that make a call to pthread library to acquire a mutex, normally that will call the thread scheduler to run. Why? Because if you attempt to acquire a mutex, you may block. So obviously you want to the thread scheduler to run at that point you don’t want to wait until the next timer interrupt to for the scheduler to run because the currently executing scheduler is stalled. Remember processor has to do something. What is it mean stall? The clock is still going, the program counter still get incremented. The processor got to do something. Got to put some value in the program counter if you can’t acquire the mutex. So a reasonable choice is to make the program counter point to your thread scheduling algorithm and let the code run to decide what to do next.

So yes. If you have dynamic priorities, the scheduler need to get more opportunity to run. Anything that could change the priority of thread need to involve thread scheduler, if you have dynamic priorities.

Penalize the thread that run a long time, give them a lower priority simply because they’re taking a long time to execute.

Does the halting problem affect your ability to estimate the execution time?

When context switch happens, you disable interrupt first. Then save the PC(push program counter on the stack), processor register that ISR might overwrite. Then ISR jumps to certain designated address. Then execute the instruction at that address. Or it could be a table of addresses of all ISRs.

Instruction vector is a table which has one jump instruction for every kind of interrupt.  Jump to the code of corresponding interrupt. All of these happens before ISR running. Then ISR code execute.

At the end of ISR, it has restore the value of  registers it had saved before running. And then re-enable interrupt and return back to main function.

Oftentimes it is useful to raise an interrupt after certain amount of time has elapsed. For example, in RRH project, you need to read the digital power sensor value every 10 ms. So every 10ms elapsed you want a new interrupt to be raised so that the main thread then goes and gets a new sample.

What happens when multiple interrupt occurs?

This depends on hardware mechanism that implemented. The way interrupt indicated is simply by raising the voltage level. There is only one interrupt at any time. Buffer might help with multiple interrupt.

What happen if you are serving interrupt A and some other interrupt B occurs?

If you respond to A and disable all interrupts. You will not be able to respond interrupt B.

When you re-enable interrupt and B is still waiting and you will be able to respond to it.

It also possible not to disable all interrupts. In some cases there could be different signals you can rate in increasing order. May be the reset interrupt is the most important. You want reset interrupt has higher priority than ADC interrupt. So the priority has to be set and you disable only the ADC interrupt when you go to service it.

Set up a timer, set the period of timer

Enable the timer to start counting

Trigger an interrupt, enable the interrupt itself

When done, disable both interrupt and timer

Using function pointer allow us to connecting the timer interrupt to interrupt service routine. It register the ISR to be invoked on every SysTick interrupt.

Between any two instructions in main function, you could have ISR executed. And possibly between two instruction in ISR, we could have another instance of ISR executed and so on. It is a form of interleaving. The code for ISR is interleaved between the code for main function.

SysTickIntRegister(&ISR)

How to avoid the case that you run ISR and you get interrupt, repeatly? Under what condition would it be highly unlikely to happen? Assumption.

1.       the time ISR execute is much much shorter than the time between interrupts.

2.      The time main function takes

3.      The main function does not mess with timer counter when running the loop.

Stack is used for procedure calls and for interrupts. Heap is used for storing persistent data that cross procedure calls.

Execution time:

Bounded iteration, bounded recursion

Minute detail of embedded system

Do you have cache? What is your cache replacement policy?

what the contents of cache when the task get start executing, what the cache after the task get preempted and then resumed.

timer interrupt:

timer: input is the impulse such as 1.93180MHZ, output0 impulse will connect to pin0 of interrupt controller and trigger a periodical interrupt. The period of this interrupt is what we call "tick". So basically, timer interrupt is actually a periodical signal which is totally hardware operation. This signal will trigger a interrupt service routine.

timer_interrupt() -> do_timer_interrupt() -> do_timer()/update_RTC()

do_timer() -> update_process_times()

every 10ms call timer_interrupt

every 11min, ie 660s update RTC information to synchronize OS timer and RTC timer

update_process_times() will do many works such as update the timer counter of current thread

interrupt installation

time_init() -> setup_irq()

setup_irq(0, &irq0) connect interrupt routine to interrupt queue and wait the execution when interrupt arrive

Generally, every timer tick allow the timer interrupt to be executed. timer interrupt frequency is 100 times/sec. Main job of timer interrupt is handle with all the information related with time and decide whether to execute schedule program and deal with the lower half. The information related to time is system time, time slice of process, delay, CPU using time, various timer, updated time slice of process provide proof for process scheduling. Lower half either have a dedicated kernel thread for each handler or are executed by a pool of kernel worker threads(sit on a run queue).

Funny Example: An 8-bit microcontroller with 16-bit addresses

In particular, general purpose 32 bits registers also have memory address in the address space, this is very common design not only design. What it means if you want to access a register in a machine, you can do so by just doing an ordinary memory access but use these first 32 memory location. And what you get is register rather than your main memory. In instruction set, typically, there is instruction that directly reference these registers so you don't have to just use the ordinary memory access to access these registers.

Given the register in data memory, why there are only 32 of them? Accessing register are generally really quick. Often a single instruction cycle can access multiple registers and operate on them. Why wouldn't we then provide more registers so that we can get faster programs that operate on more data?

You need 5 bits to choose register in order to distinguish between the registers. Where those 5 bits gonna be? They are gonna be in embedded in an instruction. How big the instruction? It is 8-bit microcontroller. So each memory access gives you 8 bits. So you'd like to be able to get an instruction that take up only 8 bits and then executed it in a single cycle. If you need 16 bits in the instruction. It's gonna take you two cycles to fetch an instruction. So 5 of those 8 bits will be accessing the register, specifying the register that it's operating on and gives you only three bits. So you can only have 8 such instructions. But actually you can only have 7 such instructions. Because you need more than a total of 8 instructions in a machine, so one of the three bit patterns has to be the one that tells you that this is not a 8 bit instruction, this is a 16 bit instruction. So you only have the possibility of having seven 8-bit instruction that operates on a register. If you had 64 registers, you would only have 3 possible instructions that would access to register. So there is design trade-off that happens where you want, you'd like to have a big register file. But register file are expensive because they take up realistic in instruction world.

There are 64 I/O registers.