Need some advice on threading on a Z80

[JamesIsAwkward]

Hey everyone,

I've been working on a totally custom Z80 computer project on and off for a while, but here recently I've really dove into it!
It is a modular design and will ultimately end up with cards on a backplane (rc2014 style with a dumb backplane). CPU card, serial card, video card, etc.

So I'm at the point where I need to make some decisions with my software and hardware philosophy before going any further.
I think I will make each discussion a separate thread because these are things I haven't seen discussed elsewhere and might end up being useful to someone in the future.

So to avoid an XY problem I will state my end goal. I am building a "real" kernel (as real as you can get with this old CPU) with a "true" OS sitting on top of it. I'm doing a filesystem (likely FAT16 to save me a headache), syscalls, everything.


While I was building my video circuit it hit me... if I hope to ever do a GUI with mouse and windows and etc, as slow as it might be, I will pretty much HAVE to have threading.


I've been doing a ton of reading and messing with some code and threading isn't really that tough to implement. My hang up is the rate in which I interrupt the Z80 to make it swap threads.
Everything I've found on the topic never mentions the frequency in which they swap threads, so I really don't know where to start. It just seems like an arbitrary number...

I'm all torn between using Mode 2 Interrupts and just a regular ol' Mode 1 interrupt as well. I've kinda hit my budget limit on this project for now and so any Mode 2 stuff will have to be emulated with an AVR chip or something. I'm trying to keep my AVR "cheating" to a minimum and only use them when finding some old school ICs are difficult or expensive (like PS/2 or video controller ICs). This is actually going to be the topic of my next thread, emulating the Z80 Mode 2 interrupt "protocol" with AVR chips.



I'd love to hear any ideas you all have.

Thanks!

[tggzzz]

Consider an alternative: cooperative multitasking.

At any/every convenient point the task calls yield(), the PC "disappears down the plughole", and reappears up the plughole of whatever thread's yield() function is appropriate.

Easy to implement, avoids all sorts of problems - except that of an overly greedy thread.

Apart from that, if you really want to force swaps, then I'd say >=10ms is not unreasonable on a "real original" Z80. Unless there is reason to choose another interval, of course. By "real original" I mean running with a 4MHz(?) clock, not a Z80 ISA implemented in an FPGA. From memory, a contemporary 6800 calculating a floating point sine/cos pair would take around 30ms.

[MarkL]

You might find it helpful to look at the old multi-process MP/M operating system.  It ran on 8080 and Z80 CPUs.

MP/M user manual:

  http://www.cpm.z80.de/manuals/mpm1ug01.pdf

It used to be a commercial product, but long ago Digital Research released the source to it, CP/M, and a bunch of others:

  http://www.cpm.z80.de/source.html

To answer your specific question regarding system tick, they recommend 16.6ms or 20ms (60Hz or 50Hz).  Reference on page 106 in the above user manual.

[JamesIsAwkward]

@tggzzz:
My Z80 is a 10MHz CMOS version, but I intend to make sure my build is built with 4MHz in mind, at least at first! I might use the 10MHz clock later to do see how far I can push things!


I'm pretty new to Z80 ASM, how would cooperative multitasking look in software on a high level?

That sounds like I would have to code all of my programs to yield, instead of being forced by an interrupt. I'm not sure how that would look in the code...


I had a rough plan for my threading where I would also set some flags in memory for each thread to tell the system how to prioritize. For example, if the IO-heavy flag is set then we can prioritize those threads so that the CPU-heavy threads don't dominate and the IO thread just sits around.


Wrapping my head around this stuff has been challenging but that's why it has been so fun!


@MarkL:
Oh thank you for these links! I've been googling quite a bit about this topic and haven't came up with much. I'll dive into these and take a look!

[RoGeorge]

If I were to build a kernel and an OS on top, which is entirely a software exercise, then I would use something else than a Z80.  Back in the days of the Z80, the programs and the OSs for it were single user and single task.  You can improvise and mock some more recent features, but Z80 has no hardware support, only an interrupts vector table and a single non maskable interrupt at a fixed address.  IIRC, NMI is triggered by an edge, while INT is active while asserted, so you may lose interrupts or overflow the stack if you don't handle disable/enable interrupts inside the interrupt routines.


If I were to build a Z80 computer, which is a hardware project with some OS needed to make a use of it, then I will port the CP/M OS to my hardware.  CP/M was an OS before MS-DOS and has 3 components:  CCP, BDOS and BIOS.

To port it, you will only need to modify the BIOS, which is very small, about 10 functions or so, don't recall exactly the number, but they are very basic, for example put a char on the screen, or read next key, or write a sector to disk, things like these.  The BIOS in CP/M plays the role of the hardware abstraction layer, similar with the drivers from Linux or Windows.

If you write those few BIOS entries, then you will suddenly have a fully functional computer, with keyboard, display, serial port, printer and disk (including a file system and console commands, e.g. a DIR *.c will just work).

Even more, this will guarantee all the existing CP/M tools and programs will work:  C compilers, Basic interpreters, databases, debuggers, assambler/disassembler, disk editors, all the tools to check and repair disks, intercomputer files exchange (like Kermit), and all the text games and the programs ever written for CP/M will run just fine on your Z80 computer.

CP/M programs are easy to find online these days, many with sources too.  I remember CP/M was donated to the public domain some years ago, with complete sources and documentation, so it would be possible to change a few well documented BIOS functions, then cross-compile all on a contemporary computer.  Doable by a single person, and in a reasonable amount of time.

Then you can add mouse features to CP/M, as a software exercise (there was no mouse in the standard CP/M, so yours might become a nice contribution to an historic OS).

[JamesIsAwkward]

I considered rolling with CP/M but it sounded more fun for me to build something from scratch and just using projects like CP/M as references.

I know that the earlier CPUs like the Z80 or 6502 weren't really meant for this kind of thing, but to me that makes it more fun to tinker with.



You are correct about the possibility of losing interrupts, which is why if I do it that way I think I would have to make sure the scheduler routine always disables interrupts while working.
I considered buying a Z80 CTC and doing the interrupts the "right" way as Mode 2, which would allow more than just the thread interrupt because it places data on the bus that is used to jump to certain section of memory. So my PS/2 controller interrupt would jump to a handler, which would disable interrupts for the moment, manipulate whatever data, then turn interrupts back on before returning.


Either way, it just sounds neat to try this sort of approach and it isn't something a lot of people have done with their builds!

[tggzzz]

@tggzzz:
I'm pretty new to Z80 ASM, how would cooperative multitasking look in software on a high level?

That sounds like I would have to code all of my programs to yield, instead of being forced by an interrupt. I'm not sure how that would look in the code...

Not specific to Z80. It will have to be heavily constrained in one way or another, and there can be several styles.

For an event-driven real-time application a main() would be
initialize();
forever {
  event = yieldUntilEventInQueue();
  processEvent;
}

For something that gradually progresses to completion
main() {
  doX1;
  yield();
  doX2;
  yield();
  doX3;
  input = yieldUntilInputAvailable();
  outputY;
  yieldUntilOutputCompleted()
  doZ;
}

I had a rough plan for my threading where I would also set some flags in memory for each thread to tell the system how to prioritize. For example, if the IO-heavy flag is set then we can prioritize those threads so that the CPU-heavy threads don't dominate and the IO thread just sits around.

Which task to schedule first is a traditional question. Highest priority first? Earliest deadline first? Random? Round robin? What happens when a deadline is missed?

My preference would be for round robin, or possibly random. That emphasises that you really shouldn't be using priorities to ensure speed or fairness.

Don't forget about priority inversion problems, and priority inheritance.

Wrapping my head around this stuff has been challenging but that's why it has been so fun!

Yeah! Excellent

[tggzzz]

I know that the earlier CPUs like the Z80 or 6502 weren't really meant for this kind of thing, but to me that makes it more fun to tinker with.

"Doing more with less" and working out the fundamentals are both very rewarding.

CP/M was made for the Z80. It is sufficient to compile and run C programs, using a glass TTY and floppy discs for i/o. Slow, but doable.

[ledtester]

That sounds like I would have to code all of my programs to yield, instead of being forced by an interrupt. I'm not sure how that would look in the code...

Actually, even in a preemptive kernel software is written like it would be in a cooperative task-switching kernel. For instance, if you want to read the next keyboard character instead of busy waiting you'll call a kernel routine which will put your task to sleep until a new keystroke becomes available and then your task will resume at the point of the call. Same goes for sleeping/delaying for a certain amount of time. These kernel calls will do the yielding for you so you don't have to put yields explicitly in your code.

[nctnico]

There is a FreeRtos port for the Z80: https://forums.freertos.org/t/freertos-on-zilog-z80-with-z88dk/9174

[T3sl4co1l]

If I were to build a kernel and an OS on top, which is entirely a software exercise, then I would use something else than a Z80.  Back in the days of the Z80, the programs and the OSs for it were single user and single task.  You can improvise and mock some more recent features, but Z80 has no hardware support, only an interrupts vector table and a single non maskable interrupt at a fixed address.  IIRC, NMI is triggered by an edge, while INT is active while asserted, so you may lose interrupts or overflow the stack if you don't handle disable/enable interrupts inside the interrupt routines.

There was a Wang mainframe-and-terminals system (which one(s) I don't recall), which was multi-user and Z80 based.  What architecture, I don't know; it might've been multiprocessor, and, I don't know how smart the terminals were, but I think they might've used one apiece?

Probably not very many multi-user systems, overall.  It's certainly not a very powerful processor to want to do more than a basic level of task switching (say to handle hardware interrupts).

Tim

[JamesIsAwkward]

I just have to say how refreshing and fun it is to find some like-minded folks who love the old vintage tech. This project has been so fun and it knowing you all are here to bounce ideas off of makes it that much more enjoyable!

[JamesIsAwkward]

@tggzzz:

Not specific to Z80. It will have to be heavily constrained in one way or another, and there can be several styles.

For an event-driven real-time application a main() would be
initialize();
forever {
  event = yieldUntilEventInQueue();
  processEvent;
}

For something that gradually progresses to completion
main() {
  doX1;
  yield();
  doX2;
  yield();
  doX3;
  input = yieldUntilInputAvailable();
  outputY;
  yieldUntilOutputCompleted()
  doZ;
}

It seems to me that implementing a hardware interrupt and trying to handle that the best I can is the least complex way of handling this, at least for my build. What do you think?

Which task to schedule first is a traditional question. Highest priority first? Earliest deadline first? Random? Round robin? What happens when a deadline is missed?

My preference would be for round robin, or possibly random. That emphasises that you really shouldn't be using priorities to ensure speed or fairness.

Don't forget about priority inversion problems, and priority inheritance.

Yeah this is a really good point. Round robin would be easier to implement, but less efficient overall I'd say. But then again, this thing is currently running on a breadboard and I'm a total noob at this. So who am I to scoff at that tradeoff? I think this might be the way to go here.

[tggzzz]

@tggzzz:

Not specific to Z80. It will have to be heavily constrained in one way or another, and there can be several styles.

For an event-driven real-time application a main() would be
initialize();
forever {
  event = yieldUntilEventInQueue();
  processEvent;
}

For something that gradually progresses to completion
main() {
  doX1;
  yield();
  doX2;
  yield();
  doX3;
  input = yieldUntilInputAvailable();
  outputY;
  yieldUntilOutputCompleted()
  doZ;
}

It seems to me that implementing a hardware interrupt and trying to handle that the best I can is the least complex way of handling this, at least for my build. What do you think?

Interrupts should be able to occur anytime except in critical sections. The scheduler is too big to be a critical section.

Interrupt routine determines source of interrupt, captures sufficient information and creates corresponding event. Event is put in a queue, interrupt ends. That process of putting the event in a queue is a critical section.

Scheduler takes event from the queue, another critical section. Scheduler determines which task should run next, and runs it.

Critical sections must be atomic, and that can be achieved by disabling interrupts. If multilevel interrupts are allowed, then re-enabling interrupts means returning to the previous interrupt level.

Which task to schedule first is a traditional question. Highest priority first? Earliest deadline first? Random? Round robin? What happens when a deadline is missed?

My preference would be for round robin, or possibly random. That emphasises that you really shouldn't be using priorities to ensure speed or fairness.

Don't forget about priority inversion problems, and priority inheritance.

Yeah this is a really good point. Round robin would be easier to implement, but less efficient overall I'd say. But then again, this thing is currently running on a breadboard and I'm a total noob at this. So who am I to scoff at that tradeoff? I think this might be the way to go here.

Define what you regard as  "fair". Define what is necessary and desirable.

System design can be regarded as applied philosophy

[DiTBho]

As platform, why not Nintendo GB, which is ~z80? 

[T3sl4co1l]

As platform, why not Nintendo GB, which is ~z80? 

Graphical too!

Not much networking or other IO though.  Or storage beyond what's on the ROM.  Clearly they need a GBA: ARM based (ARM7TDMI 16MHz!) is powerful enough for multiple users, and has a link cable for networking!

Tim

[JamesIsAwkward]

As platform, why not Nintendo GB, which is ~z80? 

I thought about it! But rolling something from scratch that is 100% my own just sounds more fun lol!

Also I have come up with a name for my OS. KludgeOS

I think it is fitting haha

[DiTBho]

Or storage beyond what's on the ROM.

There are ROM/Flash + RAM cartridges for GB 
They can be hacked, reprogrammed, and the RAM can be turned into NVRAM with a smartsocket + battery.

[DiTBho]

I thought about it! But rolling something from scratch that is 100% my own just sounds more fun lol!

yup, it was the same for "my-fs", the filesystem I designed and implemented.

It is based on btree+ and it cannot be implemented on 8bit systems because it eats so much ROM and RAM that of the addressable 64Kbytes only crumbs remain.

So why not CP/M with its "small" "flat" file system? or why not FAT16/32 which is tini and pretty documented? well ... same answer as yours

I have come up with a name for my OS. KludgeOS
I think it is fitting haha

LOL, "Kludge" as an ill-assorted collection of parts assembled to fulfill a particular purpose

A lot of self-irony, I like it!

[JamesIsAwkward]

So why not CP/M with its "small" "flat" file system? or why not FAT16/32 which is tini and pretty documented? well ... same answer as yours

Oh I thought about it, I think I might roll FAT16 just to make it easier to load everything to my compact flash card at first.
Long term I'd like to roll something of my own and write it using the C library FUSE, but that's a lower priority project haha

[Codex]

Try a Z80-mult-CPU system  - The Z80 is able to nicely shares its bus, there are pins on the chip for this.  I worked on a bus system that had multiple z80 CPU cards in it, one handling comms, another IO and another handling the control loops, I sure there was 4 of them, was a long time ago.  Maybe an other handling all the clocks. They all had a shared memory block and their own memory blocks on a memory card.  Z80s have good support for this type of architecture. Your card system should be able to support this if you bring all those bus control lines. 

[DiTBho]

They all had a shared memory block and their own memory blocks on a memory card.  Z80s have good support for this type of architecture.

bus request? DMA? how did you share the memory?

[cj7hawk]

Hi James, Sorry to all for opening up an old post but I'd love to know how you went on this.

I'm doing something similar, and as I haven't had time to build the hardware, I wrote the OS and while I come from a background of non-preemptive multitasking code, have switched to a single thread for my latest build, and wrote a new version of CP/M which I published openly on Github a few months ago. The repository is called LokiOS, and includes a Windows-10 compatible z80 assembler and an emulated Z80 environment that matches the original believed Loki architecture developed by Sinclair in the 80s but that was never brought to market.
 
Anyway, I was wondering how you were progressing.? It would be great to hear about what you were further doing in this space.

On the topic of OS, I'd recommend considering CP/M over DOS structures.

My ultimate intent is to drop in a preemptive multitasking overlay on CP/M 2.2 ( or rather, on the rewritten CP/M I wrote, though in practice, it would work with CP/M 2.2 also ) as my existing architecture has hardware support for process IDs, including hardware switching of mapped RAM when a process is running, with support, ultimately, for up to 256 concurrent processes, although I'll probably drop that to around 128 for the prototype. This allows a kernel task switcher to occupy it's own process, interrupt any other process, restructure the MMU to page in the other process and whatever supporting memory blocks it used, execute it, then switch back to the current or next task while maintaining state.

At present, it's just running in an emulator as I develop it, and so far, the only hardware I have put together was a proof-of-concept 256x192 ( or 512x192 ) display card that runs off of just five small chips that were all from 1985 to avoid building it with anything not of it's era. It also has some interesting features, like an ISA backplane ( rather than say a RC2014 ) so should be able to take PC cards as well, if the bios are reprogrammed and it extends on stock CP/M 2.2 structures to provide things like resident drivers, extra-bios services and uses the standard CP/M 2.2 BDOS routines as a defacto MMU system, so it creates a process list that can be viewed like linux, but can be copied like DOS - eg, A "Snapshot" of a process can be saved with a simple copy command, and process use can be interwoven with ramdisk use in real time without the need for drivers - with all memory being accessed in one of three ways. Directly ( MMU maps 4K blocks over 64K ) - Indirect ( All memory is accessed as I/O space in 128 byte chunks as CP/M likes it ) - and Disk ( A process or even the video RAM can be opened up as a file, and read to and written directly ).

As you can imagine, this is built over the top of a compatible CP/M OS, so much of this is implemented in hardware rather than software, but it uses CP/Ms quirks to support it directly - so my MMU is mapped as M: drive, and showing a directory of M: shows all the current processes and memory mapping of the MMU, and this is all stored in the flat CP/M directory structure that lends itself to such applications which DOS FAT does not.

So if you want to introduce compatability with z80 software in an OS that can multitask, it's not that difficult to expand CP/M or even write your own to extend into multitasking even if you ignore MPM and Concurrent CP/M. Though the biggest task I had in writing CP/M from scratch in a new OS was actually making it CP/M compatible... That's an overhead that the DOS programmers didn't have.

Anyway, if you have an update on where your project has gone from here, I'd love to hear it! And maybe borrow any good ideas you developed in your travels. ( And you are welcome also to borrow mine... The OS I wrote is available and if you strip the LOKI architecture away from it, it's just CP/M... So much so that I include a copy of DRI's CP/M source with it and my OS can be swapped out with the original DRI CP/M BDOS or CCP at will and still works... ). Well, there's some bugs still in how they both come together, but mostly it works and it's more of use in debugging why CP/M software isn't working than in any practical advantage gained from hotswapping the BDOS and CCP.

Also, In case you're not familiar with solo-writing an OS, it is possible, but it's a big task. Writing a CP/M compatible OS from the ground up took me more than 3 months, or more than a year part time if you include the development environment... But I think the number of people who have written a complete OS without borrowing code can still be counted on one's fingers. Even CP/M itself had many builders.

Good luck with your endeavor.

David.

David.

[JamesIsAwkward]

cj7hawk hey sorry I disappeared for a while!


I ended up moving and most of my project stuff has been sitting in boxes since November or so!


I haven't gotten much further since I asked my question. I'm trying to build an OS from the ground up (and as a total beginner to this type of thing!) and so right now all I have is a 60hz timer hitting the NMI.



My project has slowed to a crawl because I've been working on designing the PCBs for my system and I'm a total noob at that as well. So it's been quite the challenge lol!

[SiliconWizard]

If you're envisioning some kind of memory protection, you can watch this:

(although the title is a bit "catchy", you may find a couple ideas in this.)

[brucehoult]

I don't know why it should be impossible. Adding external MMU was common on all such CPUs, even if only for bank switching (but it's the same thing). Preventing access to some banks is not hard. The only hard thing is being able to recover from an illegal access, make it legal, and continue the program. Some early 68000 machines with MMU had two chips with one running a couple of clock cycles behind the other so it could be halted before hitting the exception the first CPU hit.

[RoGeorge]

If you're envisioning some kind of memory protection, you can watch this:
video
(although the title is a bit "catchy", you may find a couple ideas in this.)

That video was discussed 2 years ago in another topic, it's a clickbait, and no Z80 feature discovery.

My conclusion from the other thread, after watching the video back in 2022:

Not a clickbait title, it's a lying title.

To spare others' time, no Z80 secret feature was discovered.  He wants to emulate protected mode in software, after adding some external hardware, then starts to fantasize about generic advantages of protected mode as if Z80 would have such a mode, except Z80 doesn't have any hidden protected mode feature.

[bson]

You always know when next to interrupt for a context switch; when you switch to a thread you look at the runlist, and if there's anything else that wants to run at the same priority you set a timer for your round-robin timeshare quantum, whatever that is.  100ms should be fine.  Anything else, like a button press, will interrupt the processor, and in the ISR you simply check to see if any thread is waiting for this, and if so flag it as runnable.  If it's higher priority than the currently running thread you switch to it (switch to its stack so that on exit from the ISR you return to its saved state); if it's lower you let the current one run, if it's the same you can use a number of scheduling approaches, but it's common to switch to it, temporarily slightly bump its priority by 1, and set a shortened quantum for the next context switch so it can process the event, then when it has run out of its quantum you drop it back down to its actual priority and let it compete like other threads.  Or you can simply switch to it.  Or you can do nothing, requiring a strict priority order where if two threads have the same priority they can only cooperatively context switch between themselves.  All scheduling can be done by setting a timer to a known quantum and allow ISRs to context switch, no "heartbeat" needed.  For clock you keep a timestamp in memory and run another timer; the current timestamp is the value in memory plus the timer; when the timer rolls over you update the value in memory.

[JamesIsAwkward]

Do you think a simple push/pop would keep track of thread data or should I dedicate some static kernel/OS RAM space to a certain number of threads to store this data?

[tggzzz]

Do you think a simple push/pop would keep track of thread data or should I dedicate some static kernel/OS RAM space to a certain number of threads to store this data?

Linked list of structures containing the thread data, principally the location of a thread's stack pointer.

Traversing linked lists is much more of a pain in the Z80 than it is in the 6800 While the IX and IY registers look useful, doing anything with them requires more instructions than is "reasonable". In practice using the 8080 registers is just as good, if not better (source: memory from >40 years ago )

[brucehoult]

Do you think a simple push/pop would keep track of thread data or should I dedicate some static kernel/OS RAM space to a certain number of threads to store this data?

Push/pop is for sure the fastest way to save the 4 main register pairs (11 cycles to push a pair, 10 to pop) and IX/IY (15 each to push, 14 to pop) compared to ld instructions.

The question is: do you push registers onto the thread's own stack (risks stack overflow), or to a dedicated area after first saving SP somewhere (which has essentially got to be a global variable, at least initially) and then setting it to point to the thread's register save area, however you find that (global array of threads, linked list ...)

[bson]

You have to reserve space for the saved registers somewhere... might as well be on the thread stack.  It's usually more straightforward as it can be done without clobbering registers.  If you're going to point SP somewhere you need to save it first, which means you need to load it, which means you clobber it.  So you'd have to push AF, HL and maybe more just to set up SP to point to the storage area, in which case you might as well just push the rest on the stack at the same time.

[JamesIsAwkward]

Okay you guys have a lot of good points.


I admit I'm out of my depth here so let me ask this to clarify...


Are you saying it would likely be easier/better to have a thread table in kernel space, and use that to save the thread data? I have a simple mocked up thread structure here, does this seem like the right path?

Code: [Select]

; Global thread memory map:
; 2 bytes for current running thread
; 1 byte for number of active threads - likely limited to 4 or 8
; 2 bytes to store temp SP value

; local memory structure per thread:
;   2 bytes for current thread struct address
;   1 byte for IO classification - for future use if I ever move to a priority based threading system, then I could set slow I/O to low priority and etc
;   1 byte for thread status - active or suspended, so thread handler can skip over the thread if it needs to
;   12 bytes for registers - dump of all thread registers
;   2 bytes for SP
;   2 bytes for PC -        possible to save with some trickery
;   10 bytes or so for future use
;   2 bytes for pointer to next thread


OR would it just be better to have a hybrid scenario. Use the thread table but don't push the registers there. I could push them to the stack and so long as I set the SP back to the correct place I could pop them all back out. Actually after thinking this out I think this is probably the better way.



What do you guys think?

Thanks for all of the advice, you all have been incredibly helpful. This has been a really fun project to work on!

[floobydust]

I don't see the Z80 alternate registers mentioned in the thread. In my day with the Z80 used the prime register set for fast context swaps with EX and EXX op-codes. Instead of time pushing registers on/off the stack.

[brucehoult]

Pushing the registers on to the same thread's stack is certainly the least code and the fastest. But sometimes stacks get full. How are you going to handle (prevent!) stack overflow during register saving?

Going the other way you'll need more than just a temporary (absolute address) to store the SP. I think you're going to need at least HL there too? Or maybe you have a global pointing directly to the current thread's register-save area. So you can start:

Code: [Select]

ld (spTmp),sp
ld sp,(currThreadRegSave)
push af
push bc
push de
push hl
push ix
push iy
ld hl,(spTmp)
push hl

And then at that point you have all registers free to figure out what thread to run next, but you don't have a stack. I guess if nothing else you need to make sure interrupts stay disabled.

I've forgotten (if you mentioned it) what kind of threading you're doing: cooperative, or interrupt-driven?

If the latter then of course PC and PSW are already on the current stack. And you do have to preserve everything else.

If it's cooperative threading where task switch looks like a function call then depending on what ABI you use for function calls you might not need to save and restore many registers at all -- or even none. I seem to recall a lot of compilers in the late 70s/early 80s didn't preserve the non-8080 IX and IY registers, even after the 8080 was dead and forgotten.

ISTR z80 function calls did mostly preserve registers. While 6502 code generally treated the registers (all 3 bytes of them!) as volatile except to whatever extent they were used to pass arguments or function results.

[brucehoult]

I don't see the Z80 alternate registers mentioned in the thread. In my day with the Z80 used the prime register set for fast context swaps with EX and EXX op-codes. Instead of time pushing registers on/off the stack.

That doesn't scale to more than two threads. You could let the OS/scheduler use the alternate register set, but when it comes time to switch user threads you have no choice but to switch to the main registers and save and restore them.

Potentially you could keep the address of current thread's register save area in an alternate register pair, and stash the SP in another temporarily.  But it's tricky. You can only move hl to sp (or ix, iy, but they don't have shadow registers), and you can't move sp to any registers -- you can only add (or subtract) it to hl. Which means you have to zero hl first, and so you can't be storing the new sp value there.

So you end up with a shuffle like:

Code: [Select]

exx
ld hl,0x0000
add hl,sp
ld b,h
ld c,l
ld h,d
ld l,e
ld sp,hl
exx
[code]

... instead of the previously mentioned ...

[code]
ld (spTmp),sp
ld sp,(currThreadRegSave)

.. which is 11 bytes of code vs 6, and I think more cycles too .. 51 vs 40?

[tggzzz]

Pushing the registers on to the same thread's stack is certainly the least code and the fastest. But sometimes stacks get full. How are you going to handle (prevent!) stack overflow during register saving?

You just take the stack size required for each thread's internal processing (varies according to each thread's call graph, fun when recursion is involved ), and add the constant space required by the RTOS (constant for all tasks, defined by the RTOS creator, therefore easy).

Whether you have enough RAM for all the task stacks is a separate issue.

Are you saying it would likely be easier/better to have a thread table in kernel space, and use that to save the thread data?

In a Z80, there is no "kernel space" per se. There is just a single uniform unprotected address space.

Keep the thread-specific data (i.e. registers) on the relevant thread's stack. Keep the kernel-specific data somewhere else.

The kernel only needs to keep a linked-list of nodes, each node representing one thread. The node only contains a pointer to the stack pointer for its thread. The kernel chases along the linked list until it finds the relevant thread/node, then follows the pointer to the stack, pops the registers off the stack, and resumes that thread.

[cruff]

Keep the thread-specific data (i.e. registers) on the relevant thread's stack. Keep the kernel-specific data somewhere else.

Allocate the thread structure at the top of the thread's stack area (assuming the stack grows down) and set the thread's stack pointer just below that structure when starting it. That way you know you always have the required storage to switch threads. Of course you can't protect it from under flow by the thread, but that won't happen in properly written code.

[JamesIsAwkward]

In a Z80, there is no "kernel space" per se. There is just a single uniform unprotected address space.

Yeah, I should have put "kernel space" in quotes there too. What I meant by that is literally kernel space in RAM.

Keep the thread-specific data (i.e. registers) on the relevant thread's stack. Keep the kernel-specific data somewhere else.

Yeah this is my goal! I'm writing the kernel code in a unix-like way that will abstract the hardware and stuff away from user-space programs. Syscalls and the like.
I think doing that will minimize me ever entering kernel space unintentionally. Granted I am very new at this and so I'm still learning the concepts haha

Allocate the thread structure at the top of the thread's stack area (assuming the stack grows down)

Okay I'm trying to wrap my head around this so bare with me 
When you say thread stack do you mean to have a separate thread stack allocated in the kernel RAM area? Or are you just calling the thread's SP and register data that is saved somewhere in the true stack a "thread stack"?

and set the thread's stack pointer just below that structure when starting it. That way you know you always have the required storage to switch threads. Of course you can't protect it from under flow by the thread, but that won't happen in properly written code.

I understand what you are saying and this is a great idea, but as far as having RAM space for additional threads when they are created I think I will just do a hard coded number of threads for now. I can worry about a dynamic number later where RAM size will be an issue. I don't really see needing to run more than 8 threads... but I'll get back to you when I add networking and other I/O lol


I finally have my hardware back up and running again, I moved earlier this year and my breadboard needed some TLC to get it all in working order. I'm going to do some experiments with 2 simple threads today and see if I can put yalls advice into action!

[bson]

Pushing the registers on to the same thread's stack is certainly the least code and the fastest. But sometimes stacks get full. How are you going to handle (prevent!) stack overflow during register saving?

You still have to allocate the memory somewhere.  Might as well add it to the stack size.

[bson]

Allocate the thread structure at the top of the thread's stack area (assuming the stack grows down)

Okay I'm trying to wrap my head around this so bare with me 
When you say thread stack do you mean to have a separate thread stack allocated in the kernel RAM area? Or are you just calling the thread's SP and register data that is saved somewhere in the true stack a "thread stack"?

Not sure what you're talking about.  Each thread has a stack and when you context switch you change to the running thread's stack.  There is no such thing as "the true stack".  It's also common to have a separate interrupt stack, so even though an interrupt may push context onto the running thread's stack, whenever non-trivial processing needs to occur a switch is made to a dedicated interrupt stack.  This is so each thread doesn't have to provision for the overhead of interrupt processing.  On a Z80 this may not matter, but "real" systems will do things like drain ethernet buffers/respond to drain events (DMA completion) and do real work at lowered interrupt priority levels (IPL) as such systems need interrupt nesting.  Some systems also have high-priority kernel threads for this, so instead of switching to an interrupt stack they switch to a kernel thread, which runs at high enough priority that only a higher-priority kernel thread (for a higher priority hardware event) can preempt them.  This is preferable on SMP and NUMA systems with multiple sockets, especially in the latter where you want the socket close to the hardware, so you run a kernel interrupt service thread with a socket affinity.  On SMP systems you can't just block out interrupts and user space code while servicing interrupts, and a thread model allows for locking and such.  But, fundamentally, a thread is pretty much a stack.

[JamesIsAwkward]

Not sure what you're talking about.

Hey don't worry, I don't either! 

Sorry let me try to articulate better, I'm doing a poor job!
"True stack" was a poor description of what I meant.

By "true stack" I was trying to describe the stack as a whole, not just the thread stacks, but the actual z80 stack itself.
But I got myself confused on that last post so you can ignore it lol. I was getting worried about the different thread stacks overwriting each other if one of them extends too far or something.

But it is obvious that problem is solved by just defining the stack space for each thread in the table. It also wouldn't be very difficult to add a dynamic stack size when calling for a new thread and supply the desired size.



Sorry I feel kinda dumb here haha, so yeah just disregard that last post!

[tggzzz]

Not sure what you're talking about.

Hey don't worry, I don't either! 

Sorry let me try to articulate better, I'm doing a poor job!
"True stack" was a poor description of what I meant.

By "true stack" I was trying to describe the stack as a whole, not just the thread stacks, but the actual z80 stack itself.

At any instant, one thread is executing and there is one SP pointing to the location of that thread's stack.
At a different instant there may be a different thread executing, and therefore the same SP pointing to the different location of the different thread's stack.

When threadA relinquishes control, your scheduler is responsible for

• saving the registers (including PC) at that instant on the stack (i.e. in this case threadA's stack)
• saving threadA's SP in some structure which includes whether threadA is runnable. Typically all those structures are stored in an array or linked list within the scheduler.
• determining which thread to run next (e.g. thread N), based on the information in each of those structures
• loading threadN's SP from the structure
• loading threadN's registers from the stack (i.e. in this case threadN's stack)
• setting the PC to be the value loaded from the stack

For the avoidance of doubt, that cannot be done in C, since C has no concept of an SP. You have to use a small amount of machine code to twiddle SP.

[brucehoult]

For the avoidance of doubt, that cannot be done in C, since C has no concept of an SP. You have to use a small amount of machine code to twiddle SP.

Having done this a few times over the years, I can say that you can SWITCH between threads in pure C, using setjmp & longjmp. The only thing you can't do in C is initially set up the PC and SP for a new thread.

Not that it matters -- no one should be afraid of writing a little assembly language.

When we ported our embedded software to Windows I had to write my own setjmp & longjump anyway, as Microsoft's ones did some extra SEH bollocks which made them not work for either switching threads or exception handling the way we used them.

[cruff]

When you say thread stack do you mean to have a separate thread stack allocated in the kernel RAM area? Or are you just calling the thread's SP and register data that is saved somewhere in the true stack a "thread stack"?

In a system with address space protection you can save it in the kernel writable area, although it doesn't really matter as the time period during which you have to save the registers that thread is not executing and thus cannot modify that storage area. As others have said you have to allocate the space for them somewhere.

Although for the thread specific metadata you obviously wouldn't want to allocate that in the thread's address space as that data is used by the OS to perform scheduling decisions and unexpected alterations can lead to crashes or security problems (think gaining privileged access or altering the thread's scheduling priority).

However, since you are on a Z80 you likely don't have protected memory so those conceptual distinctions, while being good for documentation and reasoning about data use, it could be susceptible to wild pointer access problems, etc.

One example of hardware managed protected address space is on the Harris HD6120 PDP-8 on a chip where there is an address space known as "control panel memory" which can be used to emulate the old front panel lights and switches of older PDP-8 computers. That is not accessible by the normal code you'd think of as being in control over a computer like that. There is support for trap entry into control panel mode that switches state, which is similar to the kernel/user mode support on many current CPUs.

[cruff]

Also push the address of your OS's thread exit function at the top of the thread's stack when creating it, then if the thread returns from the entry point routine, your OS will automatically gain control and perform cleanup.

[tggzzz]

For the avoidance of doubt, that cannot be done in C, since C has no concept of an SP. You have to use a small amount of machine code to twiddle SP.

Having done this a few times over the years, I can say that you can SWITCH between threads in pure C, using setjmp & longjmp. The only thing you can't do in C is initially set up the PC and SP for a new thread.

Does that require any restrictions on how C is used, e.g. not yield()ing within a function invoked by a thread?

I've managed to avoid using evade setjump and longjump. Anytime they might have been beneficial I've either used a different language/environment, or preferred to code sufficiently defensively (i.e. visibly, understandably  ) that they weren't necessary.

Not that it matters -- no one should be afraid of writing a little assembly language.

I'll take it slightly further: everybody should expect to have to look at the machine code output, to verify the machine will do what they think they've told it to do.

When we ported our embedded software to Windows I had to write my own setjmp & longjump anyway, as Microsoft's ones did some extra SEH bollocks which made them not work for either switching threads or exception handling the way we used them.

"Embedded" and "Windows": two concepts I've managed to completely compartmentalise As far as I'm concerned, they are orthogonal concepts.

That was one of the good things about DOS: it was a program loader that your program could completely ignore

[brucehoult]

For the avoidance of doubt, that cannot be done in C, since C has no concept of an SP. You have to use a small amount of machine code to twiddle SP.

Having done this a few times over the years, I can say that you can SWITCH between threads in pure C, using setjmp & longjmp. The only thing you can't do in C is initially set up the PC and SP for a new thread.

Does that require any restrictions on how C is used, e.g. not yield()ing within a function invoked by a thread?

Absolutely not!

That's the whole point of using setjmp/longjmp. They preserve PC, SP, and all callee-save registers.

If you can only yield() from the main function of a thread then that's just a matter of structuring the main function as a switch (nextState) { } and yield() is just setting nextState and returning from the main function.

setjmp/longjmp gives proper yield()

When we ported our embedded software to Windows I had to write my own setjmp & longjmp anyway, as Microsoft's ones did some extra SEH bollocks which made them not work for either switching threads or exception handling the way we used them.

"Embedded" and "Windows": two concepts I've managed to completely compartmentalise As far as I'm concerned, they are orthogonal concepts.

It's always beneficial to be able to unit test embedded software on a desktop PC, if not run the entire program.

It worked on Mac and Linux using the standard libc setjmp & longjmp. Only Windows needed custom ones.

[tggzzz]

When we ported our embedded software to Windows I had to write my own setjmp & longjmp anyway, as Microsoft's ones did some extra SEH bollocks which made them not work for either switching threads or exception handling the way we used them.

"Embedded" and "Windows": two concepts I've managed to completely compartmentalise As far as I'm concerned, they are orthogonal concepts.

It's always beneficial to be able to unit test embedded software on a desktop PC, if not run the entire program.

It worked on Mac and Linux using the standard libc setjmp & longjmp. Only Windows needed custom ones.

Agreed. Not difficult either, provided you give a little thought to structuring your code so it includes an informal HAL layer

I first did it with a MicroSoft operating system, running on a PDP-11. Happy daze.

[JamesIsAwkward]

Alright I have it figured out!

It took me a ton of experimentation to get it to work right, and with only 2 threads, ha!
Most of my bugs were just bad memory management. I had to brush up on Z80 endianness and what not.

@tggzzz pretty much summed up the process perfectly.
I created a thread handler that fires off when my external interrupt goes active, this pushes the current thread's registers to its stack, then saves the thread's stack pointer value inside of the thread's data structure in memory. Next it grabs the next thread's data structure, grabs the next thread's stack pointer value, changes the SP to the new thread's SP value, POP's the registers and then RETs.  This pushes the new thread's program counter back to the value it was when running previously.


I created a very basic NEW_THREAD routine that helped stage a couple of test routines (routine0 prints 0 to terminal, and routine1 prints 1). It set the areas of memory where the PC's should be to their routine start addresses, then set each routine's SP 16 bytes back in order to account for the POPs from the thread handler.


It's very rough but it is a proof of concept.

Improvements to be made:

• Remove hard coded 2 thread system, move to dynamic system that uses flags on the thread structure to determine status and act from there
• Create routine for closing threads and freeing up their memory
• Create a way for threads to request more or less stack space when first init'd, right now it's a static amount. This would require my routines or "executables" to follow some kind of standard and have headers similar to ELF... and would also increase the complexity of the routines that handle finding each thread's stack. I'd have to end up using linked lists or something
• MAYBE: Allow some threads to have higher priority (I/O limited threads can be checked less often and core services will be ran more etc)

Threading will be integral to my overall design because I want to create a rudimentary GUI desktop in the future, which is pretty much impossible without threading.

Now that I kind of have my head wrapped around how this works I think I'm going to start actually designing my "kernel".
Maybe that discussion would make for another fun thread?

[tggzzz]

Consider avoid having the thread request more stack. Instead have a data structure that defines a thread's entry point, stack size, and any other resource requirements. Determine whether resources are available; if not don't bother to create the thread.

Personally I like only three thread priorities: normal, interrupt, and emergency panic.

Having multiple "normal" priorities causes priority inversion problems, and invites twiddling priorities to "get it to work not fail (yet)".

Comms between threads is best achieved with messages+queues, not with fork/join and similar. That enables easy debugging and operation monitoring. Interrupts also communicate with threads using messages.

I also like cooperative scheduling, where each thread reaches a convenient point and then calls yield(). That does require applications to be structured sympathetically, but fits naturally with event-based and finite state machine based architectures.

[JamesIsAwkward]

Consider avoid having the thread request more stack. Instead have a data structure that defines a thread's entry point, stack size, and any other resource requirements. Determine whether resources are available; if not don't bother to create the thread.

This is exactly what I was thinking! The executable header could have the resource requirements and then the kernel could decide if it has the spare resources to run it.

Personally I like only three thread priorities: normal, interrupt, and emergency panic.

Having multiple "normal" priorities causes priority inversion problems, and invites twiddling priorities to "get it to work not fail (yet)".

Yeah I think you may be right here. I like the idea of prioritizing memory bottlenecked threads over I/O threads but it would add a lot of complexity to my thread handler. I'm a big fan of getting a base system running then add more advancements later. I'll keep it simple for now lol

Comms between threads is best achieved with messages+queues, not with fork/join and similar. That enables easy debugging and operation monitoring. Interrupts also communicate with threads using messages.

This is where my knowledge totally breaks down. I need to do more reading on inter-thread communication to figure out how to handle this. Would you care to explain the high level
idea behind messages and queues vs implementing a fork system?

[tggzzz]

Comms between threads is best achieved with messages+queues, not with fork/join and similar. That enables easy debugging and operation monitoring. Interrupts also communicate with threads using messages.

This is where my knowledge totally breaks down. I need to do more reading on inter-thread communication to figure out how to handle this. Would you care to explain the high level
idea behind messages and queues vs implementing a fork system?

That would take a book!

Start by thinking at a high level way of describing what your application has to do, and how it does it. Structure your architecture to reflect that. Find design patterns that match your architecture's concepts. Often events, actions and FSMs are a good start. They work at many levels from hardware logic to telecom billing systems.

Understand the concepts in UML State diagrams (Harel StateCharts), and Sequence diagram. You don't need to use all their features in their full glory! Just use the simple bits.

Understand the concepts in Hoare's Communicating Sequential Processes, as implemented in Transputers/xCORE/TMS320, Occam/xC/Go etc.

Understand the concepts in Apples "Grand Unified Junction". EDIT: Grand Central Dispatch.

Events are messages that message sources put() into named FIFOs. Examples: "hotter button pushed", "set power to X", "new value of temperature is Y", "switch to emergency mode". Other threads get() messages from named FIFOs, and do whatever actions are required based on the message contents. For example, on receiving a "new temperature" message, a temperature controller might recalculate the power required and send a "set power" message to the output device.

FIFOs can be one deep (often called message/mail boxes) or a fixed depth.
If a FIFO is empty and a get() is attempted, one variant stalls the thread until a message is available, another returns immediately indicating nothing was extracted.
If a FIFO is full and a put() is attempted, one variant stalls that thread until the message has been inserted, while another returns immediately indicating it wasn't inserted. The former is effectively "waitUntil()" operation, the latter could be used to implement a waitUntil(X or Y or...) operation.

[brucehoult]

Understand the concepts in Apples "Grand Unified Junction".

Grand Central Dispatch?

[tggzzz]

Understand the concepts in Apples "Grand Unified Junction".

Grand Central Dispatch?

<mutter>Bollocks</mutter>

Useful correction. I knew what I meant, honestly!

[JamesIsAwkward]

man I really appreciate the help here! I'm going to chew on this for a while and start reading!

[tggzzz]

man I really appreciate the help here! I'm going to chew on this for a while and start reading!

It is a pleasure to help someone that formulates decent questions, listens, thinks and understands.

That isn't as common as we would like

[JamesIsAwkward]

Well I'm glad my questions are keeping you sharp!



I think I like your idea of co-op threading... how do you feel about this approach:
I scrap my current thread_handler, and repurpose the 60hz timer on the INT pin to fire a routine that increments a 3-4 byte section of memory. The ZX spectrum does this with its vblank signal and updates a 24bit section of memory to keep track of time.

Then, like you suggested, I can have my threads yield() after their main() loop reaches the end (that I will have to consciously write to be as quick/small as possible).
When this happens, the thread can check to see if a certain amount of elapsed time has passed (16ms maybe?), and if so it will gracefully yield to the thread handler. If the time allotment hasn't passed it will have the option of running its main() again.. or yield if it is done.

This means if a program/routine needs to do something that will likely take more time than 16ms or whatever I set, I will need to write the loop in a way that can do it in pieces and in a thread safe manner...

Pair this with a message queue, like you also recommended lol, then the thread handler can still be round-robin style but the threads can check to see if they have the message they are waiting for, and if not then they can just yield() again. I'm only planning on doing 8-16 threads max so the process of iterating through them and checking should be fast enough that it wouldn't matter.... I think?


Also I'm still thinking of my thread status flags, I'm thinking maybe "running", "suspended", and "queued" flags? Queued being the thread is ready to start but hasn't been started yet? I'm not sure about these yet though. Though I'm pretty certain on the "running" flag of course haha


That sound like a decent plan or have I missed something?

[JamesIsAwkward]

Also to add.. while I'm coding this it doesn't feel as "elegant" as the kernel handling all of this.. I mean its not much to add a couple of lines to call routines that check the elapsed time or yield but it doesn't feel as "nice" haha

[tggzzz]

My preference is that a thread should run for as long as it deems desirable, and then yield(). That leaves the thread's application logic to state when it can safely be "interrupted" by another thread. There is no need for the RTOS or compiler or library to have an concept of thread safety.

Having a specific tick size smells of pre-emptive non-cooperative threading.

Consider just having your threads like this...

do something
getBlocking( fifoA )
do something else
getBlocking( fifoB )
etc

where getBlocking( aFifo ) implicitly yields, and tells the RTOS to only return when aFifo has something in it.

A generalisation would be whichFifo=getBlockingSelect( fifo1, fifo2 ), which tells the RTOS to only return when at least one of the FIFOs has something in it, and let the thread know which fifo is not empty.

Another alternative is tick+getTime(); getBlockingOrTimeout( aFifo, tick+5 ), which will return if either aFifo contains something or getTime() > tick+5.

[T3sl4co1l]

The hazard of course is, cooperative requires cooperation, and you can't guarantee that with buggy or arbitrary code.  For example, can you guarantee that all code paths and loops through a given function/module terminate within a reasonable time frame?  I certainly can't, not that I'm a particularly bad coder or anything, but even small, well-crafted examples of the Halting Problem (taking practical functions over pathological extremes) are very rapidly nontrivial to prove.

Cooperation is also fairly trivial to implement, you don't need to smash anyones' stack, everything can be cleaned up neatly before return (yield() is more of a RET ... PROC entryPoint (...) syntactic sugar, than a function call as such -- an example of an inverted hierarchy); you can implement this in pretty much any language, even, you don't need ASM to glue it together, or interrupts or anything.  It's great, when it works... but you can't guarantee that it works *in general*.

Meanwhile, the user wants to see a response, some time this...century y'know, so inevitably a thread must be stopped, shelved on the stack, and context switched over.

As I recall, this was a major complaint of early Macs, that were supposed to be cooperative but inevitably certain user programs would hang the whole system and become unresponsive, whether briefly (longer thread time than specified/desired) or pathologically (infinite loop, have to break or reset).

A yield() is definitely a nice-to-have in a system -- or just a wait(tics) or what have you -- but it doesn't need to be implemented differently, and adds more complication to do so.  That said, there's still some justification: it can be more efficient, the thread managing its own stack at-will to save on RAM+CPU overhead by the kernel sometimes (most of the time, even?).  To take that advantage, you'd need a flag to say how it was halted and thus how to resume, and, if you're allocating memory from a pool during halt, you could save the overhead of the standard stack frame and all that and use a smaller header, maybe it's allocated from a different array (fixed size allocations, but the thread object could be x or y size so pulls from pools {X} or {Y}), or arbitrarily sized and just put on the heap wherever; but mutating the size of an already-allocated thread object in-situ would seem a non-starter, and you'd need a much more dynamic system to take advantage (say, maybe there's an array of thread IDs, type/flags, and pointers to them; and the pointers can be at members of {X}, or {Y}, or {heap}).  Or also since we're talking such a limited platform: whether pointers are stored in extended memory, on what page(s), or via other means of access (HDD paging, networking, etc., depending on how deep and modern you want to go with it, lol).

Tim

[tggzzz]

The hazard of course is, cooperative requires cooperation, and you can't guarantee that with buggy or arbitrary code.  For example, can you guarantee that all code paths and loops through a given function/module terminate within a reasonable time frame?  I certainly can't, not that I'm a particularly bad coder or anything, but even small, well-crafted examples of the Halting Problem (taking practical functions over pathological extremes) are very rapidly nontrivial to prove.

I'm certainly not a fan of using formal methods to prove something; it is rare to find a problem/implementation where the proofs can be useful.

However, given an appropriate coding style and decent languages+tools, there can be useful timing predictions. Suitable coding styles are somewhat predicated on the application, of course. There are many applications - especially embedded - that do match.

Cooperation is also fairly trivial to implement, you don't need to smash anyones' stack, everything can be cleaned up neatly before return (yield() is more of a RET ... PROC entryPoint (...) syntactic sugar, than a function call as such -- an example of an inverted hierarchy); you can implement this in pretty much any language, even, you don't need ASM to glue it together, or interrupts or anything.  It's great, when it works... but you can't guarantee that it works *in general*.

True, but then nothing works "in general"

The context is a Z80, and how someone could implement something simple and basic. Anybody expecting to be able to implement anything much more than a CP/M program loader is going to be disappointed.

For non-cooperative scheduling of competing applications, I'd choose a different starting point!

Meanwhile, the user wants to see a response, some time this...century y'know, so inevitably a thread must be stopped, shelved on the stack, and context switched over.

As I recall, this was a major complaint of early Macs, that were supposed to be cooperative but inevitably certain user programs would hang the whole system and become unresponsive, whether briefly (longer thread time than specified/desired) or pathologically (infinite loop, have to break or reset).

I still see that with some web-based applications running in a browser

(Wadda you mean? Surely a browser is the operating system )

[JCK]

I haven't read this whole thread so I apologize if this has already been mentioned, but you might want to take a look at FreeRTOS, I believe there is a port for the Z80 and variants.  This is a great RTOS and well documented and studying it can give you a lot of insight into multi-threading, because it's written by experts.  I've used it for many, many years on various microprocessors with great success.

[woofy]

One thing I've not seen mentioned is that the Z80 does not have a position independent instruction set. Branches are limited to 128 bytes and there are no relative calls. It can be worked around but its a hassle. That means you cannot just load a program "somewhere" in RAM and expect it to work.
Are you intending to run CPM like programs with RAM at zero and programs starting at 0x100, or only your own code? 

Do you have a schematic of your current hardware you can share? It might help in suggesting options.

[radiolistener]

One thing I've not seen mentioned is that the Z80 does not have a position independent instruction set.

it has, for example JR, DJNZ.
For memory access you can use (IX/IY+offset) instructions which access memory relative to IX/IY register.

For JP/CALL you can also generate table and update it for specific address at runtime. This approach was often used on ZX Spectrum tools which allowed to load and run from any address.

Regarding to mutli-threading for Z80, I think this approach will not be effective due to slow speed and expensive context switch of Z80 core. There is just 64k address space for RAM, so you will lose a lot of RAM and performance resources just for context switch.

More effective approach will be to run two separate Z80 and have shared memory for data exchange.

[tggzzz]

One thing I've not seen mentioned is that the Z80 does not have a position independent instruction set.

it has, for example JR, DJNZ.
For memory access you can use (IX/IY+offset) instructions which access memory relative to IX/IY register.

Arguably useful for Fortran arrays, but IX<-(IX+offset) would be more useful for chaining down C linked structures.

Regarding to mutli-threading for Z80, I think this approach will not be effective due to slow speed and expensive context switch of Z80 core. There is just 64k address space for RAM, so you will lose a lot of RAM and performance resources just for context switch.

Remove the adjectives, and insert numbers. Then compare with requirements.

More effective approach will be to run two separate Z80 and have shared memory for data exchange.

And for 8 threads?

[brucehoult]

One thing I've not seen mentioned is that the Z80 does not have a position independent instruction set.

it has, for example JR, DJNZ.
For memory access you can use (IX/IY+offset) instructions which access memory relative to IX/IY register.

IX/IY are slow and use extra prefix bytes in the code. LD r,(IX+n) is 19 cycles vs 7 for LD r,(HL). If stepping through RAM by 1, INC HL; LD r,(HL) is 6 cycles faster.

For JP/CALL you can also generate table and update it for specific address at runtime. This approach was often used on ZX Spectrum tools which allowed to load and run from any address.

Load-time relocation was common on all old OSes for CPUs without efficient PIC. You can also relocate absolute addresses for data access, not only call/jump. It just needs a data table which can be discarded from RAM after the relocation is done.

Regarding to mutli-threading for Z80, I think this approach will not be effective due to slow speed and expensive context switch of Z80 core. There is just 64k address space for RAM, so you will lose a lot of RAM and performance resources just for context switch.

More effective approach will be to run two separate Z80 and have shared memory for data exchange.

Registers are only 16 bytes per thread! [1] You can fit the state for 64 threads into 1K of RAM. Do you seriously propose somehow using 64 separate Z80 chips instead?

RAM for each thread's stack is a far larger problem, which is not solved by using multiple Z80s with shared memory, unless only a portion of the address space is shared.

Sharing the Z80's zero page is also an issue, though it's used far less than the 6502's zero page (absolutely needed if you use indirect addressing), so you could simply not use zero page addressing on the Z80.

[1] 24 bytes if you allow each thread to own AF',BC',DE',HL' as well, which you probably should.

[JamesIsAwkward]

As far as hardware goes this is a totally custom build.

I've actually stepped back from the software side for a bit in order to finish designing my core PCBs. I'm starting to hit the limit of my breadboard space on my desk and it is time to move this project to proper PCBs.


I'm doing a modular setup so I've designed a simple backplane and some daughter cards (CPU card, memory card, UART, keyboard/mouse, Compact Flash, etc).


I think I disagree with the idea that the Z80 will struggle with threading. There are plenty of z80 operating system projects that are threaded and run great AND most of them are preemptive threading in nature! SymbOS and KnightOS are good examples. Especially since I'm likely going to do a hard limit of 8 threads (or maybe 16 if I can make it run well enough).


My memory card v1 will just be a simple EEPROM + SRAM setup so i can get this thing fabbed and back to writing some software again.
I'm working on designing a v2 that will support bank switching and also hopefully support swapping the EEPROM with SRAM after bootloading to reclaim that chunk of memory space. (which now that I think about it I'm going to have to use I/O space to interface with the MMU so I need to take another look at my memory map and onboard address decoders on my backplane before I fab it...)


I've attached a picture of the backplane. This is the first PCB I've ever designed so I'm totally open to criticism!

[SiliconWizard]

Fun stuff.

[tggzzz]

I think I disagree with the idea that the Z80 will struggle with threading.

Everything will struggle at some point.

One of the major decision points in embedded systems is which functions must be in hardware (for low latency and/or high throughput), and which can be in software. Matching all the timing constraints is a key issue!

I've attached a picture of the backplane. This is the first PCB I've ever designed so I'm totally open to criticism!

Are you taking all Z80 control signals directly onto the backplane? That's not normal practice.

Be cautious about whether buffers are needed; the Z80 pins are not intended to drive "many" loads that are a "long" way away.

[brucehoult]

I think I disagree with the idea that the Z80 will struggle with threading.

Everything will struggle at some point.

It's about 150 clock cycles to push all main and shadow registers and PC and save the SP somewhere. And the same to load the registers for the next thread. That's 300 cycles total. Allow another 100 cycles to figure out which thread to run next and you get 400 cycles. 100 µs on a 4 MHz CPU.

A Z80 can so a full task-switch 10,000 times a second.

Most OSes from the 1970s to this day switch CPU-bound tasks (that finish their time slice) 100 times a second. So on the Z80 you'll use 1% of the CPU time to do that task switching.

That's not awful.

[tggzzz]

I think I disagree with the idea that the Z80 will struggle with threading.

Everything will struggle at some point.

It's about 150 clock cycles to push all main and shadow registers and PC and save the SP somewhere. And the same to load the registers for the next thread. That's 300 cycles total. Allow another 100 cycles to figure out which thread to run next and you get 400 cycles. 100 µs on a 4 MHz CPU.

A Z80 can so a full task-switch 10,000 times a second.

Most OSes from the 1970s to this day switch CPU-bound tasks (that finish their time slice) 100 times a second. So on the Z80 you'll use 1% of the CPU time to do that task switching.

That's not awful.

As someone using a Z80 for hard realtime embedded systems written in C (except a few lines of stack twiddling, of course!) in the early 80s, I know it is possible.

As I'm sure you know, in embedded systems, latency and predictability are usually at least as important as raw throughput.

As for "struggling at some point", it is worth calculating how many floating point operations a Z80 can do per second

[brucehoult]

I think I disagree with the idea that the Z80 will struggle with threading.

Everything will struggle at some point.

It's about 150 clock cycles to push all main and shadow registers and PC and save the SP somewhere. And the same to load the registers for the next thread. That's 300 cycles total. Allow another 100 cycles to figure out which thread to run next and you get 400 cycles. 100 µs on a 4 MHz CPU.

A Z80 can so a full task-switch 10,000 times a second.

Most OSes from the 1970s to this day switch CPU-bound tasks (that finish their time slice) 100 times a second. So on the Z80 you'll use 1% of the CPU time to do that task switching.

That's not awful.

As someone using a Z80 for hard realtime embedded systems written in C (except a few lines of stack twiddling, of course!) in the early 80s, I know it is possible.

As I'm sure you know, in embedded systems, latency and predictability are usually at least as important as raw throughput.

The above times are for fully general low priority CPU bound background tasks with forced time-slicing. The real-time parts can of course be made interrupt-driven and save and restore a lot fewer registers. in most cases. You can also make the ABI treat some of the registers as temporaries, so task switches driven by completing a unit of work and voluntarily returning to the OS can save and restore fewer registers.

As for "struggling at some point", it is worth calculating how many floating point operations a Z80 can do per second

Z80 and 6502 would not be my choice for FP-heavy tasks. Even an AVR will absolutely slaughter them.

I'm not familiar with Z80 floating point libraries but I'd guess an 80 bit FP multiply would be 10,000-15,000 cycles, 40 bit 2500-3000, and 24 bit (16 bit mantissa) something approaching 1000 cycles.

Even the last of which is several times more than a task-switch, emphasizing my point that task switch isn't especially painful in relative terms. It's just simply a slow CPU in general. But were were glad to have them in the late 70s and early 80s!

[radiolistener]

Registers are only 16 bytes per thread! [1] You can fit the state for 64 threads into 1K of RAM.

At least 11 register pairs: AF, HL, DE, BC, IX, IY, AF', HL', DE', BC, SP

PUSH = 11 tacts, POP = 10 tacts.

At least 20 bytes memory and 231 tacts for registers.
With 3.5 MHz clock with no contention and 20 ms interrupt, it will eat about 0.3% time for context switch.

RAM for each thread's stack is a far larger problem, which is not solved by using multiple Z80s with shared memory, unless only a portion of the address space is shared.

yes, this is what I mean. And a part of 64k space is reserved for ROM.

If you use separate Z80 processors, they can have their own memory, with just one page shared between the two Z80s for data exchange. This solves the issue with stack memory because each Z80 has its own separate memory for the stack and other needs. This approach was used in some hardware controllers, which have their own Z80 processor and their own memory, separate from main Z80 processor and its memory.

The shared memory can be mapped to a switchable memory window, so you can completely hide it from each processor through the control port and use the full 64k address space for user task. In this way, only the OS core can map the shared memory to a specific window and use it for synchronization between the two Z80 processors.

[tggzzz]

If you use separate Z80 processors, they can have their own memory, with just one page shared between the two Z80s for data exchange. This solves the issue with stack memory because each Z80 has its own separate memory for the stack and other needs. This approach was used in some hardware controllers, which have their own Z80 processor and their own memory, separate from main Z80 processor and its memory.

How, exactly does your concept scale to 2,3,4... threads?

What are the disadvantages to your concept? (Yes, there are quite a few)

If you want to see your concept executed well and advantageously, understand the XMOS xCORE/xC ecosystem.

[brucehoult]

Registers are only 16 bytes per thread! [1] You can fit the state for 64 threads into 1K of RAM.

At least 10 register pairs: AF, HL, DE, BC, IX, IY, AF', HL', DE', BC

You didn't read my "[1] 24 bytes if you allow each thread to own AF',BC',DE',HL' as well, which you probably should." ?

I'd imagine that C-generated code won't be using EX / EXX, but I could be wrong. It's possible to know the answer for any given compiler.

You forgot SP and PC, which complete the 24 bytes.

PUSH = 11 tacts, POP = 10 tacts.

A bit more for IX and IY, and SP needs special handling. And you need an EX and an EXX in there somewhere :-)

With 3.5 MHz clock with no contention and 20 ms interrupt, it will eat about 0.3% time for context switch.

I was guuesstimating 1% with 10 ms interrupt, but I was padding it a bit, to allow some clever choice of which thread to run next.

You may also want to reserve a few bytes of zero page for local variables, as that's much faster than stack access. At least 16 bytes, maybe 32. That will need swapping too. The rest of ZP for non-swapped small globals and small constant data (SBSS, SDATA).

[radiolistener]

How, exactly does your suggestion scale to 2,3,4... threads?

What are the disadvantages to your suggestion? (Yes, there are quite a few)

Technically, you can use as many Z80 cores as you wish. Just use a separate shared page for each Z80 core. When the OS needs to perform data exchange with processor number 7, it simply writes 7 to the control port and reads/writes its memory through the address space window.


If you want to have more than 256 Z80 cores, you can use higher address lines as a data line for port read/write. In such way you can read/write port with 16 bit data at one operation (this hack was used on some Z80 machines). 16bits allows you to address 65536 Z80 cores. 


Also, if you use paged memory, you can share the entire memory among all Z80 cores. The OS will then assign the appropriate pages to each Z80 core address space. For example, if you use hack with 16-bit port data, you can address 65536 banks of memory x 16k = 1 Gigabyte RAM and 65536 Z80 cores

For example, you can split the 64k address space into four windows, using the first window for the OS ROM and the remaining windows for mapping selected RAM pages. Each Z80 can read its ID number from a specific hardware port. When the machine starts, the first core (#0) performs the memory assignment for all Z80 cores and sends commands to start them. At startup, each processor checks its ID. The processor with ID == 0 becomes the supervisor, the rest waiting for supervisor commands.

To simplify the task, you can start with 4 to 8 Z80 cores and 4 MB of RAM. You can implement such entire system, including the Z80 cores, on a single modern FPGA chip. I think you can run each Z80 core at 100 MHz or possibly even more.

The main issue here is limited 64k address space of Z80, its very non comfortable to work with paged memory. Much more sweet to use modern 64-bit core processors, where you can use flat memory with no need for memory page twiddling. 

[tggzzz]

I suggest you (re)read the first and subsequent posts in this thread. It is about microprocessors, not cores.

You outline some hardware, without noting the scaling and contention problems as you increase the number of threads and processors.

After that you need to address the difficult problems: high level (application) and low level (comms mechanism) software.

Hint: understand the way xC language seamlessly works with the xCORE processors.

[radiolistener]

I suggest you (re)read the first and subsequent posts in this thread. It is about microprocessors, not cores.

When I wrote word "core" I mean Z80 microprocessor. 

You outline some hardware, without noting the scaling and contention problems as you increase the number of threads and processors.

As I wrote before, the way that I described is well scalable up to 65536 Z80 CPU's and up to 1 GB RAM.
But if you use so many CPU's the init may take some significant time, because Z80 is not fast core.

After that you need to address the difficult problems: high level (application) and low level (comms mechanism) software.

What difficulties? For example, this architecture allows running multiple ZX Spectrum instances in parallel using their original ROM images without modification. And it won't be able to detect that it's running on a multi-core Z80 machine if you want to lock it. You can use hardware locks for control registers to restrict writes to them from a specific OS ROM page, similar to how it was implemented in TR-DOS for WD1793 ports on the ZX Spectrum.

Memory management and IPC code can be implemented in OS ROM, so the user code can use standard RST call with requested function.

I have experience with implementing such system on Z80 in the past.

But as I said before, with modern MCU/CPU, it don't have sense. The main difficulties here is 64k address space limit and low speed, but it don't related to multi-threading. This is real bottleneck, but this is Z80 architecture difficulties.

So it's better to play with more modern MCU/CPU.

[tggzzz]

I suggest you (re)read the first and subsequent posts in this thread. It is about microprocessors, not cores.

When I wrote word "core" I mean Z80 microprocessor. 

You outline some hardware, without noting the scaling and contention problems as you increase the number of threads and processors.

As I wrote before, the way that I described is well scalable up to 65536 Z80 CPU's and up to 1 GB RAM.

While it might be claimed that cores could be scalable to a small fraction of that number, with microprocessors it isn't sensibly scalable.

After that you need to address the difficult problems: high level (application) and low level (comms mechanism) software.

What difficulties? For example, this architecture allows running multiple ZX Spectrum instances in parallel using their original ROM images without modification. And it won't be able to detect that it's running on a multi-core Z80 machine if you want to lock it. You can use hardware locks for control registers to restrict writes to them from a specific OS ROM page, similar to how it was implemented in TR-DOS for WD1793 ports on the ZX Spectrum.

Memory management and IPC code can be implemented in OS ROM, so the user code can use standard RST call with requested function.

I have experience with implementing such system on Z80 in the past.

It looks like you don't understand how multiprocessor/multithreaded code and hardware can appear to work most of the time - but still have infrequent failure modes.

I suggest you consult textbooks on such hardware and software architectures. They will enlighten you better than anyone on this forum could.

[radiolistener]

It looks like you don't understand how multiprocessor/multithreaded code and hardware can appear to work most of the time - but still have infrequent failure modes.

I suggest you consult textbooks on such hardware and software architectures. They will enlighten you better than anyone on this forum could.

I have worked with multi-threading on various platforms, including Z80, MSP430, PIC, AVR, STM32, x86, and others. I’ve ported and utilized different RTOS kernels on MCUs for various platforms, such as uCOS-II and ChibiOS. Additionally, I developed industrial devices from scratch that run multi-threaded code on RTOS kernels. I also have extensive experience in multi-threading code optimization for different versions of Windows.

I have spent a significant amount of time writing and optimizing commercial multi-threaded code for Windows applications. I have in-depth knowledge of how the thread scheduler works in various versions of Windows and how to optimize code accordingly. I've implemented highly optimized multi-threaded renderers for Direct3D, Direct2D, and OpenGL (it also works well on Linux with no changes), as well as multi-threaded network code.

I am proficient in various synchronization techniques, including lock-free synchronization, and understand advanced techniques for predicting OS scheduler behavior to optimize execution sequences for better performance using adaptive synchronization. I have been working with a wide range of thread synchronization primitives and algorithms for at least the last 25 years. Mutexes, semahores, critical sections, spin-locks, memory barriers, reader-writer locks, different kind of inter process communication - shared memory, pipes, sockets, etc.  I believe my first multi-threaded code for Windows was written around 1997.

And I fully understand that multi-threaded code can behave differently on various machines. My job was precisely to write code that would reliably work on different processors, both single-core and multi-core, with or without multi-threading, on single-processor systems as well as multi-processor servers and in a distributed network environment, where parts of the code run in realtime on different machines, exchanging data with synchronization over the network.

But of course it is possible that I still don't know something about it.
Could you please explain what I don't understand and what I need to read exactly?   

By the way, my first degree was in digital computer design. That was back in the days when digital circuits were designed manually, and we studied and practiced it all without software and CAD tools, using Karnaugh maps, etc.


If you are referring to the limitation of memory bus bandwidth, then yes, it does limit performance with a large number of processors. However, using modern high-speed memory, I don't think it will be a problem to provide a hundred or so Z80 processors with no contention at full-speed memory access. The memory controller itself will certainly be non-trivial, but quite feasible. And for 4-8 processors, I don't see this as a problem with modern memory speeds at all - the total memory bandwidth will be below 30 MB/s.

[radiolistener]

Are you planning to implement it with a real Z80 chips? Because it will be much easier to implement Z80 cores on an FPGA. With a real processor you will have many limitations.

Since such a circuit already requires a lot of logic, it's better to do it all on an FPGA. This way, you can implement the Z80 on the FPGA as well, which will make things easier. And allows other to build your machine more easy and cheaper.

As for "struggling at some point", it is worth calculating how many floating point operations a Z80 can do per second

If you implement Z80 core on FPGA, you can add floating-point hardware accelerator.

Z80 has a lot of unused opcodes which can be used to implement FPU...

I know one Z80-compatible machine that used this approach to implement memory DMA and graphics accelerators with unused Z80 opcodes.

If you are concerned that this won't resemble a real Z80, you can imagine that this co-processor is connected in parallel with the Z80 and, when it detects the necessary instructions, simply halts the Z80 and processes them itself. This approach was often used by the original Z80 chipset

[tggzzz]

It looks like you don't understand how multiprocessor/multithreaded code and hardware can appear to work most of the time - but still have infrequent failure modes.

I suggest you consult textbooks on such hardware and software architectures. They will enlighten you better than anyone on this forum could.

I have worked with multi-threading on various platforms, including Z80, MSP430, PIC, AVR, STM32, x86, and others. I’ve ported and utilized different RTOS kernels on MCUs for various platforms, such as uCOS-II and ChibiOS. Additionally, I developed industrial devices from scratch that run multi-threaded code on RTOS kernels. I also have extensive experience in multi-threading code optimization for different versions of Windows.

I have spent a significant amount of time writing and optimizing commercial multi-threaded code for Windows applications. I have in-depth knowledge of how the thread scheduler works in various versions of Windows and how to optimize code accordingly. I've implemented highly optimized multi-threaded renderers for Direct3D, Direct2D, and OpenGL (it also works well on Linux with no changes), as well as multi-threaded network code.

I am proficient in various synchronization techniques, including lock-free synchronization, and understand advanced techniques for predicting OS scheduler behavior to optimize execution sequences for better performance using adaptive synchronization. I have been working with a wide range of thread synchronization primitives and algorithms for at least the last 25 years. Mutexes, semahores, critical sections, spin-locks, memory barriers, reader-writer locks, different kind of inter process communication - shared memory, pipes, sockets, etc.  I believe my first multi-threaded code for Windows was written around 1997.

And I fully understand that multi-threaded code can behave differently on various machines. My job was precisely to write code that would reliably work on different processors, both single-core and multi-core, with or without multi-threading, on single-processor systems as well as multi-processor servers and in a distributed network environment, where parts of the code run in realtime on different machines, exchanging data with synchronization over the network.

But of course it is possible that I still don't know something about it.
Could you please explain what I don't understand and what I need to read exactly?   

By the way, my first degree was in digital computer design. That was back in the days when digital circuits were designed manually, and we studied and practiced it all without software and CAD tools, using Karnaugh maps, etc.


If you are referring to the limitation of memory bus bandwidth, then yes, it does limit performance with a large number of processors. However, using modern high-speed memory, I don't think it will be a problem to provide a hundred or so Z80 processors with no contention at full-speed memory access. The memory controller itself will certainly be non-trivial, but quite feasible. And for 4-8 processors, I don't see this as a problem with modern memory speeds at all - the total memory bandwidth will be below 30 MB/s.

Please don't choose to omit the relevant context in which I made my statement. That technique is beloved of trolls, and I'm sure you aren't that.

I've repeated the context you omitted below, and highlighted the key points.

If you have all the experience you claim, then surely you realise that the hardware of a multiprocessor/core is the easy part.

I suggest you (re)read the first and subsequent posts in this thread. It is about microprocessors, not cores.

When I wrote word "core" I mean Z80 microprocessor. 

You outline some hardware, without noting the scaling and contention problems as you increase the number of threads and processors.

As I wrote before, the way that I described is well scalable up to 65536 Z80 CPU's and up to 1 GB RAM.

While it might be claimed that cores could be scalable to a small fraction of that number, with microprocessors it isn't sensibly scalable.

After that you need to address the difficult problems: high level (application) and low level (comms mechanism) software.

What difficulties? For example, this architecture allows running multiple ZX Spectrum instances in parallel using their original ROM images without modification. And it won't be able to detect that it's running on a multi-core Z80 machine if you want to lock it. You can use hardware locks for control registers to restrict writes to them from a specific OS ROM page, similar to how it was implemented in TR-DOS for WD1793 ports on the ZX Spectrum.

Memory management and IPC code can be implemented in OS ROM, so the user code can use standard RST call with requested function.

I have experience with implementing such system on Z80 in the past.

It looks like you don't understand how multiprocessor/multithreaded code and hardware can appear to work most of the time - but still have infrequent failure modes.

I suggest you consult textbooks on such hardware and software architectures. They will enlighten you better than anyone on this forum could.

[radiolistener]

Yes, taking everything into account, including frequency and bandwidth limitations, is a challenge. However, nothing is impossible, these problems can be solved one way or another.

What I don't understand is why you chose the Z80 for this.
From my perspective, it would be better to use a 32-bit CPU to build a multi-processor machine with a multi-threading OS.

If you're concerned about compatibility with existing Z80 software, it still won't utilize your multi-threading kernel.


But in the end, if you decide to implement it on the Z80, it will be nice to see another multi-processor Z80 machine.  However, you surely understand that such a machine will not see widespread use in our time, for obvious reasons.

As for implementing multi-threading on a single Z80, it has been done many times. For example, on the ZX Spectrum, there were implementations of something resembling operating systems with multi-threading and a graphical windowed interface similar to Windows. The native 50 Hz interrupt is quite suitable for time-slicing.

[JamesIsAwkward]

For the record this is all a "just for fun" build. Years ago when I started toying with the idea of a custom retro computer I chose the Z80 arbitrarily. Mostly because it seemed nicer to mess with due to its large register set when compared to a 6502.

The constraints of the CPU are the whole reason behind it honestly, it is forcing me to really think through solutions and try to squeeze out performance where I can.

For instance, there aren't any real turn-key ICs that can help do SPI. Instead of bitbanging SPI (which would be very slow for wiznet ethernet or sd card use), I'm trying to design a circuit that allows my Z80 to interface with an SPI device via its full 8-bit data bus in parallel.

To make things harder on me I thought it would be a neat idea to have some "daemons" running in the background on my Z80, for network and printing and whatever else I can cook up lol
Seeing what SymbOS can do completely re-inspired me to continue!


Though in the future I would like to try out a 16-bit or 32-bit CPUs, though I'd like to use some older ones as well.

[JamesIsAwkward]

I will add that I plan to implement a VGA circuit for this build using this little ICE40 dev board I found. I'm cheating on this particular circuit because I really want VGA output. I'm just not a fan of composite video.
Unfortunately I've never messed with FPGA's before so Verilog and VHDL are foreign to me. I've learned a ton about a pretty large array of topics just on this one project alone!

I will still be doing a relatively limited resolution and color depth to make it still feel retro.

[brucehoult]

Years ago when I started toying with the idea of a custom retro computer I chose the Z80 arbitrarily. Mostly because it seemed nicer to mess with due to its large register set when compared to a 6502.

It's largely an illusion, because although there are more, there still aren't *enough*, and once you run out of registers on the Z80, the 6502 handles memory better.

[pqass]

For instance, there aren't any real turn-key ICs that can help do SPI. Instead of bitbanging SPI (which would be very slow for wiznet ethernet or sd card use), I'm trying to design a circuit that allows my Z80 to interface with an SPI device via its full 8-bit data bus in parallel.

See these SPI ideas: here and here.

Also, see attached for my (in progress) SPI implementation for my 8085 SBC (in 3 ICs not including /SS (/CS) line; to be provided via separate output latch). So far I've tested it @2MHz but only the SCLK, MOSI (not MISO) to cascaded '595s (to a multiplexed 14-seg. display). SCLK idles high. Replace 4001 with correct LS NOR gate.

[tggzzz]

For the record this is all a "just for fun" build.
...
The constraints of the CPU are the whole reason behind it honestly, it is forcing me to really think through solutions and try to squeeze out performance where I can.

Excellent justifications, IMNSHO. They were clear from the start

Years ago when I started toying with the idea of a custom retro computer I chose the Z80 arbitrarily. Mostly because it seemed nicer to mess with due to its large register set when compared to a 6502.

I thought something similar w.r.t. the 6800. I was wrong; trying to use the index registers for pointers is such a pain that I preferred using only the 8085 registers. The 6809 was much better in that and other respects, but by then I had moved on to other things.

Those points are very obvious when looking at the instruction maps for the 6800, 8085, 6502, Z80. Unlike the others, the Z80 instruction map is sparse and irregular.

[tggzzz]

Years ago when I started toying with the idea of a custom retro computer I chose the Z80 arbitrarily. Mostly because it seemed nicer to mess with due to its large register set when compared to a 6502.

It's largely an illusion, because although there are more, there still aren't *enough*, and once you run out of registers on the Z80, the 6502 handles memory better.

Another illusion that I remember seducing (other) people was that REP prefix plus OUT instruction made a one-instruction PRINT statement.

The 9900 handled memory better than the 6502: since the registers were in memory, a context switch only had to change one register. That was fine when processor speeds matched memory speed, but had ... limitations ... when processors became faster than memory

[brucehoult]

The 9900 handled memory better than the 6502: since the registers were in memory, a context switch only had to change one register. That was fine when processor speeds matched memory speed, but had ... limitations ... when processors became faster than memory

I've seen and touched a TMS9900 machine ... I guess a TI-99/4 ... in 1981 or 1982 but it wasn't in operation. It already had a reputation then of being slow, though looking at it now I can't quite understand why.

The ISA isn't stupid, it's very similar to PDP-11 or MSP430 (or M68k for that matter). PDP-11 2-operand instructions have 3 bits for register and 3 bits for addressing mode, for each of src and dst, plus a 3 bit opcode and 1 bit to indicate byte/word [1]. The TMS9900 increases register number to 4 bits and decreasing the number of addressing modes from 8 to 4 (2 bits), for both src and dst operands, keeping the number of opcode bits the same. The MSP430 reduces dst addressing modes to 2 (1 bit) and gives that bit to the opcode field, allowing more 2-operand instructions.

The implementation doesn't even seem all that stupid for the time. Yes, RAM could be clocked just as fast as CPUs. Something like "{add,sub,mov,cmp} r3,r10" took 14 clock cycles with 4 memory operations, single operand "{inc,dec,not,clr} r7" took 10 clock cycles with 3 memory accesses.

In general, instructions took 3 clock cycles per memory access, plus a couple. So at the usual 3 MHz that was 1 µs per memory access, or 4.67 µs for a register to register add etc. That's slow compared to a register-to-register add or move on 8086 (3 cycles) or M68k (4 cycles) but those CPUs came a bit later and used far more transistors. TMS9900 was 3100 gates (8000 transistors) vs 6502's 4528 transistors and Z80's 8500 transistors. 8086 was 29000 transistors and M68k (apparently!) 68000.

So comparing TMS9900 against 6502, it does quite well. To add two 16 bit variables in Zero Page the 6502 needs 7 instructions, 13 bytes of code, 11 clock cycles, and therefore 11 µs. The TMS9900's 1 instruction, 2 bytes of code, 14 clock cycles, 4.67 µs looks far better in every way.

The Z80 can add any of {BC,DE,HL,SP} to HL in 1 byte of code, 11 cycles, 3.67 µs at 3 MHz. But it's far more restrictive than the TMS9900 which can add any of 16 registers to any other of 16 registers. The Z80 very often needs additional instructions to organise things, and if you have very many variables at all needs to go to RAM far less efficiently.

So, given that the TMS9900 was introduced in 1976 it was actually a pretty good choice at the time, at least based on speed. Its problems lay more in the large package, multiple supply voltages (like 8080 and 6800 ... Z80 and 6502 were just +5V), and needing 16 bit wide RAM.



[1] except what you'd expect to be "ADDB" is actually "SUB", there are no byte ADD/SUB. I helped fix a bug (locally) in the PDP-11 NBS Pascal compiler where it tried to add char variables by generating what it thought would be "ADDB".

[tggzzz]

That was also my assessment of the TI9900.

Never had the chance to use one. Talked with someone who was given no choice. His principal complaint was that the development system was significantly cruder than CP/M in that it didn't allow batch commands, which was a pain during the compile-debug cycle. As always, the libraries and tools are as important as the processor and instruction set.

BTW, the 8080 requires +12,+5,-5V supplies. That was the principal reason I chose the 6800 for my first computer. The 1802 was the other contender, but general purpose subroutine calls were... convoluted.

The later 8085 only needed +5V. I have three unused ceramic NS 8080s, and that used 6800. I ought to flog the 8080s

[JamesIsAwkward]

@pqass thanks for the links to some SPI circuits! Have you had any issue with timing when using the sysclock to also clock the SPI clock? The ecstaticlyrics page mentions having to add NOPs due to timing issues on faster clocks.
I really don't think I'll ever use an SD card directly but I'd like to have "fast SPI" so that I can use an SPI network interface and get this machine on the internet somehow. I think it would be really fun to build an IRC client and connect to libera! I could write a full TCP/IP stack but that would probably murder my cpu performance so its easier to just let an external module handle that.

It's largely an illusion, because although there are more, there still aren't *enough*, and once you run out of registers on the Z80, the 6502 handles memory better.

Yeah I actually started this whole thing in 2018 or so, and I had no idea what I was doing, and I didn't spend much time on it. I just chose the Z80 cause it LOOKED better lol! I was toying with the idea of using a 6502 as the GPU but it seemed complicated and is probably easier to just use an I/O device.

[pqass]

I'm using a 4.096MHz xtal on the 8085 which is divided by 2 internally and made available on CLKOUT (pin 37). I use SYSCLK=CLKOUT which is input to the '163 (pin 2).   Correction: the SPI SCLK is actually SYSCLK (pin 2) of the '163 divided by 2, the Q0 output (pin 14), so I'm actually running the SPI SCLK at 1.024MHz.

While /CS and /WR are asserted (LOW), S0,S1=H,H which loads the '299 from the data bus. As soon as /CS or /WR are de-asserted (either HIGH), then S0,S1=H,L which starts the shift left on the next '299 clock rise (which is SYSCLK/2). Therefore you'll need 16 SYSCLK clocks to push out the 8 bits.

An OUT instruction (on an 8085) is 4+3+3=10 SYSCLKs (fetch+memrd+iowr) so you'll have to put a minimum two NOPs (2 fetches, 4 SYSCLKs each) before calling the next OUT. With a Z80, OUT (D3 opcode) is 4+3+4=11 SYSCLKs so you'll still need to call two NOPs before the next OUT.  Not sure about the other OUT opcodes; some have 16 clocks and may not need any NOP padding!  You'll still need to get your data from somewhere first (and toggle /SS too via separate output latch pin) so it'll be something else that'll consume some clocks.

Upon reflection, maybe if 0x8 is preloaded into the '163 on reset (we rely on the TC output) then you may be able to run SPI SCLK=SYSCLK (not /2 from Q0).

The ecstaticlyrics implementation uses two OUTs to prep the byte then trigger the send whereas my implementation will prep/send immediately following a single OUT instruction.  Also he uses an independent SPI clock (vs me using the CPU clock/2) and says you may need NOPs if the CPU clock approaches or is greater than the SPI clock.

There are a lot of delicious io devices available via SPI (like this Ethernet, TCP/IP stack included).

[woofy]

I will add that I plan to implement a VGA circuit for this build using this little ICE40 dev board I found. I'm cheating on this particular circuit because I really want VGA output. I'm just not a fan of composite video.
Unfortunately I've never messed with FPGA's before so Verilog and VHDL are foreign to me. I've learned a ton about a pretty large array of topics just on this one project alone!

I will still be doing a relatively limited resolution and color depth to make it still feel retro.

I did something similar a while ago, using a Z80 and an off-the-shelf iCE40 module for most of the interfacing. The fpga handles memory paging to the 512k byte RAM chip as well as ps2 keyboard and vga. It even had a small boot program embedded in the bit stream to start up the Z80 and load the OS. I used a 20MHz 5v Z80 which I ran at 12MHz and 3.3v, it worked and made fpga interfacing a breeze.

I'd be happy to share the verilog when you get to that stage.

[SiliconWizard]

For the record this is all a "just for fun" build. Years ago when I started toying with the idea of a custom retro computer I chose the Z80 arbitrarily. Mostly because it seemed nicer to mess with due to its large register set when compared to a 6502.

Yes the "for fun" part is understandable, and impossible to question. It's personal.
As to the Z80 being nicer than the 6502, it's all a matter of perspective. I did, overall, prefer the instruction set of the Z80 for hand-writing assembly, but the 6502 was much more efficient per clock cycle. If I had to write a multitasking OS on a 8-bit MCU, I would probably pick the Z80 over the 6502 without a question. Actually, I would probably go for the 6809: it was more powerful, had a better instruction set, and I've never directly programmed one in the past (contrary to the others), so that would be a "learning" experience too!

For instance, there aren't any real turn-key ICs that can help do SPI. Instead of bitbanging SPI (which would be very slow for wiznet ethernet or sd card use), I'm trying to design a circuit that allows my Z80 to interface with an SPI device via its full 8-bit data bus in parallel.

I don't think there is either, but you can design that around a discrete shift register and some glue logic (if you want to use a "vintage" approach), or you could of course implement this in a small FPGA/CPLD.

[Jonathon_Doran]

There were plenty of design issues with the 99/4A.  Most people didn't realize that while their BASIC programs were interpreted, the BASIC interpreter itself was written in an interpreted language.
Much of the I/O had to go through the 9918A which meant that you had to setup memory and then interrupt the 9918A.  There was no direct access.

I remember buying the Editor/Assembler (needed for assembly language programming) and then reading on page 1 "We assume that you know assembly language."   This was before the internet...

I would have a lot more fun with that machine now.  40 years of experience is a good equalizer.

I've had similar thoughts as the OP about vintage computing.  I was thinking of a 6502 with an external MMU and VGA graphics.  But I would have cheated and done the graphics on an FPGA because I couldn't have breadboarded a decent resolution.

[brucehoult]

There were plenty of design issues with the 99/4A.  Most people didn't realize that while their BASIC programs were interpreted, the BASIC interpreter itself was written in an interpreted language.
Much of the I/O had to go through the 9918A which meant that you had to setup memory and then interrupt the 9918A.  There was no direct access.

Ah, so nothing to do with the CPU itself.

From 1976 until the 8086 and 68000 became available to normal people in the early 80s, the TMS9900 looks like it should have been more than a match for the 6502 and Z80, and far far easier to program.

[bson]

Most OSes from the 1970s to this day switch CPU-bound tasks (that finish their time slice) 100 times a second. So on the Z80 you'll use 1% of the CPU time to do that task switching.

They used to interrupt on the line frequency, so 60 or 50Hz.  Because things like programmable timers were too expensive and frivolous, a heartbeat interrupt was used and all timing done in software.  This doesn't mean every tick resulted in a thread switch (used loosely here, meaning execution context since we've seen confusion over this term before).  With the advent of programmable timers, nobody designs systems like this anymore.

In a modern RT system, if only one thread (execution context) is active, there is no need for context switching and the timer doesn't need to run at all - at least not for this.
If a higher priority thread is activated by an interrupt, a switch to it is made, and no timer is needed.
If a lower priority thread is activated by an interrupt, no switch is made, and no timer is needed.
If a thread of the same priority is activated and the scheduler implements round-robin, it can implement a round-robin policy for these threads, and give it a quantum for which a timer is used to signal its end and that a RR context switch is needed.

The timer might still be running, to keep time - it can interrupt close to rollover, with some margin, to update a value in memory and restart.  At any point, the current time, in ticks, is that of the value in memory plus that of the timer.

Or a separate 32-bit timer, such as the core ARM SYSTICK, can be used exclusively to keep time, with a huge rollover margin.

NOBODY designing modern systems has a fixed heartbeat.  It's simply not necessary with the existence of programmable timers.