My multitasking kernel has come together quite well so far - here it is running four dummy tasks:

These tasks simply execute a no-op system call in a tight loop:
This syscall is non-yielding, so the kernel will return control to the same process afterwards. Tasks may yield by using a different syscall, but the system will also force them to yield when a VIA timer expires, currently set to 1024 cycles. As a result, in execution the trace shows a lot of syscalls being made by each process, before the timer expires and another process is forced to run. My I/O is very slow (blocking reads and writes, 9600 baud) so I don't log anything apart from process switches at the moment - but hoglet's decoder shows what is going on underneath:
In this sequence it resumed a process after an interrupt (8D08), executed a BRK (0200), the kernel determined that it was a BRK not an IRQ (8C6F-8C8F), the BRK handler went to a lot of trouble to read the BRK's operand from the user process's memory space (8D7F-8DB7) then used it to look up in a jump table (8DB9-8DBF), executed the syscall (8D7B-8D7C), then returned to the same process (8C92-8C8B) only to have it loop back and BRK again.

There is a lot of overhead to read the operand to the BRK instruction. I was trying to avoid needing the user to use registers for passing parameters, but I think that's a bad choice - it will cut a lot out if I just use A to select the syscall type, and ignore the BRK operand.

There's also the usual dilemma over how to determine that it was a BRK - here I did it the Acorn way, saving A somewhere and pulling the flags from the stack. It would be quite simple to add hardware to latch this flag and make it easy to read and branch on without needing any registers - we just need to track the last state of the D4 data line during a write operation, then the IRQ handler can begin with a BIT instruction to read that back. It would save a few instructions, or could even be used to make a different vector get called in hardware - however I don't think that's worth it as it's just a BIT and a branch that would be saved.

Interrupt latency is something I've been conscious of and I'm interested in seeing how bad it is in practice, and what can be done to improve it. As yet I'm not using hardware interrupts for anything other than the preempting timer, but there's a 65C51 there which can issue receive interrupts, and I have it connnected to the VIA's PB6 so that VIA T2 can issue transmit interrupts. I may also use the VIA's shift register, CB1 and CB2 for SD cards, PS/2, etc, at some point - so I will get to try these things out soon.

I wrote the code bearing this latency in mind, but there are no doubt more improvements to make. Here's the source code for the irqhandler routine that appears above:
At the end it falls through to scheduler_run, so the jump is commented out.

irqhandler2 is a fairly standard hardware interrupt handling routine that queries various devices to see what needs attention. It can prioritise urgent devices of course. It returns with the carry set or clear to indicate whether we should switch processes or resume the same one. Resuming the same process is more efficient, so it only sets the carry if the interrupt was due to the preempting timer running out.

Resuming the same process is efficient because we haven't really corrupted its state much - the stack pointer is exactly as it left it, the X and Y registers haven't been touched, and the A register has been saved in a cheap global variable. All we need to do is restore the PID register setting, restore the A register, and return to user mode (the "resume" block above). If we're switching processes though, at the very least we need to store all the process state somewhere it can stay for the long term, then figure out what to run next, and then restore that process's state. The "preempted" block above does the first bit of this, but there is at least as much work still to follow in scheduler_run. So, returning to the same process is better in general.

The two things that will really affect interrupt latency are increases in the code that runs before the interrupt is handled - which are minimal, in the above code that's really just the "stz PID" - but also, any other code that runs with interrupts disabled, including the recovery after the interrupt (things like running the scheduler) and syscalls. I haven't implemented this, but I think a decent mitigation for these is to re-enable interrupts while still in supervisor mode wherever possible. For example, almost all syscall code can execute with interrupts enabled - the only thing that will interrupt them is an actual hardware interrupt, so they'd only need to disable interrupts if they were accessing some complex state that's also manipulated by the interrupt handling code. It should be possible to avoid conflicts between these things in general without having to disable interrupts.

Similarly, the epilogue of the interrupt handler might be able to run with interrupts enabled - as soon as the hardware interrogation is complete, perhaps we can enable interrupts again. This would allow another interrupt to be serviced quickly, if one happened to come in while the previous one was still working out how best to return to user mode.

That said, except in the "preempt" case, where we are switching processes, the return to user mode is not too bad. Here's a full capture of the preempt interrupt being handled, and returning to a different process:

8C97-8CAA are the "preempted" block in the above code snippet; the code after than is what scheduler_run is doing. It loads the last process ID that ran, increments it, and scans the process array for the next runnable process. It finds it quickly as it's the very next one; however it's a lousy algorithm, I should probably use a run queue instead. Then it restores that process's context and executes the RTI to user mode.

Overall I don't think this is too bad in terms of overheads, but there is still room for improvement, and enabling interrupts as early as possible would mitigate a lot of the effects on interrupt latency.

Something else that's come up is the ease or difficulty of reading user process memory, and especially following pointers there. Here's the code for the syscall routine, that reads the BRK operand. I think the comments explain the context pretty well:
So each logical page is 4K - LP0 is from $0000-$0FFF, LP1 is from $1000-$1FFF, etc. The user's stack is in its logical page 0 as the four-character hex address starts with a 0. The kernel uses its own LP0 for its stack and zero page, so instead of mapping that, it maps its LP1 to the same physical page that the user process is using for its LP0. This means the user's stack at $0100 shows up in the kernel's address space at $1100 (i.e. $1000 + $0100).

Having adjusted the X register to point four entries higher than SP - so it points at PCL - we can then read the return address. It points at the instruction after the BRK, and we want the operand instead, so we subtract one from that address while copying it to zp_ptr.

Now if that address is also in the user process's LP 0 (i.e., it's less than $1000) then we're fine, we already have that mapped from the kernel's LP 1, so the kernel can read that byte, it just needs to adjust zp_ptr to point into LP1 instead of LP0 (adding $1000). But if the BRK instruction hadn't been in the user process's LP 0, then the kernel's current LP 1 mapping wouldn't work for it because it's the wrong physical page - so the code above would then look up what the user process's mapping actually is for whatever LP contains the address PC-1, and it would then remap the kernel's LP1 to point to that physical page instead of pointing to the user process's first physical page. After that it can then adjust zp_ptr to point into LP1 as before, and read the byte via LP1.

Note that the pagetable addresses are a bit swizzled - as the comment in the code says, whereas a user process would refer to a page like this:
the pagetable entries for this logical page have the following form:

Dealing with different pages is quite a bit of work, and if we wanted to do something like read a string, or just multiple bytes of any data, we'd have to be cautious about data that spans a logical page boundary in the user's address space, and make appropriate remappings to deal with that. What I wrote above was just my first shot at this, and I'm sure with more calls implemented I'll find cleaner and more generic ways to do this - but for the moment, it is awkward. It could be viable for most syscalls to require the user process to store any data that the kernel needs in its LP0 ($0000-$0FFF), so that the kernel doesn't need to map other pages - but that's a bit of a cop-out.

Splendid! Doesn't seem too bad to me to have some restriction on where to put buffers for OS calls - especially if the OS arranges some space for the purpose in the typical user memory map, for example by making &400 the default address to load and run at. Or something.

(If you're running at 2MHz or more, then your interrupt latency is going to be somewhat like the beeb's, and that was fine.)

Yes in practice it's probably not too bad to do that. Aside from this though, user processes don't really need to know anything about the paging system, page size, etc, that's why I'm a little resistant to it - and the OS doesn't put any constraints on how user processes use the address space, they get the full 64K of RAM to do whatever they want with, no locations have any special purpose.

One good strategy to avoid the restriction is to use kernel's logical pages 1 and 2 together to span a region of user data - this can reliably support up to 4K of data with any offset. So trying to follow a linked list still wouldn't be very good, but for as OSWORD-like block of data this would work well and the user process wouldn't need to know anything apart from that the block must be less than 4K in size (which is huge for a 6502).

To see how this would work for example consider a block of 32 bytes starting at $6FF3 in the user process's memory space, up to $7012. The user process would just send its pointer - $6FF3. The kernel would then see that this is in LP6, so it would map its own LP1 to wherever the user's LP6 is currently mapped, and in addition it would map its LP2 to wherever the user's next logical page - LP7 - is mapped. This way, the kernel now has two logical pages in a row mapped the same as the two logical pages of the user process, and the user's data block is available at $1FF3-$2012.

The second mapping could be skipped in cases where we know the block size doesn't cross a logical page boundary, but where the data size is not known up front I think this method could be useful, and would be easy to encapsulate generically for lots of kernel routines to use.

I have uploaded my code so far in case anybody is interested to see more of it: https://github.com/gfoot/multitasking6502/tree/main/src The OS code is in the "mtos" subdirectory, the rest are test programs and ROM images.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Indeed, the operand byte of BRK, or for that matter COP or WDM, is just not very useful. The value in A is a good signifier.

(Acorn's Communicator has a dual ABI - both vector based and software interrupt based - it might be worth a look, or it might be best regarded as a failed experiment)

Using two supervisor pages to map an unaligned user data structure seems like a fine idea!

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

ooh, i'd be interested to hear more about your 816NIX kernel BDD!
i've been trying to get some work done on my own tiny little OS for the 65816, though my idea was to keep the user and kernel stack (and direct page) seperate, so passing things through the stack wouldn't really work. instead i want to use the signature byte and accumulator for selecting a specific function, and the X/Y Registers to hold a 32-bit pointer to the process' memory where the data for the system call is located. though i'm kinda thinking of reworking that system to just have a single stack.

Sorry George...

That's effectively the OSWORD call in the Acorn MOS which I more or less wrote my own implementation of for my Ruby 6502 and 816 boards.

e.g. to call OSWORD 0 which is "read in a line of text":



and elsewhere:



I decided when moving to the '816 that my executable code would only ever run in bank 0, but there's no reason for this limitation and making the call - in this case it's JSR, but could be other means.

OSWORD does machiney sort of stuff like reading text, sound, etc. and there are other calls that work in a similar manner for filing system and for other local stuff with less parameters there is OSBYTE - code in A, parameter bytes in X and Y.

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

I think using at least one register to pass the API number is sensible, for the 65C02, and making all the API call indexes be even is an interesting idea. I had been avoiding registers because one idea was to support both the OSBYTE and the OSWORD systems, as separate system calls - and each already requires potentially all three registers - so at one point I thought I could use the BRK operand to select an API call (perhaps the last byte of Acorn's entry point for the API) leaving all three registers free for passing the parameters. But it's not worth the overhead just for compatibility with that API.

It's not too hard to read data from the user's stack, in my case - just a load and a store to set up the paging - so using the registers plus pushing any additional data to the stack would work. It takes a few more instructions to figure out the pagetable addresses for an arbitrary pointer - I could simplify that a bit by adding one more multiplexer to the circuit, but I cut that corner. API calls that need a lot of data are probably rather slow anyway so it doesn't matter too much if there's a little overhead here.

So something like an OSFILE equivalent which for the sake of argument uses Y and X to point to a parameter block, whose first entry is a two-byte pointer to a filename string, with the rest of the bytes providing other data about what we want to do with the file (load it, save to it, etc), would require mapping the right page for the block (maybe two pages if it crosses a page boundary), then mapping another two pages for the filename - but whatever we're going to do to the file is going to take ages anyway, and we'll have to do more mappings for reading and writing the actual data, so the efficiency of the initial part is not too important.

These kinds of parameter blocks are really useful, compared to pushing a lot of data onto the stack, because they reduce the amount of data churn considerably. Sometimes you embed a parameter block into a program with its fields already filled in; sometimes you alter a parameter block and reuse it (e.g. changing a "load" into a "save", or making it save to a different filename by changing the filename pointer); and sometimes you just have several different blocks at different locations doing different things. The flexibility is really powerful, and pushing that much data to the stack would be quite expensive, so I'm keen to keep supporting them, and also allow them to be located anywhere in user memory as embedding them in programs is useful and flexible.

But using a register for the initial API number makes sense to at least allow relatively simple syscalls to be decoded and executed quickly. Making them be multiples of two is appealing but I think the cost of then checking that they are multiples of two would actually cancel out the gains. I'll think about it though. It is important that the kernel doesn't just call random addresses when given an odd syscall number. Receiving the syscall number in A allows it to be bounds checked, then doubled, then move to X fairly efficiently.

I think - eventually, and with some care - all the above can be done with interrupts reenabled, as well, so won't cause further issues for interrupt latency - as soon as I know it's a syscall, not a hardware interrupt, they can be turned back on. The preempt interrupt is the thorny one there, do we allow task switching during a syscall? We can't really allow another process to also issue a syscall, I don't think that would be practical to support. So perhaps we'd need to disable (or just ignore) the preempt interurpt during the syscall, but unmask interrupts in general. If a preempt interrupt does occur then the syscall can finish its work, but return control to a new process, so that the preempt is obeyed.

On interrupt latency - the jsr in my interrupt service routine is there because the reset handler also chains to the same nested subroutine, so that it can trigger a cycle of interrupt handling before going ahead and killing the process that stopped responding. I'll see if there's another way to do that - I do find it scary how much code actually needs to run every time a character is received, for example - but then, the early 80s systems also had to do this, at lower clock speeds, and Acorn's at least had quite a substantial amount of code in its ISR, so I guess it just is what it is! The fastest rate I've received serial data on a BBC Micro is 76800 baud, but I had to disable the interrupt handler to do this, and poll the 6850 directly. Any situation with the interrupt handler enabled led to data loss due to latency caused by servicing other devices, combined with the lack of FIFOs in the UART.

I've been looking for an excuse to use a priority encoder, but I don't think it'll be useful here as I only have two devices that can cause interrupts - the 65C51 and the 65C22. The 65C51 can only cause receive interrupts, which are urgent, so I'll poll those first. The 65C22 doesn't have any urgent interrupts yet - it will handle transmit interrupts, and already causes the preempt interrupts, both of which are not time-sensitive. Later it may have more urgent ones, particularly if I use it for PS/2 communication where there's an external clock involved, and I'll just need to check for those first after the 65C51 ones (or before, depending which ends up being more cricital or expensive to handle).

Thanks for all the thoughts, opinions, and advice, it is interesting to see different perspectives!

My roadmap at the moment is:

• Implement support for loading user processes from the server - at the moment it just pokes specific code into the processes when it starts them, so it's hard to iterate on user code
• Implement print character / print string / get character APIs so user processes are more interesting
• Make the serial input be interrupt-driven
• Make the serial output be interrupt-driven
• Measure how bad the interrupt latency is, how close we are to losing data
• Port GIBL or something similar - an interesting option here is putting the whole of GIBL in a shared read-only page, so that many user processes can share the interpreter

That's my (half formed) thought too. If the timer interrupt ticks during a syscall then set a flag or something saying the timer has ticked and RTI immediately to the syscall. Then at the end of the syscall check if that flag has been set. If so call the do the normal preemptive system work and return control to the next user process afterwards.

That would be awesome... GIBL is practically stateless to the point if you swapped out page 0 and whatever other pages it needs for data if it all won't fit into ZP per process.

A trick you can use with interrupt driven serial IO is to make the buffers a power of 2 and aligned on a power of 2, and keep a head and tail pointer. Makes wrapping easy and fast and you don't need to disable interrupts when the reader pulls data out and updates the tail pointer, or the writer pushes data in and updates the head pointer. A "gotcha" might be when using the same serial line for multiple processes - simple characters are fine, but swapping processes when half way through a VDU sequence can produce some interesting results...

Here is your challenge:

https://www.youtube.com/watch?v=ZL1VI8ezgYc

That's all done via a 115200 baud serial line...

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

Yes, I use a VIA so I can easily disable that interrupt source during a syscall and still check whether the interrupt would have fired if it was enabled.

This has made me realise why something I tried earlier today didn't work - after hooking up support for loading program code into new processes from the serial host, I tried making the child process disable interrupts, to check that the watchdog timer still worked:
However the timer didn't trigger. The reason is that the BRK is causing supervisor mode to be active, which resets the watchdog, and even though the preempt interrupt doesn't get serviced, the watchdog also never picks up on this.

It is an edge case with a few possible solutions, but is also related to whether syscalls enable interrupts. To some extent it doesn't make sense for code to disable interrupts and then issue a system call. Acorn's stance on this was generally that the OS might enable interrupts while processing the API call.

The value of a user process disabling interrupts at all is questionable and I could clear the I flag on the stack before RTI from the syscall, or make the syscall handler chain into the interrupt service routine at its end in case anything is pending.

I also wondered a bit about user processes getting callbacks from interrupts, so they can execute their own asynchronous responses. I think I could do this by manipulating the process stack, pushing an extra frame, so that it returns into this callback, and the callback itself would then RTI when it is finished. This would allow things like timed callbacks, vsync callbacks, or notifications when I/O is available, without requiring threads and select().

Threads, now that's a whole other topic...