Microkernel - asynchronous interrupt handling

[FallenAvatar]

Interrupts are by definition a push mechanic. It is a device "pushing" a notification (interrupt) to the CPU.

This is the opposite of polling a device for its status.

This push idea can be programmed all the way through your OS, or you can change it to a pull/polling situation at any time via the API of your kernel.

- Monk

[bwat]

Interrupts are by definition a push mechanic. It is a device "pushing" a notification (interrupt) to the CPU.

Design a CPU and you'll find yourself polling IRQ lines. I thought this push/pull was a bit fishy but it's no worse/better than seeing interrupts as a purely external device driven mechanism. It seems it's a bit push and pull.

[Rusky]

The point is that while interrupts may be implemented with polling, they are a push interface. Some event happens and you program is immediately interrupted. If you were on the CPUDev forums it would make more sense to talk about the pull side.

[FallenAvatar]

Interrupts are by definition a push mechanic. It is a device "pushing" a notification (interrupt) to the CPU.

Design a CPU and you'll find yourself polling IRQ lines. I thought this push/pull was a bit fishy but it's no worse/better than seeing interrupts as a purely external device driven mechanism. It seems it's a bit push and pull.

With my thinking on how a CPU actually works (assumption mostly, but a big circuit ring with branching paths for various operations) It's not quite either push or pull, but just part of how the circuit ring is constructed. With one major exception being a halted CPU is woken by interrupts, making it a slightly more push oriented design than a pull, imho.

- Monk

[bwat]

Some event happens and you program is immediately interrupted.

Not necessarily:
1) Interrupts can be masked. Obviously the non-maskable types are an exception
2) Even when not masked, there are processors where there could be many clock cycles between IRQ activation and execution of the ISR. Not all instructions are restartable. Imagine a complex CISC operation that took hundreds of cycles.

With my thinking on how a CPU actually works (assumption mostly, but a big circuit ring with branching paths for various operations)

Your bog standard CPU is a control unit and a function unit/datapath. Each instruction leads to a sequence of control words, each which configure the mutliplexers in the datapath. The key to figuring out how they work is that all operations happen in parallel and it is only the one actually chosen that updates registers/memory. So, there's no real branching in the CPU (microprogramming aside). It's all done with multiplexers.

Unfortunately I don't have any of my CPU designs uploaded only some dedicated computers like this which show how the control unit datapath interaction happens.

As far as interrupts are concerned, at some point the CPU will enter a state that will sample the IRQ line/flip-flop and possibly start a new sequence to configure the multiplexers to dump the state on the stack and branch off to some code routine.

It's not quite either push or pull, but just part of how the circuit ring is constructed. With one major exception being a halted CPU is woken by interrupts, making it a slightly more push oriented design than a pull, imho.

- Monk

The IRQ is polled but it's easier to think of push not pull.

[Rusky]

Some event happens and you program is immediately interrupted.

Not necessarily:
1) Interrupts can be masked. Obviously the non-maskable types are an exception
2) Even when not masked, there are processors where there could be many clock cycles between IRQ activation and execution of the ISR. Not all instructions are restartable. Imagine a complex CISC operation that took hundreds of cycles.

The exceptions that prove the rule.

[Owen]

With my thinking on how a CPU actually works (assumption mostly, but a big circuit ring with branching paths for various operations)

Your bog standard CPU is a control unit and a function unit/datapath. Each instruction leads to a sequence of control words, each which configure the mutliplexers in the datapath. The key to figuring out how they work is that all operations happen in parallel and it is only the one actually chosen that updates registers/memory. So, there's no real branching in the CPU (microprogramming aside). It's all done with multiplexers.

Unfortunately I don't have any of my CPU designs uploaded only some dedicated computers like this which show how the control unit datapath interaction happens.

As far as interrupts are concerned, at some point the CPU will enter a state that will sample the IRQ line/flip-flop and possibly start a new sequence to configure the multiplexers to dump the state on the stack and branch off to some code routine.

Fortunately, I do happen to have the code for a very simple CPU online. Its' actually an implementation of the Nibbler 4-bit CPU; so ISA references there are comparable, but microarchitecturally the two are nothing alike (allowing you to contrast two different implementations of one processor if you like; we made different tradeoffs because FPGAs and discrete logic are very different). You can find a block diagram of my implementation here.

The first thing to understand about VHDL (what my implementation is written in) is that it turns procedural programming languages on their head. It is not procedural; everything happens at once. After all, this is how the real world works. Between the main begin and end blocks, you'll find assorted logic and some processes. Processes are "kind of" procedural: at the start of the decode process pc_action is set to PC_NOP, and then a few lines later the implementation of the JC instruction sometimes overrides that with PC_LOAD depending upon the carry flag.

Basically, how it works in all modern logic design is that you have a whole bunch of "random logic" which sits in between flipflops. The clock ticks and the flops change state, and then all of the "random logic" starts reacting to these changes. Everything goes "indeterminate" for a while, and then eventually all the changes have propagated all the way through and everything settles (Incidentally, the maximum settling time - determined by the slowest logic path from the output of one flop to the input of another - sets the maximum clock speed). You try and write your logic this way because it means minimum confusion for both you and the compiler.

So that pc_action variable only gets read in one place - inside the update_regs process - inside an event which is gated to only occur at the rising egde of the clock. So pc_action has until the next time the clock ticks to settle.

So, this has kind of been a "120 second introduction to VHDL and digital logic"; so to get to the meat of things: How do interrupts work in hardware? Well, unfortunately Nibbler doesn't have interrupts. What if I wanted to add them?

Firstly, I'd want an interrupt signal synchronized with the CPU clock (and only changing at rising clock edges), because that simplifies my logic. Then the question is "How to react to it?"

I'd probably enlarge the "ir" register by a bit (so I could encode a virtual interrupt 'pseudo-instruction', or add an 'interrupt_accepted' signal inside the processor or something. Lets assume we are stashing it as a "virtual instruction:"

Change around line 64:

Code: Select all

fetch: process(clk, phase) begin
  if rising_edge(clk) and phase = FETCH_PHASE then
    if int and not if_flag then
      ir <= '10000';
    else
      ir <= '0' & prog_data;
  end if;
end process;

& is the VHDL concatenate bits operator

And then add a interrupt "pseudo instruction" to the instruction switch table

Code: Select all

when "10000" => -- Interrupt
    -- Stash the PC somewhere
    -- Load the PC with the interrupt PC
    -- set the if_flag (Interrupt Flag) to block future interrupts
    -- probably save the other flags somewhere for safe keeping
    -- Nibbler would of course be a terrible processor to do this to because it has one register, no stack, no return instructions, a full opcode map, etc.
    -- I'm just using it as an easily comprehensible example :-)

Its not really polling. The synthesis tool (whether synthesizing for an FPGA or actual silicon) will produce a bunch of gates which look like "phase.fetch_phase AND int AND not if_flag" which feed a multiplexer which pick between "10000" and '0'&(the output of memory). The result of that will then be fed into the input of a flip-flop which ticks over on the system clock.

Hardware doesn't really poll, nor does it really push, in no part because the distinction is artificial in a world where doing something doesn't take time from something else.

[bwat]

Hardware doesn't really poll, nor does it really push, in no part because the distinction is artificial in a world where doing something doesn't take time from something else.

It looks like your CPU is a single cycle design (I've had a quick once over your design I'm not getting the phases so I'm not sure about this. I'm not a VHDL coder). Consider a later design of your CPU which had a multiple cycle instruction. If an interrupt happened during execution of one of those instructions then imagine the work required to handle the interrupt on any old rising clock edge during the execution. You would probably find it easier to sample (poll) the IRQ line at the end of instructions, no?

Firstly, I'd want an interrupt signal synchronized with the CPU clock (and only changing at rising clock edges), because that simplifies my logic. Then the question is "How to react to it?"

Why not just use an edge-triggered D flip flop? That way there's no need to constrain interrupt signal changes to rising clock edges?

A small thing. I found this:

Code: Select all

 if load_flags then
cf <= alu_out(4);
zf <= not (alu_out(3) and alu_out(2) and alu_out(1) and alu_out(0));
end if;

Is the Z flag being set correctly? Don't you want this

Code: Select all

zf <= not (alu_out(3) or alu_out(2) or alu_out(1) or alu_out(0));

or this

Code: Select all

zf <= (alu_out(3) xnor 0) and (alu_out(2) xnor 0) and  (alu_out(1) xnor 0) and (alu_out(0) xnor 0);

instead? (Again, I'm not a VHDL coder so I could be very wrong!)

[embryo]

It's not difficult at all. It can be done with a single semaphore like object: thread waits, interrupt handler signals. Once the thread has been inserted into the ready queue then there's no problem with an interrupt handler triggering a reschedule - after all that's what the timer does in most systems with scheduling quanta.

Here we can discuss "what is difficult". If there is no straight flow of control - it is not a trivial case for me. If I must think about one or even more switches between procedures of device event handler and the scheduler - it's very error prone situation. But of course, it can be implemented somehow.

And may be you have missed one thing - how thread can wait if thread waiting implementation algorithm also should wait for the device event have been handled? Here we have the switches issue.

I don't think any implementation that polls for the result of an interrupt is much good. Either use the interrupt or disable it and poll.

If you not sure about poll variant then you can design push one and show that it is safe and robust. My choice is to stick with simple things, but you can invent something special.

[Owen]

Hardware doesn't really poll, nor does it really push, in no part because the distinction is artificial in a world where doing something doesn't take time from something else.

It looks like your CPU is a single cycle design (I've had a quick once over your design I'm not getting the phases so I'm not sure about this. I'm not a VHDL coder). Consider a later design of your CPU which had a multiple cycle instruction. If an interrupt happened during execution of one of those instructions then imagine the work required to handle the interrupt on any old rising clock edge during the execution. You would probably find it easier to sample (poll) the IRQ line at the end of instructions, no?

Its' a two cycle design; alternating between FETCH_PHASE and DECODE_PHASE on each clock tick.

While you could say it "polls" at the beginning of every FETCH_PHASE, really the logic tests for interrupts continually. Its just that the loading of data from that logic is restricted to "rising_edge(clk) and phase == FETCH_PHASE"

Firstly, I'd want an interrupt signal synchronized with the CPU clock (and only changing at rising clock edges), because that simplifies my logic. Then the question is "How to react to it?"

Why not just use an edge-triggered D flip flop? That way there's no need to constrain interrupt signal changes to rising clock edges?

That, or rather a pair of such flip-flops in sequence, is how you would generate such a synchronized signal. Generally in digital design you have all on-chip signals synchronized where possible, with the exception of reset (because normally it needs to work even if the clock hasn't yet started). It simplifies things for both you and the synthesizer, plus most devices are fully edge triggered anyway. Also, one must remember that synchronizers are not perfect. You can't take a signal between two unrelated clock domains in a 100% foolproof way; synchronizers do occasionally give spurious outputs.

A small thing. I found this:

Code: Select all

 if load_flags then
cf <= alu_out(4);
zf <= not (alu_out(3) and alu_out(2) and alu_out(1) and alu_out(0));
end if;

Is the Z flag being set correctly? Don't you want this

Code: Select all

zf <= not (alu_out(3) or alu_out(2) or alu_out(1) or alu_out(0));

or this

Code: Select all

zf <= (alu_out(3) xnor 0) and (alu_out(2) xnor 0) and  (alu_out(1) xnor 0) and (alu_out(0) xnor 0);

instead? (Again, I'm not a VHDL coder so I could be very wrong!)

So back in October I was starting my Final Project in Physics, which involved VHDL. I threw this together quickly because (A) I had previously done some Verilog, but it had been quite a while, and so I was quite rusty at hardware design, and (B) as a project to learn VHDL. The board I was using had a HD47780 LCD, 8 LEDs, a bunch of buttons, etc wired up. Basically, the same LCD and a bunch of very similar hardware to the Nibbler board mentioned above (minus the speaker). So, my intention was to wire up my processor to those in a software-compatible way.

My own tests, both hand assembled and using the Nibbler assembler seemed to work, but I couldn't get any of the official ones to work. I shelved the project, being as I had to move on to doing my actual project (You know, the one which would help earn me my degree).

I suspect you may have found the bug.

Incidentally, this is possibly one of my biggest areas of criticism in VHDL; in Verilog you would wite that as "zf <= ~|alu_out" since it has unary versions of all the binary operators which mean what I had to write manually above.