I've read both on Wikipedia and http://atari8.co.uk/gui/ that being able to relocate the CPU stack is a good thing for preemptive multitasking.

I know the 65C816 can do this...but, can someone explain why this is so?

I guess I'm not understanding the benefit of moving the stack....using the stack, I get that...but moving it?

Thanks.

_________________
Cat; the other white meat.

Probably just means the ability to set up a stack pointer in a different area of memory, no?

If you don't have the ability to use a different region of memory for the stack, you would either have to simulate a stack, or move data between the designated stack area and a per-process buffer on every context switch.

Multitasking means there are multiple tasks. Each task has its own independent stack. Preemptive means that tasks can be paused & resumed in any arbitrary stack state, and that per-task stack needs to be preserved as other tasks run.

Consider IRQ handling, which obviously does share a single non-relocated stack. The handler runs to completion, and its stack data gets popped away before resuming the program, restoring the stack to the original program's view. Note that the original program was preempted, but the IRQ handler is *never* preempted to let the original program resume. Consider if the IRQ handler left stuff pushed on the stack, and wanted to have that data remain there for its next invocation. The other program would likely trample it. The two would need their own separate stack areas to work that way.

A relocatable stack pointer means you can easily switch between different stacks coexisting in RAM, each in a separate memory area.

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

OK, that makes sense in the context of separate stacks for each task.

Thanks.

_________________
Cat; the other white meat.

I've never done preemptive multitasking myself, but to do it on the '02, undoubtedly what they're doing is to use TSX, STX to get and store the current stack pointer value to use again later when you get back to that task, then changing it to the right value for another task by using LDX, TXS before re-activating that task. The stack area can be divided up into sections for the various tasks. The '02 only has page 1 for stacks though, so if you run more than say three or four or five tasks, you'll have to start being careful that none of them will ever use more than their own share of the stack space and step on another task's space, or you have to start copying it to other parts of RAM, which of course runs a huge overhead. The '816 OTOH has a 16-bit stack pointer, so you could assign several pages to stack space. Its X register is also optionally 16-bit, so TSX and TXS can handle the whole address at once. It's less limited.

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

I thought about this once before I knew about the '816. With enough address decoding, and either a PIA or one of the faster I/O schemes, a large memory could be used, separate from main memory, which would be bank switched to page one by the multitasking scheduler.

I also thought it would be handy to include half of zero page, and half of $FF page in the bank switching. But then I thought, maybe each task could have it's own $0080-$FE7F address range. Too much ambitious, perhaps woolly thinking.

All of that can be natively done by the 65C816 without "bank switching."

As Garth pointed out, the '816 has a 16 bit stack pointer (SP) that can refer to anywhere in the range of $000000-$00FFFF. SP can be read/written via the 16 bit accumulator (real handy for dynamically allocating stack space in procedure calls and interrupt handlers) or via the X-register when set to 16 bits (the usual TSX and TXS instructions). These basic features are complemented by the '816's stack pointer relative addressing modes, which make it possible for a program to treat the stack as an ephemeral set of pointers.

Similarly, the '816 has a 16 bit direct page register (DP) that determines where direct (zero) page is located. At reset, DP is set to $(00)0000, which points at the physical zero page. However, it is possible to load any 16 bit address into DP, either by the TCD instruction (copy 16 bit accumulator to DP) or the PLD instruction, which pulls the DP value from the stack. Adding to the fun is the idea of creating ephemeral workspace on the stack and then pointing DP to the start of that workspace, viz:

Code:

         rep #%00100000        ;16 bit accumulator
         phd                   ;save current direct pointer (DP) for later
         sec
         tsc                   ;get current stack pointer (SP)
         sbc #s_wrkspc         ;subtract workspace size & ...
         tcs                   ;change SP
;
;   Now we can use the allocated stack space as we choose.
;
         inc a                 ;1st location above SP
         tcd                   ;point DP to SP+1
...
   ...program does some processing...
...
         clc
         tsc                   ;get current SP
         adc #s_wrkspc         ;discard workspace
         tcs                   ;restore SP
         pld                   ;restore DP
...
   ...program continues...

In the above, S_WRKSPC is treated as a 16 bit value, not eight bits.

Once the setup code has been executed, you could store a 16 bit pointer to some data on the stack with STA 1,S and then use that pointer in indirection, such as LDA ($00),Y. The '816 will add DP to the pointer "address" ($00 in this case). For example, if SP is $BFFF after the workspace setup and SP+1 is in DP, LDA $(00),Y is effectively LDA ($C000),Y. This technique works for any legal direct page addressing mode, including the special "long" modes, e.g., LDA [$00] and LDA [$00],Y.

The gist of it is each function (subroutine) can have its own private stack and direct page space that can be created and destroyed as needed. The only caveat is that an interrupt service routine (if one is running) must preserve DP and reset it to where it expects direct page to be so as to not step on the foreground's workspace. After the ISR has finished, it must restore DP so the foreground doesn't get messed up.

Sure beats playing around with the exotic hardware needed to do the same thing with the 65C02.

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

The original question was never answered, I don't think -- the question was why a relocatable stack was a good thing, not a relocatable stack pointer.

It's because the 6502 can only put its stack in the region $0100-$01FF. There's no exception to this. So if you have three programs in memory that are using all of the stack (say, $0100-$012F for program A, $0130-$0180 for program B, and $0181-$01FF for program C), what happens when you want to launch a fourth program? ONE of those stacks needs to go, otherwise the CPU just can't use it. The S register is only 8-bits wide, and pegged to that specific page!

This means, of course, that task-switching on a 6502-based computer is a potentially expensive operation. This is why multitasking OSes for this CPU really strongly encourages you to use either a purely event-driven model (e.g., Contiki, GEOS) or really _tiny_ stacks. Keeping them under 32 bytes is quite strongly recommended, and the lower the CPU frequency, the smaller you want still.

What you describe doesn't seem to be a relocatable stack. And a relocatable stack pointer doesn't make much sense to me, as that's what the CPU uses to know where the stack is in the first place. You'd need a pointer to the stack pointer in order to move that about.

I think you have gotten the way the hardware stack works wrong. What you are describing is having 3 separate stacks in the one page, which, as far as I know, is not something the '02 can do in hardware. The whole of page 1 is reserved for the one stack that the '02 implements. You can read and write page 1 addresses, no problem, but it risks corrupting the stack. In the '816, I believe you can move where the CPU implements that stack. That, as I understand it, is a relocatable stack.
A stack can be software-implemented anywhere in memory, in exactly the same way as the '02s hardware does it, with few problems. That's sort of an exception to the page 1 nail-down.

Please keep in mind that I probably don't know what I'm wittering on about here.

EDIT: Oh, nooo. I didn't realise the above poster was Mr Falvo! He knows way more than me about this. Sorry...

DerTrueForce, the '816 has a 16-bit stack pointer, but this doesn't work the same as the direct-page pointer you might be thinking of. The described method of dividing the stack area into portions for individual tasks is right, and it can be done on the '02 in software. The 65816's direct page (DP) OTOH, although still always only one page in length, has a 16-bit DP register that dictates where the 256 bytes of DP will start. (They don't have to start on a page boundary, but it's slightly more efficient if they do, for example taking A00-AFF.) The hardware stack has no such register, even on the '816. If you want to go to another task's section of the stack area, you have to save the S (stack pointer) register, change it to what it should be now for the next task, and activate that task. The 816's 16-bit stack pointer allows you the room to designate a larger stack area and divide it into lots of sections without risk of them stepping on each other, even with lots of use of the hardware stack to pass parameters. The '816, with its stack-relative addressing modes, makes such parameter-passing work a lot better than the '02 does in this respect, and it tends to get used more than the 6502's stack in this way. You can also set the DP to overlap the hardware stack so you can get DP addressing modes in the stack area.

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

You can have as many stacks as you want on the 6502, within $0100..$01FF. You just have to manage the stack pointer accordingly.

You can have as many stack pages as you want too, you just have to make sure that the one the CPU is accessing at any given time is currently within $0100..$01FF.

In a multitasking system, there is only ever one task running at any given time. The task scheduler determines which task is running. It also moves the stack, and adjusts the stack pointer as needed.

The advantage of the '816 is that you can relocate the stack page without actually moving the contents of the page. All you change is the pointer that points to the stack page.

True that. However, it doesn't prevent one job from arbitrarily changing its stack pointer and stepping on another job's stack. Nor does it prevent scribbling on the stack below the current job's stack due to a lot of pushes. This limitation of the '816 is discussed elsewhere around here.

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

This is what all the small processors lack, wether they can or cannot relocate the stack: Memory protection! Even if you can relocate the stack, it cannot be isolated and a gone wild task can store to a foreign stack (or anywhere else in foreign RAM).

For a rugged multitasking system preemptive scheduling is only a part of the story. IMHO memory virtualization and protection schemes are the more important part. If you can't do this on your processor you might as well stick to cooperative scheduling, which is far more simple to implement.

_________________
6502 sources on GitHub: https://github.com/Klaus2m5

Yes -- well worth mentioning. It's perhaps natural for anyone learning about multitasking to gravitate toward pre-emptive schemes. But if cooperative schemes are not also considered, that's a serious oversight.

Re memory protection, I recently stumbled across a short piece that discusses the use of the 6829 (an old Motorola MMU chip) in this context. You can find "An Early MMU" about halfway down this page. (A 6829 would probably interface very easily with a 65xx system. But questionable availability -- and the poky 2 MHz clock limit -- argue against such a plan. Even so, the piece makes interesting reading.)

Slightly OT: the page is part of http://www.ganssle.com. The author, Jack Ganssle, is a seasoned embedded engineer who has posted lots of interesting material. I recently subscribed to the newsletter he publishes, and I suspect other forum members may wish to do the same. (The MMU link is actually the latest edition of the newsletter.)

-- Jeff

_________________
In 1988 my 65C02 got six new registers and 44 new full-speed instructions!
https://laughtonelectronics.com/Arcana/ ... mmary.html

Even the Linux kernel wasn't fully pre-emptive for years. Even now you can turn it off, and yield only at certain points (e.g. system calls).
So yes, virtual (or logical, so as to not confuse with virtual 'disk' memory) memory space for a process is the key to protected multitasking.