Hi everyone!

I was thinking just now... can I implement a preemptive multitasking OS on the Micro UK101? Presumably I'd need a few extra bits (RTC? Better I/O?), but I fancy it might make an interesting challenge. Start with a simple round robin scheduler (I guess this is what you'd call "co-operative multitasking") then introduce a timed interrupt (and so on).

I guess the question is this: is the 6502 capable of this sort of thing? It needs to do context switching, have some means of memory protection (that'll be interesting and not at all do-able in hardware as far as i can see - which isn't very far, ha ha), etc.

Thoughts...? Of course, this may just be so much pie in the sky, but I'm pretty curious!

You don't necessarily have to bother with memory protection: the Amiga didn't, nor the original Mac, I think.
As you say, a timed interrupt would be a normal approach, but cooperative multitasking means that the running task chooses when to yield to the scheduler so you don't even need that.
Of course you haven't got much space for the various tasks (their program, data and stack areas) but that just means they need to be small...
Good luck!
Ed

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

I don't think the basic mechanics of multi-tasking per se are the issue. The bigger problem is simply defining/relocating the code for each task, since there is no virtual memory.

You could look at something higher level, like a multi-tasking Forth, or some other style of interpreter. That can simplify the problem. Typically 6502 Forths use zero page for the parameter stack, and the system stack for the return stack. But that's not required. Both of those could be replaced by blocks of memory, then accessed via LDA (PSTACK),Y and LDA (RSTACK),Y. Then during context switch, you wouldn't have to copy entire stacks. Just swap out the stack locations in to zero page. This will likely slow down overall performance (since stack operations would be more costly), but pretty dramatically reduce context switch performance.

You don't need an interrupt to do task switching, you could tweak NEXT to do it on a schedule (every time at least N micro seconds have passed, it could switch). Wouldn't interrupt code words, but would work fine for high level words.

See André Fachat's GeckOS/A65 V2.0, a scalable, full-featured Multitasking/Multithreading operating system for the 6502 that is preemptive and implements some Unix-like features, like signals, semaphores, relocatable fileformat, standard library, internet support via a kind of simplified sockets and last but not least virtual consoles. The only disadvantage I am aware of is that it makes for terrible interrupt response.

The 6502 isn't very good at multitasking, but doing it in Forth with non-preemptive multitasking is easy, and would give a lot less overhead than preemptive. With a real-time system, I think the delays from preemptive multitasking's task switches would be prohibitive. With a good interrupt system though, I have found I don't really need multitasking. I'm not doing the kinds of things we do on the desktop computers, but I have had background programs running on the workbench computer while at the same time it interprets, compiles, or assembles source code coming in over the RS-232 from the PC, and there are several kinds of interrupts hitting all the time and getting serviced to make all this happen. As whartung said, Forth on the 6502 normally uses ZP for the data stack and the hardware stack for the return stack. As I envision doing a multitasking Forth, those two pages, according to tests, could be divided into sections to run three tasks with no trouble, and six (or maybe even more) with care, such that you wouldn't even have to swap them out when changing tasks.

Other topics that had a lot of multitasking discussion (even if their names don't let on) are:
BRK detection: viewtopic.php?f=2&t=24
POC Version 2: viewtopic.php?f=4&t=1688
Idea for multitasking support on 65Org16 (or 65Org32): viewtopic.php?f=10&t=2156
interrupt latency (and 6502 die size): viewtopic.php?f=1&t=2015
and the topic that started the 32-bit 65Org32, "Improving the 6502, some ideas": viewtopic.php?f=1&t=1419

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

If you're running a bytecode/threaded system like Forth, the least overhead and an actually pretty easy way to trigger a swap is to have an interrupt handler selfmod the dispatch routine to jump somewhere else at the beginning of what would be an instruction dispatch. Then there's no polling whatsoever.

You might need to design your dispatch so that you can change a single byte to run the trap behavior, to keep things consistent. Changing the instruction byte of a dispatching JMP to a BIT so that it falls through to a trap handler would be one way.


For swapping out regular machine code processes, the easiest way to get the PC onto the stack is to simply let the timeslice timer interrupt it, or cooperatively BRK (as BDD mentioned).


The only situation I'd recommend implementing some sort of MMU-isms is if your system has expandable or banked memory and you want programs to have easy access to it. One implementation I had used ZP pointers that the OS modified, to give a window into allocated buffers. The program would have to call the OS to say "Hey, I want this ZP address pointing to this handle", and the OS remaps things to suit, adjusting the ZP pointer in question and/or banking or DMAing memory as needed. On context switch, this would have to be restored again, and there's a limit to how many of those pointers can be "active" at once.

It's kind of complex, but anything with a MMU tends to be.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

The part of the stack that's already used, and that needs to be copied isn't going to be changed by any interrupts. So, during the stack copy, you can leave interrupts enabled. The only thing you need to worry about is that you don't try to perform a context switch while already in the middle of one. This can be done with a simple flag somewhere.

There's no need to save the program counter, since it's always pointing to the same place in the context switch routine. The previous program counter (from calling the context switch code) is safely stored on the stack. Also, the context switch routine doesn't need to preserve A, X, Y or the status register. So, all you need to do for a context switch is:

1. Save stack size in per-process memory
2. Pop all data from stack, and store it in per-process memory
3. Get memory area of next process
4. Read stack data, and push it on stack
5. RTS

You can use this for non-preemptive context switching, which I recommend for most applications. If you need preemptive context switching, you can call the context switching routine from the interrupt handler, but since you'll generally want to re-enable interrupts during the long stack copies, this requires a reentrant interrupt handler, and a mechanism that prevents multiple calls to the context switcher.

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

Maybe it's about time for me to dig out that article again on cooperative multitasking in Forth that showed how efficient it can be. They definitely were not moving stacks around. IIRC, they were just storing the stack-pointer values for the task that was taking a break and replacing them with the stack-pointer values the next task had when it left off the last time. They had their own segments of the stack area, so they did not step on each other's space. Since it was cooperative, a task would only pause when it was at a good stopping point, where it was the least work to put its stuff down to let other tasks run for awhile and then resume the next time its turn came. I imagine the OS could tell it in essence, "Until further notice, every time you reach a good stopping point, just transfer control to the task at address ____ . You don't need to bother me."

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

That's my point. The interrupt handler already takes care of saving PC, SR, A, X and Y. There's no need to do it again in the context switch routine.

True, but preemptive multitasking is much more complex, and if you're not careful, can even result in worse performance. I find a lot of people wanting preemptive multitasking, just because it's "standard", and not because it's actually a better solution to the given problem. When dealing with customers in my business, I always try to solve their problems, and not their solutions.

I'd fix the bad code, rather than designing a complex system around it to deal with it. Of course, this may not be an option for 3rd party code, but hey, realistically speaking, what's the chance that somebody will be running bad 3rd party code on a Micro UK 101 ?

Another option would be to divide the 6502 stack space into a small number of chunks, and give each process their own part of the stack. This avoids the copying of stacks. Of course, this requires good knowledge of the number of processes, and their stack requirements.

Take a look at Miro Samek's "Super Simple Tasker". It is a run to completion (RTC) environment suitable for limited stack environments like the 6502. He's taken the concepts commercial, but the basic multitasking concepts are described in the referenced "Embedded Systems" article.

_________________
Michael A.

Thanks for the pointer - the article can be found at http://www.embedded.com/design/embedded ... ple-Tasker

I agree with Arlet, that on a small well-controlled system you could define (say) 8 regions of page 1 for the different stacks.

On the subject of relocation: the Amiga relocated the program at load time and never moved it afterwards. There's a risk of fragmentation. but it removes the question of relocating later. The load time relocation is done by accompanying an executable with a table of offsets for patching-up.

Err... wow. Thinking hat on, methinks. Thanks!

Garth, thank you for the pointer to my work. Everything you say is true, even the bad interrupt response!

The only thing I have to add is that the OS supports multiple platforms, from a 32k Commodore PET, via C64 up to my selfbuilt machine with MMU...

André

_________________
Author of the GeckOS multitasking operating system, the usb65 stack, designer of the Micro-PET and many more 6502 content: http://6502.org/users/andre/