[Staff] [Ideas] Primitive Multithreading

[tr1p1ea]

I have thought about multi-threading on calc a little, but never considered putting it into practice. This is a cool achievement ben, even if it is just for the sake of it .

Perhaps you could tie a small amount of information to each thread, outlining any saferam areas it uses and how much, whether or not it uses TIOS romcalls, stack usage etc?

[KermMartian]

Mmm, that's a good idea. 'Twould definitely help avoid conflicts between the threads.

[benryves]

I haven't had much time (work!) to work on this project any more, but have extended it to add any number of threads and allocate memory for the register store and stack (in the form of programs named Thrd<random four-digit number>). You can't currently clean up threads, but I'm thinking the best way to do this would be to push data/VAT address of the temporary file to the new stack, and then an address of a cleanup routine.

[benryves]

Hm, here's a better idea for storing variables between threads - use the index registers!

That way, the memory allocated for the thread would be set up like this:

Code: Select all

+----------------+-. 
|                |  \      16 bytes
| Register store |   > (PC, SP, AF, BC,
|                |  /   DE, HL, IX, IY)
+----------------+-:
| Variable space |  \ 
|                |   IX points to the start
| |Grows  down|  |   of the variable space.
: v           v  :
:                :
: ^           ^  :
| | Grows  up |  |   SP points to the end
|                |   of the stack space.
|  Stack space   |  / 
+----------------+-'

Better would be to offset IX by 128 bytes, so you could use the full -128..127 range, but it's less confusing for users if it points to the start (and they can move it if they so wish).

[kv83]

Hmmm... i'm to stupid to get that Could you explain in more detail

[benryves]

Once the new thread has been created, some memory is allocated (it needs to be, for that thread's stack). If I also preload the new thread's IX register (as each thread is swapped, the registers are also swapped - so each thread has its own set of registers) to point at the block of memory allocated for the stack, you can also use that memory to store variables, using ix and an offset to point to different variables. This way, each thread can also have its own local variables.

[Jim e]

ewww...Lose a register?? Never! Well wait, I guess it wouldn't be totaly gone, just if you are using it in a isolated routine that only uses memory that locked in like Plotsscreen.

So I imagine it could work ok, but its adding a level of abstraction to something that wasn't greatly needed. For practicality sake couldn't threads just be expected to get along?

[benryves]

You can do whatever you like with IX. Much like SP, PC and IY, I'm talking about the preloaded state of the registers. Before a thread is allowed to start, IY (so the TIOS routines don't break), PC and SP are all set up and copied to the register store area in the freshly allocated thread memory.

All I'm saying is that for simplicity, when a new thread starts it has IX pointing to an area of memory it can use to store variables. Yes, this means that you can't use this and expect to be able to modify IX (that's the "losing a register" part), but there are ways around that. You could also easily make a thread only let itself run once by making the first instruction a NOP, and to set it to RET when it's run. That way, successive threads terminate instantly. When the thread exits, it would then need to set the first instruction back to NOP again.

[Kalimero]

...an area of memory it can use to store variables...

That would be Thread Local Storage (TLS) (just to give the child a name) and using one of the index registers is the most logical way to implement it imo.

[Timendus]

Impressive little demo, Ben. Amazing. I too have been thinking about this, but never saw a need for it and didn't really know where to start... Respect

[Timendus]

Hmm, I recently had a class about primitive multithreading, and I was also pondering (as one does ) whether it wouldn't be much easier to start with threads that are nice to each other by issuing a SLEEP once in a while which gives a scheduler the chance to make the context switch if it sees fit to do so. I'd expect such a system to be more efficient in many situations (you could use busy waits like waiting for a keypress for something useful), and easier to extend to more than two threads... Also it shouldn't require fidling with the interrupts, which would make things faster and easier to work with, and you wouldn't have to worry about locking critical sections and whatnot...

*Envisions himself trying to debug lock errors in assembly
*Screams and slaps himself back into reality

That's the one thing I'm extremely happy to have been able to avoid in my experiments with calculator networking

[qarnos]

I hope it's not too late to resurrect this thread (and it's too late to stop me if it is ).

I just had a thought today about implementing mutual exclusions (mutexes) in Z80 code. Mutexes are usually implemented using an atomic test-and-set instruction, which the Z80 lacks, but we can do an implicit test-and-set using SMC.

The idea is to create the mutex using an instruction that overwrites itself with something else. Obviously, the original instruction will be an LD, and we want to replace it with something useful. The caveat is that the new instruction must only be one byte, since we need to do this in one instruction. We could use two-bytes if you use an immediate address (like ld (xxxx), hl), but then the mutexes must be hard-coded.

The (or A) solution is to use a RET instruction ($c9). A mutex then consists of 4 bytes:

Code: Select all

mutex:
        ld      (hl), $c9   ; overwrite self with "ret" insn.
        scf
        ret

The caller of the mutex loads HL with the mutex address and resets the carry flag before calling. If the carry flag is set on return, the mutex has been acquired.

I've written 3 high-level routines (acquire_mutex, timeout_mutex and release_mutex) to manipulate the mutexes. They seem to work fine in PTI, though I haven't had a chance to test them in multi-threaded code, since I don't have any!

Code: Select all

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; acquire_mutex:
;;
;;  This routine will block until the mutex is acquired.
;;
;; INPUTS:
;;
;;  REGISTERS
;;
;;  * HL    - address of mutex to acquire.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
acquire_mutex:
        or      a
        call    $ + $0006               ; indirect call to hl (see below)
        jr      nc, acquire_mutex
        ret
        jp      (hl)
        

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; timeout_mutex:
;;
;;  This routine will block until the mutex is acquired or the timeout
;;  period elapses.
;;
;; INPUTS:
;;
;;  REGISTERS
;;
;;  * A     - timeout value (0 == 256).
;;  * HL    - address of mutex to acquire.
;;
;; OUTPUTS:
;;
;;  REGISTERS
;;
;;  * F     - carry flag set if mutex was acquired.
;;          - carry flag clear if timeout elapsed.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
timeout_mutex:
        or      a
        call    $ + $0008           ; indirect call to hl (see below)
        ret     c
        dec     a
        jr      nz, timeout_mutex
        ret
        jp      (hl)
        

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; release_mutex:
;;
;;  Releases an acquired mutex.
;;
;; INPUTS:
;;
;;  REGISTERS
;;
;;  * HL    - address of mutex to release.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
release_mutex:
        ld      (hl), $36   ; overwrite mutex with LD (hl), $c9
        ret

I guess you could also write an init_mutex routine to create mutexes on-the-fly. Just load the target address with the byte sequence: $36, $c9, $37, $c9.

Another variation (which I trialled before settling on this) is to use immediate addressing as described above to write a two-byte instruction. $fe18 would give you a nice succinct infinite loop (JR pc-2), but makes implementing timeouts somewhat impossible. On the other hand, it would allow the scheduler to check for blocked threads (just check for $fe18 and the PC before executing the thread) and not waste run-time on them.

[Timendus]

That is awesome
I haven't been here for ages, but multithreading in z80 still triggers my attention

[benryves]

Clever, though I can't help thinking it would be simpler to just disable interrupts during critical sections.

[King Harold]

Well here's proof of that:

Code: Select all

di
CS
ei

And that's it.

But it has a nasty downside compared to many other ways of implementing critical sections, you would disable all threads - also threads that have nothing to do with it and aren't even trying to enter a critical section at all (or a different section)