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.)