A year has gone by so I don't remember for sure but I may have been thinking that you were wanting to run pre-written programs under a multitasking OS. In reviewing the above, I'm not so sure. I'm not familiar with the UK101, so I didn't comment much. A few months later though I found myself working on a multitasking project with a PIC16 microcontroller which of course doesn't have the resources for a multitasking OS but you can do the same thing with nearly any processor so I'll describe it here. I started with this kind of thing:

Code:

MAIN_LOOP:
    BEGIN
        JSR  task_1
        JSR  task_2
        JSR  task_3
        <etc.>
        JSR  task_n
    AGAIN

On the PIC, this was in ROM, but you could put it in RAM if you like, and lengthen the list as you add tasks. If you do it in RAM, the task at the top of the list should probably be the one that adjusts the list, adding new tasks or deleting ones that are no longer needed and moving the following ones up to fill in the JSR instruction spot (or at least replacing them with NOPs).

Since my processing power was limited and a couple of the tasks needed a bigger share of it than others, I put their JSR lines in the main loop twice each, distributed such that they would never have to wait too long between runs.

The tasks I had were all dependent to some extent on time, or on other things having completed (like a byte being shifted in or out on a hardware serial interface), or on a flag being set to indicate whether the task was active at the time, or something like that; so each one would initially check to see if it even had anything to do. If the answer was no, it would exit right away and it would have taken very few instructions' time. If a task found that it was indeed supposed to be doing something, it might next check to see if what it was waiting for had happened yet, and if not, exit, again without taking much processor time. If it was time to do something, what that "something" was could depend on where it left off before, so I implemented basically what amounts to a state machine. Rather than having something external schedule the tasks and give each one a certain slice of time, the tasks themselves determined how much time to take, always keeping in mind the fact that processing power was not abundant, and in many cases they gave control right back almost immediately; ie, they were not selfish.

Interrupts were firing at 24,000 per second. Since the task switches were only subroutine calls and returns and there was no context-switching overhead to speak of, the interrupt timing jitter was minimal. Interrupts were never disabled. The interrupts were primarily for timing A/D and D/A (actually PWM) conversions, and a couple of the tasks were doing software anti-aliasing since I was only recording and playing 6K samples per second, for voice-band communications. The ISR also ran an RTC-- not that I cared what time of day it was, but it was for timing button de-bouncing, button-hold time (it has a different function if you hold it for a second or more), squelch-activation times, and other things. It works out fine if you work it like a room full of people all watching the same clock on the wall to time their individual projects. None interfere with any of the others.

So take for example the button debouncing. A task's state says that no button was being pressed, so we're waiting for a key press. If still nothing is being pressed, it exits; but if it finds that now one is being pressed, it increments the state, looks at the time, and adds 30ms to it and records it, then exits. The next time it executes, if the key is not still being pressed, it resets the state and exits; but if it is still being pressed, it compares the current time to the target time it had recorded, and if it has not reached it, it just exits, otherwise considers it a valid keypress, increments the state, does what it's supposed to for that keypress, and adds one second to the current time and records that for another time interval that will mean something else if it is held that long. (There's more, but I won't drag this out.)

Hopefully that gives the idea. Parts of it initially drove me nuts, but gradually I found a way to make it all work and make it clear. This was the first full project I did with my structure macros, and they sure made a difference in making it clear and keeping control of the project.

_________________
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?

There's a crucial difference, though, between a list of tasks called in some fashion, and a (preemptive) multitasking OS. The difference is in the stacks. A real multitasking OS has a stack per task, while your task list has one common stack.

This difference implies a difference in usage. When you have a stack per task, it can hold implicit state information. This means you can do something like:

While waiting for keystrokes in the first 'input string' call, the OS can switch to another task. When a key is pressed, the OS switches back and ends up in the correct place, with all the state preserved on the stack.

When you have a single stack, you can't wait in the middle of a task. You first need to record the state explicitly in some data structure, and return to the main loop. When data is available, you need to retrieve the state, and figure out where you were, and what you were doing.

For some problems, solving the problem in the form of a state machine is easy, for others, it becomes really messy, so there are advantages and disadvantages to either method.

Yes, and I plan to introduce that idea in the 6502 stacks primer [Edit: It's up, at http://wilsonminesco.com/stacks/ ], although that will be at the end of it, and the plan is to only stimulate the reader's imagination as to how that can be done and leave it at that. Round-robin cooperative multitasking is rather easily done in Forth on the 6502; and splitting page 1 into equal-sized segments for the return stack, and doing the same with ZP for the data stack, would easily allow four tasks, but you might have to start being careful if you go much over that, say 6 or more. I'll welcome any related discussion though as I'm working on the treatise on stacks. At the moment I'm working on the section about passing parameters via the hardware stack. I think the section on local variables and environments might be the hardest. Hopefully I haven't bit off more than I could chew, and I'll be able to do everything I have planned. I set a rather lofty goal. I wouldn't mind being bombarded with materials to draw from or link to. I have been combing the forum archives for ideas and things to mention.

_________________
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?

Silly question maybe, but wouldn't this be something where the 65816 would be a far better choice? Or is that considered cheating ?

The 816's added capabilties will be briefly covered, just enough to hopefully whet the reader's appetite. The '816 is one reason not to go into multitasking much in a 6502 stacks treatise; but forum posts indicate a lack of coverage on the subject of stacks, and many eyes seem to turn glassy at the mention of the '816, so one has to be careful in how to approach it so as not to lose the intended audience.

_________________
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?

For some people, part of the fun is to do something that isn't really the easiest or most suitable, like writing a multitasking OS on a 6502.

Hi Garth,

What you have coded is called a cyclic executive. For a real time system, this is a _better_ choice than preemptive multitasking, unless you add some special features to handle resource contention. Having it self-modifying is an interesting twist - I've never done one that way.

The problem with preemptive is resource locks. A lower priority task can block a higher priority task from running if it happens to be holding a resource it needs, causing your system to fail to meet its timing constraints. The solution is priority inheritance protocols. Ages ago, I implemented some for the x86 (http://catalog.lib.ncsu.edu/record/NCSU1423388 if you need a cure for insomnia ).

As others have likely pointed out, preemptive multitasking also requires stack switching. With an 8-bit stack pointer, I think remapping the stack page in hardware (or bank switching) is the only reasonable solution for the 6502.

These days, the only real-time work I do is on 8 bit systems, so I just use cyclic executives.

Thanks,
-JP

My first thought is that there's got to be a way to take advantage of the 65c02 indexed indirect jump instruction here. Supposing there's a zero-terminated "task list" of task numbers in RAM, it might look something like:

No, this is not cooperative multitasking.

Cooperative multitasking is a multitasking system where the threads voluntarily give up control of the processor. Basically, each thread must call the equivalent of a sleep() function periodically so other threads can execute.

I wrote a cooperative multitasking system for the 65816 which was used on a few SNES games, including Zombies Ate My Neighbors, Big Sky Trooper, Ghoul Patrol, etc.

Cooperative multitasking works better on the 65816 rather than the 6502 IMHO because on the 65816, each thread can have its own direct page, whereas the 6502 has a fixed zero page.

Toshi

Garth, I'd love to see a write up on this, both for the '02 and '816, and from the Forth perspective.

The 16F PIC is a pain to multitask because you have no access to stack so it can't be saved and restored. As an alternative to your loop around a set of subroutine calls you can use a set of task code addresses stored in RAM and transferred to PCLH/PCL to effect a jump. This can be quicker as a task can change its code address when a new state is required on the next invocation (rather than calling a subroutine that then does a computed jump to the right state code).

On the 16F1 and 18F you can change the stack pointer so its easy to split the limited hardware stack into two or more sections to allow task switching without losing the call stack for task. This technique works well on the 6502 if your application has modest stack requirements - There is some code in the forum library that does it (http://6502.org/source/kernels/minikernel.txt)

In several of my PIC designs I use two cooperative tasks for management and do all the time critical stuff in interrupt handlers. With two tasks you need ~6 instructions to switch.

Where STKPTR is the hardware stack pointer and _STKPTR is the saved stack pointer for the idle task. The 6502 equivalent would be something like:

The main issue is preparing the stacks for the first switch. On the 6502 i'd do something list this.

When Task1 eventually calls TaskSwitch the stack pointers are exchanged and Task2 will get kicked off.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

A hardware stack is a hardware stack, no matter the operating environment. In order for an article like Garth's (and my soon-to-be-published 65C816 interrupts article) to be useful to the widest audience, it needs to be operating environment-agnostic. I'm no Forth wiz (indeed, I've had zilch exposure to Forth) but I do seem to recall that the "stack" used by Forth for storing variables and such is a software implementation, not a hardware stack.

That said, it seems to me that some efficiency could be gained with a 65C816 Forth implementation by using only the hardware stack. The '816 almost seems to be tailor-made for this sort of thing, what with its stack addressing modes.


In theory, this shouldn't be an issue if resource locking is restricted to kernel mode operations. However, in the hypothetical cooperative multitasking environment of which you speak, there would be a problem with a lower priority process acting as a resource hog (a common malady that was seen in Windows prior to Windows 95).


CPLDs to the rescue! Kidding aside, a similar problem exists with the 65C816 if memory protection is desired. As all stack and direct page accesses automatically refer to bank $00, there's nothing to stop accidental (or not) stack collisions. All the '816's 16-bit stack pointer does for you is give you a bigger stack that can be anywhere in the range $000000-$00FFFF.


The stack picture with the '816 is only slightly more complicated than with its eight bit brethren. The basic principle of a stack pointer still applies, it's just a 16-bit pointer instead of 8-bits. Where the interesting part begins is in using the '816's stack as indexed memory with the <offset>,S and (<offset>,S),Y addressing modes. However, it's not difficult. If I can understand it, it can't be all that complicated.

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

It uses both. There are always two stacks, and on occasion more, like if you want a separate floating-point stack. The return stack uses the 6502's normal page-1 hardware stack, and the data stack is in ZP, using X as the stack pointer. Having them separate solves a lot of problems you run into if you try to do it all on the hardware stack. This also means that there's more stack space available.


Something else that immediately comes to mind is PEA, PER, and PEI. These can be synthesized on the 6502, but doing it requires a lot of instructions.

_________________
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?

In my revamped 65C816 string manipulation library, each function expects one or more pointers to parameters, e.g., the address of a string to be processed. Before, the pointers were being passed to each function by loading the registers as required. The addition of a new function necessitated that I change this, as that function works with two string pointers and two pointers to numeric values, which obviously can't fit in three registers. I decided to arrange everything so that the pointers are pushed to the stack before calling the function. The macros supplied with the library use PEA in the function calls, but any method that can push a 16 bit address to the stack will work. The handy thing about the PEx instructions is that they don't disturb any registers, including SR.

Incidentally, none of these functions use any storage other than the stack. While it would be possible to write 65C02 equivalents that would use only the stack, the code would be bulky and slow.

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

As a counterpoint to trying to use the small stack to pass parameters: the BBC OS convention is to pass a pointer to a parameter block, in X and Y. (There's often also an operation code in A, so you don't need a different call address for each function in a class of functions.) That parameter block may contain data or pointers to data or both. I think this approach allows for arbitrary call graphs - concurrency, recursion - at the possible cost of the caller needing a tactic for memory allocation and deallocation.#

Cheers
Ed